Quels standards pour la cryptographie post-quantique ?

À l’issue d’une procédure de six ans, le NIST a sélectionné quatre algorithmes à standardiser pour la cryptographie post-quantique.

Quels seront les algorithmes de référence pour la cryptographie post-quantique ? Voilà six ans, le NIST lançait une initiative dans ce domaine : un processus de type « compétition publique », à plusieurs tours. L’institut américain entendait, par cet intermédiaire, mettre à jour trois standards :

– FIPS 186-4 (signature électronique ; dernière version : 2013)
– SP 800-56A (cryptographie à logarithme discret ; 2018)
– SP 800-56B (cryptographique à factorisation d’entiers ; 2019)

Un premier appel à propositions avait été lancé fin 2016. Avec trois catégories :

– « Chiffrement à clés publiques » (création, chiffrement, déchiffrement)
– « Échange de clés » (création, encapsulation, décapsulation)
– « Signature électronique » (création, signature, vérification)

Le premier tour avait opposé 69 algorithmes. Au deuxième tour, ils n’étaient plus que 26. Puis 15 au troisième tour… dont le NIST vient d’annoncer les résultats.

Sept de ces algorithmes, « généralistes », étaient favoris pour faire l’objet d’une standardisation. Parmi eux, Classic McEliece, candidat pour succéder à RSA et EC, dans la catégorie « échange de clés ». Et récemment mis en lumière par une communication de l’OTAN dans le contexte du conflit russo-ukrainien. L’alliance avait en l’occurrence annoncé avoir finalisé l’expérimentation d’un VPN post-quantique fondé sur Classic McEliece.

Smart cards, rétrocompatibilité, coûts informatiques… Les compromis du NIST

Classic McEliece ne fait finalement pas partie des quatre algorithmes promus pour une standardisation prochaine (pour eux, le NIST va lancer le processus de publication d’un premier brouillon). Autant il affiche des performances comparables à celles des algorithmes concurrents basés sur des treillis structurés, autant la création des clés est lente et coûteuse. Non seulement du point de vue des ressources de calcul, mais aussi de la quantité de données à transmettre, la clé publique étant particulièrement longue.

Trois des algorithmes promus sont dans la catégorie « signature électronique ». Catégorie dont plusieurs des candidats en lice ont été éjectés pour des problèmes de sécurité. GeMSS et Rainbow en font partie. Pour ce dernier, une attaque a permis de récupérer une clé privée en un peu plus de deux jours avec la puissance de calcul d’un laptop.

algorithmes sélectionnés — Pour les quatre algorithmes soumis à un quatrième tour, les modifications sont acceptées jusqu’au 1^er octobre. Le NIST appelle à intégrer, entre autres « propriétés désirables », la confidentialité persistante et la résistance aux attaques par canal auxiliaire.

À l’origine, il était question de ne sélectionner qu’un algorithme entre Dilithium et FALCON. Les deux le sont finalement, le premier venant combler les limites du second sur les environnements limités en ressources, comme les smart cards.

Le NIST a fait d’autres compromis. Il a notamment tenu à ne pas sélectionner uniquement des algorithmes reposant sur une architecture en treillis. Aussi a-t-il aussi promu SHINCS⁺ comme option alternative pour la signature électronique. S’est aussi posée la question de la compatibilité de l’ensemble des algorithmes avec les applications actuelles. En particulier dans la cas où la signature et les données signées ne tiennent pas dans un seul paquet.

benchmark KEM — Kyber se montre particulièrement performant sur x86-64 avec AVX2.

benchmark KEM Arm — Saber se montre quant à lui plus efficace sur Arm (Cortex-M4).

benchmark signature NIST — Sur x86-64, la différence de coût dépend essentiellement des volumes de données transmises (et donc de la longueur des clés et du texte chiffré.

benchmark signature Arm NIST — Sur Arm, le calcul représente une plus grosse part du coût.