The CryptoLabTN (Laboratory of Cryptography at University of Trento), in collaboration with Clusit (The Italian Association for Computer Security) organizes an "RSA 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).
The set of RSA public key is public (although contest is now closed).
The format for Contest Material is a text file. Each line represents a single public key and it contains three numbers written in decimal base and separated by a space: a counter identifying the public key (1,2,3,...), a modulus and a public exponent.
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 on a single line.
Read the Instructions below for further info.
A participant will be 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, 17th October at 17:00.
You submit a Contest Solution sending a mail to contest.cryptolabtn at gmail.com.
A submission may consists of one or more solution for a subset of the proposed RSA 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 four numbers written in decimal base and separated by a space: a counter identifying the public key (1,2,3,...), the two prime factors and the private exponent.
Do I have to code my own program to factorize an integer or find the private exponent? 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 factorize an integer or find the private exponent? Absolutely not!
There are tons of good algorithms which might break short or weak keys. Look around (did I already mention this?) 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.
Do you know what is RSA algorithm? If not, go learn something about it!
An RSA public key \((N,e)\) is given by two integers \(N\) (the modulus) and \(e\) (the public exponent). The modulus is the product of two prime integers \(p,q\): \[N=pq\] A message is represented as an integer \(m\) (plaintext) such that \(0 < m < N\). Encryption produces an integer \(c\) (ciphertext) through exponentiation by the public exponent modulo \(N\): \[c \equiv m^e \pmod N\]
The contest material is a set of RSA public keys. We will not give you encrypted messages to be decrypted.
The associated RSA private key \((N,d)\) is given by the modulus and an integer \(d\) (private exponent). The private exponent is linked to public exponent by the following relation: \[de \equiv 1 \pmod {(p-1)(q-1)}\] Decryption given a ciphertext \(c\) recovers the message \(m\) through exponentiation by the private exponent modulo \(N\): \[m \equiv c^d \pmod N\] The correctness of the algorithm can be proved by Euler's Theorem. Breaking an RSA public key means finding either \(d\) or factorize \(N\) into \(p\) and \(q\). Finding the factorization of the modulus or the private exponent is equivalent up to an efficient computation (see, for example here).
A contest solution for a single public key consists of both the prime factors of the modulus and the private exponent.
Rk | Partecipant | Time of Last Submission | Valid Keys |
---|---|---|---|
1 | Lorenzo Felice Cameroni | 00:55, 17/10/2014 | 45 |
2 | CryptoBriscola* | 15:10, 17/10/2014 | 45 |
3 | CryptoBO** | 11:17, 17/10/2014 | 44 |
4 | Mauro Piva | 11:50, 17/10/2014 | 44 |
5 | Francesco Mantovani | 12:20, 17/10/2014 | 44 |
6 | Nanni Bassetti | 10:33, 17/10/2014 | 43 |
7 | Luca Chiodini | 16:52, 17/10/2014 | 43 |
8 | Alessandro Sebastian Podda | 12:35, 14/10/2014 | 36 |
9 | Cristiano Sgaravato | 10:57, 17/10/2014 | 36 |
10 | Luciano Giuseppe | 15:05, 17/10/2014 | 36 |
11 | Alessio Serraino | 16:57, 17/10/2014 | 36 |
12 | Matteo Rizzo | 13:20, 17/10/2014 | 34 |
13 | Flavio Santoro | 16:59, 15/10/2014 | 33 |
14 | John Johnson | 20:29, 15/10/2014 | 33 |
15 | Cristiano Regni | 18:16, 15/10/2014 | 30 |
16 | Amedeo Sgueglia | 23:55, 15/10/2014 | 30 |
17 | Luca Di Stefano | 20:33, 15/10/2014 | 28 |
* group composed by Carlo Brunetta, Andrea Vinci, Jacopo di Bonito and Alessandro Melloni.
** group composed by Andrea Dari and Claudio Costa.
Ranking published only for participants with more than 20 valid keys.
Final stats (updated on Friday, 17th October, 17:00).
Identifier of unbroken keys: 37, 43.
The real prize you get from participating in this contest is having fun learning and doing things by yourself. To give an additional incentive we have provided symbolic prizes for those who rank in the first three positions .
Prizes will be awarded on 22nd of December during an event organized at University of Trento.
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 knew we wanted a contest where just using general purpose factorization algoritms would not be enough to excel in the competition. So we needed to generate weak keys. What are weak keys? These can be defined in an informal way as classes of keys where a special purpose algorithm exists, which perform better than best algorithm for modulus factorization.
First, we selected the class of weak keys we would want to generate. We chose:
Next, we selected some key lengths (60,80,100,150,200,300,512,1024) and for each keylength, we generated 5 weak keys according to the above methods* and a sixth strong key, a key generated randomly without forcing any kind of previously known weakness. This process generated 48 keys which were ordered by keylength and generation method (strong key, common prime keys couple, wiener key, fermat key, pollard key).
*all our coding was done in the Magma language. Unfortunately, a bug in our implementation of the generation of pollard weak keys resulted in keys that, only for the longest keylengths, had a very small prime factor. We became aware of this only when the contest was already started.
We asked the participants the following questions:
We report here (with little editing) some of the answers from the participants. Sometimes these were in italian, and we left them that way. Note the curious twist in the challenge given by the use of a factorization database...
no, I'm a digital forensics expert and I'm 44 years old, I'm graduate in Computer Science at University of Bari.
Bari - Italy
Yes, I coded a bash script and a python script they can factorize the module N and find the private exponent "d", but they are too slow.
Yes, I used a combination of tools rsatool.py and the website: http://www.factordb.com/.
I used my laptop and a website (http://www.factordb.com/)
Yes, it was very formative.
I'm a student, 5th year of high school.
I live in a small village near Bergamo.
C++ (with boost::multiprecision to handle big numbers) and python have been used. Among other little things, I wrote a checker (given a ready-to-be-submitted output, it ascertained that RSA keys were valid).
A lot! For instance:
I used my desktop (not a cluster, although quite powerful).
I learned the algorithm right for this competition.
I'm a student from University of L'Aquila, currently attending the Laurea Magistrale course in Ingegneria Informatica e Automatica.
I started by using a Python implementation of Wiener's attack I wrote some months ago. The code is available at https://github.com/lou1306/PythonRSA
Then I brute-forced the first 24 keys by applying the MATLAB function factor() on their moduli. The function was useless for longer moduli because it was based on a simple sieve algorithm. I was going to implement a quadratic sieve but time ran out...
I used my notebook for all computation.
I already had a pretty good knowledge of RSA, but I definitely learned something on integer factorization and the quadratic sieve!
I'm a university of Salerno master's student
I'm from Avellino province, Italy.
No, I didn't
I used yafu (http://sourceforge.net/projects/yafu/) for number under 90 digits, GGNFS and MSIEVE for others numbers as read here: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html
I used my desktop pc (pentium D, dual core)
Group composed by Carlo Brunetta, Andrea Vinci, Jacopo di Bonito and Alessandro Melloni.
Tutti della magistrale di Critto (NdR: all from MSc of Cryptography at University of Trento)
Misto Italia
[...] siamo andati per la via più rapida. Magma, C++, Python. Alcuni eran già scritti, altri son stati adattati per il nostro scopo.
Algoritmi pre-fatti per fattorizzare con algoritmi tipo GNFS
Un portatile windows 8 per le prime chiavi piccole e quelle deboli ad attacchi particolari. (circa 29 chiavi) Un macbook pro per chiavi che sopra creavano problemi di memoria su windows. (circa 10 chiavi) Carta e penna per un attacco pigro facendo i gcd tra i vari n e così son uscite un paio di chiavi. (6 chiavi) Così siamo rimaste alle 3 che non abbiam potuto fare. In nottata abbiam fatto partire un piccolo server con qualche gpu e il GNFS Python che però non ha fruttato risultati. [...]
Abbiamo testato un po' quel che abbiam visto a lezione!
Non sono uno studente, sono un web developer ma negli ultimi mesi ho lavorato in Corea come aiuto cuoco.
Seoul, Auckland (NdR: moved during the contest)
Non ho scritto nemmeno una riga di codice, ho solo utilizzato python e perl per tradurre alcuni risultati che erano in esadecimale in decimale.
mi sono imbattuto in questo post che spiega per filo e per segno come aprire una chiave RSA avendo questi dati. Mi sono quindi collegato a http://www.factordb.com/ e ho incominciato a trovare i numeri primi avendo solo i modulus. Trovati i numeri primi e stato poi facile grazie a rsatool https://github.com/ius/rsatool trovare "d". Non tutti i numeri però erano presenti nel DB. Il giorno seguente, avendo commesso alcuni errori, ho rivisto il lavoro e sono tornato a fare delle query sul database; mi sono accorto che alcuni dei numeri che il giorno prima non erano presenti nel db, il giorno seguente erano presenti. Forse, avendo ricevuto più richieste per quel dato numero, dall'altra parte si sono messi a cercare i numeri primi di quei moduli.
Ho imparato qualcosa di nuovo? Un sacco di cose, soprattutto come funziona la vulnerabilità Heartbleed http://countuponsecurity.com/tag/extract-rsa-key/
I'm a 26 years old working student (well, honestly more working than student, I'm a full time java programmer and a Math student).
I work and study in Milano.
Working full time leave me no much time for coding some smart algorithm, the only one I code is not so smart: a brute force search for a factor very close to the square root of n, but it was too slow for the key provided except first ones. I code this with PARI/GP. I didn't try to code Pollard's rho (which I think is the simpler serious factoring algorithm) because i knew that PARI/GP factor function already use this algorithm (hopefully better than how i could code in few hours).
Yes, most of my work was finding the right tool for the right key, guessing what kind of "error" was done when the keys were created. Here the most useful I found:
Only my laptop (and sometimes my work laptop)
Of course: before this competition I never heard about attack on RSA such as Wiener's one, nor I could imagine that (as I read here) in real world different unrelated 1024 or 2048 bit RSA keys colud share a prime factor (altough this mostly happen when such keys are generated on embedded device with poor pseudo-random number generators)
Group composed by Andrea Dari and Claudio Costa.
Siamo 2 studenti universitari
Siamo di Bologna
Abbiamo scritto vari algoritmi per fattorizzare il modulo, tra cui Fermat e Pollard rho oltre a quello a forza bruta. Sono stati scritti in Java ed utilizzando la programmazione multi-threaded.
Abbiamo utilizzato per alcune chiavi, quelle più semplici, WolframAlpha
Abbiamo utilizzato i nostri laptop personali.
Sicuramente abbiamo imparato che esistono algoritmi più o meno validi per cercare di fattorizzare un modulo anche abbastanza grande.