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