40-bit crypto proves no problem

A graduate student at the University of California at Berkeley used a network of about 250 workstations to crack a 40-bit algorithm in less than four hours yesterday, a university professor told CNET today. Responding to an international contest announced by encryption software company RSA Security Dynamics, grad student Ian Goldberg set the UC Berkeley Network of Workstations to the task of cracking the code yesterday using cryptanalysis software, key-testing software that he "tweaked" to run even faster than usual. The software was able to test about 100 billion key combinations an hour, said Eric Brewer, the Berkeley computer science professor who oversees Goldberg's work with the Internet Security, Applications, Authentication and Cryptography research group.

For his efforts, Goldberg won the $1,000 prize for the 40-bit level, the weakest encryption that RSA offers. His ease in completing the hack adds fuel to the argument that 40-bit crypto, where scrambling codes are composed of a string of 40 digits, is too weak for commercial use.

"If we can break a random 40-bit key in three-plus hours, it means Internet commerce based on 40-bit keys is unacceptable," Brewer said.

Longer bit lengths make cracking exponentially more difficult, however. A 56-bit algorithm would take about 22 years to crack under similar circumstances, Brewer said.

There is no limit on the strength of encryption used domestically, but newly revised U.S. export regulations have set a provisional limit of 56-bit algorithms as long as the exporter agrees to support a system of key storage that allows the government access to encrypted data.

The ISAAC group made news last fall when it cracked the encryption layer of Netscape Communications' Navigator browser. In that case, Netscape programmers had failed to select completely random bits for their encryption algorithms.

Brewer and his staff were able to detect patterns in the string of digits and crack the code fairly easily. Netscape immediately fixed the problem and re-released the browser.