niteCTF 2021, Rabin to the Rescue Writeup

Description

So we have the server’s network address and the source code. Let’s examine the source code:

First, this code generates two primes p and q. The generation function is pretty interesting:

It sets p to 256-bit prime and q to p + 6 and then checks if p = 3 mod 4 and q = 3 mod 4 and returns them if they are. Otherwise, function generates p again but q this time is the next prime for p. And again it checks if p = 3 mod 4 and q = 3 mod 4.

After primes generation, the code computes n = p * q. So far this looks pretty much like an RSA problem.

Then, the code computes e with function mixer. Interesting thing is that mixer function accepts integer parameter, and the code feeds q — p into it. So we would think that e is somehow depends on values q and p. But if we look closer to the mixer code, we’ll see that the function will always return the value 1.

Note the while loop. It terminates only when num is lower or equal to 1. But num is reduced only with division by 2, so it cannot ever become lower than 1. So mixer returns 1 for any positive argument num. And num is always positive because q is always greater than p, so q — p > 0.

Finally the value returned from mixer is multiplied by 2. So e will always be 2. Now for some people it might still look like an RSA challenge, but it is already not the case. This is because we can’t have public exponent equal to 2 , because f = (p — 1) * (q — 1) is even number and 2 has no inversion modulo f, so we can’t calculate d. But let’s move on for now.

After parameters computation, the code enters the main loop, that’s where we interact with server. Server propose 3 options: encrypt some arbitrary value, print encrypted flag, and exit. Encryption function works similar to RSA.

You may notice that when we request the encrypted flag server runs encrypt function random amount of times. It calculates the same value over and over again, so this doesn’t make problem harder. This is just a protection against timing attacks.

Note that server never prints parameters of cryptosystem. And although we know e = 2 anyway, we don’t know n.

Let’s summarize all of this:

1. We have some cryptosystem that looks like an RSA, but it is not an RSA.
2. We don’t know any parameters of the cryptosystem.
3. We have an encryption oracle
4. We have an encrypted flag

Solution

So what do we do? We have encrypted flag:

To decrypt it, we would have to calculate square root modulo n. Well, first of all, we don’t know n. How do we find it? That’s where the encryption oracle becomes useful.

Remember the definition of modulo operation:

So, if we ask server to encrypt some x, such that x^2 is greater than n, then we have:

where k >= 1. Then

Now, the only value we need to calculate n is k. Well, we can find such value x so that its square is only slightly bigger than n, so k will be equal to 1. But there is actually better idea, which also works for bigger powers. We take two numbers x and y such that x^2 > n and y^2 > n, and encrypt them both

Which gives us the following

And finally we can calculate

For x and y I used 2^256 and 3^256, because p and q are both 256-bit long, so n is 512 bits long, therefore x^2 = 2^512 , which is 513-bit number, will be greater than n. Same logic is for 3^512.

Now that we have computed n we have the second problem: we need to calculate square root modulo n, and this is at least as hard as factorizing the n.

I suppose we will have to factorize n after all. We could use some existing services for that, like Alpertron, but recall the primes generation process. Primes generated in such a way that p and q are two adjacent primes. Therefore both p and q are really close to square root of n. And that’s what we are going to use. We will calculate square root of n and look for a number that divides n around the root. There is a great chance that we will find such a number in no time.

Finally, once we have factorized n the only thing left is to compute the flag. Remember that we cannot calculate f = (p — 1) * (q — 1) and compute d such that e * d = 1 (mod f) because GCD(e, f) = 2. So this is not an RSA cryptosystem. But what is it actually? This is a Rabin cryptosystem, so we use formulas from Wikipedia to decrypt the flag:

And one of r1, r2, r3, r4 will be the correct plaintext.

Below is the solution source code. Here I use my own package ptCrypt where I have some useful functions, but you can find analogues of those functions in popular libraries, such as PyCrypto.

Code run result:

awawa@awawa-pc:~/Documents/CTF/niteCTF$ python3 rabin_solution.py  
[+] Opening connection to rabin.challenge.cryptonite.team on port 1337: Done 
Obtaining x 
Obtaining y 
Calculating modulus 
Obtaining flag 
Factoring modulus 
Decrypting 
b'\x84\x14hMnf\xc7\xda\x12:\xac\xb7_\xdd\xe7\x06\xae\xc0\xf8\x99\x1a\xbbX\xf57\xc5\x9b\xde\xbc\x90&$\xfeq\x9d\x87\\U\xd4\xba\xcd2\xd0z\xe0\x06\td\x9e\xb4\xd1?\xe4\x06\x04\x84\x0e:\xec\x06\x19g}\x1c' 
b'nite{r3p34t3d_r461n_3ncrypt10n_l1tr4lly_k1ll5_3d6f4adc5e}' 
b'KQ\xbe0k\xdcCH\xa9u\xb6\x1eC\x1b\x9dk\r\xa8L\xea\xfa\x9f\x91\xa4\xf3\xbe\x88\xf3\xb44\x8aq\xe2t\xf2\x88\xef\\u\xae\xecI[\xd1\xd9\xb2\xc3&\x8e\x83\xc6;\xc7q`{\xdc\x8b\x8c\xcb\xdb=A\x8b' 
b'8\xc2\xaa\x1d\x02\x8a\x84\xff\xd29\\\x14\x8e\xf5\xb9\xce\xd5\x8c\xdf\x12\x7f\x8d\xfb\x86uur\x1ev\xbf\x0e,\x8cp\xdc.\xdbX\xcb=U[\xa9\x15r\xcc\xa5\xa9A\x9dw9{\xc8\x08>\x97\xe3\xc0\x9e\xa1_\xa1\x0e' 
awawa@awawa-pc:~/Documents/CTF/niteCTF$