In order to gain exposure and to jumpstart the expert scrutiny that ECC will need if it is to be widely trusted, Certicom is sponsoring a multi-part crypto challenge.
This page records the achievements of the individuals and groups who crack the various challenges.
The announcements below are all copyright 1997-1998 by Robert Harley.
To: certicom-ecc-challenge@certicom.com6th of December, 1997.
Dear Anonymous,
Certicom's professed aim in setting its ECC challenge is to encourage research into secure cryptosystems based on elliptic curve discrete logarithms. Yet Certicom is a member of the Key Recovery Alliance, a lobby group whose purpose is to promote the use of back-doors allowing supposedly secure communications to be intercepted. How are these contradictory positions reconciled?
The solution to your ECCp-79 problem is the residue class of 92221507219705345685350 modulo 466597814831947642887217. It was found by Wayne Baisley and myself using several Digital Alpha workstations running Linux and Digital Unix at the Institut National de Recherche en Informatique et Automatique (INRIA), at Fermi National Accelerator Laboratory and at the California Institute of Technology C.S. Department.
The method used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a random function (the same on all machines) until a collision was detected at 17:58 today at INRIA, Rocquencourt, France by a 500MHz Linux machine. This machine did 25 billion elliptic curve operations per day. The peak rate of all machines was approximately 6 six times as much. A total of about 1400 billion iterations were performed.
If this is the first correct submission, please send the prize (a copy of "Handbook of Applied Cryptography" and Maple software) to the following address:
Robert Harley, c/o Sylvie Loubressac, Projet CRISTAL, INRIA, Domaine de Voluceau - Rocquencourt, 78153 Le Chesnay, France. Thank you, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-'
Robert J. Harley,
Sevres, France,
16th of December, 1997.To: certicom-ecc-challenge@certicom.com
Dear Mr. Gallant,
There are two types of communications. On the one hand are secure communications, intelligible only to their intended recipient, and on the other are all the rest. Between them, as Louis Freeh would say, there is a "bright line". On what side of that line does Certicom stand?
The solution to your ECC2-79 problem is the residue class of 276856274258963891889538 modulo 302231454903954479142443. The work was led by a group of Alpha Linux enthusiasts, and the British Telecom Labs team joined in too. We used about 30 Alphas running Linux, from UDBs up to 600 MHz workstations. Jay Estabrook's new 21264 machine made a cameo appearance! There were also 4 Alphas running Digital Unix.
Contributors were:
Andries Brouwer Andries.Brouwer@cwi.nl Christopher Brown cbrown@alaska.net Zach Brown zab@zabbo.net Jay Estabrook Jay.Estabrook@digital.com Rick Gorton gorton@amt.tay1.dec.com Oleg Gusev oleg@usm.uni-muenchen.de Robert Harley Robert.Harley@inria.fr Richard Holmes holmes@lanl.gov Andy Isaacson adi@acm.org Greg Lindahl lindahl@cs.virginia.edu Jon Nathan jon@blading.com Dennis Opacki dopacki@mac-guru.com Vance Petree vwp@vancpower.com Tim Rowley tor@cs.brown.edu Michael Sandfort sandfort@post.cis.smu.edu Jason Shiffer jshiffer@home.com Aaron Spink spink@pa.dec.com B.T. Labs Team jcs@zoo.bt.co.uk Bart-Jan Vrielink bartjan@mail.de-boulevard.nl Marinos Yannikos nino@complang.tuwien.ac.at Xiaoguang Zhang xgz@mn.ms.ornl.govand some anonymous others.The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 12:47 today. A total of 1737410165382 iterations were performed, finding 1617 "distinguished" points and one collision. Our source code can be downloaded from:
http://pauillac.inria.fr/~harley/ecdl/ We would like to thank Michael Wiener for sending his paper, co-authored with Paul van Oorschot, in which they suggest using distinguished points for discrete log calculations. We used this idea to simplify our client program.
Thanks also to John Sager who spotted a broken line of code in one version of the program. We were quickly able to verify that it had caused no harm.
If this is the first correct submission, then, well I don't really know what you should do with the prize! Perhaps hold a raffle among the contributors?
Thank you, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-'
To: certicom-ecc-challenge@certicom.comRobert J. Harley,
Rocquencourt, France,
12th of January, 1998.Dear Mr. Gallant,
Please note that this submission, like the previous two, carries a copyright notice. If you wish to quote it on your Web pages, or anywhere else, you may not strip off the copyright notice nor replace it with "Copyright Certicom Corp." or any similar notice.
The solution to your ECCp-89 problem is the residue class of 333373190151749761757285479 modulo 416363315556124458285894983. The calculation was carried out in 24 days by a group of 57 people using Alpha workstations running Linux, Digital Unix, VMS and NetBSD:
Zach Brown Jon Reeves Dragisa Duric Tim Rowley Martin Edu John Sager Adrian Escott Michael Sandfort Douglas Frank Mike Schloss Rick Gorton Alex Selkirk Oleg Gusev Al Simons Robert Harley Aaron Spink David Hauan Murray Stokely Dave Hill Adrian En-Wei Sun Richard Holm Peter Swardes Chatchai Janta Greg Thomasraprim Olav Kongas Dimitris Tsapakidis Mika Kortela Jeff Uphoffinen Edward Lee Marko Vendelin Greg Lindah Carlos Vidall Brian Lund Bart-Jan Vrielink Rob Millner Tom Woodburn Francois Morai Berndt Josef Wulfn Pete Murray Marinos Yannikos Jon Nathan Paul Youngand a person who prefers to remain anonymous.The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 15:33 today. A total of 24249418904337 iterations were performed, finding 36345 "distinguished" points and one collision. The British Telecom team found 11333 of the points, people from Digital found 7853, people from INRIA found 4680 and individuals in more than a dozen countries found 12479. Our source code can be downloaded from:
http://pauillac.inria.fr/~harley/ecdl2/ Bye, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-'
To: certicom-ecc-challenge@certicom.com
Robert J. Harley,
Sèvres, France,
7th of February, 1998.Dear Mr. Gallant,
The solution to Certicom's ECC2-89 problem is the residue class of 41871609686648820507900581 modulo 309485009821357445894232317. The calculation was carried out in 26 days by a group of 70 people in 17 countries. 95% of the work was done on Alpha workstations running Linux and Digital Unix and the remaining 5% was done on various 32-bit machines.
The fastest, naturally, were 600 MHz Alpha systems doing 241 K elliptic curve operations per second each. The fastest 32-bit systems were 233 MHz StrongARM NCs running NetBSD at 55 K each. Several other systems contributed too including a bunch of Pentium and Pentium Pro machines with Linux, a few Sparcs with SunOS, a 150 MHz SGI MIPS with Irix, an old 80 Mhz HP PA with NextStep and a Cyrix 486 DX2. Last and definitely least were my trusty old 8 MHz ARM 2's running RISC OS (hey, they seemed fast ten years ago :).
The people involved were:
Wayne Baisley Greg Lindahl Miguel Barreir Brian Lundo Paz Uri Blument Preda Mihailescuhal Spider Boardma Francois Morainn Alvin Brattli Pete Murray Bill Broadle Jon Nathany Andries Brouwer Burkhard Neidecker-Lutz Zach Brown Wieger Opmeer Bruce Dawson Vance Petree Dr. Sven Dietric Guillaume Pierreh Einar Doerum Martin Radford Dragisa Duric Jon Reeves Martin Edu Brian Romansky Gwyn Evans Geordy Rostad Douglas Frank Tim Rowley Megan Gentry Andrew Sapozhnikov Rick Gorton Aaron Sawyer Thomas Gschwin Mike Schlossd Oleg Gusev Al Simons Mikolaj Habryn Mikko Siren Robert Harley Chris Smith David Hauan Mark Smith Mike Iglesia Murray Stokelys Chatchai Jantara Adrian En-Wei Sunprim Travis Johnson Peter Sward Martin Kahlert Marko Vendelin Asim Kepkep Paul Verwer Rohit Khare Bill Viggers Mika Kortela Bart-Jan Vrielinkinen Andreas Krall Dan Weeks Edward Lee Michael Wins Dr. Hiankiat Lee Tom Woodburn Leon Lessing Gregory Woodburyand the British Telecom team, some students of the Ecole Centrale de Lille and a person who prefers to remain anonymous.The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 16:21 today.
A total of 18161819582507 iterations i.e., over 18000 billion, were performed finding 17543 "distinguished" points. Two of the points, found by Guillaume Pierre of INRIA and Bill Broadley of U.C.Davis, were in fact equal allowing us to compute the final answer. Since an ECC2-89 iteration took close to twice as long as an ECCp-89 iteration, this was the most difficult calculation we have done so far.
Participants at INRIA found 3653 points using machines belonging to the following projects: Air, Algo, Codes, Coq, Cristal, Méval, Para, Sor and Sosso. Those at Digital found 4591 points, and others found 9299.
Our source code can be downloaded from:
http://pauillac.inria.fr/~harley/ecdl3/ We invite anyone interested in working on the next calculation to point their Web browsers at:
http://pauillac.inria.fr/~harley/ecdl4/ Bye, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-' ------------------------------------------------------------------------------
RESULTThe solution to Certicom's ECCp-97 problem is the residue class of 1 6C86AA7C ACF69F1D D28B3E2F modulo 1 6EA1595E D21AE98F B6CCA20D The calculation was carried out in 53 days by a group of 588 people and 1288 machines in more than 16 countries. It was found after 186,364 Distinguished Points. At an expected 2^30 iterations per Point, we estimate it took 200 trillion (200 E12)iterations. We sustained an average rate of 5 trillion (5 E12) iterations per day, for the past two weeks.
We achieved 440K 97bit Elliptic Curve iterations per second on an Alpha 600MHz or 494K on an Alpha 400MHz 21264 prototype. We got 125K iterations/sec from a Pentium II 300 and 39K iterations/sec from a PowerPC 604/120.
The method we used was a "birthday paradox" algorithm iterating from random initial points (distributed over all machines) with a pseudo-random function (the same on all machines) until a collision was detected at 23:38 GMT on Monday 16th of March 1998. The two Points were coincidentally both found by Greg Thomas of BT on two different AlphaServer 8200s, each with four 440MHz 21164A Alpha CPUs.
This effort was organised by the BT Labs team, led by Adrian Escott, John Sager, Alex Selkirk & Dimitris Tsapakidis and by the Linux Alpha group, led by Robert Harley at INRIA.
Our proposed prize distribution is indicated on our web page at http://www.labs.bt.com/projects/security/crackers/p97/ If we have won the prize, then we will discuss the mechanics of this separately.
CREDITS
Robert Harley(INRIA): Original 64bit Alpha code & client, p97 code optimisation, user support, ECC background.
John Sager(BT Labs): 64bit Alpha code conversion to p97, Pentium assembler, VMS & 32bit Unix clients, proxies, ECC background.
Adrian Escott(BT Labs): ECC background, 64->32bit core code conversion.
Alex Selkirk(BT Labs): Windows clients, keyserver.
Dimitris Tsapakidis(BT Labs): Live stats & user support.
Dave Parkinson(BT Labs): Pentium assembler.
Jake Hill(BT Labs): Mac client & PowerPC assembler.CONTRIBUTORS
222 Alpha machines produced 103,000 Points or 55.3%,
753 Pentium machines produced 73,691 Points or 39.5% the rest were produced by Sparcs, Macs, HPs and others.The groups & people involved follow. Figures denote Points found and total contribution.
BT Labs 131163, 70.38%
[484 email addresses]
digital 14794, 7.94%simons@zk3.dec.com gorton@amt.tay1.dec.com schloss@zk3.dec.com reeves@zk3.dec.com frank@zk3.dec.com gorton@400mhz_proto@amt.tay1.dec.com
inria 14472, 7.77%robert.harley@inria.fr guillaume.pierre@inria.fr
legion project 4961, 2.66%lindahl@cs.virginia.edu
tu wien 3153, 1.69%andi@complang.tuwien.ac.at nino@complang.tuwien.ac.at
university of tromsoe 2308, 1.24%frodef@acm.org tobias@td.org.uit.no alvin.brattli@phys.uit.no
duke university - demographics 2032, 1.09%ggw@cds.duke.edu
barbarian brothers 1065, 0.57%gorton@thetick.antix.com
csmith 1006, 0.54%csmith@stoneboro.uucp.cirr.com
lut 920, 0.49%bande@lut.fi
alcar group 839, 0.45%edlee@chinet.chinet.com
digital unix internet security 712, 0.38%spider@leggy.zk3.dec.com
hist institutt for databehandling 703, 0.38%einarfd@tihlde.hist.no
vuw:school of earth sciences 699, 0.38%bill@geo.vuw.ac.nz
de boulevard 691, 0.37%bjv@de-boulevard.nl robijn@robijn.de-boulevard.nl
stf at large 642, 0.34%spock@abraxas.adelphi.edu
pitney bowes 585, 0.31%romansbr@pb.com
lessing research 542, 0.29%leonl@icon.co.za olive@ilink.nis.za rui@ilink.nis.za
bucknell university 496, 0.27%jwilkins@bucknell.edu systems@bucknell.edu weber@bucknell.edu
penn state university 457, 0.25%duvernoi@psu.edu
daydreamers 341, 0.18%christopher.endsley@interimtechnology.com
sunquest information systems 338, 0.18%terry@venus.sunquest.com
digital equipment corporation 324, 0.17%woodburn@zk3.dec.com gelinas@zk3.dec.com
center for water research 310, 0.17%dichro-ecdl@eris.rcpt.to
centrale_lille 221, 0.12%mainaud@ec-lille.fr masson@ec-lille.fr girolami@ec-lille.fr lenzotti@ec-lille.fr vanhouv9@cti.ecp.fr je@eclia5.ec-lille.fr rezoleo@eclia5.ec-lille.fr gallico@ec-lille.fr cornet@ec-lille.fr
solnet 191, 0.10%fli@trekkers.org fli@solnet.sollentuna.se
unb 187, 0.10%jeffg@nbnet.nb.ca
danimal 167, 0.09%danimal@pobox.com
rupture dot net 157, 0.08%jon@blading.com
fermi national accelerator lab 150, 0.08%baisley@fnal.gov
none 148, 0.08%sysadmin@wolf.hip.berkely.edu gevaryah@netaxs.com wieger@dublin.student.utwente.nl sysadmin@wolf.hip.berkeley.edu
ethz informatik 142, 0.08%mihailes@inf.ethz.ch
the obfuscation organization 120, 0.06%techs@obfuscation.org
jaap 115, 0.06%schj@anna.xs4all.nl
digital equipment corporation, unix support engineering group 108, 0.06%gentry@zk3.dec.com
gaillon 98, 0.05%a1504d@micronet.fr
art - futures testbed 83, 0.04%margarida
max-planck institute for plasma physics 79, 0.04%dpc@ipp.mpg.de
damicon kraa ltd. 74, 0.04%msiren@damicon.fi
le free french 70, 0.04%charles@degaulle.com
home 58, 0.03%metal@ton.tut.fi
dso 53, 0.03%lhiankia@dso.org.sg
caos/camm center 52, 0.03%verwer@caos.kun.nl
macintosh 52, 0.03%lcollie@compuserve.com j-beda@pobox.com doolittl@uiuc.edu bluequark2@aol.com mattkime@usa.net seth@snet.net
freeth's 50, 0.03%k.brincat@rhbnc.ac.uk
aa-tech 47, 0.03%antinoja@netlife.fi
duchy of wabesylvan obspauk 47, 0.03%spider@orb.nashua.nh.us
systems test engineering 38, 0.02%dawson@nio.dec.com
harijs 35, 0.02%harijs@parks.lv
partner communications 31, 0.02%pete@partnercomm.com
team incompetent 30, 0.02%dontknowman@incompetent.to noleadership@incompetent.to loser@incompetent.to
ringzero systems 28, 0.02%arc@cts.com plalone@alphax.com
renaissance internet services 26, 0.01%cadams@ro.com
uninet 24, 0.01%barryn@pobox.com
oxfrod 23, 0.01%mert0236@sable.ox.ac.uk
fbs2 17, 0.01%
glen mcbride 13, 0.01%gmcbride@baynetworks.com
pent 12, 0.01%alnick@mail.wplus.net
delta-net 12, 0.01%daniel@delta-net.com
patanjali 11, 0.01%patanjali@prodigy.net
neural.net 9, 0.00%mdschmoeckel@stthomas.edu
crank 6, 0.00%jdonner@erols.com
tu graz 6, 0.00%harry@igi.tu-graz.ac.at
spunkmunky 5, 0.00%tiensivu@pilot.msu.edu
slap_yo 4, 0.00%lacuran
sas 4, 0.00%sas@minofdefence.demon.co.uk
ecc@computerx.com 3, 0.00%ecc@computerx.com
#macwarez 2, 0.00%goffy@2-cool.com
jobtrak 2, 0.00%schatt@jobtrak.com
al's group 1, 0.00%livalan@tig.com.au Our source code can be downloaded from:
http://pauillac.inria.fr/~harley/ecdl4/ The main project page with more info and stats is at:
http://www.labs.bt.com/projects/security/crackers/p97/ We invite anyone interested in working on the next calculation to point their Web browsers at:
http://pauillac.inria.fr/~harley/ecdl5/
Robert J. Harley,
Sèvres, France,
21st of May, 1998.Dear Mr. Gallant,
The solution to Certicom's ECC2K-95 problem is the residue class of 37837308472231540269443981458 modulo 39614081257132074233778707191. The calculation was carried out in 25 days by a group of 47 people:
Ettore Aldrovandi Michael Pfeiffer Wayne Baisley Jon Reeves Eric Bohm Panu Rissanen Craig Burley Brian Romansky James Childers Anthony Rumble Sven Dietrich Peter Rye Mike Ditto John Sager Einar Dorum Jaap Schellekens Mike DuVernois Mike Schloss Christopher Endsley David Seal Douglas Frank Al Simons Mark Gelinas Mikko Siren Rick Gorton Chris Smith Rick Gorton Ted Spradley Alexey Guzeev Greg Thomas Mikolaj Habryn Bill Viggers Robert Harley Bart-Jan Vrielink Robert Harley Mike Warren Mika Kortelainen Robert Wilhelm Andreas Krall John Wilkins Bernd Meyer Tom Woodburn Andres Meyer Gavin Woodhatch Willi More Berndt Wulf Wieger OpmeerAlmost all of the work was done on 200 Alpha's ranging from desktop workstations to big parallel servers. 60.1% was done with Linux, 36.1% with Digital Unix, 3.4% with OpenVMS and 0.2% with NetBSD. The remaining 0.2% was on 32-bit machines running Linux, Risc OS, Windows NT and OS/2.
Mike Warren made the biggest contribution using the Avalon network of seventy 533 MHz Alpha Linux workstations at Los Alamos. The next biggest teams were Digital, INRIA, Vienna University of Technology, British Telecom Labs, the University of Klagenfurt, Victoria University of Wellington Center for Water Research and "csmith".
The method we used was a birthday paradox algorithm iterating from many random starting points with a pseudo-random iteration and reporting those points with a distinguishing characteristic back to base until a matching pair was found, as for the previous Elliptic Curve Discrete Logarithm records set by Alpha enthusiasts, British Telecom Labs and others who worked with us.
A total of roughly 21600 billion iterations were performed, of which 20202935925971 led to the 74268 distinguished points that were reported back to base. The fastest systems were 600 MHz Alpha's doing up to 177 K iterations per second. A distinguished point matching a previously discovered one was found at 4:31 this morning, allowing us to compute the final answer. The matching points were found by Mike Warren with Avalon and by myself with an Alphastation 500/500 at INRIA.
Since an ECC2K-95 iteration took about 2.5 times as long as an ECCp-97 iteration, this problem was easier by a factor of 3.7. A priori, the two problems appear to be of similar difficulty and since ECCp-97 was solved with a low number of iterations due to good luck, one might have expected this one to be the most difficult yet.
However we used some extra structure by gathering the points into clusters of 194 points (technically, orbits under the involution [-1] and the Frobenius endomorphism [(-1+sqrt(-7))/2]).
We chose a pseudo-random iteration that respected this structure: it was multiplicative, multiplying each point by 2, 6, 88, 90 or 92 according to a pseudo-random function of the orbit it belonged to. The distinguishing characteristic also respected the extra structure.
This variant of the algorithm can be used with any curve but only rarely gives a speedup. For that, it needs a pseudo-random function and a distinguishing characteristic which respect the orbit structure and can be computed quickly. This can be done whenever points can be multiplied by some small-order roots of unity sufficiently quickly, by walking through the entire orbits under those multiplications.
Our first implementation did so by repeatedly squaring the point coordinates in a polynomial basis, gaining a factor of five speed-up! The hint page put up by Certicom, http://www.certicom.ca/chal/note.htm, mentioned using a normal basis in which squaring is just a rotation; this gave a factor of seven. In our final implementation we avoided walking through the orbits by instead using a population count in a normal basis, even though all arithmetic was in a polynomial basis, gaining a factor of ten.
Our source code can be downloaded from:
http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/I would like to point out that the hint-page remark:
>Recently, a successful solution to the ECCp-97 exercise was
>submitted. The ECCK-95 exercise is easier, and suggests that not
>everyone is aware of the speedups available for computing discrete
>logs on a binary anomalous curve.strikes me as particularly disingenuous since when ECCp-97 was started, nobody yet knew how to speed up ECC2K-95. It is all the more disingenuous that the "hint" is to change only the definition of distinguished points, which is not sufficient to get any speed-up at all (although the preprint added later fixed this).
I would also like to thank Rob Zuccherato for sending his and Michael Wiener's paper, "Faster Attacks on Elliptic Curve Cryptosystems", in which they describe another algorithm: they keep an additive pseudo-random function, adapt it for orbits of points and propose a mechanism for getting rid of almost all of the short cycles that would otherwise cause problems.
Finally, I draw the conclusion that cryptographic codes must no longer be based on the difficulty of discrete logarithms on curves defined over GF(2), since these logs are now demonstrably easier than on random curves and since it is not unlikely that much greater weaknesses will be discovered in future.
[ TBTF for 1998-06-01 ]
[ TBTF for 1998-03-23 ]
[ TBTF for 1998-02-16 ]
[ TBTF for 1998-01-19 ]
[ TBTF for 1997-12-24 ]
[ TBTF for 1997-12-08 ]
TBTF
HOMECURRENT
ISSUETBTF
LOGTABLE OF
CONTENTSTBTF
THREADSSEARCH
TBTF