Kryptographische Hashfunktion

Eine kryptographische Hashfunktion oder kryptologische Hashfunktion ist eine Hashfunktion (Streuwertfunktion), die bestimmte Eigenschaften erfüllt, mit denen sie für kryptographische Anwendungszwecke geeignet ist. Eine Hashfunktion erzeugt effizient aus einem Eingabewert, etwa einer Nachricht oder einer Datei, einen Ausgabewert fester Länge: den Hashwert. Für den kryptographischen Einsatz werden weitere Eigenschaften gefordert: eine kryptographische Hashfunktion stellt eine Einwegfunktion dar, bietet Kollisionsresistenz und erzeugt einen pseudozufälligen Hashwert.

Kryptographische Hashfunktionen werden zur Integritätsprüfung von Dateien oder Nachrichten eingesetzt. Dafür wird die Funktion auf die zu prüfende Datei angewendet und mit einem bekannten Hashwert verglichen. Weicht der neue Hashwert davon ab, wurde die Datei verändert. Um zu verhindern, dass ein Angreifer sowohl Datei als auch Hashwert verändert, kann ein schlüsselbasiertes kryptographisches Verfahren eingesetzt werden, beispielsweise eine digitale Signatur oder ein Message Authentication Code. Weiter dienen kryptographische Hashfunktionen zur sicheren Speicherung von Passwörtern. Wenn ein System ein eingegebenes Passwort prüft, vergleicht es dessen Hashwert mit einem in einer Datenbank gespeicherten Hashwert. Stimmen beide Werte überein, ist das Passwort richtig. So kann vermieden werden, das Passwort im Klartext abzuspeichern. Ein Angreifer, der Lesezugriff auf die Datenbank hat, erlangt somit nicht das Passwort. Außerdem können kryptographische Hashfunktionen als Pseudo-Zufallszahlengeneratoren und zur Konstruktion von Blockchiffren eingesetzt werden.

Es gibt viele kryptographische Hashfunktionen. Einige davon, wie zum Beispiel der MD5 oder SHA-1, gelten nicht mehr als sicher, weil sie keine starke Kollisionsresistenz (siehe Eigenschaft 6) gewährleisten. Zu den in der Praxis oft verwendeten Funktionen, die heute noch als sicher gelten, gehören die Algorithmenfamilien SHA-2 und SHA-3.

Eigenschaften

Eine kryptographische Hashfunktion weist folgende Eigenschaften auf:

1. Beliebige Eingabelänge: Die Hashfunktion verarbeitet beliebig lange Daten, also eine beliebige Folge von Bits oder Bytes.
2. Feste Ausgabelänge: Die Hashfunktion erzeugt einen Hashwert fester Länge (beispielsweise 256 Bits).
3. Effizienz: Die Berechnung des Hashwerts ist effizient für beliebige Eingaben .
4. Einwegfunktion (auch Urbild-Resistenz, englisch preimage resistance): Es ist praktisch unmöglich, zu einem gegebenen Ausgabewert einen Eingabewert zu finden, den die Hashfunktion auf abbildet: .
5. Schwache Kollisionsresistenz (englisch weak collision resistance, oder auch Zweites-Urbild-Resistenz, englisch second preimage resistance): Es ist praktisch unmöglich, für einen gegebenen Eingabewert einen davon verschiedenen Eingabewert zu finden, der denselben Hashwert ergibt: .
6. Starke Kollisionsresistenz (englisch strong collision resistance): Es ist praktisch unmöglich, ein beliebiges Paar von zwei verschiedenen Eingabewerte und zu finden, die denselben Hashwert ergeben. Der Unterschied zur schwachen Kollisionsresistenz besteht darin, dass hier beide Eingabewerte und frei gewählt werden dürfen.
7. Pseudozufälligkeit: Die Ausgabe der Hashfunktion ist zwar deterministisch, aber scheinbar zufällig. Statistische Tests können die Ausgabe der Hashfunktion nicht von einem nicht-deterministischen, statistisch gleichverteilten Zufallszahlengeneratoren unterscheiden.

