Linear Cryptanalysis - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 135

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 struc-
tures.
Ideally, a cipher would have nearly perfect diffusion and confusion; that is, there would be no easy way to
make predictions about the output based on the input without knowing the key. However, no cipher can have
truly perfect diffusion; there will also be some imperfections in the structures. The nature of these weaknesses
and how to exploit them yield the different attacks.
This chapter explains and demonstrates the method of linear cryptanalysis. We also look at how effective the
method is against many ciphers. Finally, I show several extensions and alterations of the method used to increase
its effectiveness.
6.1 Overview
Linear cryptanalysis was first explained and demonstrated in References [4] and [5]. It is a known-plaintext at-
tack, meaning that we will have some set of plaintexts and associated ciphertexts, all encrypted with the same
key, which is what we wish to discover. Another good source on linear cryptanalysis (and differential) is Howard
Heys [1], which provides a nice development framework for learning this technique through simpler ciphers first
(which is how I'll approach the subject).