CONTEST ENDED

The Contest

---

We published public keys for various types of digital signatures: RSA, DSA, ECDSA. A participant had to forge signatures on a given file that correspond to these public keys.

Contest Material

---

Click the button below to download the set of public keys and signatures. Private keys are now available.

Click here to Download Contest Material Click here to Download the private keys

We provide a specimen file (with one example per digital signature scheme), alongside a corresponding solution (note that the solution is not necessarily unique), in the format that should be used to submit the results.

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

The format for the contest material is a zip archive. In the archive there is a file named content.txt that describes the content:

• its first line is the name of the target file, that is the file for which the signatures should be forged;
• the second line contains an integer that says how many public keys there are in the archive;
• then for every public key there is a line with two entries: the name of the key (a single capital letter), and a letter representing its type (that is the corresponding digital signature algorithm): "r" for RSA, "d" for DSA, "e" for ECDSA.

Then there is the target file and a folder for every public key (with the corresponding name). In each folder there is a file txt:

• its first line is the letter that identifies the key type ("r" for RSA, "d" for DSA, "e" for ECDSA);
• the second line contains a letter that identifies the hash algorithm used: "m" for MD5, "s" for SHA1;
• the third line contains an integer that says how many files (and corresponding signatures) there are inside the folder;
• then there is a blank line;
• the next two or four lines (depending on the key type) describe the public key (see the Mathematical Framework section below for details on the algorithms and the notation):
  • for RSA keys there is a line with the integer n and one with the integer e;
  • for DSA keys there are three lines containing the parameters p, q, g and a fourth one with the public key y
  • for ECDSA keys there's a line with the cardinality of the base field q, a line containing the coefficients A, B of an elliptic curve E of the form y² = x³ + A·x + B, defined over F_q. The next two lines represent the base point G and the public key point Q via their coordinates (X, Y).
• then the signatures (one per file) follow, with the following format:
  • a blank line;
  • the name of the signed file;
  • the signature: for RSA is a single line containing σ, for DSA and ECDSA two lines containing r and s.

Participants are required to forge a signature of the target file for each public key given.

Warning for Windows users: If you open the files (i.e. in bloc notes) you might see everything 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.

Concerning the implementation of the two hash algorithms used in the contest, we refer to the following standard command line tools:

• Linux: md5sum pathtofile, sha1sum pathtofile;
• OSX: openssl md5 pathtofile , openssl sha1 pathtofile;
• Windows: CertUtil -hashfile pathtofile MD5, CertUtil -hashfile pathtofile SHA1;

The results should be interpreted as hexadecimal integers.

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, 14th October at 14:00.

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

A submission may consist of one or more solutions (you should include every solution you found) for a subset of the proposed public keys. Multiple submissions were allowed but only the last submission have been considered. Format for submission is a text file. The solution file should be in the following format:

• A line with the number of solutions in the file followed by a blank line
• Then for each solution:
• a line with the name of the public key
• a line for each element of the forged signature: for RSA a single line containing s, for DSA and ECDSA two lines containing r and s.
• a blank line to separate from the next solution

Every element of the signatures should be a number written in decimal base.

Coding

---

Do I have to code my own program to find the solutions? 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 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 find the solutions? 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 a digital signature scheme?

Digital signature schemes are designed to provide the digital counterpart to handwritten signatures. The digital signature is one or more integers dependent on the message and some secret known only to the signer, i.e. the signer's private key, but everyone is still able to check the validity of the signature using public data: the signer's public key.

There are plenty of digital signature schemes out there, but in this contest we focus on the most famous ones: RSA-based signing, DSA and ECDSA.

Although quite different, all three algorithms have the same general structure. The signer generates a pair of keys (PK, SK) where PK is the public key, that is distributed, and SK is the secret key, kept private. The message m to be signed is mapped via an hash function H to an integer of appropriate length: H(m). At this point the signer uses this hash H(m) and their secret key SK to compute a signature σ that attaches to the message for its authentication. Finally anyone in possess of the public key PK can verify the validity of the signature using a function V(σ, m, PK) that outputs "True" if the signature checks out, thus confirming the authencity of the message and its sender, or "False" if the signature is invalid.

RSA-based signing

