8.2.4. Einweg-Hashfunktionen

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:

• Der Hashwert H(x) einer Bitfolge x läßt sich relativ einfach, d.h. mit wenig Rechenaufwand bestimmen.

  Das Argument der Hashfunktion, also die Bitfolge x, wird auch als preimage bezeichnet.

• Es ist rechnerisch nicht möglich, zu einem vorgegebenen Hashwert z eine Nachricht x zu generieren, so daß H(x) = z gilt. Anders ausgedrückt, es darf keinen (wesentlich) effektiveren Weg zur Ermittlung von x geben, als alle in Frage kommenden Bitfolgen durchzuprobieren, bis man eine findet, die den Hashwert z besitzt.

  Diese Eigenschaft wird auch als preimage resistance bezeichnet.

• Es ist rechnerisch ebenfalls nicht möglich, zu einer vorgegebenen Nachricht eine zweite zu finden, die denselben Hashwert wie die erste hat.

  Hierfür findet man in der Literatur den Begriff second preimage resistance bzw. 2nd-preimage resistance.

Anmerkung zum Aufwand zweier Attacken auf Einweg-Hashfunktionen:

• Attacke 1: Ermittlung einer zweiten Nachricht, die denselben Hashwert wie eine vorgegebene Nachricht besitzt
• Attacke 2: Erzeugung einer Kollision

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

• Attacke 1 ungefähr 2^n-1 zufällige Nachrichten, dagegen bei

• Attacke 2 nur ungefähr 1,2 × 2^n/2 zufällige Nachrichten testen muß,

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ß

• Attacke 1 einen Aufwand der Ordnung 2ⁿ und

• Attacke 2 einen Aufwand der Ordnung 2^n/2

verursacht. Es sei hier explizit darauf hingewiesen, daß 2ⁿ das Quadrat von 2^n/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. 2⁸⁰ 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

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:

• MD2:
  • im RFC 1319 spezifiziert
  • verarbeitet Nachrichten, die aus beliebig vielen 8-Bit-Bytes bestehen
  • erzeugt 128 Bit lange Hashwerte
  • ist langsamer als die meisten anderen vorgeschlagenen Einweg-Hashfunktionen
  • wird zusammen mit MD5 in den PEM-Protokollen (Privacy Enhanced Mail) eingesetzt

  • Sicherheit:
    Für eine modifizierte Version des Algorithmus wurden Kollisionen gefunden, daher wird der Einsatz des MD2 in neuen Applikationen, die eine Kollisionsresistenz fordern, nicht mehr empfohlen. Wörtlich sagt Bulletin 4:

    Existing signatures formed using MD2 are not at risk, but MD2 can no longer be recommended for future applications that will depend on the hash function being collision-resistant. MD2 remains suitable for use as a one-way hash function.

• MD4:
  • im RFC 1320 spezifiziert
  • verarbeitet Nachrichten, die aus beliebig vielen Bits (nicht Bytes wie bei MD2) bestehen
  • erzeugt 128 Bit lange Hashwerte
  • erste kryptographische Hashfunktion, die die Struktur von 32-Bit-Prozessoren optimal nutzt
  • benötigt keine großen Substitutionstabellen und ist kompakt kodierbar

  • Sicherheit:
    Teile des Algorithmus konnten erfolgreich kryptoanalytisch angegriffen werden. So ist es z.B. dem deutschen Kryptologen Hans Dobbertin mit Hilfe einer von ihm entwickelten neuartigen kryptoanalytischen Methode gelungen, Kollisionen zu erzeugen, wobei man für die Attacke auf einem PC nur wenige Sekunden benötigt. Damit steht fest, daß MD4 keine kollisionsresistente Einweg-Hashfunktion ist.

    Der MD4 sollte generell nicht mehr genutzt werden. Im Bulletin 4 lesen wir:

    MD4 should not be used. (This merely restates a recommendation which has been present in the literature for some time, in fact, its use has not been recommended since the introduction of MD5).

