Eine Angriffs-Methodik, die die Ressourcen zur Fälschung von RSA-Digital-Signaturen erheblich reduziert

Forscher der Universität Kalifornien in San Diego haben eine verbesserte Angriffstechnik auf den RSA-Algorithmus entwickelt, die es ermöglicht, digitale Signaturen zu fälschen, ohne die zugrunde liegenden Primzahlen von RSA zu faktorisieren oder den privaten Schlüssel wiederherzustellen. Die für einen Angriff auf einen 1024-Bit-RSA-Schlüssel erforderlichen Ressourcen werden auf 1380 Jahre Berechnungen auf einem einzelnen Prozessorkern geschätzt, was es dem universitären Cluster ermöglichte, innerhalb von 5 Monaten die erforderlichen Parameter zur Erstellung gefälschter RSA-Signaturen zu bestimmen (im Experiment wurden keine KI-Beschleuniger und GPUs verwendet; bei deren Einsatz könnte sich die Berechnungszeit erheblich verkürzen). Zum Vergleich benötigt die klassische Faktorisierungsmethode zur Wiederherstellung des RSA-1024-Schlüssels zwischen 500.000 und einer Million Jahren Berechnungen auf einem einzelnen Prozessorkern.

Um einen Angriff durchzuführen, muss die Möglichkeit bestehen, wiederholt Anfragen zum Signieren der vom Angreifer generierten Daten zu senden, beispielsweise indem man einen Authentifizierungsdienst oder ein HSM-Modul anspricht. Für die Bestimmung der RSA-1024-Parameter reicht es aus, 232 solcher Anfragen zu senden, während für den Angriff auf die RSA-2048-Schlüssel, die im Privacy Pass-Protokoll verwendet werden, 243 erforderlich sind. Nachdem ein Array signierter Daten empfangen wurde, beginnt ein langwieriger Prozess zur Berechnung der Parameter (für RSA-1024 etwa 265 Operationen), nach dessen Erhalt der Angreifer gefälschte Signaturen für beliebige Daten erstellen kann, wobei jede Signatur etwa 180 Stunden Berechnungen auf einem Kern erfordert.

Die Methode ist nur für RSA-Signaturen anwendbar, bei denen keine Formatierung und keine zusätzliche Auffüllung vor der Verschlüsselung (Padding) verwendet werden. Angriffe sind gegenüber Implementierungen von Blindsignaturen anfällig, darunter auch solche, die im Privacy Pass-Protokoll verwendet werden. Die meisten gängigen Implementierungen von RSA, einschließlich PKCS#1v1.5 und RSA-PSS (die in TLS und SSH verwendet werden), verwenden zusätzliche Auffüllung und sind gegen Angriffe immun.

Die Grundlage der RSA-Verschlüsselung ist die Potenzierung modulo einer großen Zahl. Der öffentliche Schlüssel enthält das Modul und den Exponenten. Das Modul wird auf der Grundlage von zwei zufälligen Primzahlen gebildet, die nur dem Besitzer des privaten Schlüssels bekannt sind. Die vorgeschlagene Methode basiert auf einer im Jahr 2007 veröffentlichten Studie, die bewiesen hat, dass das Herausziehen der Wurzel aus der im öffentlichen Schlüssel angegebenen Potenz einer verschlüsselten Nachricht ohne Informationen über die geheimen Faktoren eine weniger ressourcenintensive Operation ist als die Faktorisierung der Faktoren selbst.

Durch die Verwendung einer speziellen Methode namens Sieb des numerischen Feldes (SNFS) gelang es den Forschern, die Komplexität der Kompromittierung von RSA-1024-Schlüsseln auf 2^65 Operationen zu reduzieren, was praktische Angriffe auf modernen Clustern ermöglicht. Bei 2048-Bit RSA-Schlüsseln wird die Angriffs-Komplexität auf 2^90 geschätzt, was theoretisch von großen Unternehmen oder Geheimdiensten realisierbar ist. Für 4096-Bit Schlüssel liegt die Angriffs-Komplexität bei 2^119 Operationen, was in der Praxis derzeit noch unerreichbar ist, aber unter dem Mindestwert von 2^128, der von der NSA, dem National Institute of Standards and Technology und der Europäischen Agentur für Netz- und Informationssicherheit empfohlen wird.

Quelle: opennet.ru