String-Vergleich gegen Timing-Angriffe härten

Christoph Iserlohn

Der String-Vergleich über die Methode String#equals in Java ist anfällig für Timing-Angriffe. Der oft empfohlene Lösungsansatz ist schwierig korrekt zu implementieren. Aber selbst eine korrekte Implementierung kann bei der Ausführung noch für Timing-Angriffe anfällig sein. Die hier vorgestellte Methode schließt diese Probleme prinzipiell aus.

Timing-Angriffe (siehe Kasten „Timing-Angriffe“) beim String-Vergleich werden oft an Passwörtern illustriert. Ein übermitteltes Passwort muss mit einem gespeicherten verglichen werden. Da Passwörter in der Regel außerordentlich gut geschützt werden, sind sie eher nicht für Timing-Angriffe anfällig (siehe Kasten „Passwörter und Timing-Angriffe“). Ein realistischeres Szenario wird im Folgenden vorgestellt.

Das Angriffsszenario

Erfolgreiche Angriffe auf Signaturen und Message-Authentication-Codes (im Folgenden MAC, siehe Kasten „Message-Authentication-Codes“) können genauso schwerwiegende oder gar schlimmere Folgen haben als Angriffe auf Passwörter. MACs werden zum Beispiel benutzt, um Cookies in Webanwendungen abzusichern.

Moderne Webanwendungen sind typischerweise zustandslos, damit sie gut horizontal skaliert werden können. Wird dennoch State benötigt, wird dieser oft in Cookies auf dem Client gespeichert, damit weiterhin horizontal skaliert werden kann. Häufig ist die Benutzer-Session mit Anmeldestatus und den Rollen der Benutzer etwas, was eine Webanwendung im State speichern muss.

Eine einfache, exemplarische Benutzer-Session könnte zum Beispiel so aussehen:

usr=Erika Evil, role=Guest;

Sie enthält lediglich den Benutzernamen und die Rolle. Anhand der gespeicherten Rolle kann die Anwendung entscheiden, welche Rechte die Benutzerin hat und welche Operationen ihr erlaubt sind. Unsere Benutzerin Erika Evil ist zufällig eine Black-Hat-Hackerin, und sie weitet ihre Rechte einfach aus, indem sie ihre Rolle ändert. Der Cookie wird auf dem Client der Hackerin gespeichert und kann folglich leicht manipuliert werden. Die Benutzer-Session, die per Cookie an die Webanwendung geschickt wird, sieht dann so aus:

usr=Erika Evil, role=Admin;

Damit das nicht passieren kann, schützen Webanwendung die Daten der Benutzer-Session in den Cookies in der Regel vor Manipulation. Sie stellen die Integrität der Nutzdaten mit einem MAC oder einer Signatur sicher. Mit einem HMAC-MD5 und dem Schlüssel “secret” abgesichert, sehen die Benutzer-Session-Daten so aus:

usr=Erika Evil, role=Guest;4dfb6e3a6b89b9baa5fd32226e70b496

Die Zeichenfolge hinter dem Semikolon ist der HMAC-MD5 über die eigentlichen Nutzdaten usr=Erika Evil und role=Guest. Ändert Erika Evil die Nutzdaten auf usr=Erika Evil, role=Admin, muss sich auch der HMAC-MD5 ändern. Diesen kann Erika aber nicht erzeugen, da sie den geheimen Schlüssel nicht kennt. Diesen kennen nur die Server der Webanwendungen. Manipuliert Erika die Benutzer-Session-Daten, kann sie nur den ursprünglichen oder einen geratenen HMAC-MD5 verwenden:

usr=Erika Evil, role=Admin;4dfb6e3a6b89b9baa5fd32226e70b496

