2.4.5 What are the most important attacks on symmetric block ciphers?
There are several attacks which are specific to block ciphers (see Question 2.1.4). Four such attacks are differential cryptanalysis, linear cryptanalysis, the exploitation of weak keys, and algebraic attacks.
Differential cryptanalysis is a type of attack that can be mounted on iterative block ciphers (see Question 18.104.22.168. These techniques were first introduced by Murphy [Mur90] in an attack on FEAL-4 (see Question 3.6.7), but they were later improved and perfected by Biham and Shamir [BS91a] [BS93b] who used them to attack DES (see Section 3.2). Differential cryptanalysis is basically a chosen plaintext attack (see Question 2.4.2); it relies on an analysis of the evolution of the differences between two related plaintexts as they are encrypted under the same key. By careful analysis of the available data, probabilities can be assigned to each of the possible keys, and eventually the most probable key is identified as the correct one.
Differential cryptanalysis has been used against a great many ciphers with varying degrees of success. In attacks against DES, its effectiveness is limited by very careful design of the S-boxes during the design of DES in the mid-1970s [Cop92]. Studies on protecting ciphers against differential cryptanalysis have been conducted by Nyberg and Knudsen [NK95] as well as Lai, Massey, and Murphy [LMM92]. Differential cryptanalysis has also been useful in attacking other cryptographic primitives such as hash functions (see Section 2.1.6).
Matsui and Yamagishi [MY92] first devised linear cryptanalysis in an attack on FEAL (see Question 3.6.7). It was extended by Matsui [Mat93] to attack DES (see Section 3.2). Linear cryptanalysis is a known plaintext attack (see Question 2.4.2) which 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 that 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. Other issues such as protecting ciphers against linear cryptanalysis have been considered by Nyberg [Nyb95], Knudsen [Knu93], and O'Conner [Oco95].
Weak keys are secret keys with a certain value for which the block cipher in question will exhibit certain regularities in encryption or, in other cases, a poor level of encryption. For instance, with DES (see Section 3.2), there are four keys for which encryption is exactly the same as decryption. This means that if one were to encrypt twice with one of these weak keys, then the original plaintext would be recovered. For IDEA (see Question 3.6.7), there is a class of keys for which cryptanalysis is greatly facilitated and the key can be recovered. However, in both these cases, the number of weak keys is such a small fraction of all possible keys that the chance of picking one at random is exceptionally slight. In such cases, they pose no significant threat to the security of the block cipher when used for encryption.
Of course, for other block ciphers, there might well be a large set of weak keys (perhaps even with the weakness exhibiting itself in a different way) for which the chance of picking a weak key is too large for comfort. In such a case, the presence of weak keys would have an obvious impact on the security of the block cipher.
Algebraic attacks are a class of techniques that rely for their success on block ciphers exhibiting a high degree of mathematical structure. For instance, it is conceivable that a block cipher might exhibit a group structure (see Section A.3). If this were the case, then encrypting a plaintext under one key and then encrypting the result under another key would always be equivalent to single encryption under some other single key. If so, then the block cipher would be considerably weaker, and the use of multiple encryption would offer no additional security over single encryption; see [KRS88] for a more complete discussion. For most block ciphers, the question of whether they form a group is still open. DES, however, is known not to be a group; see Question 3.2.5.