HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the
Electronic Frontier Foundation The Electronic Frontier Foundation (EFF) is an American international non-profit digital rights group based in San Francisco, California. It was founded in 1990 to promote Internet civil liberties. It provides funds for legal defense in court, ...
(EFF) in 1998, to perform a brute force search of the
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryp ...
(DES) cipher's key space – that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that the
key size In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known a ...
of DES was not sufficient to be secure. Detailed technical data of this machine, including block diagrams, circuit schematics,
VHDL VHDL (Very High Speed Integrated Circuit Program, VHSIC Hardware Description Language) is a hardware description language that can model the behavior and structure of Digital electronics, digital systems at multiple levels of abstraction, ran ...
source code of the custom chips and its
emulator In computing, an emulator is Computer hardware, hardware or software that enables one computer system (called the ''host'') to behave like another computer system (called the ''guest''). An emulator typically enables the host system to run sof ...
, have all been published in the book ''Cracking DES''. Its public domain license allows everyone to freely copy, use, or modify its design. To avoid the export regulation on cryptography by the US Government, the
source code In computing, source code, or simply code or source, is a plain text computer program written in a programming language. A programmer writes the human readable source code to control the behavior of a computer. Since a computer, at base, only ...
was distributed not in electronic form but as a hardcopy book, of which the open publication is protected by the
First Amendment First most commonly refers to: * First, the ordinal form of the number 1 First or 1st may also refer to: Acronyms * Faint Images of the Radio Sky at Twenty-Centimeters, an astronomical survey carried out by the Very Large Array * Far Infrared a ...
. Machine-readable metadata is provided to facilitate the transcription of the code into a computer via OCR by readers.


Background

DES uses a 56-bit key, meaning that there are 256 possible keys under which a message can be encrypted. This is exactly 72,057,594,037,927,936, or approximately 72
quadrillion Depending on context (e.g. language, culture, region), some large numbers have names that allow for describing large quantities in a textual form; not mathematical. For very large values, the text is generally shorter than a decimal numeric repres ...
possible keys. One of the major criticisms of DES, when proposed in 1975, was that the key size was too short.
Martin Hellman Martin Edward Hellman (born October 2, 1945) is an American cryptologist and mathematician, best known for his invention of public-key cryptography in cooperation with Whitfield Diffie and Ralph Merkle. Hellman is a longtime contributor to the ...
and
Whitfield Diffie Bailey Whitfield 'Whit' Diffie ForMemRS (born June 5, 1944) is an American cryptographer and mathematician and one of the pioneers of public-key cryptography along with Martin Hellman and Ralph Merkle. Diffie and Hellman's 1976 paper ''New Dire ...
of
Stanford University Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...
estimated that a machine fast enough to test that many keys in a day would have cost about $20 million in 1976, an affordable sum to national intelligence agencies such as the US
National Security Agency The National Security Agency (NSA) is an intelligence agency of the United States Department of Defense, under the authority of the director of national intelligence (DNI). The NSA is responsible for global monitoring, collection, and proces ...
. Subsequent advances in the price/performance of chips kept reducing that cost until, twenty years later, it became affordable for even a small nonprofit organization such as the EFF to mount a realistic attack.


The DES challenges

DES was a federal standard, and the
US government The Federal Government of the United States of America (U.S. federal government or U.S. government) is the national government of the United States. The U.S. federal government is composed of three distinct branches: legislative, execut ...
encouraged the use of DES for all non-classified data.
RSA Security RSA Security LLC, formerly RSA Security, Inc. and trade name RSA, is an American computer security, computer and network security company with a focus on encryption and decryption standards. RSA was named after the initials of its co-founders, ...
wished to demonstrate that DES's key length was not enough to ensure security, so they set up the DES Challenges in 1997, offering a monetary prize. The first DES Challenge was solved in 96 days by the DESCHALL Project led by Rocke Verser in
Loveland, Colorado Loveland is a List of cities and towns in Colorado#Home rule municipality, home rule municipality and the List of cities and towns in Colorado, second most populous municipality in Larimer County, Colorado, United States. Loveland is situated n ...
. RSA Security set up DES Challenge II-1, which was solved by distributed.net in 39 days in January and February 1998. In 1998, the EFF built Deep Crack (named in reference to IBM's Deep Blue chess computer) for less than $250,000. In response to DES Challenge II-2, on July 15, 1998, Deep Crack decrypted a DES-encrypted message after only 56 hours of work, winning $10,000. The brute force attack showed that cracking DES was actually a very practical proposition. Most governments and large corporations could reasonably build a machine like Deep Crack. Six months later, in response to RSA Security's DES Challenge III, and in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day – 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended
Triple DES In cryptography, Triple DES (3DES or TDES), officially the Triple Data Encryption Algorithm (TDEA or Triple DEA), is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block. The 56-bit key of the Dat ...
. The small key space of DES and relatively high computational costs of Triple DES resulted in its replacement by AES as a Federal standard, effective May 26, 2002.


Technology

Deep Crack was designed by Cryptography Research, Inc., Advanced Wireless Technologies, and the EFF. The principal designer was Paul Kocher, president of Cryptography Research. Advanced Wireless Technologies built 1,856 custom
ASIC An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficien ...
DES chips (called ''Deep Crack'' or ''AWT-4500''), housed on 29 circuit boards of 64 chips each. The boards were then fitted in six cabinets and mounted in a Sun-4/470 chassis. The search was coordinated by a single PC which assigned ranges of keys to the chips. The entire machine was capable of testing over 90 billion keys per second. It would take about 9 days to test every possible key at that rate. On average, the correct key would be found in half that time. In 2006, another custom hardware attack machine was designed based on
FPGA A field-programmable gate array (FPGA) is a type of configurable integrated circuit that can be repeatedly programmed after manufacturing. FPGAs are a subset of logic devices referred to as programmable logic devices (PLDs). They consist of a ...
s. COPACOBANA (COst-optimized PArallel COdeBreaker) is able to crack DES at considerably lower cost. This advantage is mainly due to progress in
integrated circuit An integrated circuit (IC), also known as a microchip or simply chip, is a set of electronic circuits, consisting of various electronic components (such as transistors, resistors, and capacitors) and their interconnections. These components a ...
technology. In July 2012, security researchers David Hulton and
Moxie Marlinspike Moxie Marlinspike is an American entrepreneur, cryptographer, and computer security researcher. Marlinspike is the creator of Signal (messaging app), Signal, co-founder of the Signal Technology Foundation, and served as the first CEO of Signal M ...
unveiled a cloud computing tool for breaking the MS-CHAPv2 protocol by recovering the protocol's DES encryption keys by brute force. This tool effectively allows members of the general public to recover a DES key from a known plaintext–ciphertext pair in about 24 hours.


References


External links


The DES Cracker
at the
Electronic Frontier Foundation The Electronic Frontier Foundation (EFF) is an American international non-profit digital rights group based in San Francisco, California. It was founded in 1990 to promote Internet civil liberties. It provides funds for legal defense in court, ...

Photos of the machine
at
Cryptography Research Cryptography Research, Inc. is a San Francisco based cryptography company specializing in applied cryptographic engineering, including technologies for building tamper-resistant semiconductors. It was purchased on June 6, 2011, by Rambus for $34 ...

A FPGA implementation using 48 Virtex-6 LX240Ts

ASIC design from 1994 that could crack DES in 24 hours with 256 custom chips
{{Cryptography navbox , block Cryptographic hardware Cryptanalytic devices Data Encryption Standard One-of-a-kind computers