Cryptography Reference
In-Depth Information
3.5.1 Exhaustive Key Search
The first criticism is nowadays certainly justified. The original cipher proposed by
IBM had a key length of 128 bits and it is suspicious that it was reduced to 56 bits.
The official statement that a cipher with a shorter key length made it easier to im-
plement the DES algorithm on a single chip in 1974 does not sound too convincing.
For clarification, let's recall the principle of an exhaustive key search (or brute-force
attack):
Definition 3.5.1
DES Exhaustive key search
Input
: at least one pair of plaintext-ciphertext
(
x
,
y
)
Output
: k, such that y
=
DES
k
(
x
)
Attack
:Testall
2
56
possible keys until the following condition is
fulfilled:
=
x
,
i
= 0
,
1
,...,
2
56
DES
−
1
k
i
(
y
)
−
1
.
Note that there is a small chance of 1
/
2
16
that an incorrect key is found, i.e., a key
k
which decrypts only the one ciphertext
y
correctly but not subsequent ciphertexts.
If one wants to rule out this possibility, an attacker must check such a key candidate
with a second plaintext-ciphertext pair. More about this is found in Sect. 5.2.
Regular computers are not particularly well suited to perform the 2
56
key tests
necessary, but special-purpose key-search machines are an option. It seems highly
likely that large (government) institutions have long been able to build such
brute-
force crackers
, which can break DES in a matter of days. In 1977, Whitfield Diffie
and Martin Hellman [59] estimated that it was possible to build an exhaustive key-
search machine for approximately $20,000,000. Even though they later stated that
their cost estimate had been too optimistic, it was clear from the beginning that a
cracker could be built with sufficient funding.
At the rump session of the CRYPTO 1993 conference, Michael Wiener proposed
the design of a very efficient key-search machine which used pipelining techniques.
An update of his proposal can be found in [174]. He estimated the cost of his de-
sign at approximately $1,000,000, and the time required to find the key at 1
.
5 days.
This was a proposal only, and the machine was not built. In 1998, however, the EFF
(Electronic Frontier Foundation) built the hardware machine
Deep Crack
, which
performed a brute-force attack against DES in 56 hours. Figure 3.17 shows a photo
of Deep Crack. The machine consisted of 1800 integrated circuits, where each had
24 key-test units. The average search time of Deep Crack was 15 days, and the ma-
chine was built for less than $250,000. The successful break with Deep Crack was
considered the official demonstration that DES is no longer secure against deter-
mined attacks by many people. Please note that this break does not imply that a
weak algorithm had been in use for more than 20 years. It was only possible to build
Deep Crack at such a relatively low price because digital hardware had become
