[Next] [Up/Previous] [Index]
The technique of differential cryptanalysis, in addition to being very powerful by itself, has served as a basis for the development of even more powerful techniques, such as those surveyed here and in the next section.
It is of course possible that some of the bits of E(A,k) xor E(B,k) will be more likely to match those of Y than others. If one can, in addition, ignore some of the bits of A and B, one has a truncated differential for the cipher being attacked, and this technique, due to Lars R. Knudsen, has been found to be very powerful. (Being able to ignore some bits of A and B may allow two or more truncated differentials to be used together, and this is why it is important.)
Another important addition to the available techniques deriving from differential cryptanalysis is the use of higher-order differentials, which first appeared in a paper by Xuejia Lai.
A differential characteristic of the type described above, where for a large number of different values of A, B equals A xor X, and the encrypted versions of A and B for a given key, k, are expected to have the relation E(A,k) = E(B,k) xor Y, if a target statement about the key k is true, can be made analogous to a derivative in calculus, and then it is termed that Y is the first derivative of the cipher E at the point X.
A second-order derivative would then be one involving a second quantity, W, such that E(A,k) xor E(B,k) = E(C,k) xor E(D,k) xor Z is expected to be true more often than would be true due to chance, where not only is B = A xor X, but C = A xor W and D = B xor W. In that case, Z is the second derivative of the cipher E at the point X,W. Since xor performs the function of addition and subtraction, the four items encrypted for any A are just lumped together in this case, but if differential cryptanalysis were being performed over another field where the distinction is significant, then Y=E(A+X,k)-E(A,k) and Z=(E(A+X+W,k)-E(A+W,k))-(E(A+X,k)-E(A,k)) would be the appropriate equations to use. This technique is important because a second order derivative can exist at a point for the first coordinate of which no first order derivative exists, or is probable enough to be useful.
And similarly, a third order derivative is derived from the difference of two second order derivatives, based on another constant difference, and so on.
Recently, a means of improving the flexibility of differential cryptanalysis was discovered by David A. Wagner. Called the boomerang attack, it allows the use of two unrelated characteristics for attacking two halves of a block cipher.
This diagram shows how the attack might work if everything goes perfectly for a particular initial block. The numbered points in the diagram show the steps involved in the attack.
This increases the potential effectiveness of differential cryptanalysis, because one can make use of characteristics that do not propagate through the complete cipher. Also, certain kinds of added complexities, such as a bit transpose in the middle of the cipher, do not serve as a barrier to this method, since two values differing by an XOR with some value merely differ by an XOR with some other value after a bit transpose.
However, it has its limitations. It only produces a result if both characteristics are present; it does not allow testing for each characteristic independently. Even so, it seems to double the number of rounds a cipher needs to be considered secure.
Since at one end of a sequence of rounds, the precise difference between blocks that is required for the characteristic must be input, it isn't possible directly to cascade this method to break a block cipher into four or more pieces.
Note that any single Feistel round has a large family of "characteristics" that is 100% probable, but which tells nothing about the key, since any pattern that involves leaving the half that is input to the F-function unchanged, but involves an XOR to the half that is XORed with the output of the F-function applies, so one of the things this method can do is allow the use of attacks against the first or last 15 rounds of DES against 16-round DES. Hence, if by some other trick a block cipher with 16 rounds could be broken into 16 pieces like this, one could test for an informative characteristic which applied to any single round.
Skip to Next Chapter
Table of Contents