So testen Sie

Voraussetzung ist die Installation von gcc und einer verwundbaren Version von OpenSSL.

Für den Fehler in BN_mod_sqrt(): Kompilieren Sie mit gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, führen Sie ./my_bad_sqrt aus und beobachten Sie, wie es für immer hängt! :D

Mit einem Zertifikat: Führen Sie openssl x509 -in certs/cert.der.new -inform DER -text -noout in der Befehlszeile aus; auch dies führt zum Hängen.

Die Schleife treffen

Die Funktion BN_mod_sqrt() implementiert den Tonelli-Shanks-Algorithmus zum Finden einer modularen Quadratwurzel, d.h. gegeben eine ganze Zahl a und eine Primzahl p, gibt sie einen Wert r zurück, so dass r^2 == a (mod p).

Bei der Analyse des Commits, der die Sicherheitslücke patcht, sehen wir, dass der Übeltäter die Schleife ist, die den kleinsten Index i findet, für den b^(2^i)==1 (mod p) gilt, wobei b zuvor im Algorithmus definiert wird.

Die Schleife wird geändert von

zu

Im zweiten Fall gibt es eine for-Schleife, die durch die Variable e begrenzt ist; im ursprünglichen Code gibt es jedoch nur eine Prüfung auf den Fall i==e innerhalb einer while-Schleife.

Da diese Schleifen sich innerhalb einer größeren Schleife befinden, die bei jeder Iteration den neuen Wert von e auf den aktuellen Wert von i setzt, versuchen wir die folgende Angriffsstrategie:

1. Bei der ersten Ausführung der äußeren Schleife erreichen wir, dass am Ende i=1 ist; dafür benötigen wir, dass b^2=1 (mod p).
2. Auf diese Weise haben wir während der zweiten Ausführung e=1, und wenn wir in die innere Schleife gelangen, wird die Prüfung i==e immer fehlschlagen.
3. Wenn wir es schaffen, immer t != 1 (mod p) zu haben, bleiben wir für immer in der Schleife.

Beachten Sie, dass die ersten beiden Schritte tatsächlich in einer „normalen“ Ausführung stattfinden können, d.h. mit einer Primzahl p. Wenn p jedoch zusammengesetzt ist, können wir auch den dritten Schritt erfüllen!

Ein wenig Mathematik

Der Tonelli-Shanks-Algorithmus funktioniert, indem er p - 1 = 2^e * q schreibt, mit einem ungeraden q. Dies ist auch die Ordnung der multiplikativen Gruppe der ganzen Zahlen modulo p, und die Werte e und q werden während der Ausführung mehrfach verwendet; wenn p jedoch nicht prim ist, wird die Ordnung der multiplikativen Gruppe nicht p-1 sein, und dies wird uns helfen, in die Endlosschleife zu geraten.

Insbesondere wird b initialisiert als b = a^q (mod p), was bedeutet, dass, wenn p prim wäre, b die Ordnung einer Potenz von 2 hätte, die wir dann mit der Schleife finden würden.

Aber wenn wir p = r * s setzen, ist die Ordnung der multiplikativen Gruppe (r-1)*(s-1) = r*s - r - s + 1 anstelle von r*s-1. Der Algorithmus verwendet den q-Wert, um ein Element y mit der exakten Ordnung 2^e zu erhalten; wenn p jedoch nicht prim ist, hat der q-Wert keine besondere Bedeutung für die Ordnung, sodass das Element y keine Ordnung einer Potenz von zwei modulo p=r*s haben wird.

Da am Ende der ersten äußeren Schleife b gesetzt wird auf b = b*y^(e-i) (mod p), wird die innere Schleife bei ihrer zweiten Iteration versuchen, einen Wert i zu finden, für den b^(2^i) == 1 (mod p) gilt, aber fehlschlagen, da nicht mehr garantiert ist, dass y eine Ordnung hat, die eine Potenz von zwei ist.

Der Exploit

Die Zahlen im Exploit sind sehr einfach: Wir nehmen r=17,s=41, was p=r*s=697 ergibt. Dies bedeutet, dass die berechneten Werte von e und q p-1 = 2^3 * 87 sein werden.

Wir wählen dann a=696, was bedeutet, dass a == -1 (mod p) und auch b == -1 (mod p) bei der Initialisierung. Dies erfüllt Schritt 1, indem e=1 für die folgende äußere Schleife gesetzt wird.

Dann wird b auf ein Element gesetzt, dessen Ordnung keine Potenz von 2 ist, und die innere Schleife bleibt stecken, während sie versucht, ein i zu finden, für das b^(2^i)==1 (mod p) gilt.

Erstellen eines gefährlichen Zertifikats

OK, jetzt lassen Sie uns ein gefährliches Zertifikat erstellen, das ungültige explizite Kurvenparameter mit einem Basispunkt in komprimierter Form enthält.

Die Dateien dieses Abschnitts befinden sich im Ordner certs.

Erstellen eines normalen Zertifikats mit expliziten Kurvenparametern

Zuerst müssen wir einen EC-Private-Key erstellen. Da wir ein Zielzertifikat mit expliziten Kurvenparametern möchten, sollte der Schlüssel ebenfalls explizite Kurvenparameter enthalten.

Dann haben wir der Einfachheit halber ein selbstsigniertes Zertifikat erstellt und im DER-Format ausgegeben.

