[Next] [Up/Previous] [Index]

Extensions to Differential Cryptanalysis

Several powerful methods of cryptanalysis have been developed that start from differential cryptanalysis, and deal with block ciphers that, while resistant to conventional differential cryptanalysis as originally conceived, can still be attacked using more subtle developments from that principle.

Truncated differentials

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.)

Higher-order Differentials

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.


[Next] [Up/Previous] [Index]

Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page