The CryptoLabTN (Laboratory of Cryptography at University of Trento), in collaboration with Clusit (The Italian Association for Computer Security) organizes an "ECC Awareness Contest". The event is organized within the framework of the European Cyber Security Month (ECSM) and targets students with coding activities.
Our contest aims to raise awareness of the fact that cryptographic algorithms get old and they should be countinously tested, maintained, improved (which is what cryptographers - among other things - do).
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).
Click the button below to download the set of ECC public keys. The corresponding solutions are now available too.
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.
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.
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.
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.
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.
What is the ECDLP?
Given an elliptic curve E defined over a finite field Fq, a point P ∈ E(Fq) 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.
|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|
(*): Team formed by Giuseppe Vitto, Carmine Abate, Giuseppe Cotardo.
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 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.
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:
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!
We asked the participants the following questions:
We report here the answers from the participants.
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.
Pen and paper and a Delorean DMC-12 with a flux capacitor to send the answer in 1985.
ust 0 second of the laptop and some days on paper to understand why it works.
Yes, quite a lot.
Yes, I am studying computer science at the University of Milano - Bicocca.
I live near Bergamo.
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).
I used the cloud platform of SageMath and ECDLP solver, which in turn uses a version of Pollard Rho algorithm to break keys.
I used only my personal desktop.
I learned all the details of ECC just for this contest.
Yes, I am.
I'm from Varedo (MB), Lombardia, Italy.
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.
Yes, I did. I used pari/gp.
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.
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.
I'm a 27 years old Math student.
I study in Milano, but I'm from Quarona (VC).
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.
Yes, the PARI/GP elllog function and other elliptic curves related funcion in PARI/GP.
Only my laptop.
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).
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.