Going In Circles (Crypto)

Datos del reto

Campo	Valor
CTF	Nullcon CTF 2026
Reto	Going In Circles
Categoría	Crypto
Flag	ENO{CRC_is_just_some_modular_remainder}

---

Descripción del reto

El servicio devolvía, en cada conexión, el resultado de reducir la flag módulo un polinomio aleatorio en GF(2)[x]. Con una sola muestra no era suficiente para recuperar el secreto, pero cada conexión añadía una relación nueva.

---

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 un polinomio binario, cada respuesta del servidor se podía leer así.

flag ≡ r (mod f)

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

---

Análisis

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

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

entonces se podía obtener una solución única módulo el mínimo común múltiplo de los polinomios. A medida que ese módulo combinado crecía, llegaba un punto en el que ya fijaba por completo la longitud de la flag y la solución dejaba 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 suficiente para reconstruir el entero original y luego convertirlo otra vez a bytes.

Cada respuesta solo daba un resto, pero al reunir suficientes restos se podía reconstruir el valor original.

---

Resolución

La implementación necesitaba operaciones básicas sobre polinomios binarios, como producto sin acarreo, división con resto, MCD, MCD extendido y una rutina crt_poly() para combinar 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}