On the Complexity of Matsui's Attack
|
|
|
This paper presents both experimental and theoretical original
results on Matsui's linear cryptanalysis of
the Data Encryption Standard. It superseeds the results of my diploma thesis.
|
|
|
Bibliographical References
|
|
|
P.�Junod. On the complexity of Matsui's attack. In S.�Vaudenay and A. Youssef,
editors, "Selected Areas in Cryptography: 8th Annual International Workshop,
SAC 2001, Toronto, Ontario, Canada, August 16-17, 2001. Revised papers", volume
2259 of Lecture Notes in Computer Science, pages 199-211. Springer-Verlag, 2001.
|
|
|
Abstract
|
|
|
Linear cryptanalysis remains the most powerful attack against DES
at this time. Given $2^{43}$ known plaintext-ciphertext pairs,
Matsui expected a complexity of less than $2^{43}$ DES evaluations
in 85 % of the cases for recovering the key. In this paper, we
present a theoretical and experimental complexity analysis of this attack, which
has been simulated 21 times using the idle
time of several computers. The experimental results suggest a complexity upper-bounded
by $2^{41}$ DES evaluations in 85 % of the case, while more than the half of the
experiments needed less than $2^{39}$ DES evaluations. In addition, we give
a detailed theoretical analysis of the attack complexity.
|
|
|
Download
|
|
|
Paper (version published in the proceedings of SAC'01)
|
 
|
|
Talk given at SAC'01, August 16, Toronto, Canada, 2001
|
|
|
Talk given at the Workshop on Cryptographic Protocols, March 18-23, Monte-Verita, Ascona, Switzerland, 2001
|
|
|
Talk given at the Rump Session of ASIACRYPT'00, December 5, Kyoto, Japan, 2000
|
|
|
Abstract by SpringerLink
|
[Link]
|
|
Bibtex entry
|
[Bib]
|
|
|
Last updated September 15th, 2004
|
