RSA-Schwachstelle entdeckt

[Annika_Kremer]

Forscher der Universität Michigan behaupten, eine Schwachstelle in der aktuellen Implementierung des beliebten Verschlüsselungs-Algorithmus RSA entdeckt zu haben. RSA ist sehr beliebt und wird sowohl zum Verschlüsseln als auch für digitale Signaturen benutzt.

zur News

[charminderbaer]

Hätte mich schon sehr verwundert, wenn jemand im Algorithmus selber eine Schwachstelle gefunden hätte.

[liany]

Hätte mich schon sehr verwundert, wenn jemand im Algorithmus selber eine Schwachstelle gefunden hätte.

Nicht direkt im RSA Algorithmus aber es ist eine "Angriffsoptimierung", heißt es geht schneller.

Die Signaturberechnung in OpenSSL spielt hier aber auch eine Rolle:

[...]The second contribution is the dis-
covery of a severe vulnerability in the software implementation of
RSA authentication in OpenSSL,which can be expoited to perform
fault-based attacks.
[...]
The fixed-window exponentiation algorithm in the OpenSSL li-
brary does not validate the correctness of the signature produced
before sending it to the client,a vulnerability that we exploit in our
attack.

Die Attacke ist zwar noch nicht sonderlich alltagstauglich aber den Ansatz find ich trotzdem gut..."out of the box"
gedacht und eine gute Kombination aus Hard&Software....gefällt mir.

Man setz auf einen hardwareseitigen "Fehler" im Rechenwerk des Multizieres in einem Chip der design-/spannungs- und temperaturabhängig ist.
Das heißt bei jedem Chip durch die äußeren Bedingungen wohl etwas anders. Der "Fehler" besteht darin, dass wenn die Spannung zu gering ist die "Elektronen während eines Taktes nicht bis zum Ende der Leitung ins Register" kommen und somit ein falsches Ergebnis bei der Multiplikation entsteht. Für die Attacke muss der Fehler in einem einzelnen Bit, also "in einer einzigen Leitung", auftreten. Die Software (hier OpenSSL) überprüft das Endergebnis nicht und schickt es an den Client.
Und noch paar Zahlen hinterher:
Von 10.000 Signaturen, waren 8800 fehlerhaft. Von diesen 8800 waren nur 1015 1-Bit Fehler. Von diesen 1015 Signaturen waren 650 nötig um den 1024bit Schlüssel zu berechnen. Die 104h Rechenzeit beziehen sich auf 8800 Signaturen zerlegt auf 80 Pentium 4 a 2.4GHz . Eigentlich gar keine soooo große Rechenleistung.

Danke an die Redaktion für den Link zum Original

[Novgorod]

kurze verständnisfrage: wieso kann man aus einer signierten antwort mit (genau einem?) bitfehler den privaten schlüssel rekonstruieren? muss man dafür alle deteils des verfahrens verstehen, oder lässt sich das "kurz" erklären?

außerdem: wenn man zugriff auf die spannungsversorgung der hardware hat, auf der der private schlüssel gespeichert ist, sollte man dann nicht normalerweise auch "physischen" zugriff auf den datenträger haben und den schlüssel direkt auslesen können?

[liany]

außerdem: wenn man zugriff auf die spannungsversorgung der hardware hat, auf der der private schlüssel gespeichert ist, sollte man dann nicht normalerweise auch "physischen" zugriff auf den datenträger haben und den schlüssel direkt auslesen können?

Der private Schlüssel ist in dem Fall nicht auf der Festplatte sondern in einem Chip eingebrannt gewesen und lässt sich nicht einfach auslesen.

kurze verständnisfrage: wieso kann man aus einer signierten antwort mit (genau einem?) bitfehler den privaten schlüssel rekonstruieren? muss man dafür alle deteils des verfahrens verstehen, oder lässt sich das "kurz" erklären?

Durch den 1-Bit Fehler beeinflusst man gezielt den RSA Berechnungsalgorithmus in einer bestimmten Art und Weise, die sich in einer Formel ausdrücken lässt. Man hat also die Original RSA-Formel und die modifizierte RSA-Formel. Aus beiden lässt sich durch Formelschubserei ein Bit des private keys an einer bestimmten Stelle berechnen. Unabhängig davon können durch eine weitere Formel aus bereits gefundenen Bits und falschen Signaturen weitere Bits berechnet werden.

etwas detaillierter:
Bei der Berechnung der RSA-Signatur in OpenSSL wird ein Algorithmus(Fixed Window Exponentiation) verwendet der unter anderem eine Zahl exponentieren muss. Und das in einer Dimension die sich nicht auf einem PC (egal ob 32 oder 64 Bit) in einem Rutsch durchführen lässt. Die Berechnung wird in Blöcke(Windows) geteilt und in kleineren Multiplikationen erledigt(pdf 3.1). Hier kommt es dann durch die Spannungsmanipulation zum 1-Bit Fehler, der bewirkt das dieser Block vom Endergebnis falsch berechnet wird(pdf 3.1). Die Art des Fehlers ist ja bekannt, 1-Bit heißt entweder 0=>1 oder 1=>0 was einer Addition oder Subtraktion von 2^f (f ist die Bitposition) gleichkommt. Die RSA Berechnungsformel ändert sich also auf eine bestimmte Art und Weise(pdf 4.1).
Die Blockgröße ist durch den Berechnungsalgorithmus vorgegeben, also bekannt. Die Länge des private keys, und der public key sind auch bekannt. Die falsche Signatur wird in die passenden Blöcke zerlegt(pdf 5.1).
Durch ein bisschen Formeln hin und her schubsen(pdf Appendix A) kommt man auf eine Gleichung mit 3 Unbekannten (pdf, Appendix A, Formel 7). Eine dieser Unbekannten ist ein einzelnes Bit des private keys an einer bestimmten Stelle. Die Grenzen der 3 Unbekannten sind bekannt. Jetzt werden alle Kombinationen der Unbekannten durchprobiert. Wenn es exakt eine einzige Lösung gibt hat man 1 Bit des private keys an einer bestimmten Stelle gefunden. Das wiederholt man nun mit allen Signaturen. Nebenbei kann man, wenn man eine gewisse Anzahl zusammenhängender Bits des private keys gefunden hat, durch eine weitere Formel(pdf Appendix A, Formel 10) versuchen ein weiteres Bit zu berechnen. So kommt es dann, dass man für einen 1024 Bit Schlüssel nicht 1024 Signaturen braucht.

[Novgorod]

danke für die erklärung!