Zum Inhalt springen

Kryptographische Hashfunktion

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 19. September 2007 um 17:36 Uhr durch Aktionsbot (Diskussion | Beiträge) (Link auf BKL Serpent aufgelöst). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Einleitung

Eine Hash-Funktion ist eine Funktion, die eine Zeichenfolge beliebiger Länge auf eine Zeichenfolge mit fester Länge abbildet. Die Funktion ist nicht injektiv.

Ursprünglich stammen Hash-Funktionen aus der Datenverwaltung.

Kryptologische Hash-Funktionen haben weitere Eigenschaften. Eine kryptologische Hash-Funktion sollte zumindest eine Einwegfunktion sein.

Hash-Funktionen dienen der Integritätsprüfung von Dateien oder Nachrichten. Darüber hinaus werden sie u.a. eingesetzt zum Verschlüsseln von Passwortdateien, bei digitalen Unterschriften, als Zufallszahlengeneratoren oder zur Konstruktion von Blockchiffren.

Hash-Funktionen werden klassifiziert in schlüssellose und schlüsselabhängige Hash-Funktionen. Die letzteren werden auch Message Authentication Codes (MACs) genannt. Schlüssellose Hash-Funktionen (kurz Hash-Funktionen) werden ferner unterteilt in One-Way Hash Functions (OWHFs) und Collision Resistant Hash Functions (CRHFs).

Eine OHWF erfüllt folgende Bedingungen:

1. Einwegfunktion: zu einem gegebenen Ausgabewert h(x)=y ist es praktisch unmöglich einen Eingabewert x zu finden (preimage resistance).

2. schwache Kollisionsresistenz: es ist praktisch unmöglich für einen gegebenen Wert x ein davon verschiedenes x’ zu finden, der denselben Hash-Wert h(x)=h(x')=y ergibt (2nd-preimage resistance).

Für eine CRHF gilt zusätzlich:

3. starke Kollisionsresistenz: es ist praktisch unmöglich zwei verschiedene Eingabewerte x und x’ zu finden, die denselben Hash-Wert ergeben (collision resistance).

Außerdem kann man eine Beinahe-Kollisionsresistenz fordern (near-collision resistance). Hierbei sollte es schwierig sein, zu zwei verschiedenen Eingabewerten x und x’ Hash-Werte h(x) und h(x’) zu finden, die sich nur in wenigen Bits unterscheiden.

Konstruktion

Die meisten Hash-Funktionen sind iterierte Kompressionsfunktionen. Die eingegebene Nachricht M wird in Blöcke fester Länge geteilt und mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt. Die Kompressionsfunktion hat als Input einen Nachrichtenblock und den Output der vorherigen Nachrichtenblöcke. Der Hash-Wert der gesamten Nachricht ist der Hash-Wert des letzten Blocks:

H(0)=IV

H(i)=f(M(i),H(i-1), i=1,2,….,t

h(M)=H(t)

IV bezeichnet initial value, einen Startwert.

Iterierte Hash-Funktionen basieren entweder auf Blockchiffren oder auf algebraischen Strukturen oder sind speziell entwickelte Hash-Algorithmen.

Spezielle Hash-Algorithmen

Zu diesen gehören z.B. die MD4-Familie einschließlich SHA und RIPEMD.

Hash-Funktionen, die auf einer Block-Chiffrierung basieren

Dabei unterscheidet man Hash-Funktionen, deren Hash-Wert dieselbe Länge hat wie die Blocklänge und jene, deren Hash-Wert die doppelte Blocklänge hat.

  • I) Hash-Länge gleich Blocklänge

Drei verbreitete Konstruktionen sind die


Matyas-Meyer-Oseas-Variante

Davies-Meyer-Variante

Miyaguchi-Preneel-Variante


wobei E die Verschlüsselung mit einem Blockchiffresystem ist, M(i) die Nachrichtenblöcke und H(i) die Hash-Werte.

  • II) Hash-Länge mit doppelter Blocklänge

Dazu zählen MDC-2 und MDC-4. Sie bestehen im wesentlichen aus der zwei- bzw. vierfachen Anwendung der Matyas-Meyer-Oseas-Konstruktion.

