Et si une grande fissure apparaissait du jour au lendemain dans la couche de sécurité de l'Internet ? Et si cette fracture remettait en cause les fondements mathématiques des algorithmes cryptographiques ? Ces questions ont émergé au début du mois de mars, après la publication d’un article dans lequel on peut lire en guise d’introduction cette phrase accrocheuse : « Cela détruit le système de cryptage RSA. » Si l’affirmation s'avère exacte, cela signifie qu’une grande partie des données cryptées au repos ou en mouvement ne serait plus sécurisée. Le premier problème, c’est que personne ne peut dire si l'auteur de cet article a raison. Le second problème, plus important encore, c’est que personne ne sait ce qu’il faudrait faire si ces affirmations étaient vraies.

A l'heure où nous écrivons ces lignes, les mathématiciens sont toujours en train de délibérer sur le premier problème, mais d'autres se penchent sur le second et commencent à esquisser des plans pour savoir ce qu’il faudrait faire au cas où une faiblesse catastrophique dans le système de cryptage surgissait de nulle part. Ces derniers préconisent une base plus solide constituée de plusieurs algorithmes et une implementation avec des protocoles pouvant rendre le basculement plus simple. Certains cryptographes cherchent des alternatives à l'algorithme de cryptographie asymétrique RSA (nommé d’après ses trois inventeurs Ronald Rivest, Adi Shamir et Leonard Adleman qui l’ont décrit en 1977), car c’est le seul algorithme de cryptage potentiellement vulnérable aux nouvelles machines quantiques. Selon ces mathématiciens, « le monde doit être plus agile, car de nombreuses fissures potentielles pourraient apparaître ».

Factorisation des grands nombres

L'article publié en mars, qui a remis la faiblesse sur RSA sur le devant de la scène, s'intitule « Fast Factoring Integers by SVP Algorithms » et il a été rédigé par Claus Schnorr, un cryptographe respecté de 77 ans qui a pris sa retraite de l'université Johann Wolfgang Goethe en 2011. Claus Schnorr est en partie connu pour un système de signature numérique qui porte son nom, breveté pour la première fois en 1988. Le système de Claus Schnorr est notamment utilisé sous une forme modifiée par certaines monnaies numériques, car il est efficace et produit des signatures courtes. Les blockchains de Polkadot, Kusama et Zilliqa n'en sont que trois exemples. Sa force repose sur l'impossibilité présumée de résoudre le problème du logarithme discret. RSA est un algorithme différent, avec une histoire plus longue et une adoption plus large, du moins par le passé. Il dépend de la complexité de la factorisation des grands nombres. L'approche récemment publiée par Claus Schnorr, que l’on a vu évoluer à travers une série d'articles publiés ces dernières années par le cryptographe, reformule le problème de la factorisation des grands nombres sous forme de problème que les mathématiciens appellent parfois la recherche du bon vecteur dans un treillis multidimensionnel défini par des nombres beaucoup plus petits. L’article de Claus Schnorr est cependant largement théorique, si bien que beaucoup de gens se demandent si son implementation réelle dans un logiciel permettrait d'atteindre ces objectifs. Plusieurs personnes ont fait circuler des défis de grands nombres construits comme des clés RSA. Quiconque peut attaquer le cryptage RSA peut le prouver facilement en publiant les facteurs du nombre. Mais jusqu'à présent, personne n'a réussi à faire une telle démonstration publique concrète, et certains de ceux qui ont essayé ont annoncé qu'ils ne pouvaient pas faire fonctionner l'algorithme.

Corriger les faiblesses du cryptage RSA

Résoudre des problèmes après la découverte d’une attaque récente n'a rien de nouveau. Les éditeurs de logiciels envoient régulièrement des correctifs pour corriger des failles dans le code, et elles font ouvertement appel aux rapports de bogue pour encourager les utilisateurs à signaler les problèmes qu'ils rencontrent. Mais, si elle est prouvée, l’approche de Claus Schnorr exposerait des faiblesses dans les fondements d'un protocole, et aucun éditeur ou entreprise n'assume la responsabilité de ce protocole. Une entreprise, également appelée RSA, atteste d’une longue histoire avec l'algorithme, mais les brevets ont expiré et la plupart des implémentations du cryptage RSA utilisées sur Internet ne proviennent pas de cette entreprise. La plupart des bibliothèques populaires sont open source et sont maintenues par une communauté.

