Montag, 1. M�rz 2010


Topthema

Donnerstag, 3. Mai 2007 | Topthema

About Security #103: Hashfunktionen — MD4 und Verwandte

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/035555)

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.

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

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 < 2^64 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 < 2^64 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 < 2^128 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 2^80 auf 2^63 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:

About Security: Die komplette Serie
  • 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.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � Hashfunktionen"

Kommentare

Folgende Links könnten Sie auch interessieren