Pourquoi il faut chercher maintenant les algorithmes de cryptographie résistants aux calculateurs quantiques de demain

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.

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êmes mais sur leur mise en oeuvre, 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é.

Cela vaut pour des programmes de cryptanalyse tournant sur des ordinateurs classiques.
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. D'où des appels sensationnalistes sur le thème d'« apocalypse quantique ».

Quand disposera-t-on de tels calculateurs ? Les prévisions vont de « moins de dix ans » à « cinquante ans minimum ». En effet, leur mise au point demande la résolution de problèmes de physique et d'ingénierie extrêmement complexes.

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-quantiques^1. 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.

Ainsi, il existe 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 participent (dont plusieurs françaises), soumettant des projets très variés.

Les concurrents et des chercheurs non participant se lancent ensuite dans l'analyse des failles des propositions, et celles qui ont des faiblesses irrémédiables sont retirées, après plusieurs cycles d'examens.

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 normalisation².

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 oeuvre 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 autres 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.

Les algorithmes sélectionnés par le NIST seront-ils adoptés universellement ? 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 manoeuvres cachées.

Compte-tenu de l'importance d'utiliser des algorithmes standardisés, de la difficulté à é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.

¹ 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).

² 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 oeufs dans le même panier.

Stéphane Bortzmeyer, - Afnic.