Auf dem Chaos Communication Congress (28C3) Ende Dezember 2011 haben Alexander Klink und Julian Wälde eine Schwachstelle (Advisory als PDF) in den Hash-Funktionen zahlreicher Programmiersprachen beschrieben.
Auch wenn die dargestellte Problematik und daraus resultierende Attacken nichts Neues sind, hat der Vortrag dennoch einige Aufmerksamkeit erregt. Die vorgestellte Attacke ist allerdings schon seit acht Jahren bekannt und gehört in die allgemeine Klasse der Attacken durch algorithmische Komplexität.
Hash Tables
Hash Tables sind eine sehr verbreitete Datenstruktur zum Ablegen von Schlüssel-Daten-Paaren. Sie ermöglichen es dem Programmierer, bestimmte Elemente deutlich schneller in der Datenstruktur zu finden als dies beispielsweise mit einfachen linearen Listen der Fall ist. Damit dienen sie einem ähnlichen Ziel wie Baumstrukturen. Die zentrale Idee einer Hash-Tabelle ist dabei die Verwendung einer Hash-Funktion, die einem bestimmten Schlüssel einen Index in der Hash-Tabelle zuweist. Dadurch muss dieser Schlüssel nicht in linearer Zeit in der Liste gesucht werden, sondern lässt sich mit konstanter Zeitkomplexität direkt auffinden. Die Stelle, an der das Datenobjekt eines Schlüssels in der Tabelle abgelegt ist, bezeichnet man als Bucket.
Hash-Tabellen erreichen die höchste Zeit-Effizienz, wenn jedes Objekt in einem eigenen Bucket abgelegt ist. Allgemeine Hash-Funktionen sind jedoch nicht injektiv konstruiert, das heißt, es es ist möglich, dass zwei verschiedenen Schlüsselwerten der gleiche Hash-Wert zugewiesen wird, was man als Kollision bezeichnet. Es gibt mehrere Möglichkeiten, solche Kollisionen zu behandeln, wobei häufig Verkettung der Objekte eingesetzt wird. Dabei werden in einem Bucket einfach mehrere Objekte mit dem selben Hash-Wert abgelegt, wobei die Elemente innerhalb eines Buckets als verkettete Liste implementiert sind. Im Worst-Case-Szenario sind alle Schlüssel verschieden, haben aber den gleichen Hash-Wert. Das bedeutet, sie werden alle in einem einzigen Bucket abgelegt, und die Hash-Tabelle degeneriert zu einem Array, in dem das Einfügen und Aufsuchen von Elementen die Komplexität O(n) statt O(1) besitzt. Idealerweise sollte die Hash-Funktion so konstruiert sein, dass dies nicht eintritt, denn in diesem Szenario besitzt das Einfügen von n Elementen Komplexität O(n^2).
Insbesondere Anwendungen, die Benutzerdaten in Hash-Tabellen verwalten sollten darauf achten, dass sie ein Hash-Verfahren verwenden, das Kollisionen möglichst vermeidet. Ist dies nicht der Fall, kann ein Angreifer aufgrund des Verhaltens beim Einfügen von Elementen eine Denial-of-Service-Attacke durchführen. Eine solche Attacke setzt allerdings voraus, dass der Angreifer auf einfache Art kollidierende Schlüssel erzeugen kann.
Eine sehr gebräuchliche Hash-Funktion, die in zahlreichen Programmiersprachen zum Einsatz kommt, ist der DJBX33A-Algorithmus von Dan Bernstein:
uint32_t hash(const char *arKey, uint32_t nKeyLength) { uint32_t hash = 5381; for (; nKeyLength > 0; nKeyLength -=1) { hash = ((hash << 5) + hash) + *arKey++; } return hash;
}
Diese Funktion nimmt einen Eingabe-String “arKey” der Länge “nKeyLength” und berechnet daraus durch Multiplikation mit 33 und Addition einen Hash-Wert. Diese Hash-Funktion kommt beispielsweise bei Java zum Einsatz. Dabei macht sie es einem Angreifer sehr leicht, Kollisionen zu erzeugen, denn sie enthält so genannte gleichwertige Teilzeichenfolgen.
Dies bedeutet: Gilt
Hash(String1)=Hash(String2)
so gilt auch
Hash(String1+String3)=Hash(String2+String3)
Wie Klink und Wälde explizit demonstrieren, lassen sich dadurch basierend auf den gleichwertigen Teilzeichenfolgen “tt”, “uU” und “v6” 3^n verschiedene, unter DJBX33A kollidierende Schlüssel erzeugen:
base3_strings = (0..3**n-1).each do |i| "%0nd" % i.to_s(3) # "0...0" to "2...2"
end
base3_strings.map do |s| s.gsub('0', 'tt') .gsub('1', 'uU') .gsub('2', 'v6')
end
Eine andere gebräuchliche Hash-Funktion von Bernstein ist DJBX33X:
uint32_t hash(const char *arKey, uint32_t nKeyLength) { uint32_t hash = 5381; for (; nKeyLength > 0; nKeyLength -=1) { hash = ((hash << 5) + hash) ^ *arKey++; } return hash;
}
Diese ist nicht-linear und damit nicht anfällig für den beschriebenen Angriff auf Grundlage gleichwertiger Teilzeichenfolgen. In diesem Fall ist es etwas schwieriger, Kollisionen zu finden. Sind die Hashes nur 32 Bit lang (statt 64), so ist eine Brute-Force-Attacke möglich, um kollidierende Schlüsselwerte zu finden. Dazu wendet man die Hash-Funktion auf zufällige Zeichenfolgen an und speichert diejenigen ab, die auf einen gleichen Ziel-Hash abgebildet werden. Die Wahrscheinlichkeit einen, bestimmten Hash-Wert zufällig zu treffen liegt dabei im Schnitt bei 1/(32^2).
Diese Methode ist anwendbar, aber nicht sehr effizient. Besser geeignet ist hier eine Meet-in-the-Middle-Attacke, die für die DJBX33X-Funktion möglich ist. In diesem Fall versucht der Angreifer, nicht nur eine Ziel-Hash-Funktion pro Versuch zu treffen, sondern gleich mehrere. Dabei werden die zufälligen Zeichenketten in Prefix und Postfix zerlegt, und für das Postfix werden Zwischenwerte der Hash-Funktion berechnet. Dieses Verfahren funktioniert nur bei Hash-Funktionen, bei denen sich ein Zwischenzustand aus dem Postfix berechnen lässt. Dies ist bei DJBX33X möglich und erhöht die Wahrscheinlichkeit für eine Kollision auf 1/(2^16). Damit kann ein Angreifer also deutlich schneller kollidierende Schlüssel erzeugen als über eine einfache Brute-Force-Attacke.
Angriffe auf Webanwendungen
Diese eher theoretische Betrachtung hat sehr praktische Auswirkungen: So gut wie alle Webanwendungen verwenden Hash-Tabellen, beispielsweise um HTTP-POST-Nachrichten zu verarbeiten. Dabei verwalten sie die verschiedenen Parameter der POST-Anfrage als Schlüssel-Daten-Paare in einer internen Hash-Tabelle. In PHP sieht dies allgemein so aus:
<?php echo $_POST["username"]; ?>
“$_POST” ist dabei eine Hash-Tabelle, die alle POST-Parameter der Webanfrage aufnimmt. Andere Sprachen machen dies genauso, etwa Java:
public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException { out.println(request.getParameter('username'));
}
Was passiert nun, wenn ein Angreifer zahlreiche kollidierende Schlüssel via HTTP-POST an die Webapplikation übergibt? Da die Schlüssel alle kollidieren, degeneriert die Hash-Tabelle. Der Zeitaufwand für das Einfügen der einzelnen POST-Parameter skaliert mit n^2 statt n. Das bedeutet, die CPU wird bei einer genügend großen Anzahl von Parametern vollständig damit ausgelastet, die Hash-Tabelle zu füllen. Wie der 28C3-Vortrag demonstriert, lässt sich auf diese Weise schon mit recht geringer Bandbreite unter Berücksichtigung weiterer POST-Limits eine effektive Denial-of-Service-Attack gegen Webanwendungen durchführen.
Solche Hash-Kollisions-Probleme sind nichts Neues, und Lösungen sind schon seit langer Zeit bekannt. Eine besteht darin, zufällige Hash-Funktionen zu verwenden. Dabei wechselt die Programmiersprache die Hash-Funktionen dynamisch und macht es damit für den Angreifer unmöglich, kollidierende Schlüssel vorauszuberechnen. Interessanterweise hat Perl dies schon 2003 umgesetzt. Ebenso hat auch CRuby 1.9 dies implementiert. In Perl ist das einfach durch einen zufälligen Hash-Seed-Wert umgesetzt. Der Grund für die frühzeitige Implementierung in Perl liegt darin, dass Perl für die ursprüngliche Kollisions-Attacke in dem Paper “Denial of Service via Algorithmic Complexity Attacks” von Scott A. Crosby und Dan S. Wallach als Beispiel diente. Die Perl-Community reagierte angemessen darauf.
Neben zufälligen Hash-Funktionen empfiehlt es sich als schneller Workaround, einfach die Anzahl der POST-Elemente zu begrenzen, womit sich Denial-of-Service-Attacken verhindern lassen.
Betroffen von dieser Hash-Problematik sind die folgenden Programmiersprachen und Application Server:
* Java (alle Versionen) * JRuby (<= 1.6.5) * PHP (<= 5.3.8, <= 5.4.0RC3) * Python (alle Versionen) * Rubinius (alle Versionen) * Ruby (<= 1.8.7-p356) * Apache Geronimo (alle Versionen) * Apache Tomcat (<= 5.5.34, <= 6.0.34, <= 7.0.22) * Oracle Glassfish (<= 3.1.1) * Jetty (alle Versionen) * Plone (alle Versionen) * Rack (<= 1.3.5, <= 1.2.4, <= 1.1.2) * V8 JavaScript Engine (alle Versionen)
Das einzig Überraschende an dieser Sicherheitslücke ist eigentlich, dass so viele Programmiersprachen ein wohlbekanntes Problem nicht früher korrigierten.
