How do I apply differential cryptanalysis to a block cipher?

Question

I have read a lot of summaries of block ciphers particularly with regards to the NIST competitions stating that reduced-round block ciphers are – for example – vulnerable to differential cryptanalysis.

I have a general idea that the application of differential cryptanalysis is to look at the difference between inputs; Wikipedia makes that fairly clear. However, I could take any two inputs for any given block cipher and I am pretty certain I'd be staring at random differences.

• I am aware this is the idea of a well written block cipher; however, assuming a broken or vulnerable cipher (feel free to provide simple examples) how do I go about choosing differences to try?
• Are there any clues in algorithm design that would inform a decision on which values to choose?
• How does being vulnerable to differential cryptanalysis impact a cipher in the wild?
• If all I have are differences between known plain-texts and known keys as my analysis and a captured ciphertext as my data to exploit, what can I actually deduce?

Answer 1

Basically it's analysis of a cryptographic cypher by the means of finding a relationship between the difference in the input data and the output data. Ideally, the slightest difference in input data (cleartext), even a single bit, should produce a completely different cypthertext. However, if the cypher is not well-designed, a correlation between the two resulting cyphertext might be observed. This correlation in turn might be exploited to find out the key. This, obviously requires a chosen-cleartext-attack; which means the attacker should have access to the encryption mechanism, and thus use it to encrypt any number of cleartexts he or she choses. Therefore, this kind of attack is generally applied against temper-proof hardware which one could use but not get hands on the key itself.

As per AES, see this excerpt from the Wikipedia article on differential cryptanalysis:

For example, if a differential of 1 => 1 (implying a difference in the LSB of the input leads to a output difference in the LSB) occurs with probability of 4/256 (possible with the non-linear function in the AES cipher for instance) then for only 4 values (or 2 pairs) of inputs is that differential possible. Suppose we have a non-linear function where the key is XOR'ed before evaluation and the values that allow the differential are {2,3} and {4,5}. If the attacker sends in the values of {6, 7} and observes the correct output difference it means the key is either 6 xor K = 2 or 6 xor K = 4, meaning the key is either K = {2,4}. In essence, for an n-bit non-linear function one would ideally seek as close to 2-(n-1) as possible to achieve differential uniformity. When this happens, the differential attack requires as much work to determine the key as simply brute forcing the key.

Here are a few links for warming up:

• A simplified AES algorithm and its linear and differential cryptanalyses
• Impossible differential cryptanalysis of Mini-AES
• Low Complexity Differential Cryptanalysis and Fault Analysis of AES

And here are a couple of better articles on the subject:

• A Tutorial on Linear and Differential Cryptanalysis
• A stochastic model for differential side channel cryptanalysis

Not top quality links, and especially not as practice-oriented as you seem to be looking for, but I think these last two could give you a bit of grip on the subject.

Answer 2

A good tutorial on differential cryptanalysis can be found in Stinson's book where he conducts differential attacks on reduced-round DES. He gives details on attacking 4 rounds of DES (which is relatively easy) and 6 rounds of DES (which is significantly harder) and this is enough to get the intuition on why extending the attack to full DES (which is 16 rounds) requires so many PT/CT pairs and so much computational effort (it's better to just do exhaustive key search at that point).

Biham and Shamir's original work on differential cryptanalysis was published as a book; they break several well-known ciphers (well-known at the time the book was written). However, last time I looked their book was out of print and could only be had for a very large sum.