So kann die Webanwendung die Manipulation leicht erkennen. Sie berechneten den HMAC-MD5 von usr=Erika Evil, role=Admin. Dieser ist 29866cca77c5fb63d4171b2b7e2bba6b. Dann vergleicht sie ihn mit dem übermittelten HMAC-MD5 4dfb6e3a6b89b9baa5fd32226e70b496. Stimmen diese nicht überein, wurden die Daten manipuliert.

Timing-Angriff beim normalen String-Vergleich

Auch wenn Erika keine validen HMAC-MD5 für ihre manipulierten Daten erzeugen kann, ist das Problem noch nicht gelöst. Der Vergleich der beiden HMAC-MD5-Strings ist nämlich für Timing-Angriffe verwundbar. Das gleiche gilt übrigens genauso, wenn statt Strings direkt die Bytes verglichen würden.

public static boolean stringEquals(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() != s2.length()) {
        return false;
    }
    for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            return false;
        }
    }
    return true;
}

Der Vergleich mittels String#equals sieht in vereinfachter Form aus, wie in der Methode stringEquals dargestellt (s. Listing 1). Zuerst prüft die Methode die zu vergleichenden Strings auf null und auf die gleiche Länge – sollte einer der Strings null oder die beiden Strings nicht gleich lang sein, können die Strings nicht gleich sein, und der Vergleich kann abgebrochen werden.

Dann folgt der tatsächliche Vergleich, bei dem in einer Schleife Zeichen für Zeichen verglichen wird. Stimmt ein Zeichen nicht überein, sind die Strings ungleich und die Schleife kann frühzeitig abgebrochen werden. Der frühzeitige Abbruch spart CPU-Zyklen, da unnötige Arbeit vermieden wird, wenn das Ergebnis bereits feststeht. Im Allgemeinen ist das eine gute Praxis, in diesem Fall leider das Einfallstor für einen Timing-Angriff.

Jede ausgeführte Anweisung und jeder Ausdruck benötigt eine gewisse Zeit. Diese Zeiten können gemessen werden. Angenommen in stringEquals dauern die null-Prüfung und der Vergleich der Längen etwa 10 ms:

if (s1 == null || s2 == null || s1.length() != s2.length()) {
    return false;
}

Um herauszufinden, wie lang der gesuchte String ist, wird einfach der Reihe nach ein String mit der Länge 1, dann mit Länge 2 usw. übergeben, und die Zeit für den Vergleich gemessen. Hat der übergebene String die Länge des gesuchten Strings, dauert die Ausführung nun ein klein wenig länger, da jetzt auch mindestens ein Schleifendurchlauf stattfindet. Im Beispiel ist dieser Schritt nicht nötig, da die Länge des gesuchten Strings bekannt ist. Ein HMAC-MD5 hat immer die gleiche Länge.

Jeder Schleifendurchlauf dauert ungefähr gleich lang, angenommen etwa 5 ms:

for (int i = 0; i < s1.length(); i++) {
    if (s1.charAt(i) != s2.charAt(i)) {
        return false;
    }
}

Den gesuchten String zu finden, ist nun vergleichsweise einfach. Es wird beim übergebenen String zuerst das erste Zeichen systematisch geändert und wieder die Ausführungszeit gemessen:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
caaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(...)
9aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Stimmt das erste Zeichen mit dem ersten Zeichen des gesuchten Strings überein, dauert die Ausführung etwas 5 ms länger, da die Schleife einmal mehr durchlaufen wird. Dann wird mit dem zweiten Zeichen fortgefahren:

9aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
9baaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
9caaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(...)

Dies wird solange fortgeführt, bis alle Zeichen gefunden sind, was sehr schnell geht. In hexadezimaler Darstellung des HMAC-MD5 gibt es 16 Möglichkeiten pro Zeichen (0 – 9 sowie a – f). Im Schnitt muss die Hälfte der Möglichkeiten für einen Treffer probiert werden, also 8 Versuche pro Zeichen. Bei einer Länge von 32 Zeichen sind das 32 · 8 = 256 Versuche, bis der gesuchte String gefunden ist. Bei nur einem Versuch pro Sekunde ist der String in unter fünf Minuten, bei zehn Versuchen pro Sekunde in unter 30 Sekunden und bei 100 Versuchen pro Sekunde in unter 3 Sekunden geknackt.

