Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've 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 choose 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?

share|improve this question
add comment

2 Answers

up vote 14 down vote accepted

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:

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

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.

share|improve this answer
    
Thanks for that; I've had a chance to review those links and they're definitely helpful! –  Ninefingers Jul 14 '11 at 22:37
add comment

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.

share|improve this answer
2  
Are the books these? Cryptography Theory and Practice (Douglas Stinson), Differential Cryptanalysis of the Data Encryption Standard (Eli Biham + Adi Shamir). (If so, simply edit the links into your answer.) –  Paŭlo Ebermann Oct 15 '11 at 0:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.