Hashfunktion SHA-1 offenbar gebrochen - Digitale Signaturen in Gefahr

Unter theory.csail.mit.edu/~yiqun/shanote.pdf findet sich ein technischer Bericht, in dem von einem erfolgreichen Angriff auf die Hashfunktion SHA-1 gesprochen wird. Falls diese Information zutrifft, hat dies mittelfristig drastische Konsequenzen für digitale Signaturen, den Internethandel sowie elektronische Sicherheit im allgemeinen.

Hintergrund: Hash-Funktionen sind ein wichtiger Baustein für kryptographische Protokolle und insbesondere digitale Signaturen: um eine lange Nachricht signieren zu können, wird in der Regel mittels einer Hashfunktion ein digitaler Fingerabdruck bzw. Hash-Wert mit fester Länge erstellt und dann dieser digitale Fingerabdruck mittels einer Signaturfunktion signiert. Gelingt es nun, zwei inhaltlich verschiedenen Nachrichten den selben Hash-Wert zuzuordnen, ist es für einen Außenstehenden nicht mehr nachvollziehbar, welche der beiden Nachrichten nun unterzeichnet werden sollte. Handelt es sich bei dem Außenstehenden um einen Richter, der in einem Rechtsstreit die Gültigkeit zweier widersprüchliche Verträge beurteilen soll, die jedoch beide den selben Hash-Wert aufweisen, wird die wirtschaftliche Bedeutung einer solchen Möglichkeit schnell klar. Daher wird von Hash-Funktionen "Kollisionsresistenz" gefordert, d.h. zwei unterschiedliche Texte dürfen nicht auf den selben Hash-Wert abgebildet werden - und es muss rechnerisch unmöglich sein, solche zwei Texte zu konstruieren (Fach-Terminus: "Kollision"). In diesem Kontext bedeutet "rechnerisch unmöglich" ein Arbeitsaufwand von mehr als 2 hoch 80 3DES Operationen, wie ihn z.B. das NESSIE Projekt verwendet hatte. Dass es aber doch einfacher ist als gedacht, zwei solche Texte zu finden, behauptet der oben zitierte technische Bericht: Er berichtet von einem Arbeitsaufwand von 2 hoch 69 Operationen um zwei Nachrichten zu finden, die verschieden sind, jedoch den selben Hash-Wert aufweisen.

Um diese Zahlen in Perspektive zu rücken: Stellt man sich einen Rechner vor, der pro Sekunde 1 Milliarde Hash-Werte berechnen kann, so würde eine solche Maschine ca. 20.000 Jahre benötigen, um eine SHA-1 Kollision zu finden. Alternativ wäre es auch möglich, 20.000 solcher Computer zu bauen, die dann zusammen nur ein Jahr bräuchten. Wenngleich der finanzielle Aufwand wohl keinesfalls im Verhältnis zum zu erwartenden Nutzen steht (der entsprechende Vertrag müsste schon sehr wertvoll sein), illustriert dies jedoch, dass ein solcher Angriff mit heutigen Ressourcen zwar praktikabl, wenngleich unrealistisch ist. Des weiteren sind die Kollisionen, die so konstruiert werden, für den Menschen unschwer als Fälschungen zu erkennen, da sie größtenteils aus unsinnigen und nicht lesbaren Zeichen bestehen würden. Für automatische Systeme, die "blind" auf der Kollisionsresistenz von SHA-1 vertrauen, sieht die Lage schon wieder anders aus. Des weiteren hat sich in der Vergangenheit gezeigt, dass diese Angriffe in Laufe der Zeit verbessert werden - manchmal sogar drastisch. Insbesondere für SHA-1 ist jedoch mit dem aktuellen Angriff jegliche Sicherheitsmarge ausgereizt so dass wir den nächsten Angriff sicher nicht mehr abwarten können. Für die nächsten zwei bis drei Jahre sind die Anwender jedoch noch sicher. Wir empfehlen aber auch jeden Fall die weitere Entwicklung im Auge zu behalten und ggf. eine Risikoanalyse der Anwendungen vorzunehmen. Kleine Bemerkung am Rande: Selbst durch diesen Angriff ist SHA-1 immer noch sicherer als es MD5 je war (2 hoch 69 im Vergleich zu 2 hoch 64).

Mehrfaches Signieren ist auf den ersten Blick interessant, es wurde jedoch in einem Paper von A.Joux (Multicollisions in iterated hash functions. Application to cascaded constructions, Crypt 2004, LNCS 3152, Seiten 306-316) gezeigt dass das sicherheitstechnisch nur marginale Auswirkungen hat: statt die doppelte Sicherheit zu erhalten bekommt man nur wenige Bits (je nach Hash-Funktion im Bereich von 15 und 20 Bit). Daher löst mehrfaches Hashen unsere Probleme nicht. Wirklich sinnvoll ist es jedoch, von SHA-1 auf die beiden neuen Standards SHA-256 und SHA-512 umzusteigen.

Langfristig ist es daher nötig, mehrere Hashfunktionen mit jeweils unterschiedlichen internen Verfahrensweisen zu besitzen: das Grundübel der derzeitigen "Angriffswelle" (vor SHA-1 wurden bereits SHA-0 und MD5 gebrochen) gegen Hashfunktionen liegt in der Tatsache, dass alle diese Funktionen zu einer Familie von Hash-Funktionen gehören. Ein Angriff auf eine der beteiligten Funktionen kann daher leicht auf alle anderen übertragen werden. Bestünden jedoch verschiedene Familien, hätten die Anwender eine bessere Wahlmöglichkeit und wären gegen Angriffe besser geschützt.

Um diese Vielfalt von Funktionen zu erreichen ist derzeit jedoch mehr Grundlagenforschung im Bereich von sicheren Hash-Funktionen notwendig. Diese könnte entweder auf deutscher Ebene durch das BSI oder auf europäischer Ebene durch ENISA bzw. das Ecrypt-Netzwerk koordiniert werden. Auf Grund der bekannten amerikanischen Vorliebe für "Einzellösungen" (siehe SHA-1, DES/AES) wäre es vermutlich besser, wenn Deutschland oder Europa hier selbst die Initiative ergriffen. Wichtig ist dabei jedoch, dass die gesamte Forschung offen zugänglich bleibt, da nur auf diese Weise Vertrauen und damit Akzeptanz in neue Hash-Funktionen wachsen kann.

Mittelfristig ist es jetzt an der Zeit, Migrationspfade für Anwendungen zu erstellen, die entweder SHA-1 oder das deutlich unsicherere MD5 benutzen. Analog müssen sich die internationalen Standardisierungsgremien jetzt daran machen, alternative Standards zu schaffen, und SHA-1 durch dessen Nachfolger SHA-256 und SHA-512 zu ersetzen.

Für die Neuentwicklung von Produkten sollten Firmen nur noch die Funktionen SHA-256/384/512 verwenden, wie sie in FIPS 180-2 von der amerikantischen NIST vorgeschlagen. Kurzfristig stehen auch andere Alternativen bereit (z.B. Whirlpool), diese müssen aber erst noch gründlicher erforscht werden, bevor sie in der Produktion eingesetzt werden können.

Allgemeines Fazit: Wir sollten zum Notausgang gehen, aber wir können noch gehen; rennen ist derzeit überflüssig.

Veröffentlicht am 23. Februar 2005


http://fg-krypto.gi.de/presse/hashfunktionen.html