Un algorithme candidat au chiffrement post-quantique est craqué par un PC utilisant un seul cœur et en 1 heure,

Les chercheurs se sont appuyés sur les mathématiques pures pour le craquer

Le 3 août 2022 à 13:50, par Bill Fassinou

148PARTAGES

L'un des quatre algorithmes de chiffrement recommandés par le National Institute of Standards and Technology (NIST) des États-Unis comme étant susceptibles de résister aux quanta a été craqué par des chercheurs utilisant un seul cœur d'un processeur Intel Xeon, sorti en 2013. L'algorithme, baptisé SIKE (Supersingular Isogeny Key Encapsulation), avait franchi la plupart des étapes du concours du NIST visant à développer des algorithmes de chiffrement capables de résister aux quanta. Cependant, il a été relativement facilement craqué par des chercheurs de l'université belge KU Leuven (Katholieke Universiteit Leuven).

Le mois dernier, le NIST a présenté les gagnants d'un concours de plusieurs années visant à développer de nouvelles normes de chiffrement, conçues pour se protéger contre une menace hypothétique (pour l'instant) qui n'a pas encore été inventée : les ordinateurs quantiques. Selon les prévisions, ce matériel sera un jour si puissant qu'il sera capable de craquer facilement le chiffrement actuel à clef publique, notamment des normes telles que RSA et Diffie-Hellman. Pour parer à cette menace future, le gouvernement américain a investi dans la création de nouvelles normes de chiffrement capables de résister aux attaques du matériel des jours à venir.

Le NIST a sélectionné quatre algorithmes de chiffrement qui, selon lui, offrent des protections adéquates et qu'il prévoit de normaliser. Le concours a pris des années à se dérouler et a impliqué des dizaines de concurrents du monde entier entier. Après la sélection des quatre finalistes, le NIST a également annoncé que quatre autres candidats étaient considérés comme des candidats potentiels à la normalisation. SIKE (Supersingular Isogeny Key Encapsulation) était l'un des finalistes secondaires du concours du NIST, mais une cyberattaque découverte récemment a réussi à craquer SIKE relativement facilement.

Mais encore, l'ordinateur qui a lancé l'attaque était loin d'être un ordinateur quantique : il s'agissait d'un PC utilisant un seul cœur (ce qui signifie qu'il est moins puissant qu'un PC classique), et il n'a fallu qu'une heure à la petite machine pour dénouer le chiffrement de SIKE. L'exploit a été découvert par des chercheurs du groupe Computer Security and Industrial Cryptography (CSIS) de l'université KU Leuven. SIKE comprend un algorithme de chiffrement à clef publique et un mécanisme d'encapsulation de clef, chacun étant instancié avec quatre ensembles de paramètres : SIKEp434, SIKEp503, SIKEp610 et SIKEp751.

« Exécuté sur un seul cœur, le code Magma annexé rompt les obstacles $IKEp182 et $IKEp217 de SIKE en environ 4 et 6 minutes, respectivement. Une exécution sur les paramètres SIKEp434, dont on pensait auparavant qu'ils répondaient au niveau 1 de sécurité quantique du NIST, a pris environ 62 minutes, toujours sur un seul cœur », ont écrit les chercheurs belges Wouter Castryck et Thomas Decru du CSIS dans un article préliminaire annonçant leur découverte. SIKE a été développé par Microsoft avec l'aide de plusieurs universités, du leader mondial du commerce électronique Amazon, d'Infosec Global et de Texas Instruments.

Les développeurs de SIKE ont proposé une prime de 50 000 dollars pour quiconque parviendrait à le déchiffrer. « La faiblesse nouvellement découverte est clairement un coup dur pour SIKE. L'attaque est vraiment inattendue », a déclaré David Jao, l'un des créateurs de l'algorithme. Les chercheurs du CSIS ont rendu leur code public, ainsi que les détails de leur processeur : une CPU Intel Xeon E5-2630v2 à 2,60 GHz. Cette puce a été lancée au troisième trimestre 2013, elle utilise l'architecture Ivy Bridge d'Intel et un processus de fabrication de 22 nm. La puce offrait six cœurs, mais cinq d'entre eux n'étaient en aucun cas encombrés par ce défi.

