RSA Mistakes was a 200 points cryptography master challenge in picoCTF. The final objective was to recover the encrypted message.
In the downloaded zip file we were provided with
- a traffic capture file in tcpdump format
- a python script
By looking at the pcap file we could notice that there are a bunch of request/responses, which by the problem statement were most likely encrypted using RSA.
Two of these streams, the first and the fourth, were extremely interesting, because two over the three parameters in the request were identical, while the third was not, and on the other side, the reply, which is supposed to be the encrypted message was completely different.
So, at this point, let’s give a look at the server python script and try to figure things out.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
The interesting part is the following:
1 2 3 4 5 6 7
By looking at these instructions we can notice that
- the application accepts 3 parameters as imput, separated by a space
- the program splits them to generate N, e and user_id, where N is the modulus and e is the exponent
- and then it encrypts the message.
But if we look at the encryption function more closely, we can notice that the user_id plays a key role here, as it’s used to modify the supplied message before the RSA encryption is performed.
The encryption itself is done with a typical RSA equation where we have
but m in this specific case is
where t is the user supplied text
So, putting things togeder we have:
- two different encrypted messages
- a small public exponent: 3
- the same public key being used for both messages, because the public key (e, n) is the same in both encryption processes
Plus, we also have a user_id parameter which differs, and allows us to determine a linear relation between the two messages so that
This is a convenient situation, because there is an interesting theorem: the theorem of Franklin-Raiter that states:
Set and let be an RSA public key. Let satisfy for some linear polynomial with . Then, given , the attacker can recover in time quadratic in .
The original paper which can be found here: https://www.cs.unc.edu/~reiter/papers/1996/Eurocrypt.pdf
also provides us with all the mathematical functions we need to calculate the value of our plaintext message from the encrypted messages: so all we were left to do was to calculate in function of as shown above, and implement the formula in a python script to compute the values for us; once the plaintext for the message is recovered, it’s then just a matter of extracting .
First let’s start by working on the messages and have them set in a proper way: since we need and we procede as follows.
- user_id1 as the first message userid
- user_id2 as the second message userid
- t as the plaintext we need to recover
- x as the modular multiplicative inverse of 37
Now that we have and what remains to do is punch them in our python script with and to retrieve
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
Running the above script returns the following output
that converted to ASCII gives us the flag:
Wow! Your flag is: did_you_know_you_can_sometimes_gcd_outside_a_euclidean_domain