Paper 2016/990

Revisiting the Wrong-Key-Randomization Hypothesis

Tomer Ashur, Tim Beyne, and Vincent Rijmen

Abstract

Linear cryptanalysis is considered to be one of the strongest techniques in the cryptanalyst’s arsenal. In most cases, Matsui’s Algorithm 2 is used for the key recovery part of the attack. The success rate analysis of this algorithm is based on an assumption regarding the bias of a linear approximation for a wrong key, known as the wrong-key-randomization hypothesis. This hypothesis was refined by Bogdanov and Tischhauser to take into account the stochastic nature of the bias for a wrong key. We provide further refinements to the analysis of Matsui’s Algorithm 2 by considering sampling without replacement. This paper derives the distribution of the observed bias for wrong keys when sampling is done without replacement and shows that less data are required in this scenario. It also develops formulas for the success probability and the required data complexity when this approach is taken. The formulas predict that the success probability may reach a peak and then decrease as more pairs are considered. We provide a new explanation for this behavior and derive the conditions for encountering it. We empirically verify our results and compare them to previous work.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in JOC 2020
Keywords
linear cryptanalysiswrong-key-randomization hypothesissuccess probabilitydata complexity
Contact author(s)
tim beyne @ esat kuleuven be
History
2020-02-12: revised
2016-10-17: received
See all versions
Short URL
https://ia.cr/2016/990
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/990,
      author = {Tomer Ashur and Tim Beyne and Vincent Rijmen},
      title = {Revisiting the Wrong-Key-Randomization Hypothesis},
      howpublished = {Cryptology ePrint Archive, Paper 2016/990},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/990}},
      url = {https://eprint.iacr.org/2016/990}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.