Hashverfahren

Einige kurze Erläuterungen zu Hashverfahren und das vermutlich wichtigste Anwendungsgebiet für diese wurden bereits im Abschnitt über digitale Signaturverfahren erwähnt. Dies soll nun weiter vertieft werden.

Hashverfahren sind Funktionen, die Eingaben variabler, aber endlicher Länge auf eine Ausgabe kleinerer bzw. konstanter Länge mit abbilden und sich einfach berechnen lassen. Dabei unterscheidet man zwischen zwei Typen: Hashverfahren, die einen geheimen Schlüssel verwenden, und solche, die ohne eine weitere Eingabe auskommen. Zum ersten Typ zählen die sogenannten message authentication codes (MACs), die sowohl zur Überprüfung des Urhebers als auch der Integrität einer Nachricht verwendet werden. Weiter verbreitet sind jedoch Funktionen des zweiten Typs, u.a. die modification/manipulation detection codes (MDCs), deren einziger Zweck im Nachweis der Unversehrtheit einer Nachricht besteht. Diese lassen sich weiter unterteilen in die one-way hash functions (OWHFs) und die collision resistant hash functions (CRHFs), welche später noch genauer betrachtet werden. Im Folgenden werden wir uns - wenn nicht anders erwähnt - auf die MDCs beschränken.

Eigenschaften der Funktionen

An Hashfunktionen stellt man oft noch weitere Anforderungen, ohne die ein praktischer Einsatz nicht von Nutzen wäre:

Wie man leicht einsieht, folgt aus der starken Kollisionsfreiheit die schwache Form, d.h. eine stark kollisionsfreie Hashfunktion ist somit immer auch schwach kollisionsfrei.

Im Gegensatz dazu folgt jedoch aus (starker) Kollisionsfreiheit nicht die Eigenschaft der Einweg-Funktion, ein Beispiel hierfür ist die Identitätsfunktion fester Länge, die aufgrund ihrer Bijektivität (stark) kollisionsfrei ist. Diese Funktion ist jedoch zugleich das Inverse von sich und somit keine Einweg-Funktion.

Nun lassen sich auch die schon genannten OWHFs und CRHFs definieren:

Angriffe auf Hashfunktionen

Je nachdem, welche der oben genannten Eigenschaften eine Hashfunktion besitzt, verbleiben verschiedene Angriffsmöglichkeiten und Situationen, in denen die Verwendung dieser Funktion nicht sinnvoll ist.

Unterschriften fälschen.
Angenommen, es existiert ein Dokument mit der gültigen Unterschrift . Der Angreifer Oskar könnte nun versuchen, ein weiteres Dokument mit zu finden. Dies gelingt ihm nur, wenn es sich bei um eine Hashfunktion handelt, die nicht schwach kollisionsfrei ist. Sollte es Oskar möglich sein, eine Kollision zu ermitteln, befände er sich dann im Besitz des gefälschten, aber nicht als solches erkennbaren Paares .

Nehmen wir nun an, Bob ist mit diesem Problem vertraut und benutzt deshalb nur die schwach kollisionsfreie Hashfunktion , doch von stark kollisionsfreien hat er noch nie etwas gehört. Unser Angreifer Oskar, der Bob gut genug kennt, um dieses zu wissen, nutzt es für einen weiteren Angriff aus. Er bestimmt zwei Dokumente und , mit und überredet Bob, das Dokument mit dem Hashwert zu signieren. Wenn er damit Erfolg hat, so stellt ebenfalls eine gültige, aber gefälschte Signatur von dar und Oskar kann beispielsweise Alice gegenüber behaupten, Bob hätte das Dokument unterschrieben.

birthday attack.
Betrachten wir nun Hashfunktionen der Form mit . Je zwei Elemente aus dem Urbild für liefern eine Kollision. Die Anzahl an Kollisionen lässt sich mit der Cauchy-Schwartz Ungleichung (, falls ) abschätzen

Falls gilt, so erhält man also sehr viele Kollisionen.

Für ideale Hashfunktionen beträgt der maximale Aufwand, für einen festen Hashwert ein zugehöriges Dokument bzw. zu einem vorgegebenen Dokument ein weiteres mit identischem Hashwert zu ermitteln, jeweils Hashoperationen: wenn man davon ausgeht, dass eine zufällige, gleichmäßig verteilte Eingabe zu einem zufälligen, gleichmäßig verteilten Hashwert führt, ist die Wahrscheinlichkeit, mit einer solchen Eingabe einen festen Hashwert zu treffen gleich und die erwartete Anzahl Versuche bis zum ersten Treffer somit . Unter Verwendung des sogenannten Geburtstagsangriffs (birthday attack) ist es jedoch möglich, zwei Dokumente mit gleichem Hashwert mit etwa Operationen zu bestimmen.

Dazu wählt man zufällig Nachrichten und berechnet deren Hashwerte. Dann gilt

also . Nun sei konstant, und somit folgt

Für und genügend groß erhält man deshalb

d.h. man hat mit etwa zufällig gewählten Werten eine gute Chance, eine Kollision zu finden.

Übungen

Aufgabe 1

1. Wie viele Leute müssen in einem Raum sein, so dass mit einer Wahrscheinlichkeit größer als mindestens eine Person heute Geburtstag hat?
   (Hinweis: Betrachten Sie das Komplementärereignis.)
2. Wie viele Leute müssen in einem Raum sein, so dass mit einer Wahrscheinlichkeit größer als mindestens zwei Personen am gleichen Tag Geburtstag haben?
   (Hinweis: Betrachten Sie das Komplementärereignis. Es gilt für .)

Link zu den Lösungen