Kryptographische Hash-Funktionen

In dieser Lektion betrachten wir kryptographische Hash-Funktionen, die in der schnellen Validierung und Authentifizierung weit verbreitet sind.

Am Ende der Lektion haben wir folgende Themen behandelt:

• Was kryptographische Hash-Funktionen sind
• Python-Codebeispiele zur Veranschaulichung der Verwendung von Hash-Funktionen
• Anwendungen des kryptographischen Hashings
• Die Sicherheit des kryptographischen Hashings
• Bedrohungen dieser Algorithmen durch klassische und Quantencomputer

Einführung in das kryptographische Hashing

Hash-Funktionen stellen ein wertvolles Konstrukt in der Kryptographie dar, da sie Validierung mit Vertraulichkeit verbinden. Als solche bilden Hash-Funktionen einen wichtigen Bestandteil von Mechanismen zur Datenauthentifizierung und Integrität, wie hash-basierte Nachrichtenauthentifizierungscodes (HMAC) und digitale Signaturen. Dieser Artikel erläutert die grundlegenden Ideen und Sicherheitsüberlegungen hinter kryptographischen Hash-Funktionen und skizziert potenzielle Schwachstellen durch das Aufkommen von Quantencomputing.

Grundlegende Konzeption und Gestaltung von Hash-Funktionen

Es gibt viele Situationen, in denen Authentifizierung und Integritätsprüfung kostengünstig und ohne Preisgabe privater Informationen an die prüfende Partei durchgeführt werden müssen.

Beim Herunterladen von Software von einem entfernten Server wird beispielsweise ein effizienter Mechanismus benötigt, um zu überprüfen, ob die heruntergeladene Software seit ihrer Erstellung durch den Originalautor nicht verändert wurde. Ebenso wäre es bei der Authentifizierung von Benutzern in Webanwendungen wünschenswert, einen Mechanismus zu verwenden, der weder die physische Speicherung noch die Übertragung der eigentlichen Passwörter erfordert, was deren Vertraulichkeit potenziell gefährden kann.

Kryptographische Hash-Funktionen (CHFs) begegnen diesen Anforderungen effizient und sicher.

Im Wesentlichen nimmt eine kryptographische Hash-Funktion eine Eingabe (oder Nachricht) beliebiger Länge entgegen und gibt eine Zeichenkette fester Länge von n Bits aus. Die Ausgabe einer CHF wird auch als Digest bezeichnet.

Eine nützliche CHF sollte mehrere wichtige Eigenschaften erfüllen:

1. Gleichmäßigkeit: Die von einer CHF erzeugten Digests sollten gleichmäßig verteilt sein und zufällig wirken. Das Ziel ist sicherzustellen, dass die Ausgabe keine Informationen über die Eingabe preisgibt.
2. Determinismus: Für eine gegebene Eingabe muss eine CHF stets denselben Digest erzeugen, d. h., sie muss deterministisch sein.
3. Irreversibilität: Eine CHF ist eine Einwegfunktion: Aus einem gegebenen Digest soll es praktisch unmöglich sein, das Hashing umzukehren und die Eingabe zu rekonstruieren.
4. Näherungsweise Injektivität: Obwohl CHFs Viele-zu-Eins-Funktionen sind, sollen sie wie Eins-zu-Eins-Funktionen wirken. Dies wird durch eine enorm große Ausgabemenge in Kombination mit dem Lawineneffekt erreicht, bei dem kleine Änderungen in der Eingabe zu sehr unterschiedlichen Digests führen. Diese Eigenschaft wird als näherungsweise Injektivität bezeichnet.

Auf dieser Basis lässt sich ein Datenstück gegen die Originalversion validieren, indem ein Digest der Daten mit einem Digest des Originals verglichen wird.

• Stimmen die beiden Digests überein, kann mit hoher Wahrscheinlichkeit davon ausgegangen werden, dass die Daten mit dem Original identisch sind.
• Weichen die Digests voneinander ab, ist sicher, dass die Daten manipuliert wurden oder anderweitig nicht authentisch sind.

