Österreichische Kryptologen attackieren Hash-Funktionen

Österreichische Kryptologen präsentierten auf der Crypto 2008 Fortschritte bei Angriffen auf Hash-Funktionen. So stellten sie einen Angriff auf den russischen Hash-Standard GOST vor, dessen Verwendung in russischen Behörden vorgeschrieben ist. Außerdem zeigen sie erste Ansätze für Invertierungsangriffe auf SHA-1, mit denen man beispielsweise ein Passwort aus dem Hash zurückrechnen könnte.

Die GOST Hash-Funktion wurde etwa um die gleiche Zeit wie SHA-1 (1995) als GOST-Standard festgelegt und galt bis jetzt als sehr sicher. Wie in der Raumfahrt sind auch die russischen Standards in der Informationssicherheit sehr konservativ ausgelegt.

Nun hat jedoch ein österreichisch-polnisches Team von Kryptologen von der TU Graz und der MUT Warschau eine unerwartete strukturelle Schwäche gefunden und für einen Angriff genutzt. Das Resultat ist eine Kollisionsattacke, die 2²³ mal schneller ist als erwartet. Eine Kollisionsattacke findet zwei beliebige Nachrichten, die den gleichen Hash-Wert erzeugen.

Zum Vergleich: Die erste erfolgreiche Kollisionsattacke 2005 auf SHA-1 machte einen Angriff um den Faktor 2¹¹ schneller als erwartet (2⁶⁹ statt 2⁸⁰). Trotzdem sind wohl vorerst keine praktikablen Angriffe auf die GOST-Hash-Funktion zu erwarten, weil dazu wegen der Ausgabegröße von 256 Bit immer noch 2¹⁰⁵ Operationen erforderlich wären – also deutlich mehr, als derzeit realistisch durchführbar wären.

Alle in den letzten Jahren bekannt gewordenen Angriffe auf Hash-Funktionen wie SHA-1 und jetzt GOST sind Kollisionsangriffe. Sie sind aber hauptsächlich für Signaturanwendungen relevant, bei denen ein Angreifer Zugriff auf die Dokumente hat, bevor die Signatur berechnet wird. Ein nachträgliches Verändern von Dokumenten mit dem Ziel einer gültig bleibenden Signatur ist damit nicht möglich. Auch sind viele andere Anwendungen von Hash-Funktionen, etwa das sichere Abspeichern von Passwörtern, davon nicht betroffen. Das ist auch der Grund, warum beispielsweise die amerikanische Standardisierungsbehörde NIST die Hash-Funktion SHA-1 für diese und andere Anwendungsbereiche weiterhin empfiehlt.

Auf der Crypto präsentierten Forscher der TU Graz und ENS Paris erstmals Ansätze für Angriffe auf SHA-1, die auch bei diesen Anwendungen relevant sind. Also etwa ein Passwort berechnen, wenn man nur den SHA-1-Hashwert davon kennt, oder signierte Dokumente erst dann verändern, nachdem die Signatur schon ausgestellt ist. Diese Angriffe funktionieren für rundenreduzierte Versionen von SHA-1 (maximal 45 der 80 Runden). Dies ist ungefähr vergleichbar mit Kollisionsattacken auf SHA-1 vor 4 Jahren: Hier waren theoretische Angriffe bis maximal 53 Runden bekannt. Im Moment sieht es zwar nicht danach aus, dass solche Angriffe auf die vollen 80 Runden ausgedehnt werden können, aber es gibt eine weitere Parallele zu den früheren Kollisionsangriffen: Diese neuen Invertierungsangriffe, wie auch die frühen Kollisionsangriffe (bis 2004), haben viele ungenutzte Freiheitsgrade. Die neuesten Kollisionsangriffe (von 2007) nutzen mittlerweile alle verfügbaren Freiheitsgrade aus.

Selbst wenn viele aktuelle Angriffe bislang theoretischer Natur sind, sollte man berücksichtigen, dass die Analyse kryptographischer Hash-Funktionen noch längst nicht ausreichend erforscht ist und somit weitere Dammbrüche nicht ausgeschlossen werden können. Auch mit Blick auf den bevorstehenden Wettbewerb für den neuen Hash-Standard SHA-3 ab 2012, für den Einreichungen noch bis Ende Oktober 2008 möglich sind, erscheint es um so wichtiger, Hash-Funktionen mit nachvollziehbaren Sicherheitsargumenten (die es weder bei SHA-1 noch bei GOST gibt) zu bevorzugen. (Christian Rechberger)

Christian Rechberger ist wissenschaftlicher Mitarbeiter am Institut für Angewandte Informationsverarbeitung und Kommunikationstechnologie (IAIK) an der TU Graz und Mitautor der Veröffentlichungen zu GOST und den Invertierungsangriffen auf SHA-1. (ju)