Modern Cryptanalysis: Techniques for Advanced Code Breaking

Chapter 6. Linear Cryptanalysis

The previous chapters introduced some general methods of analyzing block ciphers. The methods were "general" in that there was not a lot of analysis of a specific cipher; the attacks work equally well on many different classes of ciphers. Any errors exploited weren't so much inherent to the ciphers: Detailed analysis of the ciphers was not what yielded these attacks.

While there are many cryptanalytic strategies that might rely on deep analysis of a cipher, I wish to focus on a few different classes of these ciphers. In this chapter, I'll discuss a very important class of newer cryptanalysis methods — linear cryptanalysis.

Linear cryptanalysis is a known-plaintext attack first detailed by Mitsuru Matsui and Atsuhiro Yamagishi in the early 1990s against FEAL and DES [4,5]. This formal method attempts to relate the inputs and outputs of algorithm components together so that solving a system of linear equations will yield information about the bits of the key used to encrypt them.

Linear cryptanalysis is also a statistical attack: It is not guaranteed to work in every single case. However, it does work most of the time, which I'll define more precisely below.

Previous methods did not rely on deficiencies of the cryptographic algorithm, at least in the same way. The methods in this and the next chapter are designed to take advantage of weaknesses in some of the cipher structures.

Ideally, a cipher would have nearly perfect diffusion and confusion; that is, ...