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 avancée pour attaquer l'algorithme RSA, permettant de falsifier des signatures numériques sans avoir besoin de factoriser les nombres premiers sous-jacents à RSA ni de récupérer la clé privée. Les ressources nécessaires pour mener à bien une attaque sur une clé RSA de 1024 bits sont évaluées à 1380 ans de calculs sur un cœur de processeur, ce qui a permis, sur le cluster universitaire, de déterminer en 5 mois les paramètres nécessaires pour générer des signatures RSA fictives (aucun accélérateur AI ni GPU n'a été utilisé dans l'expérience, et avec leur utilisation, le temps de calcul peut être considérablement réduit). En comparaison, la méthode classique de factorisation nécessite entre 500 000 et un million d'années de calculs sur un cœur de processeur pour restaurer la clé privée RSA-1024.

Pour mener l'attaque, il est nécessaire de pouvoir envoyer plusieurs fois des demandes de signature des données générées par l'attaquant, par exemple en interrogeant un service d'autorisation ou un module HSM. Pour déterminer les paramètres RSA-1024, il suffit d'envoyer 232 demandes similaires, et pour attaquer les clés RSA-2048 utilisées dans le protocole Privacy Pass, 243. Une fois le tableau de données signées obtenu, un long processus de calcul des paramètres est lancé (environ 265 opérations pour RSA-1024), après quoi l'attaquant peut créer de fausses signatures pour n'importe quelles données, dépensant environ 180 heures de calculs sur un cœur pour chaque signature.

La méthode n'est applicable qu'aux signatures RSA qui ne utilisent pas de formatage et de remplissage supplémentaire avant le chiffrement (padding). Les implémentations de signature aveugle, y compris celles utilisées dans le protocole Privacy Pass, sont vulnérables à cette attaque. La plupart des implémentations courantes de RSA, y compris PKCS#1v1.5 et RSA-PSS (utilisées dans TLS et SSH), appliquent un remplissage supplémentaire et ne sont pas vulnérables à cette attaque.

L'algorithme de chiffrement RSA repose sur l'opération d'exponentiation modulaire d'un grand nombre. La clé publique contient le module et l'exposant. Le module est formé à partir de deux nombres premiers aléatoires, qui ne sont connus que du possesseur de la clé privée. La méthode proposée repose sur une étude publiée en 2007, qui a démontré que l'extraction de la racine d'un message chiffré à l'exposant indiqué dans la clé publique, sans information sur les multiplicateurs secrets, est une opération moins gourmande en ressources que la factorisation des multiplicateurs eux-mêmes.

En utilisant une méthode spéciale de crible sur les corps numériques (SNFS), les chercheurs ont réussi à réduire la complexité de la compromission des clés RSA-1024 à 265 opérations, ce qui permet de réaliser des attaques pratiques sur des clusters modernes. Pour les 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 services secrets. Pour les clés de 4096 bits, la complexité de l'attaque est de 2119 opérations, ce qui, dans la pratique, est encore inaccessibile, mais reste en dessous du minimum de 2128 recommandé par la NSA, l'Institut national des standards et de la technologie et l'Agence européenne de la sécurité des réseaux et de l'information.

Source : opennet.ru