Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've read some papers about linear cryptanalysis. But since I am going to give a lecture about it I am looking for an example of breaking a system using this attack. Is there such an example available?

share|improve this question

1 Answer 1

The most well known example of a cipher practically broken with linear attacks is by no doubt DES, a cipher with 56-bit key and 64-bit block. Equipped with a cluster of PCs in the year 1994, Mitsuru Matsui has experimentally found a secret key after 10 days of the analysis (the data generation took additional 40 days on the same machine set).

By that time the behaviour of linear attacks was not well understood, but eventually a simple concept emerged. Given $N$ (plaintext,ciphertext) pairs of 64-bit blocks, a cryptanalyst obtains a list of candidate keys ordered by their likelihood to be the right key. There are estimates of the probability $P$ that the right key is among top $R$ candidates. Clearly, $P$ increases as $N$ or $R$ grows, and it is in fact the success rate of the attack under parameters $(N,R)$.

A comprehensive treatment of this subject has been given by Junod in his PhD thesis, where Figure 3.3, p.80, provides a plot of the success rate given fixed $N =2^{40}..2^{45}$. Both theoretical and implementation details are given in Section 3.2 of the same text.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.