Geschrieben von Quintus am 4.1.2012
Auswirkung
Es handelt sich hierbei um etwas, das mit mathematischer Komplexität zu tun hat. Es wurden speziell angefertige Folgen von Strings gefunden, welche untereinander kollidierende Hashwerte besitzen. Mithilfe solcher Aneinanderreihnungen ist es einem Angreifer etwa mithilfe von POST-Parametern eines HTTP-Requests für eine Rails-Anwendung möglich, eine Denial-Of-Service-Attacke durchzuführen.
Detaillierte Beschreibung
Das Problem ist dem 2003 in Perl gefundenen ähnlich. In Rubys
1.8er-Serie benutzen wir eine deterministische Hash-Funktion für
Strings, wobei »deterministisch« bedeutet, dass keine anderen
Informationen in die Berechnung des Hashwerts einfließen als der
Input-String selbst. Daher ist es möglich, den Hashwert eines Strings im
Vorhinein zu berechnen. Sammelt man nun eine Folge von Strings, welche
denselben Hashwert besitzen, ist es einem Angreifer möglich, einen
Ruby-Prozess zahlreiche Hashtabellen kollidieren zu lassen (das schließt
Instanzen der Klasse Hash mit ein). Die ungefähre Komplexität von
Hashtabllen liegt bei O(1), hängt jedoch von der gleichmäßigen
Verteilung der Hashwerte ab. Gibt man nun entsprechend angefertigten
Input, ist es einem Angreifer möglich, die Hashtabellen wesentlich
langsamer arbeiten zu lassen (genaugenommen O(n²), um eine n-elementige
Tabelle in diesem Falle zu erstellen).
Betroffene Versionen
- Ruby 1.8.7-p352 und alle vorangegangenen Versionen.
- Alle Ruby-Versionen der 1.9er-Serie sind nicht von dieser Art von Attacke betroffen. Sie nutzen eine andere Hash-Implementation als Rubys 1.8er-Serie.
Lösung
Unsere Lösung is es, die Hashfunktion für Strings mit ein paar durch PRNG generierten Werten aufzulockern, sodass der Hashwert eines Strings nicht mehr länger deterministisch ist. Dies bedeutet, dass das Ergebnis von String#hash nur noch für die Laufzeit des aktuellen Prozesses konsistent ist und nach dem nächsten Start eine andere Zahl generieren wird. Will ein Angreifer dies umgehen, muss er eine Folge von Strings erstellen, die gegen diese Art von Scrambling immun sind, was generell für sehr schwierig gehalten wird.
Bitte aktualisieren Sie auf Ruby 1.8.7-p357.
Hinweise
- Denken Sie bitte daran, dass diese Lösung nicht bedeutet, dass unser Hashalgorithmus kryptographisch sicher ist. Um es einfach auszudrücken: Wir haben die Hashtabelle gefixt, nicht aber die Schwäche in String#hash. Ein Angreifer wird immer noch Erfolg haben, wenn er/sie ein Paar von Strings und ihren von String#hash zurückgegebenen Wert bekommt. Daher sollten Ausgaben von String#hash nicht öffentlich werden. Wenn es wirklich sein muss, überlegen Sie, ob Sie nicht sichere Hash-Algorithmen verwenden wollen, von denen einige (wie z.B. SHA-256) auch in Rubys Standard Library enthalten sind.
- Für diejenigen, die die alternativen Hash-Algorithmen in unserer Code-Basis kennen: Wir unterstützen sie nicht (sie sind auch standardmäßig deaktiviert). Wenn Sie einen von diesen wählen, nehmen wir an, dass Sie C lesen können und verstehen, was mit dem Standardalgorithmus falsch war. Stellen Sie sicher, dass Ihre Wahl sicher ist—auf ihr eigenes Risiko.
Dank
Dank geht an Alexander Klink und Julian Wälde, die dieses Problem gemeldet haben.
Nachtrag
- CVE-2011-4815 befasst sich mit diesem Problem.
- oCERT.org hat einen Ratschlag darüber veröffentlicht.
- JRuby hat Version 1.6.5.1 veröffentlicht, um einen identischen Fehler zu korrigieren. Andere Ruby-Alternativen könnten ebenfalls betroffen sein.
- Der Twitter-Account @hashDoS sammelt informationen über Hash-Kollisions-Attacken.