Question 65. Has DES been Broken?

No easy attack on DES has been discovered, despite the efforts of many researchers over many years. The obvious method of attack is brute-force exhaustive search of the key space; this takes 255 steps on average. Early on it was suggested [DH77] that a rich and powerful enemy could build a special-purpose computer capable of breaking DES by exhaustive search in a reasonable amount of time. Later, Hellman [Hel80] showed a time-memory trade-off that allows improvement over exhaustive search if memory space is plentiful, after an exhaustive precomputation. These ideas fostered doubts about the security of DES. There were also accusations that the NSA (see Question 148) had intentionally weakened DES. Despite these suspicions, no feasible way to break DES faster than exhaustive search (see Question 57) was discovered. The cost of a specialized computer to perform exhaustive search (requiring 3.5 hours on average) has been estimated by Wiener at one million dollars [Wie94].

The first attack on DES that is better than exhaustive search in terms of computational requirements was announced by Biham and Shamir [BS93a] using a new technique known as differential cryptanalysis (see Question 58). This attack requires the encryption of 247 chosen plaintexts (see Question 63), that is, the plaintexts are chosen by the attacker. Although it is a theoretical breakthrough, this attack is not practical because of both the large data requirements and the difficulty of mounting a chosen plaintext attack. Biham and Shamir have stated that they consider DES secure.

More recently Matsui [Mat94] has developed another attack, known as linear cryptanalysis (see Question 59). A DES key can be recovered by the analysis of 243 known plaintexts and the first experimental cryptanalysis of DES was successfully achieved in an attack requiring 50 days on 12 HP 9735 workstations. Clearly however, this attack is still impractical.

The consensus is that DES, when used properly, is still secure and that triple encryption DES (see Question 72 and Question 85) is far more secure than DES. Both single and triple encryption DES are used extensively in a wide variety of cryptographic systems.




| Question 66|
| Back to FAQ INDEX |
|RSA Labs' FAQ Home | RSA Home | What's New? |
| RSA & Partner Products | FTP Server | About ... |
| Contact Sales | Contact Technical Support |




Contact RSA Laboratories:
100 Marine Parkway, Suite 500
Redwood City, CA
94065-1031

phone: 415-595-8782
fax: 415-595-1873
Website: http://www.rsa.com/rsalabs/



Website feedback or comments can be sent to : WEBMAVEN@RSA.COM

Copyright ©1996, RSA Laboratories, Inc. All Rights Reserved.
Last Updated: Friday, May 24, 1996