Schwache RSA-Schlüssel mit 380 Jahre altem Faktorisierungsalgorithmus knacken
Drucker von Canon und Fujifilm benutzten eine fehlerhafte Krypto-Bibliothek: Deren Schlüssel waren verwundbar gegenüber einem 380 Jahre alten Verfahren.
(Bild: Thomas Kuhlenbeck)
Verschlüsselungsverfahren schützen tagtäglich Transaktionen, verifizieren Dokumente und sorgen für Authentizität. Das alles funktioniert, weil jeder an die Sicherheit des benutzten Verfahrens glaubt und den Entwicklern vertraut, die Verschlüsselung fehlerfrei in Software zu implementieren. Programmierfehler passieren jedoch auch hier. Um Fehler mit gefährlichen Konsequenzen zu vermeiden, nutzen viele Entwickler Krypto-Bibliotheken, die bereits viele Tests durchlaufen haben.
Problematisch wird es allerdings, wenn sich herausstellt, dass eine dieser Bibliotheken schwache RSA-Schlüssel generiert, die ausgerechnet mit einem 380 Jahre alten Verfahren knackbar sind. So war eine ganze Reihe von Druckern von Canon und Fujifilm verwundbar. Was also war passiert?
- Die 380 Jahre alte Faktorisierungsmethode von Fermat knackt schlecht erstellte RSA-Schlüssel in wenigen Sekunden.
- Programmierfehler in wichtigen Bibliotheken können schwerwiegende Folgen haben und Löcher in Sicherheitsnetze reißen.
- Mit unserem Python-Skript können Sie RSA-Module selbst abklopfen.
Recherche
Anfang März dieses Jahres prüfte der freie Journalist und Sicherheitsforscher Hanno Böck TLS-Zertifikate auf schwache Schlüssel. Zu seiner Überraschung stieß er auf ein paar RSA-Schlüssel, die anfällig für einen Angriff sind. Betroffen waren Drucker der Firmen Canon und Fujifilm (früher noch unter dem Namen Fuji Xerox), die wohl eine proprietäre Bibliothek der Firma Rambus verwendeten, in der sich der Fehler versteckte.
Mit dem Faktorisierungsalgorithmus des französischen Mathematikers Pierre de Fermat konnte er innerhalb von Sekunden den öffentlichen Schlüssel knacken. Fermat ist allerdings kein Sicherheitsforscher, der sich auf RSA spezialisiert hat: Der Mathematiker lebte von 1607 bis 1665.
Mit dem privaten Schlüssel könnte man sich mutmaßlich in den verschlüsselten Datenverkehr der Drucker einklinken, um Zugangsdaten oder andere vertrauliche Daten auszuspähen. Der Fehler blieb fast zwei Jahre lang unentdeckt, da Sicherheitsforscher und potenzielle Angreifer selten versuchen, Schlüssel genauer unter die Lupe zu nehmen, die eigentlich sicher sein sollten. Der Fehler in der Rambus-Bibliothek erhielt die Kennung CVE-2022-26320, mittlerweile hat Rambus den Schnitzer mit einem Patch beseitigt.
Eigentlich unknackbar
Bei korrekter Implementierung und ausreichender Schlüssellänge gilt das asymmetrische Verfahren RSA als unknackbar. Asymmetrisch heißt das Verfahren, weil es Paare aus je einem öffentlichen und einem privaten Schlüssel benutzt: Daten, die mit dem öffentlichen Schlüssel chiffriert wurden, lassen sich nur mit dem dazugehörigen privaten Schlüssel wieder lesbar machen und umgekehrt. Seine Sicherheit zieht das Verfahren daraus, dass es für die Schlüsselerstellung zwei gigantisch große Primzahlen miteinander multipliziert. Von hier aus ist es unglaublich schwierig, aus dem Ergebnis wieder die ursprünglichen Primzahlen zu gewinnen, da diese aufgrund ihrer speziellen Eigenschaften nicht mit einer Formel berechenbar sind und man so als Angreifer unendlich viele Kombinationen testen müsste.
So etwas nennen Mathematiker ein Falltürproblem: Die Multiplikation der Primzahlen erledigen Computer in Bruchteilen einer Sekunde, während die Faktorisierung des Ergebnisses selbst Supercomputern große Schwierigkeiten bereitet. Im RSA-Verfahren sorgt das dafür, dass es praktisch unmöglich ist, aus einem Schlüssel den jeweils anderen zu berechnen.
Das Produkt der beiden Primzahlen heißt RSA-Modul und ist Bestandteil des öffentlichen Schlüssels, den jeder besitzen kann und der später auch Teil des TLS-Zertifikates wird. Für den derzeitigen Standard von 2048 Bit benötigt RSA Primzahlen mit mehr als 300 Dezimalstellen. Diese werden nach einem bestimmten Schema ausgesucht, sodass das RSA-Modul im öffentlichen Schlüssel jedem Angriff trotzen kann.
Wie sich in der Analyse von Hanno Böck herausstellte, suchte der Primzahl-Algorithmus in der Rambus-Bibliothek zuerst eine große geeignete Primzahl und wählte danach die nächstgrößere aus. Ein fataler Fehler, der den Schlüssel direkt verwundbar machte für den Faktorisierungsalgorithmus von Fermat. Die Methode lohnt sich nämlich nur, wenn die Primfaktoren nahe beieinanderliegen. Das ist bei den gefundenen Schlüsseln der Fall. Ein Angreifer könnte ohne Weiteres mit dem Algorithmus das RSA-Modul in seine Primzahlen zerlegen und den privaten Schlüssel nachbauen. Bei normalen RSA-Schlüsseln mit weit auseinanderliegenden Primzahlen würde man dagegen ewig rechnen und nie zu einem Ergebnis kommen.
Korrespondenz aus Zahlen
Vermutlich kennen Sie den Namen Fermat noch aus dem Schulunterricht. Der Mathematiker prägte mit seinen Theoremen die Mathematik bis heute. Er gehört wie Euler, Laplace oder Gauß zu einer exklusiven Gruppe von Mathematikern, die berühmte Definitionen, Formeln und Algorithmen schufen, die nach ihnen benannt wurden.
Auch damals schon war man sich der Bedeutung der Primzahlen und deren vielseitiger Möglichkeiten bewusst. Fermat stellte seine Faktorisierungsmethode erstmalig in einem Brief an den Mathematiker Marin Mersenne vor, der zu dieser Zeit Primzahlen erforschte. Für eine gegebene Zahl errechnet die Methode die Primfaktoren. Fermat demonstrierte das Verfahren an der Zahl 2027651281, die es prompt in die Faktoren 46061 und 44021 zerlegte.
Alte Schule
Fermats Methode funktioniert so: Für eine gegebene Zahl N, die keine Primzahl ist, existieren Minimum zwei Faktoren, die es zu finden gilt. Ausgenommen vom Verfahren sind identische Faktoren, denn N kann in solchen Fällen nur eine Quadratzahl sein – 49 zum Beispiel ist eine solche Zahl, denn die Wurzel aus 49 ergibt 7.
Da abgesehen von der 2 alle Primzahlen ungerade sind, gibt es also eine theoretische Mitte zwischen den beiden Faktoren. Da beide Zahlen gleich weit von der Mitte entfernt sind, können Sie den Abstand beider Zahlen zur Mitte einfach b nennen und die Mitte a. Daraus folgt, dass N aus der kleineren Zahl (a − b) und der größeren Zahl (a + b) besteht – zusammengenommen ergibt das die Gleichung N = (a − b) · (a + b). Auf den ersten Blick mag das willkürlich wirken, aber die Mitte a lässt sich mit der Wurzel aus N gut annähern, sodass es sich lohnt, diese anschließend durch geschicktes Raten zu präzisieren. Zwei vollständige Rechenbeispiele können Sie in dem Kasten "Zahlenbeispiele" nachvollziehen.
Reine Mathematik mit Buchstaben wirkt auf den ersten und zweiten Blick ganz schön verwirrend, daher erklären wir im Folgenden zwei Beispiele mit Zahlen. Zuerst rät die Methode beim ersten Versuch korrekt und beim zweiten braucht es mehr Iterationen.
Das erste Modul besteht aus den Primzahlen 101 und 113. Multipliziert ergeben sie 11413. Mit der Wurzel des Moduls 11413 nähern Sie sich der Mitte zwischen den beiden Faktoren an: 106,83…, gerundet also 107. Spoiler: Wie Sie jetzt schon sehen können, liegt 107 perfekt in der Mitte zwischen 101 und 113.
Anschließend setzen Sie die Werte in die Formel b2 = a2 − N ein, 107 als a und N = 11413. Heraus kommt b2 = 1072 − 11413 = 11449 − 11413 = 36. Da es sich bei 36 um eine Quadratzahl handelt (√(36) = 6), haben Sie im gleichen Zug a = 107 als die Mitte bestätigt. Anschließend rechnen Sie die kleinere Primzahl mit 107 − 6 = 101 aus und die größere mit 107 + 6 = 113. Voilà, gleich beim ersten Versuch!
Als zweites Beispiel mit mehr Iterationen sei das Modul N = 15347 gegeben, dessen Primfaktoren wir vorerst nicht verraten. Die Wurzel aus N ergibt 123,88…, gerundet also 124. Wenn Sie die Werte wieder in die Gleichung einsetzen, kommt b2 = 1242 − 15347 = 29 heraus. Das ist aber keine Quadratzahl, daher müssen Sie a um eins erhöhen. Auch bei der zweiten Iteration kommt keine Quadratzahl heraus: b2 = 1252 − 15347 = 278. Aller guten Dinge sind drei, denn beim nächsten Versuch kommt b2 = 1262 − 15.347 = 529 heraus, was eine Quadratzahl ist (√(529) = 23). Die Primzahlen lauten also 126 − 23 = 103 und 126 + 23 = 149. Dass es sich um die korrekten Faktoren handelt, können Sie mit der Multiplikation 103 · 149 beweisen – das Ergebnis ist 15347.
Das geübte Auge erkennt in der Gleichung N = (a − b) · (a + b) die dritte binomische Formel. Keine Angst, niemand wird Sie in der Nacht wach klingeln und die Formeln abfragen! Sie können auch ohne das Wissen der binomischen Formeln die Klammern durch Multiplizieren auflösen, dann erhalten Sie N = a2 − b2.
Als Nächstes müssen Sie die Gleichung nach b2 umstellen, denn das ist der Wert, den Sie ausrechnen möchten. Die Formel lautet also am Ende b2 = a2 − N. N ist das RSA-Modul, das sie knacken wollen, und für a raten Sie eine Zahl. Wenn das Ergebnis b2 eine Quadratzahl ist, handelt es sich bei a um die gesuchte Mitte. Eine Quadratzahl liegt dann vor, wenn das Ergebnis von Wurzel aus b ganzzahlig ist.
Wüst nach Zahlen zu raten führt nicht zum Erfolg, daher brauchen Sie zuerst einen guten Startwert. Wie zuvor erwähnt lohnt es sich, als ersten Wert für a die Wurzel aus N zu nehmen, da diese recht mittig zwischen den beiden Faktoren liegen sollte. Dabei kommt eine Kommazahl heraus, die Sie auf eine Ganzzahl runden können – wenn nicht, ist N eine Quadratzahl.
Bei sehr nahe beieinanderliegenden Zahlen ist der erste Versuch schon genau genug und Sie erhalten die Faktoren. Wenn nicht, dann müssen Sie a verfeinern: Wenn b keine Quadratzahl ist, dann zählen Sie a um 1 hoch und rechnen die Formel nochmal aus. Je weiter die Zahlen voneinander entfernt sind, desto mehr Iterationen brauchen Sie. Haben Sie die Mitte a gefunden und die Abweichung b, dann müssen Sie nur noch die Faktoren (a – b) und (a + b) berechnen.
Neue Schule
Wenn Sie die Iterationen nicht aufwendig per Hand durchrechnen wollen, können Sie unser Python-Skript zum Herumspielen und Erweitern benutzen (siehe Listing "Fermat-Angriff" bei GitHub). Die zwei Dutzend Zeilen sind platzsparend angelegt und tun nur das Nötigste, trotzdem zerlegt das Programm ohne Weiteres RSA-Module, Primzahlen oder Quadratzahlen.
Fermat-Angriff
import math
MODUL = 18487289 * 18543067
def attack(guess, max_tries=1000000):
for tries in range(max_tries):
b = pow(guess + tries, 2) - MODUL
if b >= 0 and pow(math.isqrt(b), 2) == b:
return guess + tries, math.isqrt(b), tries + 1
return 0, 0, max_tries
def main():
first_try = math.isqrt(MODUL)
a, b, tries = attack(first_try)
prime1 = a - b
prime2 = a + b
if a != 0:
print(
f"Es braucht {tries} Versuche, um die Faktoren {prime1} und {prime2} zu finden.")
else:
print(f"Kein Treffer in {tries} Versuchen.")
if __name__ == "__main__":
main()
Der Faktorisierungsalgorithmus von Fermat braucht 23 Durchläufe, um das Beispielmodul 342811038575363 in seine Primfaktoren 18487289 und 18543067 aufzuteilen. Sollte das Programm die Abweichung b von der Mitte a in einer Million Versuchen nicht erraten können, bricht das Programm ab.
Als Beispiel für das RSA-Modul können Sie hinter MODUL = jede x-beliebige Zahl eintippen. Eine Größenbeschränkung gibt es dabei nicht: Pythons Integer-Arithmetik rechnet mit beliebig großen Zahlen, solange sie in den Hauptspeicher passen. Als Beispiel vorgewählt ist das fünfzehnstellige Modul 342811038575363 aus den Primfaktoren 18487289 und 18543067. Das Programm arbeitet auf die gleiche Weise wie gerade eben erklärt. Zuerst nähern Sie sich in der main()-Methode mit der Wurzel von N (im Code MODUL) an die Mitte der beiden Faktoren an:
first_try = math.isqrt(MODUL)Die Methode isqrt() zieht die Ganzzahl-wurzel aus dem MODUL, das heißt, isqrt(n) liefert die größte ganze Zahl w, für die w*w <= n gilt. Der Rückgabewert ist also immer abgerundet. Anschließend übergeben Sie den Startwert an die Methode attack(), die in einer for-Schleife die Iterationen durchspielt, bis b eine Quadratzahl ergibt. Der Einfachheit halber heißt die Variable für b2 in der Methode nur b. Die Abfrage
if b >= 0 and pow(math.isqrt(b), 2) == b:
return guess + tries, math.isqrt(b), tries + 1fängt im ersten Teil negative b-Werte ab, die aufgrund der zwangsweisen Rundung zu kleineren Zahlen entstehen können. Im zweiten Teil prüft sie, ob b eine Quadratzahl ist. Dafür verwenden wir einen kleinen Trick: pow(math.isqrt(b), 2) quadriert das Ergebnis der Wurzel von b. Nur wenn dabei wieder b herauskommt, war das Ergebnis nicht gerundet – b ist folglich eine Quadratzahl.
Wenn die Werte nicht übereinstimmen, kommt b nicht als Kandidat infrage. Stattdessen verfeinern Sie die Annäherung an die Mitte, indem Sie a um 1 hochzählen. Die Extra-Variable tries kümmert sich stellvertretend darum.
Wenn nach ein paar Iterationen b sich als eine Quadratzahl herausstellt, also die Abfrage
pow(math.isqrt(b), 2) == berfüllt ist, dann gibt die Methode gleich drei Werte zurück: zuerst die erratene Mitte a, im Code guess + tries, danach die Abweichung b zu den Faktoren (math.sqrt(b)) und zu guter Letzt die Variable tries, welche die Iterationen gezählt hat. Wenn attack() nach einer Million Versuchen die Mitte nicht erraten konnte, signalisiert sie das, indem sie für a und b den Wert 0 zurückgibt; die Anzahl der Versuche können Sie durch Ändern von max_tries anpassen.
main() nimmt die Variablen auf, berechnet danach die beiden Primzahlen
prime1 = a - b
prime2 = a + bund gibt diese mit der Anzahl der Iterationen aus. Für das Beispiel-Modul lautet die Ausgabe: "Es braucht 23 Versuche um die Primzahlen 18487289 und 18543067 zu finden." Falls für Ihr gewähltes Modul Zahlen herauskommen, die keine Primzahlen sind, dann können Sie das Programm für beide Faktoren so lange anwenden, bis Sie diese in seine Primfaktoren zerteilt haben.
Letzte Worte
Wenn Sie mal auf der Suche nach schwachen RSA-Schlüsseln sind und diese überprüfen wollen, dann wissen Sie jetzt, wie Sie es mit der Faktorisierungsmethode von Fermat probieren können. Moral der Geschichte bleibt wohl, dass nicht alles, was sicher scheint, auch wirklich sicher ist. Vertrauen ist gut, Kontrolle ist besser: Dass viele die Sicherheit der Schlüssel nicht hinterfragt haben, war vermutlich der einzige Grund, weshalb es keine schwerwiegenden Angriffe gegeben hat. Manchmal braucht es eben einen Sicherheitsforscher, der nochmal genauer hinschaut und angeblich unknackbare Schlüssel unter die Lupe nimmt.
(wid)
