RETEX ECW21 : Mise en œuvre de la cryptographie post-quantique

Dans le cadre de la 6e édition de l’European Cyber Week ayant lieu cette semaine, la DGA – Maîtrise de l’information, l’IRMAR et l’IRISA ont co-organisé avec le soutien du Pôle d’excellence cyber, du CNRS et d’Inria, un workshop dédié à la cryptographie post-quantique.

​Compétition, défis, cet article revient sur les différentes sujets évoqués.

Brève mise en contexte de la cryptographie traditionnelle

De nos jours, la cryptographie est omniprésente quand il s’agit de protéger nos communications, nos identités et, de façon plus générale, nos données sensibles.

La cryptographie traditionnelle comprend trois grandes catégories de systèmes, dont la cryptographie asymétrique, également dite à clé publique. Elle peut être utilisée pour établir un canal chiffré entre deux parties, pour l’authentification ou encore la signature électronique.

La grande majorité des systèmes asymétriques repose sur deux problèmes mathématiques difficiles à résoudre par un attaquant. Le premier problème concerne la factorisation des entiers. Multiplier deux nombres entre eux est une opération facile. Toutefois, pour des (très) grands nombres, retrouver les facteurs qui le composent est beaucoup plus difficile. C’est sur ce problème qu’est basé RSA (chiffrement, signature). Le second problème est celui du logarithme discret sur lequel repose des mécanismes tels que Diffie-Hellman (échange de clés) ou ECDSA.

La robustesse des mécanismes cryptographiques asymétriques repose donc généralement sur la puissance de calcul nécessaire pour les casser ; ils sont ainsi dimensionnés de telle sorte qu’un attaquant ait besoin de millions d’années pour contourner leur sécurité.

A moins que…

Mieux vaux prévenir que guérir

Dans les années 90, Peter Shor a décrit un algorithme qui permet, à l’aide d’un ordinateur quantique suffisamment puissant, de factoriser de grands nombres ou retrouver des logarithmes discrets beaucoup plus rapidement. Les algorithmes asymétriques tels que RSA ou Diffie-Hellman se retrouveraient alors brisés en quelques instants.

Bien qu’à ce jour, seuls des prototypes d’ordinateurs quantiques aient vu le jour, il convient d’étudier dès à présent cette menace potentielle. Pourquoi ?

De nombreux algorithmes d’échanges de clés ou de chiffrement asymétriques sont vulnérables à une attaque rétroactive. Un attaquant pourrait donc enregistrer des communications dès maintenant et attendre l’apparition d’un ordinateur quantique pour casser les mécanismes et retrouver les données a posteriori.

Plusieurs recherches ont permis d’estimer un risque élevé d’apparition d’un ordinateur quantique à grande échelle d’ici 20 à 30 ans. Cela impacterait fortement les secrets ayant une longue durée de vie. C’est pour cela qu’il faut rechercher des alternatives quantum-safe permettant de protéger les données sensibles au long terme, et il faut commencer maintenant pour espérer parvenir à une maturité comparable aux algorithmes actuels d’ici l’aboutissement de l’ordinateur quantique (sécurité éprouvée, usage généralisé, etc.).

En ce sens, des académiciens à l’internationale sont investis depuis 2017, à  travers la compétition organisée par le NIST, pour développer de tels algorithmes capables de résister aux attaques des ordinateurs quantiques tout en restant résistants aux attaques classiques actuelles.

QUID des mécanismes symétriques ? ils seront également impactés par l’ère quantique mais dans une moindre mesure. Bien qu’il existe déjà un algorithme quantique permettant de traiter le problème de la recherche non structurée (celui de Grover), une solution consiste à augmenter la taille des clés ou de la sortie produite, et à privilégier donc AES-256 plutôt qu’AES-128 ou encore SHA-384 pour les fonctions de hachage.

Cryptographie quantique versus cryptographie post-quantique

La cryptographie quantique consiste à exploiter les principes de la mécanique quantique pour construire des cryptosystèmes, notamment basés sur la distribution quantique des clés. 

