Personalized

3 minutes to read

We are given the Python source code used to encrypt the flag:

#!/usr/bin/env python3

from Crypto.Util.number import *
from random import seed, getrandbits

m = bytes_to_long(open('flag.txt', 'rb').read())
print("What's your name?\n>>> ", end='')
name = open(0, 'rb').readline().strip()
seed(bytes_to_long(name))
e = 2*getrandbits(32)+1
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, e, n)
print(f"Here's your flag, {''.join(chr(i) for i in name)}!")  
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')

It uses a RSA implementation where we can provide a name that will be used as the seed for a Pseudo-Random Number Generator (PRNG). And then the public exponent $e$ is computed as 2 * getrandbits(32) + 1.

Each time we connect to the server, the public modulus $n$ will be different, but as long as we use the same name, the exponent $e$ will be the same. Hence, we will get this system of congruences:

$$ \begin{cases} m^e \equiv c_1 \pmod{n_1} \newline m^e \equiv c_2 \pmod{n_2} \newline m^e \equiv c_3 \pmod{n_3} \newline \dots \newline m^e \equiv c_k \pmod{n_k} \newline \end{cases} $$

According to the Chinese Remainder Theorem (CRT), this system of congruences will have a unique solution modulo $n_1 \cdot c_2 \cdot \dots \cdot n_k$ as long as all $n_i$ are coprime with each other (which is satisfied). With enough equations, we will have that $m^e < n_1 \cdot c_2 \cdot \dots \cdot n_k$, and the solution of the CRT will be precisely $m^e$.

Then, the next step will be to do the $e$-th root and get $m$.

To make this strategy work, we need to find an exponent $e$ that is short enough, so that we don’t need to get so many messages.

One approach is to use brute force. We will find out that using 8115501 ("{\xd5-" as bytes) as a seed will result in $e = 73$, which is short enough.

For the CRT, I requested 1000 pairs of ciphertext and modulus. Maybe it is a lot, but it will make sure that the CRT works (imported from SageMath into Python).

This is the final Python script:

#!/usr/bin/env python3

from gmpy2 import iroot
from pwn import context, log, remote, sys
from random import getrandbits, seed
from sage.all import CRT


def main():
    if len(sys.argv) != 3:
        log.warning(f'Usage: python3 {sys.argv[0]} <host> <port>')  
        exit(1)

    host, port = sys.argv[1], sys.argv[2]

    seeds = log.progress('Seed')

    for i in range(10000000):
        seeds.status(str(i))
        seed(i)

        if getrandbits(32) < 50:
            nice_seed = i
            break

    if nice_seed is None:
        log.warning('Could not find nice seed')
        exit(1)

    seeds.success(str(nice_seed))

    name = bytes.fromhex(hex(nice_seed)[2:])
    seed(nice_seed)
    e = 2 * getrandbits(32) + 1

    log.info(f'{e = }')

    ns, cs = [], []

    connections = log.progress('Connections')

    for i in range(1000):
        connections.status(str(i + 1))

        with context.local(log_level='CRITICAL'):
            r = remote(host, int(port))
            r.sendlineafter(b'>>> ', name)

            r.recvuntil(b'n = ')
            ns.append(int(r.recvline().strip().decode()))
            r.recvuntil(b'c = ')
            cs.append(int(r.recvline().strip().decode()))
            r.close()

    connections.success(str(i))

    m_e = CRT(cs, ns)
    m = iroot(m_e, e)

    log.success(f'Flag: {bytes.fromhex(hex(m[0])[2:]).decode()}')


if __name__ == '__main__':
    main()

And we obtain the flag:

$ python3 solve.py puzzler7.imaginaryctf.org 4002  
[+] Seed: 8115501
[*] e = 73
[+] Connections: 1000
[+] Flag: ictf{just_f0r_y0uuuuuuuu}

The full script can be found in here: solve.py.