Pour aggraver les choses, la faiblesse, si elle existe, ne peut pas être corrigée en modifiant quelques lignes avec un nouveau code comme c'est le cas pour de nombreux trous ou bogues. Toute solution pourrait mettre des années à émerger, car il faut du temps pour tester et déployer tout nouvel algorithme. Il n'est peut-être pas si difficile de passer à un nouvel algorithme, car de nombreuses solutions de cryptage permettent d'utiliser différents algorithmes avec différentes longueurs de clé. Mais c’est la mise à jour de l'infrastructure d'authentification qui maintient la hiérarchie des certificats utilisée pour valider les clés publiques qui pourrait représenter le plus grand défi. Les principaux navigateurs Internet actuels sont livrés avec des certificats racine provenant de différentes autorités de certification et beaucoup d'entre eux reposent sur le cryptage RSA.

Le remplacement des certificats racine dans les navigateurs (et d'autres outils) nécessite l'envoi de nouvelles versions, ce qui peut s'avérer délicat, car les certificats racine sont très puissants. Par exemple, certaines attaques consistent à insérer de faux certificats qui se portent garants des attaquants, afin de leur permettre de se faire passer pour d'autres sites. À l'heure actuelle, les certificats de certaines autorités de certification majeures comme Verisign, Amazon, GoDaddy et Entrust reposent tous sur l'algorithme RSA.

La question des ordinateurs quantiques

Savoir ce qu'il faut faire face aux ordinateurs quantiques potentiels est une autre source de préoccupation. La communauté de la cryptographie est déjà bien engagée dans la recherche de solutions de remplacement capables de résister aux machines quantiques, voie sur laquelle elle s'est engagée il y a plusieurs années car certains craignent que ces ordinateurs ne soient bientôt disponibles. Les machines quantiques pourraient menacer des algorithmes comme le RSA, car l'un des algorithmes les plus connus pour les machines quantiques, développé par Peter Shor, est capable de factoriser des nombres. Les machines actuelles ne sont pas très puissantes et le plus grand nombre qu'elles ont factorisé est 21. Mais beaucoup pensent que l’arrivée de modèles plus puissants est possible. Cet algorithme n'est pas la seule menace, car la factorisation des grands nombres est un défi attrayant, notamment en raison de sa valeur économique. Par exemple, un nouvel article d'Élie Gouzien et de Nicolas Sangouard évoque l’usage d’un type spécial de mémoire quantique. Leur conception, également loin d'être réalisée, pourrait permettre de factoriser les nombres de 2048 bits utilisés dans les certificats racine basés sur un cryptage RSA en six mois environ.

Imaginer un nouveau système de cryptage non-RSA 

Ce sont des résultats théoriques comme celui-ci qui ont incité le National Institute of Standards and Technology (NIST) à lancer un concours en 2016 pour identifier les possibilités de remplacements potentielle du cryptage RSA. En 2019, 26 demi-finalistes étaient encore en lice et il reste sept finalistes en 2020. Le processus de sélection est toujours ouvert, car le comité a également choisi d’inclure huit alternatives pour les étudier. Ils espèrent pouvoir choisir une alternative au RSA dans les prochaines années, mais la pandémie de Covid-19 pourrait ralentir ce processus.

Les finalistes retenus ont proposé trois approches mathématiques différentes. Ceux que le NIST qualifie « d’algorithmes polyvalents les plus prometteurs » utilisent des treillis et dépendent de la difficulté de trouver un élément ou un vecteur dans ce treillis. Il existe trois schémas de cryptage différents (CRYSTALS-KYBER, NTRU et SABER) et deux algorithmes de signature différents (CRYSTALS-DILITHIUM et FALCON). Le NIST a également choisi une approche de signature plus ancienne, développée par Robert McEliece en 1978. Cette approche repose sur la difficulté de trouver la bonne solution à un code général de correction d’erreurs. Ces constructions mathématiques sont normalement utilisées dans le stockage et la transmission de données pour récupérer les erreurs, mais Robert McEliece a trouvé un moyen de modifier leur construction de façon à ce que la récupération de l'erreur devienne difficile pour tout le monde, sauf pour les personnes détenant la bonne clé secrète. 

Le dernier finaliste est connu sous le nom de code Rainbow et construit des polynômes à partir de nombreuses variables difficiles à résoudre pour un attaquant. Plusieurs variantes ont été nommées afin d'encourager les recherches sur leurs fondements. Certains reposent sur des bases mathématiques similaires à celles des finalistes, mais d'autres utilisent des approches totalement différentes. Par exemple, le SPHINCS+ construit des signatures à partir de valeurs hachées. Les nouveaux remplaçants potentiels du cryptage RSA ne sont pas forcément interchangeables avec les systèmes existants. Certains sont beaucoup plus lents et d'autres n'offrent pas les mêmes options pour générer des signatures ou crypter les données. Beaucoup dépendent de clés beaucoup plus longues et une grande partie du travail actif est consacrée à la recherche de variantes qui utilisent des clés plus petites. Il n'est pas rare d'entendre parler de clés d'une taille de 500 kilo-octets ou plus, ce qui est nettement supérieur à la plupart des clés actuelles qui ne font que quelques centaines d'octets.

Des protocoles combinant plusieurs algorithmes distincts

Whitfield Diffie, un cryptographe qui a contribué à la création de la cryptographie à clé publique, fait remarquer que la mise en place des nouvelles propositions pourrait nécessiter davantage de calculs. « Il faudra probablement faire plus de mise en cache », déclare-t-il. « Si les systèmes post-quantiques sont plus coûteux en calcul que les systèmes actuels, il faudra peut-être consacrer une minute de calcul pour négocier une clé avec eBay ou Amazon, disons le 2 janvier, la conserver toute l'année et procéder à l'authentification de manière classique. » Les protocoles actuels négocient généralement une nouvelle clé pour chaque interaction. « Le fait d'exécuter moins souvent la génération de clés, plus coûteuse en calcul, peut aboutir au même coût global de calcul », explique encore Whitfield Diffie, mais au prix d'une « diminution du secret de transmission et de la valeur probante des signatures ».

Martin Hellman, qui fait également partie des premiers mathématiciens qui ont commencé à explorer la cryptographie à clé publique dans les années 1970, suggère que le monde pourrait avoir envie de développer de nouveaux protocoles combinant plusieurs algorithmes distincts. Au lieu de s'appuyer sur un seul algorithme pour créer la clé aléatoire permettant de chiffrer des données, le protocole devrait exécuter plusieurs algorithmes et combiner les clés de chacun d'entre eux en une seule clé (peut-être via XOR ou une fonction à sens unique plus élaborée). Depuis plus de dix ans, Martin Hellman réfléchit à la manière de survivre à l'effondrement d'un algorithme. L'ajout de ce type de sécurité à long terme permettrait d'éviter une situation de panique qui pourrait se produire si une attaque sérieuse apparaissait très soudainement. Mais même si ces ruptures catastrophiques ne se produisaient pas, celui-ci fait remarquer que même les plus petits incréments issus de l'évolution des algorithmes de factorisation (ou d'autres attaques) peuvent s'additionner. Une bonne solution pour les effondrements catastrophiques permettrait également de se défendre contre la lente augmentation de la puissance de calcul qui évolue au fil des années. « Certaines données qui sont secrètes aujourd'hui devraient l'être encore dans cinquante à cent ans », prévient Martin Hellman. « Ainsi, une avancée dans un futur aussi lointain pourrait avoir des implications dangereuses pour les données protégées d’aujourd’hui. »