SHA-224 kollisionsfreier Hash

[SimonX]

Hi,

Der SHA-256 und SHA-224 sollen kollisionsfrei sein. Wie sieht es aus, wenn man nun den SHA-224 benutzt um Signaturen von kurzen Messages zu machen um die Einzigartigkeit einer Message zu testen. Kann man davon ausgehen, das es dann auch keine Kollisionen geben wird bzw. welche Wahrscheinlichkeit gibt es für Kollisionen?

Es geht mir nur um die Komprimierungseigenschaft des SHA.

Ausserdem: Kann man den SHA-256 oder SHA-224 auf noch weniger Bits reduzieren ohne die Kollisionsfreiheit zu zerstören?

PS: Ich möchte die Einzigartigkeit der letzten 20 Milliarden Messages sicherstellen (alle Messages der letzten zwei Monate). Die Messages sind alle so 20 bis 60 Zeichen lang.

[ESAD]

kollisionsfrei kann kein hashwert sein. es kann die wahrscheinlichkeit möglichst verringert sein aber man hat eben nur begrenzt möglichkeiten die werte als hash darzustellen. 100% kollisionsfrei wäre wenn man den klartext als hash heranzieht.

aber ja es ist sehr unwahrscheinlich dass eine kollision auftritt

[drmaniac]

kurzes OT: was sind das für messages? Irgendwelche Systemevents? Selbst wenn ich an etwas wie Tivoli und co denke, ist das einfachzu groß... Mich fasziniert die Menge :D

[SimonX]

Das sind die CDR's eines GSM Operators über zwei Monate. Man will ja einen Call nicht zweimal bezahlen ... ;-)

(So 200M Calls pro Tag.)

[Grestorn]

kollisionsfrei kann kein hashwert sein. es kann die wahrscheinlichkeit möglichst verringert sein aber man hat eben nur begrenzt möglichkeiten die werte als hash darzustellen. 100% kollisionsfrei wäre wenn man den klartext als hash heranzieht.

Kommt darauf an, was man alles als Hash bezeichnet.

Der gezippte Klartext ist immer eineindeutig in den Klartext rückführbar und dennoch kleiner. Wenn man das als Hash bezeichnen würde... :)

Ich weiß, ich spalte Haare... :)

[SimonX]

Kann man denn bei nur 64 bytes verkünftig zippen?

[Berni]

Bei 20 - 60 Byte Datenmenge lohnt sich aber auch der SHA256-Hash fast nicht (braucht 32 Byte), da spart man ja nicht mal die Hälfte und hat dabei das (wenn auch sehr geringe) Risiko der Kollisionen. Durch SHA256 können eben exakt 2^256 Zustände abgebildet werden. Das ist extrem viel mehr als die 20 Milliarden Datensätze aber theoretisch kann auch schon bei 2 zufälllig gebildeten Datensätzen eine Kollision auftreten (wenn auch mit verschwindend geringer Wahrscheinlichkeit).

Die Kollisionsfreiheit jedweden Hashalgorithmus bezieht sich nur darauf, dass man Kollisionen nicht bewusst erzeugen kann (zumindest nach derzeitigem Wissensstand); zufällig können Kollisionen aber immer auftreten.

Wenn die Kollisionsfreiheit zu 100% sicher gestellt werden muss musst du den Klartext speichern (evtl. verschlüsselt wenn es darum geht dass der Klartext nnicht erkennbar sein soll). Komprimiert macht wohl in der Tat wenig Sinn bei so wenig Bytes.
Wenn du für eine Datenbank einen kostant großen Schlüssel brauchst kannst du schon SHA256 nehmen aber ich würde zusätzlich noch den Klartext mitspeichern und als kombinierten Index verwenden. Wenn du statt dem Klartext in einer weiteren Spalte einen weiteren Hash (z.B. md5) mitspeichern solltest wird die Wahrscheinlichkeit einer Kollision zwar nochmals verringert aber möglich ist sie trotzdem. Nur das Speichern des Klartexts, einer komprimierten Form des Klartexts oder ein verschlüsselter Klartext kann Kollisionen zu 100% ausschließen!

[SimonX]

@Berni,

Das hatte ich schon befürchtet. Ich hatte über Hash-Funktionen nachgedacht um jede Message auf ein Bit zu reduzieren. Die Hash-Funktion hätte dann so 37 bits liefern müssen, die kollisionsfrei sein müssten, damit 16GiB ausreichen.

