Calculate number of required pairs for differential cryptanalysis

Question

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?

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.