Werden dagegen bei einem Brute-Force-Angriff alle möglichen Strings ausprobiert und im Schnitt nach der Hälfte der Versuche ein Treffer erzielt, sind 16³²/2 = 1,7 · 10³⁸ Versuche nötig. Selbst bei einer Billiarde (1.000.000.000.000.000) Versuchen pro Sekunde dauert das Knacken des Strings ca. 5.395.141.535.403.006 Jahre – weitaus länger, als die Sonne existieren wird.

Das gleiche Prinzip funktioniert auch, wenn statt der Strings direkt die Bytes verglichen werden. Schon vor über 15 Jahren wurde gezeigt, dass Timing-Angriffe selbst über das Netzwerk praktikabel sind (vgl. [1]), trotz der unvermeidlichen Latenzen und dem auftretenden Jitter – genügend Versuche und passende statistische Methoden vorausgesetzt. Diese Ergebnisse wurden später bestätigt (vgl. [2]) und die Methoden mit der Zeit weiter verfeinert (vgl. [3]).

String-Vergleich in gleichbleibender Zeit

Eine oft empfohlene Gegenmaßnahme gegen den beschriebenen Timing-Angriff ist, den String-Vergleich so zu implementieren, dass immer die gleiche Zeit benötigt wird, egal wie viele Zeichen in den Strings übereinstimmen. Ein solcher Vergleich wird in Listing 2 gezeigt. Hier werden immer alle Schleifendurchläufe ausgeführt, egal ob ein Zeichen unterschiedlich ist und damit das Ergebnis bereits vorzeitig feststeht.

public static boolean stringEqualsNoShortcut(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() != s2.length()) {
        return false;
    }
    boolean isEqual = true;
    for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            isEqual = false;
        }
    }
    return isEqual;
}

Diese Implementierung schützt zuerst einmal vor dem Timing-Angriff (für Alternativen siehe Kasten „Alternative Gegenmaßnahmen“). Sie hat jedoch zwei Probleme. Erstens wird über die Ausführungszeit immer noch Information über die Länge des gesuchten Strings preisgegeben. Und eine Implementierung, die eine gleichbleibende Ausführungszeit hat, egal ob einer der Strings null oder die Länge verschieden ist, ist alles andere als einfach.

Das zweite Problem ist auf lange Sicht noch schwerwiegender. Ob überhaupt genau das ausgeführt wird, was im Quelltext steht, ist alles andere als sicher. Der Quelltext wird vom Java-Compiler in Bytecode übersetzt. Dabei kann er Änderungen und Optimierung vornehmen, solange er die Semantik nicht verändert. Die Ausführungszeit gehört nicht zur Semantik. Einen Compiler, der die Variante mit gleichbleibender Ausführungszeit durch eine schnellere mit variabler Ausführungszeit ersetzt, gibt es derzeit zwar nicht, ist aber vorstellbar und wäre valide. Jedes Mal, wenn der Quelltext mit einem neuen Compiler übersetzt wird, kann es dazu kommen, dass der Schutzmechanismus ausgehebelt wird. Auch wenn der Quelltext nicht neu übersetzt wird, kann der Schutzmechanismus ausgehebelt werden, falls der Bytecode auf einer neuen JVM ausgeführt wird. Der JIT-Compiler versucht beim Kompilieren des Bytecodes in Maschinencode schließlich auch zu optimieren, solange die Semantik nicht geändert wird. Im Java-Universum optimiert der Compiler typischerweise so gut wie gar nicht, dafür der JIT umso mehr. Die CPU kann dann schlussendlich Optimierungen bei der Ausführung des Maschinencodes vornehmen, um ihre Ressourcen besser zu nutzen. Optimierungen der CPU haben Meltdown und Spectre [4] ermöglicht, die wohl folgenschwersten Sicherheitslücken der letzten Jahre, obwohl die Semantik sich auch hier nicht verändert hat.

