Resumen
Kyber ha sido sometido a criptoanálisis extensivo desde su publicación en 2017. Hasta julio de 2026, no se conoce ningún ataque que rompa los parámetros recomendados en tiempo práctico. Sin embargo, existen ataques que reducen el costo y líneas de investigación abiertas.
Ataques Clásicos
Ataques de Retículos (BKZ + SVP)
El ataque más conocido contra LWE es resolver el problema de retículo subyacente usando el algoritmo BKZ (Block Korkine-Zolotarev) con un oráculo SVP (Shortest Vector Problem).
Costo estimado para ML-KEM-768:
- BKZ con bloque β ≈ 500
- Tiempo estimado: > 2²⁰⁷ operaciones
- Memoria: varias TB
La complejidad crece exponencialmente con el tamaño del bloque. Para Kyber, los parámetros están elegidos para que el bloque necesario exceda cualquier capacidad práctica previsible.
Ataques de Decisión
El atacante puede intentar distinguir instancias LWE de aleatorias usando técnicas estadísticas. Estos ataques no recuperan la clave pero pueden romper la seguridad semántica.
Para Kyber, los parámetros están elegidos para que la ventaja del distinguidor sea insignificante (< 2⁻¹⁴⁰).
Ataques Algebraicos
Algunos trabajos han explorado ataques algebraicos aprovechando la estructura de anillo (por ejemplo, usando bases de Gröbner). Para Module-LWE con los parámetros de Kyber, no se ha encontrado una reducción significativa del costo.
Ataques Cuánticos
Ataques de Grover sobre el secreto
Grover puede buscar el secreto s en espacio O(2^(n/2)). Para Kyber:
| Parámetro | Búsqueda clásica | Búsqueda cuántica (Grover) |
|---|---|---|
| ML-KEM-512 | 2²⁵⁶ | 2¹²⁸ |
| ML-KEM-768 | 2³⁸⁴ | 2¹⁹² |
| ML-KEM-1024 | 2⁵¹² | 2²⁵⁶ |
Grover ofrece una aceleración cuadrática, pero sigue siendo intratable para las dimensiones de Kyber.
Algoritmo de Shor
Shor no resuelve LWE. Shor resuelve el problema del logaritmo discreto y la factorización explotando la estructura de grupo abeliano oculto. LWE sobre retículos no tiene esa estructura — es un problema de aproximación de retículos, no de grupos.
Algoritmo de Regev (cuántico)
Regev (2023) propuso un nuevo algoritmo cuántico que resuelve LWE en tiempo 2^(n/2) bajo ciertas condiciones, comparable al ataque clásico con BKZ pero con ventajas de memoria. Hasta ahora, no se ha demostrado que supere los ataques clásicos para los parámetros de Kyber.
Ataques de Fourier
Los ataques cuánticos basados en la transformada de Fourier sobre retículos (como el algoritmo de Kuperberg para isogenías) no tienen análogo conocido que sea eficiente para LWE estándar o Module-LWE.
Ataques de Side-Channel
Temporización
La implementación de referencia de Kyber es constante en tiempo. Sin embargo, implementaciones incorrectas pueden filtrar:
- El secreto
smediante variaciones en la multiplicación NTT no constante - El valor
men la descompresión si no se implementa con cuidado
Mitigación: usar la implementación de referencia verificada o librerías auditadas (liboqs, AWS-LC, BoringSSL).
Consumo de Potencia / EM
Los ataques de análisis de potencia (DPA/SPA) pueden recuperar s si el dispositivo no tiene contramedidas. Kyber es particularmente vulnerable en dispositivos embebidos sin blindaje.
Mitigación: blinding de exponentes, aleatorización de operaciones NTT, desacople de señales.
Errores de Cálculo (Fault Attacks)
Inducir errores en el cómputo de NTT durante la desencapsulación puede hacer que el resultado incorrecto filtre información sobre s.
Mitigación: verificación redundante, detección de errores en NTT.
Ataques Híbridos
La NSA recomienda X25519Kyber768 precisamente porque nadie confía al 100% en Kyber solo. Un ataque que rompa Kyber pero no X25519 seguiría siendo detenido por la capa clásica, y viceversa.
Líneas de Investigación Abiertas
| Línea | Riesgo actual | Notas |
|---|---|---|
| Algoritmos cuánticos para LWE | Bajo | No se conoce aceleración subexponencial |
| Ataques algebraicos mejorados | Bajo-Medio | La estructura de módulo podría ser explotable |
| Ataques de red neuronal | Bajo | Las NN no han mostrado ventaja sobre BKZ |
| Side-channel en implementaciones reales | Alto | El mayor riesgo real hoy |
| Fallos de parametrización en protocolos | Alto | Kyber es seguro; el protocolo que lo usa quizá no |
Conclusión
Kyber es seguro contra todo ataque conocido en julio de 2026. Su mayor riesgo no es criptoanalítico sino implementacional y protocolario: una mala implementación o un protocolo mal diseñado pueden romper la seguridad aunque el algoritmo subyacente sea sólido.
Esto no es diferente de la criptografía clásica. La novedad es que, al ser más nuevo, tiene menos auditoría acumulativa que AES o SHA-3.
Referencias
- Albrecht, M. et al. (2022). "Estimate all the LWE, NTRU schemes!" — Estimaciones de costo de ataques.
- Regev, O. (2023). "An Efficient Quantum Algorithm for LWE?" — Preprint, debate abierto.
- Bernstein, D. J. & Lange, T. (2020). "Post-quantum cryptography: handling the fallout."
- Xagawa, K. (2022). "Side-channel attacks on lattice-based KEMs." CHES 2022.