I am currently doing some study on differential cryptanalysis.

However, I have two open questions in the field.

The first question is: How can I calculate the number of messages necessary for a successful attack?

I have read that if you have found a concrete characteristic by the cipher with probability $p$ that the number depends directly on $p$, which is understandable. However, I don't know how to calculate the number and more importantly, I can't find any literature (book or paper). If someone has a concrete tip, I would like to read it.

My second question is: Is there a measure for evaluating a probability $p$ of a characteristic? How high (or good) should a probability be for the attack to be successful? Are there any literature recommendations here?


1 Answer 1


See Heys' Tutorial on Linear and Differential Cryptanalysis (google it) for a gentle introduction.

Ali Aydin Selcuk has carefully analyzed this success probability in a number of papers.

For differential cryptanalysis roughly $c/p$ plaintext ciphertext pairs are needed where $c$ is a small constant dependent on the cipher.

As for your second question, unless $p$ is much larger than about $2^{-80}$ there is no practical attack. After all, you need to encrypt at least as many as $c/p$ plaintext ciphertext pairs to collect data before you can mount the attack and the quantity $c/p$ is a lower bound on at least your time complexity (possibly also your memory complexity depending on your attack).

However a $p$ value that is appreciably larger than $2^{-k}$ where $k$ is the keylength of the block cipher indicates a weakness in that the cipher is weaker than expected, as in Biham and Shamir's attack on DES.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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