thread.sleep(random.nextInt(100))

Eine Kontrolle über den Java-Compiler, die JVM und die CPU, auf welcher der String-Vergleich am Ende ausgeführt wird, ist meistens nicht möglich. Somit besteht keine Sicherheit, ob der implementierte Schutzmechanismus, Ausführung in gleichbleibender Zeit, wirklich greift. Eine bessere Lösung sollte das Problem prinzipiell ausschließen, sodass die Ausführungszeit keinen Rückschluss auf den gesuchten String zulässt. Im Folgenden wird so eine Lösung vorgestellt.

Hash-Vergleich statt String-Vergleich

Statt direkt die Strings zu vergleichen, werden die Hashes der Strings aus kryptografischen Hash-Funktionen wie SHA-256 verglichen (s. Listing 3). Kryptografische Hash-Funktionen haben drei Eigenschaften, die für einen sicheren String-Vergleich von außerordentlichem Nutzen sind.

public static boolean stringHashEquals(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return false;
    }
    MessageDigest sha256 = getSHA256Digest();
    byte[] s1AsByteArray = s1.getBytes(StandardCharsets.UTF_8);
    byte[] s2AsByteArray = s2.getBytes(StandardCharsets.UTF_8);

    byte[] sha256S1 = sha256.digest(s1AsByteArray);
    byte[] sha256S2 = sha256.digest(s2AsByteArray);

    String sha256S1AsHexString = bytesToHexString(sha256S1);
    String sha256S2AsHexString = bytesToHexString(sha256S2);

    return stringEquals(sha256S1AsHexString, sha256S2AsHexString);
}

Erstens gibt es für jede Eingabe (die zu vergleichenden Strings) eine eindeutige Ausgabe, für die es praktisch unmöglich ist, eine Kollision zu finden. Das heißt, der Hash zweier verschiedener Strings ist immer unterschiedlich und gleiche Hashes bedeuten, dass auch die Strings gleich sind. Die Hashes können also statt der ursprünglichen Strings verglichen werden, ohne ein anderes Ergebnis zu liefern.

Zweitens kann vom Hash nicht auf den ursprünglichen Wert geschlossen werden. Sollte der Hash in die Hände der Angreiferin Erika geraten, kann sie damit nichts anfangen. Der gesuchte String bleibt weiterhin geheim.

Drittens ändert sich der Hash sehr stark, selbst bei minimalen Änderungen in der Eingabe – der sogenannte Lawineneffekt:

sha("Erika Evil") = 646f7d71f2a4175af1e41b843e5ee5c3b58b2405
sha("Erica Evil") = 1d3d8f375318b47922d7ab4679a941f02c1bee87

Ein Timing-Angriff ist jetzt nicht mehr möglich. Sollte die Ausführungszeit länger sein, weil es eine Übereinstimmung gibt, gilt diese nur für den Hash, nicht für das Zeichen im gesuchten String. Im Beispiel ist der gesuchte String der HMAC-MD5 der Benutzer-Session-Daten “29866cca77c5fb63d4171b2b7e2bba6b”:

sha256("29866cca77c5fb63d4171b2b7e2bba6b") =
        94225fa5338614d7491d0ce6c555e4db91e006be497bbde7d5267348b66739ef

Beim systematischen Ausprobieren werden nun die SHA-256 der Strings verglichen:

sha256("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") =
        3ba3f5f43b92602683c19aee62a20342b084dd5971ddd33808d81a328879a547
sha256("baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") =
        ceef1b7f2a317811bc99327cc241ebcbf9db3670f7c329a60674f4ce9e7a2d72
(...)

Den ersten Treffer gibt es bei "0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa":

