header-blog-NIST

Le NIST annonce les gagnants du concours post-quantique

Accueil > Observatoire & ressources > Papiers d’experts > Le NIST annonce les gagnants du concours post-quantique
Le 12/07/2022

Le NIST, organisme états-unien gouvernemental de normalisation, a annoncé le 5 juillet 2022 les gagnants de son concours, lancé en 2016, pour trouver des algorithmes de cryptographie résistant aux calculateurs quantiques. Les vainqueurs sont CRYSTALS-Kyber, pour le chiffrement, et CRYSTALS-Dilithium, pour les signatures. Quelles conséquences pratiques attendre de cette annonce, pour le DNS et pour l’Internet en général ?

D’abord, un petit mot sur la cryptographie ; cette technique est absolument indispensable à la sécurité de l’Internet, à la fois parce qu’elle assure la confidentialité des communications, en chiffrant celles-ci, et parce qu’elle permet de garantir l’authenticité des messages, grâce à la signature électronique. La cryptographie repose sur la mathématique, via des opérations qui sont faciles à exécuter lorsqu’on connaît un certain secret, la clé, mais qui sont incroyablement difficiles à faire si on ignore ce secret. En théorie, l’opération peut toujours être effectuée en essayant d’innombrables possibilités, ce qu’on nomme la force brute, mais cela prendrait un temps qui, par rapport à la durée de nos vies, est infini.

La cryptographie, comme toute technique de sécurité, n’est pas parfaite. La plupart des attaques réussies contre des systèmes cryptographiques ne portent pas sur les algorithmes eux-même mais sur leur mise en œuvre, par exemple via une bogue dans les programmes. Mais on peut aussi s’inquiéter de faiblesses dans les algorithmes et la cryptanalyse, l’art d’attaquer les algorithmes cryptographiques, « casse » régulièrement des algorithmes. Toutefois, les « grands » algorithmes de cryptographie comme RSA ou AES ont toujours résisté, parfois en augmentant la taille de leur clé pour augmenter la marge de sécurité. La difficulté progresse en effet beaucoup plus vite que la taille de la clé, un doublement de celle-ci provoque bien plus qu’un doublement de la difficulté.

Mais cela, c’est pour des programmes de cryptanalyse tournant sur des ordinateurs classiques, comme celui que vous utilisez en ce moment pour lire cet article. Or, depuis quelques années, on commence à faire fonctionner des calculateurs quantiques, qui, profitant des propriétés très surprenantes de la physique quantique, peuvent résoudre certains problèmes très difficiles en un temps bien plus court et, surtout, qui n’augmente pas autant avec la taille de la clé. Le jour où on aura des calculateurs quantiques utilisables, des algorithmes de cryptographie comme RSA deviendront inutiles. Les médias ont souvent fait des articles sensationnalistes sur ce thème, parlant par exemple d’« apocalypse quantique ».

Mais quand aura-t-on de tels calculateurs ? La réponse n’est pas facile à donner et les prévisions vont de « moins de dix ans » à « cinquante ans minimum ». C’est que leur mise au point demande la résolution de problèmes de physique et d’ingénierie extrêmement complexes. Non seulement les prototypes actuels de calculateurs quantiques sont très loin des capacités requises, mais il est sans doute vain d’essayer de prédire quand on disposera de tels calculateurs.

Faut-il donc ne rien faire en attendant ? Non, car la mise au point et le déploiement des solutions nécessitera sans doute du temps, souvent de nombreuses années, et c’est maintenant qu’il faut commencer. D’où le travail de nombreuses équipes de recherche dans le monde sur les algorithmes post-quantiques1. Il s’agit d’algorithmes de cryptographie pour lesquels on ne connaît pas de solutions de cryptanalyse, même quand on a un calculateur quantique à sa disposition. Vu le temps de mise au point, d’analyse, puis de mise en place sur le terrain des algorithmes de cryptographie, il n’est pas exagéré de commencer le travail tout de suite.

