Dix ans d'algorithme de chiffrement quantique monocœur de bureau craqué en 1 heure, cryptographe : C'est trop soudain

Les futurs ordinateurs quantiques pourraient rapidement briser la cryptographie moderne. C’est pourquoi les mathématiciens et les cryptographes recherchent de nouveaux algorithmes de chiffrement adaptés pour résister aux attaques des ordinateurs quantiques. Cette nouvelle génération d'algorithmes cryptographiques capables de résister aux attaques informatiques quantiques sur les algorithmes cryptographiques existants est appelée algorithme de « cryptographie post-quantique (PQC, cryptographie postquantique) ».

Mais récemment, des chercheurs de l'Université de Louvain en Belgique ont découvert qu'un algorithme de cryptage PQC prometteur peut être complètement craqué en seulement 1 heure (certaines versions peuvent être craquées en seulement 4 minutes). Le problème est que ce record n'a pas été établi par un ordinateur haut de gamme, mais par un ordinateur de bureau doté d'un processeur vieux de dix ans, fonctionnant sur un seul cœur. Les chercheurs affirment que cet échec récent et surprenant met en évidence les nombreux obstacles que la cryptographie post-quantique doit surmonter avant de pouvoir être adoptée.

Lien papier : https://eprint.iacr.org/2022/975

Théoriquement, les ordinateurs quantiques peuvent résoudre rapidement des problèmes que les ordinateurs traditionnels prendraient beaucoup de temps à résoudre. Par exemple, la cryptographie moderne s’appuie largement sur l’extrême difficulté rencontrée par les ordinateurs classiques pour traiter des problèmes mathématiques complexes, tels que la factorisation de grands nombres. Et les ordinateurs quantiques pourraient en principe exécuter des algorithmes capables de briser rapidement ce cryptage.

Pour faire face à cette menace, les cryptographes du monde entier ont passé 20 ans à concevoir des algorithmes de chiffrement post-quantique. Ces algorithmes sont basés sur de nouveaux problèmes mathématiques difficiles à résoudre aussi bien pour les ordinateurs quantiques que classiques.

Depuis des années, des chercheurs d'institutions comme le National Institute of Standards and Technology (NIST) étudient quels algorithmes PQC devraient devenir de nouvelles normes que le monde peut adopter. L'agence a annoncé en 2016 qu'elle recherchait des algorithmes PQC candidats et a reçu 82 propositions en 2017. Ensuite, après trois cycles de révision, le NIST a annoncé quatre algorithmes qui deviendront bientôt des standards, et quatre autres qui entreront dans le prochain cycle de révision en tant que candidats potentiels.

L'examen n'est pas encore terminé, et l'un des concurrents est tombé en panne et a été compromis par un ordinateur de bureau vieux de 10 ans. L'algorithme s'appelle SIKE (Supersingular Isogeny Key Encapsulation) et a été étudié par Microsoft, Amazon, Cloudflare et d'autres. Christopher Peikert, cryptographe à l'Université du Michigan à Ann Arbor, a déclaré : « Cette attaque est arrivée si soudainement qu'elle était une solution miracle (une solution extrêmement efficace). »

Qu'est-ce que l'algorithme SIKE ?

SIKE est une famille d'algorithmes PQC impliquant des courbes elliptiques. "Les courbes elliptiques sont un sujet d'étude pour les mathématiciens depuis longtemps", explique Dustin Moody, mathématicien au NIST. "Ils sont décrits par une équation similaire à y^2 = x^3 + Ax + B, où A et B sont des nombres. Par exemple, une courbe elliptique peut être y^2 = x^3 + 3x + 2."

En 1985, « les mathématiciens ont trouvé un moyen de créer des systèmes cryptographiques impliquant des courbes elliptiques qui sont maintenant largement déployés », a déclaré Moody. "Cependant, ces cryptosystèmes à courbe elliptique sont vulnérables aux attaques des ordinateurs quantiques."

Vers 2010, les chercheurs ont découvert une nouvelle façon d'utiliser les courbes elliptiques en cryptographie. On pense que cette nouvelle idée n’est pas vulnérable aux attaques des ordinateurs quantiques.

Cette nouvelle méthode est basée sur la question : comment ajouter deux points sur une courbe elliptique pour obtenir un autre point sur la courbe elliptique. L'« isogénie » dans le nom de l'algorithme signifie homologie, une application d'une courbe elliptique à une autre, qui préserve la loi d'addition.

"Si vous rendez cette cartographie suffisamment complexe, alors le défi du cryptage des données devient que, étant donné deux courbes elliptiques, il est très difficile de trouver l'homologie entre elles", a déclaré le co-auteur de l'étude, Thomas Decru, cryptographe mathématique à l'Université de Louvain en Belgique.

