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
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."
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.
------------------------------------------------------------------------------
-- B.K. DeLong Research Lead ZOT Group617.642.7149 bkdelong@zotgroup.com http://www.zotgroup.com