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:
1. Transformación lineal secreta. Se aplica una matriz invertible que mezcla
las coordenadas entre sí; cada nodo tiene su propia matriz.
2. Función no lineal pública. Se pasa el resultado por una función diseñada con
criterios muy parecidos a los de una caja S de un cifrado de bloque moderno: alto grado de no linealidad, mezcla entre coordenadas, y sin simetrías sencillas
que permitan ataques por escalado o interpolación baratos.
3. Segunda transformación lineal secreta. Se combina de nuevo con otra
transformación del mismo nodo para obtener el valor cifrado que se publica.
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:
1. Resolución local. Se elige un nodo como referencia. Con el valor cifrado que
llega a ese nodo y con las matrices secretas de ese nodo, se plantea una pequeña
ecuación no lineal local: ¿qué posibles valores de entrada, al pasar por las
transformaciones y por la función pública, podrían haber dado ese resultado? Por construcción, el número de soluciones es muy pequeño.
2. Propagación por la red. Para cada solución candidata en ese nodo, se
reconstruye la configuración completa propagando por los enlaces según las
reglas de coherencia del haz. Esto da una posible imagen del mensaje original
extendido sobre todos los nodos.
3. Verificación. Se vuelve a aplicar el algoritmo de cifrado sobre esa configuración
y se comprueba si el resultado coincide exactamente con el texto cifrado recibido.
Si coincide, se acepta como descifrado; si no, se descarta y se prueba con la
siguiente candidata, si es que hay más.
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,
Nota de Chema Alonso
Además, aquí te dejo todos los artículos que he publicado en este blog sobre estos temas por si quieres leer con calma todo.
Espero que estos temas te estimulen a ir haciendo cada día más cosas con las tecnologías alrededor del mundo cuántico, porque cada día vamos a ver nuevos avances al respecto.
¡Saludos Malignos!
Sigue El lado del mal en Telegram
Chema Alonso en Threads
Chema Alonso en Mastodon
Chema Alonso en BSKY
Chema Alonso en Linkedin
DragonJAR
8.8 Chile
Ekoparty
e-Hack MX 
AREA 51 
Comunidad Dojo Panamá 
ARPAHE SOLUTIONS 