Da die CHF-Digests selbst den tatsächlichen Inhalt der Daten oder des Originals nicht preisgeben, ermöglichen sie eine Validierung unter Wahrung der Privatsphäre.

Mathematical description

Eine Hash-Funktion $H$ kann wie folgt definiert werden:

$H : Σ^* \rightarrow \{0,1\}^n$

wobei $Σ^*$ die Menge aller möglichen Zeichenketten ist, die wir als binäre Zeichenketten beliebiger Länge betrachten können.

Die Tatsache, dass die Größe des Eingabebereichs $Σ^*$ von $H$ unbeschränkt ist, während die des Kobereichs $\{0,1\}^n$ beschränkt ist, bedeutet, dass $H$ notwendigerweise eine Viele-zu-Eins-Abbildung ist, die unendlich viele Eingaben auf eine gegebene n-Bit-Zeichenkette abbildet.

Die Eigenschaften der Gleichmäßigkeit und des Determinismus sind schön im Zufallsorakel-Modell des kryptographischen Hashings zusammengefasst.

Beispiel für kryptographisches Hashing in Python mit SHA-256

Dieses einfache Beispiel demonstriert kryptographisches Hashing mit dem beliebten SHA-256-Algorithmus aus der Python-Bibliothek cryptography. Zunächst zeigen wir, wie ein geringfügiger Unterschied in den Klartexten zu einem sehr großen Unterschied in den Hash-Digests führt.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Die beiden Nachrichten unterscheiden sich in genau einem Zeichen.

Als Nächstes instanziieren wir hash-Objekte, um den Hashing-Prozess zu ermöglichen, der Aufrufe zweier Methoden beinhaltet: update und finalize.

Wir sehen, dass aufgrund des Lawineneffekts in der SHA-256-CHF ein einziger Zeichenunterschied in den Eingabenachrichten zu zwei sehr unterschiedlichen Digests führt.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Anwendungen des kryptographischen Hashings

Die einzigartigen Eigenschaften von CHFs machen sie für eine Vielzahl von Anwendungen geeignet:

• Datenintegritätsprüfungen: Hash-Funktionen können verwendet werden, um eine Prüfsumme für einen Datensatz zu erstellen. Jede Änderung der Daten, ob absichtlich oder nicht, führt zu einer anderen Prüfsumme und warnt Systeme oder Benutzer vor der Änderung. Die Prüfsumme ist außerdem in der Regel wesentlich kompakter als die Originaldaten, was Prüfsummenvergleiche sehr schnell macht.

Abbildung 1. Sicheres Hashing für Datenintegrität

• Digitale Signaturen: Kryptographische Hashes sind für das Funktionieren digitaler Signaturen unerlässlich, da sie den Vergleich kryptographisch gehashter Nachrichten beinhalten, um Authentizität und Integrität zu gewährleisten und gleichzeitig die Privatsphäre zu wahren.

Abbildung 2. Digitale Signaturen

• Blockchain und Kryptowährungen: Kryptowährungen wie Bitcoin stützen sich stark auf CHFs, insbesondere bei der Sicherstellung der Transaktionsintegrität und bei der Ermöglichung von Konsensmechanismen wie dem Proof of Work.

Sicherheit des kryptographischen Hashings

Die Sicherheit einer CHF wird typischerweise anhand ihrer Widerstandsfähigkeit gegenüber zwei Angriffstypen bewertet: Preimage- und Kollisionsangriffen.

Preimage-Resistenz

Preimage-Resistenz bedeutet, dass es bei gegebenem Digest praktisch unmöglich sein sollte, die Eingabe zu finden.

Dies hängt mit der Einwegeigenschaft von CHFs zusammen.

Eine gute CHF ist so konzipiert, dass einer Partei, die einen Preimage-Angriff durchführen möchte, keine bessere Option als ein Brute-Force-Ansatz zur Verfügung steht, der eine Zeitkomplexität von $2^n$ hat.

mathematical details