C. Hash-Funktionen, die auf algebraischen Strukturen basieren

MASH (Modular Arithmetic Secure Hash) verwendet einen RSA-ähnlichen Modulus n=pq, mit p und q Primzahlen. Die Kompressionsfunktion ist im Kern:


A: Konstante, : excl. oder, : incl oder

Angriffe

Angriffe gegen Hash-Funktionen können allgemeiner Art sein, und nur von der Bit-Länge des Hash-Werts abhängen und den Hash-Algorithmus als Black-Box behandeln. Sie können sich andererseits gegen die Kompressionsfunktion richten. Bei Hash-Funktionen, die auf einem Block-Chiffre basieren, kann ein Angriff gegen die zugrundeliegende Block-Chiffrierung erfolgen. Überdies sind Angriffe auf die Implementierung des Hash-Algorithmus möglich.

Black-Box Angriffe

  • I) Raten (2nd Preimage)

Der Angreifer wählt zufällig eine Nachricht und vergleicht deren Hash-Wert mit dem einer gegebenen Nachricht. Die Erfolgsrate bei diesem Vorgehen liegt bei (2)^n für einen n-Bit langen Hash-Wert.

  • II) Geburtstagsangriff (Kollision)

Der Angreifer erzeugt v1 Variationen einer echten Nachricht und v2 Variationen einer gefälschten Nachricht. Er ermittelt die Hash-Werte h(v1) und h(v2) und sucht nach einer Kollision. Eine Kollision ist nach 2^(n/2) Versuchen zu erwarten.

Angriffe auf die Kompressionsfunktion

  • I) Meet-in-the-Middle

Der Angreifer erzeugt v1 Variationen der ersten Hälfte einer gefälschten Nachricht und v2 Variationen der zweiten Hälfte. Er berechnet die Hash-Werte vorwärts beim Startwert IV beginnend und rückwärts vom Hash-Resultat aus und versucht eine Kollision am Angriffspunkt zu finden. D.h. er muss die Kompressionsfunktion effizient invertieren können: gegeben H(i+1)
ein Paar (H(i), M(i+1)) finden, so dass gilt f(H(i), M(i+1))=H(i+1).

  • II) Correcting Block Attack

Der Angreifer ersetzt alle Blöcke einer Nachricht bis auf einen - etwa den ersten. Anschließend legt er diese Variable so fest, dass sie im Laufe der Verkettung den gewünschten Gesamt-Hash-Wert liefert.

  • III) Fixed Point Attack

Der Angreifer sucht nach einem H(i-1) und M(i), so dass f(M(i), H(i-1))=H(i-1). In diesem Fall kann er an diesem Punkt Nachrichtenblöcke einfügen, ohne den Hash-Wert zu ändern.

  • IV) Differentielle Kryptanalyse

Hierbei werden Eingabedifferenzen und die korrespondierenden Ausgabedifferenzen untersucht. Eine Differenz von Null entspricht dann einer Kollision.

Angriffe auf die Blockchiffrierung

Schwachstellen eines Blockchiffrierverfahrens, die solange das Verfahren zur Verschlüsselung verwendet wird, eigentlich irrelevant sind, können bedeutende Auswirkungen haben, wenn es zur Konstruktion eines Hash-Verfahrens herangezogen wird. Diese wären z.B. schwache Schlüssel oder eine Komplementäreigenschaft.

Übersicht über Hash-Funktionen

Snefru

wurde 1990 von Merkle entworfen. Der Kern der Hash-Funktion ist ähnlich dem Blockchiffriersystem Khafre (Merkle). Snefru gilt als unsicher.

N-Hash

wurde 1990 bei Nippon Telephone and Telegraph entwickelt. Der Algorithmus ähnelt dem Blockchiffriersystem FEAL (Nippon T&T). N-Hash gilt als unsicher.[1]

FFT-Hash

ist eine Hash-Funktion auf der Basis der Fast Fourier Transformation. Sie wurde von Schnorr 1991 erstmals vorgestellt, aber bald geknackt.[2] Später folgte eine zweite Version. [3] Sie gilt als unsicher.

