Differential Cryptanalysis of the Data Encryption Standard

Author: Eli Biham & Adi Shamir

Published in: Springer-Verlag

ISBN: 978-1-4613-9314-6

File Type: pdf

File Size:  15 MB

Language: English

Description of Differential Cryptanalysis of the Data Encryption Standard

The security of iterated cryptosystems and hash functions has been an active research area for many years. The best known and most widely used function of this type is the Data Encryption Standard (DES). It was developed at IBM and adopted by the National Bureau of Standards in the mid 70's, and has successfully withstood all the attacks published so far in the open literature. Since the introduction of DES, many other iterated cryptosystems were developed, but their design and analysis were based on ad-hoc heuristic arguments, with no theoretical justification.

In Differential Cryptanalysis of the Data Encryption Standard book, we develop a new type of cryptanalytic attack which can be successfully applied to many iterated cryptosystems and hash functions. It is primarily a chosen plaintext attack but under certain circumstances, it can also be applied as a known plaintext attack. We call it "differential cryptanalysis" , since it analyzes the evolution of differences when two related plaintexts are encrypted under the same key. Differential cryptanalysis is the first published attack which is capable of breaking the full 16-round DES in less than 255 complexity. The data analysis phase computes the key by analyzing about 236 ciphertexts in 237 time. The 236 usable ciphertexts are obtained during the data collection phase from a larger pool of 247 chosen plaintexts by a simple bit repetition criteria which discards more than 99.9% of the ciphertexts as soon as they are generated.

This attack can be applied to a wide variety of DES-like substitution/ permutation cryptosystems, and it demonstrates the crucial role of each element in their design. In particular, we show that almost any structural modification of DES leads to a much weaker cryptosystem, and that DES reduced to eight rounds is so weak that it can be broken in two minutes on a personal computer. The attack is also applicable to bounded-round versions of the cryptosystems FEAL, Khafre, REDOC-II, LOKI and Lucifer, and to the hash functions Snefru and N-Hash.

We would like to use this opportunity to thank our colleagues who contributed remarks, suggestions, ideas and designs. Shoji Miyaguchi's FEAL cryptosystem motivated the first version of our attack, and Ralph Merkle's Snefru motivated its extension to hash functions. We had valuable discussions with Henry Gilbert and Matthew Kwan, who carried out related attacks on some of the cryptosystems discussed here, and we received valuable remarks from Philip Zimmermann. Don Coppersmith, Martin Hellman, and Alan Konheim sent us many helpful comments and suggestions which greatly improved the presentation of our results. Finally, the encouragement and help of our families are greatly appreciated.
Similar Books