8.2.4. Einweg-Hashfunktionen

Hashfunktionen finden in der Informatik eine breite Anwendung. Sie dienen allgemein dazu, Daten variabler Länge (z.B. Zeichenketten) auf Werte fester Länge (beispielsweise ganzzahlige Feldindexe) abzubilden. Das jeweilige Ergebnis nennt man Hashwert (hash value) oder kurz nur Hash. Eine sehr einfache Hashfunktion stellt die XOR-Verknüpfung aller Bytes der Ausgangsdaten dar.

Für die Kryptologie sind primär Einweg-Hashfunktionen relevant, also jene, die sich zwar leicht berechnen, aber nur sehr schwer invertieren lassen. D.h., die Invertierung muß einen extremen Aufwand verursachen und sollte nach Möglichkeit die gesamte verfügbare Rechen- und Speicherkapazität bei weitem übersteigen. Ein durch eine solche Funktion bestimmter Hashwert wird auch als Message Digest bzw. Fingerabdruck (fingerprint) bezeichnet.

Eine kurze Bemerkung nebenbei:

Beutelspacher weist darauf hin, daß nicht bekannt ist, ob es Einweg-Funktionen theoretisch überhaupt gibt. Die Mathematiker konnten nämlich noch von keiner einzigen Funktion stringent nachweisen, daß es sich bei ihr um eine Einweg-Funktion handelt. Das heißt, man kennt keine Funktion, deren Funktionswerte in polynomialer Zeit berechnet werden können, deren Invertierung aber einen exponentiellen Aufwand verursacht. Für praktische Zwecke existieren allerdings Funktionen mit hinreichend guten Eigenschaften.

Eine Einweg-Funktion, die sich leicht invertieren läßt, sofern man über eine nicht aus der Funktion ableitbare geheime Zusatzinformation (Falltür oder trapdoor) verfügt, heißt Einweg-Funktion mit Falltür. Deren Existenz läßt sich wiederum nicht mathematisch beweisen. Es gibt allerdings auch hier praktisch nutzbare Kandidaten.

Eine Einweg-Hashfunktion H zeichnet sich durch folgende Eigenschaften aus:

Für bestimmte Zwecke wird zusätzlich die Kollisionsresistenz (collision resistance) gefordert, die besagt, daß es rechnerisch unmöglich ist, eine Kollision, d.h. zwei beliebige unterschiedliche Nachrichten zu finden, die denselben Hashwert haben, obwohl natürlich klar ist, daß es viele davon gibt, sobald deutlich mehr Nachrichten als Hashwerte existieren.

Anmerkung zum Aufwand zweier Attacken auf Einweg-Hashfunktionen:

Attacke 2 stellt eine wesentlich einfachere, d.h. weniger aufwendige Aufgabe als Attacke 1 dar. Es läßt sich zeigen, daß man bei Verwendung einer typischen Einweg-Hashfunktion mit n Bit langen Hashwerten im statistischen Mittel bei

um erfolgreich zu sein.

Unter Vernachlässigung der für die Aufwandsabschätzung unbedeutenden Faktoren 0,5 (bzw. 2-1) bei Attacke 1 und 1,2 bei Attacke 2 ergibt sich die auch häufig in der Literatur zu findende Aussage, daß

verursacht. Es sei hier explizit darauf hingewiesen, daß 2n das Quadrat von 2n/2 darstellt.

Die Attacke 2 wird auf Grund ihrer Analogie zu dem aus der mathematischen Statistik relativ bekannten Geburtstags-Paradoxon (birthday surprise oder birthday paradox) auch als birthday attack bezeichnet. Das Geburtstags-Paradoxon besagt, daß man mit einer erstaunlich geringen Anzahl zufällig ausgewählter Personen eine relativ große Wahrscheinlichkeit dafür erhält, daß mindestens zwei von ihnen am selben Tag Geburtstag haben, und daß diese Wahrscheinlichkeit mit steigender Personenzahl sehr schnell wächst. Die folgende Tabelle soll dies veranschaulichen:

Personen Wahrscheinlichkeit
23 0.507297234324
30 0.706316242719
40 0.891231809818
50 0.970373579578
60 0.994122660865

Dagegen benötigt man mindestens 183 zufällig ausgewählte Personen, wenn man erreichen möchte, daß die Wahrscheinlichkeit dafür, daß wenigstens eine dieser Personen an einem bestimmten (vorgegebenen) Tag Geburtstag hat, mindestens 0,5 beträgt.

