Cryptography Reference
In-Depth Information
Table 3.13
History of full-round DES attacks
Date Proposed or implemented attacks
1977 W. Diffie and M. Hellman propose cost estimate for key-search machine
1990 E. Biham and A. Shamir propose differential cryptanalysis, which requires 2
47
chosen plaintexts
1993 M. Wiener proposes detailed hardware design for key-search machine with an
average search time of 36 h and estimated cost of $1,000,000
1993 M. Matsui proposes linear cryptanalysis, which requires 2
43
chosen ciphertexts
Jun. 1997 DES Challenge I broken through brute-force; distributed effort on the Internet
took 4.5 months
Feb. 1998 DES Challenge II-1 broken through brute-force; distributed effort on the Inter-
net took 39 days
Jul. 1998 DES Challenge II-2 broken through brute-force; Electronic Frontier Founda-
tion built the Deep Crack key-search machine for about $250,000. The attack
took 56 h (15 days average)
Jan. 1999 DES Challenge III broken through brute-force by distributed Internet effort
combined with Deep Crack and a total search time of 22 hours
Apr. 2006 Universities of Bochum and Kiel built COPACOBANA key-search machine
based on low-cost FPGAs for approximately $10,000. Average search time is
7days
or cell phones. Hardware refers to DES implementations running on ICs such as
application-specific integrated circuits (ASICs) or field programmable gate arrays
(FPGAs).
Software
A straightforward software implementation which follows the data flow of most
DES descriptions, such as the one presented in this chapter, results in a very poor
performance. This is due to the fact that many of the atomic DES operations involve
bit permutation, in particular the
E
and
P
permutation, which are slow in software.
Similarly, small S-boxes such as used in DES are efficient in hardware but only mod-
erately efficient on modern CPUs. There have been numerous methods proposed for
accelerating DES software implementations. The general idea is to use tables with
precomputed values of several DES operations, e.g., of several S-boxes and the per-
mutation. Optimized implementations require about 240 cycles for encrypting one
block on a 32-bit CPU. On a 2-GHz CPU this translates into a theoretical throughput
of about 533 Mbits/s. 3DES, which is considerably more secure than single DES,
runs at almost exactly 1/3 of the DES speed. Note that nonoptimized implementa-
tions are considerably slower, often below 100 Mbit/s.
A notable method for accelerating software implementations of DES is
bit-
slicing
, developed by Eli Biham [20]. On a 300-MHz DEC Alpha workstation an
encryption rate of 137 Mbit/sec has been reported, which was much faster than a
standard DES implementation at that time. The limitation of bit-slicing, however, is
that several blocks are encrypted in parallel, which can be a drawback for certain
