Si les protocoles de cryptographie d'aujourd'hui devaient échouer, il serait impossible de sécuriser les connexions en ligne - pour envoyer des messages confidentiels, effectuer des transactions financières sécurisées ou authentifier des données. N'importe qui pouvait accéder à n'importe quoi; n'importe qui pouvait se faire passer pour n'importe qui. L'économie numérique s'effondrerait.
Quand (ou if) un ordinateur quantique entièrement fonctionnel devient disponible, c'est précisément ce qui pourrait arriver. En conséquence, en 2017, le National Institute of Standards and Technology (NIST) du gouvernement américain a lancé un concours international pour trouver les meilleurs moyens de réaliser la cryptographie «post-quantique».
Le mois dernier, l'agence a sélectionné son premier groupe de gagnants : quatre protocoles qui, avec quelques révisions, seront déployés comme un bouclier quantique. Il a également annoncé quatre candidats supplémentaires toujours à l'étude.
Puis le 30 juillet, deux chercheurs ont révélé qu'ils avaient cassé un de ces candidats en une heure sur un ordinateur portable. (Depuis lors, d'autres ont rendu l'attaque encore plus rapide, brisant le protocole en quelques minutes.) "Une attaque aussi dramatique et puissante... a été un choc", a déclaré Steven Galbraith, mathématicien et informaticien de l'Université d'Auckland en Nouvelle-Zélande. Non seulement les mathématiques sous-jacentes à l'attaque ont été surprenantes, mais elles ont également réduit la diversité (indispensable) de la cryptographie post-quantique - éliminant un protocole de cryptage qui fonctionnait très différemment de la grande majorité des schémas du concours NIST.
"C'est un peu dommage", a déclaré Christophe Peikert, cryptographe à l'Université du Michigan.
Les résultats ont laissé la communauté de la cryptographie post-quantique à la fois ébranlée et encouragée. Secoué, parce que cette attaque (et une autre d'un tour précédent de la compétition) a soudainement transformé ce qui ressemblait à une porte en acier numérique en journal humide. "Il est sorti de nulle part", a déclaré Dustin Maugrey, l'un des mathématiciens à la tête de l'effort de normalisation du NIST. Mais si un schéma cryptographique va être cassé, il est préférable que cela se produise bien avant qu'il ne soit utilisé dans la nature. "Il y a beaucoup d'émotions qui vous traversent", a déclaré David Jao, un mathématicien de l'Université de Waterloo au Canada qui, avec un chercheur d'IBM Luca De Féo, a proposé le protocole en 2011. Certes, la surprise et la déception en font partie. "Mais aussi", a ajouté Jao, "au moins, il s'est cassé maintenant."
Promenades secrètes parmi les courbes
Jao et De Feo avaient vu une opportunité pour un système cryptographique qui était à la fois similaire et convenablement distinct des protocoles bien connus. Leur schéma, appelé protocole Diffie-Hellman d'isogénie supersingulaire (SIDH), traitait des courbes elliptiques - les mêmes objets mathématiques utilisés dans l'un des types de cryptographie les plus répandus déployés aujourd'hui. Mais il les a utilisés d'une manière complètement différente. C'était aussi le schéma le plus compact que le NIST envisageait (avec le compromis qu'il était plus lent que la plupart des autres candidats).
Et "mathématiquement, c'est vraiment élégant", a déclaré Jao. « À l'époque, cela semblait être une belle idée.
Supposons que deux parties, Alice et Bob, souhaitent échanger un message en secret, même sous le regard attentif d'un agresseur potentiel. Ils commencent par une collection de points reliés par des arêtes appelées graphe. Chaque point représente une courbe elliptique différente. Si vous pouvez transformer une courbe en une autre d'une manière particulière (via une carte appelée isogénie), tracez une arête entre la paire de points. Le graphique résultant est énorme et il est facile de s'y perdre : si vous faites une promenade relativement courte le long de ses bords, vous vous retrouverez dans un endroit qui semble complètement aléatoire.
Les graphiques d'Alice et de Bob ont tous les mêmes points, mais les arêtes sont différentes - elles sont définies par des isogénies différentes. Alice et Bob commencent au même point, et ils sautent chacun le long d'arêtes aléatoires sur leur propre graphique, en gardant une trace de leur chemin d'un point à un autre. Chacun publie ensuite son emplacement d'arrivée mais garde son chemin secret.
Maintenant, ils changent de place : Alice va au dernier point de Bob et Bob à celui d'Alice. Chacun répète sa marche secrète. Ils le font de telle manière qu'ils finiront tous les deux au même point.
Cet emplacement a été trouvé en secret, donc Alice et Bob peuvent l'utiliser comme clé secrète - des informations qui leur permettent de chiffrer et de déchiffrer les messages de l'autre en toute sécurité. Même si un attaquant voit les points intermédiaires qu'Alice et Bob s'envoient, ils ne connaissent pas la marche secrète d'Alice ou de Bob, donc ils ne peuvent pas comprendre ce point final.
Mais pour que SIDH fonctionne, Alice et Bob ont également besoin d'échanger quelques informations supplémentaires sur leurs promenades. C'est cette information supplémentaire qui a conduit à la chute du SIDH.
Une nouvelle tournure sur les anciennes mathématiques
Thomas Décru n'a pas cherché à casser le SIDH. Il essayait de s'appuyer sur cela - de généraliser la méthode pour améliorer un autre type de cryptographie. Cela n'a pas fonctionné, mais cela a déclenché une idée : son approche pourrait être utile pour attaquer le SIDH. Et ainsi il s'approcha Wouter Castryck, son collègue de l'Université catholique de Louvain en Belgique et l'un de ses anciens directeurs de thèse, et les deux se sont plongés dans la littérature pertinente.
Ils sont tombés sur un article publié par le mathématicien Ernst Kani en 1997. Il s'agissait d'un théorème qui "était presque immédiatement applicable au SIDH", a déclaré Castryck. "Je pense qu'une fois que nous avons réalisé que … l'attaque est arrivée assez rapidement, en un ou deux jours."
En fin de compte, pour récupérer la marche secrète d'Alice (et donc la clé partagée), Castryck et Decru ont examiné le produit de deux courbes elliptiques - la courbe de départ d'Alice et la courbe qu'elle a envoyée publiquement à Bob. Cette combinaison produit une sorte de surface appelée surface abélienne. Ils ont ensuite utilisé ces surfaces abéliennes, le théorème de Kani (qui relie les surfaces abéliennes aux courbes elliptiques) et les informations supplémentaires qu'Alice a données à Bob pour découvrir chaque pas qu'Alice a fait.
"C'est presque comme un signal de ralliement qui vous permet de vous verrouiller sur [certaines surfaces abéliennes]", a déclaré Jao. "Et ce signal vous indique que c'est la voie à suivre pour passer à l'étape suivante afin de trouver la bonne [marche secrète]." Ce qui les a conduits directement à la clé partagée d'Alice et Bob.
"C'est une approche très inattendue, aller vers des objets plus compliqués pour dériver des résultats sur l'objet le plus simple", a déclaré Jao.
"J'étais très excité de voir cette technique utilisée", a déclaré Christine Lauter, mathématicien et cryptographe chez Meta AI Research qui a non seulement aidé à développer la cryptographie basée sur l'isogénie, mais a également travaillé sur les surfaces abéliennes. "Alors honte à moi de ne pas y avoir pensé comme un moyen de le casser."
L'attaque de Castryck et Decru a brisé la version la plus basse du protocole SIDH en 62 minutes et le niveau de sécurité le plus élevé en un peu moins d'une journée. Puis, peu de temps après, un autre expert a peaufiné l'attaque de sorte qu'il n'a fallu que 10 minutes pour casser la version à faible sécurité et quelques heures pour casser la version à haute sécurité. Des attaques plus générales publié ces dernières semaines rendent peu probable que le SIDH puisse être récupéré.
"C'était un sentiment spécial", a déclaré Castryck, bien que doux-amer. "Nous avons tué l'un de nos systèmes préférés."
Un moment de bassin versant
Il est impossible de garantir qu'un système est inconditionnellement sécurisé. Au lieu de cela, les cryptographes comptent sur suffisamment de temps qui passe et sur suffisamment de personnes essayant de résoudre le problème pour se sentir en confiance. "Cela ne veut pas dire que vous ne vous réveillerez pas demain et découvrirez que quelqu'un a trouvé un nouvel algorithme pour le faire", a déclaré Jeffrey Hoffstein, mathématicien à l'Université Brown.
C'est pourquoi les compétitions comme celles du NIST sont si importantes. Lors du précédent tour du concours NIST, Ward Beullens, un cryptographe chez IBM, a conçu une attaque qui a brisé un stratagème appelé Rainbow en un week-end. Comme Castryck et Decru, il n'a pu mettre en scène son attaque qu'après avoir vu le problème mathématique sous-jacent sous un angle différent. Et comme l'attaque contre SIDH, celle-ci a brisé un système qui reposait sur des mathématiques différentes de la plupart des protocoles post-quantiques proposés.
"Les récentes attaques ont été un moment décisif", a déclaré Thomas Prest, un cryptographe de la startup PQShield. Ils soulignent à quel point la cryptographie post-quantique est difficile et combien d'analyses pourraient être nécessaires pour étudier la sécurité de divers systèmes. "Un objet mathématique peut n'avoir aucune structure évidente dans une perspective et avoir une structure exploitable dans une autre", a-t-il déclaré. "Le plus difficile est d'identifier la bonne nouvelle perspective."
