1. Einweg Hash-Funktionen (One-Way Hash Functions)

1.1 Definition der kryptographischen Hash Funktion

Eine kryptographische Hash Funktion ist eine Hash Funktion mit bestimmten zusätzlichen Sicherheitseigenschaften damit diese sich in verschiedenen Anwendungen für Informationssicherheit, wie Authentifizierung und Nachrichten Integrität, eignet. Eine Hash Funktion nimmt einen String (oder Nachricht) von beliebiger Länge als Input und produziert einen Output fixer Länge, der manchmal als Message Digest bzw. Digitaler Fingerabdruck bezeichnet wird.
Hash Funktionen sind Einweg Funktionen, was bedeutet, dass aus einem gegebenen Message Digest H(M) es schwierig ist die Message M wieder zu finden. Schwierig wird in diesem Fall mathematisch in der Komplexitätstheorie (provably hard problem) definiert.

zurück zur Übersicht

1.2 Überblick

Die Sicherheitseigenschaften von Hash Funktionen werden gebraucht um sicherzustellen, dass der Message Digest für einen potentiellen Angreifer "zufällig" aussieht, der Message Digest keine Information über die Nachricht selbst ausgibt, und keine andere Nachricht gefunden werden kann, die den selben Message Digest produziert. Jede Änderung an der Nachricht, wenn auch nur ein einzelnes Bit, soll einen drastisch veränderten Message Digest ergeben, wenn dieser neu von der empfangenen Nachricht generiert wird. Eine kryptographische Hash Funktion wird als sicher empfunden wenn es nicht möglich ist den Inhalt der Nachricht aus dem Message Digest zu bestimmen und es nicht möglich ist Kollisionen (collisions) zu finden, wobei zwei unterschiedliche Nachrichten den selben Message Digest besitzen. Im ersten Fall kann ein unsicherer Message Digest verwendet werden um die Nachricht die verschlüsselt wurde zu rekonstruieren, womit die Verschlüsselung fehlschlagen würde. Im zweiten Fall, wenn es möglich ist eine andere Nachricht zu finden, die den selben Digest produziert, kann der Angreifer Nachrichten unbemerkt austauschen - dies wäre eine gefährliche Situation.

zurück zur Übersicht

1.3 Kryptographische Eigenschaften von Hash Funktion

Mathematisch ist eine kryptographische Hash Funktion eine Hash Funktion die folgende Eigenschaften aufweist:

Preimage resistant: Aus einem gegebenen Hash Value h soll es schwierig sein eine Message M zu finden die h = hash(M) erfüllt.

Angriff auf die preimage Resistenz: Wenn es möglich ist aus dem Hash h wieder einen Text zu produzieren, der den selben Hash Value besitzt, wäre es beispielsweise möglich oftmals verwendete Password Hash Werte zu besiegen. Es würden dadurch nicht die aktuell verwendeten Input Daten herausgefunden werden, aber das ist nicht mehr wichtig. Alles was zählt ist, dass der Hash des Passworts übereinstimmt, damit würde der Zugriff garantiert sein. Kollisionen bedeutet dabei, dass mehr als ein Passwort akzeptiert wird.

Second preimage resistant: Mit einer gegebenen Message M1 soll es schwierig sein eine andere Message M2 (unterschiedlich zu M1) zu finden, so dass gilt hash(M1) = hash(M2).

Angriff auf die Second Preimage Resistenz: Wenn es möglich ist mit einer gegebenen Message M1 eine andere Message M2 zu finden, die beide den selben Hash Value ergeben, könnte man eine authentifizierte Nachricht durch eine andere ersetzen.

Collision resistant: Es soll schwierig sein zwei unterschiedliche Nachrichten M1 und M2 zu finden, so dass hash(M1) = hash(M2) gilt. Aufgrund des Geburtstagsparadoxons heißt das die Hash Funktion muss ein größeres Image besitzen als für die preimage resistance gefordert wird.

