Tough decisions
4 minutos de lectura
Champagne for my real friends, real pain for my sham friends.
Challenge contributed by CryptoHack
Challenge files:
Análisis del código fuente
Se nos proporciona un script en Python que toma la flag como bits y, por cada bit, imprime 6 salidas de una de las funciones real (bit 0) o fake (bit 1):
if __name__ == "__main__":
s = sample_key()
for b in get_flag():
print([[real, fake][b](s) for _ in range(6)])
Por lo tanto, el objetivo es encontrar una manera de diferenciar entre resultados de real y fake para obtener los bits de la flag.
Learning With Errors
La función fake devuelve solo bytes aleatorios:
def fake(s):
a = secrets.token_bytes(len(s))
return a, secrets.randbelow(256)
Mientras que real usa LWE (Learning With Errors) usando s como clave:
def real(s):
a = secrets.token_bytes(len(s))
e = sample_noise(7) - 64
return a, (dot(a, s) + e) % 256
En LWE, el cifrado funciona de la siguiente manera:
$$ b = \vec{a} \cdot \vec{s} + e \mod{n} = \sum_{i = 1}^N (a_i \, s_i) + e \mod{n} $$
Donde solo conocemos un vector $\vec{a}$, el módulo $n = 256$ y el texto cifrado $b$. La dimensión de los vectores $\vec{a}$ y $\vec{s}$ es $16$, y todos sus elementos son números de 8 bits:
def sample_key():
# LWE estimator told me I'd have more bits of security than bits in my key...
return secrets.token_bytes(16)
Distribución de los errores
Además, conocemos los posibles valores para los errores $e$:
def drbg():
# wuch wow, very deterministic
return secrets.randbelow(2)
def sample_noise(n):
e = 0
for _ in range(n):
e |= drbg()
e <<= 1
return e
Como e = sample_noise(7) - 64, observamos que todos los errores son números pares:
$ python3 -q
>>> import secrets
>>>
>>> def drbg():
... # wuch wow, very deterministic
... return secrets.randbelow(2)
...
>>>
>>> def sample_noise(n):
... e = 0
... for _ in range(n):
... e |= drbg()
... e <<= 1
... return e
...
>>> {sample_noise(7) - 64 for _ in range(10000)}
{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, -64, -62, -60, -58, -56, -54, -52, -50, -48, -46, -44, -42, -40, -38, -36, -34, -32, -30, -28, -26, -24, -22, -20, -18, -16, -14, -12, -10, -8, -6, -4, -2}
Solución
Entonces, sabemos que $e \in \{-128, -126, \dots, -2, 0, 2, \dots, 126, 128\}$, y este es el oráculo que necesitamos.
Además, como la flaf está formada por bytes ASCII, sabemos que el bit más significativo de cada byte es $0$. Por tanto, ya sabemos algunas salidas de real.
Usando este conocimiento, podemos formar esta ecuación usando $m$ muestras:
$$ \vec{b} = A \cdot \vec{s} + \vec{e} \mod{256} $$
Que es equivalente a esta ecuación matricial:
$$ \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} = \begin{pmatrix} a_{1, 1} & \dots & a_{1, N} \\ \vdots & \ddots & \vdots \\ a_{m, 1} & \dots & a_{m, N} \end{pmatrix} \cdot \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_N \end{pmatrix} + \begin{pmatrix} e_1 \\ e_2 \\ \vdots \\ e_m \end{pmatrix} \mod{256} $$
Sería bueno encontrar el valor de $\vec{s}$. Hay retos relacionados con LWE donde es posible encontrar $\vec{s}$ resolviendo el Closest Vector Problem (CVP) mediante algoritmos de reducción de retículos. Sin embargo, no es posible en este reto porque los errores $e$ son muy grandes.
En cambio, podemos emplear el hecho de que todos los errores son pares, por lo que podemos aplicar $\mod{2}$ y hallar $\vec{s} \mod{2}$:
$$ \vec{b} = A \cdot \vec{s} \mod{2} \iff \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} = \begin{pmatrix} a_{1, 1} & \dots & a_{1, N} \\ \vdots & \ddots & \vdots \\ a_{m, 1} & \dots & a_{m, N} \end{pmatrix} \cdot \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_N \end{pmatrix} \mod{2} $$
Por lo tanto, podremos encontrar $\vec{s} \mod{2}$ con al menos 16 pares de vectores $\vec{a_i}$ y textos cifrados $b_i$.
Una vez que tengamos un valor para $\vec{s} \mod{2}$, podemos pasar por todas las salidas que tenemos, tomar cada vector $\vec{a}$, multiplicarlo por $\vec{s} \mod{2}$ y ver si el texto cifrado $b \mod{2}$ coincide. Si alguna de las 6 salidas que tenemos para cada bit de la flag no coincide, estamos seguros de que es una salida de fake. De lo contrario, si las 6 salidas coinciden, con alta probabilidad tenemos una salida de real.
Flag
Si implementamos el procedimiento anterior, encontraremos la flag:
$ python3 solve.py
ECSC{D3c1s10n4l_LWE_m0d_2_445fb8dc91}
El script completo se puede encontrar aquí: solve.py.