(A Javascript-enabled browser is required to email me.)


Certicom ECC Challenge(s) Cracked
from 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



Certicom is a maker of eliptical-curve encryption software. ECC algorithms are drawing considerable interest and study because they hold out the possibility of offering security comparable to the RSA algorithms using smaller keys, therefore requiring less computation. This possibility is not yet considered verified by most of the mathematics and cryptosystems research community.

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.


ECCp-79

To: certicom-ecc-challenge@certicom.com

6th 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  `-'


ECC2-79

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.gov
and 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   `-'


ECCp-89

To: certicom-ecc-challenge@certicom.com

Robert 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 Holmes                 Peter Sward
         Chatchai Jantaraprim             Greg Thomas
             Mika Kortelainen             Jeff Uphoff
             Greg Lindahl               Carlos Vidal
         Francois Morain          Berndt Josef Wulf
             Pete Murray               Marinos Yannikos
              Jon Nathan                  Paul Young
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 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   `-'


ECC2-89

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 Barreiro Paz       Brian Lund
              Uri Blumenthal         Preda Mihailescu
           Spider Boardman        Francois Morain
            Alvin Brattli             Pete Murray
             Bill Broadley             Jon Nathan
          Andries Brouwer         Burkhard Neidecker-Lutz
             Zach Brown             Wieger Opmeer
            Bruce Dawson             Vance Petree
         Dr. Sven Dietrich       Guillaume Pierre
            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 Gschwind            Mike Schloss
             Oleg Gusev                 Al Simons
          Mikolaj Habryn             Mikko Siren
           Robert Harley             Chris Smith
            David Hauan               Mark Smith
             Mike Iglesias   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 Woodbury
and 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   `-'
------------------------------------------------------------------------------


ECCp-97

RESULT

The 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%                        ethz informatik 142,  0.08%
  [484 email addresses]                         mihailes@inf.ethz.ch
digital 14794,  7.94%                         the obfuscation org. 120,  0.06%
  simons@zk3.dec.com                            techs@obfuscation.org
  gorton@amt.tay1.dec.com                     jaap 115,  0.06%
  schloss@zk3.dec.com                           schj@anna.xs4all.nl
  reeves@zk3.dec.com                          dec, unix supp. eng. gp. 108,  0.06%
  frank@zk3.dec.com                             gentry@zk3.dec.com
  gorton@400mhz_proto@amt.tay1.dec.com        gaillon 98,  0.05%
inria 14472,  7.77%                             a1504d@micronet.fr
  robert.harley@inria.fr                      art - futures testbed 83,  0.04%
  guillaume.pierre@inria.fr                     margarida
legion project 4961,  2.66%                   max-planck inst. pl. phy. 79,  0.04%
  lindahl@cs.virginia.edu                       dpc@ipp.mpg.de
tu wien 3153,  1.69%                          damicon kraa ltd. 74,  0.04%
  andi@complang.tuwien.ac.at                    msiren@damicon.fi
  nino@complang.tuwien.ac.at                  le free french 70,  0.04%
university of tromsoe 2308,  1.24%              charles@degaulle.com
  frodef@acm.org                              home 58,  0.03%
  tobias@td.org.uit.no                          metal@ton.tut.fi
  alvin.brattli@phys.uit.no                   dso 53,  0.03%
duke univ. - demographics 2032,  1.09%          lhiankia@dso.org.sg
  ggw@cds.duke.edu                            caos/camm center 52,  0.03%
barbarian brothers 1065,  0.57%                 verwer@caos.kun.nl
  gorton@thetick.antix.com                    macintosh 52,  0.03%
csmith 1006,  0.54%                             lcollie@compuserve.com
  csmith@stoneboro.uucp.cirr.com                j-beda@pobox.com
lut 920,  0.49%                                 doolittl@uiuc.edu
  bande@lut.fi                                  bluequark2@aol.com
alcar group 839,  0.45%                         mattkime@usa.net
  edlee@chinet.chinet.com                       seth@snet.net