Angriff auf die Kollisionsresistenz: Wenn es möglich ist zwei Nachrichten zu erstellen, die den selben Hash Wert produzieren werden Digitale Signaturen suspekt. Ein signiertes Dokument könnte dann verändert oder ausgetauscht werden ohne, dass die Veränderung durch den Empfänger bemerkt wird.

Scharfe Relationen der Eigenschaften:

aus preimage resistant folgt nicht second preimage resistant.
aus second preimage resistant folgt nicht preimage resistant.
aus collision resistant folgt second preimage resistant.

Schwierig wird in diesen Eigenschaften wieder mathematisch in der Komplexitätstheorie (provably hard problem) definiert und bedeutet, dass dieses Problem so schwierig ist (in 'NP'), dass alle Experten und informierten Beobachter keine Aussicht auf eine mögliche Lösung haben.

zurück zur Übersicht

2. Implementierte Hash Algorithmen

In der ActiveX Komponente sind nachfolgende Hash Code bzw. Manipulation Detection Code (MDC) Algorithmen implementiert. All diese Funktionen können auf Dateien und Strings angewendet werden.

Tabelle 1: Manipulation Detection Codes und Hash Algorithmen

zurück zur Übersicht

3. Beschreibung von einigen Hash Algorithmen

3.1 CRC und CRC-32

CRC ist ein Akronym für Cyclic Redundancy Check. Ein CRC ist eine "digitale Signatur" in der Datenrepräsentation. Der am weitesten verbreitete CRC ist CRC32, in welchem die "digitale Signatur" als eine 32-bit Zahl dargestellt wird. Die Länge der Daten über welche die CRC berechnet wird kann beliebig sein. Als source dient entweder eine Datei oder ein String. Der CRC Algorithmus hat mehrere für Hash Algorithmen allgemeine charakteristische Eigenschaften. Erstens, wenn man die CRC mehrmals von den gleichen Daten berechnet muss man jedes mal das gleiche Ergebnis erhalten. Zweitens, wenn man die CRC von zwei unterschiedliche Daten berechnet muss das Ergebnis der CRC sehr unterschiedliche Werte liefern. Wenn man nun die CRC über die gleichen Daten zweimal berechnet erhält man die gleiche digitale Signatur. Jedoch wenn man die CRC von Daten berechnet, die sich auch nur in einem Byte unterscheiden erhält man zwei sehr unterschiedliche digitale Signaturen. Mit einer 32-bit CRC gibt es über 4 Milliarden mögliche CRC Werte. Um dies exakt zu formulieren, es sind 2^32 oder 4294967296 Möglichkeiten. Mit so einer großen Anzahl an CRC Werten ist es nicht sonderlich schwierig für unterschiedliche Daten auch einzigartige CRC Werte zu generieren. Aber, es ist möglich, dass zwei komplett unterschiedliche Datenstücke dieselbe CRC erhalten. Dies ist dann der Punkt wo sichere Hash Algorithmen eingesetzt werden.

zurück zur Übersicht

3.2 Warum verwendet man CRCs?

Die meiste Zeit werden CRCs verwendet um Daten mit einem Integritätscheck zu vergleichen. Angenommen man möchte zwei Dateien vergleichen und herausfinden ob diese identisch sind. Wenn die CRC Werte unterschiedlich sind, dann hat man eine 100%ige Garantie, dass diese Dateien nicht gleich sind. Wenn die CRC Werte gleich sind, dann kann man zu 99% sicher sein, dass die Dateien gleich sind.

zurück zur Übersicht

3.3 Message-Digest Algorithmen (MD)