Gegeben eine CHF $H$ und einen Digest $g$, soll es rechnerisch nicht machbar sein, eine Eingabe $m$ aus dem Preimage von $g$ zu finden, sodass $H(m) = g$ gilt.

Kollisionsresistenz

Kollisionsresistenz bedeutet, dass es schwierig ist, zwei verschiedene Eingaben zu finden, die auf denselben Digest gehasht werden.

Eine kryptographische Hash-Kollision tritt auf, wenn zwei Eingaben auf denselben Digest gehasht werden. Obwohl Kollisionen aufgrund der Viele-zu-Eins-Natur von CHFs zwangsläufig existieren, macht eine gute CHF es dennoch unpraktisch, eine solche gezielt zu finden.

Kollisionsresistenz ist entscheidend für Anwendungen wie digitale Signaturen und Zertifikate, bei denen es katastrophal wäre, wenn eine böswillige Partei eine Fälschung erstellen könnte, die auf denselben Wert gehasht wird.

mathematical details of hash collisions

$m_1, m_2$ können so gefunden werden, dass $H(m_1) = H(m_2)$ gilt.

Hash-Länge

Kollisionsresistenz ist eine schwierigere Anforderung als Preimage-Resistenz und erfordert Ausgabelängen, die doppelt so lang sind wie die für Preimage-Resistenz benötigten. Dies liegt daran, dass ein Brute-Force-Angriff, bekannt als Geburtstagsangriff, der zur Identifizierung von Hash-Kollisionen verwendet werden kann, eine Zeitkomplexität von $2^{n/2}$ hat.

In Abwesenheit kryptanalytischer Schwächen wird die Sicherheit einer Hash-Funktion daher hauptsächlich durch ihre Hash-Länge beeinflusst. Je länger der Hash, desto sicherer ist er, da Brute-Force-Angriffe schwieriger werden.

Häufig verwendete kryptographische Hash-Funktionen

Die folgende Tabelle listet einige häufig verwendete kryptographische Hash-Funktionen zusammen mit ihren Hash-Längen und primären Anwendungsbereichen auf:

Hash-Funktion	Ausgabelänge (Bits)	Häufige Anwendungen
MD5	128	Dateiintegritätsprüfung, ältere Systeme, nicht-kryptographische Zwecke
SHA-1	160	Legacy-Systeme, Git für Versionskontrolle
SHA-256	256	Kryptowährung (Bitcoin), digitale Signaturen, Zertifikate
SHA-3	Variabel (bis 512)	Verschiedene kryptographische Anwendungen, Nachfolger von SHA-2
Blake2	Variabel (bis 512)	Kryptographie, ersetzt MD5/SHA-1 in einigen Systemen
Blake3	Variabel (bis 256)	Kryptographie, Datei-Hashing, Datenintegrität

• MD5 und SHA-1, obwohl noch in weniger sicherheitskritischen Anwendungen anzutreffen, gelten hinsichtlich der Kollisionsresistenz als veraltet und werden für neue Systeme nicht empfohlen. SHA-256, Teil der SHA-2-Familie, ist weit verbreitet und für die meisten Anwendungen derzeit sicher.
• SHA-3 ist ein neuerer Standard, der 2015 von NIST als Gewinner des NIST-Hash-Funktions-Wettbewerbs ausgewählt wurde. Er ist als Drop-In-Ersatz für SHA-2 konzipiert, weist aber auch einige andere interne Eigenschaften auf und ist gegen bestimmte Angriffstypen resistent, die gegen SHA-2 wirksam sein könnten.
• Blake2 und Blake3 sind kryptographische Hash-Funktionen, die schneller als MD5, SHA-1, SHA-2 und SHA-3 sind, aber mindestens so sicher wie der neueste Standard SHA-3. Sie werden zunehmend in neuen Systemen eingesetzt, insbesondere dort, wo Geschwindigkeit wichtig ist.

Quantenrisiken für traditionelles kryptographisches Hashing

Die primäre Quantenbedrohung für das kryptographische Hashing geht von Brute-Force-Angriffen aus.

