Introduction

The United States' key-length limit of 40-bits for exportable cryptography is laughably small: Ian Goldberg at the University of California at Berkeley needed fewer than 4 hours of compute-time to brute-force the key space of 40-bit RC5. Forty-eight bit algorithms are small improvement; a European team led by the Swiss Federal Institute of Technology in Zurich exhausted the key-space of 48-bit RC5 in 13 days. The 56-bit key length of the Data Encryption Standard, DES, has likewise been claimed too small; Diffie and Hellman objected at the time of the standard's adoption, in 1977 [DH77].

A number of papers have provided estimates of the cost and time of breaking DES using brute-force search. Custom hardware invariably performs much better than software for this task; DES is not particularly suited to software implementation due to its employment of bit-permutations and variable word lengths. Table 1 summarizes the costs and speeds of hardware implementations proposed from the time of DES' first adoption.

By Garon and Outerbridge's estimates, DES chips are increasing in speed by a factor of eight every five years [GO91]. Thus, Wiener's 1993 0.8 $\mu$m CMOS design using a 50M block/s DES chip [Wie94], could now be translated into a $10,000 machine that would extract a DES key in 44 hours. If one is going to spend money on a cracking machine, one might wisely ask if, for a small additional expenditure, the machine may be made flexible enough to accomodate multiple algorithms. This paper attempts to more quantitatively assess that possibility. In particular, we will discuss the creation of an optimizing compiler to create hardware structures for cryptographic algorithms, and the results of a chip-level design of an FPGA-based brute-force search engine.

 

Implementation Year Cost per Blocks/s Chips Time, Ref

chip per $1M given $1M

$$\approx$$ 77 1M 50k 17 days [DH77]

$$\approx$$ 84 1.1M 25k 30 days [HGD85]

AMD 84 $19 218k 53k 72 days [AMD84]

$$\approx$$ 92 448k 31k 30 days [Way93]

VLSI Technology 92 $170 3M 6k 47 days [VLS91]

DEC 92 $300 16M 3k 16 days [Ebe93]

Wiener 93 $11 50M 58k 4 hours [Wie94]

Paper study. These tend to be rather optimistic.