C’est pour cela que le NIST, National Institute of Standards and Technology, qui intervient dans la normalisation technique sur de nombreux domaines, a lancé en 2016 un concours pour sélectionner les algorithmes de cryptographie post-quantiques qui seront normalisés et seront donc probablement préférés par de nombreux acteurs de l’Internet. Il existe en effet de très nombreux algorithmes candidats (l’imagination des mathématicien·nes est sans limite) et il faut choisir avec soin. Un algorithme post-quantique qui serait « cassé » au bout de quelques années par la cryptanalyse ne serait pas un progrès. D’où le choix d’un concours, où de nombreuses équipes ont participé (dont plusieurs françaises, voyez cet interview d’une mathématicienne dans le journal du CNRS), soumettant des projets très variés. Les concurrents et des chercheurs ne participant pas au concours se lancent ensuite dans l’analyse des failles des propositions, et celles qui ont des faiblesses irrémédiables sont retirées, au fur et à mesure des différents cycles d’examens. Le dernier cycle ne laissait plus en lice que quatre concurrents pour le chiffrement2 et trois pour les signatures.

Les vainqueurs, annoncés le 5 juillet, sont donc Kyber pour chiffrer les données et Dilithium pour les signer. Deux autres algorithmes de signature seront également normalisés, Falcon et Sphincs+, et plusieurs autres algorithmes continuent à être examinés pour une éventuelle normalisation3. Vont-ils être utilisés par votre ordinateur dans les prochaines semaines ? Non, car il reste des étapes à franchir. Le NIST, une fois cette décision de principe prise, doit désormais rédiger et approuver les normes techniques. Les programmeur·ses doivent ensuite mettre en œuvre ces normes, ce qui n’est pas forcément aisé (dans ce domaine, une erreur de programmation a de sérieuses conséquences). C’est en raison de ces délais qu’il fallait commencer le travail sur les algorithmes post-quantiques bien avant que les calculateurs ne soient disponibles.

Dans le cas de l’Internet, il va falloir inclure les nouveaux algorithmes post-quantiques dans les systèmes de cryptographie utilisés, comme TLS (Transport Layer Security, qui est entre autre derrière la sécurisation du Web avec HTTPS) ou comme DNSSEC, qui permet de s’assurer que les noms de domaine donnent accès à de l’information authentique. Ce sera notamment la tâche de l’IETF, organisme de normalisation auquel l’Afnic participe activement. Ensuite, la plupart des acteurs de l’Internet ne programment pas eux-mêmes les bibliothèques logicielles de cryptographie (ce qui serait très imprudent) et devront donc attendre que des nouvelles versions de ces bibliothèques, incluant les algorithmes post-quantiques, soient disponibles. Ce n’est donc pas pour aujourd’hui, mais il est important de préparer le futur en y travaillant dès maintenant.

Les algorithmes sélectionnés par le NIST seront-ils adoptés universellement ? Ce n’est pas obligatoire l’Internet est « sans permission » et le NIST n’a pas d’autorité pour imposer son choix, à part à l’administration de son pays. La crédibilité du NIST a sérieusement souffert des révélations qui avaient montré qu’il avait délibérément affaibli un algorithme utilisé en cryptographie, le Dual EC DRBG, suite aux exigences d’un service d’espionnage états-unien. C’est d’ailleurs en partie en raison de cette affaire que le NIST a choisi de faire un concours public, où toutes les étapes se font au grand jour, pour limiter le risque de manœuvres cachées. Compte-tenu de l’importance d’utiliser des algorithmes standardisés, de la difficulté qu’il y a à évaluer un algorithme de cryptographie soi-même, et du fait qu’il ne semble pas y avoir d’autre effort de normalisation, il est probable que les « gagnants » de ce concours seront largement utilisés.

Pour des détails sur les calculateurs quantiques et sur la cryptographie post-quantique, je recommande le document de l’ANSSI « sur la migration vers la cryptographie post-quantique ». Ces algorithmes post-quantiques avaient été longuement détaillés lors de la JCSA (Journée du Conseil Scientifique de l’Afnic) en 2019. Sur le quantique en général, on notera également en 2019 le rapport parlementaire de la députée Paula Forteza. Enfin, en anglais cette fois, l’ICANN a publié en 2022 une bonne étude, discutant notamment des conséquences futures du post-quantique sur DNSSEC.

 


1- Le sigle en français n’étant pas forcément très heureux, on parle parfois d’algorithmes AP (Après Quantique), RQ (Résistant au Quantique) ou COQ (Cryptographie Outre-Quantique).

2 – Ou, en toute rigueur, pour l’échange des clés qui seront utilisées pour le chiffrement.

3 – Il y a plusieurs raisons à ces choix multiples, le fait que les algorithmes ont des propriétés différentes et complémentaires, et aussi le désir de ne pas mettre tous les œufs dans le même panier.