RSA-Angriff ohne Faktorisierung: Forscher zeigen, wie sich digitale Signaturen fälschen lassen. Moderne RSA-Systeme sind vorerst geschützt.
Ein Forschungsteam von der University of California in Zusammenarbeit mit dem französischen Forschungsinstitut Inria hat einen neuen Angriff auf RSA demonstriert. Dabei lassen sich digitale RSA-Signaturen bei Blind-Signature-Verfahren auf Basis von Textbook RSA auch ohne vorherige Faktorisierung fälschen. Unter Faktorisierung ist die Zerlegung des öffentlichen RSA-Modulus in seine beiden geheimen Primfaktoren zu verstehen. Für moderne Implementierungen besteht derzeit keine akute Gefahr. Problematisch sind vielmehr ältere RSA-Verfahren, die einem Angreifer Zugriff auf ein geeignetes Signatur-Oracle ermöglichen.
RSA: Sicherheit durch schwer lösbare Mathematik
Das RSA-Kryptosystem zählt bereits seit Jahrzehnten zu den bekanntesten Verfahren der digitalen Kryptografie. Es kommt sowohl zur Verschlüsselung als auch zur Erstellung digitaler Signaturen zum Einsatz. RSA arbeitet mit einem Schlüsselpaar aus öffentlichem und privatem Schlüssel. Der öffentliche Schlüssel kann etwa zum Verschlüsseln von Daten und zur Überprüfung von Signaturen dienen. Der private Schlüssel wird zum Entschlüsseln und Signieren benötigt.
Der RSA-Modulus ist eine sehr große Zahl, die bei der Erzeugung eines RSA-Schlüssels aus zwei miteinander multiplizierten Primzahlen entsteht. Er ist Bestandteil des öffentlichen Schlüssels und damit für jeden einsehbar. Die beiden ursprünglichen Primzahlen bleiben dagegen geheim. Will ein Angreifer den privaten Schlüssel auf herkömmlichem Weg aus dem öffentlichen Schlüssel ableiten, müsste er diese Primzahlen zurückgewinnen. Die Primfaktorzerlegung, auch Faktorisierung genannt, ist bei großen Zahlen extrem aufwändig. Für ausreichend große Schlüssel gilt das mit klassischer Rechenleistung als praktisch nicht durchführbar. Auf dieser Schwierigkeit beruht im Wesentlichen die Sicherheit von RSA. Benannt ist das Verfahren nach seinen Entwicklern Ron Rivest, Adi Shamir und Leonard Adleman, die RSA 1977 veröffentlichten.
Noch sind Quantencomputer nicht leistungsfähig genug, um RSA auf diesem Weg praktisch zu brechen. Ein entsprechend leistungsfähiges System könnte jedoch die Faktorisierung großer Zahlen drastisch beschleunigen.
Ein Forschungsteam um Laura Shea, Miro Haller, Adam Suhl und Nadia Heninger von der University of California, San Diego sowie Emmanuel Thomé vom französischen Forschungsinstitut Inria hat nun einen anderen gangbaren Weg aufgezeigt. Ihr RSA-Angriff kann dabei gültige Signaturen erzeugen, ohne den privaten Schlüssel zuvor durch Faktorisierung zu rekonstruieren. Statt den Schlüssel auf dem klassischen Weg zu berechnen, nutzt das Verfahren eine andere kryptanalytische Schwachstelle aus.
RSA-Angriff umgeht die klassische Faktorisierung
Das Forschungsteam beschreibt die Methode in einem bei IACR veröffentlichten Paper mit dem Titel „Forging 1024-bit RSA signatures in nearly SNFS time“. Der Angriff zielt auf RSA-Blind-Signaturen auf Basis von Textbook RSA und die Möglichkeit, einem Signatur-Oracle gezielt Anfragen zu stellen. Dabei kann der Angreifer ausgewählte Eingaben signieren lassen und erhält jeweils eine gültige RSA-Signatur zurück, ohne den privaten Schlüssel zu kennen.
Die Forscher kombinieren diese Abfragemöglichkeit mit einer Variante des Number Field Sieve (NFS), einem Verfahren zur Faktorisierung großer Zahlen. Die Antworten des Signatur-Oracles liefern dabei zusätzliche Informationen, die sich nutzen lassen, um eine gültige Signatur für eine vom Angreifer ausgewählte Nachricht zu erzeugen. Dadurch umgehen die Forscher die klassische Faktorisierung des RSA-Modulus, ohne den privaten Schlüssel rekonstruieren zu müssen.
Moderne RSA-Implementierungen verwenden für Signaturen in der Regel Verfahren wie PKCS#1 v1.5 oder RSA-PSS. Dabei wird die zu signierende Nachricht in ein festgelegtes Format überführt. Die üblichen Signatur-Schnittstellen stellen dadurch kein frei nutzbares Raw-RSA-Oracle bereit, das der Angreifer mit beliebigen Eingaben füttern könnte. Jedoch ist diese Zugriffsmöglichkeit eine Voraussetzung für den neuen Angriff. Laut Einschätzung der Forscher stellt die Methode deshalb für die verbreitete Verwendung von RSA mit PKCS#1- oder PSS-Signaturen derzeit keine praktische Bedrohung dar. Problematischer sind spezielle Anwendungen wie Blind-RSA-Signaturen oder HSM-Schnittstellen, die rohe RSA-Operationen zulassen.
1024-Bit-RSA bereits praktisch angegriffen
Die Forscher demonstrierten ihren Ansatz auch praktisch an 1024-Bit-RSA. Dafür waren herkömmlich rund 1.380 CPU-Kernjahre Rechenzeit erforderlich. Eine direkte Faktorisierung eines 1024-Bit-RSA-Schlüssels wird mit einem Aufwand von ungefähr 2^80 Operationen und mehreren Hunderttausend CPU-Kernjahren veranschlagt.
Für die demonstrierte Signaturfälschung ergibt sich eine Größenordnung von etwa (2^{65}) Operationen. Damit sinkt die angenommene Sicherheitsstärke von 1024-Bit-RSA auf ein Niveau, das aus heutiger Sicht nicht mehr als ausreichend gilt.
Nach der Analyse der Forscher sinkt die effektive Sicherheitsstärke des Verfahrens bei 2048-Bit-RSA auf etwa 2^90 und bei 4096-Bit-RSA auf etwa 2^119 Operationen. Die Forscher gehen zudem davon aus, dass sich der Aufwand durch eine optimierte Implementierung weiter reduzieren ließe. Für ihre Demonstration kamen weder GPUs noch KI-Unterstützung zum Einsatz.
Die veröffentlichten Ergebnisse sind noch Gegenstand wissenschaftlicher Prüfung. Ars Technica zitiert den Kryptografieexperten Karsten Nohl mit der Einschätzung, dass das Ergebnis, sollte es sich im Peer-Review bestätigen, einen konzeptionellen Durchbruch darstellen könnte.
Konkretes Einsatzgebiet: Privacy Pass
Privacy Pass dient als konkretes Beispiel für einen möglichen Anwendungsfall des Angriffs. Das Protokoll ermöglicht es Nutzern, gegenüber einem Dienst Berechtigungen nachzuweisen, ohne dabei Informationen über ihre Identität preiszugeben. Die Technik wird eingesetzt, um Zugriffe zu ermöglichen, ohne dass Nutzer bei jeder Anfrage erneut ein CAPTCHA lösen müssen. Stattdessen kommen kryptografisch abgesicherte Tokens zum Einsatz.
Laut den Forschern gehört auch Privacy Pass zu den Anwendungen, bei denen Blind-RSA-Signaturen ein geeignetes Signatur-Oracle bereitstellen können. Cloudflare dokumentiert den Einsatz von Blind RSA in seinem Privacy-Pass-System. Auch Apple nutzt entsprechende Privacy-Pass-Techniken.
Für einen Angriff auf eine solche Infrastruktur wären nach den Berechnungen der Forscher rund (2^{43}) Signatur- beziehungsweise Token-Anfragen erforderlich. Hinzu kommt der eigentliche Rechenaufwand des Angriffs. Die Forscher betonen, dass ein Angreifer dafür zunächst Zugriff auf die entsprechende Signatur-Infrastruktur benötigen würde. Regelmäßige Schlüsselwechsel können das verfügbare Zeitfenster zusätzlich verkürzen und erschweren einen erfolgreichen Angriff.