Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:31 ADT
Matt Blaze (mab@crypto.com)
Fri, 17 Jul 1998 02:57:13 -0400
On June 23 1997, I offered a prize of 56 bits ($7.00) for finding a
DES key with a certain interesting property. In particular, I wanted
a DES key such that some ciphertext block of the form <XXXXXXXX>
decrypts to a plaintext block of the form <YYYYYYYY>, where X and Y
represent any fixed eight-bit byte value repeated across each of the
eight bytes of the 64 bit DES codebook block.
Finding a key of this form would require either computational effort
approximately equal to searching the DES keyspace, or discovering a
new cryptanalytic techique against DES. Knowing such a key would
therefore demonstrate that it is feasible to mount an exhaustive
search against the DES keyspeace or that there is some weakness in DES
that allows keys to be found analytically. This challenge, then, has
the desirable property that a result ``speaks for itself'' in
demonstrating the weakness of DES, without the need for an ``honest
broker'' who must safeguard the solution. The solution keys could not
be known to any people who haven't themselves searched the keyspace or
found some other weakness. It would be just as much of an
accomplishment for me to claim the prize as it would be for anyone
else.
I am pleased to announce that the prize has been claimed. On July 2,
1998, John Gilmore, of the Electronic Frontier Foundation, informed me
that:
With a (parity-padded) key of 0E 32 92 32 EA 6D 0D 73, the plaintext
of 8787878787878787 becomes the ciphertext 0000000000000000
According to John, this solution was found after several days of work
with the EFF ``Deep Crack'' hardware, a specialized parallel processor
optimized for DES key search. Information on Deep Crack can be found
at <http://www.eff.org/descracker>. I am especially gratified that
this DES challenge problem was chosen as the first application of the
Deep Crack hardware, and that the challenge has revealed data that
might, perhaps, yield some additional analytic clues about the
structure of the DES algorithm.
A number of individuals and organizations generously pledged
additional bits to supplement my original (quite modest) 56 bit prize,
for a total over 10000 bits ($1250.00). I will be contacting these
individuals privately to inform them that their pledges have come due.
Note that although the prize has been claimed and the contest is now
officially closed, there may be other solution keys (in fact, we'd
expect to find about 255 more, if DES emulates a random permutation).
I encourage the community to continue looking for solution keys.
Indeed, it would be interesting to know how many such keys actually do
exist in DES.
Congratulations John!
-matt
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:31 ADT