Certicom ECC Challenge

Elliptic Curve Discrete Logarithms: ECC2-97

The first two matching distinguished pointer were both found by the supercomputer farm!

4K Associates Press Release
INRIA Press Release
ComputerWorld
Le Monde
Tasty Bits
ZDNet
Toronto Globe & Mail
Data Communications


Early in September 1999 the idle time on the supercomputer farm was put towards a global project to solve the latest Certicom ECC challenge. As with the last two challenges (ECC2K-95 and ECCp-97), solving challenge ECC2-97 attracts a $5000 prize. The first six problems in the Certicom ECC challenge have been already been solved. This next problem called ECC2-97 and is considered the hardest one so far. The code and the organisation for the challenge was organised and distributed by Robert Harley of INRIA. It is thought that this is the biggest calculation ever to use a true parallel algorithm! The total amount of work is expected to be between 40000 or 50000 MIPS-years which is twice as much as ECCp-97 took and five times as much as the recently completed factorisation of RSA-155.

There have been a few bigger distributed calculations. For instance a DES crack by exhaustive search is 5 to 10 times bigger, but no parallel algorithm is required. In such a case, coordination is not necessary so it doesn't matter much whether one group organises the whole lot or ten groups each organise separate smaller calculations using different software (and dedicated hardware!) Some work may be duplicated but that causes only a small constant-factor slowdown. In the end, one lucky individual finds the DES key. Likewise with RC5 cracking. Same thing with finding a new Mersenne prime or a SETI@home block with a message from aliens. However large factorisations and discrete logarithm calculations are more complex. No single person finds the answer. Ten teams each doing ten times less work would have little hope of success. With this ECDL project, the answer can only be found because the participants are all working together using the same distinguishing feature, the same pseudo-random hash function and because everybody's distinguished points are being compared with everyone else's.

The software to solve this challenge was released to the participants on the 13th August, the Center for Astrophysics and Supercomputing joined the group on the 1st of September. The software ran on each node at a maximum "nice" value so that it only used idle time on the farm and didn't interfere with the real work. Initially the software was only available for UNIX platforms but by the 11th of September there were versions avialable for most flavours of UNIX as well as for Macintosh and machines running Microsoft Windows.

Typically a 400MHz 2 processor 686 running Windows find around 4-6 distingiushed points per day, a single processor R8000 SGI Indigo finds 2-4 points per day, the Dec Xp1000 ev6 processors in the farm were finding between 20 and 30 points per day depending on the load by other users. Therefore the supercomputer farm quickly put us ahead of the other players, the final distribution (24th September) of distinguished points by team is shown in the table below (only those groups who found more tlhan 500 points are shown).

Position Group Total
1 Astrophysics_Supercomputing 38633
2 INRIA 16963
3 SchlagTeam 12701
4 FoRK 8751
5 Compaq 8451
6 Polytechnique 5826
7 Alan Ling 5360
8 WinTeam 4505
9 TU Wien 4253
10 SOR 3435
11 CMS Vienna 3126
12 ISS 2718
13 BT Labs 2677
14 Rupture Dot Net 2349
15 LIX 1685
16 IRIX 1325
17 Jabberwocky 1306
18 ENS 1179
19 Maksimisoolo 1107
20 Entrust Technologies 1094
21 TAEUS 935
22 Network Alchemy 901
23 csmith 851
24 Paraski 771
25 MyTeam 741
26 LUT 738
27 USYD 721
28 MacTeam 645
29 Aphelion 632
30 Alpha OSF1 537
31 STF at large 518
32 Dublin 516
33 Brain_Dynamics 516
34 foobar 508

At 1pm on the 21st of September the machine called "ssi15" found a point matching an earlier one found by machine "it5". The match was found earlier than expected with a probability of 1 chance in 12.

The answer was: 64206457470187038759216338447 modulo 79228162514264464603828067969.

History
ECCp-79, solved on December 6th 1997.
ECC2-79, solved on December 16th 1997.
ECCp-89, solved on January 12th 1998.
ECC2-89, solved on February 7th 1998.
ECCp-97, solved on March 16th 1998 in association with British Telecom Labs.
ECC2K-95, solved on May 21st 1998.
ECC2-97, solved on September 22nd 1999.

Quotes
Serge Vaudenay, chargé de recherche au CNRS:

« L'Etalonnage de la complexite des problemes cryptographiques est indispensable pour proposer le meilleur compromis entre efficacite et securite. La performance technique realisee par Robert Harley constitue un resultat de premier ordre dans cette perspective. »

Andrew Odlyzko, Head of Mathematics and Cryptography Research at AT&T Labs:

"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 that "validates theoretical security predictions, and demonstrates the need to keep increasing cryptographic key sizes to protect against growing threats."

Dr. Robert Zuccherato, senior cryptographer in the advanced security technology group 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. 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."


Certicom Challenge ecdl2K-108

Started 6 December 1999

Status

Completed, solved on the 4th April 2000. The total amount of computation was even more (by 50 %) than a secret-key DES crack. The lucky people who found the matching points were Jean-Frederic Clere from Apache Team and Asa Reed from Colorado Group. Jean-Frederic found one of the points with the Unix64 program and sent it in on the 28th of March at 15:52:17. Asa found the other with the WinGUI version and sent it on the 3rd of April at 15:01:08.

Machine statistics

The following table gives the names, attributes, and iteration rate of machines being used by the Astrophysics and Supercomputing team.

