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 se calcula como 2 * getrandbits(32) + 1.

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

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

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

Para que esta estrategia funcione, tenemos que encontrar un exponente 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 , 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.