Par cryptographie post-quantique, on entend, comme mentionné précédemment, des algorithmes cryptographiques conçus pour être résistants non seulement aux ordinateurs “classiques” tels que nous les connaissons, mais aussi à d’hypothétiques ordinateurs quantiques suffisamment puissants.

La plupart des algorithmes asymétriques post-quantiques proposés à ce jour se répartissent en un nombre restreint de familles : schémas fondés sur les réseaux euclidiens ou lattices, sur les codes correcteurs, sur la cryptographie multivariable, sur les isogénies ou sur le hachage.

Les réseaux euclidiens sont des structures mathématiques géométriques discrètes qui correspondent à des points à intervalle régulier. Le fait de trouver la distance minimal entre deux points dans le cas général est un problème difficile. On peut donc tirer partie de cette difficulté pour concevoir de nouveaux algorithmes. Si ce sujet vous intéresse davantage, un programme de l’institut Simon “Lattice: Algorithms, Complexity, and Cryptography” est une bonne référence.

En cryptographie à base de code, le chiffrement d’un message consiste simplement à appliquer le code correcteur correspondant, et le déchiffrement à appliquer l’algorithme de décodage du code correcteur, le décodage de codes aléatoires étant un problème difficile.

NIST Post-Quantum Cryptography Standardization

En 2017, le NIST a lancé un effort international pour la standardisation d’algorithmes cryptographiques dits post-quantiques, ce qui signifie qu’ils résisteraient également aux adversaires disposant d’un ordinateur quantique. Ce processus de standardisation se déroule sous la forme d’une compétition internationale à laquelle tous les volontaires étaient invités à soumettre de nouveaux algorithmes d’échange de clé et de nouveaux schémas de signature.

Sur 82 soumissions reçues, 69 candidats valides ont été retenus au premier tour de la compétition.

Ces candidats ont été rendus publics et leur sécurité a fait l’objet d’une analyse très précise menée par l’ensemble de la communauté cryptographique. Sur la base des premières évaluations, le NIST a sélectionné, en 2019, 26 soumissions pour le second tour de la compétition.

En 2020, 7 candidats finalistes ont été retenus au troisième tour ainsi que 8 systèmes alternatifs.

Après plusieurs années d’analyse, cet effort devrait aboutir vers 2022-2023 avec une publication draft soumise à revue publique, suivi des premières standardisations en 2024.

Contrairement aux compétitions précédentes, on ne cherche pas à concevoir un seul type de primitive (fonction de hachage par exemple). Les candidats peuvent aussi bien être des mécanismes de signature que des mécanismes d’échange de clés/chiffrement. En outre, l’objectif n’est pas d’obtenir un seul vainqueur mais un ensemble de systèmes viables. L’objectif est de diversifier les systèmes cryptographiques asymétriques pour éviter de se retrouver sans solution de secours en cas d’attaques futures.

Et l’avis de l’ANSSI ?

La prochaine décennie étant un horizon envisageable pour la réalisation d’un ordinateur quantique, pour des produits ou applications devant assurer une protection pour une très longue durée de la confidentialité des informations (après 2030), l’ANSSI (Agence Nationale de la Sécurité des Systèmes d’Information) considère qu’il est raisonnable de commencer à se prémunir au mieux contre la menace quantique sans risque de perte de sécurité classique.

En ce sens, l’ANSSI préconise l’usage de mécanismes hybrides pour assurer la protection de telles données dans la mise à jour récente des ces guides de sélection de mécanismes cryptographiques.

L’agence propose une transition en trois étapes:

  • La première, jusqu’en 2025, consistera à basculer sur des solutions hybrides dès lors que la construction employée garantit l’absence de régression de sécurité face aux attaques des ordinateurs classiques actuels. Le critère de sécurité pré-quantique reste donc prédominant, et la sécurité post-quantique est vue comme un mécanisme de défense en profondeur. Du point de vue développeur, lors de cette première phase, les mécanismes d’hybridations ne pourront pas faire l’objet d’un visa de sécurité. Le choix du mécanisme d’hybridation restera relativement libre. Il pourra ne pas s’agir d’un des mécanismes standardisés par le NIST à l’issue de la compétition, les finalistes stables et bien étudiés seront acceptables, en privilégiant les systèmes offrant le plus haut niveau de sécurité (niveau V du NIST).
  • La seconde phase, jusqu’en 2030, consistera à passer d’une simple recommandation à une obligation, dans certains cas, de mettre en place de l’hybridation. Ainsi, l’ANSSI ne délivrera plus de labels de sécurité pour certains types de produits visant une sécurité ou un usage à long terme s’ils n’offrent pas de sécurité post-quantique. Le choix des mécanismes sera également plus restreint.
  • La phase 3, après 2030, consistera à finaliser la transition avec une sécurité post-quantique qui pourrait être obligatoire pour de plus en plus de produits.