Die Wahrscheinlichkeit von False-Duplicates ist aber auch bei 256 bits gegeben. Ich denke jetzt über eine kontextsensitive Kompression nach um die Message-Id klein zu halten.

Danke für eure Antworten.

[Berni]

Ich hatte über Hash-Funktionen nachgedacht um jede Message auf ein Bit zu reduzieren.
Ein 1-Bit-Hash? Hmm ;)
Wenn das ne Datenbank werden sollte könnte man möglicherweise auch numerische IDs hochzählend vergeben und die eigentlichen Werte als Fremdschlüssel oder nicht indiziertes Feld vergeben. Oder man könnte einen "Quickcheck" gegen einen sehr kurzen Hash machen und dann die verbliebenen Werte im Klartext durchsehen (SQL-Datenbanken bieten das in gewisser Form auch schon integriert in Form von Partitionierung).
Mit Komprimierung wirst du wohl eigene Sachen bauen müssen. Ich hab mal gzip und deflate getestet und das erzeugt bei der kurzen Länge eher eine Verlängerung des Strings als eine Verkürzung. Evtl. bietet die Datenbank hier Funktionen oder das Dateisystem kann effizienter komprimieren weil dieses ja einen größeren zusammenhängenden Block mit Text sieht. Auch eine Huffman-Codierung (oder auch LZW) könnten in Frage kommen, insbesondere wenn der Zeichenumfang sehr eingeschränkt ist könnte auch ein eigenes Datenformat für die Buchstaben (also anstatt ASCII direkt Bits in eigenem Format speichern!) was bringen.

Es kommt halt aufs Anwendungsgebiet drauf an (also welche Abfragen und Anforderungen genau bestehen) aber das ist uns nicht bekannt. Daswäre dann auch eher was für das "Programmieren"-Forum als Krypto wenn du hier noch weiter Fragen hast...

[SimonX]

Ein 1-Bit-Hash? Hmm ;)
Das geht schon, man hätte ja 128 milliarden bits = 16GiB. Ohne Kollisionen könnte man ja direkt sehen ob eine Message schon da war oder nicht.

[Berni]

1-Bit-Hash würde heißen, dass dieser als Ausgabe entweder "0" oder "1" hat ;) Wie du auf 128 Milliarden Bits kommst ist mir ein Rätsel.

[Nasenbaer]

1-Bit-Hash würde heißen, dass dieser als Ausgabe entweder "0" oder "1" hat ;) Wie du auf 128 Milliarden Bits kommst ist mir ein Rätsel.
Ich weiß auch nicht wie er darauf kommt aber er sagte was von 37 Bit und 2^37 = 16GiB. Wieso man allerdings 20 Mrd. Messages auf eine Menge von 137 Mrd. Schlüsseln abbilden will ist mir auch schleierhaft.

Es ist wohl so, dass ab einer Belegung von 90% einer Hashtabelle die Warscheinlichkeit für Kollisionen in einer Hashtabelle enorm zunimmt.
Also wenn man eine Hashfunktion geschickt wählt und dann die Größe so anpasst, dass man die Tabelle zu 50% füllt also ca. 40 Mrd. Hashwerte bilden kann, dann bräuchte man 35 Bit lange Hashwerte (2^35 sind ungefähr 35 Mrd.).

Aber finde mal eine Hashfunktion, die wohl sehr ähnliche Messages so chaotisch streut, dass du keine Kollision erhälst.


Und nochmal zum Verständnis: Sinn einer Hashfunktion ist es eine Menge von Werten auf eine möglichst deutlich kleinere Menge von Schlüsseln (den Hashwerten) abzubilden.
Wenn du dann 20 Mrd. unterschiedlicher Werte auf Werte mit der Länge von 1 Bit abbilden willst, sprich auf die Menge {0,1}, dann haste du ab der 3. Message eine Kollision mit 100% Wahrscheinlichkeit - clever ist was anderes. :D

[The Cell]

Dass beim Hashing die Injektivität ein Problem ist, wurde ja hier hinreichend oft erwähnt. Hier der Hinweis zum Thema "Perfektes hashing"

"Sei N eine Primzahl und S Teilmenge von U = [0…N-1] mit |S| = n.
Für S kann eine perfekte Hash-Tafel der Größe O(n) und eine
Hash-Funktion mit Zugriffszeit O(1) in erwarteter Zeit O(n)
aufgebaut werden."

Gruß,
TC