INDEX

CONTACT

EPFL - I&C - ISC - LASEC

Station 14 - Building INF

CH-1015 Lausanne

Switzerland

Tel. +41 21 693 7603

Fax. +41 21 693 7689

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.

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.

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.

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^{47}
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^{14} chosen plaintexts and
succeeds with a probability of 2^{-33}.

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.

[2] M. Hellman, "A cryptanalytic time-memory tradeoff", IEEE Transactions on Information Theory, v. 26, n.4, Jul. 1980, pp 401-406

[3] E. Biham and A. Shamir, Differential Cryptanalysis of DES, Springer-Verlag, 1993

[4] M. Matsui, "Linear Cryptanalysis of DES cipher", Advances in Cryptology - EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, pp. 386-397

[5] NIST Homepage

[6] EFF Homepage

[7] NSA Homepage

[8] distributed.net

[10] "Cracking DES", Electronic Frontier Fundation, May 1998, O'Reilly