Read between the lines

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 $i + \mathtt{0x1337}$ repetido $b_i$ veces, donde $b_i$ es el valor ASCII del carácter $i$-é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:

$$ c = \sum_{m \in \mathtt{encoded\_flag}} m^e \mod{n} $$

Recordemos que cada $m$ en encoded_flag es $i + \mathtt{0x1337}$ repetido $b_i$ veces, Entonces tenemos

$$ c = \sum_{i = 0}^{N - 1} b_i \cdot (i + \mathtt{0x1337})^e \mod{n} $$

donde $N$ es la longitud de la flag y $b_i$ es el carácter $i$-é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 $c$ de la siguiente manera:

$$ c = b_0 (0 + \mathtt{0x1337})^e + b_1 (1 + \mathtt{0x1337})^e + \dots + b_{N - 1} (N - 1 + \mathtt{0x1337})^e \mod{n} $$

Reducción de retículo

Nótese que podemos pre-calcular $(i + \mathtt{0x1337})^e \mod{n}$, y queremos encontrar los coeficientes $b_i$. Para esto, podemos usar una técnica de retículo como LLL.

En primer lugar, nos desharemos de $\mod{n}$ para trabajar sobre los enteros, así que para cierto $k \in \mathbb{Z}$ tenemos:

$$ b_0 (0 + \mathtt{0x1337})^e + b_1 (1 + \mathtt{0x1337})^e + \dots + b_{N - 1} (N - 1 + \mathtt{0x1337})^e + k \cdot n - c = 0 $$

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

$$ M = \begin{pmatrix} (0 + \mathtt{0x1337})^e & (1 + \mathtt{0x1337})^e & \dots & (N - 1 + \mathtt{0x1337})^e & n & -c \\ 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \\ 0 & 0 & \dots & 0 & 0 & R \\ \end{pmatrix} $$

Donde $R$ es un número arbitrariamente grande como $R = 2^{1024}$. el vector objetivo es $(0, b_0, b_1, \dots, b_{N - 1}, k, R)$, que pertenece al retículo porque:

$$ \begin{pmatrix} (0 + \mathtt{0x1337})^e & (1 + \mathtt{0x1337})^e & \dots & (N - 1 + \mathtt{0x1337})^e & n & -c \\ 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \\ 0 & 0 & \dots & 0 & 0 & R \\ \end{pmatrix} \cdot \begin{pmatrix} b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ R \\ \end{pmatrix} $$

Y dado que el vector objetivo es corto (porque $0 \leqslant b_i \lt 256$), podemos hallarlo usando LLL en la matriz $M$. Podemos usar el valor $R$ 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.