• MD5:
  • im RFC 1321 spezifiziert
  • verarbeitet Nachrichten, die aus beliebig vielen Bits bestehen
  • erzeugt 128 Bit lange Hashwerte
  • wurde wie der MD4 mit dem Ziel entworfen, auf 32-Bit-Maschinen schnell zu arbeiten
  • benötigt keine großen Substitutionstabellen und ist kompakt kodierbar
  • Erweiterung des MD4: im Vergleich zum Vorgänger etwas komplexer, konservativer im Design und auch langsamer (etwas Geschwindigkeit wurde zugunsten von mehr Sicherheit geopfert). So gibt es im MD5 vier Runden, beim MD4 nur drei.

  • Sicherheit:
    Durch kryptoanalytische Analysen wurden verschiedene Schwächen gefunden. Eine der vermutlich schwerwiegendsten besteht darin, daß es Hans Dobbertin gelungen ist, Kollisionen in der im Inneren des MD5 verwendeten Kompressionsfunktion zu finden. Eine Implementierung der von ihm entwickelten Attacke benötigte nach seinen Angaben aus dem Jahre 1996 ca. 10 Stunden auf einem Pentium-PC. Dies beweist, daß ein Entwurfsprinzip des MD5, nämlich das Design einer kollisionsresistenten Kompressionsfunktion, verletzt wurde.

    Einige weitere Informationen zu diesem Thema finden sich in Dobbertins Artikel The Status of MD5 After a Recent Attack, der im Volume 2, No. 2 (Sommer 1996) der Zeitschrift CryptoBytes erschienen ist. Diese Zeitschrift sowie weitere Publikationen der Firma RSA Data Securities, Inc. (RSADSI) können Sie über folgenden URL beziehen: http://www.rsa.com/PUBS/. Beachten Sie bitte, daß viele Dokumente im PDF-Format verteilt werden. Sie benötigen daher ein geeignetes Programm zum Lesen von PDF-Dateien, z.B. den von der Firma Adobe kostenfrei erhältlichen Acrobat Reader.

    In seinem Artikel sagt Dobbertin, daß die von ihm präsentierten Attacken für praktische Anwendungen des MD5 zwar noch keine Gefährdung darstellen, einer solchen aber schon recht nahekommen. Deshalb empfiehlt er, den MD5 künftig nicht mehr in Applikationen einzusetzen, die kollisionsresistente Einweg-Hashfunktionen benötigen, wozu typischerweise Verfahren zur Erstellung digitaler Signaturen zählen. Als Alternativen nennt er SHA-1 und RIPEMD-160.

    Solange nur eine Einweg-Funktion, nicht aber die Kollisionsresistenz benötigt wird (z.B. beim weiter unten vorgestellten Algorithmus HMAC), kann man den MD5 nach Dobbertins Auffassung weiter benutzen.

    Bulletin 4 äußert sich wie folgt:

    Existing signatures formed using MD5 are not at risk and while MD5 is still suitable for a variety of applications (namely those which rely on the one-way property of MD5 and on the random appearance of the output) as a precaution it should not be used for future applications that require the hash function to be collision-resistant.

    Als Alternativen zum MD5 werden im Bulletin 4 der SHA-1 sowie der RIPEMD-160 empfohlen.