MD4

wurde 1990 von Rivest entwickelt.[4] Sie erzeugt nach drei Runden einen 128 Bit langen Hashwert.
Zu Beginn wird die Länge der Nachricht auf ein ganzzahliges Vielfaches von 512 gebracht. Dazu wird sie mit einer „1“ und entsprechend vielen „0“ aufgefüllt, so dass beträgt. Ihr wird die Länge der ursprünglichen Nachricht in 64-Bit-Darstellung angehängt.
Als nächstes wird der Puffer initialisiert.
Die Hauptschleife besteht aus drei Runden mit je 16 Schritten. Jede Runde erhält als Eingabe einen 512-Bit langen Nachrichtenblock und den 128-Bit langen Pufferinhalt. Jede Runde benutzt 16mal eine nichtlineare Rundenfunktion. Der ausgegebene Hashwert ist die Konkatenierung der letzten 32-Bit words im Puffer.[5]

MD5

1992 veröffentlichte Rivest ein verbessertes Hash-Verfahren noch bevor eine ernsthafte Schwäche von MD4 aufgedeckt wurde.
Die wesentlichen Veränderungen sind: MD5 hat eine vierte Runde. Die vierte Runde hat eine neue Rundenfunktion; die der zweiten Runde wurde durch eine neue Funktion ersetzt. Die additiven Konstanten wurden neu definiert.
Der erste partielle Angriff auf MD5 von 1993 findet Pseudokollisionen, d.h. es können zu einem Nachrichtenblock zwei sich in nur wenigen Bits voneinander unterscheidende Verkettungsvariablen V1 und V2 gefunden werden, die denselben Output ergeben.[6] Der Angriff hat allerdings keine schwerwiegenden Konsequenzen. Ein neuer effizienter Angriff erfolgte 2005.[7] Hierbei suchten die Autoren nach einem Nachrichtenpaar mit je zwei Blöcken, die nach Verarbeitung des zweiten Blocks eine Kollision erzeugen.

SHA

NIST schlug 1993 den Secure Hash Algorithm (SHA) vor. Zwei Jahre später wurde es durch SHA-1 ersetzt. SHA-1 unterscheidet sich von seinem Vorgänger nur durch eine zusätzliche 1-Bit-Rotation.
Die Nachricht wird wie bei MD4 aufgefüllt. Der Puffer wird mit fünf Konstanten initialisiert. Die Hauptschleife besteht aus vier Runden mit je 20 Schritten.
1998 wurde eine differentielle Analyse gegen SHA-0 und SHA-1 durchgeführt.[8]
2004 ist ein verbesserter Angriff auf SHA-0 beschrieben.[9] Hier fanden die Autoren Beinahe-Kollisionen, sowie Kollisionen für eine auf 65 Runden reduzierte Version von SHA. Ein Jahr später berichten dieselben Autoren von einem Angriff auf die volle Rundenzahl von SHA-0 mit einer Komplexität von 2^51.[10] Im selben Jahr gelingt ein verbesserter Angriff gegen SHA-0 mit einer Komplexität von 2^39 Hash-Operationen[11] und gegen SHA-1 mit einer Komplexität von 2^69[12] NIST rät mittlerweile vom langfristigen Einsatz des SHA-1 ab.

RIPEMD

RIPE-MD wurde 1992 im Rahmen des Projects RACE Integrity Primitives Evaluation der Europäischen Union entwickelt. 1996 wurde die ursprüngliche Hashwert-Länge von 128 Bits auf 160 erweitert.[13] Außerdem wurden die RIPEMD-256 und RIPEMD-320 eingeführt.
Die Nachricht wird wie bei MD4 aufgefüllt. Der Puffer wird mit fünf Konstanten initialisiert. Die Hauptschleife besteht aus fünf Runden mit je 16 Schritten. Der Algorithmus läuft in zwei Ausführungen parallel. Nach jedem Block werden die beiden Ausgabewerte beider Linien zu den Verkettungsvariablen addiert.
Im ursprünglichen RIPEMD konnten mit einer Komplexität von 2^16 Kollisionen gefunden werden,[14]so dass es nicht verwendet werden sollte.

HAVAL

wurde 1992 vorgestellt und gehört ebenfalls zur MD4-Familie. Die Nachrichten werden in 1024-Bit langen Blöcken verarbeitet. Der Hashwert kann 128, 160, 192, 224 oder 256 Bit lang sein. Auch die Rundenzahl kann von drei bis fünf variieren. Jede Runde besteht aus 16 Schritten.[15]
2003 konnte für HAVAL mit drei Runden Kollisionen gefunden werden. Der Angriff gelingt gegen alle möglichen Ausgabelängen. Die Komplexität entspricht dabei 2^29 Rechenschritten der Kompressionsfunktion. HAVAL sollte deswegen nicht für Applikationen verwendet werden, die Kollisionsresistenz erfordern.[16]

TIGER

wurde 1996 von Anderson und Biham entwickelt. Nachrichtenpadding ist wie bei MD4, d.h. der Nachricht wird eine „1“ plus eine Folge von „0“, sowie die Nachrichtenlänge als ein 63-Bit Word angehängt. Das Resultat wird in 512-Bit lange Blöcke geteilt. Der Hashwert enthält 192 Bits. Aus Gründen der Kompatibilität sind TIGER/128 oder TIGER/160 definiert, die die ersten 128, bzw. 160 Bits von TIGER/192 verwenden.[17]

PANAMA

ist von Daemen und Clapp und stammt aus 1998.[18] Es verarbeitet Nachrichtenblöcke mit 256 Bit Länge und gibt einen Hashwert mit 256 Bit aus. Der Puffer ist ein lineares Schieberegister mit 32 Zuständen mit je acht Words.
Es sind zur Zeit keine gravierenden Schwächen von PANAMA bekannt, aber die Sicherheit ist fraglich.[19]

Whirlpool

wurde von Rijmen und Barreto entworfen. Es beruht auf dem Miyaguchi-Preneel-Schema.
Die Nachricht wird wie bei MD4 aufgefüllt. Die aufgefüllte Nachricht wird in 512-Bit lange Blöcke geteilt. Der Hashwert ist 512 Bit lang. Whirlpool verwendet als Funktion eine AES-Variante in 10 Runden[20]

SMASH

wurde 2005 von Knudsen entwickelt. Nach dem Nachrichtenpadding zu Beginn wird die Nachricht wahlweise in 256-Bit oder 512-Bit langen Blöcken verarbeitet und liefert einen 256-Bit, bzw. 512-Bit langen Hashwert. Die Hauptrunde besteht aus mehreren Runden, die H-Runden und L-Runden genannt werden. Drei verschiedene H-Runden sind definiert. Jede H-Runde enthält eine eigene S-Box (Substitutionstabelle), die an die des Blockchiffrierverfahrens Serpent angelehnt sind. In der L-Runde werden Links- oder Rechtsverschiebungen durchgeführt.[21]
SMASH wurde bald erfolgreich angegriffen und gilt als unsicher.[22]

FORK-256

wurde beim Cryptographic Hash Workshop von Hong et al. vorgestellt. Es verarbeitet 512-Bit lange Nachrichtenblöcke unterteilt in 16 Words und liefert einen 256-Bit langen Hashwert. Die Hauptschleife besteht aus vier Verzweigungen und acht Schritten je Zweig[23]

Quellen

  • A. J. Menezes, P. C. van Oorschot, S. A. Vanstone: Handbook of Applied Cryptography. CRC Press, 1996, S. 321-384.
  • B. Preneel: Cryptographic Primitives for Information Authentication - State of the Art. State of the Art in Applied Cryptography, LNCS 1528, Springer-Verlag, 1998, S. 49-104.
  • D. R. Stinson. Cryptography - Theory and Practice. Chapman&Hall/CRC, 2002, S. 117-154.

Einzelnachweise

  1. ↑ B. Schneier: Angewandte Kryptographie. Addison-Wesley, 1996, S. 491-524
  2. ↑ S. Vaudenay: FFT-Hash is not yet Collision-free. Advances in Cryptology-CRYPTO 92, LNCS 740, Springer-Verlag, 1993, S. 587-593.
  3. ↑ C. P. Schnorr, S. Vaudenay: Parallel FFT-Hashing, Fast Software Encryption, LNCS 809, Springer-Verlag, 1994, S. 149-156.
  4. ↑ R. L .Rivest: The MD4 Message Digest Algorithm, Advances in Cryptology-CRYPTO 90, LNCS 537, Springer_Verlag, 1991, S. 303-311
  5. ↑ W. Stallings: Cryptography and Network Security. Prentice Hall, 1999, S. 271-297.
  6. ↑ B. denBoer, A. Bossalaers: Collisions for the Compression Function of MD5, Advances in Cryptology-EUROCRYPT 93, LNCS 765, Springer-Verlag, 1994, S. 293-304.
  7. ↑ X. Wang, H. Yu: How to Break MD5 and Other Hash Functions, Advances in Cryptology-EUROCRYPT 2005, LNCS 3496, Springer-Verlag, 2005, S. 19-35
  8. ↑ F. Chabaud, A. Joux: Differential Collisions in SHA-0, Advances in Cryptology-CRYPTO 98, LNCS 1462, Springer-Verlag, 1999, S. 56-71
  9. ↑ E. Biham, R. Chen: Near-Collisions of SHA-0, Advances in Cryptology-CRYPTO 2004, LNCS 3152, Springer-Verlag, 2005, S. 290-305
  10. ↑ E. Biham, R. Chen et al.: Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology-EUROCRYPTO 2005, LNCS 3494, Springer-Verlag, 2005, S. 526-541
  11. ↑ X. Wang, H. Yu, Y. L. Yin: Efficient Collision Search Attacks on SHA-0, Advances in Cryptology-CRYPTO 2005, LNCS 3621, Springer-Verlag, 2006, S. 1-16
  12. ↑ X. Wang, Y. L. Yin, H. Yu: Finding Collisions in the Full SHA-1, Advances in Cryptology-CRYPTO 2005, LNCS 3621, Springer-Verlag, 2006, S. 17-36
  13. ↑ H. Dobbertin, A. Basselaers, B. Preneel: RIPEMD-160:A Strengthened Version of RIPEMD, Fast Software Encryption, LNCS 1039, Springer-Verlag, 1996, S. 71-79.
  14. ↑ X. Wang et al.: Cryptanalysis of the Hash Functions MD4 and RIPEMD, Advances in Cryptology-EUROCRYPT 2005, LNCS 3494, Springer-Verlag, 2005, S. 1-18
  15. ↑ Y. Zheng, J. Pieprzyk, J. Seberry: HAVAL-A one-way hashing algorithm with variable length of output, AUSCRYPT 92, LNCS 718, Springer-Verlag, 1993, S. 83-104
  16. ↑ B. van Rompay, A. Biryukov, B. Preneel, J. Vanderwalle: Cryptanalysis of 3-Pass HAVAL, Advaces in Cryptology-ASIACRYPT 2003, LNCS 2894, Springer-Verlag, 2003, S. 228-245
  17. ↑ http://www.cs.technion.ac.il/~biham/Reports/Tiger/
  18. ↑ J. Daemen, C. Clapp: Fast Hashing and Stream Encryption with PANAMA, Fast Software Encryption, LNCS 1372, Springer-Verlag, 1998, S. 60-74.
  19. ↑ V. Rijmen et al.: Producing Collisions for PANAMA, Fast Software Encryption, LNCS 2355, Springer-Verlag, 2001, S. 303-311
  20. ↑ http://paginas.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
  21. ↑ L. R. Knudsen: SMASH-A Cryptographic Hash Function, Fast Software Encryption, LNCS 3557, Springer-Verlag, 2005, S. 228-242
  22. ↑ N. Pramstaller, C. Rechberger, V. Rijmen: Smashing SMASH, Cryptology ePrint Archive Report 2005/081
  23. ↑ http://www.csrc.nist.gov/pki/HashWorkshop//index.html
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Kryptographische_Hashfunktion&oldid=36892308“