digital unix i'net sec. 712,  0.38%           freeth's 50,  0.03%
  spider@leggy.zk3.dec.com                      k.brincat@rhbnc.ac.uk
hist institutt  databehandling 703,  0.38%    aa-tech 47,  0.03%
  einarfd@tihlde.hist.no                        antinoja@netlife.fi
vuw:school of earth sciences 699,  0.38%      duchy of wabesylvan obspauk 47,  0.03%
  bill@geo.vuw.ac.nz                            spider@orb.nashua.nh.us
de boulevard 691,  0.37%                      systems test engineering 38,  0.02%
  bjv@de-boulevard.nl                           dawson@nio.dec.com
  robijn@robijn.de-boulevard.nl               harijs 35,  0.02%
stf at large 642,  0.34%                        harijs@parks.lv
  spock@abraxas.adelphi.edu                   partner communications 31,  0.02%
pitney bowes 585,  0.31%                        pete@partnercomm.com
  romansbr@pb.com                             team incompetent 30,  0.02%
lessing research 542,  0.29%                    dontknowman@incompetent.to
  leonl@icon.co.za                              noleadership@incompetent.to
  olive@ilink.nis.za                            loser@incompetent.to
  rui@ilink.nis.za                            ringzero systems 28,  0.02%
bucknell university 496,  0.27%                 arc@cts.com
  jwilkins@bucknell.edu                         plalone@alphax.com
  systems@bucknell.edu                        renaissance i'net serv. 26,  0.01%
  weber@bucknell.edu                            cadams@ro.com
penn state university 457,  0.25%             uninet 24,  0.01%
  duvernoi@psu.edu                              barryn@pobox.com
daydreamers 341,  0.18%                       oxfrod 23,  0.01%
  christopher.endsley@interimtechnology.com     mert0236@sable.ox.ac.uk
sunquest information systems 338,  0.18%      fbs2 17,  0.01%
  terry@venus.sunquest.com                      email
digital equipment corporation 324,  0.17%     glen mcbride 13,  0.01%
  woodburn@zk3.dec.com                          gmcbride@baynetworks.com
  gelinas@zk3.dec.com                         pent 12,  0.01%
center for water research 310,  0.17%           alnick@mail.wplus.net
  dichro-ecdl@eris.rcpt.to                    delta-net 12,  0.01%
centrale_lille 221,  0.12%                      daniel@delta-net.com
  mainaud@ec-lille.fr                         patanjali 11,  0.01%
  masson@ec-lille.fr                            patanjali@prodigy.net
  girolami@ec-lille.fr                        neural.net 9,  0.00%
  lenzotti@ec-lille.fr                          mdschmoeckel@stthomas.edu
  vanhouv9@cti.ecp.fr                         crank 6,  0.00%
  je@eclia5.ec-lille.fr                         jdonner@erols.com
  rezoleo@eclia5.ec-lille.fr                  tu graz 6,  0.00%
  gallico@ec-lille.fr                           harry@igi.tu-graz.ac.at
  cornet@ec-lille.fr                          spunkmunky 5,  0.00%
solnet 191,  0.10%                              tiensivu@pilot.msu.edu
  fli@trekkers.org                            slap_yo 4,  0.00%
  fli@solnet.sollentuna.se                      lacuran
unb 187,  0.10%                               sas 4,  0.00%
  jeffg@nbnet.nb.ca                              sas@minofdefence.demon.co.uk
danimal 167,  0.09%                           ecc@computerx.com 3,  0.00%
  danimal@pobox.com                             ecc@computerx.com
rupture dot net 157,  0.08%                   #macwarez 2,  0.00%
  jon@blading.com                               goffy@2-cool.com
fermi national accelerator lab 150,  0.08%    jobtrak 2,  0.00%
  baisley@fnal.gov                              schatt@jobtrak.com
none 148,  0.08%                              al's group 1,  0.00%
  sysadmin@wolf.hip.berkely.edu                 livalan@tig.com.au
  gevaryah@netaxs.com                         
  wieger@dublin.student.utwente.nl            
  sysadmin@wolf.hip.berkeley.edu              
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/


[ 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 ]