Certicom ECC Challenge

Elliptic Curve Discrete Logarithms: ECC2-97

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).

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.

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

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.

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...

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

• 36% on 32-bit Unix machines (mostly PCs running Linux or BSD),
• 31% on 64-bit Unix machines (many Alphas with Tru64 Unix or Linux, also SPARC, MIPS, HP etc.)
• 31% on Windows PCs

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:

Likewise with participants. The top 10 participants were: