Introduction
Le Centre canadien pour la cybersécurité (Centre pour la cybersécurité), qui relève du Centre de la sécurité des télécommunications, est l’autorité de cybersécurité du Canada. Le Centre pour la cybersécurité est un partenaire du National Institute of Standards and Technology (NIST) pour ce qui est du Programme de validation des modules cryptographiques (PVMC). Il recommande l’utilisation des normes cryptographiques NIST mentionnées dans ses documents d’orientation, comme l’ITSP.40.111. Les scientifiques en cryptographie du Centre pour la cybersécurité procèdent à l’évaluation des derniers finalistes et des autres candidats à la cryptographie post-quantique (PQC pour Post-Quantum Cryptography) afin d’étayer le processus de sélection et de s’assurer que les candidats sélectionnés aux fins de normalisation continuent de fournir une protection cryptographique à l’information et aux systèmes qui seront importants pour le Canada et les Canadiens après l’arrivée des ordinateurs quantiques. Les opinions exprimées dans la présente sont strictement celles du Centre pour la cybersécurité.
Contexte
En 1994, Peter Shor a inventé un algorithme capable de résoudre efficacement les problèmes mathématiques à la base de la cryptographie asymétrique moderne lorsqu’il est exécuté sur un grand ordinateur quantique. Bien que ces grands ordinateurs quantiques soient encore inexistants, plusieurs chercheurs croient qu’ils pourraient devenir réalité au cours des prochaines décennies. Cette constatation est à l’origine des efforts considérables qui sont consacrés à la recherche en cryptographie post-quantique PQC, un domaine visant à assurer la sécurité du chiffrement après l’arrivée des grands ordinateurs quantiques.
Dans cette optique, le National Institute of Standards and Technology NIST des États-Unis a lancé une nouvelle initiative PQC en 2016 dans le but de normaliser un ou plusieurs des algorithmes cryptographiques post-quantiques (le processus de normalisation de la PQC du NIST, en anglais seulement). Les 2 types d’algorithmes envisagés sont : les modèles de chiffrement à clé publique (utilisés pour chiffrer les messages ou établir des clés secrètes partagées) et les modèles de signature (utilisés pour signer numériquement les messages).
Novembre 2017 était la date limite pour l’envoi des soumissions initiales au processus de normalisation et un mois plus tard, en décembre, le NIST annonçait avoir reçu 69 soumissions valides. Ces dernières provenaient de chercheurs dans plus de 25 pays et faisaient appel à des techniques tirées de plusieurs familles mathématiques différentes, dont les réseaux euclidiens, les codes de correction d’erreurs, les équations à plusieurs variables, les fonctions de hachage et les courbes elliptiques. C’est ce qui a donné le coup d’envoi à la première ronde d’évaluation. En janvier 2019, la deuxième ronde ne comptait plus que 26 candidats et la troisième ronde a commencé officiellement en juillet 2020.
La troisième ronde compte deux types de candidats : 7 finalistes et 8 substituts. Le NIST s’attend à ce qu’un finaliste ou plus soit choisi et normalisé à la fin de la troisième ronde. Les substituts ont été sélectionnés pour un examen plus approfondi en prévision que certains de ces algorithmes puissent être normalisés après une quatrième ronde d’évaluation.
Bien que la sécurité soit toujours le critère le plus important, les exigences relatives à la vitesse et la bande passante de l’algorithme demeurent des facteurs essentiels au processus de normalisation. Au début de la troisième ronde, le NIST a indiqué que la cryptographie basée sur les réseaux euclidiens était la famille la plus prometteuse pour un usage général. Cinq des sept finalistes étaient basés sur les réseaux euclidiens et le NIST voudrait normaliser (au maximum) un algorithme de chiffrement basé sur les réseaux euclidiens et (au maximum) un algorithme de signature basé sur les réseaux euclidiens à la fin de la troisième ronde. Les 2 autres finalistes, le premier étant basé sur la théorie des codes et le deuxième étant basé sur les polynômes multivariés, ne sont pas adaptés à un usage général puisqu’ils exigent une bande passante importante. Ces autres finalistes (et leurs substituts) offrent toutefois des avantages qui leur sont propres. La prochaine section proposera une brève description de la famille mathématique à laquelle les candidats finalistes et substituts appartiennent, et traitera de leurs avantages et de leurs inconvénients.
Familles mathématiques
Réseaux euclidiens
La sécurité de la cryptographie basée sur les réseaux euclidiens repose sur des problèmes mathématiques liés à ces derniers. Il s’agit d’un domaine de recherche actif, un fait souvent attribué à la célèbre analyse de complexité en cas « pire à moyen » élaborée par Ajtai en 1996. Vingt-six des 69 soumissions initiales étaient basées sur les réseaux, tout comme 5 des 7 finalistes. À première vue, plusieurs des techniques employées dans les soumissions transmises dans le cadre du processus peuvent ne pas ressembler à des problèmes liés aux réseaux, mais leurs preuves de sécurité et leurs attaques les mieux connues reposent toutefois sur la complexité des problèmes de réseaux. Les cinq finalistes font appel à des variantes du problème NTRU ou du problème d’apprentissage avec erreurs (LWE pour Learning with errors), et offrent un rendement avantageux pour ce qui est des exigences en matière de vitesse et de bande passante.
Le problème NTRU a été introduit il y a plus de 20 ans et est basé sur la factorisation d’une certaine fonction polynomiale en un produit composé de 2 polynômes ayant des propriétés spéciales. Les attaques les mieux connues contre le problème NTRU sont basées sur les réseaux et 2 finalistes de la troisième ronde utilisent le problème NTRU.
À l’instar de la cryptographie basée sur la théorie des codes décrite à la section suivante, le problème LWE est une modification d’un problème d’algèbre linéaire simple dont la résolution a été complexifiée en y ajoutant intentionnellement des erreurs. Le problème LWE initial exige de très grandes clés publiques et est plus lent que les finalistes basés sur les réseaux que le NIST a pris en considération. Les finalistes basés sur le LWE utilisent les modifications apportées au LWE pour permettre la création de clés plus petites et accélérer le traitement.
Parmi les candidats restants, les approches basées sur les réseaux sont les seules à offrir des fonctions de chiffrement et de signature, et les plus rapides dans ces deux catégories. Bien que les propositions spécialisées puissent fournir un meilleur rendement, les approches basées sur les réseaux proposent un rendement avantageux pour ce qui est des exigences matière de bande passante, ce qui en fait d’excellents candidats pour un usage général.
Codes de correction d’erreurs
La cryptographie basée sur les codes repose sur la théorie des codes de correction d’erreurs. On utilise traditionnellement les codes de correction d’erreurs en théorie de l’information pour résoudre des problèmes non liés à la cryptographie : deux parties veulent communiquer par l’intermédiaire d’un canal bruité, ce qui veut dire que les messages envoyés comportent des erreurs lorsqu’ils atteignent leur destination. On utilise les codes de correction d’erreurs pour supprimer l’erreur et récupérer le message d’origine. Dans la plupart des solutions cryptographiques basées sur les codes, le concept de clé correspond aux erreurs qui sont insérées intentionnellement de manière à ne pouvoir être identifiées ou supprimées que par le détenteur de la clé secrète. Sans cette dernière, il faut résoudre le problème complexe de décoder le mot de code comportant les erreurs à partir d’un code linéaire en apparence aléatoire.
La cryptographie basée sur les codes a d’abord été proposée il y a plus de 40 ans sous la forme du modèle de chiffrement de McEliece. Dix-sept modèles de chiffrement basés sur les codes et 2 signatures basées sur les codes avaient été soumis dans le cadre de la demande initiale de candidats PQC du NIST. De ce nombre, 3 modèles de chiffrement étaient toujours parmi les candidats à la troisième ronde : 1 finaliste et 2 substituts. Le finaliste est un modèle de McEliece qui utilise des codes de Goppa, tandis que les modèles substituts font appel à des familles de codes différentes de celles utilisées par le modèle de McEliece traditionnel : le premier se sert de codes de contrôle de parité à densité modérée (MDPC pour Moderate Density Parity Check) quasi cyclique et le second, de codes quasi cycliques aléatoires.
Malheureusement, les clés publiques du modèle de McEliece d’origine sont extrêmement volumineuses, un problème qui demeure encore aujourd’hui un des principaux inconvénients des systèmes de chiffrement basés sur les codes. Des variantes de la famille de codes sous-jacente ont souvent été proposées pour corriger la situation, mais dans les meilleurs scénarios, les clés publiques des systèmes basés sur les codes sont plus grandes que celles employées par les systèmes finalistes basés sur les réseaux euclidiens. Les principaux avantages du système de McEliece sont le niveau de sécurité que lui confère sa maturité, les textes chiffrés très petits (plus petits que les autres modèles) qu’il emploie et la vitesse à laquelle il est en mesure de procéder à l’encapsulation et à la décapsulation (très rapide).
Systèmes d’équations quadratiques multivariées
Les modèles quadratiques multivariés (MVQ pour Multivariate Quadratic) sont basés sur la résolution de systèmes polynomiaux du deuxième degré ayant 2 variables ou plus dans un corps fini. Un modèle MVQ typique construit un système de manière à ce que seul le détenteur de la clé secrète puisse trouver la solution. Pour ce faire, on doit construire les équations à partir d’une structure spéciale et les masquer de manière à sembler aléatoires pour un attaquant. Lors de la première ronde du processus de normalisation du NIST, 7 modèles de signatures MVQ et 2 modèles de chiffrement MVQ ont été soumis. À la troisième ronde, on comptait 2 signatures MVQ : un finaliste et un substitut.
Un avantage des modèles de signature MVQ est qu’ils génèrent des signatures très petites (dans certains cas, plus petites que les signatures RSA que l’on utilise aujourd’hui). Dans le cas du finaliste, ces petites signatures accélèrent le processus de signature. Des progrès ont été réalisés lors d’une recherche récente sur la théorie de la sécurité relative aux modèles MVQ, ce qui a donné lieu à des changements au niveau des paramètres pour le finaliste de la troisième ronde et a soulevé des questions sur la stabilité des problèmes MVQ complexes. La taille des clés publiques (et parfois privées) des modèles de signature MVQ est l’un des inconvénients de cette approche, ce qui fait en sorte qu’elle ne convient pas à un usage général.
Fonctions de hachage
Les signatures basées sur le hachage (HBS pour Hash-Based Signature) reposent uniquement sur la sécurité d’une fonction de hachage cryptographique, à savoir une fonction irréversible qui utilise une chaîne d’une longueur quelconque pour générer une sortie à longueur fixe. On estime que les tailles de sortie plus grandes sont protégées contre les ordinateurs quantiques. Selon ce concept, une HBS est une collection de plusieurs modèles de signature uniques (OTS pour One-Time Signature), ce qui fait en sorte que chaque OTS ne peut signer qu’un seul message. Elle a recours à une structure de données que l’on appelle une arborescence pour combiner efficacement les nombreuses OTS. Une HBS choisit une seule OTS dans sa collection et l’utilise pour signer le message. L’enjeu majeur est que la HBS ne doit jamais sélectionner la même OTS à plus d’une reprise sans quoi la sécurité sera compromise. Les modèles HBS les plus efficaces sont avec état, ce qui signifie que la HBS doit savoir quelles OTS ont déjà été utilisées. Ce processus exige une procédure de gestion des états qui pourrait ne pas être possible dans certaines applications. Le NIST a publié ses recommandations sur les signatures basées sur le hachage avec état.
Deux modèles HBS sans état ont été soumis lors de la demande de candidature PQC initiale du NIST, dont une qui est toujours prise en compte comme modèle substitut à la troisième ronde. L’idée est d’utiliser une arborescence très vaste et de choisir la OTS de façon aléatoire. Si l’arborescence est suffisamment large, il y a très peu de risque qu’une OTS soit réutilisée. Bien que plusieurs améliorations aient été apportées aux modèles HBS sans état, les signatures sont volumineuses et le rendement est lent comparativement aux autres candidats de signature PQC. Néanmoins, les signatures basées sur le hachage offrent un degré élevé de confiance envers leur sécurité, ce qui explique pourquoi elles sont toujours sous considération.
Isogénies des courbes elliptiques
La cryptographie basée sur les isogénies fait appel à des transformations entre les courbes elliptiques pour construire des cryptosystèmes à clé publique. On sait que les courbes elliptiques employées par les cryptosystèmes à clé publique sont vulnérables aux ordinateurs quantiques. Cela dit, comme les modèles basés sur les isogénies n’utilisent pas les mêmes opérations arithmétiques, on estime qu’ils pourront résister aux mécanismes de cryptographie post-quantique. La seule soumission basée sur les isogénies ayant été reçue lors du processus de normalisation du NIST est le modèle de chiffrement qui est toujours sous considération à la troisième ronde en tant que candidat substitut. L’intérêt envers les clés publiques demeure, car elles sont plus petites que celles des autres candidats en lice et la taille des textes chiffrés est également très petite. Bien que ce modèle ait fait l’objet de plusieurs optimisations, il est beaucoup plus lent que ses concurrents. Comme pour les autres candidats substituts, le NIST a suggéré que la cryptographie basée sur les isogénies pourrait tirer avantage des recherches plus poussées qui seront menées au cours de la troisième ronde.
Autres
Certaines des 69 soumissions initiales n’appartenaient pas à aucune des catégories précédentes. Parmi ces soumissions, on retrouve des codes à métrique de rang (une variante de la théorie des codes), des marches aléatoires et des tresses. Seul le modèle de signature qui intègre la cryptographie symétrique et ce qu’on appelle une « preuve à divulgation nulle de connaissance » demeure un modèle substitut à la troisième ronde. Ce modèle utilise une clé publique de petite taille, mais il faut plus de temps pour procéder à la signature et les signatures sont plus volumineuses. Comme pour les candidats basés sur le hachage, ce modèle offre une sécurité qui repose exclusivement sur la cryptographie symétrique, ce qui constitue l’un de ses principaux avantages. Étant basé sur un concept relativement nouveau, il n’a pas fait l’objet d’une étude approfondie comparativement aux modèles appartenant aux autres familles. Pour cette raison, des améliorations importantes ont pu être relevées au cours des deux premières rondes et le NIST estime que cette tendance pourrait se répéter au cours des rondes subséquentes. Cette nouveauté a toutefois pour inconvénient de faire en sorte qu’il faudra plus de temps avant que la communauté cryptographique ait confiance dans le niveau de sécurité qu’il confère.
Conclusion
On s’attend à ce que la troisième ronde d’évaluation des candidats PQC dure de 12 à 18 mois, et que le NIST sélectionne un petit nombre de candidats parmi les finalistes afin de procéder à la normalisation d’ici le début de 2022 et d’en venir à une norme finale d’ici 2024. Le NIST envisage également d’effectuer une quatrième ronde d’évaluation pour les candidats ou finalistes substituts qui nécessitent une évaluation plus approfondie, ce qui pourrait se traduire par de plus amples normes à une date ultérieure. Alors que les réseaux euclidiens semblent être les mieux adaptés à un usage général, la communauté cryptographique continuera d’examiner les autres familles en raison des avantages qu’elles confèrent pour des cas d’utilisation en particulier et de la diversité qu’elles offrent advenant une sophistication des attaques visant les réseaux euclidiens. Compte tenu du nombre limité de candidats toujours en lice à la troisième ronde, le NIST s’attend à ce que la communauté de recherche en cryptographie soit en mesure de procéder à un examen plus approfondi de chaque candidat dans des domaines tels que la résistance des canaux auxiliaires, les données de performance dans les protocoles Internet et les données de performance dans le déploiement matériel, ainsi qu’à une analyse rigoureuse et continue de la sécurité.
Pour plus de détails sur la normalisation de la PQC du NIST, veuillez visiter le site Web officiel du NIST sur la cryptographie post-quantique (en anglais seulement) ou consulter le rapport du NIST sur l’avancement de la deuxième ronde (NISTIR 8309 en anglais seulement), 2 sources qui ont été largement consultées lors de la rédaction de ce blogue. Le Centre pour la cybersécurité recommande fortement aux consommateurs d’attendre l’achèvement des normes liées aux modèles de chiffrement et de signature à clé publique post-quantiques avant d’utiliser les candidats PQC pour protéger leurs données ou leurs systèmes. Pour l’heure, ce qui importe est de planifier une migration cryptographique en dressant la liste des systèmes qu’il conviendra de protéger au moyen de mécanismes post-quantiques et en les préparant en conséquence.