Lassen Sie uns die Zertifikatsinformationen überprüfen. Es enthält wie erwartet explizite Kurvenparameter.

Ein ungültiges Zertifikat erstellen

Jetzt müssen wir die Werte dieser Parameter ändern: Prime, A, B, Generator. Sie erfüllen die folgende Gleichung

wobei p die Primzahl (Prime) ist, a der Parameter A und b der Parameter B. p, a, b bestimmen zusammen eine Kurve. Das Dekomprimieren eines Punktes bedeutet, die Y-Koordinate aus der entsprechenden X-Koordinate zu berechnen.

Offensichtlich sollte eine modulare Quadratwurzeloperation verwendet werden, die BN_mod_sqrt() aufruft.

Basierend auf der Arbeit von Drago-96 nehmen wir p=697, x^3+ax+b=696. Und dann müssen wir nur geeignete a, b, x wählen, die die zweite Gleichung erfüllen. Wir nehmen hier x=8, a=23, b=0.

OK, jetzt können wir beginnen, das Zertifikat zu bearbeiten. Das manuelle Bearbeiten der ASN.1-Struktur ist wirklich mühsam. Ich habe das Tool xxd verwendet, um das Zertifikat in das Hex-Format umzuwandeln, und es dann mit vim bearbeitet. Nach Abschluss der Bearbeitung habe ich es mit xxd -r zurückgewandelt.

Ich habe kein bequemeres Tool gefunden. Falls jemand ein solches Tool kennt, bitte teilen Sie es in den Kommentaren mit.

Die Schritte zum Erstellen sind grob wie folgt:

1. Ändern Sie die Werte von Prime, A, B, Generator
   1. Ändern Sie Prime auf 697, d.h. 0x2b9 in hex
   2. Ändern Sie A auf 23, d.h. 0x17 in hex
   3. Ändern Sie B auf 0
   4. Ändern Sie die X-Koordinate des Generators auf 8, d.h. 0x020008 (oder 0x030008) bei Kodierung im komprimierten Format
2. Da OpenSSL das Padding-Format von ASN1_INTEGER überprüft, sollte Prime keine führenden 0-Bytes enthalten, daher müssen wir die Länge von Prime ändern
3. Ähnlich vergleicht OpenSSL die Länge von Prime mit der Länge des Punkt-Strings, daher sollte die Länge der X-Koordinate des Generators mit Prime übereinstimmen. Deshalb setzen wir Generator auf 030008 und nicht auf 0308.
4. Da die ASN.1-Struktur des Zertifikats verschachtelt ist, sollten auch alle Längen der externen Objekte korrigiert werden.
5. Beachten Sie, dass nach dem Ausführen von xxd -r möglicherweise ein unerwünschtes abschließendes Zeilenumbruch-Zeichen (0x0a) am Ende der Datei vorhanden ist. Entfernen Sie es.

Werfen wir nun einen Blick auf die ASN.1-Struktur des normalen Zertifikats. Die mit roter Linie markierten Teile sind zu ändern.

Die Längen vor und nach der Änderung sind wie folgt aufgeführt:

Verwendung von ASN1-Vorlagen

Aktualisiert am 21.03.2020:

Eine viel einfachere Methode ist die Verwendung des Tools asn1template von wllm-rbnt.

Klonen Sie das Repository:

Generieren Sie eine DER-Vorlage aus diesem Zertifikat:

Ändern Sie dann die oben erwähnten Parameter:

Konvertieren Sie es mit ASN1_generate_nconf(3) zurück in DER-kodiertes ASN1:

Die Ausgabe cert_new.der entspricht der manuell bearbeiteten Version.

Wir haben nun erfolgreich ein ungültiges Zertifikat erstellt. Sehen wir uns die neue ASN.1-Struktur an:

Alle roten Teile wurden geändert, und das Zertifikat kann korrekt DER-dekodiert werden.

Test mit dem ungültigen Zertifikat

Versuchen wir nun, das Zertifikat zu parsen. Der Prozess wird in die Endlosschleife geraten, wenn alles wie erwartet funktioniert.

Wie gezeigt, beträgt die CPU-Auslastung von openssl 100 %, und der Aufrufstapel befindet sich innerhalb von BN_mod_sqrt().

Wenn ein böswilliger Angreifer ein solches manipuliertes Zertifikat während des SSL-Handshakes mit dem Server sendet, gerät der Server in die Endlosschleife, was einen DoS-Angriff verursacht.

Erstellen eines Zertifikats, alternative Methode

Wir werden versuchen, ein Zertifikat mit der OpenSSL-C-libcrypto-Bibliothek zu erstellen.

Wie wir gesehen haben, müssen wir eine Kurve mit nicht-prime Basis-Feld verwenden und Punkte in komprimierter Form kodieren, sodass wir beim Parsen auf den Fehler in BN_mod_sqrt() stoßen.

Dies kann erreicht werden, indem y^2 = x^3 + 1*x + 694 (mod 697) als Kurve mit (1, 132) als Generator gesetzt wird; dies ruft BN_mod_sqrt() mit genau denselben Parametern wie in my_bad_sqrt auf.

Das Ausführen von gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group generiert die Datei my_bad_group.der, die die ECparams im DER-Format enthält.

Der Versuch, diese Parameter mit OpenSSL zu parsen, führt zur Endlosschleife: openssl ecparam -in my_bad_group.der -inform der.

... WIP ...