Das Finden einer Person mit einem bestimmten Geburtstag ist analog zu Attacke 1. Das Finden zweier Personen mit identischem, aber beliebigem Geburtstag entspricht Attacke 2.

Für weitere Details sei auf entsprechende Publikationen zur mathematischen Statistik oder auf Stallings (speziell auf den recht gut verständlichen Anhang Mathematic Basis of Birthday Attack) und Menezes verwiesen.

Zur Abwehr von birthday attacks sollte man Hashfunktionen mit einem hinreichend großen n einsetzen. Die heute verfügbaren guten Verfahren erzeugen mindestens 160 Bit lange Hashwerte. Dabei muß ein Angreifer im Mittel ca. 280 Nachrichten testen, bevor er eine Kollision findet. Diese Attacke gilt momentan als nicht in angemessener Zeit durchführbar, wobei je nach konkreter Realisierung des Angriffs nicht nur die Rechenzeit, sondern möglicherweise auch der erforderliche Speicher eine nicht zu überwindende Barriere darstellt.

In verschiedenen Publikationen wird auch von kryptographischen, kryptographisch sicheren oder einfach nur sicheren Hashfunktionen gesprochen. Darunter werden meist nur die kollisionsresistenten, manchmal aber auch alle Einweg-Hashfunktionen verstanden.

Einweg-Hashfunktion sind öffentlich. Ihre Sicherheit liegt nicht in einem Geheimnis (Schlüssel), sondern im Einweg-Charakter begründet, d.h., die Ergebnisse hängen von den Argumenten in einer solch komplexen Weise ab, daß eine Umkehrung der Operation nicht möglich ist, obwohl man den verwendeten Algorithmus kennt. Sobald sich ein Bit der Nachricht ändert, bewirkt dies im Mittel eine Modifikation der Hälfte aller Bits des Hashwertes.

Gute Einweg-Hashfunktionen erzeugen zufällig aussehende Hashwerte. Diese Eigenschaft wird an vielen Stellen benötigt und genutzt.

Einige in der Praxis verwendete Einweg-Hashfunktionen

Zu den in der heutigen Praxis am häufigsten genutzten Einweg-Hashfunktionen gehören der von Ron Rivest entwickelte MD5 Message Digest Algorithm sowie der vom NIST in Zusammenarbeit mit der NSA entworfene und als a Secure Hash Algorithm bezeichnete SHA-1.

Ron Rivest hat noch zwei weitere bekannte Message-Digest-Algorithmen entworfen: MD2 und MD4. Auf dem MD4 bzw. den dabei von Rivest genutzten Design-Prinzipien basieren verschiedene andere Einweg-Hashfunktionen. Man spricht daher auch von der MD4-Familie. Hierzu gehören u.a. MD5 und SHA-1.

Das Bulletin Nr. 4 der RSA Laboratories vom 12. November 1996 mit dem Titel On Recent Results for MD2, MD4 and MD5 informiert über die bisher entdeckten Schwächen in den drei genannten Hashfunktionen, schätzt deren Folgen ab und gibt Empfehlungen für den Einsatz dieser Algorithmen. Das Dokument kann per WWW über die Seite http://www.rsa.com/rsalabs/html/bulletins.html bezogen werden.

Bei den im Bulletin 4 diskutierten Schwachstellen von MD2, MD4 und MD5 geht es primär um deren Kollisionsresistenz, die bei verschiedenen Signaturverfahren vorausgesetzt wird. Wichtig erscheint in diesem Zusammenhang der Hinweis, daß existierende digitale Signaturen vermutlich auch dann sicher bleiben, wenn sich später herausstellt, daß die beim Signieren verwendete Hashfunktionen nicht kollisionsresistent ist. Beim Attackieren existierender Signaturen kann der Angreifer nicht von Kollisionen profitieren, da die unterschriebene Nachricht sowie deren Hashwert fest vorgegeben sind und nicht durch ihn gewählt werden können. Daher muß er weiterhin die schwierige Aufgabe lösen, ein second preimage zu finden. Wörtlich heißt es im Bulletin 4 dazu:

