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 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
Análisis del código fuente
Afortunadamente, el código es corto. Comienza definiendo tres números enteros 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
Analizar la salida
Expresamos
Si expandimos los valores de
Podemos hacer lo mismo con
Pero no nos dan
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
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
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
Un truco es eliminar la variable
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
Nótese que
- Primero encontramos
:
- A continuación, resolvemos para
:
Y con esto, encontramos la flag
Implementación
En SageMath, podemos definir las variables
#!/usr/bin/env sage
p = 0x31337313373133731337313373133731337313373133731337313373133732ad
a = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
b = 0xdeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0dedeadc0de
trunc = 48
hint1 = 77759147870011250959067600299812670660963056658309113392093130
hint2 = 50608194198883881938583003429122755064581079722494357415324546
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
load('coppersmith.sage')
y, z = small_roots(P, (2 ** trunc, 2 ** trunc))[0]
print(f'{y = }; {z = }')
Finalmente, calculamos el valor de
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 = 53006259096585; z = 248699398699637
b'HTB{sm1th1ng_mY_c0pp3r_fl4G}L\xc6'
El script completo se puede encontrar aquí: solve.sage
.