Cryptography Reference
In-Depth Information
Table 4.1:
DES key search efforts
Year
Source
Implemented?
Cost in US$
Search time
1977
Diffie & Hellman
No
20 million
12 hours
1993
Wiener
No
10.5 million
21 minutes
1993
Wiener
No
1.5 million
3.5 hours
1993
Wiener
No
600,000
35 hours
1997
Internet
Yes
Unknown
140 days
1998
EFF
Yes
210,000
56 hours
2007
COPACOBANA
Yes
10,000
6.4 days
been a debate about the potential availability and cost of powerful computing
devices. Some milestones in this debate, which are summarised in Table 4.1, are:
1977
: Partly in response to their concerns over the key length of DES, Whit Diffie
and Martin Hellman estimated that a search machine could be built for $20
million dollars, a sum that they did not rule out being within the capabilities
of government security agencies such as the NSA. It is probably fair to say that
in 1977 nobody really believed that anyone would invest this kind of money
to build such a machine. It is also doubtful whether such a machine could
practically have been built at that time.
1993
: Mike Wiener proposed the figures in Table 4.1 for the development of a
specified DES key search machine. The development of his machine cost a
further $500,000. There was no evidence that anyone had actually built such
a machine. These figures only worried a few people but it was acknowledged
that such a machine was beginning, at least conceptually, to become feasible to
build.
1997
: In an extraordinary effort, a DES key was found using amassive group effort
that harnessed parallel processing of the idle time of over 10 000 computers
worldwide. At its peak, this effort processed 7000 million keys per second.
(Note that this is significantly slower than our theoretical example at the start of
this discussion!) As a cryptographic contribution this result was not surprising,
since at these speeds of processing the search time was within expected bounds.
What was extraordinary was the management feat of coordinating so many
computers and successfully running them in this type of cooperative manner.
What was also significant was that people had been motivated to conduct this
search in the first place.
1998
: The real breakthrough came when the Electronic Frontier Foundation
(EFF), motivated by a desire to influence US government cryptography policy,
