A worldwide team of volunteers, using spare computing power, found the secret key for a message encrypted with the RC5-64 cipher, winning a $10,000 prize and, they say, casting some doubt on the security of messages protected by the cipher.
Distributed.net, a collection of more than 331,000 volunteers who lent their machines idle processing power to the effort, solved the challenge posed in 1997 by RSA Laboratories, the research arm of RSA Security Inc. It took nearly four years, a search through 15,769,938,165,961,326,592 keys and processing power roughly equivalent to nearly 46,000 2GHz AMD Athlon machines for the team to find the correct key.
The plaintext message that the key unlocked was: “Some things are better left unread.”
A 450MHz Pentium III machine in Japan found the key on July 14, but a technical glitch prevented the Distributed.net team from realizing they had the correct key until Aug. 12.
The teams organizers said their effort should not only prove the effectiveness of distributed computing efforts in solving large problems but also cause people to think twice before using the 64-bit RC5 cipher to encrypt some data.
“While its debatable that the duration of this project does much to devalue the security of a 64-bit RC5 key…we can say with confidence that RC5 is not an appropriate algorithm to use for data that will still be sensitive in more than several years time,” the team said in a statement.
The RC5 algorithm was designed by renowned cryptographer Ron Rivest, one of the three designers of the original RSA algorithm.
Rivest, now a professor of electrical engineering and computer science at Massachusetts Institute of Technology in Cambridge, Mass., said he has no quibble with Distributed.nets statements about the utility of RC5 with 64-bit keys.
“Yes, I think that their statement is fine,” Rivest said, adding that using RC5 with longer key sizes such as 128 bits makes it far more difficult to find a secret key. Rivest and a group of other cryptographers in 1996 suggested that users employ keys of at least 90 bits for symmetric cryptosystems such as RC5. Adding one bit to the length of a key doubles the number of possible keys.
An RSA spokesman in Bedford, Mass., said the company always recommends that its customers use longer keys, typically 128 bits.
The RC5-64 challenge is just one of several such contests that RSA Laboratories has devised over the last several years in an effort to validate the strength of the various algorithms the company uses in its products. Others have included the RC5-40, RC5-56 and DES (Digital Encryption Standard) challenges.
Distributed.net also solved the DES challenge in 1999.
- RSA Reports Loss; Revenues Drop
- RSA Banks on Web Services
- More Security Coverage
(Editors note: This story has been updated since its original posting to add comments from Rivest and RSA.)