3.5.2 Has DES been broken?

DES has never been ``broken'', 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 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 had intentionally weakened DES. Despite these suspicions, no feasible way to break DES faster than exhaustive search was discovered. The cost of a specialized computer to perform exhaustive search has been estimated by Wiener at one million dollars.

Just recently, however, the first attack on DES that is better than exhaustive search was announced by Eli Biham and Adi Shamir, using a new technique known as differential cryptanalysis. This attack requires encryption of 2⁴⁷ chosen plaintexts, i.e., plaintexts chosen by the attacker. Although a theoretical breakthrough, this attack is not practical under normal circumstances because it requires the attacker to have easy access to the DES device in order to encrypt the chosen plaintexts. Another attack, known as linear cryptanalysis, does not require chosen plaintexts.

The consensus is that DES, when used properly, is secure against all but the most powerful enemies. In fact, triple encryption DES (see Question 3.5.3) may be secure against anyone at all. Biham and Shamir have stated that they consider DES secure. It is used extensively in a wide variety of cryptographic systems, and in fact, most implementations of public-key cryptography include DES at some level.