Tough decisions

Champagne for my real friends, real pain for my sham friends.

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• tough_decisions.py

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:

Donde solo conocemos un vector , el módulo y el texto cifrado . La dimensión de los vectores y es , 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 :

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 , 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 . Por tanto, ya sabemos algunas salidas de real.

Usando este conocimiento, podemos formar esta ecuación usando muestras:

Que es equivalente a esta ecuación matricial:

Sería bueno encontrar el valor de . Hay retos relacionados con LWE donde es posible encontrar 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 son muy grandes.

En cambio, podemos emplear el hecho de que todos los errores son pares, por lo que podemos aplicar y hallar :

Por lo tanto, podremos encontrar con al menos 16 pares de vectores y textos cifrados .

Una vez que tengamos un valor para , podemos pasar por todas las salidas que tenemos, tomar cada vector , multiplicarlo por y ver si el texto cifrado 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.