------------------------------------------------------------------------------ FOR IMMEDIATE RELEASE Global Effort Solves Elliptic Curve Crypto Challenge Confirms 97-bit Elliptic Curve Discrete Logarithm is harder than factoring 512-bit RSA ------------------------------------------------------------------------ Contacts: ZOT Group (US Press Contact) B.K. DeLong bkdelong@zotgroup.com +1.617.642.7149 4K Associates (Europe) and INRIA Robert Harley Robert.Harley@inria.fr +33.1.3963.5157 4K Associates (US) Rohit Khare Rohit@4K-Associates.com +1.626.806.7574 ------------------------------------------------------------------------ PARIS -- 28 September 1999 -- Irish mathematician Robert Harley announced today the solution to the seventh and most difficult Certicom ECC Challenge problem so far. The solution was arrived at by 195 volunteers in 20 countries after 40 days of calculation distributed on 740 computers. This computation, coordinated from INRIA (the French National Institute for Research in Computer Science and Control), has confirmed theoretical predictions that a 97-bit code based on elliptic curves is harder to break than a 512-bit code based on factorization such as RSA (Rivest-Shamir-Adleman). "Our results increase confidence in codes based on properly-chosen elliptic curves, and should be taken into account in standards for Internet security," said Mr. Harley. BACKGROUND 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. DETAILS The "ECC2-97 problem" involved a set of nearly 10^29 points on an elliptic curve chosen by Certicom. The participants attacked ECC2-97 by calculating 119,248,522,782,547 (well over 10^14) 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. IMPLICATIONS 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 Arrangement." 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." FURTHER DETAILS 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. Major contributors to the project included: Astrophysics & Supercomputing Australia Institut National de Recherche en Informatique et en Automatique France University of New South Wales Australia FoRK, "Friends of Rohit Khare" USA and France École Polytechnique France Compaq USA and Italy Technischen Universität Wien Austria University of Vermont USA WinTeam Worldwide British Telecom Labs UK Internet Security Systems UK Rupture Dot Net USA Jabberwocky USA École Normale Supérieure France For a complete list of participants, consult the URLs below. FOR MORE INFORMATION: The ECDL Project http://cristal.inria.fr/~harley/ecdl/ The Certicom ECC Challenge http://www.certicom.com/chal/ 4K Associates http://www.4K-Associates.com/ ------------------------------------------------------------------------ ABOUT 4K ASSOCIATES -- 4K Associates is an alliance of Internet professionals and academics offering standards strategy consulting to organizations of all sizes. In particular, 4K draws upon extensive experience at the World Wide Web Consortium, Internet Engineering Task Force, Object Management Group, and other standards bodies to guide clients, whether forum-shopping to promulgate new standards, or to choose from the plethora of existing specifications. ------------------------------------------------------------------------------