Tags: python rsa-crypto cryptography-rsa crypto rsa

Rating:

# Santa's List 2.0
Reading the source provided in Santa's List 2.0, the only difference is that there is a limit of 5 requests to the server. Fortunately, our previous solution only requires 3 requests: 2 for encrypting '!' and '#', and 1 for decrypting the modified ciphertext. This is the same solution.

Logging into the server, we see the following prompt:

Ho, ho, ho and welcome back!

Sarah - Nice
Bob - Nice
Eve - Naughty
Alice - Nice
Johnny - Naughty

[1] Encrypt
[2] Decrypt
[3] Exit

Exploring the options, we have the ability to:

1. Encrypt an arbitrary string. This gives us a large integer.
2. Decrypt an integer. This also gives us a large integer.
3. Exit. Not very interesting.

Clearly, "Galf" has an interesting Naughty/Nice value. It appears to be a hex encoded value. Unfortunately it does not decode to a string, and it unpacks to a very large integer. Decrypting this integer gives the result Ho, ho ho, no.... Note that opening the server again will give Galf a different value.

Along with the nc server, we were given santas_list.zip. This archive contains one file, list.py. Reading this file, it is clearly the same one running on the server. list.py basically:

* Generates a random RSA key
* Opens the file flag.txt, encrypts it, converts it to hex, and displays it in the opening message
* Listens for user input
* When encrypting, it simply converts the text to hex, converts that to a long, and encrypts it. However, it also adds the numberical plaintext to the list used.
* When decrypting, it first checks that the value isn't the encrypted flag (which is why we were unable to decrypt it previously). After decrypting, it also checks that message % previous != 0 for every previous in the list used. This will be important later.

So we have access to an encrypted flag (C = M<sup>e</sup> (mod N)), an RSA encrypt function (X<sup>e</sup> (mod N)), and an RSA decrypt function that doesn't allow us to decrypt C directly. There is an attack called [Blinding](https://en.wikipedia.org/wiki/Blinding_(cryptography)) iwhich allows us to modify the ciphertext, decrypt that modified value, then un-modify it. Basically, we need an arbitrary message S which we will encrypt (S<sup>e</sup> (mod N)), then multiply it by the ciphertext (CS<sup>e</sup> = M<sup>e</sup>S<sup>e</sup> = MS<sup>e</sup> (mod N)), decrypt that ((MS<sup>e</sup>)<sup>d</sup> ≅ MS (mod N)), then divide by S to get the original M. Note that we can't necessarily use normal integer division because of modular arithmetic. Instead, we must calculate the modular inverse of S (mod N) and multiply by that.

However, the modulo check in the decrypt step blocks this plan. If we encrypt S using the Encrypt function, it will be recorded in used. When we try to multiply the ciphertext by the encrypted S and decrypt that, it will notice that the result is divisible by S and block our decryption attempt. We need a way to avoid this check. If we can find a way to encrypt S without using the Encrypt function, we will be able to use Decrypt.

The RSA encrypt function is simply M<sup>e</sup> (mod N). By running list.py and adding some debug statements, we can determine that e is 65537, a very common value. Unfortunately, it appears that N is randomized every time list.py is run, so we will have to find a way to determine it using only what we can get out of the prompt. Let's do some number theory:

RSA encryption:

x<sup>e</sup> ≅ C<sub>x</sub> (mod N)

x<sup>e</sup> = C<sub>x</sub> + kN (for some value of k)

x<sup>e</sup> - C<sub>x</sub> = kN

y<sup>e</sup> - C<sub>y</sub> = jN (same equation, but different value for x)

Note that the Greatest Common Denominator (GCD) of kN and jN is N. For reasonably small values of x and y, we can use [Euclid's Algorithm](https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid's_algorithm) to determine N in a reasonable amount of time.

Practically speaking, the smallest values of x and y I could easily find were 33 and 35, which correspond to characters '!' and '#'. We can Encrypt these strings using the prompt, then calculate N using the following code:

cx = Encrypt('!') # 33
cy = Encrypt('#') # 35
kn = (33 ** 65537) - cx
jn = (35 ** 65537) - cy
N = gcd(kn, jn)

Now that we know N, we can encrypt anything we want without using the server. We will now pick an arbitrary S (I used N/2), then use the above blinding attack to decrypt the encrypted ciphertext. See https://github.com/dchiquit/xmasctf-2018/blob/master/santaslist/santaslist_solve.py for my solution.

Original writeup (https://github.com/dchiquit/xmasctf-2018).