• RIPEMD-160:
  • relativ neue Entwicklung (1996)
  • Autoren: Hans Dobbertin (Bonn) sowie Bart Preneel und Antoon Bosselaers (beide von der Katholischen Universität Leuven, Belgien)
  • verbesserte (strengthened) Version von RIPEM, einem für das EG-Projekt RIPE (RACE Integrity Primitives Evaluation) entwickelter Hashalgorithmus, der auf dem MD4 basiert und so entwurfen wurde, daß er den zur Zeit seiner Entwicklung bekannten kryptoanalytischen Attacken widersteht
  • für Software-Implementierungen und für 32-Bit-Architekturen optimiert
  • etwas geringere Performance als SHA-1
  • erzeugt 160 Bit lange Hashwerte (dieselbe Länge wie bei SHA-1)
  • Eine Beschreibung ist in folgenden Dokumenten zu finden:
    • The RIPEMD-160 page [http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html]

    • Artikel The Cryptographic Hash Function RIPEMD-160, der im Volume 3, No. 2 (Herbst 1997) der Zeitschrift CryptoBytes erschienen ist. Diese Zeitschrift kann über die WWW-Seite http://www.rsa.com/PUBS/ bezogen werden.

  • Sicherheit:
    • RIPEMD-160 gehört zur Public Domain
    • das komplette Design wird offen diskutiert
    • Kryptoanalytiker sind aufgefordert, die Sicherheit des Verfahrens zu untersuchen
    • bisher keine erfolgreichen kryptoanalytischen Attacken bekannt
    • Entwicklungsziel bei RIPEMD-160: high security level for the next 10 years or more, long-term security
    • RIPEMD-128: schnellere, aber nicht so sichere Variante des RIPEMD-160 mit 128-Bit-Hashwerten