Interestingly, digital signatures previously signed using a hash function that is no longer collision resistant are likely to remain safe from compromise. In attacking existing signatures, the task of the cryptanalyst is essentially that of finding a second preimage since the first preimage (the message signed) and the associated hash value are already fixed. This is a much harder problem than that of generally finding a collision and it might well be the case that techniques that generate collisions for a hash function offer no advantage in finding a second preimage. Thus, existing signatures might well remain free from risk of compromise even when collision-resistance is lost.

Nachfolgend einige Bemerkungen zu ausgewählten Verfahren, wobei sich die i.a. besonders interessanten Aussagen zur Sicherheit von MD2, MD4 und MD5 teilweise auf das o.g. Bulletin 4 beziehen:

Die Algorithmen SHA-1, RIPEMD-160 und RIPEMD-128 wurden in den internationalen Standard ISO/IEC 10118-3 (Information technology -- Security techniques -- Hash-functions, Part 3: Dedicated hash-functions) aufgenommen.

Dobbertins erfolgreiche Attacken gegen den MD4 verstärkten bei Eli Biham sowie dem in Cambridge tätigen englischen Kryptologen Ross Anderson die Frage, wie lange die MD4-Familie noch ungebrochen bleiben wird. Beide Wissenschaftler entwickelten deshalb im September 1995, als Biham zu einem Arbeitsbesuch in Cambridge weilte, einen völlig neuen, nicht zur MD4-Familie gehörenden Hashalgorithmus mit dem Namen Tiger.

Dieses Verfahren wurde nicht mehr für 32-Bit-Maschinen, sondern bereits für 64-Bit-Prozessoren (z.B. DEC Alpha) optimiert, läuft aber auch auf der existierenden Hardware immer noch ziemlich schnell. So geben die Autoren an, daß ihr Algorithmus auf 32-Bit-Systemen so schnell wie SHA-1 und auf 64-Bit-Maschinen sogar 2,5 Mal schneller als SHA-1 arbeitet.

Tiger nutzt 8x4-Bit-S-Boxen, die eine starke Diffusion sowie eine hohe Resistenz gegen die differentielle Kryptoanalyse bewirken sollen, und erzeugt im Standardfall Hashwerte von 192 Bit. Diese können bei Bedarf auf 160 oder 128 Bit gekürzt werden, wobei die Entwickler davon ausgehen, daß selbst diese kürzeren Varianten sicherer sind als die anderen Verfahren mit derselben Ausgabelänge.

Tiger unterliegt keinen Nutzungsbeschränkungen oder Patenten. Er kann also generell kostenfrei eingesetzt werden. Die Autoren stellen eine Referenzimplementierung in der Sprache C zur Verfügung.

Wer mehr über Tiger erfahren möchte, sollte sich Eli Bihams WWW-Seite http://www.cs.technion.ac.il/~biham/Reports/Tiger/ ansehen. Hierüber findet man u.a. eine Beschreibung des Algorithmus sowie letzte Neuigkeiten.

Einweg-Hashfunktionen sind Gegenstand intensiver Forschungen. Hinsichtlich des aktuellen Wissens über deren Sicherheit kommt der belgische Kryptologe Bart Preneel, Mitautor von RIPEMD-160, in seinem vom 27.2.1997 datierten Paper The State of Hash Functions [ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/preneel/hash_seminar.ps.gz] u.a. zu folgenden interessanten Schlußfolgerungen:

In dem oben erwähnten Artikel The Cryptographic Hash Function RIPEMD-160 findet sich zum Thema Sicherheit von Hashfunktionen eine ähnlich kritische Aussage:

It is not an understatement to say that designers have typically overestimated the security of their hash functions.

Anwendungsgebiete

Einweg-Hashfunktionen lassen sich zu verschiedenen Zwecken einsetzen. Hier einige Beispiele:

Es sei noch erwähnt, daß es einige Vorschläge gibt, symmetrische Verschlüsselungsverfahren auf der Basis von Einweg-Hashfunktionen zu konstruieren. Allerdings ist hier Vorsicht geboten. Gute Einweg-Hashfunktionen garantieren keineswegs automatisch gute Verschlüsselungsverfahren, da die jeweils gestellten Anforderungen verschieden sind. Schneier rät von der Verwendung solcher Chiffren ab, da sie nicht hinreichend kryptoanalytisch untersucht wurden.

