Welcome to the resource topic for 2005/202
Title:
The Best Differential Characteristics and Subtleties of the Biham-Shamir Attacks on DES
Authors: Nicolas Courtois
Abstract:In about every book about cryptography, we learn that the plaintext complexity of differential cryptanalysis on DES is 2^47, as reported by Biham and Shamir. Yet few people realise that in a typical setting this estimation is not exact and too optimistic.
In this note we show that the two “best” differentials for DES used by Biham and Shamir are NOT the best differentials that exist in DES.
For approximations over many rounds such as used in the Biham-Shamir attack from the best characteristic is in fact a third, different differential already given by Knudsen.
A more detailed analysis shows that on average the best differential attack on DES remains the Biham-Shamir attack, because it can exploit two differentials at the same time and their propagation probabilities are related.
However for a typical fixed DES key, the attack requires on average
about 2^48.34 chosen plaintexts and not 2^47 as initially claimed.
In addition, if the key is changing frequently during the attack,
then in fact Biham and Shamir initial figure of 2^47 is correct.
We were surprised to find out that (with differential cryptanalysis) it is easier to break DES with a changing key, than for one fixed key.
ePrint: https://eprint.iacr.org/2005/202
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .