Was ist eine gute Hash-function?

Was ist eine gute Hash-function? Ich habe eine Menge Hash-functionen und Anwendungen in meinen Datenstruktur-Kursen in der Universität gesehen, aber ich habe meistens festgestellt, dass es ziemlich schwer ist, eine gute Hash-function zu erstellen. Als Faustregel, um Kollisionen zu vermeiden, sagte mein Professor:

function Hash(key) return key mod PrimeNumber end 

(mod ist der% Operator in C und ähnlichen Sprachen)

mit der Primzahl, um die Größe der Hash-Tabelle zu sein. Ich verstehe, dass das eine gute function ist, um Kollisionen zu vermeiden, und eine schnelle, aber wie kann ich eine bessere machen? Gibt es bessere Hash-functionen für Zeichenfolgenschlüssel gegen numerische Schlüssel?

Solutions Collecting From Web of "Was ist eine gute Hash-function?"

Für “normale” Hashtabellen-Lookups auf praktisch jeder Art von Daten – dieser von Paul Hsieh ist der beste, den ich je benutzt habe.

http://www.azillionmonkeys.com/qed/hash.html

Wenn Sie kryptografisch sicher sind oder etwas anderes fortgeschrittener, dann YMMV. Wenn Sie nur eine allgemeine Hash-function für Hash-Tabellen suchen möchten, dann ist dies genau das, was Sie suchen.

Es gibt keine “gute Hash-function” für universelle Hashes (ed. Ja, ich weiß, es gibt so etwas wie “universelles Hashing”, aber das ist nicht, was ich meinte). Je nach Kontext bestimmen unterschiedliche Kriterien die Qualität eines Hashes. Zwei Leute haben SHA bereits erwähnt. Dies ist ein kryptografischer Hash und es ist überhaupt nicht gut für Hash-Tabellen, die Sie wahrscheinlich meinen.

Hash-Tabellen haben sehr unterschiedliche Anforderungen. Dennoch ist es schwierig, eine gute Hash-function universell zu finden, da verschiedene Datentypen unterschiedliche Informationen verfügbar machen, die gehackt werden können. Als Faustregel gilt, dass alle Informationen, die ein Typ enthält, gleichermaßen berücksichtigt werden. Dies ist nicht immer einfach oder sogar möglich. Aus Gründen der Statistik (und damit der Kollision) ist es auch wichtig, eine gute Verteilung über den Problemraum, dh alle möglichen Objekte, zu erzeugen. Das bedeutet, dass es beim Hashing von Zahlen zwischen 100 und 1050 nicht sinnvoll ist, die höchstwertige Ziffer im Hash zu verwenden, da für ~ 90% der Objekte diese Ziffer 0 ist. Es ist viel wichtiger, die letzten drei zu lassen Ziffern bestimmen den Hash.

Ebenso ist es beim Hashing von Strings wichtig, alle Zeichen zu berücksichtigen – es sei denn, es ist im Voraus bekannt, dass die ersten drei Zeichen aller Strings identisch sind. Diese zu betrachten, ist eine Verschwendung.

Dies ist tatsächlich einer der Fälle, in denen ich rate, zu lesen, was Knuth in der Kunst der Computerprogrammierung zu sagen hat. 3. Eine weitere gute Lektüre ist Julienne Walker The Art of Hashing .

Es gibt zwei Hauptzwecke von Hash-functionen:

  • Datenpunkte gleichmäßig in n Bits zu verteilen.
  • um die Eingabedaten sicher zu identifizieren.

Es ist unmöglich, einen Hash zu empfehlen, ohne zu wissen, wofür Sie ihn verwenden.

Wenn Sie nur eine Hash-Tabelle in einem Programm erstellen, brauchen Sie sich keine Gedanken darüber zu machen, wie reversibel oder hackbar der Algorithmus ist … SHA-1 oder AES ist dafür völlig überflüssig, Sie sollten besser damit umgehen eine Variation von FNV . FNV erzielt eine bessere Dispersion (und somit weniger Kollisionen) als ein einfacher Prime-Mod, wie Sie es bereits erwähnt haben, und er ist anpassbarer an unterschiedliche Eingangsgrößen.

Wenn Sie die Hashes verwenden, um öffentliche Informationen zu verbergen und zu authentifizieren (z. B. ein Passwort oder ein Dokument zu hashen), sollten Sie einen der wichtigsten Hash-Algorithmen verwenden, die von der Öffentlichkeit überprüft werden. Die Hash Function Lounge ist ein guter Ausgangspunkt.

Dies ist ein Beispiel für ein gutes Beispiel und auch ein Beispiel dafür, warum Sie niemals eines schreiben möchten. Es ist ein Fowler / Noll / Vo (FNV) Hash, der zu gleichen Teilen Computer Science Genie und reinem Voodoo ist:

 unsigned fnv_hash_1a_32 ( void *key, int len ) { unsigned char *p = key; unsigned h = 0x811c9dc5; int i; for ( i = 0; i < len; i++ ) h = ( h ^ p[i] ) * 0x01000193; return h; } unsigned long long fnv_hash_1a_64 ( void *key, int len ) { unsigned char *p = key; unsigned long long h = 0xcbf29ce484222325ULL; int i; for ( i = 0; i < len; i++ ) h = ( h ^ p[i] ) * 0x100000001b3ULL; return h; } 

Bearbeiten:

  • Landon Curt Noll empfiehlt auf seiner Seite den FVN-1A-Algorithmus gegenüber dem ursprünglichen FVN-1-Algorithmus: Der verbesserte Algorithmus zerstreut besser das letzte Byte im Hash. Ich habe den Algorithmus entsprechend angepasst.

Ich würde sagen, dass die Hauptregel nicht darin besteht, eigene zu rollen. Versuchen Sie, etwas zu verwenden, das gründlich getestet wurde, z. B. SHA-1 oder etwas Ähnliches.

Eine gute Hash-function hat folgende Eigenschaften:

  1. Bei einem Hash einer Nachricht ist es für einen Angreifer rechnerisch unmöglich, eine andere Nachricht zu finden, so dass ihre Hashes identisch sind.

  2. Mit einem Nachrichtenpaar, m ‘und m, ist es rechnerisch unmöglich, zwei solche zu finden, dass h (m) = h (m’)

Die beiden Fälle sind nicht gleich. Im ersten Fall gibt es einen bereits vorhandenen Hash, für den Sie eine Kollision suchen. Im zweiten Fall versuchen Sie zwei beliebige Nachrichten zu finden, die kollidieren. Die zweite Aufgabe ist aufgrund des Geburtstagsparadoxons wesentlich einfacher.

Wenn performance nicht so ein großes Problem ist, sollten Sie immer eine sichere Hash-function verwenden. Es gibt sehr clevere Angriffe, die durch Erzwingen von Kollisionen in einem Hash ausgeführt werden können. Wenn Sie von Anfang an etwas Starkes verwenden, werden Sie sich gegen diese sichern.

Verwenden Sie MD5 oder SHA-1 nicht in neuen Designs. Die meisten Kryptographen, inklusive mir, würden sie als kaputt ansehen. Die Hauptursache für die Schwäche in diesen beiden Entwürfen ist, dass die zweite Eigenschaft, die ich oben skizziert habe, für diese Konstruktionen nicht gilt. Wenn ein Angreifer zwei Nachrichten generieren kann, m und m ‘, die beide auf denselben Wert hashen, können sie diese Nachrichten gegen Sie verwenden. SHA-1 und MD5 leiden außerdem unter Nachrichtenerweiterungsangriffen, die Ihre Anwendung tödlich schwächen können, wenn Sie nicht vorsichtig sind.

Ein modernerer Hash wie Whirpool ist eine bessere Wahl. Es leidet nicht unter diesen Nachrichtenerweiterungsangriffen und verwendet die gleiche Mathematik, die AES verwendet, um Sicherheit gegen eine Vielzahl von Angriffen zu beweisen.

Ich hoffe, das hilft!

Was Sie hier sagen, ist, dass Sie eine verwenden möchten, die Kollisionsresistenz hat. Versuchen Sie es mit SHA-2. Oder versuchen Sie es mit einer (guten) Blockchiffre in einer einseitigen Kompressionsfunktion (noch nie zuvor versucht), wie AES im Miyaguchi-Modus. Das Problem damit ist, dass Sie:

1) habe eine IV. Versuchen Sie, die ersten 256 Bits der Bruchteile von Khinchins Konstante oder etwas ähnliches zu verwenden. 2) habe ein Padding-Schema. Einfach. Heben Sie es von einem Hash wie MD5 oder SHA-3 (Keccak [ausgesprochen ‘Ket-Chak’]). Wenn Sie sich nicht um die Sicherheit kümmern (ein paar andere sagten das), schauen Sie sich FNV oder lookup2 von Bob Jenkins an (eigentlich bin ich der erste, der lookup2 empfiehlt) Versuchen Sie auch MurmurHash, es ist schnell (überprüfen Sie dies: .16 cpb ).