Personalized

3 minutos de lectura

Se nos proporciona el código fuente en Python utilizado para cifrar la 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 = }')

Utiliza una implementación de RSA en la que podemos proporcionar un nombre que será usado como semilla de un Generador de Números Pseudo-Aleatorios (PRNG, Pseudo-Random Number Generator). Luego, el exponente $e$ se calcula como 2 * getrandbits(32) + 1.

Cada vez que nos conectemos al servidor, el módulo público $n$ será diferente, pero si utilizamos el mismo nombre, el exponente $e$ siempre será el mismo. Por tanto, tenemos el siguiente sistema de congruencias:

$$ \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} $$

De acuerdo con el Teorema Chino del Resto (CRT, Chinese Remainder Theorem), este sistema de congruencias tiene una única solución módulo $n_1 \cdot c_2 \cdot \dots \cdot n_k$ siempre que todos los $n_i$ sean coprimos unos con otros (lo cual es cierto). Con las ecuaciones suficientes, obtendremos que $m^e < n_1 \cdot c_2 \cdot \dots \cdot n_k$, y la solución del CRT será precisamente $m^e$.

Luego, el siguiente paso será hacer la raíz $e$-ésima para hallar $m$.

Para que esta estrategia funcione, tenemos que encontrar un exponente $e$ que sea suficientemente pequeño, de manera que no tengamos que conseguir demasiados mensajes.

Una iniciativa es utilizar fuerza bruta. Encontraremos que usando 8115501 ("{\xd5-" en bytes) como semilla resultará en $e = 73$, que es suficientemente pequeño.

Para que funcione el CRT, necesité 1000 pares de textos cifrados y módulos. A lo mejor son muchos, pero así aseguramos que el CRT funciona (importado desde SageMath en Python)

Este es el script final:

#!/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()

Y obtenemos la flag:

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

El script completo se puede encontrar aquí: solve.py.