CONTEST NOW CLOSED

The Contest

---

We have published a set of ECC public keys. A participant had to find the corresponding private key of each public key solving an ECDLP (Elliptic Curve Discrete Logarithm Problem).

Contest Material

---

Click the button below to download the set of ECC public keys. The corresponding solutions are now available too.

Click here to Download Contest Material Click here to Download the solutions

We also provide a specimen file (with two simple keys to attack), alongside the corresponding solution, in the format you should use to submit your results.

Click here to Download the specimen file Click here to Download the solutions

The format for Contest Material is a text file. Each public key is represented by 5 lines, and is separated from the next with a blank line.

• The first line contains a counter identifying the public key (1, 2, 3, ...).
• The second line contains a prime number p that is the cardinality of the base field.
• The third line contains two elements of F_p: A, B that describe an elliptic curve E of the form y² = x³ + A·x + B, defined over F_p.
• The fourth line represents a rational point P of E via its coordinates (X, Y).
• Finally the fifth line describes the actual public key, that is a rational point Q of E that is a multiple of P (Q= k P for some k).

Participants are required to the find the integer k for each public key given.

Warning for Windows users: If you open the file (i.e. in bloc notes) you might see all public keys on a single line. It should not be too difficult to process them manually or automatically to have each public key in the appropriate format.

Read the Instructions below for further info.

Submission of Contest Solutions

---

A participant is identified by a unique email address. A participant may submit one or more solutions to the contest at any time between the publication of Contest Material and the end of the context, which is set on Friday, 23th October at 17:00.

You submit a Contest Solution sending a mail to contest.cryptolabtn at gmail.com.

A submission may consist of one or more solution for a subset of the proposed ECC public keys. Multiple submissions are allowed but only the first three submission for each public key will be considered valid. Further submissions will be discarded. Format for submission is a text file. Each line will represent a contest solution for a single public key and it will contain two numbers written in decimal base and separated by a space: a counter identifying the public key (1, 2, 3, ...) and the corresponding private key.

Coding

---

Do I have to code my own program to solve ECDLP (Elliptic Curve Discrete Logarithm Problem) and find the private key? Short answer is: No, but Yes.

Long answer is: we have no way of checking if you have written your code to solve our contest (we are not asking to show the code and you can work in whichever programming language you prefer). And it will be probably be easier to look around for some already existing program which does all the work. But the whole point of this contest is to challenge yourself to understand a cryptographic problem, look out for possible solutions, write code that implements the solutions and try to make it more and more efficient.

Do I have to cook my own algorithms to solve ECDLP (Elliptic Curve Discrete Logarithm Problem) and find the private key? Absolutely not!

There are tons of good algorithms which might break short or weak keys. Look around and find an algorithm that you are able to understand. Then try to implement it. This already looks like a good strategy to have fun in the contest.

Mathematical Framework

---

What is the ECDLP?

Given an elliptic curve E defined over a finite field F_q, a point P ∈ E(F_q) of order n and a point Q= kP, where 1 ≤ k ≤ n-1, the ECDLP consists in determining k. The Point Q is called public key, while k is called private key.

A contest solution for a single public key Q consists of the integer k such that kP = Q.

Why are we interested in ECDLP?

The computational intractability of the Elliptic Curve Discrete Logarithm Problem underlies most elliptic curve cryptography.

Do you know what is ECC algorithm? If not, go learn something about it!

An example of ECC cryptography is the Elliptic Curve Digital Signature Algorithm (ECDSA), an algorithm for digital signature. It offers a variant applied to elliptic curves of the Digital Signature Algorithm (DSA) and his security is based on the difficulty of ECDLP under certain hypothesis.

Digital signature schemes are designed to provide the digital counterpart to handwritten signatures. The digital signature is a number dependent on some secret known only to the signer, the signer's private key, but everyone is still able to check the signature using public data: the signer's public key.

We refer to Wikipedia for a more detailed view of ECDSA.

The contest material is a set of ECC public keys. We will not give you encrypted messages to be decrypted.

CONTEST NOW CLOSED

Final ranking

---

Rk	Participant	Time of Last Submission	Valid Keys
1	Crypto Terroni Team(*)	2015/10/22 - 19:19	20
2	Luca Chiodini	2015/10/21 - 21:24	14
3	Lorenzo Cameroni - Alessandro De Piccoli	2015/10/23 - 16:32	14
4	Anomalous Marty with Delorean	1985/10/21 - 15:26	1
5

