Schnelle Hash-Funktion mit Kollisionsmöglichkeit in der Nähe von SHA-1

Question

Ich verwende SHA-1, um Duplikate in einem Programm zu erkennen, das Dateien verarbeitet. Es muss nicht kryptographisch stark sein und kann reversibel sein. Ich fand diese Liste der schnellen Hash-Funktionen https://code.google.com/p/xxhash/

Was wähle ich, wenn ich eine schnellere Funktion und Kollision auf Zufallsdaten in der Nähe von SHA-1 möchte?

Vielleicht ist ein 128-Bit-Hash für die Datendeduplizierung gut genug? (vs 160 bit sha-1)

In meinem Programm wird der Hash auf Chuncks von 0 - 512 KB berechnet.

Answer 1

Vielleicht wird Ihnen helfen: https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

Kollisionen selten: FNV-1, FNV-1a, DJB2, DJB2a, SDBM & MurmurHash

Ich weiß nicht, über xxHash aber es sieht auch vielversprechend aus.

MurmurHash ist sehr schnell und Version 3 unterstützt 128bit Länge, würde ich diese wählen. (Implementiert in Java und Scala.)

Answer 2

Google entwickelt und verwendet (glaube ich) FarmHash für leistungskritisches Hashing. Vom project page:

ist FarmHash ein Nachfolger CityHash und enthält viele der gleichen Tricks und Techniken, einige von ihnen aus Austin Appleby MurmurHash genommen.

...

Auf CPUs mit allen notwendigen Maschinenbefehle, etwa sechs verschiedene Hash-Funktionen können zu FarmHash Lineup beitragen. In einigen Fällen haben wir gegenüber CityHash erhebliche Leistungssteigerungen erzielt, indem wir neuere Anweisungen verwendet haben, die jetzt allgemein verfügbar sind. Wir haben aber auch etwas mehr Geschwindigkeit auf andere Weise verdrängt, so dass die meisten Programme, die CityHash verwenden, beim Umschalten auf FarmHash mindestens ein bisschen mehr gewinnen sollten.

(CityHash war bereits eine leistungsoptimierte Hash-Funktion Familie von Google.)

vor einem Jahr veröffentlicht wurde, an welcher Stelle es an Sicherheit grenzender Wahrscheinlichkeit der Stand der Technik, zumindest unter dem veröffentlichten Algorithmen. (Sonst hätte Google etwas Besseres benutzt.) Es besteht eine gute Chance, dass es immer noch die beste Option ist.

Answer 3

Die Fakten:

1. gute Hash-Funktionen, speziell die Verschlüsselungs diejenigen (wie SHA-1), erfordern erhebliche CPU-Zeit, weil sie eine Reihe von Eigenschaften zu ehren, die gewohnt sehr nützlich sein für Sie in diesem Fall;
2. Jede Hash-Funktion gibt Ihnen nur eine Sicherheit: Wenn die Hash-Werte von zwei Dateien unterschiedlich sind, sind die Dateien sicherlich unterschiedlich. Wenn jedoch ihre Hash-Werte gleich sind, besteht die Möglichkeit, dass die Dateien auch gleich sind, aber die einzige Möglichkeit, sicher zu sagen, ob diese "Gleichheit" nicht nur eine Hash-Kollision ist, besteht darin, auf einen binären Vergleich der beiden zurückzugreifen Dateien.

Fazit:
In Ihrem Fall ich einen viel schnelleren Algorithmus wie CRC32 versuchen würde, die so ziemlich alle Eigenschaften, die Sie brauchen, und würde der Umgang mit mehr als 99,9% der Fälle fähig sein und nur auf eine langsamere Vergleichsmethode zurückgreifen (wie Binärvergleich), um die Falschpositiven auszuschließen. In der großen Mehrheit der Vergleiche würde es viel schneller sein, würde es wahrscheinlich kompensieren, dass es keine "ehrfurchtgebietende" Gleichförmigkeit (möglicherweise einige weitere Kollisionen) aufweist.

Answer 4

128 Bits sind in der Tat gut genug, um verschiedene Dateien oder Chunks zu erkennen. Das Risiko einer Kollision ist infinitesimal, zumindest solange keine beabsichtigte Kollision versucht wird.

64 Bits können auch gut genug sein, wenn die Anzahl der Dateien oder Chunks, die Sie verfolgen möchten, "klein genug" bleibt (d. H. Nicht mehr als ein paar Millionen).

Sobald die Größe des Hashes festgelegt ist, benötigen Sie einen Hash mit einigen sehr guten Verteilungseigenschaften, wie z. B. den mit Q.Score = 10 in Ihrem Link aufgeführten.

Answer 5

Da die einzige relevante Eigenschaft von Hash-Algorithmen in Ihrem Fall die Kollisionswahrscheinlichkeit ist, sollten Sie sie schätzen und den schnellsten Algorithmus wählen, der Ihre Anforderungen erfüllt.

Wenn wir annehmen, Ihr Algorithmus absolute Gleichmäßigkeit hat, ist die Wahrscheinlichkeit einer Hash-Kollision zwischen n Dateien Hashes mit d möglichen Werte werden mit:

Zum Beispiel, wenn Sie benötigen Bei einer Kollisionswahrscheinlichkeit von weniger als einer Million unter einer Million Dateien müssen Sie mehr als 5 * 10^17 unterschiedliche Hashwerte haben, was bedeutet, dass Ihre Hashes mindestens 59 Bit haben müssen. Lassen Sie uns auf 64 Punkte eingehen, um eine mögliche schlechte Uniformität zu erklären.

Also ich würde sagen, jede anständige 64-Bit-Hash sollte für Sie ausreichend sein. Längere Hashes werden die Kollisionswahrscheinlichkeit weiter reduzieren, und zwar zu einem Preis mit höherer Rechenleistung und erhöhtem Hash-Speichervolumen. Bei kürzeren Caches wie CRC32 müssen Sie einen expliziten Kollisionsverarbeitungscode schreiben.

Answer 6

Es hängt davon ab, wie viele Hashes Sie in einer Iteration über berechnen werden. ZB 64bit Hash erreicht eine Kollisionswahrscheinlichkeit von 1 in 1000000 mit 6 Millionen Hashes berechnet.

Siehe auch: Hash collision probabilities