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 ) 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 (
) 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
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  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.
In 1990, Biham and Shamir, two Israeli cryptographers working at the Weitzmann Institute, have invented (see )
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 247
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 214 chosen plaintexts and
succeeds with a probability of 2-33.
Another very important generic method to break ciphers is the linear cryptanalysis (), which was invented in
1994 by a japanese researcher working at Mitsubishi ELectronics, Mitsuru Matsui. If we have 243
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
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.
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.
More on the linear cryptanalysis topic
 "Data Encryption Standard", in Federal Information Processing Standards Publications, No. 46, U.S Department of
Commerce, National Bureau of Standards, January 1977
 M. Hellman, "A cryptanalytic time-memory tradeoff", IEEE Transactions on Information Theory, v. 26, n.4, Jul. 1980,
 E. Biham and A. Shamir, Differential Cryptanalysis of DES, Springer-Verlag, 1993
 M. Matsui, "Linear Cryptanalysis of DES cipher", Advances in Cryptology - EUROCRYPT '93 Proceedings,
Springer-Verlag, 1994, pp. 386-397
 NIST Homepage
 EFF Homepage
 NSA Homepage
 AES Project Homepage
 "Cracking DES", Electronic Frontier Fundation, May 1998, O'Reilly