Elliptic Curves could solve the security problem

Though public-key cryptosystems have been based on the ECDL (Elliptic Curve Discrete Logarithm) problem for fifteen years, industry leaders such as RSA Security Inc. have adopted them only recently. To encourage research into cryptographic applications of elliptic curves and thereby strengthen the case for ECC (Elliptic Curve Cryptography) in the heated RSA-vs-ECC debate, Canadian company Certicom launched a series of increasingly difficult challenge problems in November 1997 with prizes worth up to $100,000. The amount of effort expended by winning entrants provides a rough index of the strength of ECC.

The "ECC2-97 problem" involved a set of nearly 10²⁹ points on an elliptic curve chosen by Certicom. The participants attacked ECC2-97 by calculating 119,248,522,782,547 (well over 10¹⁴) of the points using open-source software developed by Mr. Harley. Of these, 127,492 "distinguished" points were filtered out and collected on an Alpha Linux workstation at INRIA near Versailles, France. A final phase of processing selected two matching points and, using some attached information, calculated the solution to the challenge thereby delivering the coup de grace to the most difficult elliptic curve problem ever.

Mr. Harley's team was lucky enough to find the solution with less than a third of the expected amount of computation. The probability of detecting matching points so soon was less than one in ten -- and even more surprisingly, a second match was detected just hours later, a less than one in a hundred chance! Even so, the project used approximately 16,000 MIPS-years of computation. That is twice as much as used for the recent factorization of a 512-bit RSA number, announced by Herman Te Riele at CWI Amsterdam on 26 August.

Andrew Odlyzko, Head of Mathematics and Cryptography Research at AT&T Labs described the project as "a great achievement that demonstrates the value of fruitfully harnessing some of the huge computational power of the Internet that is idle most of the time" and stated that it "validates theoretical security predictions, and demonstrates the need to keep increasing cryptographic key sizes to protect against growing threats."

"Understanding the bounds of ECC's strength grows more urgent as it is written into more and more Internet standards," noted Rohit Khare, a principal of the 4K Associates standards-strategy consultancy and colleague of Mr. Harley. "For example, our recent analysis of the WAP [Wireless Application Protocol] suite agreed that RSA is too power-hungry for hand-held devices, but cautioned that there are pitfalls in blindly incorporating ECC into existing protocols."

According to Dr. Robert Zuccherato, senior cryptographer at Entrust Technologies Inc., "Successful efforts like this one, while demonstrating the weakness in practice of short keys, also confirm the security level achieved by the 160-bit or longer keys used in commercial elliptic-curve cryptosystems." He added that "Entrust Technologies was pleased to provide resources to assist in this project."

Arjen K. Lenstra, Vice President at Citibanks's Corporate Technology Office in New York and one of the main contributors to the recent successful attack on the 512-bit RSA challenge, compared the two computational efforts and noted that the present result makes 160-bit ECC keys look even better compared to 1024-bit RSA keys, from a security point of view. "Ideally we would like new theoretical advances to further reinforce these practical results, although such advances appear out of reach for the moment."

Khare observed that a determined adversary such as a government agency or a corporation with substantial computing resources would make short work of a 97-bit ECC key or indeed the 109-bit key in the next Certicom problem.

"We are now close to the 112-bit limitation that many Western governments impose on exportable ECC software via the Wassenaar Agreement." said Mr. Harley. "Our repeated successes are demonstrating that such short keys offer a wholly inadequate level of security. These export restrictions, while claimed to be in the public interest, in fact facilitate industrial espionage, hinder global competition and limit people's right to privacy."

Four fifths of the US$5000 prize will be donated to the Free Software Foundation whereas the remaining US$1000 will go to Paul Bourke at the Swinburne Centre for Astrophysics and Supercomputing in Australia. The matching points had in fact both been calculated by Mr. Bourke using spare cycles on a cluster of Alpha Unix machines mainly used to study pulsars.