(*): Team formed by Giuseppe Vitto, Carmine Abate, Giuseppe Cotardo.

Stats

---

• Participants: 4
• Submissions: 32
• Broken Keys: 20
• Unbroken Keys: 0

Prizes

---

The real prize you get from participating in this contest is having fun learning and doing things by yourself!

To give an additional incentive, the winner will be awarded free membership to Clusit. Those who will rank in the first three positions will be invited to attend (for free) all the events the CryptoLabTN will host during all 2015 and 2016. Moreover we will treat them to lunch the day of the award ceremony.

Prizes will be awarded during an event organized at University of Trento (updates will follow).

Ranking

---

Ranking among participants is done considering the following two simple rules applying to all valid submissions.

1. A participant ranks higher than another participant if it has broken more public keys.

2. A participant ranks higher than another participant with the same number of broken public keys if his/her last valid submission for a broken public key was done earlier in time.

How did we design the contest?

---

We used Magma software to generate a lot of curves with random parameters and then we selected them according to various parameters as we wanted:

• a few curves with supposedly secure parameters (for example large prime field, large set of rational points, etc) but actually insecure,
• some weak curve that is stronger than how it looks,
• some "average" curve.

In this light, the main trick used to choose the curves was to factorize the order of the elliptic curve generators. In fact, curves defined over large prime fields whose generator's order factorizes in many primes are very vulnerable to the Pollard-Rho attack. On the other hand if the order is prime this vulnerability does not exist and so a curve defined over a smaller prime-field might actually be more secure than curves defined over larger prime fields. Furthermore, we proceeded to test every curve with the discrete logarithm algorithm of Magma (that implements Pollard-Rho and various optimizations) to check out the amounts of time required to break them.

Finally we selected curves that we broke in few seconds, few minutes, few hours and a nasty curve that despite being defined over a prime field of only 75 bits, took almost 3 days to be broken.

On top of that we added an anomalous curve, taken from safecurves.cr.yp.to, to raise awareness on this vulnerability. We strongly suggest to check out the website to learn more about the security of the curves in ECC.

As a final advice we suggest the reading of this interesting pdf to learn more about ECC and ECDSA. In particular Section 8.1 recaps all the main attacks on ECDLP. Have a nice read!

Feedback from participants

---

We asked the participants the following questions:

• Are you a student?
• Where are you from?
• Did you code some algorithm to participate? In which language? Which algorithms did you code?
• Did you use some existing tools? which ones?
• Did you have access to a cluster or you just used personal desktops/laptops?
• Did you learn something new on ECC?

We report here the answers from the participants.

---

Carlo Brunetta (Anomalous Marty with Deloran, ranked 4th)

• Are you a student?

Yes.

• Where are you from?

Practically Trento.

• Did you code some algorithm to participate? In which language? Which algorithms did you code?

Just some code for make algebraic calculus easier. It was written in Python/Sage. The algorithm is a particular attack over a special family of weak curves.

• Did you use some existing tools? Which ones?

Pen and paper and a Delorean DMC-12 with a flux capacitor to send the answer in 1985.

• Did you have access to a cluster or you just used personal desktops/laptops?

ust 0 second of the laptop and some days on paper to understand why it works.

• Did you learn something new on ECC?

Yes, quite a lot.

---

Luca Chiodini (ranked 2nd)

• Are you a student?

Yes, I am studying computer science at the University of Milano - Bicocca.

• Where are you from?

I live near Bergamo.

• Did you code some algorithm to participate? In which language? Which algorithms did you code?

I wrote a script in SageMath for doing the basic calculations (for instance, to calculate the order of a point in the given elliptic curve).

• Did you use some existing tools? Which ones?

I used the cloud platform of SageMath and ECDLP solver, which in turn uses a version of Pollard Rho algorithm to break keys.

• Did you have access to a cluster or you just used personal desktops/laptops?

I used only my personal desktop.

• Did you learn something new on ECC?

I learned all the details of ECC just for this contest.

---

Alessandro De Piccoli (ranked 3rd)

• Are you a student?

Yes, I am.

• Where are you from?

I'm from Varedo (MB), Lombardia, Italy.

• Did you code some algorithm to participate? In which language? Which algorithms did you code?

I coded baby step giant step and pollard rho using pari/gp. The first was simple but it was expensive in terms of memory, so I thought to store results in a .txt file but at the size of 300Mb I stopped the process. I coded pollard rho but when I discovered that pari uses pollard rho for big sizes of keys I decided to use directly the function of pari.

