Student Wins Race to Crack Code

Some cryptographers crack the code of an enciphered document with the subtle dexterity of master lockpicks. But even when brute force is used, the message is the same: Better tighten security.

On 28 January, RSA Data Systems, an encryption company based in Redwood City, California, challenged computer jocks to crack a message encrypted with the firm's new 40-bit RC5 block cipher. The very same day, Ian Goldberg, a graduate student at the University of California, Berkeley, forced open the cryptographic lock. By trying all the combinations, one after another, he was able to read a message that said, "The unknown message is: This is why you should use a longer key." Goldberg won a $1000 reward for his unscrambling efforts.

Goldberg's program ran on Berkeley's network of 250 workstations, not some fancy supercomputer, and it ran in the background, sucking up computer power only when it wasn't needed for other jobs. Even under those constraints, the program was able to test about 100 billion keys per hour. Although it would have taken about 10 hours to sift through all 240 possible combinations, it only took 3.5 hours to find the correct one.

The feat, while impressive, "does not change the terms of the debate," says Herbert Lin, director of the National Research Council's study of cryptography policy. The government severely restricts the export of cryptosystems using keys longer than 40 bits, on the grounds that such systems in the wrong hands could thwart U.S. intelligence-gathering.

Goldberg says he's shown that the bar must be raised: "The export restrictions are really silly. Forty bits is a ridiculously weak system." But Lin disagrees: "Is one message with a 40-bit encryption secure? Probably not. But if I send 10,000 encrypted-but-irrelevant messages a day, you'd still have to decrypt all of them to find the interesting message."