Matrixfun II (Crypto)

Datos del reto

Campo	Valor
CTF	Nullcon CTF 2026
Reto	Matrixfun II
Categoría	Crypto
Flag	ENO{l1ne4r_alg3br4_i5_ev3rywh3re}

---

Descripción del reto

El servidor cifraba bloques sobre el alfabeto Base64 usando una transformación afín del estilo c = A·x + b (mod 65). Además, no solo mostraba el ciphertext de la flag, también dejaba cifrar mensajes arbitrarios con la misma clave. Ese oráculo de cifrado era justo lo que hacía falta para reconstruir A y b.

---

Reconocimiento

Cada bloque de 16 símbolos Base64 se convertía a índices 0..64, y sobre ese vector el servidor aplicaba esto.

c = A·x + b (mod 65)

Cuando un esquema así deja cifrar texto elegido con la misma matriz y el mismo vector, recuperar la clave suele ser cuestión de preparar bien las entradas.

---

Análisis

Aquí había dos observaciones muy sencillas.

• Si el bloque de entrada era todo ceros, la salida era directamente b.
• Si el bloque de entrada tenía un único 1 en la posición j, la salida era la columna j de A sumada con b.

Como en Base64 el índice 0 corresponde a 'a', el siguiente paso era construir mensajes cuya primera salida representara esto.

• aaaaaaaaaaaaaaaa para obtener b
• un bloque con un único 1 en la posición deseada para recuperar cada columna de A

Con b y las 16 columnas de A, ya solo faltaba invertir la matriz módulo 65 y descifrar el ciphertext inicial.

No hacía falta romper nada por fuerza bruta. Todo salía de explotar la linealidad del esquema.

---

Resolución

El procedimiento completo fue este.

1. Guardar el ciphertext de la flag.
2. Pedir el cifrado de un bloque que se traduzca a 16 ceros y extraer b.
3. Repetir el proceso 16 veces con bloques que tengan un único 1 para recuperar cada columna de A.
4. Calcular A^-1 mod 65.
5. Aplicar x = A^-1(c - b) a cada bloque del ciphertext.
6. Reconstruir la cadena Base64 y decodificarla.

En el código, esto requería una función para recuperar A y b desde el servicio, otra para invertir matrices módulo 65 y una última para transformar los bloques cifrados de vuelta al texto original.

Una vez montado eso, el cifrado dejaba de ser desconocido. Pasaba a ser un sistema determinista del que se podían recuperar sus partes una por una.

---

Flag

ENO{l1ne4r_alg3br4_i5_ev3rywh3re}