• Did you use some existing tools? Which ones?

Yes, I did. I used pari/gp.

• Did you have access to a cluster or you just used personal desktops/laptops?

I only used my personal computers but me and my friend have observed that there are important differences. For example, with my computer, I was faster than an hour in a total time of 4 hours, but he was faster of 50 seconds in a total time of a minute.

• Did you learn something new on ECC?

In general, I reviewed my knowledge about ECC. I studied new algorithms such as babystep-giantstep and pollard rho for dlp. These algorithms were unknown to me. I discovered Mov attack that was unuseful in contest. I tried also to study an article of hp that uses the lift of points in E(Qp) and my friend said to me that the Silverman hint was to use E(Z(p^2)) with another form of the equation of curve and so we tried that way.

---

Lorenzo Cameroni (ranked 3rd)

• Are you a student?

I'm a 27 years old Math student.

• Where are you from?

I study in Milano, but I'm from Quarona (VC).

• Did you code some algorithm to participate? In which language? Which algorithms did you code?

Yes, I tried to code (with PARI/GP) an attack on curve 19 which is anomalous (i.e. the number of rational point of E over F_p is p), but my code didn't work as expected (well, now it works, but now is too late); the details of the algorithm I've coded are in Silverman, "The Arithmetic of Elliptic Curves", pages 389-390. I didn't try to code Pollard's rho algorithm because i knew that PARI/GP elllog function already use this algorithm. I didn't try to code Baby-step giant-step algorithm because it needs too much memory.

• Did you use some existing tools? Which ones?

Yes, the PARI/GP elllog function and other elliptic curves related funcion in PARI/GP.

• Did you have access to a cluster or you just used personal desktops/laptops?

Only my laptop.

• Did you learn something new on ECC?

Yes of course: I've learned about supersingular curves (but there wasn't in the contest), anomalous curves and I've learned the Baby-step giant-step algorithm (even if I didn't tried to implement it).

---

Crypto Terroni Team (ranked 1st)

Instead of just answering directly to questions proposed, we decided to tell you our story. This way we hope to transmit together with the required information our feelings during the whole competition, from the moment we heard the notice of it to the end.

On monday morning Abate and Cotardo received a phone call from Vitto : "Guys from second year (we are studying Cryptography and Coding Theory in Trento) told me something about a cryptography contest. They suggested to take part for fun. But i have no idea what elliptic curves are". So we met and started looking for some notes on elliptic curves.

Our first attempt to break the example keys was by developing a magma script for a brute-force attack. Although we knew that it was not efficient, we started to deal with the group structures of elliptic curves over a finite field. Obviously we had no success with this approach and we started to study the baby-step giant-step algorithm. We found a python implementation of that and on our laptop it worked for the example keys. So we started applying that algorithm to the keys of the contest. Although it is a good algorithm, G-s B-s needs lots of RAM and the computation started to be unfeasible. So we studied the Pollard's Rho algorithm that requires a constant amount of memory and we found a python implementation of this. We broke with these algorithm 4 keys but their implementation was not so efficient and worked well only for "tiny" curves.

We understand that the key was the computation power (at this point we had only 3 days left) and we started to implement a Magma script where a discrete logarithm is computed (Magma uses a very efficient version of the Pollard's rho algorithm). We ran it on a Microsoft Azure Virtual Machine with 20 CPU @ 2,5Ghz with 60GB of RAM and we broke 15 additional keys in 2 days. The 19th key was the last one that remained unbroken: we needed an idea.

On thursday morning, while looking for probabilistic algorithm, speed up of Pollard-rho algorithm and so on, Vitto noticed that the order of the curve was the characteristic of the field, but we did not know how to use this information. On that evening, Vitto broke the last key: he just found that the curve belongs to the family of "Anomalous Elliptic Curves" for which the lifting of the curve over the p-adic field reduces the original ECDLP problem to the DLP problem over the additive group of order p (that has polynomial cost); with a Sage script ran on a Sage cloud server the last keys was instantly computed!

All members of the team agree that this contest was very formative: we learned not only algebra and algorithms that could be useless without a good theoretical background, but we also understand the importance of team working, where different ideas and approaches were the key to win this competition.

CryptoTerroni Team - Giuseppe Vitto, Carmine Abate, Giuseppe Cotardo"

PS: We are all from the south of Italy: Bari, Lecce, Salerno. For this reason we are proudly called CryptoTerroni: Terroni is how people from the north of Italy call people from the south.