FRAMINGHAM (04/20/2000) - After four months of number-crunching, a large, distributed network of computers worldwide has cracked an encryption method that will likely secure the next generation of wireless phones and other devices. The unprecedented effort revealed the strength of the encryption system but also highlighted some potential weaknesses.
"Just as crash tests by automobile manufacturers contribute to the safety of cars, this experiment helps improve cryptosystems being deployed to secure electronic communications and commerce," said Daniel de Rauglaudre, a research engineer at the French National Institute for Research in Computer Science and Control (INRIA), which announced the results last week.
Irish mathematician Robert Harley and three INRIA colleagues, including de Rauglaudre, revealed that a brute-force collaborative effort by 9,500 computers on the Internet had found the 109-bit key that had been used to scramble a message. The message was encrypted using elliptic-curve cryptography (ECC), which calculates the number of points on a curve and uses that information to generate keys that secure data.
Keys Have Size Advantage
ECC could be useful for mobile devices built around processors with less power than those found in PCs, because the algorithms require less computational power to encode and decode data.
Many software vendors use 1,024-bit RSA keys in their secure applications. But Rohit Khare, president of the security research group 4K Associates in Irvine, California, noted that ECC keys can be up to 100 times faster and five times smaller than RSA keys. He added that ECC keys used in digital certificates for cell phones can allow those devices to securely carry digital wallets containing credit-card information. "It's very important to find faster and smaller encryption codes, and this demonstration shows that elliptic-curve technology that can be a fraction of the size and done much more quickly on more limited computers is just as strong," said Khare.
The search for the 109-bit key was sponsored by Certicom Corp., a cryptographic company in Toronto that wanted to encourage researchers to test the security of ECC. The search challenge, known as ECC2K.108, was solved by what appears to be the world's largest network of distributed computing power. The effort, which was completed on April 4, included 1,300 volunteers in 40 countries who tried every key combination until they found one that worked. According to the INRIA, two-thirds of the computation was done on Unix workstations and one-third on Windows PCs. On a single 450-MHz machine, it would have taken an estimated 500 years.
The project used open-source software that Harley developed to calculate more than 2 million billion points on a type of elliptic curve called a Koblitz curve, which was used by Certicom. Of these points, 2 million "distinguished points" were sent to an AlphaServer at INRIA, where a Web site allowed participants to follow the effort's progress in real time.
"The amount of computation we did is more than what is needed to crack a secret-key system like [Data Encryption Standard] and enough to crack a public-key system like RSA of at least 600 bits," said Arjen Lenstra, vice president of the corporate technology office at Citibank in New York and a participant in the project.
Strengths and Weaknesses
But the project highlighted the relative weaknesses of some curves with special properties and confirmed that random curves are best for optimal security.
Harley noted that the computation was only about one-tenth of what normally should be required to crack a 109-bit curve because Certicom chose a curve with properties that helped speed up the attack. "This underlines the danger of adopting particular curves and the need to pick random ones with no special characteristics," Harley said.
Lenstra pointed out that RSA still has the advantage over ECC because RSA keys are less cumbersome to generate and companies like Certicom are not willing to share information on their curves. "There are many mathematicians who are still concerned about the security of elliptic curve," said Lenstra.
Despite concerns, there is still confidence in the strength of ECC. Khare noted that ECC has been written into the new Wireless Application Protocol standards as an optimized version of the Wireless Transport Layer Security protocol, formerly known on the desktop as the Secure Sockets Layer standard. He pointed out that wireless software developers such as Phone.com have already shipped software with ECC to handset manufacturers and that its deployment is just a matter of carrier rollout.