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 challenge source can be found here.

The Vuln: The padding

This is a pretty straightforward challenge. Take a look at the padding code:

1
2
3
4
5
6
7
8
9
10
11
12
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.

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.

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
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.

1
2
3
4
5
6
7
8
9
# 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.

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
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

1
2
3
4
5
6
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.sage.