Une nouvelle attaque a facilement éliminé un algorithme de chiffrement potentiel

Apr 14, 2023

Dan Goodin, Ars Technica

Dans la campagne en cours du gouvernement américain pour protéger les données à l'ère des ordinateurs quantiques, une nouvelle et puissante attaque qui a utilisé un seul ordinateur traditionnel pour briser complètement un candidat au quatrième tour met en évidence les risques liés à la normalisation de la prochaine génération d'algorithmes de chiffrement.

Cette histoire est apparue à l'origine sur Ars Technica, une source fiable d'actualités technologiques, d'analyses de politiques technologiques, de critiques, etc. Ars appartient à la société mère de WIRED, Condé Nast.

Le mois dernier, le National Institute of Standards and Technology (NIST) des États-Unis a sélectionné quatre algorithmes de chiffrement post-informatique quantique pour remplacer des algorithmes tels que RSA, Diffie-Hellman et la courbe elliptique Diffie-Hellman, qui sont incapables de résister aux attaques d'un système quantique. ordinateur.

Dans le même mouvement, le NIST a avancé quatre algorithmes supplémentaires en tant que remplaçants potentiels en attendant des tests supplémentaires, dans l'espoir qu'un ou plusieurs d'entre eux puissent également être des alternatives de cryptage appropriées dans un monde post-quantique. La nouvelle attaque brise SIKE, qui est l'un des quatre derniers algorithmes supplémentaires. L'attaque n'a aucun impact sur les quatre algorithmes PQC sélectionnés par le NIST comme normes approuvées, qui reposent tous sur des techniques mathématiques complètement différentes de celles de SIKE.

SIKE - abréviation de supersingular isogeny key encapsulation - est désormais probablement hors course, grâce à une recherche publiée ce week-end par des chercheurs du groupe Computer Security and Industrial Cryptography de la KU Leuven. L'article, intitulé "Une attaque efficace de récupération de clé sur SIDH (version préliminaire)", décrit une technique qui utilise des mathématiques complexes et un seul PC traditionnel pour récupérer les clés de chiffrement protégeant les transactions protégées par SIKE. L'ensemble du processus ne nécessite qu'environ une heure de temps. Cet exploit rend les chercheurs, Wouter Castryck et Thomas Decru, éligibles à une récompense de 50 000 $ du NIST.

"La faiblesse récemment découverte est clairement un coup dur pour SIKE", a écrit David Jao, professeur à l'Université de Waterloo et co-inventeur de SIKE, dans un courriel. "L'attaque est vraiment inattendue."

L'avènement du cryptage à clé publique dans les années 1970 a été une percée majeure, car il a permis à des parties qui ne s'étaient jamais rencontrées d'échanger en toute sécurité du matériel crypté qui ne pouvait pas être brisé par un adversaire. Le chiffrement à clé publique repose sur des clés asymétriques, avec une clé privée utilisée pour déchiffrer les messages et une clé publique distincte pour le chiffrement. Les utilisateurs rendent leur clé publique largement disponible. Tant que leur clé privée reste secrète, le schéma reste sécurisé.

Dans la pratique, la cryptographie à clé publique peut souvent être difficile à manier, de sorte que de nombreux systèmes reposent sur des mécanismes d'encapsulation de clé, qui permettent à des parties qui ne se sont jamais rencontrées auparavant de convenir conjointement d'une clé symétrique sur un support public tel qu'Internet. Contrairement aux algorithmes à clé symétrique, les mécanismes d'encapsulation de clé utilisés aujourd'hui sont facilement brisés par les ordinateurs quantiques. SIKE, avant la nouvelle attaque, était censé éviter de telles vulnérabilités en utilisant une construction mathématique complexe connue sous le nom de graphe d'isogénie supersingulaire.

La pierre angulaire de SIKE est un protocole appelé SIDH, abréviation de supersingular isogeny Diffie-Hellman. Le document de recherche publié au cours du week-end montre comment le SIDH est vulnérable à un théorème connu sous le nom de "glue-and-split" développé par le mathématicien Ernst Kani en 1997, ainsi qu'aux outils conçus par ses collègues mathématiciens Everett W. Howe, Franck Leprévost et Bjorn Poonen en 2000. La nouvelle technique s'appuie sur ce que l'on appelle l'attaque adaptative GPST, décrite dans un article de 2016. Les calculs derrière la dernière attaque sont garantis impénétrables pour la plupart des non-mathématiciens. Voici à peu près aussi près que vous allez obtenir:

