Ich hashe eine große Anzahl von Dateien, und um Hash-Kollisionen zu vermeiden, speichere ich auch die Originalgröße einer Datei - auf diese Weise ist es selbst bei einer Hash-Kollision äußerst unwahrscheinlich, dass die Dateigrößen ebenfalls identisch sind . Ist dieser Ton (eine Hash-Kollision ist gleichermaßen wahrscheinlich von beliebiger Größe), oder brauche ich eine andere Information (wenn eine Kollision wahrscheinlich auch die gleiche Länge wie das Original hat).
Oder allgemeiner: Ist es so wahrscheinlich, dass jede Datei unabhängig von der ursprünglichen Dateigröße einen bestimmten Hashwert erzeugt?
Hängt von Ihrer Hash-Funktion ab, aber im Allgemeinen haben Dateien mit derselben Größe, aber unterschiedlichen Inhalten weniger wahrscheinlich denselben Hashwert wie Dateien mit unterschiedlicher Größe. Dennoch wäre es wahrscheinlich sauberer, einen einfach getesteten Hash mit größerem Speicherplatz zu verwenden (z. B. MD5 statt CRC32 oder SHA1 anstelle von MD5), als auf eigene Lösungen wie die Speicherung der Dateigröße zu wetten.
Hash-Funktionen werden im Allgemeinen geschrieben, um die Daten gleichmäßig über alle Ergebnisbereiche zu verteilen.
Wenn Sie davon ausgehen, dass Ihre Dateien gleichmäßig über einen festen Bereich verfügbarer Größen verteilt sind, können wir sagen, dass es nur 1024 (2 ^ 10) gleichmäßig verteilte unterschiedliche Größen für Ihre Dateien gibt. Das Speichern der Dateigröße reduziert bestenfalls die Wahrscheinlichkeit einer Kollision um die Anzahl der unterschiedlichen Dateigrößen.
Hinweis: Wir könnten davon ausgehen, dass es 2 ^ 32 gleichmäßig verteilte und unterschiedliche Größen gibt und es den Rest der Mathematik immer noch nicht ändert.
Es wird allgemein akzeptiert, dass die allgemeine Wahrscheinlichkeit einer Kollision auf MD5 (zum Beispiel) 1/(2^128) ist.
Es sei denn, es gibt etwas, das speziell in eine Hash-Funktion eingebaut ist, die etwas anderes sagt. Gegeben sei eine gültige X , so dass die Wahrscheinlichkeit von P(MD5(X) == MD5(X+1)) gleich bleibt wie zwei zufällige Werte { Y , Z } Das heißt, dass P(MD5(Y) == MD5(Z)) = P(MD5(X) == MD5(X+1)) = 1/(2^128) für alle Werte von X , Y und Z .
Wenn Sie dies mit den 2 ^ 10 unterschiedlichen Dateien kombinieren, bedeutet das, dass Sie durch Speichern der Dateigröße maximal 10 Bits erhalten, die anzeigen, ob die Elemente unterschiedlich sind oder nicht (auch hier wird davon ausgegangen, dass Ihre Dateien gleichmäßig verteilt sind) .
Also fügen Sie im besten Fall noch weitere N Byte Speicher für eindeutige Werte von Kurz gesagt, wenn MD5 nicht gut genug für Kollisionen ist, verwenden Sie einen stärkeren Hash, wenn die stärkeren Hashes zu langsam sind, dann verwenden Sie einen schnellen Hash mit geringer Wahrscheinlichkeit von Kollisionen wie MD5 und Verwenden Sie dann einen langsameren Hash wie SHA-1 oder SHA256, um die Wahrscheinlichkeit einer Kollision zu verringern, aber wenn SHA256 schnell genug ist und der doppelte Speicherplatz kein Problem darstellt, sollten Sie wahrscheinlich SHA256 verwenden.
Die Größe des Hash ist unabhängig von der Größe der Originaldaten gleich. Da es nur eine begrenzte Anzahl möglicher Hashes gibt, ist es theoretisch möglich, dass zwei Dateien mit unterschiedlichen Größen denselben Hashwert haben. Allerdings bedeutet dies, dass es auch möglich ist, dass zwei Dateien mit der selben Größe den gleichen Hashwert haben.
Hash-Funktionen sind so konzipiert, dass es sehr schwierig ist, die Kollision zu bekommen, sonst sind sie nicht effektiv
Wenn Sie eine Hash-Kollision haben, die absolut unglaublich ist etwa 1: number_of_possible_hashs Wahrscheinlichkeit, die nichts über die Dateigröße sagt.
Wenn Sie wirklich sicher sein wollen, dass Hash-Kollisionen auftreten, können Sie zwei verschiedene Hashes für die gleiche Datei berechnen - es ist weniger fehleranfällig als das Speichern von Hash + Dateigröße.
Der ganze Sinn der Familie der kryptografischen Hashes (MD5, SHA-x, usw.) liegt darin, Kollisionen verschwindend gering zu machen. Die Vorstellung ist, dass die offiziellen rechtlichen Prozesse darauf vorbereitet sind, dass es unpraktisch ist, eine Kollision absichtlich zu produzieren. Also, wirklich, es ist eine schlechte Nutzung von Speicherplatz und CPU-Zeit, um den Hosenträgern dieser Hashes einen Gürtel hinzuzufügen.
Tags und Links hash hash-collision hash-code-uniqueness