Wegen ihrer Unumkehrbarkeit nutzt man Einweg-Hashfunktionen manchmal auch dazu, die Kenntnis eines bestimmten Geheimnisses (Schlüssel, Paßwort, ...) glaubhaft zu machen, ohne dieses offenzulegen. Nachfolgend zwei Beispiele:

HMAC

Wir beobachten ein wachsendes Interesse daran, zur MAC-Berechnung keine Verschlüsselungsverfahren, sondern an deren Stelle Einweg-Hashfunktionen zu nutzen. Dies hat u.a. folgende Gründe:

Generell ist dabei zu beachten, daß Hashfunktionen ursprünglich nicht für die Authentifizierung von Nachrichten entworfen wurden. Deshalb ist große Sorgfalt geboten, wenn man sie als Bausteine eines MAC-Algorithmus einsetzt. Eine von vielen Schwierigkeiten besteht z.B. darin, daß Hashfunktionen von Hause aus keinen Schlüssel verwenden. Die Abhängigkeit von einem geheimen Key muß also durch geeignete Konstruktionen nachträglich eingeführt werden.

Es gibt nun eine ganze Reihe von Vorschlägen, wie der MAC konkret gebildet werden könnte bzw. sollte. So wurde in den Sicherheitsprotokollen von SNMPv2 (RFC 1446) noch die simple Version spezifiziert, einen geheimen Schlüssel vor die Nachricht zu setzen und den Hashwert dieser so entstehenden Bytefolge als kryptographische Prüfsumme zu verwenden. Mittlerweile ist bekannt, daß genau diese Version (auch secret prefix genannt) unsicher ist. Aber auch das Anfügen des Schlüssels (secret suffix) bzw. die Kombination von geheimem Präfix und Suffix (envelope) hat bekannte Probleme.

Eine auf dem MD5 basierende Variante der Envelope-Methode, bei der zwischen dem ersten Schlüssel und der Nachricht noch ein Padding erfolgt, wurde im RFC 1828 (IP Authentication using Keyed MD5) für die IP-Sicherheits-Architektur vorgeschlagen. Dieser Keyed MD5 ist laut RFC 1826 (IP Authentication Header) für alle zu ihm konformen Implementierungen obligatorisch.

