Copperbox

10 minutos de lectura

Se nos proporciona el siguiente código fuente en Python que cifra la flag:

import secrets

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

def lcg(x, a, b):
    while True:
        yield (x := a*x + b)

flag = open('flag.txt', 'rb').read()
x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')
gen = lcg(x, a, b)

h1 = next(gen) * pow(next(gen), -1, p) % p
h2 = next(gen) * pow(next(gen), -1, p) % p

with open('output.txt', 'w') as o:
    trunc = 48
    # oops, i forgot the last part
    o.write(f'hint1 = {h1 >> trunc}\n')
    o.write(f'hint2 = {h2 >> trunc}\n')

Y también tenemos la salida en output.txt:

hint1 = 71423363559670126636256015849609248068471254188780947659031431
hint2 = 60279909443976522334351660980145297750342536242395671298832176

Análisis del código fuente

Afortunadamente, el código es corto. Comienza definiendo tres números enteros , y , que se utilizan para definir un generador lcg:

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

def lcg(x, a, b):
    while True:
        yield (x := a*x + b)

El generador anterior implementa un generador lineal congruencial (LCG), que normalmente se usa como un generador de números pseudo-aleatorios (PRNG). Por ejemplo, Glibc y Java usan algoritmos de PRNG basados en LCG.

La semilla del LCG es la flag como valor entero con algunos bytes aleatorios al final:

flag = open('flag.txt', 'rb').read()
x = int.from_bytes(flag + secrets.token_bytes(30-len(flag)), 'big')
gen = lcg(x, a, b)

Luego, el programa calcula dos valores h1 y h2 que dependen de las salidas del LCG (4 pasos en total):

h1 = next(gen) * pow(next(gen), -1, p) % p
h2 = next(gen) * pow(next(gen), -1, p) % p

Finalmente, se nos dan los valores truncados de estos h1 y h2. En particular, el programa elimina los 48 bits menos significativos:

with open('output.txt', 'w') as o:
    trunc = 48
    # oops, i forgot the last part
    o.write(f'hint1 = {h1 >> trunc}\n')
    o.write(f'hint2 = {h2 >> trunc}\n')

Generador congruencial lineal

Definamos el LCG en términos matemáticos de la siguiente manera:

Hay que tener en cuenta que nos falta la parte “congruencial” del LCG porque no hay módulo.

Las salidas del LCG generalmente se definen de manera recursiva, pero podemos transformar la expresión:

Con esto, hemos expresado las salidas del LCG en términos de la semilla inicial :

Obsérvese que los LCG no son seguros, porque si se filtra el valor de se podrán recuperar los estados anteriores y predecir las salidas futuras. Por esta razón, las salidas de los LCG generalmente se truncan, para evitar que los adversarios rompan el PRNG (o al menos, que sea más difícil de romper).

Analizar la salida

Expresamos en términos matemáticos:

Si expandimos los valores de y , obtenemos

Podemos hacer lo mismo con , que depende de y :

Pero no nos dan ni … eso sería demasiado fácil. En cambio, tenemos:

Solución

Cada vez que vea salidas truncadas en un desafío CTF de criptografía, es muy probable que la solución esté relacionada con el método de Coppersmith o alguna técnica de reducción de retículo. De hecho, el nombre de reto es Copperbox, que sugiere el uso del método de Coppersmith.

Para esto, necesitamos definir uno o más polinomios módulo un entero, de tal manera que haya una raíz pequeña en módulo un divisor del módulo del polinomio. Esta vez, el módulo es un número primo, por lo que no tenemos que preocuparnos por eso.

Esta raíz pequeña será encontrada por el método de Coppersmith. La técnica emplea reducción de retículo para encontrar otro polinomio que comparta la misma raíz con el polinomio modular proporcionado. Sin embargo, el nuevo polinomio está definido en los enteros, por lo que el cálculo de las soluciones es eficiente.

Entonces, veamos qué valores nos faltan. Básicamente,

Semilla inicial (la flag)
Valor truncado de (48 bits). Llamémos lo
Valor truncado de (48 bits). Llamémos lo

Por lo tanto, podemos expresar:

En este punto, podemos sustituir estos valores en las expresiones anteriores. Para mejorar la legibilidad, sea , y sean , , so

Hasta ahora, todo bien. Pero eliminemos el inverso modular multiplicando en ambos lados:

Ahora, podemos agrupar variables:

Nos quedan tres variables y dos ecuaciones. Si no tuviéramos más información sobre este sistema, no sería resoluble. Sin embargo, esta vez sabemos que , por lo que son valores pequeños en comparación con , o . Estos son buenos candidatos para buscar raíces pequeñas. Obsérvese que puede ser grande, ya que es una flag (generalmente alrededor de 30 caracteres, así que alrededor de ).

Un truco es eliminar la variable en las ecuaciones combinando las dos. Dado que las expresiones son un poco largas, sean

Entonces, comenzamos con

Luego, ponemos el mismo coeficiente en la variable :

Ahora restamos ambas ecuaciones:

Obsérvese que podemos simplificar un poco la expresión y eliminar el valor :

Así que hemos encontrado una sola ecuación en variables y . Ahora podemos definir fácilmente el polinomio:

Nótese que , por lo que es una raíz, y de hecho pequeña porque está limitadas por . Como resultado, podemos usar el método de Coppersmith bivariado para encontrar ambos valores. Una vez que los tenemos, es trivial encontrar :

Primero encontramos :

A continuación, resolvemos para :

Y con esto, encontramos la flag .

Implementación

En SageMath, podemos definir las variables y en , definir los valores auxiliares y luego definir el polinomio :

#!/usr/bin/env sage

p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de

trunc = 48

hint1 = 71423363559670126636256015849609248068471254188780947659031431113392093130
hint2 = 60279909443976522334351660980145297750342536242395671298832176357415324546


Y, Z = PolynomialRing(Zmod(p), 'Y, Z').gens()

A = [sum(a ** m for m in range(i + 1)) for i in range(4)]

H1 = hint1 << trunc
H2 = hint2 << trunc

HY = a * H1 + a * Y - 1
HZ = a * H2 + a * Z - 1

P = a ** 2 * HZ * ((H1 + Y) * A[1] - A[0]) - HY * ((H2 + Z) * A[3] - A[2])

Ahora, usamos el método de Coppersmith para calcular las raíces pequeñas y . Estaré usando la implemetación de defund:

load('coppersmith.sage')
y, z = small_roots(P, (2 ** trunc, 2 ** trunc))[0]
print(f'{y = }; {z = }')

Finalmente, calculamos el valor de para obtener la flag:

h1 = H1 + y
h2 = H2 + z

x = b * (A[0] - A[1] * h1) * pow(a ** 2 * h1 - a, -1, p) % p
assert x == b * (A[2] - A[3] * h2) * pow(a ** 4 * h2 - a ** 3, -1, p) % p

print(bytes.fromhex(hex(x)[2:]))

Flag

Si ejecutamos el script, obtendremos la flag (un buen easter egg es que el relleno aleatorio L\xc6 parece decir LCG):

$ sage solve.sage
y = 43830429126143; z = 31877652973308
b'HTB{sm1th1ng_mY_c0pp3r_fl4G}\xa9\xa2'

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