Cryptology ePrint Archive: Report 2005/202

The Best Differential Characteristics and Subtleties of the Biham-Shamir Attacks on DES

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.

Category / Keywords: secret-key cryptography / DES, differential cryptanalysis

Date: received 28 Jun 2005

Contact author: courtois at minrank org

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Written in 2004 and not changed since.

Version: 20050629:201929 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]