Bart Preneel und Paul C. van Oorschot haben sich in ihrem Artikel On the Security of Two MAC Algorithms ( ftp://ftp.esat.kuleuven.ac.be/pub/COSIC/preneel/twomacs.ps.gz) speziell mit der Sicherheit des Keyed MD5 auseinandergesetzt und dabei herausgefunden, daß unter ganz bestimmten Bedingungen nicht nur das Fälschen von Nachrichten, sondern sogar die Rückgewinung des geheimen Schlüssels gelingen kann.

Mittlerweile hat die IPSEC (IP Security Protocol Working Group) der IETF an Stelle des Keyed MD5 einen anderen obligatorischen Mechanismus definiert: HMAC. Dieser von Mihir Bellare, Ran Canetti und Hugo Krawczyk entwickelte Algorithmus gilt gegenwärtig als eines der sehr guten hashbasierten MAC-Verfahren.

Seine Beschreibung findet sich z.B. im RFC 2104 (HMAC: Keyed-Hashing for Message Authentication) sowie unter http://www-cse.ucsd.edu/users/mihir/papers/hmac.html. HMAC spielt nicht nur bei der IPSEC eine Rolle, sondern hat auch bereits Eingang in die derzeit aktuellen Internet-Drafts für das TLS Protocol Version 1.0 sowie das SSH Transport Layer Protocol Version 2.0 gefunden, die wir später noch detaillierter diskutieren werden.

HMAC nutzt das als Basis gewählte Hashverfahren im Sinne einer Black Box und kann so existierende Implementierungen unverändert verwenden. Auch der Austausch von Hashfunktionen, der aus Gründen der Performance bzw. der Sicherheit notwendig werden kann, stellt kein Problem dar. Der größte Vorteil gegenüber vielen anderen Vorschlägen ist aber, daß die Sicherheit von HMAC bewiesen werden kann, sofern die zugrunde gelegten Hashfunktionen eine gewisse kryptographische Stärke besitzen. Man kann es auch so sagen: Wenn HMAC sein Ziel verfehlt, ein sicherer MAC-Algorithmus zu sein, dann folgen daraus derart ernste Schwächen der darunterliegenden Hashfunktion, daß diese nicht nur bei HMAC, sondern auch für eine Vielzahl anderer Anwendungen nicht mehr taugt.

Die Forderungen an die Hashfunktion sollten nicht zu stark sein, da verschiedene Eigenschaften der aktuellen Kandidaten (z.B. MD5, SHA-1) noch nicht hinreichend untersucht wurden. Allgemein gilt: Je schwächer die unterstellten Sicherheitseigenschaften sind, desto stärker wird die resultierende MAC-Konstruktion, da die schwachen Forderungen mit sehr hoher Wahrscheinlichkeit erfüllt werden.

Für HMAC gehen die Autoren im wesentlichen von einer im Vergleich zu anderen Anwendungen abgeschwächten Form der Kollisionsresistenz sowie einer begrenzten "Nichtvorhersagbarkeit" der Ergebnisse der internen Kompressionsfunktion aus. Konkret wird angenommen, daß die verwendete Hashfunktion bei zufällig gewähltem und geheimem IV kollisionsresistent ist und sich das gesamte Ergebnis der Kompressionsfunktion schwer vorhersagen läßt, wenn das erste Argument zufällig und geheim ist. Dadurch kann es möglich sein, daß eine Funktion H als Hashfunktion gebrochen wird, ein auf H basierender HMAC jedoch weiter sicher bleibt.

Im RFC 2104 ist zu lesen, daß die Attacken von Dobbertin sowie andere bekannte Schwächen des MD5 seinen Einsatz bei HMAC nicht kompromittieren. Allerdings erscheint den Autoren SHA-1 als die kryptographisch stärkere Funktion. Der Einsatz des MD5 bietet sich speziell dort an, wo dessen im Vergleich zu SHA-1 höhere Performance eine Rolle spielt. Generell sind alle Nutzer und Implementatoren angehalten, sich stets über aktuelle kryptoanalytische Entwicklungen zu informieren, die die genutzten Hashfunktion betreffen, und bei Bedarf deren Austausch vorzunehmen.

Nun zum Algorithmus selbst: Neben einer kryptographischen Hashfunktion H (z.B. MD5 und SHA-1) wird ein geheimer, zufällig gewählter Schlüssel K benötigt. HMAC akzeptiert beliebig lange Argumente. H bestimmt sowohl die Länge des Hashwertes (128 Bit bei MD5, 160 Bit bei SHA-1) als auch die maximale Byteanzahl von K (64 bei MD5 und SHA-1, da sie beide die Ausgangsdaten schrittweise in Blöcken zu je 64 Byte verarbeiten). Als Mindestlänge des Schlüssels wird die Länge des erzeugten Hashwertes empfohlen (16 Byte bei MD5, 20 Byte bei SHA-1). Sofern ein Key länger als das vorgegebene Maximum ist, wird er durch Anwendung von H gekürzt (d.h., dann nutzt man den Hashwert von K als Key).

Des weiteren sind zwei konstante und unterschiedliche Zeichenketten definiert (0x symbolisiert eine Hexadezimalzahl):

ipad = das Byte 0x36 B-Mal wiederholt
opad = das Byte 0x5C B-Mal wiederholt
Der jeweils erste Buchstabe der Bezeichnungen ipad und opad steht für inner bzw. outer. B ist wieder die bei der Verarbeitung der Ausgangsdaten verwendete Blockgröße (also 64 für SHA-1 und MD5).

Die Berechnung des HMAC über einem Text erfolgt gemäß folgender Vorschrift:

H(K  XOR  opad, H(K  XOR  ipad, Text))
In Worten:
  1. K wird durch Anhängen von Null-Bits auf eine B Byte lange Zeichenkette aufgefüllt.
    Bsp.: Falls K 20 Byte lang ist und B 64 beträgt, werden 44 Null-Bytes (alle Bits gleich Null) angehängt.
  2. XOR-Verknüpfung der in Schritt 1 berechneten Bytefolge mit ipad.
  3. Anhängen des Textes (d.h. der zu authentifizierenden Daten) an das Ergebnis von Schritt 2.
  4. Anwendung von H auf das Resultat von Schritt 3.
  5. XOR-Verknüpfung der in Schritt 1 berechneten Bytefolge mit opad.
  6. Verkettung der Ergebnisse von Schritt 5 und 4.
  7. Generieren des MAC durch Anwendung von H auf das Resultat von Schritt 6.


© Holger Trapp, 13.10.1998