DES Key Search Project

Introduction

Machine Design Information

Pictures of the machine

Additional Information

      "This represents a tremendous practical breakthrough."
      —Burt Kaliski, Chief Scientist, RSA Data Security

      "A billion billion is a large number, but it's not that large a number."
      —Whitfield Diffie, Co-inventor of public key cryptography

Introduction

Machine Design Information

Pictures of the machine

Additional Information

Record-Breaking DES Key Search Completed
A machine built by Cryptography Research, Advanced Wireless Technologies, and EFF has demonstrated fast key search for the Data Encryption Standard (DES).  DES, the most widely used commercial encryption algorithm, protects financial transactions and electronic communications worldwide.  Developed by the US Government and IBM in the 1970s, DES is the government-approved symmetric algorithm for protecting sensitive information.

The DES algorithm uses a 56-bit encryption key, meaning that there are 72,057,594,037,927,936 possible keys. The DES Key Search Project developed specially designed hardware and software to search 90 billion keys per second, determining the key and winning the $10,000 RSA DES Challenge after searching for 56 hours.   

The DES Key Search Machine was a collaborative project by Cryptography Research, Advanced Wireless Technologies, and EFF. The hardware and software design and chip simulators were developed by Paul Kocher with assistance from Joshua Jaffe and other researchers at Cryptography Research.  Advanced Wireless Technologies developed the chip specification, board layout, and system assembly.  John Gilmore of the EFF also assisted with aspects of the project.
Cryptography Research logo
AWT
EFF

DES Key Search Machine Design Information
The DES Key Search Machine uses a sieve-and-check search process that can find keys even when little is known about the plaintext.  Each chip processes two separate ciphertexts and contains a 256-bit vector specifying which bytes can appear in the plaintext -- making it possible, for example, to find a key if the input message is simply known to consist of ASCII text.

As assembled, the machine is housed in six recycled SUN-2 cabinets and consists of 27 circuit boards that hold over 1800 custom chips.  Each chip contains 24 search units, which independently scan through a range of keys, filtering out those that do not pass the search criteria for both of the ciphertexts. For example, search units may check the decrypted block to determine that it contains only ASCII text characters, or may verify that specific bytes match known or expected values. When a search unit finds a potential match, it stops until the the controlling computer (a PC running Windows 95 or Linux) retrieves the key and restarts that search unit.  The PC tests keys against another more strict set of criteria to eliminate any incorrect keys that pass the search unit's tests.  Over 37000 search units were active, testing more than 92 billion keys per second, when the RSA DES Challenge key was discovered on July 15, 1998.

Cost and development time were major factors the machine's design. Most of the expenses were one-time research and design costs.  The total project budget remained under $250,000, making the machine the fastest, most economical key search device ever known to have been produced. 

Designed by Cryptography Research, Advanced Wireless Technologies, and EFF, the record-breaking DES Key Search Machine won the RSA DES Challenge on July 15, 1998 after searching for 56 hours.

If you have questions, please write to info@cryptography.com
 

Additional DES and DES Key Search Information

Questions?  Please write to info@cryptography.com
Cryptography Research logo

Please contact webmaster@cryptography.com with questions or comments.
Copyright © 1998, 1999 by Cryptography Research, Inc.  All rights reserved.