Hallo,
Ich möchte die Wahrscheinlichkeit wissen, wie oft es bei SHA256 zu Kollisionen kommt wenn E-Mail Adressen gehashed werden.
Beispiel: Ich möchte die Hashcodes von 50 Mio E-Mail Adressen speichern (Hashcodes wegen des Datenschutzes). Wie hoch ist die Chance, dass zwei unterschiedliche E-Mail Adressen den selben Hashcode bilden?
Problem dabei: E-Mail Adressen sind in der Regel zwischen 9 und etwa 50 Zeichen lang und bestehen nur aus einem eingeschränkten Zeichensatz (zB nur Kleinbuchstaben, wenige Sonderzeichen etc). Somit ist auch die Chance auf Kollisionen im SHA256 höher, oder?
Wie kann ich die Wahrscheinlichkeit einer Kollision berechnen? Wenn ich die Adressen der Reihe nach einspeise, alle wieviel Adressen muss ich mit einer Kollision rechnen?
Volker
Frage an Mathe-Spezialisten betreffend SHA256
Also wenn der SHA256 einen 256-Bit-Schlüssel generiert (keine Ahnung ob das so ist, aber ich geh von der Namensgebung her mal davon aus), dann kannst Du 2^256 verschiedene Schlüssel speichern ohne Kollision. Diese Zahl ist verdammt groß, ich weiß gar nicht ob man die noch mit "normalen" Worten ausdrücken kann. Auf jeden Fall ein extrem vielfaches von 50 Mio, von daher würd ich mal davon ausgehen, daß das verdammt sicher ist.
ZeHa hat bisher kein Danke erhalten.
Klicke hier, wenn Du wissen möchtest, woran ihm das vorbeigeht.
Hi ZeHa,
Naja, so einfach ist das dann doch wieder nicht. Natürlich sind es 2^256 mögliche(!) Hashcodes. Aber das bedeutet nicht, dass man so viele Ursprungsdokumente benötigt um eine Kollision zu finden. Das lässt sich am Geburtstagsparadoxon erkennen: Die Wahrscheinlichkeit, dass in einer Gruppe von mindestens 23 Personen zwei Personen am gleichen Tag Geburtstag haben, ist größer als ½.
Eine Geburtstags-Attacke lautet dann so:
Angriff auf die Kollisionsresistenz
Länge des Hashwertes: n Bits
2n verschiedene Hashwerte möglich
Erzeugen von Hashwerten zu ca. 2^n/2 verschiedenen Nachrichten liefert mit hoher Wahrscheinlichkeit eine Kollision
Desshalb suche ich jemanden der mir hier eine Wahrscheinlichkeit errechnen kann, alle wie viele E-Mail Adressen ich mit einer Kollision rechnen muss. Vor allem weil die möglichen Eingangsvariationen (E-Mail) begrenzt sind.
Volker
Naja, so einfach ist das dann doch wieder nicht. Natürlich sind es 2^256 mögliche(!) Hashcodes. Aber das bedeutet nicht, dass man so viele Ursprungsdokumente benötigt um eine Kollision zu finden. Das lässt sich am Geburtstagsparadoxon erkennen: Die Wahrscheinlichkeit, dass in einer Gruppe von mindestens 23 Personen zwei Personen am gleichen Tag Geburtstag haben, ist größer als ½.
Eine Geburtstags-Attacke lautet dann so:
Angriff auf die Kollisionsresistenz
Länge des Hashwertes: n Bits
2n verschiedene Hashwerte möglich
Erzeugen von Hashwerten zu ca. 2^n/2 verschiedenen Nachrichten liefert mit hoher Wahrscheinlichkeit eine Kollision
Desshalb suche ich jemanden der mir hier eine Wahrscheinlichkeit errechnen kann, alle wie viele E-Mail Adressen ich mit einer Kollision rechnen muss. Vor allem weil die möglichen Eingangsvariationen (E-Mail) begrenzt sind.
Volker
Hm, Forschern ist ja gelungen, eine Kollision mit 2^69 Versuchen zu "ermitteln" - raten wäre der bessere Ausdruck. Daraus ergibt es eine Wahrscheinlichkeit von 1/2^69 *glaub* ... auf alle Fälle ist die Gefahr einer Kollision sehr gering. Bei SHA128 liegt die Wahrscheinlichkeit bei 0,000 000 000 000 000 000 000 000 000 000 000 000 029%, dass ein Schlüssel 2x vorkommt. Bei SHA256 dürfte es noch "etwas" weniger sein 
Gruß, Daniel 
| In der Realität ist die Wirklichkeit ganz anders...
PB 4.10 (Windows XP SP 2)
| In der Realität ist die Wirklichkeit ganz anders...PB 4.10 (Windows XP SP 2)
Klar, das stimmt natürlich, aber den Geburtstags-Test kannst Du doch auf jede beliebige Größenordnung anwenden. Somit mußt Du halt nur statt mit 365 Möglichkeiten die Berechnung mit 2^256 Möglichkeiten machen 
ZeHa hat bisher kein Danke erhalten.
Klicke hier, wenn Du wissen möchtest, woran ihm das vorbeigeht.
also laut http://en.wikipedia.org/wiki/SHA-1 bzw. der kleinen tabelle weiter unten bei "SHA sizes", sind bisher keine kollisionen für SHA-256/224 & SHA-512/384 bekannt.
c ya,
nco2k
c ya,
nco2k
~|__/
..o.o.. <--- This is Einkaufswagen. Copy Einkaufswagen into your signature to help him on his way to world domination.
..o.o.. <--- This is Einkaufswagen. Copy Einkaufswagen into your signature to help him on his way to world domination.
das ist von logik her schon falsch - da aus einem text (egal wie lang der ist) - ein 256 bit hash errechnet wird - somit sind kollisionen vorprogrammiert - jedoch ist SHA darauf optimiert möglichst wenige kollisionen zu produzieren...also laut http://en.wikipedia.org/wiki/SHA-1 bzw. der kleinen tabelle weiter unten bei "SHA sizes", sind bisher keine kollisionen für SHA-256/224 & SHA-512/384 bekannt.
generell werden diese hash's für passwörter benutzt. wenn du dagegen prüfen willst, ob eine email in deiner datenbank schon existiert - du aber nie den echten mail-namen nutzten kannst, dann ist SHA - und alle anderen Hash-Verfahren ungeeignet - da wie gesagt das Problem mit Kollisionen besteht - so kann es passieren dass mail@web.de und xyz@gmx.de den gleichen hash-wert haben - woher willst du dann wissen welche von den adressen bereits registriert ist? da nutzt dir jede wahrscheinlichkeit nix - es ist einfach "zufall", dass die gleich sind...
für passwörter ist es nicht so schlimm, da du nicht eine million/milliarde an passwörtern eingeben wirst
trotzdem ist die wahrscheinlichkeit, dass 2 mail-addr gleichen hash haben fast 0 - das kommt daher, weil:
1) mail-addr sind kurz (schon mal 32 zeichen lange adresse gesehen?)
2) mai-adressen haben nur bestimmte zeichen (kleine buchstaben reichen schon aus) und wenige sonderzeichen
sollten alle mails das erfüllen, dann liegt die wahrscheinlichkeit für eine kollision bei 1 zu 2^128 (schätze ich)
-
Froggerprogger
- Badmin
- Beiträge: 855
- Registriert: 08.09.2004 20:02
Klar sind Kollisionen möglich. Was die dort meinen ist, dass keine einzige bekannt ist. D.h. niemand kennt bisher irgendwelche 2 Worte, die auf denselben Hashwert abgebildet werden. Das klingt doch erstmal vielversprechenddas ist von logik her schon falsch - da aus einem text (egal wie lang der ist) - ein 256 bit hash errechnet wird - somit sind kollisionen vorprogrammiert - jedoch ist SHA darauf optimiert möglichst wenige kollisionen zu produzieren...also laut http://en.wikipedia.org/wiki/SHA-1 bzw. der kleinen tabelle weiter unten bei "SHA sizes", sind bisher keine kollisionen für SHA-256/224 & SHA-512/384 bekannt.
Ansonsten zur Wahrscheinlichkeit:
Nehmen wir mal an, dass die Hashfunktion echt zufällig in ihren Wertebereich der Größe N = 2^256 hasht (wenngleich das etwas optimistisch ist).
Dann können wir einfach die klassische Wahrscheinlichkeit nutzen.
Dann ist die Wahrscheinlichkeit für eine Kollision beim Hinzufügen der ersten Mail: 0 / N
beim Hinzufügen der zweiten: 1 / N
beim Hinzufügen der dritten: <= 2 / N
beim Hinzufügen der vierten: <= 3 / N
...
Das <-Zeichen stammt daher, dass die Wahrscheinlichkeit - sollte es bereits eine Kollision gegeben haben - im Folgenden für eine weitere geringer wird, da ja dann nach z.B. 3 Email-Adressen mit 1 Kollision nur 2 verschiedene enthalten sind. D.h. diese Abschätzung ist hier schon der worst-case.
Also erhalten wir 0/N + 1/N + .... + 50.000.000/N = 1/N * (0 + 1 + 2 + ... + 50.000.000) = 1/N * (50.000.000^2 + 50.000.000)/2 = 1/N * 1.250.000.025.000.000 =~ 1.0795 * 10^-62
Dafür, dass bei 50.000.000 Emails eine Kollision auftritt ist die Wahrscheinlichkeit mit 1 zu 10^62 also außerordentlich gering. (entspricht etwa 1 zu 2^202)
Ein Hauptanliegen von Hashfunktionen ist, Ähnlichkeiten zwischen Ausgangsworten zu zerstören. Es wird daher sogar eher im Gegenteil sein, dass durch ähnliche Worte Kollisionen noch unwahrscheinlicher werden.Problem dabei: E-Mail Adressen sind in der Regel zwischen 9 und etwa 50 Zeichen lang und bestehen nur aus einem eingeschränkten Zeichensatz (zB nur Kleinbuchstaben, wenige Sonderzeichen etc). Somit ist auch die Chance auf Kollisionen im SHA256 höher, oder?
Meine Einschätzung ist, dass du ohne Sorgen einfach SHA-2 nutzen kannst. Um noch eine paranoide Stufe sicherer zu gehen (was nie schaden kann), kannst du ja noch einen zweiten SHA-2 zusätzlich speichern, der z.B. erzeugt wird, wenn du die Email-Adresse rückwärts einliest. Damit sollte wirklich jeder letzte Zweifel behoben sein. Dass zwei verschiedene Email-Adressen vorwärts und rückwärts auf jeweils denselben Hashwert gehasht werden ist absolut derbst unwahrscheinlich.
(Man ist versucht zu glauben, dass da kein großer Unterschied ist, aber da die Wahrscheinlichkeit schon für ein einmaliges Auftreten derart gering ist, ist es ganz im Gegenteil eine sehr krasse weitere Sicherheitsmaßnahme.)
Außerdem könntest du so im Falle des Falles, dass einer der Hashwerte übereinstimmt, dieses Ereignis abfangen, die entsprechenden Emailadressen raussuchen und Ruhm dafür ernten, die erste Kollision gefunden zu haben.
Aber warte da nicht drauf. Bei einer Wahrscheinlichkeit von 1 zu 1^62 (hundert Decillionen) würde ich locker auch mal mein Leben aufs Spiel setzen. Selbst die Gefahr, in seinem Leben von einem vom Himmel fallenden Klavier erschlagen zu werden ist unglaublich viel größer:
Wieviele Menschen hat es bisher auf der Erde gegeben ? Worst-Case: 20000 Jahre, wobei alle 20 Jahre 5.000.000.000 neue Menschen da sind, macht 1000*5 Mrd = 5*10^12 Menschen bisher. Von all denen sind vielleicht erst sieben von einem Klavier erschlagen worden. Damit ist die Wkt von einem Klavier erschlagen zu werden 7 zu 5*10^12, und somit ca. 10^50-fach, also etwa hundert Oktillionen-fach größer, als eine Kollision in deiner Email-Liste. Also immer schön nach oben gucken!
Noch mehr Rechenspaß: Um mit Wahrscheinlichkeit 0.000004 Prozent eine Kollision zu haben musst du etwa 10^36 Emails - also eine Quinquilliarde Emails - einsortieren.
Aber dies alles gilt nur für eine echt zufällige Hashfunktion. Da SHA-2 aber nicht echt zufällig sein kann ist sie vielleicht 10-mal oder sogar ein paar hundertausendmal schlechter als echt zufällig - was immernoch völlig egal wäre.
!UD2
jep, genauso habe ich es auch gemeint.Froggerprogger hat geschrieben:Klar sind Kollisionen möglich. Was die dort meinen ist, dass keine einzige bekannt ist. D.h. niemand kennt bisher irgendwelche 2 Worte, die auf denselben Hashwert abgebildet werden. Das klingt doch erstmal vielversprechenddas ist von logik her schon falsch - da aus einem text (egal wie lang der ist) - ein 256 bit hash errechnet wird - somit sind kollisionen vorprogrammiert - jedoch ist SHA darauf optimiert möglichst wenige kollisionen zu produzieren...also laut http://en.wikipedia.org/wiki/SHA-1 bzw. der kleinen tabelle weiter unten bei "SHA sizes", sind bisher keine kollisionen für SHA-256/224 & SHA-512/384 bekannt.
c ya,
nco2k
~|__/
..o.o.. <--- This is Einkaufswagen. Copy Einkaufswagen into your signature to help him on his way to world domination.
..o.o.. <--- This is Einkaufswagen. Copy Einkaufswagen into your signature to help him on his way to world domination.