Prolog

Angenommen, du möchtest mit einem Freund eine Datei austauschen. Dieser speichert sie auf einem USB-Stick und hinterlegt ihn für dich in deinem Büro.

Als du nun die Datei öffnen möchtest, überkommt dich spontan die Frage, ob nicht jemand in deiner Abwesenheit den USB-Stick und dessen Daten verändert haben könnte.
Ist es möglich, so überlegst du, zu überprüfen, ob die Datei noch dieselbe ist, welche dein Freund auf den USB-Stick kopiert hatte?

Theorie

Die grundlegende Idee ist bei Hashfunktionen recht simpel: Man kann eine beliebig große Datei oder Datenmenge in eine Zeichenfolge mit fester Länge umwandeln.
Das heißt, dass man für jede Art von Daten (Zeichenfolgen, Archive, Daten von CDs als iso...) einen Hashwert, auch Prüfsumme genannt, generieren kann.

Daten beliebiger Größe -> Zeichenfolge fester Länge

Damit wir jetzt anhand der Prüfsumme unsere Datei möglichst eindeutig identifizieren können, muss die Hashfunktion jedoch noch einige Bedingungen erfüllen.

Einweg-Funktion

Es darf nicht möglich sein, aus einer Prüfsumme die ursprünglichen Daten wiederherzustellen.
Dies gilt automatisch für schwach kollisionsresistente Hashfunktionen.

Schwache Kollisionsresistenz (second pre-image resistance)

Es darf in realistischer Zeit nicht möglich sein, zu Daten und deren Prüfsumme weitere Daten zu generieren, die dieselbe Prüfsumme haben.
Dies gilt automatisch für kollisionsresistente Hashfunktionen.

Kollisionsresistenz

Eine Kollision liegt vor, falls zwei unterschiedliche Daten dieselbe Prüfsumme ergeben.
Kollisionen können leider nicht gänzlich ausgeschlossen werden, da es bei der Umwandlung potenziell unendlich vielen Eingabemöglichkeiten auf eine begrenzte Anzahl an Prüfsummen zu Kollisionen kommen muss.

Die Kollisionsresistenz erfordert daher nur, das solch eine Kollision nicht in realistischer Zeit berechnet werden kann.

Hashfunktionen

In der Praxis werden vor allem vier Funktionen verwendet: MD5 und SHA-1-3.
Um den Post nicht zu lang zu machen, werde ich hier vorerst nur auf MD5 und SHA-1 eingehen.
SHA-2 und SHA-3 folgen in einem zweiten Teil.

MD5

MD5-Prüfsummen sind 32 Zeichen (128Bits) lang und werden in Hexadezimalschreibweise (0-9, A-F) dargestellt.

Sicherheit

Die ersten Kollisionen für das auf Endgeräten verwendete MD5 wurden 2004 von X. Wang, D. Feng, X. Lai und H. Yu gefunden. 2006 veröffentlichte V. Klima eine Möglichkeit, Kollisionen auf handelsüblichen Computern in unter einer Minute zu berechnen.
Da die Kollisionsresistenz nicht mehr gegeben ist, ist von der Verwendung von MD5 in den meisten Anwendungsfällen abzuraten.

SHA-1

SHA-1 Prüfsummen sind 160bits lang und werden in 40 Zeichen (hexadezimal) angegeben.
SHA-1 gehört zur gleichen Familie der iterativen Hashfunktionen wie MD5 und wird daher ähnlich konstruiert.

Sicherheit

Auch wenn die Kollsionsberechnung in SHA-1 derzeit noch aufwändig ist, ist es dennoch empfehlenswert, bei sicherheitskritischen Anwendungen (und anderen, wo Kollisionsresistenz wichtig ist) auf SHA-1 zu verzichten.
Die Historie derzeit bekannter Angriffe kann hier angesehen werden.

Beispiel

Über die GNU-Programme md5sum und sha1sum können Prüfsummen generiert werden.

echo "Hello World" > /tmp/myfile

md5sum /tmp/myfile

e59ff97941044f85df5297e1c302d260 /tmp/myfile

sha1sum /tmp/myfile

648a6a6ffffdaa0badb23b8baf90b6168dd16b3a /tmp/myfile

Quellen

• Hans Delfs, Helmut Knebl - Introduction to Cryptography, Third Edition

---

Einen Link zu meinem Vorstellungspost findet ihr hier.