• SHA-1:
  • in den USA von NIST und NSA entwickelt
  • im Secure Hash Standard (kurz SHS, NIST FIPS PUB 180-1 [http://csrc.nist.gov/fips/fip180-1.ps]) als Secure Hash Algorithm spezifiziert
  • stellt eine leicht modifizierte, dadurch offenbar verbesserte Version des zuvor gültigen Standards SHA dar
  • verarbeitet Nachrichten, die weniger als 2⁶⁴ Bit lang sind
  • erzeugt wie RIPEMD-160 Hashwerte der Länge 160 Bit (im Gegensatz zu 128 Bit bei MD2/MD4/MD5), woraus eine größere Resistenz gegen brute-force und birthday attacks resultiert
  • etwas bessere Performance als RIPEMD-160
  • nutzt nach Aussagen seiner Entwickler Prinzipien, die denen ähneln, welche Rivest für seinen MD4 verwendet hat, und ist außerdem hinsichtlich der Struktur ziemlich stark an MD4 angelehnt
  • die genauen Design-Kriterien sowie die gefundene Schwäche, die zum Übergang von SHA auf SHA-1 geführt hat, werden geheimgehalten

  • Sicherheit:
    • erfolgreiche kryptoanalytische Attacken sind bisher nicht (öffentlich) bekannt
    • Verfahren gilt als sehr sicher und wird häufig für neue Applikationen empfohlen und auch genutzt

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:

• We understand very little about the security of hash functions.
• Designers have been too optimistic.

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

• Ein wichtiger Anwendungsfall ist die auf sichere Weise durchgeführte Verdichtung (Kompression) von speziell langen Nachrichten oder Dateien, die digital signiert werden sollen. Dies ist das ursprüngliche Ziel, das mit der Entwicklung von Einweg-Hashfunktionen verfolgt wurde. Im RFC 1321, der den Algorithmus MD5 beschreibt, lesen wir dazu folgendes:

  The MD5 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA.

  Fast wortgleiche Erläuterungen finden sich in den Beschreibungen der Algorithmen MD2 und MD4. Auch SHS enthält eine vom Sinn her ähnliche Aussage.

  Die für digitale Signaturen genutzten Public-Key-Verfahren sind sehr rechen- und damit zeitaufwendig, so daß in der Regel aus Gründen der Effizienz statt der langen Nachricht deren kurzer Fingerabdruck mit dem privaten Key unterschrieben wird.

  Des weiteren hat die Verwendung geeigneter Einweg-Hashfunktionen noch den Vorteil, daß dadurch ein existentielles Fälschen verhindert wird.

• Generell empfiehlt es sich nicht, Paßwörter im Klartext auf Datenträgern zu speichern, da immer die Gefahr besteht, daß sie in die Hände Unbefugter gelangen. Deshalb erscheint es zunächst naheliegend, die zur Authentifizierung eines Nutzers gegenüber einem Computersystem benötigten Paßwörter verschlüsselt in der Paßwort-Datenbasis zu hinterlegen. Verwendet man dazu ein symmetrisches oder asymmetrisches Kryptosystem, so wird bei jedem Authentifizierungsvorgang der geheime bzw. private Schlüssel benötigt.

  In der Regel läßt es sich nicht vermeiden, den verwendeten Key permanent im System zu speichern, da sonst nach jedem Neustart eines Rechners ein Administrator persönlich an das Gerät gehen und den Schlüssel eingeben müßte. Gelingt es nun einem Angreifer, den Schlüssel zu stehlen, hat das zur Folge, daß mit einem Schlag alle in der Datenbasis enthaltenen Paßwörter kompromittiert sind, da sie dechiffriert werden können.

  Mit Hilfe von Einweg-Hashfunktionen ist dieses Problem sehr elegant lösbar, denn sie gestatten eine Chiffrierung, ohne dazu einen (geheimen) Schlüssel zu benötigen. Da sie nur mit extrem hohem Aufwand invertierbar sind, läßt sich der Geheimtext in der Regel nicht wieder dechiffrieren. Die Paßwort-Datenbasis ist also de facto unentschlüsselbar, und es gibt kein Geheimnis, so daß es auch nicht geschützt werden muß.

  Diese Technik wurde in den 60er Jahren an der Universität Cambridge von Roger Needham (dem Mitautor des Needham-Schroeder-Protokolls, das in einer modifizierten Form bei Kerberos zum Einsatz kommt) vorgeschlagen und realisiert. Eine zuverlässige Authentifizierung ist dabei sehr leicht möglich. Man berechnet lediglich den Hashwert eines eingegebenen Paßworts und vergleicht diesen mit dem in der Datenbasis hinterlegten Wert. Stimmen beide überein, wird dem Nutzer der Zugang zu einem System gewährt, anderenfalls verweigert.

  Man muß natürlich beachten, daß dieses Verfahren nicht gegen schlecht gewählte Paßwörter schützt. Ein Angreifer kann immer versuchen, ein gültiges Paßwort zu "erraten". Mit Hilfe eines Computers ist es ihm leicht möglich, eine Menge häufig genutzter Kandidaten (z.B. Namen, Telefonnummern, Geburtsdaten, Wörter eines Wörterbuches) durchzuprobieren, da er genau wie das System deren Hashwerte berechnen und mit den Einträgen der Datenbasis vergleichen kann. Die als Password-Cracker bezeichneten Programme tun vom Prinzip her genau das, wobei sie unterschiedlich ausgefeilte Strategien zur Bestimmung geeigneter Kandidaten verwenden. Um derartige Attacken zu verhindern, sind z.B. in neueren UNIX-Systemen die Hashwerte nur dem Super-User zugänglich (Datei /etc/shadow).

  Anmerkung: Das üblicherweise im UNIX genutzte Hashverfahren basiert auf einer DES-ähnlichen Blockchiffre, deren Aufgabe in der Verschlüsselung der Zahl 0 besteht, wobei der Key aus dem Paßwort des Nutzers abgeleitet wird. Bei neueren Implementierungen (u.a. bei einigen Linux-Systemen) kommt mitunter auch der MD5 zum Einsatz.

• Fingerabdrücke gestatten eine effiziente Überprüfung der Integrität von Dateien. Will man feststellen, ob eine Datei verändert wurde, so berechnet man deren Hashwert und vergleicht ihn mit dem (sicher aufbewahrten) Fingerabdruck der Originalversion. Stimmen beide überein, kann mit sehr hoher Wahrscheinlichkeit angenommen werden, daß keine Modifikation (z.B. durch einen Virus) stattgefunden hat. Man könnte natürlich auch die Originale sicher aufbewahren und diese zum Vergleich heranziehen, allerdings bewirken die Hashwerte eine enorme Speicherplatzersparnis, da sie wesentlich kleiner als die Daten und damit bequemer handhabbar sind. Eine praktische Anwendung dieses Konzepts finden wir z.B. beim Werkzeug Tripwire.

• Analog lassen sich Hashwerte vorteilhaft nutzen, wenn zwei Partner feststellen möchten, ob sie im Besitz derselben Daten sind. Dann berechnen beide die Fingerabdrücke der betreffenden Informationen und vergleichen diese. Somit kann man beispielsweise überflüssige Transfers großer Daten über ein Netz vermeiden, die notwendig wären, wenn die Dateien Byte für Byte verglichen werden müßten. Auch beim PGP findet diese Technik Verwendung. Statt der öffentlichen Schlüssel lesen sich die Partner am Telefon in der Regel den Key fingerprint vor.

• Wir hatten bereits gesehen, daß kryptographische Prüfsummen von Nachrichten mit Hilfe schlüsselabhängiger Einweg-Hashfunktionen berechnet werden. Statt der bisher als Basis genutzten Blockchiffren sind auch die im vorliegenden Abschnitt diskutierten Einweg-Hashfunktionen verwendbar, wenn dafür gesorgt wird, daß deren Werte in geeigneter Weise von einem Schlüssel abhängen. Mit HMAC wird weiter unten eine konkrete Realisierung vorgestellt.

• Vielfach nutzt man Einweg-Hashfunktionen, um aus Paßwörtern bzw. Pass Phrases die für eine Chiffre benötigten Schlüssel abzuleiten. So handelt es sich z.B. bei dem im PGP 2.x zum Schutz des privaten Schlüssels eingesetzten IDEA-Key um den MD5-Hashwert der Pass Phrase (Mantra) des Anwenders.

• Da gute Einweg-Hashfunktionen zufällig aussehende Hashwerte erzeugen, sind sie als Basis für Pseudozufallszahlen-Generatoren geeignet. In der NIST FIPS PUB 186 Digital Signature Standard (kurz DSS) [http://csrc.nist.gov/fips/fips186.ps] wird z.B. konkret die Verwendung von SHA-1 zur Erzeugung von Zufallszahlen beschrieben.

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:

• Beim Einmal-Paßwortsystem von Leslie Lamport überträgt man auf dem Netz ausschließlich Einmal-Paßwörter, also solche, die nur für genau eine Authentifizierung gegenüber einem Rechner gelten. Sie stellen jeweils das Ergebnis der n-fachen Anwendung einer Einweg-Hashfunktion auf das nur dem Nutzer bekannte und nirgendwo auf einem Computer hinterlegte geheime Paßwort dar. Kann jemand den richtigen Hashwert vorweisen, so "glaubt" ihm der Rechner, daß er das richtige Paßwort kennt. Die Zahl n wird kontinuierlich dekrementiert, so daß ein Angreifer aus einem mitgehörten Einmal-Paßwort nicht auf dasjenige schließen kann, das als nächstes aktuell wird, da er dazu die Einweg-Hashfunktion invertieren müßte.

• Das bei der Diskussion der symmetrischen Verschlüsselungsverfahren vorgestellte Challenge-Response-Protokoll zum Nachweis der beiderseitigen Kenntnis eines geheimen Schlüssels läßt sich mit einer Einweg-Hashfunktionen MD prinzipiell analog realisieren:
  

  Achtung:: Die konkret gezeigte Variante ermöglicht wiederum die schon erwähnte Reflection Attack. Dazu kommt, daß die Art der Berechnung des Hashwertes die Sicherheit des Protokolls entscheidend beeinflußt. Wie neuere kryptoanalytische Untersuchungen im Zusammenhang mit der auf Hashfunktionen basierenden MAC-Berechnung belegen, kann unter bestimmten Umständen eine Schlüsselrückgewinnung gelingen. Das in der Abbildung dargestellte einfache Hintereinanderreihen von Key und Zufallszahl ist keinesfalls zu empfehlen (s. dazu die folgende Diskussion des HMAC).

HMAC

• Software-Realisierungen von Einweg-Hashfunktionen sind wesentlich schneller als entsprechende Implementierungen von Verschlüsselungsalgorithmen,
• letztere sind z.T. patentiert (z.B. IDEA, RSA) und
• unterliegen im Gegensatz zu Hashfunktionen oft staatlichen Restriktionen (z.B. einem Exportverbot).

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

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

H(K  XOR  opad, H(K  XOR  ipad, Text))

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.