# 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\$`

--

--

--

## More from 0awawa0

awawa.fun

Love podcasts or audiobooks? Learn on the go with our new app.

## What is SSL? ## July: Government bans 47 more Chinese Apps in India after TikTok last month ## The Internet Stole Your Privacy. Now We Can Take it Back. ## Turkey passport template in PSD format, fully editable, + editable PSD photo look (2018 — present) ## 8 Short Links on Provenance Analytics for Cyber Security  awawa.fun

## TCMSecurity | Dev | Write-up ## Hackthebox Horizontall machine writeup ## HTB Previse writeup ## HTB: Silo Writeup w/o Metasploit 