The CryptoLabTN (Laboratory of Industrial Mathematics and Cryptography at University of Trento), in collaboration with Clusit (The Italian Association for Computer Security), organizes the "Digital Signature Awareness Contest". The event is organized within the framework of the ECSM (European Cyber Security Month) 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 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.
Click the button below to download the set of public keys and signatures. Private keys are now available.
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.
The format for the contest material is a zip archive. In the archive there is a file named content.txt that describes the content:
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:
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:
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, 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:
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.
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 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 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 = gx 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 = (gk 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, u1 = (H(m) w) mod q, u2 = (r w) mod q, and v = ((gu1 yu2) 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.
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 Fq and a base point G ∈ E(Fq) 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 ∈ Fq, 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, u1 = (H(m) w) mod n, u2 = (r w) mod n, and the curve point (x, y) = u1 G + u2 Q. The signature is valid if and only if r = x mod n.
We refer to Wikipedia for a more detailed view of ECDSA.
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:
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).
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!
|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|
* marks group entries.
**: valid signatures for 8 public keys, but one signature was mislabeled.
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
organized at University of Trento jointly with other Italian universities.
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.
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:
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:
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 m1 and m2 are such that hash(m1) = hash(m2). 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.
After the contest we will ask the participants the following questions:
We will report here the answers from the participants.
Yes, we are three students from University of Trento, currently attending the Master's Degree in Coding Theory and Cryptography.
Gianira and Giuseppe come from Apulia, Bari and Lecce respectively. Marco comes from Verona.
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”.
We used some MAGMA functions as "Log", "GreatestCommonDivisor" and "Factorization" and we checked on the website "factordb.com" some factorizations of the RSA integers.
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.
Yes,we learned a lot of details on Digital Signature Schemes, in particular about weakness and attacks on such protocols.
Yes, we are students from the University of Trento.
Cristian is from Lecce, Elena from Trento and Fulvio from Manerba del Garda.
Yes, but they were almost useless. We code some functions in Magma.
Yes, we used Magma.
Our personal computers and one desktop computer.
Yes, it was a formative and enjoyable experience.
Yes, we are in the first year of the curriculum in Coding Theory and Cryptography by University of Trento.
Luca is from Trento, Tommaso is from Bassano Del Grappa (Vicenza) and Gaetano is from Salerno.
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.
We used the Magma software.
We just used our personal laptops.
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.
Yes, I am.
I'm from Varedo (MB).
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.
Yes, I did. I used the gp calculator.
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.
I knew that there were something called Digital Signature, but I didn't know anything else. I discovered a new side of cryptography.
Yes, I study at University of Trento.
I’m from Messina.
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.
I used an online software to recover the Hash from the target Document.
I only used my laptop.
I enjoyed this experience and I’ve seen how to apply what, until now, I knew only theoretically.