Hashfunktionen - Kollisionsresistenz

ich versuche mal zu erklären, was ich zu dem Thema Kollisionsresistenz bei Hashfunktionen verstanden habe:

Schwache Kollisionsresistenz:
Man hat eine Nachricht mit einen Hashwert vorgegeben. Es ist hier unmöglich eine andere Nachricht zu finden die den gleichen Hashwert hat.

Im Skript wurde das Geburtstagsparadoxon als Beispiel verwendet. Ich würde den zugehörigen Fall darin sehen, wie viele Gäste erscheinen müssen, damit die Wahrscheinlichkeit, dass einer am gleichen Tag Geburtstag hat wie du größer ist als 50%. Wir haben also sozusagen eine vorgegeben Nachricht mit einen Wert (dein Geburtstag) und suchen eine Nachricht mit dem gleichen Wert (also jemanden der am selben Tag Geburtstag hat).

Die Aufgabe 2.6 a) (KE2 S. 84) würde ich auch als schwache Kollisionsresistenz ansehen.
Denn auch hier hat man eine vorgegebene Nachricht und sucht eine andere Nachricht mit dem selben Hashwert.


Starke Kollisionsresistenz:
In diesem Fall hat man sozusagen einen ganzen Topf voll Nachrichten gegeben und sucht sich zwei raus, die den selben Hashwert besitzen. Es gibt also keine vorgegebene Nachricht mehr. Man erzeugt also unterschiedliche Nachrichten bis 2 beliebige von diesen den gleichen Hashwert haben.

Das Beispiel mit dem Geburtstag wäre dann entsprechend: Wie viele Gäste müssen erscheinen, damit die Wahrscheinlichkeit, dass 2 Gäste am gleichen Tag Geburtstag haben größer ist als 50%. Hier haben wir kein festes Datum mehr gegeben. Man hat hier eine Gruppe von Personen und sucht sich die Personen raus, die zufällig am gleichen Tag Geburtstag haben. Der Tag und die Person sind also nicht vorgegeben so wie bei der schwachen Kollisionsresistenz.

Zu der starken Kollisionsresistenz würde ich entsprechend Aufgabe 2.6 b) im Skript zählen. Hier sollen 2 der zufällig erzeugten Nachrichten den gleichen Hashwert haben. Es ist also nicht vorgegeben zu welcher Nachricht mit einem bestimmten Hashwert eine andere Nachricht mit dem selben Hashwert gesucht wird. Beide Nachrichten sind sozusagen beliebig aus den erzeugten Nachrichten wählbar.

Ich hoffe das ist verständlich und nun klarer.
Bitte um Korrektur, wenn ich etwas falsch wiedergegeben bzw. verstanden habe.

schwach, aka 2tes urbild: du hast einen hash von einem haufen daten gegeben und versuchst zu genau diesem hash noch einen haufen zu finden, der denselben hat.

stark: du findest zwei beliebige datenhaufen, die denselben hash haben.

es gibt zb für MD4 eine implementierung in C, da drückst du das knöpfchen und es kommen 2 haufen daten raus, die denselben hash haben. es ist aber nicht möglich, einen hash vorzugeben, zu dem dann die kollision gefunden wird. letzteres hat (nach meinem verständnis) für die praxis viel schwerwiegendere folgen. insofern ist die bezeichnung schwach/stark etwas unglücklich und falschherum.


grüßchen

backi schrieb:

[...] insofern ist die bezeichnung schwach/stark etwas unglücklich und falschherum.


grüßchen

Zum Vergrößern anklicken....

Danke für den letzten Satz, ohne diesen hätte ich die Beschreibung immer noch nicht verstanden. Hab nämlich immer noch ein kleines Problem das zu 100% zu verstehen. Aber so wie du es beschrieben hast hätte ich die Bezeichnungen stark und schwach wohl auch vertauscht.

Ich nehme alles zurück. Verstehe es doch nicht. Ist für mich irgendwie 1:1 das selbe.

Wikipedia:
Die Hashfunktion wird als schwach kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, zu einem gegebenen Dokument ein zweites Dokument zu finden, das mit kollidiert (für das also gilt).

Die Hashfunktion wird als (stark) kollisionssicher bezeichnet, wenn es praktisch undurchführbar ist, überhaupt eine Kollision, also zwei beliebige (aber verschiedene) mit , zu finden.

Andere Seite: https://www.secupedia.info/wiki/Hash-Funktion#Schwache_Kollisionsresistenz

Da steht für mich immer das selbe --> h(M0) = h(M1) darf nicht gegeben sein.

Ich glaube, Du hast das Prinzip des Hashen noch nicht ganz verstanden. Hier wird auf eine Ursprungsmenge auf eine kleinere Zielmenge abgebildet. Stell Dir vor, Du hast eine Urmenge von 20 Nachrichten aber nur eine Zielmenge von 10 Hashwerten. Bei der Gleichverteilung der 20 Nachrichten auf die 10 Hashwerte, werden 2 Nachrichten auf jeweils einen Hashwert abgebildet. In der Realität muss also der Raum der Zielmengen deutlich größer sein um Kollisionen zu verhindern.

Bei der schwachen Kollisionsresistenz darf es eben zu einem gegebenen Wert der Ursprungsmenge kein zweiten Wert der Ursprungsmenge geben, die auf den selben Zielwert (Hashwert) abgebildet wird.

Bei der starken Kollisionsresistenz soll es unmöglich sein für zwei beliebige Urbildmengen (M1 und M2) zu finden, die auf einen Zielwert abbilden. Dies wird im Skript mit den Geburtstags-Paradoxon beschrieben.

deka-online schrieb:

Da steht für mich immer das selbe --> h(M0) = h(M1) darf nicht gegeben sein.

Zum Vergrößern anklicken....

An sich ja.
Schwache Kollisionsresistenz sagt dass du zu einem m0 kein m1 findest, das auf denselben Hashwert abbildet.
Starke Kollisionsresistenz betrachtet zwei beliebige m0 und m1, bei denen das ebenfalls praktisch nicht möglich sein soll.

Zu den Begriffen "Stark" und "Schwach": Es ist für den Angreifer viel einfacher zu zwei beliebigen Klartexten denselben Hashwert zu finden (daher muss die Kollisionsresistenz stark sein) als zu einem vorgegebenen Hashwert einen weiteren Klartext (daher "Schwach"). Vielleicht kannst du dir das so merken.