Six ways to break DES

by Pascal Junod

DES (Data Encryption Standard) is a symmetric cryptographic algorithm which was adopted in January 1977 as a standard (see [1]) for protecting non-classified information in the United States by the former National Bureau of Standards (now known as National Institute of Standards and Technology). It is widely used for protecting sensitive informations and for the authentication of banking transactions, for example. We propose here to present six different ways to break DES, the last one being currently analysed at the LASEC.

Exhaustive key search

DES is an algorithm which encrypts 64 bits blocks of data using a 56 bits secret key. A common scenario is the following: we have an encrypted block at disposal, we have some information about the plaintext (we know that it is an ASCII text, or a JPEG image, for example) and we would like to recover the secret key.

The simpler method is to try to decrypt the block with all the possible keys. The information we have on the clear text will allow us to recognize the right key and to stop the search. In average, we will have to try 36'028'797'018'963'968 (36 millions of billions) of keys. Knowing that a common modern PC can check about one to two millions keys each second, this represents a work time of about 600 to 1200 years for a single machine.

A dedicated machine

An exhaustive search is quite time consuming for a single PC, but it is possible to do better. In 1998, the EFF (Electronic Frontier Fundation has built a dedicated machine ([10]) in order to show to the world that DES is not (or no more) a secure algorithm. Deep Crack, that's the name of the machine, costs $200'000 and is built with 1536 dedicated chips. Deep Crack is able to recover a key with the help of an exhaustive search in 4 days in average, checking 92 billions of keys each second. Knowing the budget of electronic intelligence agencies (for example, the National Security Agency in the USA), it is easy to be pessimistic on the security of DES against such organizations!

A huge cluster of computers

One needs not even a lot of money to break DES. Volunteers which are ready to donate their machine's idle time and the Internet are sufficient. In January 1999, Distributed.Net, an organization specialized in collecting and managing computer's idle time, broke a DES key in 23 hours! More than 100'000 computers (from the slowest PC to the most powerful multiprocessors machines) have received and done a little part of the work; this allowed a rate of 250'000'000'000 keys being checked every second.

A time-memory tradeoff

An exhaustive search needs a lot of time, but negligible memory at all. It is now possible to imagine an scenario: we have a lot of available memory, and we are ready to precompute for all the possible keys k the encrypted block y corresponding to a given block x of data and storing the pairs (y, k) . So we will be able to find very quickly the right key if we have at disposal an encrypted version x' of our known block with an unknown key k' by searching in this kind of dictionnary. This method becomes to be interesting in the case where we have more than one key to find and we have enough memory at disposal.

In 1980, Martin Hellman proposed in [2] a time-memory tradeoff algorithm, which needs less time than an exhaustive search and less memory than the storing method. His algorithm needs in the order of 1000 GB of storage possibilities and about 5 days of computations for a single PC.

Differential cryptanalysis

In 1990, Biham and Shamir, two Israeli cryptographers working at the Weitzmann Institute, have invented (see [3]) a new generic technique to break symmetric algorithms called the differential cryptanalysis. It was the first time that a method could break DES in less time than an exhaustive search.

Imagine that we have a device which encrypts data with a hard-wired secret key, and imagine furthermore that we don't have the tools needed to "read" the key in the chip. What we can do is to choose some blocks of data and to encrypt them with the device.

The data analysis phase computes the key by analysing about 2⁴⁷ chosen plaintexts. A big advantage of this attack is that its probability of success increases linearly with the number of available chosen plaintexts and can thus be conducted even with fewer chosen plaintexts. More precisely, the attack analyses about 2¹⁴ chosen plaintexts and succeeds with a probability of 2^-33.

Linear cryptanalysis

Another very important generic method to break ciphers is the linear cryptanalysis ([4]), which was invented in 1994 by a japanese researcher working at Mitsubishi ELectronics, Mitsuru Matsui. If we have 2⁴³ = 8'796'093'022'208 known plaintext-ciphertext pairs at disposal, which represents 64'000 GB of data, it is possible to recover the corresponding key in a few days using linear cryptanalysis. It is the most powerful attack on DES known at this time.

A current research project at the LASEC is the cost analysis of this attack. We have first implemented a very fast DES encryption routine using advanced techniques on a common Intel Pentium III architecture; this routine is able to encrypt at a rate of 192 Mbps on a PIII 666MHz processor. We have then implemented the attack; it is currently running on 18 CPU's, breaking a DES key in 4 days.

The goal of this project is to do a better statistical analysis on its complexity and on its success probability. First experimental and theorical results have shown that a linear cryptanalysis needs in reality less time as estimated by Matsui in 1994.

Conclusion

DES shows some signs of old age. It can no more be considered as a secure cryptographic algorithm. The NIST has launched a process in order to develop a new standard, called AES (Advanced Encryption Standard), which will replace DES for the next 10 years.