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.
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:
searched | more than 99.6% (key was #7EF0 and #8000-#FFFF was searched first!) |
max speed possible | 1,924,000 keys/sec (220.88 kps) |
MasPar MP-1 speed | 1,500,000 keys/sec (220.52 kps) |
time | 8 days |
searched | just over half the key space |
average speed overall | 850,000 keys/sec (219.70 kps) |
max speed | 1,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/.
time | 31.8 hours |
searched | 47% of key space |
not searched | 22% of key space was allocated but no results were returned |
average speed overall | 4,515,000 keys/sec (222.11 kps) |
max contribution | 8.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
time | 3.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
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/
time | 13.00 days |
searched | 57.58% of key space |
average speed overall | 144,220,000 keys/sec (227.10 kps) |
maximum speed | 440,000,000 keys/sec (228.71 kps) |
machines involved | 5000 maximum, 7000 overall |
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
time | 270 days |
searched | 47% of key space |
average speed overall | 1,467,000,000 keys/sec (230.45 kps) |
maximum speed | 7,000,000,000 keys/sec (232.70 kps) |
machines involved | 4000 teams, "tens of thousands of machines" |
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 time | 1470 days |
searched | 60% of key space |
current speed | 156,734,000,000 keys/sec (237.19 kps) |
average speed | 88,000,000,000 keys/sec (236.36 kps) |
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).
time | 120+ days |
considered | 2.3E15 distict points |
machines involved | 9500 in total, 5000 active at any one time |
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 selection | 2.2 months |
factoring | 5.2 months |
machines involved | 292 plus a Cray for the last stage |
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 speed | 238 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.psThis 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 speed | 238.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) |
searched | 51.8% of key space |
average speed overall | 4,800,000,000 keys/sec (232.16 kps) |
maximum speed | 7,000,000,000 keys/sec (232.70 kps) |
machines involved | max: 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
time | 38.89 days |
searched | 88.4% of key space |
average speed overall | 18,950,000,000 keys/sec (234.14 kps) |
maximum speed | 34,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/
time | 56.05 hours |
searched | 24.8% of key space |
average speed overall | 88,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/.
time | 22.25 hours |
searched | 22.2% of key space |
average speed overall | 199,000,000,000 keys/sec (237.53 kps) |
maximum speed | 250,000,000,000 keys/sec (237.86 kps) |
EFF contribution | 88,804,000,000 keys/sec |
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/
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
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 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).