Die ersten drei Eigenschaften sind erforderlich für die praktische Verwendbarkeit einer Hashfunktion. Mathematisch stellt eine Hashfunktion eine Abbildung von einer großen Definitionsmenge auf eine kleinere Zielmenge dar, wodurch die Abbildung nicht injektiv ist. Daraus ergibt sich notwendigerweise die Existenz von Kollisionen, also Paaren von Eingabewerten, die denselben Hashwert ergeben. Die Kollisionsresistenz einer kryptographischen Hashfunktion besteht darin, dass es nur unter einem unrealistisch hohen Rechenaufwand möglich ist, eine solche Kollision zu berechnen. Somit ist es zwar theoretisch möglich, aber praktisch unrealistisch.

Die Sicherheit einer kryptographischen Hashfunktion hängt von den letzten vier Eigenschaften ab. Die Eigenschaft der Pseudozufälligkeit wird in der Literatur nicht immer explizit genannt, ist aber notwendige Voraussetzung für die Einwegeigenschaft und Kollisionsresistenz sowie für Anwendungszwecke wie beispielsweise Schlüsselableitung. Eine weitere mögliche Eigenschaft ist die Resistenz gegen Beinahe-Kollisionen (englisch near-collision resistance). Hierbei soll es praktisch unmöglich sein, zwei verschiedene Eingabewerte und zu finden, deren Hashwerte und sich nur in wenigen Bits unterscheiden.

Klassifikation und Begriffe

Hashfunktionen können in schlüssellose und schlüsselabhängige Hashfunktionen eingeteilt werden. Eine schlüssellose Hashfunktion erhält nur die Nachricht als Eingabewert, während eine schlüsselabhängige Hashfunktion neben der Nachricht einen geheimen Schlüssel als zweiten Eingabewert erhält. Nach ihrem Einsatzzweck wird eine schlüssellose Hashfunktion auch Modification Detection Code und eine schlüsselabhängige Hashfunktion Message Authentication Code (MAC) genannt. Zu den MACs zählen Konstrukte wie HMAC, CBC-MAC oder UMAC.

Die schlüssellosen Hashfunktionen werden ferner unterteilt in Einweg-Hashfunktionen (englisch One-Way Hash Function, kurz OWHF) und kollisionsresistente Hashfunktionen (englisch Collision Resistant Hash Function, kurz CRHF). Eine Einweg-Hashfunktionen erfüllt die Einwegeigenschaft und schwache Kollisionsresistenz, während eine kollisionsresistente Hashfunktion zusätzlich die starke Kollisionsresistenz erfüllt.

Der Hashwert wird auch Fingerprint genannt (englisch für ‚Fingerabdruck‘), da er eine Nachricht oder Datei nahezu eindeutig identifiziert. Ein anderer Begriff für den Hashwert ist message digest (englisch für ‚Nachrichten-Kurzfassung‘).

Konstruktion

Die meisten kryptographischen Hashfunktionen teilen die zu hashende Nachricht in Abschnitte gleicher Länge , die nacheinander in einen Datenblock der Länge eingearbeitet werden. Die Nachricht wird ggfs. auf ein Vielfaches von verlängert, wobei oft auch eine Kodierung der Länge der Ausgangsnachricht angefügt wird. Es gibt eine Verkettungsfunktion, die einen Nachrichtenabschnitt und den aktuellen Wert des Datenblocks als Eingabe erhält und den nächsten Wert des Datenblocks berechnet. Manche Hashalgorithmen sehen noch weitere Eingaben in die Verkettungsfunktion vor, zum Beispiel die Zahl der bis dahin verarbeiteten Nachrichtenblöcke oder -bits, siehe etwa das HAIFA-Verfahren. Die Größe des Datenblocks beträgt typischerweise 128 bis 512 Bit, teils auch mehr, bei SHA-3 z. B. 1600 Bit. Nach Verarbeitung des letzten Nachrichtenabschnitts wird der Hashwert dem Datenblock entnommen, teils wird zuvor noch eine Finalisierungsfunktion darauf angewandt.