RSA signatures work almost exactly the same as RSA encryption, the main difference being the order in which private and public keys are used. In fact where in RSA encryption the message is encrypted using the public key and then decrypted with the secret key, whereas in signing the message is first signed with the private key and then the signature is checked with the public key.

Let p, q be two distinct prime numbers and n = p q. Given φ(n) = (p-1)(q-1) (φ is Euler's totient function), the signer chooses a random integer 1< e < φ(n) such that gcd(e, φ(n)) = 1, i.e. e and φ(n) are coprime. The pair (n, e) will be published as the public key of the signer. Then the private key exponent d is computed as d = e^-1 (mod φ(n)).

Once the keys have been generated and the public key has been distributed to the intended recipients, the actual signing may begin. Let m be the message to be signed. Its signature σ is computed as: σ = H(m)^d mod n where d is the secret key exponent. Finally any recipient may check this signature by computing y = σ^e (mod n) (using the values of the public key), and checking wether y = H(m). This holds for a valid signature since for Fermat's little theorem x ^{e d} mod n = x if (e d) mod φ(n) = 1.

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

DSA

DSA is the acronym of Digital Signature Algorithm, an algorithm developed by NIST in 1991. Like RSA it works with integers and modular arithmetic.

The first step is to choose the parameters to be used. Let p, q be two random primes such that p - 1 is a multiple of q. Then let g be an integer whose multiplicative order modulo p is q.

Once the parameters (p, q, g) are fixed, the signer sets their own keys choosing a random secret key x ∈ ℤ, with 0 < x < q, and computing the correspondig public key y = g^x mod p.

To sign a message m it is necessary to generate a random per-message value 0 < k < q, then the two values of the signature (r, s) are computed this way: r = (g^k mod p) mod q, s = k^-1 (H(m) + x r) mod q. In the unlikely case that r = 0 or s = 0 a new k must be chosen and the process repeated.

To verify a signature (r, s) on the message m first check that 0 < r < q, and 0 < s < q, reject it otherwise. Then compute w = s^-1 mod q, u₁ = (H(m) w) mod q, u₂ = (r w) mod q, and v = ((g^u₁ y^u₂) mod p ) mod q. The signature is valid if and only if v = r.

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

ECDSA

The Elliptic Curve Digital Signature Algorithm (ECDSA) offers a variant, applied to elliptic curves, of DSA.

Given an elliptic curve E defined over a finite field F_q and a base point G ∈ E(F_q) of prime order n, the signer chooses their secret key that is a random integer 1 ≤ d ≤ n - 1 and computes the corresponding public key, that is the point Q= d G.

As in DSA to sign a message m a random, per-message integer 1 ≤ k ≤ n - 1 is selected, then the curve point (x, y) = k G is computed. Subsequently the signature is computed as the pair (r, s) where r = x mod n (thechnically x ∈ F_q, but it can be safely seen as an integer), and s = k^-1 (H(m) + r d) mod n. If r = 0 or s = 0 another value for k is chosen and the procedure repeated.

To verify a signature (r, s) on the message m first check that both r and s lie in the interval [1, n - 1], reject it otherwise. Then calculate w = s^-1 mod n, u₁ = (H(m) w) mod n, u₂ = (r w) mod n, and the curve point (x, y) = u₁ G + u₂ Q. The signature is valid if and only if r = x mod n.

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

Hash Functions

An hash function is a function that maps data of arbitrary size to a bit string of a fixed size. In cryptography, cryptographic hash functions are desired: an hash function is said cryptographic if it is designed to be a one-way function (i.e. it is easy to compute images but infeasible to compute pre-images).

Hence, an ideal cryptographic hash function has these main properties:

• it is easy to compute the hash value for any input;
• it is extremely difficult to recover a data from its hash value except by trying all possible values;
• a small change to a data changes radically the hash value;
• it is impossible to find two different data with the same hash value.

MD5 is a hash function designed by Ronald Rivest in 1991 that outputs bit-strings of fixed length 128 bits (16 bytes).

SHA1 is a hash function designed by the National Security Agency that outputs bit-strings of fixed length 160 bits (20 bytes).

We refer to Wikipedia for a more detailed view of MD5 and SHA1.

---

A contest solution for a single public key PK consists of a signature σ such that V(σ, m, PK) = True, where m is the target message. That is, without having the secret key, try to forge a signature for m.

---

Do you know how to forge a digital signature? If not, go learn something about it!

Final Ranking

---

Rk	Participant	Time of Last Submission	Valid Signatures
1	Cryptoresearch *	13/10/2016 00:22	15
2	Cryptostage *	14/10/2016 12:36	13
3	TGL *	14/10/2016 08:25	10
4	Alessandro De Piccoli	14/10/2016 13:49	7.5 **
5	Francesco Romeo	13/10/2016 21:10	7

Notes:

* marks group entries.

**: valid signatures for 8 public keys, but one signature was mislabeled.

Stats

---

• Participants: 5 (11 people)
• Submissions: 16
• Forged Signatures: 15
• Unforged Signatures: 2

Prizes

---

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

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 2016 and 2017. Moreover we will treat them to lunch the day of the award ceremony.

It is possible to participate in groups, however prizes will be awarded to a maximum of three components. Individual participants can not compete in a group also.

Prizes will be awarded November 16th 2016 during the Cryptography Workshop

BunnyTN7 2016

organized at University of Trento jointly with other Italian universities.

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 they has forged more signatures.

2. A participant ranks higher than another participant with the same number of forged signatures if their last valid submission was done earlier in time.

How have we designed the contest?

---

First of all, using Magma we selected keys that could be broken in 10 minutes (one for RSA-based signing, one for DSA and one for ECDSA), in 60 minutes (one for RSA-based signing, one for DSA and one for ECDSA) and in about 1 day (one for DSA and one for ECDSA), running general purpose algorithms to factorize or to solve the discrete logarithm problem.

However, we wanted a contest where just using general purpose algorithms to factorize or to solve the discrete logarithm problem 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 special purpose algorithms exist, which perform better than the best known general purpose algorithm.

We selected different classes of weak keys we would want to generate, both for RSA-based signing and ECDSA. In particular we chose:

• RSA-based signing:
  • Wiener weak keys: keys with small private exponent (d <1/3 N^1/4) which can be broken with the Wiener's attack, based on continued fractions;
  • a couple of keys with a common prime factor, which can be broken very easily by computing Greatest Common Divisor by means of Euclid's algorithm, which just requires repeated subtractions. In the famous paper “Ron was wrong, Whit is right (2012)”, Lenstra et al. studied some millions of public available RSA keys and discovered that many of them were vulnerable to a common factor attack.
• ECDSA:
  • anomalous curve keys, to raise awareness on the vulnerability of anomalous curves, which are curves defined over a prime field of p elements and having p rational points (we used an anomalous curve taken from safecurves.cr.yp.to);

We would like also to highlight that rough implementations of secure cryptographic schemes could lead to fatal weaknesses, as famous examples prove. In fact, signing via DSA or ECDSA it is fundamental to choose a random k since if the ks are generated using a linear congruential generator, then it is possible to successfully attack the signing protocol. In order to reach such a goal we proposed:

• DSA:
  • For a given key, two digital signatures obtained using the same k. Given two signatures (r,s₁) and (r,s₂) for two different files m₁ and m₂, achieved using the same k, from the expression of s_1-s2 one can recover k solving a linear congruence. Knowing k, the private key x can be retrieved from s₁’ expression.
  • For a given key, two digital signatures obtained using consecutive ks Given two signatures (r₁,s₁) and (r₂,s₂) for two different files m₁ and m₂, achieved using k₁ and k₂=k₁+1 respectively it is possible to perform an attack that recovers easily the private key x. Indeed, from s₁*k≡hash(m₁)+x*r₁ (mod q) and s₂*k+s₂≡hash(m₂)+x*r₂ (mod q), one can retrieve x solving a linear congruence system.
• ECDSA:
  • For a given curve, two digital signatures obtained using the same k. Given two signatures (r,s₁) and (r,s₂) for two different files m₁ and m₂, achieved using the same k, the procedure to recover k is analogous to the one reported above for DSA. This implementation failure was exploited to stole private signing keys used for PlayStation 3.

Finally we included two easter eggs.

For a RSA-based signing key, we provided a digital signature for a file with the same MD5 hash of the target file, i.e. we exploited a collision of the hash function MD5. A collision is when two different files m₁ and m₂ are such that hash(m₁) = hash(m₂). It is well known that the two very famous hash functions, MD5 and SHA-1, do not satisfy the collision resistance property. For this reason they are no more used for digital signatures, even if they are still used for other purposes (like password hashing). It is possible to obtain a collision for MD5 with an algorithm which takes just a few seconds on a regular computer.

One of the elliptic curves proposed is the P-256 curve, recommended by NIST and considered secure. So it is impossible to solve the discrete logarithm problem over it using classical algorithms. However, we choose a very small d, to show that sometimes a brute force attack can lead to The Answer.

Feedback from participants

---

After the contest we will ask 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 Digital Signatures?

We will report here the answers from the participants.

---

Alfarano Gianira, Cotardo Giuseppe and Zaninelli Marco (Cyptoresearch, ranked 1st)

• Are you students?

Yes, we are three students from University of Trento, currently attending the Master's Degree in Coding Theory and Cryptography.

• Where are you from?

Gianira and Giuseppe come from Apulia, Bari and Lecce respectively. Marco comes from Verona.

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

Yes. We implemented in MAGMA the Wiener's attack, useful to break one RSA signature. Moreover we used a SAGE implementation for an attack on the so called “Anomalous Elliptic Curves”.

• Did you use some existing tools? Which ones?

We used some MAGMA functions as "Log", "GreatestCommonDivisor" and "Factorization" and we checked on the website "factordb.com" some factorizations of the RSA integers.

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

We had access to a cluster (Windows Azure) and a Mac-Pro and we use them in order to break the weakest keys. Then we worked on our laptops and did some computations with pen and papers.

• Did you learn something new on ECC?

Yes,we learned a lot of details on Digital Signature Schemes, in particular about weakness and attacks on such protocols.

---

Elena Canali, Cristian Mirto and Fulvio Rizzardini (Cryptostage, ranked 2nd)

• Are you students?

Yes, we are students from the University of Trento.

• Where are you from?

Cristian is from Lecce, Elena from Trento and Fulvio from Manerba del Garda.

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

Yes, but they were almost useless. We code some functions in Magma.

• Did you use some existing tools? Which ones?

Yes, we used Magma.

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

Our personal computers and one desktop computer.

• Did you learn something new on ECC?

Yes, it was a formative and enjoyable experience.

---

Luca Girardi, Tommaso Parise and Gaetano Russo (TGL, ranked 3rd)

• Are you students?

Yes, we are in the first year of the curriculum in Coding Theory and Cryptography by University of Trento.

• Where are you from?

Luca is from Trento, Tommaso is from Bassano Del Grappa (Vicenza) and Gaetano is from Salerno.

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

We wrote some algorithms to ease calculations, we tried implementing the rho-pollard both in the factorization and discrete logarithm form, but we ended using the functions already existing in Magma.

• Did you use some existing tools? Which ones?

We used the Magma software.

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

We just used our personal laptops.

• Did you learn something new on ECC?

We were completely new to the subject (except for RSA encryption), so we learned a lot just to know what we were facing. We decided to partecipate in order to have fun and learn something new and we can say that our objectives were accomplished.

---

Alessandro De Piccoli (ranked 4th)

• Are you a student?

Yes, I am.

• Where are you from?

I'm from Varedo (MB).

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

I coded two famous attacks to rsa and ecc for particular cases. I also coded various attacks to dsa and ecdsa from an article of Draziotis and Poulakis without successful. All of this algorithms were coded using pari library.

• Did you use some existing tools? Which ones?

Yes, I did. I used the gp calculator.

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

I used my desktop and my laptop. I forged all my signatures in 3 hours and a lot of time trying to forge the others.

• Did you learn something new on ECC?

I knew that there were something called Digital Signature, but I didn't know anything else. I discovered a new side of cryptography.

---

Francesco Romeo (ranked 5th)

• Are you a student?

Yes, I study at University of Trento.

• Where are you from?

I’m from Messina.

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

Yes I coded by myself algorithms in Magma. There were One algorithm to break RSA, returning a valid RSA Signature, 2 algorithms to break DSA and ECDSA, and two algorithms to verify that the outputs were right.

• Did you use some existing tools? Which ones?

I used an online software to recover the Hash from the target Document.

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

I only used my laptop.

• Did you learn something new on ECC?

I enjoyed this experience and I’ve seen how to apply what, until now, I knew only theoretically.