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 2⁵⁵ steps on average. Early on it was suggested 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.

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 2⁴⁷ 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 2⁴³ 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|