Die Verkettungsfunktion ist nach den Prinzipien der Konfusion und der Diffusion entworfen, um zu erreichen, dass man nicht durch gezielte Konstruktion der eingegebenen Nachrichtenabschnitte zwei verschiedene Nachrichten erzeugen kann, die den gleichen Hashwert ergeben (Kollisionssicherheit).

Die Merkle-Damgård-Konstruktion erzeugt den Hashwert aus den Nachrichtenblöcken durch wiederholte Anwendung der Kompressionsfunktion

Die meisten Hashfunktionen, die vor 2010 entwickelt wurden, folgen der Merkle-Damgård-Konstruktion. Im Zuge des SHA-3-Wettbewerbs wurde diese Konstruktion durch verschiedene weitere Methoden ergänzt oder modifiziert.

Merkle-Damgård-Verfahren

In der Merkle-Damgård-Konstruktion wird eine Kompressionsfunktion als Verkettungsfunktion genutzt, die kollisionssicher ist, d. h. es ist schwer, verschiedene Eingaben zu finden, die die gleiche Ausgabe liefern. Daraus ergibt sich auch die Eigenschaft einer Einwegfunktion, d. h. man kann nur schwer zu einer gegebenen Ausgabe einen passenden Eingabewert finden. Die Kompressionsfunktion kann auf verschiedene Arten dargestellt werden, oft wird sie aus einer Blockchiffre konstruiert.

Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht zuerst erweitert und dabei auch eine Kodierung der Nachrichtenlänge angefügt. Dann wird sie in Blöcke bis der Länge geteilt. Die Kompressionsfunktion erhält einen Nachrichtenblock und den Verkettungsblock als Eingabe und gibt den nächsten Verkettungsblock aus. IV bezeichnet einen konstanten Startwert für den Verkettungsblock (initial value). Der Wert des letzten Blocks ist das Resultat, also der Hashwert der Nachricht :

Blockchiffre-basierte Kompressionsfunktionen

Die Kompressionsfunktion wird aus einer Blockverschlüsselung konstruiert. soll die Verschlüsselung von mit der Blockchiffre unter dem Schlüssel bezeichnen. steht für das bitweise XOR. Wie oben sind die Nachrichtenblöcke und die Werte des Verkettungsblocks. Einige verbreitete Kompressionsfunktionen sind:

Davies-Meyer (wird unter anderem in MD4, MD5 und SHA verwendet) verschlüsselt den Verkettungsblock mit dem Nachrichtenabschnitt als Schlüssel, der Schlüsseltext wird dann noch mit dem Verkettungsblock verknüpft, typisch per XOR:

Matyas-Meyer-Oseas verschlüsselt umgekehrt den Nachrichtenabschnitt mit dem Verkettungsblock. Dabei dient die Funktion zur Anpassung der Blockgrößen und ist häufig die Identität:

Miyaguchi-Preneel ist sehr ähnlich wie Matyas-Meyer-Oseas, nur wird auch der Verkettungsblock mit dem Schlüsseltext verknüpft:

Hirose nutzt einen Verkettungsblock von der doppelten Breite eines Klar- bzw. Schlüsseltextblocks der Blockchiffre. bezeichnen je eine Hälfte des Verkettungsblocks. Hier ist eine fixpunktfreie Funktion, die simpel gehalten werden kann, es genügt z. B. nur ein Bit zu invertieren. bezeichnet die Konkatenation, d. h. das Aneinanderfügen zweier Bitblöcke:

Die Hashfunktion MDC-2 beruht im Wesentlichen auf der zweifachen Anwendung der Matyas-Meyer-Oseas-Konstruktion. bzw. bezeichnen die linke bzw. rechte Hälfte eines Datenblocks (und damit ein Viertel eines Verkettungsblocks):

Kompressionsfunktionen, die auf algebraischen Strukturen basieren