Bei einem gegebenen Digest versucht ein Angreifer, zufällige Eingaben auszuprobieren, bis er eine findet, die denselben Digest erzeugt.

Bei $n$ Bits in der Eingabe gibt es $2^n$ mögliche Werte. Daher muss der Angreifer etwa $2^{n-1}$ Eingaben ausprobieren, um eine Erfolgswahrscheinlichkeit von über 50 % zu haben.

Grovers Algorithmus

Für einen solchen unstrukturierten Suchkontext kann Grovers Algorithmus eine quadratische Beschleunigung durch eine Technik namens Quantenamplitudenverstärkung bieten und die Zeitkomplexität eines Preimage-Angriffs auf $2^{n/2}$ reduzieren.

Praktisch bedeutet das, dass eine 256-Bit-CHF, die derzeit gegen Preimage-Angriffe durch klassische Computer als sicher gilt, bei einem Quantenangreifer, der Grovers Algorithmus einsetzt, das gleiche Sicherheitsniveau wie eine 128-Bit-CHF bieten würde.

Grovers Algorithmus allein ist nicht dafür bekannt, zusätzliche Quantenbeschleunigungen gegenüber Kollisionsangriffen über die Grenzen des Geburtstagsangriffs hinaus zu bieten, der auf klassischen Computern durchgeführt werden kann. Da der klassische Geburtstagsangriff CHFs bereits zwingt, doppelt so lange Hash-Längen zu verwenden wie für Preimage-Resistenz erforderlich, stellt die Tatsache, dass die Grover-Suche die Hash-Länge in Bezug auf Preimage-Angriffe effektiv halbiert, keine praktische Bedrohung dar.

Zum Beispiel wäre die Durchführung von etwa $2^{128}$ Operationen für einen Grover-unterstützten Preimage-Angriff auf SHA-256 in absehbarer Zukunft nach wie vor nicht machbar.

BHT-Algorithmus

Ein Quantenalgorithmus, der Aspekte des Geburtstagsangriffs mit der Grover-Suche kombiniert, wurde 1997 von Brassard, Høyer und Tapp (BHT) vorgeschlagen und bietet eine theoretische Skalierung von $O(2^{n/3})$ für das Finden von Hash-Kollisionen. Diese verbesserte Skalierung setzt jedoch die Existenz von Quantenzufallsspeicher-QRAM-Technologie voraus, die derzeit nicht existiert.

Ohne QRAM beträgt die realisierbare Skalierung $\tilde{O}(2^{2n/5})$, und für die derzeit verwendeten Hash-Längen stellt diese marginale Verbesserung der Kollisionsfindungsfähigkeit im Vergleich zum Geburtstagsangriff keine kritische Bedrohung dar.

Zusammenfassung

Kryptographische Hash-Funktionen sind ein wesentlicher Bestandteil für die Gewährleistung von Datenintegrität und Privatsphäre in digitalen Informationssystemen und finden in vielen Kontexten breite Anwendung.

Die Sicherheitsanforderungen an CHFs werden hauptsächlich in Bezug auf ihre Widerstandsfähigkeit gegenüber Preimage- und Kollisionsangriffen verstanden. Bei gut konzipierten CHFs ist die Hash-Länge ein guter Indikator für das Sicherheitsniveau.

Obwohl das Aufkommen von Quantencomputern, die Grover- und BHT-Algorithmen ausführen, theoretisch die Preimage- und Kollisionsresistenz traditioneller CHFs beeinflusst, bedeuten die bereits heute verwendeten langen Hash-Längen, dass moderne kryptographische Hashing-Algorithmen wie SHA-3 voraussichtlich sicher bleiben werden – vorbehaltlich der Entdeckung bisher unbekannter kryptanalytischer Angriffe.

Die Relevanz von CHFs liegt in ihrer Rolle als grundlegender Baustein für quantenresistente kryptographische Verfahren, die sicherstellen, dass digitale Informationen auch angesichts potenzieller zukünftiger Fortschritte in Quantencomputing-Algorithmen und -Technologien sicher bleiben.