Custom hardware attack

From Wikipedia, the free encyclopedia

The EFF's  "Deep Crack" machine contained over 18,000 custom chips and could brute force a DES key in a matter of days — the photo shows a  circuit board fitted with 32 custom attack chips
The EFF's "Deep Crack" machine contained over 18,000 custom chips and could brute force a DES key in a matter of days — the photo shows a circuit board fitted with 32 custom attack chips

In cryptography, a custom hardware attack uses specially designed electronic circuits to decipher encrypted messages.

Mounting a cryptographic brute force attack requires a large number of similar computations: typically trying one key, checking if the resulting decryption gives a meaningful answer and trying the next key if it does not. Computers can perform these calculations at a rate of millions per second, and thousands of computers can be harnessed together in a distributed computing network. But the number of computations required on average grows exponentially with the size of the key and for many problems standard computers are not fast enough. On the other hand, many cryptographic algorithms lend themselves to fast implementation in hardware, i.e. networks of logic circuits or "gates." Integrated circuits (ICs) are constructed of these gates and often can execute cryptographic algorithms hundreds of times faster than a general purpose computer.

Each IC can contain large numbers of gates (hundreds of millions in 2005) and the number continues to grow according to Moore's law. Thus the same decryption circuit, or cell, can be replicated thousands of time on one IC. The communications requirements for these ICs are very simple. Each must be initially loaded with a starting point in the key space and, in some situations, with a comparison test value (see known plaintext attack). Output consists of a signal that the IC has found an answer and the successful key.

Since IC's lend themselves to mass production, thousands or even millions of ICs can be applied to a single problem. The ICs themselves can be mounted in printed circuit boards. A standard board design can be used for different problems since the communication requirements for the chips are the same. Wafer-scale integration is another possibility. The primary limitations on this method are the cost of chip design, IC fabrication, floor space, electric power and thermal dissipation.

An alternative approach is to use FPGAs (field-programmable gate arrays); these are slower and more expensive per gate, but can be reprogrammed for different problems. COPACOBANA (Cost-Optimized Parallel COde Breaker) is such machine, consisting of 120 FPGAs of type XILINX Spartan3-1000 which run in parallel.

[edit] History

The COPACOBANA machine, built by the Universities of Bochum and Kiel, contains 120 low-cost FPGAs and can perform an exhaustive key search on DES in 9 days on average. The photo shows the backplane of the machine with the FPGAs.
The COPACOBANA machine, built by the Universities of Bochum and Kiel, contains 120 low-cost FPGAs and can perform an exhaustive key search on DES in 9 days on average. The photo shows the backplane of the machine with the FPGAs.

The earliest custom hardware attack may have been the Bombe used to recover Enigma machine keys in World War II. In 1998, a custom hardware attack was mounted against the Data Encryption Standard cipher by the Electronic Frontier Foundation. Their "Deep Crack" machine cost U.S. $250,000 to build and decrypted the DES Challenge II-2 test message after 56 hours of work. The only other confirmed DES cracker was the COPACOBANA machine (Cost-Optimized Parallel COde Breaker) built in 2006. Unlike Deep Crack, COPACOBANA consist of commercially available, reconfigurable integrated circuits. COPACOBANA costs about $10,000 to build and will recover a DES key in under 9 days on average. It is generally believed that large government code breaking organizations, such as the U.S. National Security Agency, make extensive use of custom hardware attacks, but no examples have been declassified as of 2005.