Attaques Connues

Résumé

Kyber a été soumis à une cryptanalyse extensive depuis sa publication en 2017. Jusqu'en juillet 2026, aucune attaque qui brise les paramètres recommandés en temps pratique n'est connue. Cependant, il existe des attaques qui réduisent le coût et des pistes de recherche ouvertes.

Attaques Classiques

Attaques de Réseaux (BKZ + SVP)

L'attaque la plus connue contre LWE consiste à résoudre le problème de réseau sous-jacent en utilisant l'algorithme BKZ (Block Korkine-Zolotarev) avec un oracle SVP (Shortest Vector Problem).

Coût estimé pour ML-KEM-768 :
  - BKZ avec bloc β ≈ 500
  - Temps estimé : > 2²⁰⁷ opérations
  - Mémoire : plusieurs To

La complexité croît exponentiellement avec la taille du bloc. Pour Kyber, les paramètres sont choisis pour que le bloc nécessaire dépasse toute capacité pratique prévisible.

Attaques de Décision

L'attaquant peut tenter de distinguer des instances LWE d'instances aléatoires en utilisant des techniques statistiques. Ces attaques ne récupèrent pas la clé mais peuvent briser la sécurité sémantique.

Pour Kyber, les paramètres sont choisis pour que l'avantage du distingueur soit insignifiant (< 2⁻¹⁴⁰).

Attaques Algébriques

Certains travaux ont exploré des attaques algébriques exploitant la structure d'anneau (par exemple, en utilisant des bases de Gröbner). Pour Module-LWE avec les paramètres de Kyber, aucune réduction significative du coût n'a été trouvée.

Attaques Quantiques

Attaques de Grover sur le secret

Grover peut chercher le secret s dans un espace O(2^(n/2)). Pour Kyber :

Paramètre	Recherche classique	Recherche quantique (Grover)
ML-KEM-512	2²⁵⁶	2¹²⁸
ML-KEM-768	2³⁸⁴	2¹⁹²
ML-KEM-1024	2⁵¹²	2²⁵⁶

Grover offre une accélération quadratique, mais reste intraitable pour les dimensions de Kyber.

Algorithme de Shor

Shor ne résout pas LWE. Shor résout le problème du logarithme discret et la factorisation en exploitant la structure de groupe abélien caché. LWE sur les réseaux n'a pas cette structure — c'est un problème d'approximation de réseaux, pas de groupes.

Algorithme de Regev (quantique)

Regev (2023) a proposé un nouvel algorithme quantique qui résout LWE en temps 2^(n/2) sous certaines conditions, comparable à l'attaque classique avec BKZ mais avec des avantages de mémoire. Jusqu'à présent, il n'a pas été démontré qu'il surpasse les attaques classiques pour les paramètres de Kyber.

Attaques de Fourier

Les attaques quantiques basées sur la transformée de Fourier sur les réseaux (comme l'algorithme de Kuperberg pour les isogénies) n'ont pas d'analogue connu qui soit efficace pour LWE standard ou Module-LWE.

Attaques par Canaux Auxiliaires

Temporisation

L'implémentation de référence de Kyber est constante dans le temps. Cependant, des implémentations incorrectes peuvent fuiter :

Le secret s par des variations dans la multiplication NTT non constante
La valeur m dans la décompression si elle n'est pas implémentée avec soin

Mitigation : utiliser l'implémentation de référence vérifiée ou des bibliothèques auditées (liboqs, AWS-LC, BoringSSL).

Consommation Énergétique / EM

Les attaques par analyse de puissance (DPA/SPA) peuvent récupérer s si le dispositif n'a pas de contre-mesures. Kyber est particulièrement vulnérable dans les dispositifs embarqués sans blindage.

Mitigation : blinding d'exposants, randomisation des opérations NTT, découplage de signaux.

Erreurs de Calcul (Fault Attacks)

Induire des erreurs dans le calcul de NTT pendant la désencapsulation peut faire en sorte que le résultat incorrect fuite des informations sur s.

Mitigation : vérification redondante, détection d'erreurs dans NTT.

Attaques Hybrides

La NSA recommande X25519Kyber768 précisément parce que personne ne fait confiance à 100 % à Kyber seul. Une attaque qui brise Kyber mais pas X25519 serait toujours arrêtée par la couche classique, et vice versa.

Pistes de Recherche Ouvertes

Piste	Risque actuel	Notes
Algorithmes quantiques pour LWE	Faible	Aucune accélération sous-exponentielle connue
Attaques algébriques améliorées	Faible-Moyen	La structure de module pourrait être exploitable
Attaques par réseau de neurones	Faible	Les NN n'ont pas montré d'avantage sur BKZ
Canaux auxiliaires dans les implémentations réelles	Élevé	Le plus grand risque réel aujourd'hui
Défauts de paramétrisation dans les protocoles	Élevé	Kyber est sécurisé ; le protocole qui l'utilise peut-être pas

Conclusion

Kyber est sécurisé contre toute attaque connue en juillet 2026. Son plus grand risque n'est pas cryptanalytique mais implémentatoire et protocolaire : une mauvaise implémentation ou un protocole mal conçu peuvent briser la sécurité même si l'algorithme sous-jacent est solide.

Ce n'est pas différent de la cryptographie classique. La nouveauté est qu'étant plus récent, il dispose de moins d'audit cumulatif qu'AES ou SHA-3.

Références

Albrecht, M. et al. (2022). "Estimate all the LWE, NTRU schemes!" — Estimations de coût d'attaques.
Regev, O. (2023). "An Efficient Quantum Algorithm for LWE?" — Prépublication, débat ouvert.
Bernstein, D. J. & Lange, T. (2020). "Post-quantum cryptography: handling the fallout."
Xagawa, K. (2022). "Side-channel attacks on lattice-based KEMs." CHES 2022.

Attaques ConnuesAttaques Connues