Channel Security

MD4, MD5 und SHA sowie SHA-1 sind aktuelle Hashfunktionen. MD4 wurde 1990 von Ronald L. Rivest mit dem Ziel entwickelt, einfach implementierbar zu sein und auf 32-Bit-Rechnern besonders effektiv zu laufen. MD4 wird in RFC 1320 beschrieben und erzeugt wie der letzte Woche vorgestellte MD2-Algorithmus einen 128-Bit-langen Hashwert. MD4 arbeitet mit 512-Bit-Blöcken, die beliebig lange Eingabe wird dafür vor Beginn der Komprimierung entsprechend aufgefüllt. 1995 wurde von Hans Dobbertin beschrieben, wie Kollisionen im Zeitraum unter einer Minute berechnet werden können. Für eine reduzierte Version wurde 1998 bewiesen, dass es keine Einweg-Funktion ist. Bereits damit galt MD4 als gebrochen und sollte nicht mehr eingesetzt werden. 2004 wurden Angriffe präsentiert, die sich teilweise von Hand durchführen lassen.

Eine direkte Weiterentwicklung von MD4 ist der 1991 von Ronald L. Rivest entwickelte MD5-Algorithmus, beschrieben in RFC 1321. MD5 liefert wie MD4 einen 128 Bit langen Hashwert und arbeitet ebenfalls mit 512 Bit großen Blöcken. 2004 wurde ein praktischer Angriff beschrieben, womit MD5 ebenfalls gebrochen ist. Der Algorithmus wird trotzdem noch vielfach eingesetzt, was besser unterlassen werden sollte.

Eine andere Weiterentwicklung von MD4 ist SHA (inzwischen als SHA-0 oder SHA0 bezeichnet), der 'secure hash algorithm'. SHA wurde 1993 als Secure Hash Standard vom US-amerikanischen 'National Institute of Standards and Technologies' (NIST) als FIPS PUB 180 veröffentlicht. SHA verarbeitet Nachrichten bis zu einer Länge von Bit mit einer Blockgröße von 512 Bit und liefert einen 160 Bit langen Hashwert. Wegen eines Designfehlers wurde der Algorithmus 1995 korrigiert (Hinzufügen eines Links-Shifts). Die korrigierte Version wird als SHA-1 bezeichnet und ist in FIPS PUB 180-1 spezifiziert.

Der bei SHA-0 und SHA-1 im Vergleich zu MD4 und MD5 längere Hashwert erschwert Brute-Force-Angriffe zum Finden von Kollisionen. 2002 wurden in FIPS PUB 180-2 (PDF) drei weitere Versionen veröffentlicht: SHA-256 verarbeitet ebenso wie SHA-1 Nachrichten bis zu einer Länge von Bit mit einer Blockgröße von 512 Bit, liefert aber einen 256 Bit langen Hashwert. SHA-384 und SHA-512 verarbeiten Nachrichten bis zu einer Länge von Bit mit einer Blockgröße von 1024 Bit und liefern einen 384 bzw. 512 Bit langen Hashwert. 2005 wurden erste Angriffe auf SHA-1 veröffentlicht, die den Rechenaufwand für die Berechnung einer Kollision von ursprünglich auf Berechnungen reduziert. Im August 2006 wurde ein Angriff veröffentlicht (PDF), bei dem ein Teil der gefälschten Nachricht frei gewählt werden kann.

Die Bundesnetzagentur, zuständig für die Bewertung der Algorithmen für digitale Signaturen nach dem Signaturgesetz, hält zurzeit (Stand: April 2007) SHA-1 noch bis Ende 2009 für geeignet (PDF), SHA-224 und die Varianten mit längeren Hashwerten bis Ende 2012.

Angriffe auf Hashfunktionen

Man unterscheidet zwei Arten von Angriffen auf Hashfunktionen:

• Bei einem so genannten Kollisionsangriff sollen zwei Nachrichten mit identischem Hashwert gefunden werden: Gesucht werden zwei Nachrichten M und M' (M ≠ M') mit H(M) = H(M').
• Bei einem so genannten Preimage-Angriff wird zu einer gegebenen Nachricht (dem preimage) und dem dazu berechneten Hashwert eine zweite Nachricht mit identischem Hashwert gesucht: Gegeben sind M und H(M), gesucht wird M' (M ≠ M') mit H(M) = H(M'). Im Rahmen eines gezielten Angriffs kommt als weitere Einschränkung hinzu, dass M' ein sinnvoller und für den Angreifer nützlicher Text ist.

Der Aufwand für die beiden Angriffe unterscheidet sich stark, wie man am so genannten Geburtstagsparadoxon erkennen kann:

• Um mit einer Trefferwahrscheinlichkeit von 50 Prozent jemanden zu finden, der an einem bestimmten Tag Geburtstag hat, werden 253 Personen benötigt (Preimage-Angriff).
• Werden dagegen nur zwei Personen gesucht, die an demselben Tag Geburtstag haben, reichen für eine Trefferwahrscheinlichkeit von 50 Prozent 23 Personen aus. Bei mehr als 57 Personen steigt die Wahrscheinlichkeit auf über 99 Prozent an (Kollisionsangriff).

Abgeleitet vom Geburtstagsparadoxon wurde der so genannte Geburtstagsangriff: Es werden mehrere Varianten der originalen Nachricht erstellt, deren Unterschiede dem Opfer nicht auffallen. Ebenso werden Varianten der gefälschten Nachricht erstellt. Der Angreifer sucht dann ein Paar aus Original und Fälschung, die den gleichen Hashwert ergeben. Signiert das Opfer danach das ausgewählte Original, gilt diese Signatur auch für die dazu gehörende Fälschung. Um einem Geburtstagsangriff entgegenzuwirken, gibt es zwei Möglichkeiten: Ein möglichst großer Hashwert erhöht den Aufwand zum Finden passender Texte. Ändert der Signierer den Text direkt vor dem Signieren, läuft der Angriff ins Leere: Die Signatur des durch den Signierer geänderten Textes passt nicht mehr zur vorbereiteten Fälschung.

Die Auswirkungen der Angriffe auf die Sicherheit der Hashfunktionen ist das Thema der nächsten Folge.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – Hashfunktionen"

• About Security #102: Hashfunktionen – Einführung
• About Security #103: Hashfunktionen – MD4 und Verwandte
• About Security #104: Hashfunktionen – Sicherheit