A method for the cryptanalysis of block ciphers introduced by Mitsuru Matsui in the EUROCRYPT '93 paper: "Linear Cryptanalysis Method for DES Cipher". This attack seems to be the most effective (so far) known plaintext attack against DES, capable of breaking an 8-round DES variant with 221 known plaintexts and full 16-round DES with 247 known plaintexts. The attack works by attempting to find linear approximations to the cipher given plaintext and ciphertext pairs, creating a simpler approximation to the cipher, where it is easy to derive the key from. Those approximations that tend to hold true are likely to have the value of the key for the real cipher, and as more and more plaintext-ciphertext pairs are obtained, the better the approximations get, and the more likely the real key has been found.

As the only nonlinear elements in most block ciphers are the s-boxes (as is the case in DES, Rijndael, and CAST) it is sufficient to generate approximations to the s-boxes to perform the attack. After Mitsui's paper was written new ciphers were created that incorporated resistance to linear cryptanalysis as a design decision.

Log in or registerto write something here or to contact authors.