Denial-of-Service-Angriff auf Rubys Hash-Algorithmus gefunden (CVE-2011-4815)

Veröffentlicht von Urabe Shyouhei am 28. Dez. 2011

Auswirkungen

Dies hat etwas mit der rechnerischen Komplexität zu tun. Eine speziell präparierte Serie von Strings, die absichtlich ihre Hash-Werte kollidieren, wurde gefunden. Mit solchen Sequenzen kann ein Angreifer einen Denial-of-Service-Angriff ausführen, indem er sie beispielsweise als POST-Parameter von HTTP-Anfragen für Ihre Rails-Anwendung übergibt.

Detaillierte Beschreibung

Die Situation ist ähnlich wie die, die 2003 für Perl gefunden wurde. In der 1.8-Serie von Ruby verwenden wir eine deterministische Hash-Funktion, um einen String zu hashen. Hier bedeutet "deterministisch", dass keine anderen Informationsbits als der Eingabe-String selbst zur Erzeugung eines Hash-Wertes verwendet werden. Sie können also den Hash-Wert eines Strings im Voraus berechnen. Durch das Sammeln einer Reihe von Strings, die den identischen Hash-Wert haben, kann ein Angreifer Ruby dazu bringen, Kollisionen in Hash-Tabellen (einschließlich Instanzen der Hash-Klasse) zu erzeugen. Die amortisierte O(1)-Eigenschaft von Hash-Tabellen hängt von der Gleichmäßigkeit der Verteilung der Hash-Werte ab. Durch die Übergabe solcher präparierten Eingaben kann ein Angreifer Hash-Tabellen dazu bringen, viel langsamer als erwartet zu arbeiten (nämlich O(n²) für die Erstellung einer Tabelle mit n Elementen in diesem Fall).

Betroffene Versionen

• Ruby 1.8.7-p352 und alle früheren Versionen.

Alle Ruby 1.9-Serien sind von dieser Art von Angriff nicht betroffen. Sie teilen keine Hash-Implementierungen mit der Ruby 1.8-Serie.

Lösung

Unsere Lösung besteht darin, die String-Hash-Funktion mit einigen von PRNG generierten Zufallsbits zu verschleiern. Dadurch ist der Hash-Wert eines Strings nicht mehr deterministisch. Das heißt, ein String#hash-Ergebnis ist nur für die aktuelle Prozesslaufzeit konsistent und wird beim nächsten Start eine andere Zahl erzeugen. Um diese Situation zu brechen, muss ein Angreifer eine Reihe von Strings erstellen, die gegen diese Art von Verschleierung robust sind. Dies wird als ziemlich schwierig erachtet.

Bitte aktualisieren Sie auf ruby 1.8.7-p357.

Hinweise

• Bitte beachten Sie, dass die Lösung *nicht* bedeutet, dass unser Hash-Algorithmus kryptografisch sicher ist. Vereinfacht ausgedrückt haben wir die Hash-Tabelle behoben, aber nicht die Schwäche von String#hash. Ein Angreifer könnte sie immer noch ausnutzen, sobald er ein Paar aus einem String und seinem von String#hash zurückgegebenen Hash-Wert erhalten hat. Sie *dürfen* String#hash-Ausgaben *nicht* offenlegen. Wenn Sie solche Dinge tun müssen, sollten Sie stattdessen sichere Hash-Algorithmen verwenden. Einige davon (wie SHA256) sind in Rubys Standardbibliothek enthalten.

• Für diejenigen, die alternative Hash-Algorithmen in unserer Codebasis kennen: Wir unterstützen diese nicht (sie sind standardmäßig deaktiviert). Indem Sie sich für sie entscheiden, gehen wir davon aus, dass Sie C lesen können und verstehen, was mit dem Standardalgorithmus falsch war. Stellen Sie sicher, dass Ihre Wahl auf eigenes Risiko sicher ist.

Danksagung

Dank an Alexander Klink alexander.klink@nruns.com und Julian Waelde jwaelde@cdc.informatik.tu-darmstadt.de für die Meldung dieses Problems.

EDIT Einige verwandte Links

• CVE-2011-4815 wurde diesem Problem zugewiesen.
• oCERT.org hat eine Beratung dazu veröffentlicht.
• JRuby hat die Version 1.6.5.1 veröffentlicht, um dasselbe Problem zu beheben. Andere Ruby-Alternativen könnten ebenfalls betroffen sein.
• Der Twitter-Account @hashDoS sammelt Informationen über Hash-Kollisionsangriffe.