What is Linear Cryptanalysis?

Linear cryptanalysis was first devised by Matsui and Yamagishi [MY92] in an attack on FEAL (see Question 79). It was extended by Matsui [Mat93] to attack DES (see Question 64). Linear cryptanalysis is a known plaintext attack (see Question 63) and uses a linear approximation to describe the behavior of the block cipher. Given sufficient pairs of plaintext and corresponding ciphertext, bits of information about the key can be obtained and increased amounts of data will usually give a higher probability of success.

There have been a variety of enhancements and improvements to the basic attack. Langford and Hellman [LH94] introduced an attack called differential-linear cryptanalysis which combines elements of differential cryptanalysis (see Question 58) with those of linear cryptanalysis. Also, Kaliski and Robshaw [KR94] showed that a linear cryptanalytic attack using multiple approximations might allow for a reduction in the amount of data required for a successful attack.

| Question 60 |