"L'attaque exploite le fait que SIDH a des points auxiliaires et que le degré d'isogénie secrète est connu", a expliqué Steven Galbraith, professeur de mathématiques à l'Université d'Auckland et le "G" de l'attaque adaptative GPST, dans un court article. sur la nouvelle attaque. "Les points auxiliaires de SIDH ont toujours été une gêne et une faiblesse potentielle, et ils ont été exploités pour les attaques par faute, l'attaque adaptative GPST, les attaques par points de torsion, etc."

Lauren Goode

Lauren Goode

Julien Chokkattu

Chevalier

Plus important que de comprendre les mathématiques, Jonathan Katz, membre de l'IEEE et professeur au Département d'informatique de l'Université du Maryland, a écrit dans un e-mail : "L'attaque est entièrement classique et ne nécessite pas du tout d'ordinateurs quantiques".

SIKE est le deuxième candidat PQC désigné par le NIST à être invalidé cette année. En février, le chercheur postdoctoral d'IBM Ward Beullens a publié une recherche qui a brisé Rainbow, un schéma de signature cryptographique avec sa sécurité, selon Cryptomathic, "s'appuyant sur la difficulté du problème de la résolution d'un grand système d'équations quadratiques multivariées sur un champ fini".

La campagne de remplacement du PQC du NIST est en cours depuis cinq ans. Voici un bref historique :

Rainbow est tombé au tour 3. SIKE avait réussi jusqu'au tour 4.

Katz a poursuivi :

Il est peut-être un peu inquiétant qu'il s'agisse du deuxième exemple au cours des six derniers mois d'un schéma qui a atteint le 3e tour du processus d'examen du NIST avant d'être complètement brisé à l'aide d'un algorithme classique. (L'exemple précédent était Rainbow, qui a été cassé en février.) Trois des quatre schémas PQC reposent sur des hypothèses relativement nouvelles dont la difficulté exacte n'est pas bien comprise, donc ce que la dernière attaque indique, c'est que nous devons peut-être encore être prudents/conservateurs avec le processus de normalisation qui va de l'avant.

J'ai demandé à Jao, le co-inventeur de SIKE, pourquoi la faiblesse n'avait été révélée que maintenant, à un stade relativement avancé de son développement. Sa réponse était perspicace. Il a dit:

Il est vrai que l'attaque utilise des mathématiques qui ont été publiées dans les années 1990 et 2000. Dans un sens, l'attaque ne nécessite pas de nouvelles mathématiques ; cela aurait pu être remarqué à tout moment. Une facette inattendue de l'attaque est qu'elle utilise des courbes de genre 2 pour attaquer les courbes elliptiques (qui sont des courbes de genre 1). Une connexion entre les deux types de courbes est tout à fait inattendue. Pour donner un exemple illustrant ce que je veux dire, pendant des décennies, les gens ont essayé d'attaquer la cryptographie à courbe elliptique régulière, y compris certains qui ont essayé d'utiliser des approches basées sur les courbes de genre 2. Aucune de ces tentatives n'a abouti. Donc, pour cette tentative de réussir dans le domaine des isogénies, c'est un développement inattendu.

En général, il y a beaucoup de mathématiques profondes qui ont été publiées dans la littérature mathématique mais qui ne sont pas bien comprises par les cryptographes. Je me range dans la catégorie de ces nombreux chercheurs qui travaillent en cryptographie mais ne comprennent pas autant les mathématiques que nous le devrions vraiment. Donc, parfois, tout ce qu'il faut, c'est quelqu'un qui reconnaît l'applicabilité des mathématiques théoriques existantes à ces nouveaux cryptosystèmes. C'est ce qui s'est passé ici.

La version de SIKE soumise au NIST utilisait une seule étape pour générer la clé. Une variante possible de SIKE pourrait être construite en deux étapes. Jao dit qu'il est possible que cette dernière variante ne soit pas sensible aux calculs causant cette rupture. Pour l'instant, cependant, SIKE est mort, du moins dans la course actuelle. Le calendrier des trois candidats restants est actuellement inconnu.

Cette histoire est apparue à l'origine sur Ars Technica.