Um die Sicherheit der Kompressionsfunktion auf ein schwieriges Problem reduzieren zu können, wird deren Operation in entsprechenden algebraischen Strukturen definiert. Der Preis für die beweisbare Sicherheit ist ein Verlust an Geschwindigkeit. MASH (Modular Arithmetic Secure Hash) verwendet einen RSA-ähnlichen Modulus , mit und Primzahlen. Die Kompressionsfunktion ist im Kern: , wobei A für eine Konstante und für bitweises inklusives Oder steht.

Sponge-Verfahren

Sponge-Konstruktionen haben grundsätzlich andere Eigenschaften als Merkle-Damgård-Konstruktionen. Der bekannteste Vertreter dieser Klasse ist SHA-3.

Angriffe

Angriffe gegen Hashfunktionen können allgemeiner Art sein, und nur von der Bit-Länge des Hashwerts abhängen und den Hash-Algorithmus als Black-Box behandeln. Sie können sich andererseits gegen die Kompressionsfunktion richten. Bei Hashfunktionen, 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

Black-Box-Angriffe sind Angriffe auf Hashfunktionen, bei denen über die eigentliche Funktionsweise der Hashfunktion nichts bekannt ist. Lediglich die Länge des Hashwerts  wird als bekannt vorausgesetzt und man nimmt an, dass die Hashwerte gleichverteilt sind.

1. Raten (englisch: 2nd preimage): Der Angreifer wählt zufällig eine Nachricht und vergleicht deren Hashwert mit dem einer gegebenen Nachricht. Die Erfolgsrate bei diesem Vorgehen liegt bei für einen  Bit langen Hashwert.
2. Kollisionsangriff: Der Angreifer erzeugt viele Variationen einer echten Nachricht und viele Variationen einer gefälschten Nachricht. Anschließend vergleicht er die beiden Mengen und sucht nach zwei Nachrichten, und , die den gleichen Hashwert haben. Eine Kollision ist nach Versuchen zu erwarten.

Angriffe auf die Kompressionsfunktion

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 von Hashfunktionen

Siehe auch

• Salt (Kryptologie)

Literatur

• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, 1996, S. 321–384.
• Bart 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.
• Douglas R. Stinson: Cryptography – Theory and Practice. Chapman&Hall / CRC, 2002, S. 117–154.

Weblinks

• Übersicht über Hash-Funktionen (englisch)
• NIST-Ausschreibung (englisch)
• Kandidaten der Hashfunktion-Ausschreibung (englisch)
• Keccak-Spezifikation

Einzelnachweise

