Differential cryptanalysis

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

See http://www.execpc.com/~alcourt/desdoc.html.

Perhaps someone will incorporate this before I get to it. I'm writing as as I learn... <>< tbc

See also: cryptanalysis, cryptography

A form of cryptanalysis most often used on block ciphers, although it has occasionally 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 there are indications it was known to some sections the closed cryptographic community much earlier. For instance it is almost certain that someone involved in the design of DES in the early to mid 1970s knew about it.

This is a form of chosen plaintext cryptanalysis. 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 would be bad, and may allow more practical attacks in the real world.

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