Post-quantique : le BSI allemand déconseille Classic McEliece après une série d'attaques

Le 1er octobre 2026, l'Office fédéral allemand de la sécurité de l'information (BSI) a recommandé de ne plus utiliser l'algorithme post-quantique Classic McEliece pour les nouveaux développements. Depuis août, plusieurs travaux de cryptanalyse ont fortement réduit l'estimation de sa sécurité. L'agence précise qu'aucune attaque pratique n'existe à ce jour. Le signal compte pourtant : le BSI recommandait ce mécanisme d'échange de clés depuis 2020, en combinaison avec un algorithme classique.

Ce qui s'est passé depuis août

Classic McEliece est un mécanisme d'encapsulation de clés (KEM) fondé sur les codes correcteurs d'erreurs, ici des codes de Goppa binaires. Il dérive d'un système proposé en 1978 et passait pour un choix très conservateur, malgré des clés publiques très volumineuses. Le NIST américain ne l'a pas normalisé : en mars 2025, il a retenu HQC comme algorithme de secours.

Le 7 août, quatre chercheurs ont déposé un article sur l'archive ePrint de l'IACR. Il s'agit d'Ashrujit Ghoshal (IIT Madras), de Yuval Ishai (Technion et AWS), ainsi que d'Aayush Jain et Nuozhou Sun (université Carnegie Mellon). Ils y décrivent un « distingueur » en temps quasi polynomial, c'est-à-dire un algorithme capable de différencier une clé publique McEliece d'une matrice aléatoire. Selon eux, cette méthode s'applique à tous les jeux de paramètres examinés par le NIST. Ils en tirent aussi des attaques heuristiques, dont une qui récupère la clé.

D'autres chercheurs ont ensuite chiffré le coût de ces attaques de récupération de clé :

• Kirill Vedenev (CryptoPro et université fédérale du Sud, en Russie) l'estime entre 2^89,9 et 2^98,6 opérations binaires. Il dit avoir résolu plusieurs défis McEliece de taille réduite.
• Markku-Juhani Saarinen (université de Tampere) obtient des estimations conditionnelles comprises entre 2^126,77 et 2^145,22. Toutes sont sous le seuil de référence du NIST pour la catégorie de sécurité revendiquée.
• Stephen Weis (Anthropic) évalue une exécution entre 2⁸⁹ et 2⁹⁸ opérations. Il arrive à 2¹¹⁷ à 2¹²⁸ s'il compte la mémoire selon la règle du guide de sécurité de Classic McEliece. Avec la même règle, le décodage générique coûte de 2¹⁵⁹ à 2³¹⁶.

Ces chiffres sont encore très loin d'une attaque réalisable. Aucune clé de taille réelle n'a été cassée, et les estimations reposent sur des hypothèses vérifiées seulement sur de petites clés. Ces articles sont par ailleurs des prépublications, pas encore relues par des pairs. Ils placent pourtant l'algorithme sous le niveau de sécurité qu'il revendique.

Ce que dit exactement le BSI

Selon le BSI, les jeux de paramètres de sa directive technique TR-02102-1 ne permettent pas encore d'attaque pratique. L'agence juge toutefois de nouveaux progrès possibles, et même attendus. Elle recommande de préférer ML-KEM et FrodoKEM, qui ne sont pas concernés, puis HQC dès que sa norme sera publiée. Elle rappelle qu'une combinaison hybride conserve au moins la sécurité de l'algorithme classique utilisé avec Classic McEliece. Le BSI réécrira ses positions sur McEliece dans la prochaine version de la directive, prévue début 2027. Il ajoute que la migration vers le post-quantique reste tout aussi urgente.

ML-KEM (FIPS 203), l'algorithme normalisé par le NIST et le plus déployé, n'est pas touché par ces travaux.

Que faire ?

• Faire l'inventaire : vérifiez si Classic McEliece est utilisé chez vous ou chez vos fournisseurs (VPN, messageries, bibliothèques cryptographiques). Selon le site PostQuantum.com, le VPN Mullvad l'utilise par défaut sur ses applications de bureau, en hybride avec ML-KEM.
• Traiter d'abord les usages isolés : un McEliece employé sans autre algorithme à ses côtés est le cas le plus exposé.
• Ne pas retirer en urgence les déploiements hybrides : planifiez leur remplacement selon un calendrier maîtrisé.
• Pour les nouveaux projets : choisissez ML-KEM, en mode hybride.
• Soigner l'agilité cryptographique : il faut pouvoir changer d'algorithme sans tout reconstruire.