17 July 1998

See related news story: http://www.nytimes.com/library/tech/98/07/biztech/articles/17encrypt.html

    To: cypherpunks@toad.com
    Subject: "EFF DES Cracker" machine brings honesty to crypto debate
    Date: Fri, 17 Jul 1998 00:16:28 -0700
    From: John Gilmore <gnu@toad.com>

    FOR IMMEDIATE RELEASE
    July 17, 1998

    CONTACTS:
       Alexander Fowler, +1 202 462 5826, afowler@eff.org
       Barry Steinhardt, +1 415 436 9333 ext. 102, barrys@eff.org
       John Gilmore, +1 415 221 6524, gnu@toad.com

      "EFF DES CRACKER" MACHINE BRINGS HONESTY TO CRYPTO DEBATE

    ELECTRONIC FRONTIER FOUNDATION PROVES THAT DES IS NOT SECURE

    SAN FRANCISCO, CA -- The Electronic Frontier Foundation (EFF) today
    raised the level of honesty in crypto politics by revealing that the
    Data Encryption Standard (DES) is insecure.  The U.S. government has
    long pressed industry to limit encryption to DES (and even weaker
    forms), without revealing how easy it is to crack.  Continued adherence
    to this policy would put critical infrastructures at risk; society
    should choose a different course.

    To prove the insecurity of DES, EFF built the first unclassified
    hardware for cracking messages encoded with it.  On Wednesday of this
    week the EFF DES Cracker, which was built for less than $250,000,
    easily won RSA Laboratory's "DES Challenge II" contest and a $10,000
    cash prize.  It took the machine less than 3 days to complete the
    challenge, shattering the previous record of 39 days set by a massive
    network of tens of thousands of computers.  The research results are
    fully documented in a book published this week by EFF and O'Reilly and
    Associates, entitled "Cracking DES: Secrets of Encryption Research,
    Wiretap Politics, and Chip Design."

    "Producing a workable policy for encryption has proven a very hard
    political challenge.  We believe that it will only be possible to
    craft good policies if all the players are honest with one another and
    the public," said John Gilmore, EFF co-founder and project leader.  "When
    the government won't reveal relevant facts, the private sector must
    independently conduct the research and publish the results so that we
    can all see the social trade-offs involved in policy choices."

    The nonprofit foundation designed and built the EFF DES Cracker to
    counter the claim made by U.S. government officials that governments
    cannot decrypt information when protected by DES, or that it would
    take multimillion-dollar networks of computers months to decrypt one
    message.  "The government has used that claim to justify policies of
    weak encryption and 'key recovery,' which erode privacy and security
    in the digital age," said EFF Executive Director Barry Steinhardt.  It
    is now time for an honest and fully informed debate, which we believe
    will lead to a reversal of these policies."

    "EFF has proved what has been argued by scientists for twenty years,
    that DES can be cracked quickly and inexpensively," said Gilmore.
    "Now that the public knows, it will not be fooled into buying products
    that promise real privacy but only deliver DES.  This will prevent
    manufacturers from buckling under government pressure to 'dumb down'
    their products, since such products will no longer sell."  Steinhardt
    added, "If a small nonprofit can crack DES, your competitors can too.
    Five years from now some teenager may well build a DES Cracker as her
    high school science fair project."

    The Data Encryption Standard, adopted as a federal standard in 1977 to
    protect unclassified communications and data, was designed by IBM and
    modified by the National Security Agency.  It uses 56-bit keys,
    meaning a user must employ precisely the right combination of 56 1s
    and 0s to decode information correctly.  DES accounted for more than
    $125 million annually in software and hardware sales, according to a
    1993 article in "Federal Computer Week."  Trusted Information Systems
    reported last December that DES can be found in 281 foreign and 466
    domestic encryption products, which accounts for between a third and
    half of the market.

    A DES cracker is a machine that can read information encrypted with
    DES by finding the key that was used to encrypt that data.  DES
    crackers have been researched by scientists and speculated about in
    the popular literature on cryptography since the 1970s.  The design
    of the EFF DES Cracker consists of an ordinary personal computer
    connected to a large array of custom chips.  It took EFF less than
    one year to build and cost less than $250,000.

    This week marks the first public test of the EFF DES Cracker, which
    won the latest DES-cracking speed competition sponsored by RSA
    Laboratories (http://www.rsa.com/rsalabs/).  Two previous RSA
    challenges proved that massive collections of computers coordinated
    over the Internet could successfully crack DES.  Beginning Monday
    morning, the EFF DES Cracker began searching for the correct answer to
    this latest challenge, the RSA DES Challenge II-2.  In less than 3
    days of searching, the EFF DES Cracker found the correct key.  "We
    searched more than 88 billion keys every second, for 56 hours, before
    we found the right 56-bit key to decrypt the answer to the RSA
    challenge, which was 'It's time for those 128-, 192-, and 256-bit
    keys,'" said Gilmore.

    Many of the world's top cryptographers agree that the EFF DES Cracker
    represents a fundamental breakthrough in how we evaluate computer
    security and the public policies that control its use.  "With the
    advent of the EFF DES Cracker machine, the game changes forever," said
    Whitfield Diffie, Distinguished Engineer at Sun Microsystems and famed
    co-inventor of public key cryptography.  "Vast Internet collaborations
    cannot be concealed and so they cannot be used to attack real, secret
    messages.  The EFF DES Cracker shows that it is easy to build search
    engines that can."

    "The news is not that a DES cracker can be built; we've known that for
    years," said Bruce Schneier, the President of Counterpane Systems.
    "The news is that it can be built cheaply using off-the-shelf technology
    and minimal engineering, even though the department of Justice and the FBI
    have been denying that this was possible."  Matt Blaze, a cryptographer
    at AT&T Labs, agreed: "Today's announcement is significant because it
    unambiguously demonstrates that DES is vulnerable, even to attackers with
    relatively modest resources.  The existence of the EFF DES Cracker proves
    that the threat of "brute force" DES key search is a reality.  Although
    the cryptographic community has understood for years that DES keys are
    much too small, DES-based systems are still being designed and used
    today.  Today's announcement should dissuade anyone from using DES."

    EFF and O'Reilly and Associates have published a book about the EFF
    DES Cracker, "Cracking DES: Secrets of Encryption Research, Wiretap
    Politics, and Chip Design."  The book contains the complete design
    details for the EFF DES Cracker chips, boards, and software.  This
    provides other researchers with the necessary data to fully reproduce,
    validate, and/or improve on EFF's research, an important step in the
    scientific method.  The book is only available on paper because
    U.S. export controls on encryption potentially make it a crime to
    publish such information on the Internet.

    EFF has prepared a background document on the EFF DES Cracker, which
    includes the foreword by Whitfield Diffie to "Cracking DES."  See
    http://www.eff.org/descracker/.  The book can be ordered for worldwide
    delivery from O'Reilly & Associates at http://www.ora.com/catalog/crackdes,
    +1 800 998 9938, or +1 707 829 0515.

                                  **********

    The Electronic Frontier Foundation is one of the leading civil liberties
    organizations devoted to ensuring that the Internet remains the world's
    first truly global vehicle for free speech, and that the privacy and
    security of all on-line communication is preserved.  Founded in 1990 as a
    nonprofit, public interest organization, EFF is based in San Francisco,
    California.  EFF maintains an extensive archive of information on
    encryption policy, privacy, and free speech at http://www.eff.org.

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

    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