Cryptology ePrint Archive: Report 2016/990

Revisiting the Wrong-Key-Randomization Hypothesis

Tomer Ashur and Tim Beyne and Vincent Rijmen

Abstract: Linear cryptanalysis can be 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 the more natural setting of sampling without replacement. This paper derives the distribution for the observed bias for wrong keys when sampling is done without replacement and shows that less data is required when duplicate pairs are discarded. 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, 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.

Category / Keywords: secret-key cryptography / linear cryptanalysis, wrong-key-randomization hypothesis, success probability, data complexity

Date: received 13 Oct 2016

Contact author: tim beyne at student kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20161017:193156 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]