3.2.2 Has DES been broken?
No easy attack on DES has been discovered, despite the efforts of researchers over many years. The obvious method of attack is a brute-force exhaustive search of the key space; this process 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 tradeoff that allows improvement over exhaustive search if memory space is plentiful. These ideas fostered doubts about the security of DES. There were also accusations the NSA (see Question 6.2.2) had intentionally weakened DES. Despite these suspicions, no feasible way to break DES faster than exhaustive search (see Question 2.4.3) has been 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]. This estimate was recently updated by Wiener [Wie98] to give an average time of 35 minutes for the same cost machine.
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 2.4.5). This attack requires the encryption of 247 chosen plaintexts (see Question 2.4.2); 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 they consider DES secure.
More recently Matsui [Mat94] has developed another attack, known as linear cryptanalysis (see Question 2.4.5). By means of this method, a DES key can be recovered by the analysis of 243 known plaintexts. The first experimental cryptanalysis of DES, based on Matsui's discovery, was successfully achieved in an attack requiring 50 days on 12 HP 9735 workstations. Clearly, this attack is still impractical.
Most recently, a DES cracking machine was used to recover a DES key in 22 hours; see Question 2.4.4. The consensus of the cryptographic community is that DES is not secure, simply because 56 bit keys are vulnerable to exhaustive search. In fact, DES is no longer allowed for U.S. government use; triple-DES (see Question 3.2.6) is the encryption standard until AES (see Section 3.3) is ready for general use.