MD5 ist Teil der Message-digest Algorithmen Familie MD2, MD4 und MD5 wurden von Ron Rivest in der Zusammenarbeit mit dem MIT Laboratory for Computer Science und der RSA Data Security, Inc. entwickelt. MD2 und MD4 sind ältere Versionen, haben Schwächen und sollten nicht benutzt werden. MD2 ist aus dem Jahre 1989 und MD4 von 1990. Der MD5-Algorithmus ist seit 1991 bekannt. Der MD5 Algorithmus ist eine Erweiterung des MD4 Message-digest Algorithmus, zwar etwas langsamer als MD4, bietet aber auf der anderen Seite eine höhere Sicherheit. MD5 wird als mäßig sicher betrachtet. Alle drei Algorithmen verarbeiten eine Nachricht von unbeschränkter Länge und produzieren einen 128-bit langen Message Digest. Dies ist eine 39-stellige Dezimalzahl. Bei MD5 ist es nahezu unmöglich, die Nachricht so zu verändern, dass der Inhalt sich ändert, aber der Hash-Code gleich bleibt. Sind die Hash Code gleich, aber die Nachricht unterschiedlich, haben wir das Problem einer Kollision. Da ein MD5-Hash-Wert 128 Bit lang ist, kann er 2^128 verschiedene Ausgabewerte annehmen. Zwangsläufig sind unter 2^128 + 1 verschiedenen Nachrichten mindestens zwei Texte mit gleichem Hash-Wert. Die Wahrscheinlichkeit, dass eine beliebige Nachricht den gleichen Hash-Wert wie eine vorgegebene Nachrichten hat, ist 1/(2^128). Die Wahrscheinlichkeit jedoch, dass zwei beliebig gewählte unterschiedliche Nachrichten den gleichen Hash-Wert haben, ist deutlich höher.
Ebenso kompliziert gestaltet es sich, eine Botschaft zu generieren, die einen vorgegebenen Fingerabdruck besitzt. Doch unmöglich ist das nicht. 1994 haben Paul van Oorschot und Mike Wiener gezeigt, dass sich in weniger als einem Monat mit einem Budget von etwa zehn Millionen US-Dollar (Stand 1994) ein 128-Bit-Schlüssel knacken lässt. Die Kosten halbieren sich etwa alle 18 Monate. Im Durchschnitt tritt alle 24 Tage eine Kollision bei MD5 auf.

zurück zur Übersicht

3.4 Secure Hash Algorithmen (SHA)

Der Secure Hash Algorithmus (SHA) spezifiziert im Secure Hash Standard (SHS), wurde von der NIST entwickelt und publiziert als ein Federal Information Processing Standard (FIPS PUB 180). SHA-1 war eine Revision von SHA der im Jahr 1994 präsentiert wurde. Die Revision korrigierte einen unpublizierte Schwachstelle in SHA. Das Design ist sehr ähnlich zur MD4 Familie von Hash Funktionen entwickelt von Ron Rivest. Der SHA-1 Algorithmus produziert von Nachrichten in beliebiger Länge einen 160-bit Message Digest. Der Algorithmus ist etwas langsamer als MD5, aber durch den längeren Message Digest bietet SHA-1 einen höheren Sicherheitsstandard und macht ihn sicherer gegen brute-force Kollision und Inversion Attacken. Das Forschungsteam von Xiaoyun Wang, Yiqun Lisa Yin, und Hongbo Yu (hauptsächlich von der Shandong Universität in China) haben im Semptember 2005 eine neue Attacke gegen SHA-1 mit der Komplexität 2^63 (statt 2^80 bei brute force) entwickelt. Nun ist die Suche nach Kollisionen bei SHA-1 im Bereich des Möglichen und der Algorithmus gebrochen.

Motiviert durch die AES Auswahl, hat die NIST einen Ersatz des SHA-1 Hash Algorithmus durch SHA-224, SHA-256, SHA-384 und SHA-512 Algorithmen vorgestellt. Diese wurden mit einem Level der Kollisionsfestigkeit (collision resistance) ausgestattet der äquivalent zur Sicherheit der jeweiligen AES Schlüssellängen ist. Die Länge des Message Digest beträgt für SHA-1 160 bit (20 byte). Die Länge des Message Digest für die neuen SHA-224, SHA-256, SHA-384, und SHA-512 Algorithmen sind 224 bit (28 byte), 256 bit (32 byte), 384 bit (48 byte), 512 bit (64 byte). Die Zunahme der Länge ist signifikant, womit die neuen Algorithmen äußerst schwierig zu brechen sind. Bisher ist kein Angriff bekannt, der die Nutzung von SHA-2 in Frage stellt.

zurück zur Übersicht