Tags: coppersmith mt19937 rsa
Rating:
# The Challenge
The challenge consists of an RSA implementation. As with most RSA challenges we are given the public key: The exponent `e` and the modulus `n`.
We are allowed to encrypt any data we want and the server will return with its encryption (Option 1).
The server can also encrypt the flag and return its encryption (Option 2).
We are allowed to send messages that aren't too long. The padding generated has to be at least 9 bytes long.
The source can be found in the [./chal](./chal) folder.
## The Vuln: The padding
This is a pretty straightforward challenge. Take a look at the padding code:
```python
from random import getrandbits
# ... #
def pad(m, n): # pkcs#1 v1.5
ms = long_to_bytes(m)
ns = long_to_bytes(n)
if len(ms) >= len(ns) - 11:
return -1
padlength = len(ns) - len(ms) - 3
ps = long_to_bytes(getrandbits(padlength * 8)).rjust(padlength, b"\x00")
return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")
```
The key thing to note is that the padding is random bytes generated by python's `random.getrandbits`. Python's random module is a Pseudo-RNG (PRNG) called MT19937. This PRNG isn't cryptographically secure and shouldn't be used to generate padding.
Furthermore, given that the flag length is lesser than `55` bytes, the padding will be at least `198` bytes of the whole padded message `256` bytes. If we can somehow predict the padding, we would know _majority_ of the padded message, represented in RSA as `enc(padded_msg) = padded_msg^e mod n`.
From knowing majority of the message, we can represent `enc(pad(flag))` as `(a + b*flag)^e mod n`, where the magnitude of `flag` is a lot smaller than `n`. One can then recover `flag` via [Coppersmith](https://en.wikipedia.org/wiki/Coppersmith_method).
## The Approach
Our attack will look something like this:
1. Get the padding of multiple messages
2. From the known padding, clone the `random` object generating the padding
3. Predict the padding used when encrypting the flag.
4. Recover the flag with Coppersmith.
### Getting the padding
We can generate a message `pt` for the server to encrypt, which will give us back `ct = enc(pt)`.
Via the same logic as before, we can make `pt` long enough such that it is the majority of the `256` bytes padded message, such that `ct = (a + b*padding)^e mod n`, where the magnitude of `padding` is a lot smaller than `n`, and we can recover `padding` via Coppersmith.
To make cloning the PRNG easy, `padding` length should also be aligned to 4 bytes, since MT19937 outputs 32 bits per call. I chose the `padding` length to be 12 bytes, equivalent to 3 outputs of the MT19937. Since in order to clone an MT19937 we need at least 624 of its output, we need to query the server `624//3` times.
```python
from nclib import Netcat
def ru(nc, b):
"""Recieve until"""
r = b""
while b not in r:
r += nc.recv(1)
return r
nc = Netcat(("193.57.159.27", 56926))
ru(nc, b"n: ")
n = int(nc.recvline())
def get_enc(buf):
"""Returns enc(pad(buf)) from the server"""
ru(nc, b"opt: ")
nc.send(b"1\n")
ru(nc, b"msg: ")
nc.send(str(buf).encode() + b"\n")
ru(nc, b"c: ")
return int(nc.recvline())
def gen_poly(pad, padbitlength, ct, pt):
"""
Generate polynomial enc(pad(pt)) - ct
"""
return ((2<<(8*254)) + (pad * 2^(8*(256 - padbitlength//8 - 2))) + pt)^e - ct
pt = 1 << (1920) # Long enough pt such that padding is 12 bytes
pads = []
for i in range(624//3):
ct = get_enc(pt)
x = PolynomialRing(Zmod(n), 'x').gen() # `x` represents padding
pol = gen_poly(x, 96, ct, pt).monic() # create polynomial in `x`
pads.append(pol.small_roots()[0]) # solve polynomial to get `x`
```
### Cloning the PRNG
From the padding recovered above, we can now recover the `624` 32-bit integers that are the output of the MT19937, and thereafter clone the RNG.
```python
# https://github.com/JuliaPoo/MT19937-Symbolic-Execution-and-Solver
from MT19937 import MT19937
data624 = []
for p in pads:
for i in range(3):
data624.append((int(p) >> 32*i) & ((1<<32) - 1))
rng_clone = MT19937(state_from_data = (data624, 32))
```
I used an MT19937 library I wrote _ages_ ago to clone the PRNG. While we're at it, might as well implement `getrandbits` so we can predict the padding.
```python
def copy_genrandbits(rng, nbits):
ds = [rng() for _ in range(nbits//32)][::-1]
res = ds[0]
for d in ds[1:]:
res <<= 32
res += d
q = nbits % 32
if q:
res += (rng() >> (32-q)) << (32*(nbits//32))
return res
```
### Predicting the padding of the flag
At this point we might as well get the encryption of the flag from the server too:
```python
def get_encflag():
ru(nc, b"opt: ")
nc.send(b"2\n")
ru(nc, b"c: ")
return int(nc.recvline())
enc_flag = get_encflag()
```
Now the padding for `enc_flag` is created by the PRNG that has been forward 624 times (due to all the previous encryptions we made). So to predict the padding for this, we have to forward our cloned RNG 624 times as well.
Do note however, we don't know the length of the flag, so we don't know how many bits is the padding. Eitherways we can make a guess of `54` bytes:
```python
flen = 54
padbitlength = (256-flen-3)*8
rng_clone = MT19937(state_from_data = (data624, 32))
for i in range(624):
rng_clone() # forward rng_clone
fpad = copy_genrandbits(rng_clone, padbitlength)
```
### Recovering the flag
With all these we can do the exact same thing as before: Coppersmith to recover the flag
```python
x = PolynomialRing(Zmod(n), 'flag').gen()
pol = gen_poly(fpad, padbitlength, enc_flag, x)
roots = pol.small_roots(X=(1<<(flen*8)))
print(roots)
# > []
```
But wait, there are no roots. This probably means that the flag length `flen` guessed earlier is wrong, so just create a loop to guess the flag length:
```python
for flen in range(54,0,-1):
padbitlength = (256-flen-3)*8
rng_clone = MT19937(state_from_data = (data624, 32))
for i in range(624):
rng_clone()
fpad = copy_genrandbits(rng_clone, padbitlength)
x = PolynomialRing(Zmod(n), 'flag').gen()
pol = gen_poly(fpad, padbitlength, enc_flag, x)
roots = pol.small_roots(X=(1<<(flen*8)))
if len(roots) != 0:
break
flag = long_to_bytes(roots[0])
print("Flag:", flag.decode())
# > Flag: rarctf{but-th3y_t0ld_m3_th1s_p4dd1ng_w45-s3cur3!!}
```
The full solve script can be found in [sol/sol.sage](sol/sol.sage).