sha256("0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") =
        9572359935f176e21797526b32e8d6309fae06d8ceafcbd740109aa0b43054fd

Das erste Zeichen des SHA-256 stimmt mit den ersten Zeichen des SHA-256 des gesuchten Strings überein. Nicht jedoch das erste Zeichen des probierten Strings mit dem ersten Zeichen des gesuchten. Der nächste Versuch führt wegen des Lawineneffekts zu keinem Treffer mehr. Der SHA-256 hat keine Ähnlichkeit mehr mit dem des letzten Versuchs:

sha256("0baaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") =
        37e1db3f3df0ade1ebd2dcc8da2873c434c71c8c27dac04ae41c6be4fbce77f3

Die Ausführungszeit bietet der Angreiferin keine Möglichkeit festzustellen, ob es Übereinstimmungen in den Strings gibt. Für einen erfolgreichen Angriff wäre eine Liste von Strings nötig, mit der sich die Hashes systematisch durchprobieren lassen:

sha256("<????????????????????????????????>") =
        aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
sha256("<????????????????????????????????>") =
        baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Eine solche Liste kann allerdings nicht erstellt werden, weil vom Hash nicht auf den Eingabewert geschlossen werden kann.

Die Alu-Hut-Variante: randomisierter Hash-Vergleich

Die Angriffsmethoden werden niemals schlechter, sondern immer nur besser. Oder wie es der renommierte Sicherheitsexperte Bruce Schneier formuliert: “today’s secret NSA programs become tomorrow’s PhD theses, and the next day’s criminal hacker tools” [6].

Angenommen es gäbe eine solche Liste mit Strings, ist diese mit wenig Aufwand auszuhebeln. Der Hash wird nicht mehr direkt über den String gebildet, stattdessen über einen Zufallswert, konkateniert mit dem zu vergleichenden Strings, wie in Listing 4.

public static boolean stringRndHashEquals(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return false;
    }
    MessageDigest sha256 = getSHA256Digest();
    byte[] randomBytes = getRandomBytes(16);

    byte[] s1AsByteArray = s1.getBytes(StandardCharsets.UTF_8);
    byte[] s2AsByteArray = s2.getBytes(StandardCharsets.UTF_8);

    byte[] rndS1 = appendByteArray(randomBytes, s1AsByteArray);
    byte[] rndS2 = appendByteArray(randomBytes, s2AsByteArray);

    byte[] rndSha256S1 = sha256.digest(rndS1);
    byte[] rndsha256S2 = sha256.digest(rndS2);

    String sha256S1AsHexString = bytesToHexString(rndSha256S1);
    String sha256S2AsHexString = bytesToHexString(rndsha256S2);

    return stringEquals(sha256S1AsHexString, sha256S2AsHexString);
}

Jeder Versuch ergibt nun einen anderen Hash, auch wenn der gleiche String probiert wird, weil bei jedem Versuch ein anderer Zufallswert in den Hash einfließt. Auch wenn die Fragezeichen in:

sha256("<????????????????????????????????>") =
        aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

bekannt sind, wird beim Vergleich daraus:

sha256("<random>" + "<????????????????????????????????>") =
        ????????????????????????????????????????????????????????????????

Ein systematischer Vergleich ist auch mit der (fiktiven) Liste der Hashes nicht mehr möglich. Eine Übereinstimmung eines Zeichens des SHA-256 ist purer Zufall. Beim nächsten Versuch mit demselben String ändert sich der Hash aufgrund des neuen Zufallswerts und es gibt keine Übereinstimmung mehr. Aus der Ausführungszeit ist nichts mehr abzuleiten. Es spricht natürlich nichts dagegen, die Hashes auch mit der Methode stringEqualsNoShortcut zu vergleichen. Eine zusätzliche Sicherheit wird damit zwar nicht erreicht, der Alu-Hut passt dann aber irgendwie besser.

Literatur und Links