M a c h i n e
n a m e
M a c h i n e
t y p e
O p e r a t i n g
S y s t e m
E C D
B I T S
I t e r a t i o n s
p e r s e c o n d
alphix Digital XP1000, EV6.7 (21264A), 667MHz Tru64 4.0F 64 386,000
jocelyn Compaq AlphaServer ES40, DECchip 21143, 667MHz Tru64 4.0F 64 375,000
ssi 0->24
it 0->8
iris 0
vr 0->2
crc 0->2
Digital XP1000, EV6 (21264), 500MHz Tru64 4.0F 64
Optimised
32
289,000
305,000
81,000
maths 0->2 Digital XP1000, EV5.6 (21164A), 599MHz Tru64 4.0F 64 242,000
psr 1->15 Digital XP1000, EV5.6 (21164A), 500MHz Tru64 4.0F 64 201,000
WWW Digital XP1000, EV5.6 (21164A), 532 MHz Tru64 4.0F 64
32
201,000
69,000
HP HPVisualise, E9000, 600MHz HPUX V10 32 128,000
whiz, kid Pentium II, Dual processor i686, 350MHz Linux 6.0 32
Optimised
Optimised MMX
42,000
84,000
113,000
pegasus PowerPC G3, 350MHz Mac OS 8.6 32 66,000
jim Pentium III, i686, 450MHz Linux 6.1 32
Optimised
54,000
89,000
cpu, nfs SGI Indigo, 250MHz IP22 (R4400) IRIX 6.5 32 48,000
marr SGI O2, 180MHz IP32 (R5000) IRIX 6.5 32 40,000
cortex DEC 3000 Digital UNIX V3.2 32 16,000

Estimates recorded during the "event"

Second day
On the 6th December the points were being found by the cluster at a rate of 800 per day. Given that it is estimated it will take 1.3 million, this comes out to just under 4.5 years. Sigh! Lets hope a LARGE number of other groups join in.

End of first week
At the end of the first week (still early days) all the teams combined have found 15,000 points. At this rate the target of 1,300,000 will be reached after about 85 weeks.

16 December
The points are now coming in at 3100 per day (average over the last 5 days). At this rate it will take over 400 days, just over 1 year. A goal would be to triple this to bring the likely completion date to around the end of April 2000.

24 December
Finally, the challenge has reached 10,000 points per day. The ETA then for 1.3 million points is 130 days. The rate per day seems to be increasing but that could be due to free machines over the Christmas break.

10 January 2000
The average points per day seems to have leveled out at just over 12,000 perday, 84,000 per week, about 360,000 per month. At this rate, 1 million points will be reached by the end of March.

20 February 2000
Just hit 1,000,000 points and doing over 130,000 per week. Must be getting close with around a 50% chance of success.

End of February 2000
Formed the "Death Star Rising" team.

5 April 2000
Solved by Jean-Frederic Clere from Apache Team and Asa Reed from Colorado Group.

Summary by the Organisers

People: Over 1300 people sent in results (This number is an approximation since some registered several times whereas others participated without registering)

Machines: 9500 machines sent in at least one result. (This is again an approximation since some people gave a single name covering several machines whereas others gave varying names for a single machine). At any given time, about 5000 were actively sending in results.

Time: we started at the beginning of December and took just over four months.

Amount of computation: the calculation would have taken about 200000 days on a 450 MHz PC with MMX, i.e. more than 500 years. For comparison, cracking a 56-bit DES key by exhaustive search would take about 110000 days. On a 500 MHz Alpha 21164, the times would be about two thirds (for ECDL) and one half (for DES) respectively.

Elliptic-curve operations: altogether we did about 2.8 × 10^15 elliptic-curve operations of which 2.3 × 10^15 led to distinguished points recorded at INRIA. We collected 2.05 million distinguished points in 1.3 Gigabytes of email.

Machine speeds: the fastest were...

Operations per second CPU Clock speed Program version O.S.
454 k Alpha 21264 750 MHz 64 bit Linux
416 k Alpha 21264 667 MHz 64 bit Tru64 Unix
355 k PowerPC G4 450 MHz Altivec MacOS
349 k Athlon 1 Ghz MMX Win98

Machine and OS type: the points sent in split up into three thirds...

The remaining 2% was on MacOS, OS/2, BeOS etc.

Solution: The people who found the matching points that finally enabled us to calculate the solution were: Asa Reed with Colorado Group and a person who prefers to remain anonymous (and who is donating his $1000 to the Apache Software Foundation).

The points were well distributed among the teams, with no single team dominating. Top 10 teams:

% Team Remarks
12.5 INRIA Mostly INRIA people, also using lots of École Polytechnique machines
12.3 Death Star Rising AT&T, Swinburne Astrophysics and others
7.0 CLX Linux group from the north of France
6.6 FoRK Friends of Rohit Khare mailing list, plus a contingent from Red Hat
5.8 Pingouins Bretons Linux group from the west of France including IRISA
4.9 Entrust Cabalist Alliance Entrust Technologies + the "cabalists" who factored RSA-155
4.9 No Team Yet Over 200 people who didn't pick any team!
2.6 University of Kentucky Like the name says
2.3 TU+CMS Wien Technical University of Vienna, Austria
2.2 URZ Uni Ulm University of Ulm in Germany

Likewise with participants. The top 10 participants were:

% Name Affiliation
4.1 Paul Bourke Swinburne Astrophysics & Supercomputing, Australia
3.7 Rajit Manohar Cornell Computer Systems Laboratory
3.2 Bruno Verlyck INRIA
2.5 Philippe Deschamp INRIA
2.4 Vincent Goffin AT&T
2.2 Bernd Leibing University of Ulm, Germany
2.1 Mark A. Brown Rhythm and Hues Studios, L.A.
1.5 Dan Schwartz Lehigh University, Pennsylvania.
1.5 Patrick Ménager EUDIL, Lille, France
1.3 David Mentré IRISA, Rennes, France