Read between the lines

4 minutos de lectura

Este es un reto que diseñé para CrewCTF 2024 como miembro de thehackerscrew. Se nos proporciona el código fuente en Python para cifrar la flag:

#!/usr/bin/env python3

from random import shuffle
from Crypto.Util.number import getPrime


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

assert len(FLAG) < 100

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

shuffle(encoded_flag)

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n{e = }\n{c = }\n')

También tenemos la salida del script:

n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623

Análisis del código fuente

Primero, la flag se codifica como el índice del carácter de la flag repetido veces, donde es el valor ASCII del carácter -ésimo:

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

Esta lista encoded_flag se mezcla con shuffle, pero es irrelevante como veremos más adelante:

shuffle(encoded_flag)

Entonces este es el texto cifrado:

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n

Solución

Entonces, en términos matemáticos tenemos:

Recordemos que cada en encoded_flag es repetido veces, Entonces tenemos

donde es la longitud de la flag y es el carácter -ésimo de la flag. Obsérvese que el shuffle es irrelevante porque la suma es conmutativa, por lo que el orden no importa.

Podemos expresar de la siguiente manera:

Reducción de retículo

Nótese que podemos pre-calcular , y queremos encontrar los coeficientes . Para esto, podemos usar una técnica de retículo como LLL.

En primer lugar, nos desharemos de para trabajar sobre los enteros, así que para cierto tenemos:

Ahora, usaremos el retículo generado por las columnas de

Donde es un número arbitrariamente grande como . el vector objetivo es , que pertenece al retículo porque:

Y dado que el vector objetivo es corto (porque ), podemos hallarlo usando LLL en la matriz . Podemos usar el valor para encontrar el vector objetivo en la matriz del retículo reducido:

N = 100
cts = [pow(m + 0x1337, e, n) for m in range(N)]

R = 2 ** 1024
M = Matrix([
    [*cts, n, -c],
    *[[0] * i + [1] + [0] * (len(cts) - i + 1) for i in range(len(cts))],
    [0] * len(cts) + [0, R]
])

L = M.T.LLL()
assert L[-1][0] == 0 and L[-1][-1] == R
res = L[-1][1:-1]

flag = [v for v in res if v != 0]
print(bytes(flag).decode())

Flag

Con esto, tendremos la flag:

$ python3 solve.py
crew{D1d_y0u_3xp3cT_LLL_t0_b3_h1Dd3n_b3tw3en_th3_l1n3s???}

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