Alaniz Cipher: Un Cifrado Simétrico Quantum Resistant

En el mundo post-cuántico llevamos años hablando de siempre lo mismo: cifrados basados en retículas, en códigos, en funciones hash gordas y en esquemas multivariantes
que se apoyan en sistemas de ecuaciones polinómicas. El Alaniz Cipher se mete en ese último grupo, pero con una vuelta de tuerca
importante: en lugar de construir un sistema de ecuaciones público que cualquiera
pueda escribir y analizar, lo que hace es esconder todas esas ecuaciones dentro de
una estructura topológica discreta —un grafo con una especie de campo de datos
encima— y usar coeficientes secretos que nunca se exponen. 

El problema que le
planteas al atacante es: «tienes una caja negra no lineal, conectada según una red
concreta, y sólo puedes hacer consultas entrada-salida; intenta invertirla sin saber
qué ecuaciones hay dentro». El objetivo es claro: proponer una base de dureza que no se parezca demasiado a nada
de lo que ya está en el estándar, ni a las arquitecturas que han ido cayendo (como
Rainbow), pero que siga viviendo en la familia multivariante, donde de momento no
hay atajos cuánticos conocidos.

La red estructural donde vive el mensaje

El esquema se construye sobre una red de nodos conectados por enlaces, sin ciclos,
es decir, una estructura de árbol. A cada nodo se le asocia un pequeño espacio de
estados posibles con varias coordenadas, y cada enlace especifica cómo debe encajar
el estado de un nodo con el de su vecino para que todo sea coherente.

Un mensaje en claro se representa como una asignación de un estado concreto en
cada nodo tal que todas esas reglas de coherencia se cumplen simultáneamente. Si
miras cualquier enlace, los dos extremos encajan exactamente con la transformación
que le corresponde a ese enlace. A eso, en lenguaje matemático, se le llama una
sección global del haz, pero aquí basta con pensar en «configuración global válida de
la red».

Como la red es un árbol y las reglas están bien elegidas, ocurre algo muy útil: basta
con fijar el estado en un único nodo para que todo lo demás quede determinado. Es
decir, hay una correspondencia limpia entre «mensaje corto en un nodo» y «mensaje
extendido por toda la red de forma coherente». Esa propiedad se explota tanto en el
cifrado como, sobre todo, en el descifrado.

Qué hace realmente el cifrado en cada nodo

Una vez tienes el mensaje extendido por la red, el cifrado actúa localmente en cada
nodo de manera independiente, pero siempre con la misma estructura lógica:

La clave simétrica es simplemente el conjunto de todos esos pares de transformaciones
secretas de cada nodo. El mapa no lineal público se ha construido como una pequeña
red de sustitución y permutación en dos etapas: opera de forma no lineal sobre cada
coordenada, mezcla coordenadas entre sí, introduce una constante aditiva y vuelve a
aplicar una operación no lineal, añadiendo también una parte lineal explícita.

¿Por qué tanto cuidado con la función no lineal? Porque las primeras versiones del
esquema usaban funciones homogéneas y separables por coordenadas (por ejemplo,
elevar al cubo cada componente por separado), y eso permitió un ataque muy eficiente:
el analista Rodríguez Langa mostró cómo, con un número lineal de consultas de
texto elegido, se podía recuperar la clave aprovechando las simetrías de escalado que
introducía esa homogeneidad. La versión actual rompe justamente esas simetrías y
obliga al atacante a enfrentarse a un sistema polinómico mucho más enredado, con
coeficientes secretos acoplados entre coordenadas.

Cómo se descifra aprovechando la estructura de la red

Para el legítimo destinatario, que sí conoce todas las transformaciones secretas, el
descifrado sigue un patrón bastante claro en tres pasos, apoyándose en el hecho de
que basta recuperar bien el estado en un nodo para reconstruir todo el mensaje:

La propia estructura de árbol y las restricciones lineales que la definen actúan como
filtro: si intentas propagar una solución incorrecta, casi siempre acabas generando
una configuración que no se corresponde con el cifrado real, por lo que el chequeo
final falla. En el artículo se explicita una cota teórica sobre la probabilidad de que
haya más de una solución válida y se acompaña de evidencia experimental en muchas
configuraciones donde el descifrado resulta único.

Supuesto de dureza y ataques previstos

El trabajo introduce un problema de inversión específico, el llamado Problema de
Inversión de Morfismos No Lineales de Haces sobre Grafos (NL-SMIP). Dicho sin jerga: te dan acceso a este cifrado como si fuera un oráculo, puedes inyectar
entradas y observar las salidas, pero no ves las ecuaciones internas ni sus coeficientes,
y tu objetivo es invertirlo o extraer la clave.

Se demuestra que, si alguien encontrase un algoritmo eficiente para resolver ese
problema en general, también podría resolver eficientemente un problema clásico
muy bien estudiado: encontrar soluciones de sistemas de ecuaciones cuadráticas con
muchas variables sobre un cuerpo finito. Ese problema es el que está detrás de muchas
construcciones multivariantes y se sabe que es, como mínimo, tan difícil como los
problemas típicos de la clase NP-completa.

En cuanto a la superficie de ataque:

No hay sistema de ecuaciones público. A diferencia de diseños como HFE
o Rainbow, las técnicas que explotan directamente la estructura algebraica
visible del sistema (ataques tipo MinRank, relinearización, análisis del jacobiano
público, etc.) no se trasladan de forma obvia.

• 
  Ataques por interpolación bloqueados. La imposibilidad de separar coordenadas y la presencia de constantes y mezcla intercoordenada en la función
  no lineal rompen las homogeneidades aprovechables.

• 
  Métodos algebraicos generales. Las bases de Gröbner y XL se encuentran
  con un sistema de grado alto y coeficientes secretos, lo que en la práctica los
  devuelve a un escenario similar al del problema multivariante genérico sin
  estructura explotable especial.

• Plano cuántico. A día de hoy no se conoce un algoritmo de tiempo polinómico
  que resuelva de forma general este tipo de sistemas, y el diseño del cifrado
  evita introducir estructuras adicionales que hayan dado problemas en otras
  propuestas.

Conviene remarcar que estamos ante un cifrado simétrico puro: la misma clave se
usa para cifrar y descifrar. Para llevarlo a un escenario de intercambio de claves al
estilo Kyber habría que envolverlo en una construcción de encapsulado (un KEM)
que aporte las propiedades criptográficas que se exigen en protocolos reales. Esto es trabajo futuro, igual que se hizo en su día al pasar de
un cifrado de sólo confidencialidad a un esquema estandarizable.

Tienes una implementación de referencia de Alaniz Cipher en GitHub, para que lo pruebes, lo evalúes, y aportes lo que consideres.

Saludos,

¡Saludos Malignos!