1. Easttom 2021, S. 207 f.
2. Easttom 2021, S. 208 f.
3. William Easttom: Modern Cryptography: Applied Mathematics for Encryption and Information Security. Springer International Publishing, Cham 2021, ISBN 978-3-03063114-7, S. 206, doi:10.1007/978-3-030-63115-4. 
4. William Stallings: Cryptography and Network Security. Pearson Education Limited, Essex 2017, ISBN 978-1-292-15858-7, S. 349 f. 
5. Alfred Menezes, Paul van Oorschot, Scott Vanstone: Handbook of Applied Cryptography. CRC Press, 1996, Kap. 9, S. 324 (uwaterloo.ca [PDF]). 
6. Antoine Joux, Thomas Peyrin: Hash Functions and the (Amplified) Boomerang Attack. Advances in Cryptology-CRYPTO2007, LNCS4622. Springer-Verlag, 2007, S. 244–263
7. Florian Mendel, Christian Rechberger, Martin Schlaffer, Soren S. Thomsen: The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl. Fast Software Encryption, LNCS5665. Springer-Verlag, 2009, S. 260–276
8. John Kelsey, Tadayoshi Kohno: Herding Hash Functions and the Nostradamus Attack. (iacr.org [PDF]). 
9. Bruce Schneier: Angewandte Kryptographie. Addison-Wesley, 1996, S. 491–524
10. Serge Vaudenay: FFT-Hash is not yet Collision-free. Advances in Cryptology-CRYPTO 92, LNCS 740. Springer-Verlag, 1993, S. 587–593.
11. Claus-Peter Schnorr, Serge Vaudenay: Parallel FFT-Hashing, Fast Software Encryption, LNCS 809. Springer-Verlag, 1994, S. 149–156.
12. Ronald L. Rivest: The MD4 Message Digest Algorithm, Advances in Cryptology-CRYPTO 90, LNCS 537. Springer Verlag, 1991, S. 303–311.
13. William Stallings: Cryptography and Network Security. Prentice Hall, 1999, S. 271–297.
14. Bert den Boer, Antoon Bosselaers: Collisions for the Compression Function of MD5, Advances in Cryptology-EUROCRYPT 93, LNCS 765. Springer-Verlag, 1994, S. 293–304.
15. Xiaoyun Wang, Hongbo Yu: How to Break MD5 and Other Hash Functions, Advances in Cryptology-EUROCRYPT 2005, LNCS 3496. Springer-Verlag, 2005, S. 19–35.
16. Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0, Advances in Cryptology-CRYPTO 98, LNCS 1462. Springer-Verlag, 1999, S. 56–71.
17. Eli Biham, Rafi Chen: Near-Collisions of SHA-0, Advances in Cryptology-CRYPTO 2004, LNCS 3152. Springer-Verlag, 2005, S. 290–305.
18. Eli Biham, Rafi Chen et al.: Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology-EUROCRYPTO 2005, LNCS 3494. Springer-Verlag, 2005, S. 526–541.
19. Xiaoyun Wang, Hongbo Yu, Yiqun Lisa Yin: Efficient Collision Search Attacks on SHA-0, Advances in Cryptology-CRYPTO 2005, LNCS 3621. Springer-Verlag, 2006, S. 1–16.
20. Xiaoyun Wang, Hongbo Yu, Yiqun Lisa Yin: Finding Collisions in the Full SHA-1, Advances in Cryptology-CRYPTO 2005, LNCS 3621. Springer-Verlag, 2006, S. 17–36.
21. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. The first collision for full SHA-1
22. Hans Dobbertin, A. Basselaers, Bart Preneel: RIPEMD-160:A Strengthened Version of RIPEMD, Fast Software Encryption, LNCS 1039. Springer-Verlag, 1996, S. 71–79.
23. Xiaoyun Wang et al.: Cryptanalysis of the Hash Functions MD4 and RIPEMD, Advances in Cryptology-EUROCRYPT 2005, LNCS 3494. Springer-Verlag, 2005, S. 1–18.
24. Yuliang Zheng, Josef Pieprzyk, Jennifer Seberry: HAVAL-A one-way hashing algorithm with variable length of output, AUSCRYPT 92, LNCS 718. Springer-Verlag, 1993, S. 83–104.
25. Bart Van Rompay, Alex Biryukov, Bart Preneel, Joos Vandewalle: Cryptanalysis of 3-Pass HAVAL, Advances in Cryptology-ASIACRYPT 2003, LNCS 2894. Springer-Verlag, 2003, S. 228–245.
26. Tiger: A Fast New Hash Function. (Designed in 1995)
27. Joan Daemen, Craig Clapp: Fast Hashing and Stream Encryption with PANAMA, Fast Software Encryption, LNCS 1372. Springer-Verlag, 1998, S. 60–74.
28. Joan Daemen, Gilles van Assche: Producing Collisions for PANAMA, Instantaneously, Fast Software Encryption, LNCS 4593. Springer-Verlag, 2007, S. 1–18.
29. (Memento vom 8. April 2006 im Internet Archive)
30. Lars R. Knudsen: SMASH-A Cryptographic Hash Function, Fast Software Encryption, LNCS 3557. Springer-Verlag, 2005, S. 228–242.
31. Norbert Pramstaller, Christian Rechberger, Vincent Rijmen: Smashing SMASH, Cryptology ePrint Archive Report 2005/081
32. http://csrc.nist.gov/groups/ST/hash/first_workshop.html