Datos del reto

Descripción del reto

El reto nos da un script chall.py que:

1. Lee la flag desde flag.txt y la convierte en un entero (interpretando los bytes en big-endian).
2. Genera un polinomio aleatorio f de 32 bits (entero de hasta 32 bits, interpretado como polinomio en GF(2)[x]).
3. Aplica una función reduce(flag, f) y nos devuelve el par (reduce(flag, f), f).

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

Cada conexión al servicio nos da dos números: el "resto" de la flag módulo f y el propio f.

Reconocimiento

En GF(2)[x] los coeficientes están en {0, 1} y la suma es XOR. Un entero se interpreta como polinomio: el bit en posición i es el coeficiente de x^i. La función reduce(a, f) hace la reducción de a módulo f en GF(2)[x]. Por tanto, en cada muestra tenemos r = flag mod f y f = polinomio "módulo" (grado ≤ 31), es decir flag ≡ r (mod f) en GF(2)[x].

Análisis de la vulnerabilidad

El Teorema Chino del Resto (CRT) también vale en GF(2)[x]: si tenemos congruencias x ≡ r1 (mod f1) y x ≡ r2 (mod f2) con f1 y f2 coprimos, existe un único x módulo lcm(f1,f2) que cumple ambas.

Cada conexión nos da un nuevo par (r_i, f_i) con flag ≡ r_i (mod f_i). Combinando estas congruencias con CRT (empezando con R = r1, M = f1 y actualizando con cada nuevo (r, f) a R', M' = lcm(M, f)), cuando el grado de M sea mayor o igual que la longitud en bits de la flag, la solución módulo M será única y coincidirá con la flag. Entonces se puede decodificar R como bytes y buscar el formato ENO{...}.

Explotación

Aritmética en GF(2)[x]

Se implementan sobre enteros: grado, multiplicación sin acarreo, división con resto, MCD y MCD extendido (para CRT).

CRT en GF(2)[x]

La función crt_poly(r1, m1, r2, m2) resuelve x ≡ r1 (mod m1) y x ≡ r2 (mod m2), comprueba consistencia y devuelve (x, m) con m = lcm(m1, m2).

Bucle principal

1. Conectar al servicio y recibir (r, f).
2. Si f es 0 o 1 se ignora.
3. La primera muestra válida inicializa R = r, M = f.
4. Para las siguientes, combinar con CRT: R, M = crt_poly(R, M, r, f).
5. Tras cada actualización, intentar decodificar R como bytes y buscar prefijo/sufijo de la flag; si se encuentra, imprimir y terminar.

Con suficientes conexiones, el módulo combinado M crece hasta acotar unívocamente la flag.

Flag

ENO{CRC_is_just_some_modular_remainder}

Lecciones aprendidas

El nombre "Going In Circles" encaja con dar vueltas al servidor (muchas conexiones) y con la estructura algebraica de polinomios sobre GF(2) y congruencias (CRT).