The only legally exportable cryptography level is totally insecure; UC Berkeley grad student breaks challenge cipher in hours

by Robert Sanders

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

Yesterday (1/28) 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 practical 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 the deployment of technology that could greatly strengthen security on the Internet, 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 UC Berkeley's Network of Workstations (NOW) 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 at UC Berkeley, which is led by assistant professor of computer science Eric Brewer. In the fall of 1995 the ISAAC group made headlines by revealing a major security flaw in Netscape's web browser.

This server has been established by the University of California at Berkeley Public Information Office. Copyright for all items on this server held by The Regents of the University of California. Thanks for your interest in UC Berkeley.
More Press Releases | More Campus News and Events | UC Berkeley Home Page

Send comments to: