Richard Clayton

Brute force attacks on cryptographic keys

Many cryptographic systems have no (practical) known weaknesses and so the only way of "cracking" them is to use a "brute force attack" by trying all possible keys until the message can be decoded. This web page reviews the topic.

There are a classic series of challenges relating to RC4, RC5, elliptic curves and RSA.

The Data Encryption Standard (DES) has an insufficiently long key, so there are many papers on possible machines for attacking it - a few of which have actually been built.

To complete this survey, there are a few pointers to reports of the speed of software implementation, a pointer to the classic paper on key lengths and a pointer to the LCS35 puzzle, that is designed to be a brute force puzzle that cannot be attacked by a parallel array of machines.

40 bit RC4

In July 1995 Hal Finney issued a challenge (http://www.finney.org/~hal/sslchallong.html) on the cypherpunk mailing list. This challenge was to read an SSLv2 session - which involves both MD5 and RC4 - and it was broken at almost the same time by two independent efforts:

searchedmore than 99.6%
(key was #7EF0 and #8000-#FFFF was searched first!)
max speed possible1,924,000 keys/sec (220.88 kps)
MasPar MP-1 speed1,500,000 keys/sec (220.52 kps)
 
time8 days
searchedjust over half the key space
average speed overall850,000 keys/sec (219.70 kps)
max speed1,350,000 keys/sec (220.36 kps)

Hal Finney's second challenge (http://www.brute.cl.cam.ac.uk/brute/hal2) was issued in August 1995 and was also an SLLv2 problem. This was cracked by a group of about 200 people in 31.8 hours. The problems with running the server to distribute the segments of key space are described at http://www.brute.cl.cam.ac.uk/brute/hal2probs/.

time31.8 hours
searched47% of key space
not searched22% of key space was allocated
but no results were returned
average speed overall4,515,000 keys/sec (222.11 kps)
max contribution8.5% = 384,000 keys/sec (218.55 kps)

In January 1997 RSA issued a series of crypto challenges at various key lengths. The RC40 challenge was first completed in 3.5 hours by Ian Goldberg using the Berkeley NOW clusters (http://now.cs.berkeley.edu/) and some other machines. Details are at: http://www.isaac.cs.berkeley.edu/isaac/crypto-challenge.html

time3.5 hours
average speed overall~28,000,000 keys/sec (~225 kps)

An organised group, started by Germano Caronni and other graduate students at the Swiss Federal Institute of Technology in Zurich, communicating via the Internet, took only a few more minutes to find the key using a group of about 1200 machines. http://www.brute.cl.cam.ac.uk/brute/challenge/rsa_eng.phtml

48 bit RC5

The January 1997 RSA challenge also included a 48 bit RC5 key. This was broken by the Caronni group ("The Distributed Internet Crack") in 13 days. For details see: http://www.brute.cl.cam.ac.uk/brute/rsa_clng/en/

time13.00 days
searched57.58% of key space
average speed overall144,220,000 keys/sec (227.10 kps)
maximum speed440,000,000 keys/sec (228.71 kps)
machines involved5000 maximum, 7000 overall

56 bit RC5

The 56 bit RC5 key from the January 1997 RSA Challenge was cracked in 250 days by the Bovine group (later known as distributed.net). For details see: http://www.rsasecurity.com/news/pr/971022-2.html

time270 days
searched47% of key space
average speed overall1,467,000,000 keys/sec (230.45 kps)
maximum speed7,000,000,000 keys/sec (232.70 kps)
machines involved4000 teams, "tens of thousands of machines"

64 bit RC5

Efforts are ongoing to tackle the 64 bit RC5 key from the January 1997 RSA Challenge. See http://www.distributed.net/rc5/ for the current details. The project has (as of October 2001) swept 60% of the keyspace and will take about 4.5 months to sweep the next 10% of the space. (Full statistics at: http://stats.distributed.net/rc5-64/ .)

Details as of October 2001
elapsed time1470 days
searched60% of key space
current speed156,734,000,000 keys/sec (237.19 kps)
average speed88,000,000,000 keys/sec (236.36 kps)

Elliptic curves

Certicom have produced a series of challenges at 109, 131, 163, 191, 239 and 359 bits. (see: http://www.certicom.com/research/ch_62.html The 109 bit challenge (to find a particular 108 bit prime) was solved in April 2000 ( http://cristal.inria.fr/~harley/ecdl7/readMe.html).

time120+ days
considered2.3E15 distict points
machines involved9500 in total, 5000 active at any one time

RSA

RSA have a series of challenges for factoring public keys. The largest broken so far is the 512 bit value (RSA-155 since it has 155 decimal digits). Details are at: http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html

polynomial selection2.2 months
factoring5.2 months
machines involved292 plus a Cray for the last stage

56 bit DES

The 56 bit key length chosen for the Data Encryption Standard (DES) has been controversial ever since it was first announced. In 1977 Whit Diffie and Martin Hellman published a paper design for a $20M machine that would recover one DES key per day.

W. Diffie and M. E. Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard," in IEEE Computer, vol. 10, 1977, pp. 74-84. (not on the web)
Search speed238 keys/sec
Cost per key$50,000 (amortised over 1 year)

There were a number of further paper designs over the next two decades, of which the most detailed was Michael Wiener's in 1993.

M. Wiener, "Efficient DES key search", TR-244 Carleton University, 1993
also appears in William Stallings, Practical Cryptography for Data Internetworks, IEEE Computer Society Press, 1996
and Advances in Cryptology: Proceedings of CRYPTO '93, Santa Barbara, Ca, 1994. Springer LNCS 773.
Available online in PostScript at: http://www.ja.net/CERT/Wiener/des_key_search.ps
This machine was estimated to cost $0.5M to design and then $0.1M to build for a search time of 35 hours per key. However, spending $1M would yield one key every 3.5 hours, and spending $10M would allow one key to be found every 21 minutes.
Search speed238.07 keys/sec [$100K machine]
241.39 keys/sec [$1M machine]
244.71 keys/sec [$10M machine]
Cost per key$6.59 (amortised over 1 year)

One of the January 1997 RSA challenges was a DES key. This was cracked by a distributed software effort called DESCHALL. The homepage for this effort is archived at http://www.interhack.net/projects/deschall/ and a detailed paper describing the effort can be found at http://www.interhack.net/pubs/des-key-crack/.

time~90 days
(assuming a mid-March start point)
searched51.8% of key space
average speed overall4,800,000,000 keys/sec (232.16 kps)
maximum speed7,000,000,000 keys/sec (232.70 kps)
machines involvedmax: 14000 in a single day

The January 1998 RSA challenge ("DES Challenge II") was won by distributed.net in 39 days. General details are at http://www.distributed.net/des/ and specific information at http://lists.distributed.net/hypermail/announce/0039.html

time38.89 days
searched88.4% of key space
average speed overall18,950,000,000 keys/sec (234.14 kps)
maximum speed34,430,000,000 keys/sec (235.00 kps)

The July 1998 RSA challenge ("DES Challenge II-2") was won by the EFF DES Cracker machine (sometimes called "Deep Crack"). The EFF press release is here: http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html and their FAQ contains detailed timings. The machine itself has a homepage at: http://www.eff.org/descracker/

time56.05 hours
searched24.8% of key space
average speed overall88,804,000,000 keys/sec (236.37 kps)

The EFF machine was the first hardware design actually to be built and run (that has been acknowledged - major governments are predicted to have been running systems for years). It is fully documented in a 268 page paperback book:

Electronic Frontier Foundation. Cracking Des : Secrets of Encryption Research, Wiretap Politics & Chip Design. O'Reilly. May 1998. It is available online at http://cryptome.org/cracking-des.htm.

For the January 1999 RSA challenge ("DES III"), the EFF machine teamed up with distributed.net. The key was found in 22 hours, thereby winning the maximum prize money from RSA (the prize would have halved at the 24 hour mark). This may be seen as being fairly lucky since only about a quarter of the key space was searched. Details can be found at: http://www.distributed.net/des/.

time22.25 hours
searched22.2% of key space
average speed overall199,000,000,000 keys/sec (237.53 kps)
maximum speed250,000,000,000 keys/sec (237.86 kps)
EFF contribution88,804,000,000 keys/sec

An annotated bibliography of further brute force papers (mainly on DES)

R.C. Fairfield, A. Matusevich, and J. Plany. An LSI Digital Encryption Processor (DEP). CRYPTO '84. LNCS 0196, Springer Verlag. pp 115-143. Available on the net as: http://link.springer.de/link/service/series/0558/papers/0196/01960115.pdf

First LSI chip to get the whole of DES into a single device. Ran at 4.5MHz, and could manage 0.59 Mbytes/sec (64 bits wide). Its potential cracking speed was just 73750 keys/second ... but even so the authors warned that using multiple chips, unrolling the DES loops and the speed up caused by ever smaller gate sizes would mean that a key might be cracked in a month.

Frank Hoornaert, Jo Goubert, and Yvo Desmedt. Efficient Hardware Implementation of the DES. CRYPTO '84. LNCS 0196, Springer Verlag 1985. pp 147-173. Available online as: http://link.springer.de/link/service/series/0558/papers/0196/01960147.pdf

This paper discusses the issues for hardware solutions in 1984 - routing of signals, keeping pin numbers down, and minimizing area whilst maximimizing speed. An exhaustive search design would run at 1,130,000 keys/sec. They assume a $40 chip, so for a chip cost of $1,000,000 they project a performance of one key per two weeks.

Albert G. Broscius and Jonathan M. Smith. Exploiting parallelism in hardware implementation of the DES. In Advances in Cryptology: Proceedings of CRYPTO '91, pages 367-376. Springer-Verlag, 1992. It is available online (in compressed PostScript) at: http://www.cis.upenn.edu/~dsl/read_reports/DES-12.ps.Z

This paper discusses the various places where parellizing DES can produce a faster design.

Hans Eberle. A High-speed DES Implementation for Network Applications. SRC Research Report 90, DEC SRC 1992. Available online as: http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC-090.pdf

A 250MHz design in Gallium Arsenide technology that could process data at 1GHz/sec (the chip is not pipelined - hence its performance is 16 times less than might be expected for ECB mode). Eberle observes that his $300 chip could form the basis of a $1,000,000 machine that broke DES in an average time of 8 days. Note that the speed is for 3333 chips running at 250MHz ... but the lack of pipelining means that the effective speed is only 15.6MHz.

Peter C. Wayner. Content-Addressable Search Engines and DES-Like Systems. CRYPTO '92. LNCS 0740 Springer Verlag. pp 575-586. Available on the net at: http://link.springer.de/link/service/series/0558/papers/0740/07400575.pdf

Uses the processors that implement content addressable memory to provide DES encryption. Estimated that a $30,000,000 machine could crack one key a day.

Ian Goldberg and David Wagner. Architectural considerations for cryptanalytic hardware. Overview page Paper: Architectural considerations for cryptanalytic hardware

This widely referenced project tackled RC4, A5, DES and CDMF. The algorithms were implemented on FPGAs (though only one round in several cases) and the "bang per buck" calculated for a range of components. They concluded that RC4 was best tackled in software, that the "Magnificent Seven" (see above) had over-estimated the capabilities of 1996 vintage FPGAs and that DES was crackable at one key per year for an investment of $45,000 in chips.

Leonard M. Adleman, Paul W. K. Rothemund, Sam Roweis and Erik Winfree. On Applying Molecular Computation To The Data Encryption Standard. In: Proceedings of the Second Annual Meeting on DNA Based Computers, held at Princeton University, June 10-12, 1996. Available on the web as: http://www-scf.usc.edu/~pwkr/des.pdf

A theoretical design for a highly parallel attack on DES using about a gram of DNA. This assumes an error rate of 10-4. At an error rate of 10-2 the amount of DNA you need is about 23 times the mass of the earth. They note in passing how DES's design is insecure against massively parallel attacks and observe that only 6655 steps are needed to do an encryption - hence the feasability of a slow, molecular, computer attacking DES.

Toby Schaffer, Alan Glaser, Srisai Rao and Paul Franzon. A Flip-Chip Implementation of the Data Encryption Standard (DES). 1997 IEEE Multi-Chip Module Conference (MCMC '97). Available on the web (in compressed PostScript) as: http://www.eos.ncsu.edu/eos/info/vlsi_info/techreports/NCSU-ERL-97-02.PS.Z

A "flip chip" is a chip that is placed onto the circuit board face side down. This can improve cooling, but the main aim is to remove wire bonding and therefore allow shorter interconnections between circuits. Connections by solder bumps means that the chip no longer has all its I/O around the edge. This particular design runs at 9.6Gb/sec (150MHz with a 64 bit wide data path). The design is fully pipelined, with the key passed along in parallel with the data to allow multiplexing of data streams. Triple DES can be done by connecting three dice together. The design was simulated - it is unclear if a physical device exists.

A. Buldas and J. Poldre. A VLSI implementation of RSA and IDEA encryption engine. In: NORCHIP '97, 1997. Available on the web as: http://www.cyber.ee/research/cryptochip.pdf

A 25Mhz chip from Estonia that does IDEA and RSA. Real chip prototypes exist.

Jens-Peter Kaps. High speed FPGA architectures for the Data Encryption Standard. Master's thesis, ECE Dept., Worcester Polytechnic Institute, Worcester, USA, May 1998. Available on the web in PostScript as: http://www.ece.wpi.edu/Research/crpyt/theses/documents/ms_kaps.ps.gz

Assesses FPGA designs for DES involving combinations of pipelining and loop unrolling. The fastest designs ran at 34MHz or with a throughput of 384Mb/sec.

Jens-Peter Kaps and Christof Paar. Fast DES Implementation for FPGAs and its Application to a Universal Key-Search Machine. Selected Areas in Cryptography 1998, pp 234-247. Available on the web in Postscript as: http://ece.wpi.edu/Research/crypt/publications/documents/sac98kaps.neu.ps

Builds on the thesis work above to propose a key cracking chip. Projects a speed of 6.29 million keys/sec (222.58). A machine to break keys at one per day would cost $38million ($104,000 per key). Such a design would however be flexible and other cracking attempts could be done with it.

Ivan Hamer and Paul Chow. DES Cracking on the Transmogrifier 2a. Cryptographic Hardware and Embedded Systems, LNCS 1717, Springer-Verlag, 1999. pp 13-24. Available online (in compressed PostScript) as: http://www.eecg.toronto.edu/~pc/research/publications/des.ches99.ps.gz

The Transmogrifier is a number of FPGAs that are interconnected to form a large reprogrammable machine. The 2a version has 32 usable FPGAs and the DES cracking design can be run at 25MHz (ie the speed would be 80,000,000 keys/sec). This equates to an average time to find a DES key of 520 days. The cost of the Transmogrifier is estimated to be about $60,000 (in 1998). There authors have also provided an amusing picture at: http://www.eecg.toronto.edu/~pc/research/fpga/des/

Software performance

Michael Roe. Performance of Symmetric Ciphers and One-way Hash Functions. In: Fast Software Encryption, LNCS 809 Springer-Verlag, December 1993. Available on the net as: http://research.microsoft.com/users/mroe/fse93.pdf

Covers the performance of the hash functions MD2, MD4, MD5, SHA (the original NIST algorithm), RIPE-MD and the block ciphers DES, GOST and SAFER-K64.

Michael Roe. Performance of Block Ciphers and Hash Functions - One Year Later. Fast Software Encryption: Second International Workshop, LNCS 1008, Springer-Verlag, 1995. pp 359-362.

Covers, inter alia, SHA-1, RC4, WAKE, SEAL and Blowfish.

The performance of the Crypto++ software library in running a wide range of crypto functions is documented by Wei Dai at: http://www.eskimo.com/~weidai/benchmarks.html

Recommended key lengths

Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, and Michael Wiener. Minimal key lengths for symmetric ciphers to provide adequate commercial security: A report by an ad hoc group of cryptographers and computer scientists, January 1996. Available on the Internet as: http://theory.lcs.mit.edu/~rivest/bsa-final-report.txt

Influential paper on brute force performance. The authors recommend 90 bit keys for protection from major governments for the forseeable future. Their figures for 1996 FPGA performance appear optimistic - but this only makes a difference of a couple of bits to the key length you need.

The LCS35 Puzzle

The LCS35 puzzle is described at: http://www.lcs.mit.edu/news/crypto.html. It is designed to foil attempts of a solver to exploit parallel or distributed computing to speed up the computation. The computation required to solve the puzzle is "intrinsically sequential". The puzzle parameters have been chosen to make a solution possible by 2033 (35 years after the puzzle was set).

Return to Richard Clayton's Home Page

last modified 29 OCT 2001 -- http://www.cl.cam.ac.uk/~rnc1/brute.html