SIKE est une forme de cryptographie basée sur l'homologie basée sur le protocole d'échange de clés Super Singular Homology Diffie-Hellman (SIDH). "SIDH/SIKE est l'un des premiers protocoles de chiffrement pratiques basés sur l'origine", a déclaré Decru.

Il y a cependant une faiblesse de SIKE : pour que cela fonctionne, il doit fournir des informations supplémentaires au public, à savoir des points de torsion auxiliaires. "Les adversaires tentent d'exploiter ces informations supplémentaires depuis un certain temps, mais n'ont pas réussi à les utiliser pour vaincre SIKE", a déclaré Moody. "Mais ce nouvel article trouve un moyen, en utilisant des méthodes mathématiques assez avancées ."

Pour expliquer cette nouvelle attaque, Decru a déclaré que bien que les courbes elliptiques soient des objets unidimensionnels, en mathématiques, les courbes elliptiques peuvent être visualisées comme des objets bidimensionnels ou tout autre objet dimensionnel. On peut aussi créer des homologues entre ces objets généralisés.

En appliquant un théorème vieux de 25 ans, la nouvelle attaque utilise les informations supplémentaires exposées par SIKE pour construire une homologie bidimensionnelle. Cette homologie peut ensuite être utilisée pour reconstruire la clé utilisée par SIKE pour chiffrer le message.

"La chose la plus surprenante pour moi est que cette attaque semble sortir de nulle part", a déclaré Jonathan Katz, cryptographe à l'Université du Maryland, College Park. Bien qu'il n'ait pas été impliqué dans la nouvelle recherche, il a déclaré : « Il y a eu très peu de résultats indiquant que SIKE présente des faiblesses, et ce résultat entraîne soudainement une attaque complètement dévastatrice contre SIKE car il trouve la clé complète. Et elle a été trouvée rapidement. sans aucune informatique quantique. "

Il a fallu plus de dix ans pour attaquer, et quatre minutes pour craquer. À l'aide d'un algorithme basé sur la nouvelle méthode d'attaque mentionnée ci-dessus, les chercheurs ont découvert qu'une machine équipée d'un ordinateur qui prenait dix ans" Il ne faut qu'au moins 4 minutes à un ordinateur de bureau équipé d'un "ancien" processeur (processeur Intel Xeon E5-2630v2) pour trouver une clé protégée par un certain algorithme SIKE, et il ne faut que 4 minutes pour casser le SIKE. algorithme, qui est considéré comme répondant à la norme de sécurité quantique 1 du NIST, 62 minutes. Ces expériences sont exécutées sur un cœur du processeur.

"Habituellement, les attaques graves contre les systèmes cryptographiques se produisent peu de temps après que le système est proposé, ou lorsque le système attire pour la première fois l'attention de tous. Au fil du temps, les attaques deviennent progressivement plus fortes ou affaiblissent considérablement le système. Mais il y avait Aucun avertissement pour cette attaque, et le cryptosystème a été soudainement complètement brisé, a déclaré Peikert : "Depuis que le SIDH a été proposé pour la première fois, il n'y a eu presque aucun progrès dans l'attaque contre le SIDH/SIKE jusqu'à cette percée complète.

Même si." Les chercheurs testent SIKE depuis plus d'une décennie. L'une des raisons pour lesquelles SIKE n'a pas été sélectionné comme norme était la crainte qu'il soit trop nouveau et ne fasse pas suffisamment l'objet de recherches. Steven Galbraith, mathématicien à l'Université d'Auckland, a déclaré : « Les gens craignaient que SIKE ne risque une attaque majeure, et il s'avère qu'ils avaient raison. Alors pourquoi aucune vulnérabilité de SIKE n'a-t-elle été détectée jusqu'à présent ? » Galbraith estime qu'une raison importante est que la nouvelle attaque "applique des mathématiques très avancées". Katz a accepté, déclarant : « Je soupçonne qu'il y a moins de 50 personnes dans le monde qui possèdent à la fois les mathématiques sous-jacentes du PQC et les connaissances nécessaires en cryptographie.

De plus, David Joseph, cryptographe à la startup PQC Sandbox AQ, a dit un jour : "Tant d'un point de vue de mise en œuvre que d'un point de vue théorique, le même problème d'origine est "notoirement difficile", ce qui rend ses défauts fondamentaux plus susceptibles d'être découverts plus tard.

