This Cipher Was a Cinch

A Berkeley Graduate Student Cracks Encryption in Hours

by Robert Sanders

It took graduate student Ian Goldberg only three and a half hours to crack the most secure level of encryption that the government allows U.S. companies to export.

In January, RSA Data Security Inc. challenged the world to decipher a message encrypted with its RC5 symmetric stream cipher, using a 40-bit key, the longest keysize allowed for export. RSA offered a $1,000 reward, designed to stimulate research and experience with the security of today's codes.

Goldberg succeeded a mere 3 1/2 hours after the contest began, which provides very strong evidence that 40-bit ciphers are totally unsuitable for practical security.

"This is the final proof of what we've known for years: 40-bit encryption technology is obsolete," Goldberg said.

RSA's RC5 cipher can, however, be used with longer keysizes, ranging from 40 to 2,048 bits, to provide increasing levels of security.

U.S. export restrictions have limited deployment of technology that could greatly strengthen internet security, often affecting both foreign and domestic users, Goldberg said.

"We know how to build strong encryption; the government just won't let us deploy it. We need strong encryption to uphold privacy, maintain security and support commerce on the Internet -- these export restrictions on cryptography must be lifted," he said.

Fittingly, when Goldberg finally unscrambled the challenge message, it read: "This is why you should use a longer key."

The number of bits in a cipher is an indication of the maximum level of security the cipher can provide, Goldberg said. Each additional bit doubles the potential security level of the cipher. A recent panel of experts recommended using 90-bit ciphers, and 128-bit ciphers are commonly used throughout the world, but U.S. government regulations restrict exportable U.S. products to a mere 40 bits.

Goldberg used Berkeley's Network of Workstations to harness the computational resources of about 250 idle machines. This allowed him to test 100 billion possible "keys" per hour -- analogous to safecracking by trying every possible combination at high speed. This amount of computing power is available with little overhead cost to students and employees at many large educational institutions and corporations.

Goldberg is a founding member of the ISAAC computer security research group here, which is led by assistant professor of computer science Eric Brewer.


Copyright 1997, The Regents of the University of California.
Produced and maintained by the Office of Public Affairs at UC Berkeley.
Comments? E-mail