Linear cryptanalysis is a known plaintext attack 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.

Linear cryptanalysis was first devised by Matsui and Yamagishi (MY92) in an attack on FEAL. It was extended by Matsuito attack DES. 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 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.

history | show excerpt | excerpt history