Cryptography Reference
In-Depth Information
In either case, many people have discussed the possibility to design and
actually build dedicated machines to do an exhaustive key search for DES. For
example, Michael J. Wiener proposed such a design in 1993 [8]. He came to the
conclusion that a US$1,000,000 version of such a machine would be capable of
finding a DES key in 3.5 hours on the average. In 1997, he modified his estimates
with a factor of 6 (i.e., a US$1,000,000 version of the machine would be capable
of finding a DES key in 35 minutes on the average and a US$10,000 version of the
machine would be capable of finding a DES key in 2.5 days on the average [9]).
These numbers are worrisome (for the security of DES against an exhaustive key
search).
It was not until 1998 that a hardware-based search machine named
Deep Crack
was built by the Electronic Frontier Foundation (EFF) [10].
14
Deep Crack costs
US$200,000 to build and consists of 1,536 processors, each capable of searching
through 60 million keys per second. Referring to (10.1), the time to do an exhaustive
key search is then
2
56
60
,
000
,
000
2
55
60
,
000
,
000
|K|
t
=
1
,
536
=
1
,
536
≈
390
,
937 seconds
.
2
p
·
2
·
·
Consequently, Deep Crack is able to recover a DES key in approximately
6,516 minutes, 109 hours, or 4.5 days.
More interestingly, one can also spend the idle time of networked computer
systems to look for DES keys and run an exhaustive key search. If enough computer
systems participate in the search, then a DES key can be found without having to
build a dedicated machine such as Deep Crack. For example, in January 1999, the
participants of the
Distributed.Net project
15
broke a DES key in only 23 hours. More
than 100,000 computer systems participated, received, and did a little part of the
work. This allowed a rate of 250 billion keys being checked every second.
Against this background, it is obvious that the relatively small key length
and the corresponding feasibility of an exhaustive key search is the most serious
vulnerability and security problem of the DES. There are only a few possibilities
to protect a block cipher with a small key length, such as DES, against this type of
attack. For example, one can frequently change keys, eliminate known plaintext, or
use a complex key setup procedure. An interesting idea to slow down an exhaustive
key search attack is due to Rivest and is known as
all-or-nothing encryption
[11]. It
yields an encryption mode for block ciphers that makes sure that one must decrypt
the entire ciphertext before one can determine even one plaintext message block.
14
http://www.eff.org/descracker.html
15
http://www.distributed.net
