Encyclopedia > Differential cryptanalysis

Article Content

Differential cryptanalysis

Differential cryptanalysis is a form of cryptanalysis most often used on block ciphers, although it has been applied to stream ciphers and cryptographic hash functions[?] as well.

Differential cryptanalysis was first published by Sean Murphy[?], Eli Biham[?] and Adi Shamir circa 1990, but it was known to the National Security Agency as far back as the early-1970's. Parties involved in the creation of DES have admitted that defending against differential cryptanalysis was the primary design goal of DES, and the secrecy of the technique was the reason the design process of DES was kept secret.

This is a chosen plaintext attack. The attacker must persuade the victim to encrypt many pairs of plaintexts, where the difference between members in each pair is a constant. This is called the input difference. Most often "difference" here means the XOR of the two plaintexts, but other notions of difference can be used also. The attacker then examines the corresponding pairs of ciphertext. In the simplest case, the statistics of the differences in the ciphertext pairs may be significantly different from random behaviour. One particular output difference might occur fairly frequently, if the cipher is weak enough.

There are variations on this that would allow some information about the cipher key to be retrieved.

For any particular cipher, the choice of input difference can have a large impact on the success of the method. Careful analysis of the cipher is needed to determine the best input difference to use.

Differential cryptanalysis should be seen as mostly a "white hat" method, since such an attack would be very hard to mount in a real-world situation. However, a cipher designer, or an expert evaluating someone else's design, can use differential cryptanalysis to look for one kind of linear structure in a cipher. Any linear structure indicate a possible weakness, and may allow more practical attacks in the real world.

Since differential cryptanalysis became public knowledge, it has become an essential tool of cipher designers. No cipher will be taken seriously unless there is reason to believe it has strong resistance to this attack.