Ce mardi 5 juillet 2022, l'organisme de normalisation étatsunien
NIST a annoncé qu'il avait choisi les
algorithmes de cryptographie
post-quantiques qu'il allait maintenant
normaliser. Ce sont Kyber pour
l'échange de clés et Dilithium
pour les signatures.
L'annonce était prévue plus tôt mais a été retardée, selon
certains par des problèmes liés aux nombreux
brevets qui grèvent ces algorithmes
(l'annonce du NIST prévoit des négociations), selon d'autres par la
difficulté qu'avait la NSA à
attaquer les algorithmes proposés . Il est difficile de le
savoir puisque le NIST, même s'il avait fait un effort
d'ouverture à cette occasion, reste assez opaque. En tout cas,
désormais, c'est fait.
Pour comprendre l'importance de cette annonce, il faut revenir
sur celle de la cryptographie. On sait que
cet ensemble de techniques est absolument indispensable à la
sécurité de l'utilisateur sur l'Internet. Ne croyez pas les
politiciens ou les éditorialistes qui vont vous expliquer que si
vous ne faites rien de mal, vous n'avez rien à cacher et pas besoin
de cryptographie. Cet argument a été réfuté d'innombrables fois
depuis des années mais continue à être
parfois utilisé pour pousser les citoyen·nes à communiquer en
public. Ignorez-le, et chiffrez l'intégralité de vos communications,
c'est indispensable dans le monde d'aujourd'hui.
Mais aucune technique de sécurité n'est parfaite, que cela soit
la cryptographie ou une autre. Il y a des questions non-techniques mais
aussi des limites techniques de la cryptographie. Notamment, dans
l'ordre d'importance décroissante :
- La cryptographie protège contre des tiers qui écoutent et/ou
modifient les communications, mais pas contre le
destinataire.
- Les logiciels de cryptographie, comme les autres, ont des
bogues.
- Et les algorithmes utilisés en cryptographie peuvent ne pas
être aussi solides qu'on le pense ; la
cryptanalyse peut parfois en venir à
bout. (Voyez par exemple le RFC 7465.)
Ce dernier risque est le plus spectaculaire et celui que les
geeks préfèrent mentionner. Mais, en pratique, il
est sans doute le moins sérieux. Vous avez bien plus de chances de
voir vos secrets percés suite à une imprudence ou une maladresse de
votre correspondant·e ou de vous-même que suite à une découverte
mathématique fondamentale résolvant le problème du
logarithme discret et cassant ainsi ECDSA. Certes, un problème mathématique comme
la décomposition en facteurs premiers, qui
est à la base de RSA, reste un problème ouvert et on n'a
jamais démontré qu'il était insoluble. Néanmoins, vu le nombre de
gens qui l'ont attaqué depuis des dizaines d'années, on peut être
raisonnablement confiant : le problème est manifestement très
difficile, et RSA reste donc sûr. La seule méthode connue pour
attaquer des algorithmes comme ECDSA ou RSA reste donc la force
brute, l'examen systématique de toutes les possibilités, ce qui
prend quelques milliards d'années avec les machines existantes. (Je
simplifie : on dispose en fait d'algorithmes meilleurs que la pure
force brute mais ils ne font pas de miracles non plus.) En
outre, la difficulté augmente exponentiellement avec la taille de la
clé, et un progrès dans les processeurs ou bien certaines optimisations des
programmes de cryptanalyse peuvent
facilement être annulés en agrandissant la clé.
Mais les calculateurs quantiques
pourraient changer les choses. Je ne vais pas détailler ici le
fonctionnement de ces machines. Je dirais juste que, reposant
directement sur la quantique, ils permettent
de faire tourner des algorithmes radicalement différents (et pas
évidents du tout à programmer !) de ceux qui sont utilisés
actuellement, sur les ordinateurs classiques. Ainsi,
l'algorithme de Shor permet de décomposer un
nombre en ses facteurs premiers, en un temps linéaire, et donc de
trouver une clé privée RSA à partir de la clé publique, tâche qui
était impossible aux ordinateurs classiques. L'algorithme de Shor ne
tournant que sur des calculateurs quantiques, si on dispose d'un tel
calculateur, on a cassé RSA (et, avec un algorithme proche, ECDSA et
les autres algorithmes à courbes
elliptiques). Ce serait une catastrophe pour la sécurité
de l'Internet, puisque les communications confidentielles pourraient
toutes être décryptées, et les signatures toutes imitées. (Notez que
cela serait pareil, même sans calculateur quantique, si un·e
mathématicien·ne génial·e découvrait demain un moyen simple de
décomposer un nombre en facteurs premiers. Comme indiqué plus haut,
c'est peu probable mais pas impossible.)
Mais attention, le « si on dispose d'un calculateur quantique »
est un gros « si ». De même qu'Euclide
avait développé des algorithmes et qu'Ada
Lovelace avait écrit des programmes longtemps avant
qu'un ordinateur ne soit disponible pour les exécuter,
Shor a développé son algorithme sans avoir de
calculateur quantique. On a progressé depuis et des
calculateurs quantiques existent, et on peut
faire tourner l'algorithme de Shor dessus. Le problème
est qu'ils sont très expérimentaux, très peu existent dans le monde
et leurs plus grands exploits sont très loin de ce qui serait
nécessaire pour casser les clés d'aujourd'hui. Les optimistes
parient que ce n'est qu'une question de temps et que, dans quelques
années, les calculateurs quantiques (dont les enthousiastes
prédisent depuis des années qu'ils sont presque au point)
s'attaqueront facilement à nos algorithmes cryptographiques. Les
pessimistes font remarquer que les difficultés pratiques qui se
présentent face aux calculateurs quantiques sont colossales et que
les résoudre n'est pas un simple travail d'ingéniérie prévisible
mais est souvent plus proche de la recherche fondamentale et de ses
incertitudes. Bref, il n'y a pas actuellement de consensus sur le
temps dont nous disposons encore face à la « menace quantique ».
Comme il faut s'y prendre à l'avance pour développer, tester et
déployer de nouveaux algorithmes dits post-quantiques, les
cryptographes n'ont pas attendu de voir les
calculateurs quantiques en vente chez
Darty pour réagir. Le travail sur des algorithmes
post-quantiques a commencé il y a longtemps. Ces nouveaux
algorithmes doivent résister aux calculateurs quantiques. Plus
exactement, il faut qu'on ne connaisse pas d'algorithme quantique
pour les attaquer. Mais il faut aussi qu'ils résistent à la
cryptanalyse classique (voir par exemple cette attaque contre Rainbow,
un des finalistes du concours). Et il faut aussi qu'ils soient
réalistes en performance, en taille
de clés, etc. Plusieurs candidats prometteurs ont été
développés, et les cryptanalystes se sont déjà fait les dents à
essayer de les casser.
Sur l'Internet, mais aussi en général dans
le monde numérique, la normalisation est
essentielle. Avoir des protocoles et des
algorithmes, notamment de cryptographie,
communs, permet l'interopérabilité, qui
garantit liberté de choix, et bon fonctionnement du réseau. Pour
qu'Alice puisse envoyer un message à Bob, il faut bien qu'Alice
chiffre avec un algorithme que Bob puisse déchiffrer. Le rôle des
organisations de normalisation est donc
crucial. C'est pour cela que le NIST étatsunien a lancé en
2016 un grand concours pour choisi le
meilleur algorithme à normaliser. Plutôt que de faire travailler
ensemble des cryptologues à développer en commun ce meilleur
algorithme, ce qui risquait d'amener à un compromis qui ne
satisferait personne, le NIST a choisi le concours : de nombreuses
équipes proposent leur algorithme, chacun essaie de casser celui des
concurrents et que le meilleur gagne. C'est ce concours qui vient de
franchir une étape décisive, avec l'annonce du choix de :
- Kyber pour
l'échange de clés (aussi nommé KEM pour key encapsulation
mechanism cf. RFC 9180), préalable au chiffrement
effectué ensuite avec un algorithme
symétrique classique comme AES. Kyber utilise les
réseaux
euclidiens.
- Dilithium
(oui, ça vient de Star
Trek) pour les signatures. Dilithium utilise également les
réseaux euclidiens.
- Deux autres algorithmes de signature ont été également
retenus, pour des usages spécifiques, Sphincs+ et Falcon, et
plusieurs autres algorithmes seront examinés pour fournir un
algorithme de secours, au cas où des problèmes apparaissent avec
ceux sélectionnés (rappelons que, contrairement à, par exemple,
RSA, ils n'ont pas bénéficié d'années de recherches de
failles). Sphincs+ est le seul à ne pas utiliser les réseaux
euclidiens, mais des fonctions de condensation.
Maintenant que ces algorithmes ont été choisis, verra-t-on dès
demain TLS,
SSH, DNSSEC et
les autres utiliser des algorithmes post-quantiques ? Non, car il
reste plusieurs étapes à franchir. D'abord, le NIST doit finir le
travail de normalisation : il faut spécifier rigoureusement
l'algorithme et publier la spécification officielle. (Cela a été
fait deux ans après, le 14 août 2024, avec la parution de FIPS-203, FIPS-204 et
FIPS-205.) Cela implique,
comme le note l'annonce officielle, une négociation réussie sur les
brevets qui plombent le champ de la
cryptographie post-quantique (cf. par exemple le
problème avec le CNRS et l'accord
ultérieur). Ensuite, la plupart des utilisations
de la cryptographie se fait au sein d'un protocole de cryptographie
comme TLS. Les protocoles sérieux disposent tous de la propriété
d'agilité (RFC 7696), ce qui veut dire qu'ils
ne sont pas lié à un algorithme de cryptographie particulier. Mais
il faudra quand même spécifier l'utilisation du nouvel algorithme pour
ce protocole (par exemple, pour DNSSEC, il faudra l'ajouter au
registre IANA, ce qui nécessitera la publication d'un
RFC). (Cet
article donne une première idée du travail à faire.) Ensuite,
les programmeur·ses devront programmer ces algorithmes
post-quantiques (une tâche à effectuer soigneusement ; on a vu que
les bogues sont à l'origine de bien des problèmes de
cryptographie). Même s'il existe déjà plusieurs mises en œuvre de
ces algorithmes, des programmes dignes d'être utilisés en production
sont une autre affaire. Et il faudra ensuite déployer ces programmes
dans le monde réel.
Pour la partie de normalisation dans les protocoles
TCP/IP, ce qui relève de l'IETF, on peut
noter que quelques RFC parlent déjà de post-quantique. C'est le
cas par exemple des RFC 8784, RFC 8696, RFC 8773 et RFC 8784, mais c'est exagéré,
ils décrivent simplement des clés de cryptographie symétrique
pré-partagées. Plus sérieusement, le RFC 8032
discute les risques que les calculateurs quantiques posent à
l'algorithme EdDSA, et le RFC 8391 le fait pour XMSS, tandis que le RFC 9180
(section 9.1.3) a une vision plus générale. Même discussion pour les
RFC 8240 et RFC 8576,
dans le contexte de l'Internet
des objets. Le RFC 9021 doit être un des rares
qui repose déjà sur un algorithme post-quantique mais on voit que la
prise de conscience était ancienne.
Il faudra donc compter de nombreuses années avant d'avoir les
algorithmes post-quantiques massivement déployés. C'est d'ailleurs
pour cela qu'il faut commencer tout de suite le processus, alors
même que la menace des calculateurs quantiques est lointaine. (On
peut aussi se rappeler que la cryptographie sert parfois à protéger
des secrets de longue durée. Si les fichiers que vous chiffrez
actuellement seront toujours sensibles dans trente ans, dites-vous
bien que les calculateurs quantiques capables de casser les clés
utilisées seront peut-être une réalité dans trente ans.)
Le mot « quantique » est parfois mis à toutes les sauces. Il faut
notamment signaler que les questions discutées ici n'ont rien à voir
avec ce qu'on nomme parfois la « cryptographie quantique » (et qui
serait mieux appelée « distribution quantique de
clés »), une technique dont l'intérêt n'est pas du tout
évident (voir aussi le démontage de cette
idée par Dan Bernstein et l'avis
de l'ANSSI, en anglais seulement). De même, la question de la
cryptographie post-quantique n'a pas de lien direct avec les projets
d'« Internet quantique » (où les routeurs sont quantiques), sur lesquels
travaille entre autres l'IRTF dans son groupe QIRG.
Sinon, question mises en œuvre, Kyber et Dilithium sont dans
la bibliothèque de
Cloudflare (écrite en Go). Elle n'a apparemment aucune
documentation et son utilisation semble difficile. (La bibliothèque de
Microsoft avait fait le choix d'autres algorithmes.)
Quelques bonnes lectures sur cette question des algorithmes de
cryptographie post-quantiques :
Et merci à Manuel Pégourié-Gonnard et Damien Stehlé pour leur
relecture attentive. Évidemment, les erreurs restantes sont de moi.
