Going In Circles (Crypto) – Nullcon CTF 2026

Datos del reto

Descripción del reto

El servicio entregaba, en cada conexión, el resultado de reducir la flag módulo un polinomio aleatorio en GF(2)[x]. No parecía suficiente para recuperar el secreto en una sola muestra, pero sí daba una relación nueva cada vez, y ahí estaba la gracia del reto.

Reconocimiento

El script del reto leía flag.txt, convertía la flag a entero y luego hacía algo equivalente a calcular el resto de ese entero al dividirlo por un polinomio de 32 bits en GF(2)[x]:

def reduce(a, f):
    while (l := a.bit_length()) > BITS:
        a ^= f << (l - BITS)
    return a

Interpretando cada entero como polinomio binario, cada respuesta del servidor se podía leer como:

flag ≡ r (mod f)

O sea, cada conexión no daba la flag directamente, pero sí una nueva restricción sobre ella.

Análisis

La forma de juntar esas restricciones era aplicar el Teorema Chino del Resto en GF(2)[x]. Si combinamos suficientes ecuaciones del estilo:

x ≡ r1 (mod f1)
x ≡ r2 (mod f2)

entonces se puede obtener una solución única módulo el mínimo común múltiplo de los polinomios. A medida que ese módulo combinado crece, llega un punto en el que ya fija por completo la longitud de la flag y la solución deja de tener varias opciones.

En la práctica, el ataque consistía en ir acumulando pares (r, f) hasta que el grado del módulo combinado fuera lo bastante grande como para reconstruir el entero original y luego convertirlo a bytes.

Resolución

La implementación necesitaba operaciones básicas sobre polinomios binarios: producto sin acarreo, división con resto, MCD, MCD extendido y una rutina crt_poly() para juntar dos ecuaciones cada vez.

El bucle principal quedaba así:

1. Conectar al servicio y recoger (r, f).
2. Ignorar casos degenerados como f = 0 o f = 1.
3. Inicializar R y M con la primera muestra válida.
4. Ir combinando cada nueva muestra con CRT.
5. Tras cada actualización, intentar decodificar R como bytes y comprobar si ya aparece algo con forma de ENO{...}.

Después de suficientes conexiones, el valor recuperado coincidía con la flag completa.

Flag

ENO{CRC_is_just_some_modular_remainder}