``Better DES challenge'' solved by John Gilmore and ``Deep Crack''

[Mr. Arlington Hewes]

========
(Given that John sent his message to Matt on July 2 I will presume most of you 
are aware of this, but I had missed it. Apologies for rehashing - Darren)
========

Begin excerpt from:

RISKS-LIST: Risks-Forum Digest  Friday 17 July 1998  Volume 19 : Issue 87

Date: Fri, 17 Jul 1998 03:31:45 -0400
From: Matt Blaze <mab@crypto.com>
Subject: ``Better DES challenge'' solved by John Gilmore and ``Deep Crack''

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 technique against DES.  Knowing such a key would therefore
demonstrate that it is feasible to mount an exhaustive search against the
DES keyspace 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

============================
end


-- 
Mr. Arlington Hewes           (tpcadmin@info.tpc.int)
The TPC.INT Subdomain          (http://www.tpc.int/)

       **************************************************
       ***  FOR GENERAL INFORMATION                   ***
       ***         mailto:tpcfaq@info.tpc.int         ***
       ***  FOR A LIST OF CURRENT COVERAGE            ***
       ***         mailto:tpccover@info.tpc.int       ***
       ***  TO REPORT A PROBLEM (read the FAQ first!) ***
       ***         mailto:support@info.tpc.int        ***
       **************************************************