De plus, "Il convient également de le noter." "Avant que le NIST ne mène plusieurs séries d'examens de sélection, de nombreux algorithmes PQC étaient disponibles pour l'analyse, de sorte que les efforts de recherche étaient dispersés. Après plusieurs séries de sélections, les chercheurs ont pu se concentrer sur un petit nombre d'algorithmes", a déclaré Joseph.

David Jao, l'un des inventeurs de SIKE et professeur à l'Université de Waterloo au Canada, a déclaré : "Je pense que ce nouveau résultat est un travail incroyable, et je donne les plus grands éloges aux auteurs. Au début, je était sceptique quant au craquement de SIKE. Triste parce que c'est une solution mathématiquement très élégante"

"Mais les nouvelles découvertes reflètent simplement le fonctionnement de la science : nous avons mis au point un système et tout le monde a pensé qu'il avait l'air bien à l'époque. Puis quelqu'un l'a analysé et. "Il leur a fallu plus de 10 ans pour trouver la faiblesse, ce qui est inhabituel, mais à part ça, cela ne dépasse pas le domaine du progrès scientifique ordinaire", a ajouté David Jao.

De l'avis de Jao, c'est une bonne chose que SIKE ait été craqué maintenant, après tout, il n'a pas été largement déployé.

Qu'est-ce que cela signifie si SIKE est fissuré ?

SIKE est le deuxième algorithme candidat du NIST PQC à être craqué cette année. En février de cette année, Ward Beullens, cryptographe chez IBM Research à Zurich, a révélé qu'il pouvait utiliser son ordinateur portable pour déchiffrer l'algorithme Rainbow en participant au troisième cycle d'examen du NIST. "Cela suggère que toutes les options PQC nécessitent une étude plus approfondie", a déclaré Katz.

Cependant, Moody a souligné que bien que SIKE ait été craqué, d'autres systèmes de cryptographie basés sur l'homologie, tels que CSIDH ou SQIsign, n'ont pas été craqués. "Certaines personnes peuvent penser que la cryptographie basée sur l'homologie est morte, mais la vérité est loin. " Sinon, je pense qu'il reste encore beaucoup à étudier en cryptographie basée sur l'homologie ", a déclaré Decru.

De plus, ces nouveaux travaux peuvent ne pas refléter le niveau de recherche PQC du NIST. Comme l’a noté Decru, SIKE était le seul système cryptographique basé sur l’homologie parmi les 82 propositions reçues par le NIST ; de même, Rainbow était le seul algorithme multivarié parmi ces soumissions ;

Les algorithmes adoptés comme « normes » par le NIST ou qui entrent dans son quatrième cycle de révision sont basés sur des idées mathématiques qui ont été étudiées et analysées par les cryptographes depuis longtemps, a déclaré Galbraith. "Cela ne garantit pas qu'ils sont sécurisés, cela signifie simplement qu'ils résistent aux attaques plus longtemps."

Moody est d'accord, notant qu'"on découvre toujours des avancées étonnantes pour briser les systèmes cryptographiques. . Il n'y a pas de sécurité absolue. "Notre programme est conçu pour cela. Il permet les attaques et les piratages", a déclaré Moody. "Nous les avons constatés à chaque série d'évaluations. C'est le seul moyen de gagner confiance en la sécurité", a reconnu Galbraith, soulignant que des études comme celle-ci "fonctionnent".

Pourtant, "je pense que la disparition de Rainbow et de SIKE incitera davantage de personnes à envisager sérieusement la nécessité d'un plan de secours pour tous les gagnants qui émergeront du processus de normalisation post-quantique du NIST", a déclaré Decru. "Il pourrait être trop risqué de s'appuyer uniquement sur un concept ou un schéma mathématique. C'est également la pensée même du NIST - leur schéma principal est probablement basé sur la cryptographie en réseau (basée sur un réseau), mais ils veulent un schéma de cryptographie sans réseau pour préparer Choisir ."

Decru a noté que d'autres chercheurs ont commencé à développer de nouvelles versions de SIDH/SIKE qui, selon eux, pourraient empêcher ce nouveau type d'attaque. "Je m'attendais à ce qui se passerait à mesure que les attaques s'intensifieraient et que les gens tenteraient de patcher SIDH/SIKE", a déclaré Decru.

Au total, il s'avère que le point de départ de cette nouvelle attaque est un théorème "totalement étranger à la cryptographie" et "révèle l'importance de faire des recherches fondamentales en mathématiques pures pour comprendre les cryptosystèmes", a déclaré Galbraith.

Decru est d’accord et déclare : « En mathématiques, tout n’est pas immédiatement applicable. Certaines choses ne s’appliqueront presque jamais à aucune situation réelle. Mais cela ne veut pas dire que nous ne devrions pas laisser la recherche mener à ces sujets plus obscurs. "

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!