CryptoDB
The Best Differential Characteristics and Subtleties of the Biham-Shamir Attacks on DES
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2005-12538,
title={The Best Differential Characteristics and Subtleties of the Biham-Shamir Attacks on DES},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / DES, differential cryptanalysis},
url={http://eprint.iacr.org/2005/202},
note={ courtois@minrank.org 12962 received 28 Jun 2005},
author={Nicolas Courtois},
year=2005
}