Hash: Kollisionswahrscheinlichkeit abschätzen

[Buzzler]

Ich finde beim Suchen Infos über Hash-Algorithmen, Implementationen, Geschwindigkeit... was ich aber nicht finde, ist eine Aussage darüber, wie man die Wahrscheinlichkeit von Kollisionen bestimmen könnte.

Lässt sich das zumindest abschätzen? Angenommen ich habe z.B. 200 unterschiedliche Strings, wieviele Bits Adressraum brauche ich bei einem gegebenen Hash-Algorithmus, um unter x% Kollisionswahrscheinlichkeit zu kommen? Kann ich näherungsweise davon ausgehen, dass eine gute Hash-Funktion surjektiv und gleichverteilt ist und als Kollisionswahrscheinlichkeit Zahl der Eingangswerte durch Adressraum annehmen?

[Trap]

http://en.wikipedia.org/wiki/Birthday_attack

[AlecWhite]

Hashfunktionen sind in jeden Fall - d.h. per Definition surjektiv - alles andere würde auch keinen Sinn ergeben.

Gleichverteilung ist das Ziel jeder Hashfunktion, da sie ansonsten anfällig für Attacken wird. Das ist jedoch eher eine theoretische Überlegung. Mir ist keine Hashfunktion bekannt, wo der Nachweis gelingt. Die Wahrscheinlichkeit für eine Kollision ist somit im Idealfall gleich 1 / Größe des Zielraums.

[pest]

Hashfunktionen sind in jeden Fall - d.h. per Definition surjektiv

Zwingend ist dies m.M. nach nicht.


Die Wahrscheinlichkeit für eine Kollision ist somit im Idealfall gleich 1 / Größe des Zielraums.

So einfach ist das nicht. Wenn ich nur ein Datum abbilde ist die Wkt. einer Kollision 0.

Wichtige Fragen die man klären muss: Wie sind die Daten verteilt und wie sind die Schlüssel über dem Datumsraum verteilt.

[Monger]

Ein guter Hash versucht, für ähnliche Objekte möglichst unähnliche Hash Values zu geben - um eben zu verhindern, dass die Ausgangsmenge zu einer Konzentration von Hash Values in einem bestimmten Bereich führt.

Das setzt aber stillschweigend möglichst homogen verteilte Eingangsdaten voraus. Wenn man die Ausgangsdaten klever wählt und den Hash Algorithmus kennt, kann man natürlich Kollisionen provozieren. Und natürlich kann der Hash Algorithmus schlecht implementiert sein, wenn z.B. zwischen den Faktoren die den Hash bilden sollen irgendeine Relation besteht die man nicht kennt.

[Coda]

Mir ist keine Hashfunktion bekannt, wo der Nachweis gelingt.
Kryptografisch sichere Hash-Verfahren erfüllen das, wenn sie nicht total beschissen sind. Auch auf dem Papier.

Zwingend ist dies m.M. nach nicht.
Ne muss es nicht. Es muss ja nicht die gesamte Zielmenge abgebildet werden.

Ein guter Hash versucht, für ähnliche Objekte möglichst unähnliche Hash Values zu geben
Nein. Die W-Keit, das sich für zwei beliebige unterschiedliche Objekte der Hash-Wert unterscheidet sollte konstant sein. Das ist ein Unterschied.

[Buzzler]

http://en.wikipedia.org/wiki/Birthday_attackBirthday problem wohl eher, aber trotzdem danke. Angenähert mit der Stirling-Formel wäre bei dem Beispiel von 200 strings und 13 Bit Schlüsselbreite selbst im Idealfall die Kollisionswahrscheinlichkeit schon über 90%... und mit 16 Bit immer noch über 25%.

Gleichverteilung ist das Ziel jeder Hashfunktion, da sie ansonsten anfällig für Attacken wird.Nicht jede Hash-Funktion dient der Kryptografie. ;) Nicht dass es am Ziel der Gleichverteilung etwas ändern würde.

Wichtige Fragen die man klären muss: Wie sind die Daten verteilt und wie sind die Schlüssel über dem Datumsraum verteilt.Wie kann man die Verteilung der Daten beurteilen? Im Beispielfall wären das mindestens 10stellige strings, die von unterschiedlichen Benutzern eingegeben werden. Inwieweit ist das wichtig? In meiner (nicht mehr ganz so) jugendlichen Unschuld nahm ich bisher an, dass die Verteilung der Daten auf die Verteilung der Schlüssel kaum einen Einfluss hat, weil Chaos noch am Einfachsten zu erreichen wäre.

[petersenk]

Im Beispielfall wären das mindestens 10stellige strings, die von unterschiedlichen Benutzern eingegeben werden [...], weil Chaos noch am Einfachsten zu erreichen wäre.

Da täuschst du dich aber gewaltig. Die Eingaben dieser Benutzer werden wohl eher *nicht* unabhängig voneinander sein! Teilen diese Benutzer dieselbe Sprache? Was meinst du was nun mit der Häufigkeit von z.B. Vokalen, Wörtern oder Sätzen geschieht? Na? Klingelts?

Menschen produzieren so alles Mögliche, Chaos ist allerdings nicht darunter. (Überhaupt würde dies ja implizieren, dass wir gar keine determinierten Automaten sind, die ohne es zu wissen einem höheren Ziel entgegenwirken, dass ausserhalb unserer Sprache liegt. ;D)

[Buzzler]

Da täuschst du dich aber gewaltig.Nein. Es geht im Beispiel um Eingaben, die bestimmten Regeln unterworfen wären. Solange die Regeln eingehalten werden, wäre jede Eingabe zumindest einmalig. Wenn sich jemand nicht an diese Regeln hält, würde das unter shit happens fallen und wäre nicht weiter schlimm.

Menschen produzieren so alles Mögliche, Chaos ist allerdings nicht darunter.Chaos bezog sich auf die Hash-Funktion, nicht auf die Eingaben.

[Der_Donnervogel]

Wie kann man die Verteilung der Daten beurteilen? Im Beispielfall wären das mindestens 10stellige strings, die von unterschiedlichen Benutzern eingegeben werden.Mein Studium ist schon etwas her, und ich hab einiges schon wieder vergessen, aber könnte man da nicht vielleicht mit dem Chi-Quadrat-Test etwas machen? Damit müsste man doch zeigen können, dass die Hash-Funktion eine passende Verteilung hat, oder nicht? Vielleicht bin ich da aber auch auf dem Holzweg. Ich bin da über die Jahre etwas eingerostet, da ich solche theoretischen Spielereien in der Praxis nicht mehr brauche.

[Tiamat]

http://www.cs.uni-potsdam.de/ti/lehre/05-Kryptographie/slides/bremser_crypt-hashpdf.pdf

Ab Folie 8 wird die Wahrscheinlichkeit betrachtet.