Kryptographische Hash-Funktionen

Eine kryptographische Hash-Funktion komprimiert beliebige Eingaben in einen kurzen, festen Digest, und zwar auf eine Weise, die einweg und kollisionsresistent ist. Sie dient als grundlegender Baustein für Integrität, Authentifizierung und viele übergeordnete Protokolle.

Definition

Eine kryptographische Hash-Funktion ist eine deterministische Funktion, die Eingaben beliebiger Länge auf eine Ausgabe fester Länge (Digest) abbildet, sodass es undurchführbar ist, ein Preimage, ein Second-Preimage oder zwei beliebige unterschiedliche Eingaben zu finden, die dieselbe Ausgabe erzeugen.

Scope

Dieses Thema behandelt die Sicherheitseigenschaften von Hash-Funktionen (Preimage-, Second-Preimage- und Kollisionsresistenz), ihre internen Konstruktionen (Merkle-Damgaard, Sponge), die standardisierten Familien SHA-2 und SHA-3 sowie Anwendungen wie Integritätsprüfung, Passwortspeicherung, Commitment und Proof-of-Work. Es befasst sich mit kryptanalytischen Angriffen, einschließlich der Geburtstagsschranke und den Brüchen von MD5 und SHA-1. Ausgenommen sind schlüsselbasierte Authentifizierungscodes, die unter Nachrichtenauthentifizierungscodes behandelt werden, obwohl viele MACs aus Hash-Funktionen aufgebaut sind.

Core questions

• Was unterscheidet eine kryptographische Hash-Funktion von einer gewöhnlichen Prüfsumme oder Hash-Tabellenfunktion?
• Warum sind Preimage-, Second-Preimage- und Kollisionsresistenz unterschiedlich, und wie hängen sie zusammen?
• Warum begrenzt das Geburtstagsparadoxon die Kollisionsresistenz auf die Hälfte der Digest-Länge?
• Wie erweitern Merkle-Damgaard- und Sponge-Konstruktionen eine Kompression fester Größe auf beliebige Eingaben?
• Wie werden Hash-Funktionen verwendet, um Daten zu committen, die Integrität zu überprüfen und Passwörter zu speichern?

Key concepts

• Nachrichten-Digest
• Preimage-Resistenz
• Second-Preimage-Resistenz
• Kollisionsresistenz
• Geburtstagsangriff
• Merkle-Damgaard-Konstruktion
• Sponge-Konstruktion (Keccak)
• Längenerweiterungsangriff
• Proof-of-Work

Key theories

Kollisionsresistenz und die Geburtstagsschranke

Aufgrund des Geburtstagsparadoxons ist ein generischer Kollisionsfindungsangriff auf einen n-Bit-Hash in etwa 2^(n/2) Arbeit erfolgreich; Kollisionsresistenz erfordert daher Digests, die ungefähr doppelt so lang sind wie das gewünschte Sicherheitsniveau (z. B. 256 Bit für 128-Bit-Sicherheit).

Iterierte und Sponge-Konstruktionen

Das Merkle-Damgaard-Paradigma konstruiert einen vollständigen Hash, indem es eine Kompressionsfunktion mit fester Eingabe über Nachrichtenblöcke iteriert; die von SHA-3 (Keccak) verwendete Sponge-Konstruktion absorbiert Eingaben in einen großen Permutationszustand und presst Ausgaben daraus, wodurch Längenerweiterungsschwächen vermieden werden.

Mechanisms

Ein Merkle-Damgaard-Hash füllt die Nachricht auf, teilt sie in Blöcke und wendet iterativ eine Kompressionsfunktion an, die jeden Block in einen laufenden Verkettungswert mischt, wobei der endgültige Wert als Digest ausgegeben wird. Die Sponge-Konstruktion von SHA-3 absorbiert stattdessen Nachrichtenblöcke, indem sie diese in einen Teil eines großen Zustands XORt, der durch die Keccak-f-Funktion permutiert wird, und presst dann Digest-Bits heraus, wodurch die Längenerweiterungseigenschaft vermieden wird, die einem einfachen Merkle-Damgaard inhärent ist.

Clinical relevance

Hash-Funktionen sind allgegenwärtig: Sie überprüfen die Integrität von Software-Downloads, verankern digitale Signaturen (die einen Hash signieren, nicht das gesamte Dokument), indizieren Inhalte in Git und Content-Delivery-Netzwerken, sichern die Passwortspeicherung über langsame Schlüsselableitungsfunktionen (bcrypt, Argon2) und stellen den Proof-of-Work und die Merkle-Bäume bereit, die Blockchains zugrunde liegen. Der praktische Bruch der Kollisionsresistenz von MD5 und SHA-1 erzwang die Migration zu SHA-2 im gesamten Internet.

Evidence & guidelines

SHA-2 (SHA-256, SHA-512) ist in FIPS 180-4 und SHA-3 in FIPS 202 spezifiziert; beide sind NIST-zugelassen. MD5 und SHA-1 sind für Sicherheitsanwendungen nach demonstrierten Kollisionsangriffen (wobei die SHAttered SHA-1-Kollision von 2017 ein Meilenstein war) veraltet. Für die Passwortspeicherung empfehlen Standards speicherintensive Funktionen wie Argon2 anstelle von einfachem Hashing.

History

Die MD-Familie (Rivests MD4 und MD5) und die von der NSA entworfenen SHA-0/SHA-1 dominierten die 1990er Jahre. Xiaoyun Wangs Kollisionsangriffe (2004-2005) brachen MD5 und schwächten SHA-1, was den offenen SHA-3-Wettbewerb des NIST (2007-2012) auslöste, der vom Keccak-Sponge-Design von Bertoni, Daemen, Peeters und Van Assche gewonnen wurde. SHA-1 wurde 2017 durch die SHAttered-Kollision praktisch gebrochen.

Key figures

• Ralph Merkle
• Ivan Damgaard
• Guido Bertoni
• Joan Daemen
• Xiaoyun Wang

Seminal works

• nist2015sha3
• katz2020
• menezes1996

Frequently asked questions

Warum kann ich ein Passwort nicht einfach hashen und den Digest speichern?

Einfache kryptographische Hashes sind schnell, was Angreifern ermöglicht, Milliarden von Vermutungen pro Sekunde gegen eine gestohlene Datenbank zu testen. Die Passwortspeicherung verwendet stattdessen bewusst langsame, gesalzene, speicherintensive Funktionen (bcrypt, scrypt, Argon2), damit das Brute-Forcing jedes Passworts aufwendig ist.

Ist SHA-256 jetzt gebrochen, da SHA-1 es ist?

Nein. SHA-1 und SHA-256 sind unterschiedliche Algorithmen; die Kollisionsangriffe auf SHA-1 übertragen sich nicht auf SHA-2. SHA-256 bleibt ungebrochen und ist neben SHA-3 der empfohlene Allzweck-Hash.