Hash-Algorithmen

Hash-Algorithmen spielen in der Informatik eine wichtige Rolle. Im Folgenden befasse ich mich hauptsächlich mit dem wohl populärsten Hash-Algorithmus MD5 und dessen Nachfolger dem SHA-1. Beide sind heutzutage noch im Einsatz, gelten jedoch als nicht mehr sicher.

Einleitung

Eine Hashfunktion (auf Deutsch: Streuwertfunktion) erzeugt aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, aus einer kleinen Zielmenge. Die einzelnen Stellen des Codes bestehen meist aus skalaren Werten der natürlichen Zahlen. Ein solcher Hashwert wird auch Fingerprint genannt, da er nahezu eindeutig eine größere Datenmenge beschreibt. Hashfunktionen unterscheiden sich in ihren Ein- und Ausgaben sowie den Einfluss bestimmter Muster und Eingaben.

Hash-Algorithmen

Hash-Algorithmen sind darauf optimiert Kollisionen zu vermeiden. Eine Kollision tritt dann auf, wenn zwei unterschiedliche Eingaben einer Hashfunktion zu der gleichen Ausgabe führen. Eine gute Hashfunktion zeichnet sich folglich dadurch aus, dass sie so wenige Kollisionen wie möglich erzeugt.

MD5 (Message Digest Algorithm 5)

MD5 ist eine weitverbreiteter Hash-Algorithmus, der aus einer Nachricht einen 128-Bit-Hashwert erzeugt. Er wurde 1991 von Ronald L. Rivest am Massachusetts Institute of Technology entwickelt, entspricht den heutigen Sicherheitsstandards jedoch nicht mehr. Entwickelt wurde er, weil das Vorgängermodell (MD4) als nicht mehr sicher eingestuft wurde.

Funktionsweise

Zunächst einmal wird die Länge der Nachricht auf ein Vielfaches von 512 Bit aufgefüllt. Das passiert auch, wenn die Nachricht bereits die erforderliche Länge besitzt. An das Ende der ursprünglichen Nachricht wird eine Eins angehangen und anschließend so viele Nullen, bis folgender Term erfüllt ist:
- (Länge der Nachricht) mod 512 - 64 = 0
Anschließend werden vier Funktionen definiert, die jeweils drei 32-Bit-Worte aufnehmen und ein 32-Bit-Wort zurück liefern.
· F(X, Y,Z) = (X ^ Y ) v (¬X v Z)
· G(X, Y,Z) = (X ^ Z) v (Y ^ ¬Z)
· H(X, Y,Z) = X ? Y ? Z
· I(X, Y,Z) = Y ? (X v ¬Z)
Weiterhin werden vier 32-Bit-Variablen definiert, die letztendlich zusammengesetzt den 128-Bit-Hashwert ergeben. Diese werden mit speziellen hexadezimalen Standardwerten initialisiert.
· h0 = 0x67452301
· h1 = 0xefcdab89
· h2 = 0x98badcfe
· h3 = 0x10325476
Alle 512-Bit-Blöcke der Nachricht werden in 16 32-Bit-Blöcke unterteilt. Nachdem die vier zuvor definierten Funktionen auf die ersten vier 32-Bit-Blöcke angewandt wurden, werden diese zu den vier Variablen des Hashwertes addiert. Das Ganze wiederholt sich so oft, bis der letzte 512-Bit-Block abgearbeitet wurde.

Schwächen

1996 wurde eine erste Schwäche des Algorithmus entdeckt, eine Kollision wurde festgestellt. Zwei unterschiedliche Nachrichten ergaben nach diesem Hashverfahren ein und denselben Hashwert. Die Sicherheit von MD5 war davon aber nicht sehr beeinträchtigt, da diese Nachrichten keinen Sinn ergaben und es auch kein festes Muster gab, wie man vorgehen sollte um gleiche Hashwerte zu erzeugen. Dennoch wurde empfohlen auf sichereren Algorithmen umzusteigen wie z.B. SHA-1.

Im nächsten Schritt gelang es Kollisionen systematisch zu erzeugen. Der Anfang einer Nachricht konnte beliebig gewählt werden, musste aber für alle Nachrichten, die den gleichen Hash-wert erzeugen sollen, fest vorgegeben sein. Die Fortsetzung der Nachricht konnte in absehbarer Zeit errechnet werden, sodass man auf den gleichen Wert kommt. Dieser Hashwert bleibt ebenso gleich, wenn man dieser bisher erzeugten Nachricht ein Suffix anhängt.

2004 gelang es chinesischen Forschern Kollisionen mit unterschiedlichen Anfangsstrings zu erzeugen. 2008, nach einer Verfeinerung der eben erwähnten Attacke, haben Wissenschaftler ein vertrauenswürdiges A-Zertifikat erstellt. Damit war es möglich für jede beliebige URL ein SSL-Zertifikat und somit die vorherrschende Verschlüsselung im Web auszuhebeln. Zur Kollisionserzeugung wurde ein Cluster von 200 Playstation 3 benutzt. Ebenfalls ist seitdem der Aufwand gesunken.

Zusammenfassend ist zu sagen, dass es nun möglich ist zwei Dokumente zu erzeugen, die den gleichen Hashwert ergeben.

Verwendung

MD5 werden häufig als Prüfsummen eingesetzt, wie sie uns von den CRC Prüfsummen bekannt sind. Dabei wird zunächst einmal vor dem Verschicken einer Datei ein Hashwert erzeugt. Nachdem diese Datei beim Zielcomputer angekommen ist, wird erneut ein Hashwert erzeugt und mit dem alten verglichen um diese Datei eben auf Übertragungsfehler hin überprüfen zu können.

