On the Wrong Key Randomisation and Key Equivalence Hypotheses in Matsui’s Algorithm 2

Andrey Bogdanov, Elmar Tischhauser

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


This paper aims to improve the understanding of the complexities for Matsui’s Algorithm 2 — one of the most well-studied and powerful cryptanalytic techniques available for block ciphers today. We start with the observation that the standard interpretation of the wrong key randomisation hypothesis needs adjustment. We show that it systematically neglects the varying bias for wrong keys. Based on that, we propose an adjusted statistical model and derive more accurate estimates for the success probability and data complexity of linear attacks which are demonstrated to deviate from all known estimates. Our study suggests that the efficiency of Matsui’s Algorithm 2 has been previously somewhat overestimated in the cases where the adversary attempts to use a linear approximation with a low bias, to attain a high computational advantage over brute force, or both. These cases are typical since cryptanalysts always try to break as many rounds of the cipher as possible by pushing the attack to its limit. Surprisingly, our approach also reveals the fact that the success probability is not a monotonously increasing function of the data complexity, and can decrease if more data is used. Using less data can therefore result in a more powerful attack. A second assumption usually made in linear cryptanalysis is the key equivalence hypothesis, even though due to the linear hull effect, the bias can heavily depend on the key. As a further contribution of this paper, we propose a practical technique that aims to take this into account. All theoretical observations and techniques are accompanied by experiments with small-scale ciphers.
Original languageEnglish
Title of host publicationFast Software Encryption. Revised Selected Papers
Publication date2014
ISBN (Print)978-3-662-43932-6
ISBN (Electronic)978-3-662-43933-3
Publication statusPublished - 2014
Event20th International Workshop on Fast Software Encryption (FSE 2013) - Singapore, Singapore
Duration: 10 Mar 201313 Mar 2013
Conference number: 20


Workshop20th International Workshop on Fast Software Encryption (FSE 2013)
SeriesLecture Notes in Computer Science


  • Block ciphers
  • Linear cryptanalysis
  • Data complexity
  • Wrong key randomisation hypothesis
  • Key equivalence
  • Linear hull effect


Dive into the research topics of 'On the Wrong Key Randomisation and Key Equivalence Hypotheses in Matsui’s Algorithm 2'. Together they form a unique fingerprint.

Cite this