Dans l'article publié ce week-end, les chercheurs du CSIS ont expliqué avoir abordé le problème d'un point de vue purement mathématique, en s'attaquant au cœur de la conception de l'algorithme plutôt qu'à d'éventuelles vulnérabilités du code. Ils ont réussi à déchiffrer SIKE en s'attaquant à son algorithme de chiffrement de base, Supersingular Isogeny Diffie-Hellman (SIDH). SIDH serait vulnérable au théorème "glue-and-split", développé en 1997 par le mathématicien Ernst Kani, avec des outils mathématiques supplémentaires conçus en 2000. L'attaque utilise aussi des courbes de genre 2 pour attaquer des courbes elliptiques.

« L'attaque exploite le fait que SIDH a des points auxiliaires et que le degré de l'isogénie secrète est connu. Les points auxiliaires dans SIDH ont toujours été une gêne et une faiblesse potentielle, et ils ont été exploités pour des attaques de fautes, l'attaque adaptative GPST, des attaques de points de torsion, etc. », a expliqué Steven Galbraith, professeur de mathématiques à l'Université d'Auckland. Pour le reste d'entre nous, tout cela signifie que les chercheurs ont utilisé les mathématiques pour comprendre le schéma de chiffrement de SIKE et ont pu prédire - puis récupérer - ses clefs de chiffrement.

Pour leurs efforts et leur article intitulé "An Efficient Key Recovery Attack on SIDH (Preliminary Version)", les chercheurs recevront la prime de 50 000 dollars proposée par Microsoft et ses pairs. L'attaque des chercheurs du CSIS n'a aucun impact sur les quatre premiers algorithmes sélectionnés par le NIST comme normes approuvées, qui reposent tous sur des techniques mathématiques complètement différentes de SIKE. Toutefois, rien n'indique pour l'instant qu'ils sont à labri d'autres attaques plus sophistiquées. Les chercheurs devraient continuer à mettre à l'épreuve leur chiffrement pour tenter de trouver les éventuelles vulnérabilités.

La recherche sur le chiffrement résistant aux quanta est un sujet brûlant, car on estime qu'il est presque certain que les ordinateurs quantiques deviendront prévalents et suffisamment puissants pour craquer les algorithmes de chiffrement existants. Il est donc prudent de développer des algorithmes de chiffrement capable de survivre aux attaques futures, afin que les données chiffrées aujourd'hui restent sûres demain, et que les communications numériques puissent rester sécurisées. À l'heure actuelle, la complexité de la technologie quantique nous met quelque peu à l'abri d'une cascade de piratages quantiques.

« Il est peut-être un peu inquiétant que ce soit le deuxième exemple, au cours des six derniers mois, d'un schéma qui soit parvenu au 3e tour du processus d'examen du NIST avant d'être complètement craqué à l'aide d'un algorithme classique », a déclaré Jonathan Katz, membre de l'IEEE (Institute of Electrical and Electronics Engineers) et professeur au département d'informatique de l'université du Maryland. Rainbow, le candidat auquel il fait référence, a été craqué en février de cette année, bien que seulement à un niveau théorique.

« Trois des quatre schémas PQC [Post-Quantum Cryptography] 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 à l'avenir », a-t-il ajouté. Mais l'on estime que tout n'est pas perdu avec SIKE. Jao pense que la version de SIKE soumise au NIST utilise une seule étape pour générer la clef, et qu'une variante plus résistante pourrait être construite en deux étapes.

Selon les experts, que l'heure soit à la normalisation ou non, une chose est sûre : un travail intense sur le chiffrement post-quantique est nécessaire. Il suffit de penser aux dommages systémiques qu'une seule attaque réussie contre une banque de taille moyenne - transformant toutes ses informations en un zéro, par exemple - aurait sur ses clients et sur le système financier dans son ensemble.

Sources : SIKE, Article des chercheurs du CSIS (PDF), Microsoft

Et vous ?