Are there any practical examples of breaking a system using linear attacks?

Question

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?

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.