Beispiele

Der Hashwert der Nachricht „dies soll zu einem Hashwert konvertiert werden“:
4b8a9a418b2363acd67035e0dab5eb3e
Der Hashwert der Zeichenfolge Null ist:
d41d8cd98f00b204e9800998ecf8427e

SHA (Secure Hash Algorithm)

SHA dient ebenfalls der Berechnung eines eindeutigen Hashwerts. Dieser besteht aus 160 Bit, für Daten bis ca. 2 Exbibyte. Intern werden 512 Bit Blöcke bearbeitet. Der Algorithmus ähnelt dem MD4 von Ronald L. Rivest, ist jedoch durch den längeren Hashwert nicht so anfällig für Kollisionen. Die Korrektur eines Designfehlers führte 1995 dazu, dass der Algorithmus ab da SHA-1 heißt. Die alte Version des Algorithmus ist unter dem Namen SHA-0 bekannt. Ebenfalls soll dieser Algorithmus in neueren Entwicklungen nicht mehr eingesetzt werden, da man eine wesentliche Schwäche entdeckt hat.

Vom Jahre 2002 bis 2004 wurden weitere Versionen des Algorithmus veröffentlicht die im Allgemeinen unter der Bezeichnung SHA-2 zusammengefasst werden:

• SHA-224
• SHA-256
• SHA-384
• SHA-512

Wobei die Zahl der Bezeichnung für die Größe des Hashwerts in Bit steht.

SHA-256

Bei diesem Algorithmus werden die Quelldaten in 512-Bit-Blöcke bzw. 16 32-Bit-Wörter aufgeteilt und iterativ mit 64 Konstanten und sechs logischen Funktionen verrechnet. Dabei wird mit einem Start-Hash aus acht 32-Bit-Wörtern begonnen. Dazu werden die ersten 32 Bits des Nachkommateils der Quadratwurzeln der ersten
acht Primzahlen (2 bis 19) verwendet.

SHA-224

Bei SHA-224 wird exakt der gleiche Algorithmus verwendet, der Initialhash wird jedoch mit acht anderen Werten gesetzt (Bits 33 bis 64 der Nachkommastellen der Quadratwurzeln der Primzahlen ab 23). Beim Endergebnis wird einfach das achte 32-Bit-Wort weggelassen.

SHA-512

Bei SHA-512 wird mit 1024-Bit-Blöcken und einer Wortbreite von 64 Bit gearbeitet. Es werden 80 64-Bit-Konstanten und sechs logische Funktionen verwendet. Der Initialhash besteht aus acht 64-Bit-Werten, wobei auch hier die Nachkommastellen der Quadratwurzeln der ersten acht Primzahlen herangezogen werden.

SHA-384

Für SHA-384 gilt der gleiche Algorithmus. Der Initialhash wird allerdings aus den 64 Nachkommabits der Quadratwurzeln der nachfolgenden Primzahlen (23, 29 usw.) berechnet. Am Ende werden vom Ergebnis nur die ersten sechs 64-Bit-Wörter genommen.

Schwächen

2005 schrieb erstmal ein Kryptographieexperte dass es Wissenschaftler gelungen sei den Aufwand der Kollisionserrechnung von 2^80 auf 2^69 zu verringern. Die Anzahl an Berechnung befanden sich im Rahmen des Möglichen mittels Hochleistungsrechnern. Kollisionen wurden bis heute jedoch nicht veröffentlicht. Kurze Zeit später wurde der Aufwand sogar noch auf 2^63 reduziert. 2006 wurde ein Angriff auf diesen Algorithmus gestartet, der es sogar ermöglichte 25% der Nachricht zu fälschen. Um auf diese Weise ein Dokument zu fälschen musste aber der restliche Teil der Nachricht ebenfalls so erzeugt werden, sodass der Hashwert übereinstimmt. Dadurch ergibt sich in diesem Teil eine sinnlose Ansammlung an Zeichen, auch als Datenmüll bekannt. Das kann aber vor dem eigentlichen User kaschiert werden.

Beispiele

Der Hashwert der Nachricht „dies soll zu einem Hashwert konvertiert werden“:
2350db69daef97adc45b1aecaceb82e8a39e2576
Der Hashwert der Zeichenfolge Null ist:
da39a3ee5e6b4b0d3255bfef95601890afd80709

Zusammenfassung

Zusammenfassend ist zu sagen, dass diese Algorithmen, so kompliziert sie auch erscheinen mögen, gravierende Schwächen haben und damit als nicht sicher eingestuft werden müssen. Dennoch ist der Aufwand beispielsweise SHA-1 zu knacken so hoch, dass es sich für die meisten nicht lohnen würde. Zudem wäre ein schneller Umstieg auf vermeintlich sicherere Algorithmen nicht die Lösung, da diese bisher zu wenig erforscht worden wären.

Literatur

[CH07] Christian Henrich: Security properties of hash functions / Englisch (2007)
[LIN98] SHA-1 geknackt http://www.heise.de/security/meldung/SHA-1-geknackt-Nachfolger-gesucht-135948.html Stand: 21.11.09
[WIKI09] Message-Digest Algorithm 5 http://de.wikipedia.org/wiki/Md5 Stand: 21.11.09
[WIKI09] Secure Hash Algorithm http://de.wikipedia.org/wiki/Secure_Hash_Algorithm Stand: 21.11.09

Autor des Beitrags

Alex Schuhaida