Le candidat au chiffrement post-quantique est éliminé par un PC monocœur et 1 heure

Getty Images

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.

Le mois dernier, le National Institute of Standards and Technology, ou NIST, du Département américain du commerce, 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 de un ordinateur quantique.

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.

Être totalement 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é An Efficient Key Recovery Attack on SIDH (Preliminary Version), 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 pour 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é.

Publicité

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 le 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.

Il a continué:

Laisser soit la courbe de base et soit avoir la commande . Laisser être donnée telle qu’il existe une isogénie de degré avec , et

Un aspect clé de SIDH est que l’on ne calcule pas directement, mais comme une composition d’isogénies de degré 3. Autrement dit, il existe une suite de courbes reliées par des 3-isogénies.

Essentiellement, comme dans GPST, l’attaque détermine les courbes intermédiaires et détermine donc éventuellement la clé privée. A l’étape l’attaque effectue une recherche par force brute de tous les et l’ingrédient magique est un gadget qui indique lequel est le bon.

(Ce qui précède est trop simplifié, les isogénies dans l’attaque ne sont pas de degré 3 mais de degré une petite puissance de 3.)

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”.