Abstract
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 language | English |
---|---|
Title of host publication | Fast Software Encryption. Revised Selected Papers |
Publisher | Springer |
Publication date | 2014 |
Pages | 19-38 |
ISBN (Print) | 978-3-662-43932-6 |
ISBN (Electronic) | 978-3-662-43933-3 |
DOIs | |
Publication status | Published - 2014 |
Event | 20th International Workshop on Fast Software Encryption (FSE 2013) - Singapore, Singapore Duration: 10 Mar 2013 → 13 Mar 2013 Conference number: 20 |
Workshop
Workshop | 20th International Workshop on Fast Software Encryption (FSE 2013) |
---|---|
Number | 20 |
Country/Territory | Singapore |
City | Singapore |
Period | 10/03/2013 → 13/03/2013 |
Series | Lecture Notes in Computer Science |
---|---|
Volume | 8424 |
ISSN | 0302-9743 |
Keywords
- Block ciphers
- Linear cryptanalysis
- Data complexity
- Wrong key randomisation hypothesis
- Key equivalence
- Linear hull effect