--- begin forwarded text Date: Tue, 28 Sep 1999 16:17:07 -0400 To: [EMAIL PROTECTED] From: David Farber <[EMAIL PROTECTED]> Subject: IP: Elliptic Curve 97-bit Challenge Broken Sender: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] Date: Tue, 28 Sep 1999 15:44:17 -0400 From: [EMAIL PROTECTED] (Dorothy Denning) Subject: Elliptic Curve 97-bit Challenge Broken To: [EMAIL PROTECTED] http://www.inria.fr/Actualites/pre55-eng.html INRIA leads nearly 200 international scientists in cracking code following challenge by Canadian company Certicom Paris, September 28. 1999 - A new code-cracking challenge set by Certicom has been successfully overcome using 740 computers in 20 countries over a period of 40 days. The code, ECC2-97, is based on a technique known as elliptic curves. Led by Robert Harley, a member of the Cristal project at INRIA, France's National Institute for Research in Computer Science and Control, the 195 researchers involved showed that a 97-bit encryption system based on elliptic curves is more difficult to crack than a 512-bit system based on integers such as RSA-155. Encryption systems based on elliptic curves have been known since the mid-1980s, but have only recently been adopted by leading encryption companies such as RSA Security Inc. Certicom issued its "ECC Challenge" in November 1997, specifying a series of challenges of increasing difficulty. The company offers prizes up to US$100,000. The aim of the challenge is to encourage research in the field of elliptic curves and their applications in encryption, and to strengthen arguments in favor of using elliptic curve cryptography instead of systems based on integer factorization. The challenge dubbed "ECC2-97" took place in a set of about 10^29 points on an elliptic curve chosen by Certicom. To solve the problem, participants first computed 119,248,522,782,547 (more than 10^14) using open-source software developed by Harley. Among these points, they screened 127,492 "distinctive" points and collected them on a Alpha Linux workstation at INRIA where further processing revealed two twin points. Finally Harley computed the solution using information associated with these two points, thus nailing the problem. The solution was found after less than one third of the predicted computation. The probability of finding the answer so quickly was less than one in ten. Two other twins were detected a few hours after the first - a less than one in 100 probability! Nevertheless the computing power used, around 16,000 MIPS/years, was twice as much as that used for the factorization of RSA-155 announced by Herman Te Riele of CWI (Amsterdam) and his colleagues on 26 August 1999. "These results strengthen our confidence in codes based on properly-chosen elliptic curves," said Harley. "This needs to be taken into account in standards for security and confidentiality on the Internet." According to Andrew Odlyzko, Head of Mathematics and Cryptography Research, at AT&T Labs, the code-cracking operation was "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". He added: "It validates theoretical security predictions, and demonstrates the need to keep increasing cryptographic key sizes to protect against growing threats." 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 RSA-155 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." Out of the $5000 prize money, the team members will give $4,000 to the Free Software Foundation to encourage the creation of new free software. The remaining $1,000 go to the team members who identified the twin points. Both were in fact found by Paul Bourke using a network of Alpha workstations, mainly used for studying pulsars at the Centre of Astrophysics at Swinburne University in Australia. The most active teams in the project were: Astrophysics & Supercomputing Australia INRIA France University of New South Wales Australia "Friends of Rohit Khare" USA and France Ecole Polytechnique France Compaq USA and Italy Technischen Universität Wien Autriche University of Vermont USA "WinTeam" International British Telecom Labs UK Internet Security Systems UK Rupture Dot Net USA "Jabberwocky" USA Ecole Normale Supérieure de Paris France For a complete list of participants consult the project's Web pages. Further information: The ECDL Project http://cristal.inria.fr/~harley/ecdl/ The Certicom ECC Challenge http://www.certicom.com/chal/ Technical contact: Robert Harley, INRIA : 33 1 39 63 51 57 - [EMAIL PROTECTED] Media contacts: Christine Genest, INRIA : 33 1 39 63 55 18 - [EMAIL PROTECTED] Sylvie Baranger, Andrew Lloyd & Associates : 33 1 43 22 79 56 - [EMAIL PROTECTED] ------------- End Forwarded Message ------------- --- end forwarded text ----------------- Robert A. Hettinga <mailto: [EMAIL PROTECTED]> The Internet Bearer Underwriting Corporation <http://www.ibuc.com/> 44 Farquhar Street, Boston, MA 02131 USA "... however it may deserve respect for its usefulness and antiquity, [predicting the end of the world] has not been found agreeable to experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
