Une méthode d'attaque qui réduit considérablement les ressources nécessaires pour falsifier les signatures numériques RSA

Des chercheurs de l'Université de Californie à San Diego ont développé une technique d'attaque avancée contre l'algorithme RSA, permettant de falsifier des signatures numériques sans factoriser les nombres premiers à la base de RSA et sans avoir besoin de restituer la clé privée. Les ressources nécessaires pour mener une attaque sur une clé RSA de 1024 bits sont évaluées à 1380 ans de calculs sur un seul cœur de processeur, ce qui a permis, sur le cluster de l'université, de déterminer les paramètres nécessaires à la formation de faux RSA-signatures en 5 mois (aucun accélérateur AI ni GPU n'ont été utilisés lors de l'expérience, et leur utilisation pourrait réduire considérablement le temps de calcul). En comparaison, la méthode classique de factorisation nécessite de 500 000 à un million d'années de calculs sur un cœur de processeur pour recréer la clé privée RSA-1024.

Pour mener l'attaque, il est nécessaire d'avoir la possibilité d'envoyer plusieurs fois des requêtes pour signer les données générées par l'attaquant, par exemple, en s'adressant à un service d'autorisation ou à un module HSM. Pour déterminer les paramètres RSA-1024, il suffit d'envoyer 232 requêtes de ce type, tandis que pour l'attaque sur les clés RSA-2048 utilisées dans le protocole Privacy Pass, 243 requêtes sont nécessaires. Après avoir obtenu un ensemble de données signées, un long processus de calcul des paramètres est lancé (pour RSA-1024, environ 265 opérations sont nécessaires), après quoi l'attaquant peut créer des signatures fausses pour n'importe quelles données, en consacrant environ 180 heures de calcul sur un seul cœur pour chaque signature.

La méthode est applicable uniquement aux signatures RSA, où aucun formatage ni ajout de remplissage n'est utilisé avant le chiffrement (padding). Les mises en œuvre de la signature à l'aveugle, y compris celles utilisées dans le protocole Privacy Pass, sont vulnérables. La plupart des mises en œuvre de RSA courantes, y compris PKCS#1v1.5 et RSA-PSS (utilisées dans TLS et SSH), appliquent un remplissage complémentaire et ne sont pas vulnérables à cette attaque.

À la base du chiffrement RSA se trouve l'opération d'exponentiation modulo un grand nombre. La clé publique contient le module et l'exposant. Le module est formé sur la base de deux grands nombres premiers aléatoires, connus uniquement du propriétaire de la clé privée. La méthode proposée repose sur une étude publiée en 2007, qui a prouvé que l'extraction de la racine à l'exposant indiqué dans la clé publique à partir d'un message chiffré, sans information sur les facteurs secrets, est une opération moins gourmande en ressources que la factorisation des facteurs eux-mêmes.

En utilisant une méthode spéciale de criblage des champs numériques (SNFS), les chercheurs ont réussi à réduire la complexité de la compromission des clés RSA-1024 à 265 opérations, permettant ainsi des attaques pratiques sur des clusters modernes. Pour des clés RSA de 2048 bits, la complexité de l'attaque est estimée à 290, ce qui est théoriquement réalisable par de grandes entreprises ou des agences gouvernementales. Pour des clés de 4096 bits, la complexité de l'attaque s'élève à 2119 opérations, ce qui est encore inaccessibile dans la pratique, mais en dessous du minimum de 2128 recommandé par la NSA, l'Institut national des normes et de la technologie et l'Agence européenne de cybersécurité.

Source : opennet.ru