algorithm - zurückrechnen - preimage resistance




Was ist eine gute Hash-Funktion? (5)

Was ist eine gute Hash-Funktion? Ich habe eine Menge Hash-Funktionen und Anwendungen in meinen Datenstruktur-Kursen in der Universität gesehen, aber ich habe meistens festgestellt, dass es ziemlich schwer ist, eine gute Hash-Funktion 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 Funktion ist, um Kollisionen zu vermeiden, und eine schnelle, aber wie kann ich eine bessere machen? Gibt es bessere Hash-Funktionen für Zeichenfolgenschlüssel gegen numerische Schlüssel?


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.

Eine gute Hash-Funktion 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 Leistung nicht so ein großes Problem ist, sollten Sie immer eine sichere Hash-Funktion 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!


Es gibt zwei Hauptzwecke von Hash-Funktionen:

  • 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.


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-Funktion für Hash-Tabellen suchen möchten, dann ist dies genau das, was Sie suchen.


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 ).





hash