Le sujet de la transition vers le post-quantique doit faire l’objet d’une publication par l’agence d’ici la fin de l’année. Stay tuned!

Quelques challenges soulevés

Le passage à la cryptographie post-quantique nécessite de répondre à plusieurs problématiques. En raison de contraintes environnementales (mémoire, débit, etc.), la taille des clés, beaucoup plus importante pour les algorithmes post-quantiques, ou encore les performances des mécanismes, peuvent limiter les usages.

Certaines contre-mesures destinées à empêcher les attaques par canaux auxiliaires (masquage par exemple) se révèlent difficiles, voire potentiellement impossible à adapter pour certains mécanismes post-quantiques. C’est notamment le cas de schémas basés sur des distributions gaussiennes. La majorité des candidats du NIST ont évité ce type de distribution.

Un mot du côté des industriels

L’ANSSI encourage les développeurs à penser crypto-agilité, c’est à dire à concevoir les solutions de sorte qu’il soit possible de mettre à jour facilement les mécanismes cryptographiques implémentés ou de les remplacer un algorithme par un autre.

CryptoNext a déjà initié un tel effort à travers la conception de QSL, sa bibliothèque cryptographique intégrant des mécanismes de signature et d’échange de clés quantum-safe. Développée en C et assembleur, elle se veut modulaire et agile. Ils ont commencé à intégrer cette bibliothèque dans d’autres librairies (typiquement OpenSSL) ou des applications réelles (messagerie sécurisée, HSM, signature de document PDF).

La machine est également en route du côté de sociétés telles que Thales, ou encore Secure-IC.

D’autres groupes de travail autour de l’application concrète de la cryptographie post-quantique

Horizon 2020 PROMETHEUS est un projet de recherche européen dont l’objectif est de fournir un ensemble d’outils cryptographiques efficaces (signature, chiffrement), principalement fondés sur les réseaux euclidiens, permettant la protection de la vie privée dans un monde post-quantique. L’objectif est de fournir des solutions efficaces de mécanismes d’authentification anonymes, pour plusieurs applications concrètes, comme les systèmes de paiement ou le vote électronique. 

Plusieurs propositions de nouveaux formats de certificats X.509 sont en cours de discussion du côté de l’IETF. Une première proposition concerne l’usage de certificats hybrides non composés. Les entités disposeront de plusieurs certificats, un pour chaque algorithme, essentiellement pour des raisons d’interopérabilité lors de la transition vers le post-quantique.

Une autre méthode consiste à incorporer des ensembles alternatifs de matériaux cryptographiques (par exemple une nouvelle clé publique post-quantique) dans les certificats numériques X.509v3, des listes de révocation de certificats X.509v2 et des demandes de signature de certificat PKCS#10 via l’utilisation d’extension ou d’attributs spécifiques. Cette méthode permet de conserver une rétrocompatibilité avec les systèmes utilisant les algorithmes existant.

Du côté des protocoles réseaux, des travaux sont également en cours concernant TLS et IPsec/IKEv2 notamment.

Quel bilan ?

Bien que tout cela soit relativement récent, et que le gros du travail reste à faire, la cryptographie post-quantique est un sujet pris à cœur par bon nombre d’institutions, académiciens et industriels en France comme à l’international.

Côté CESTI, vous l’aurez bien compris, les schémas de certification vont petit à petit intégrer la sécurité post-quantique. De quoi rendre les évaluations passionnantes !

 

 

 

 

Besoin d’être accompagné en cybersécurité ?