Datos del reto

Descripción del reto

El servidor nos da un cifrado que funciona así:

1. Alfabeto: Base64 estándar (65 caracteres: a-z, A-Z, 0-9, +, /, =).
2. Parámetros: Matriz aleatoria A ∈ ℤ₆₅^(16×16) y vector b ∈ ℤ₆₅^16.
3. Proceso: El mensaje se codifica en Base64, se rellena con = hasta longitud múltiplo de 16, se divide en bloques de 16 símbolos (cada símbolo → índice 0–64). Para cada bloque x: c = A·x + b (mod 65).

Al conectar, el servidor imprime el cifrado de la flag y luego actúa como oráculo: podemos enviar mensajes en hex y nos devuelve su cifrado con la misma A y b.

Reconocimiento

El cifrado es afín por bloques: c = A·x + b (mod 65). Si recuperamos A y b, podemos despejar x = A⁻¹(c − b) (mod 65) y descifrar cualquier texto. La vulnerabilidad es tener oráculo de cifrado con la misma clave.

Análisis de la vulnerabilidad

• Recuperar b: El vector b es el cifrado del bloque cuyos 16 índices son 0 (16 veces 'a'). Enviando un mensaje cuya Base64 tenga como primer bloque 16×'a', la respuesta del oráculo para ese bloque es b.
• Recuperar A (columna a columna): Para la columna j usamos el vector eⱼ (0 salvo un 1 en la posición j). Enviando un mensaje con primer bloque con ese contenido, el oráculo devuelve cⱼ = (columna j de A) + b, luego columna j de A = cⱼ − b (mod 65). Con 1 consulta para b y 16 para las columnas de A tenemos la clave.
• Invertir A módulo 65: Con eliminación de Gauss–Jordan en ℤ₆₅ se obtiene A⁻¹. Si no hay pivote coprimo con 65, A no sería invertible (en este reto no fue necesario manejarlo).

Explotación

1. Conectar y guardar el ciphertext de la flag del banner.
2. Enviar mensaje cuya Base64 empiece en 16×'a' → respuesta = b.
3. Para j = 0..15, enviar mensaje con bloque eⱼ (1 en posición j) → cⱼ − b = columna j de A.
4. Calcular A⁻¹ (mod 65) con Gauss–Jordan.
5. Para cada bloque c del ciphertext: x = A⁻¹(c − b), mapear a Base64, decodificar y ajustar padding.

Referencia del código: recover_Ab(oracle) obtiene b y A; mat_inv_mod(A, 65) calcula la inversa; decrypt(cipher_list, A, bvec) aplica x = A⁻¹(c − b) y decodifica Base64.

Flag

ENO{l1ne4r_alg3br4_i5_ev3rywh3re}

Lecciones aprendidas

• Un cifrado afín por bloques con oráculo de cifrado permite recuperar la matriz y el vector de desplazamiento enviando bloques elegidos (cero y vectores canónicos).
• La inversión de matrices en ℤₙ (n compuesto) requiere pivotes coprimos con n en Gauss–Jordan.