The open source movement has helped demonstrate the security of a new approach to encryption by cracking the code in Certicom’s ECC Challenge with a level of computing power unavailable to individual hackers.
In 1997, Candadian security vendor Certicom Corp. laid out the ECC Challenge to encourage researchers to test the security of cryptography based on elliptic curves — gently curving lines along an X-Y axis (think back to your ninth-grade algebra).The company challenged researchers to find the public key for an encryption scheme that used a 109-bit ECC, or elliptic-curve cryptography key.
Unscrambling the code — one of the most difficult cryptographic challenges to date — took 1,300 volunteers in 40 countries four months, and required the CPUs of 9,500 computers. The effort relied on open source software written by Irish mathematician Robert Harley, and three colleagues at INRIA, the French National Institute for Research in Computer Science and Control.
ECC holds out the promise of creating more secure cryptosystems with shorter key lengths. A public key cryptosystem using RSA, the existing cryptography standard, would need at least 600 bits to be as secure as an ECC cryptosystem using 109 bits, according to Harley.
ECC’s ability to provide high levels of security using shorter keys makes it attractive for mobile devices such as handhelds and cell phones, and for use over the Internet. Wireless software developer Phone.com has already started using ECC, and 3Com has signed an agreement with Certicom to use ECC for encrypting the Palm platform’s Internet connections. The new Wireless Application Protocol (WAP) standard for wireless devices also incorporates ECC.
A 500-year task
The effort to crack the code relied on volunteers at organizations such as Cornell Computer Systems Laboratory, Swinburne Astrophysics in Australia, the University of Kentucky, and the Technical University of Vienna, Austria, who contributed spare CPU cycles on their computers, much as the Search for Extraterrestial Intelligence (SETI) project does. The computers ran Harley’s open source software to calculate more than two million billion points on a particular type of elliptic curve, called a Koblitz curve, generated by Certicom. Harley’s software ran in the background on the volunteers’ computers, e-mailing results periodically back to INRIA. That data was then analyzed on a Linux-based AlphaServer workstation to extract the solution. An INRIA Web site, running the Apache Web server, allowed participants to follow the computation’s progress in real-time.
Harley wrote the original code under the GNU General Public License v. 2, which lets any user amend the code without copyright infringement. While Harley posted the source code, he also made available ports to more than a half-dozen operating systems, including Linux, Macintosh, Windows, and several flavors of Unix. Nearly a third of the systems that helped crack the code, Harley estimates, were running Linux. And the fastest machines — by a long shot — were a group of 750MHz Compaq Alphas running Linux at Alpha Processor Inc.’s headquarters in Concord, Mass.
The collaborative approach was key to finding the result in a short period of time–it took the team four months to find the key. Harley calculates that it would have taken 500 years for a single 450Mhz PC to crack the code.
Harley seems particularly well suited to take on the challenge of cracking the ECC code. A mathematician who’s well versed in computer programming, he is nearly finished writing the thesis for his Ph.D. at INRIA about advanced algorithms in algebra and number theory. He’s also a fan of open source: not only does his workstation run Linux, but he made sure that $9,000 of the $10,000 prize money from Certicom is going to the Apache Software Foundation to further development of the open source Apache Web server.
Harley himself runs a highly patched version of Red Hat Linux v. 4.x on an Alpha system. For Harley, running Linux on his computer is a sound financial decision. With the money he saved by avoiding the cost of Unix, he was able to purchase a faster processor. And he hasn’t moved to the current version of Linux for Alpha because he’s been running continuously without rebooting for nearly 400 days.
Cracking the code
The point of the Certicom challenge was to see exactly how hard it would be to find the public key in an elliptic-curve cryptograph. The amount of computing power, combined with the length of time needed to crack it, would provide a measure of how strong ECC is, especially relative to RSA.
RSA (for Rivest, Shamir, and Adleman, its inventors) is currently the most widely used public-key cryptosystem. Public-key cryptography is a secure way to encrypt information because it requires two keys — a public key for encryption, and a private key for decryption. Each user has a unique private key, so only the intended recipient can decode the data. Complex mathematical formulas are used to factor long numbers so that the private key is extremely difficult to determine from the public key.
There are several different ways of trying to crack these encryption schemes. The simplest is a brute force attack, where computers simply pound away looking for a way in. "You try all the possible keys," says Harley, "and eventually find one that works." DES, the Data Encryption Standard, was cracked in such a way.
With an ECC key of 109 bits, it’s impossible to do a brute force search, according to Harley. To crack ECC, a hacker must find two distinguished points on the curve. The INRIA group’s approach was to use a distributed algorithm that only required people to compute partial solutions. "We tried to find two pieces that match in a certain way," Harley says.
With the distributed algorithm, says Harley, "we didn’t have to specify pieces in advance, the pieces are chosen at random because there was very little chance that work would be duplicated, there are so many possible pieces to work on."
The group’s success at breaking the code shows that elliptic curve technology can be cracked. Given the amount of computing horsepower needed to do it, however, ECC provides a reasonable level of security, with substantially shorter keys than RSA, says Harley. And barring some unexpected mathematical advance that makes it easy to decipher ECC encryption, it’s likely to be 20 or 30 years before computing power increases to the point where individuals or small groups of hackers could crack the code on their own.