Automatisierte Suche nach Integer-Hash-Funktionen

 (github.com/skeeto)
3 Punkte von GN⁺ 2024-05-06 | 1 Kommentare | Auf WhatsApp teilen

Hash Function Prospector

Dieses Tool ist ein kleines Werkzeug zur automatisierten Suche nach Integer-Hash-Funktionen. Es wählt zufällig aus neun invertierbaren Operationen aus und erzeugt dadurch Milliarden von Integer-Hash-Funktionen. Die generierten Funktionen werden JIT-kompiliert, und deren Avalanche-Verhalten wird bewertet. Die aktuell beste Funktion wird in C-Syntax ausgegeben.

  • Avalanche-Score: die Anzahl der Ausgabebits, die im Durchschnitt stabil bleiben, wenn ein einzelnes Eingabebit invertiert wird. Ein niedrigerer Score ist besser. Idealerweise ist der Score 0. Das heißt, wenn ein einzelnes Eingabebit invertiert wird, werden alle Ausgabebits mit 50 % Wahrscheinlichkeit invertiert.
  • Prospector kann 32-Bit- und 64-Bit-Integer-Hash-Funktionen erzeugen. Alle Optionen sind in der Hilfe (-h) beschrieben. Aufgrund des JIT-Compilers werden nur x86-64 unterstützt, die gefundenen Funktionen lassen sich aber überall einsetzen.

Gefundene Hash-Funktionen

Prospector und die dort verfügbaren Hilfsprogramme haben zwei nützliche Klassen von Hash-Funktionen entdeckt. Beide verwenden eine xorshift-multiply-xorshift-Struktur, unterscheiden sich aber in der Rundenzahl.

2-Runden-Funktionen

TheIronBorn hat eine kombinatorische Optimierung verwendet, um die besten bekannten Parameter für diese Struktur zu finden.

  • Diese 32-Bit-2-Runden-Permutation hat insbesondere einen besonders geringen Bias und schlägt den bekannten MurmurHash3-32-Bit-Finalizer mit kleinem Vorsprung.
  • Die Struktur der Hash-Funktion wurde von Prospector entdeckt, die Parameter wurden mit Hill Climbing und genetischen Algorithmen abgestimmt.

Es gibt weitere 2-Runden-Konstanten mit niedrigerem Bias; einige davon sind besser als lowbias32.

3-Runden-Funktionen

Fügt man in dieser Struktur eine weitere multiply-xorshift-Runde hinzu, kann man bei sorgfältig gewählten Parametern die theoretische Bias-Grenze erreichen. Beispielsweise ist diese Hash-Funktion nicht von einer perfekten PRF zu unterscheiden.

  • triple32 behebt nicht nur das Problem hash(0) = 0, sondern reduziert auch den Bias weiter.
  • Es gibt weitere 3-Runden-Konstanten mit niedrigerem Bias.

Exakte Bias-Bewertung

Der -E-Modus bewertet den Bias der angegebenen Hash-Funktion (-p oder -l). Standardmäßig nutzt Prospector eine Schätzung, um den Bias der Funktion schnell zu bewerten; diese ist jedoch nicht deterministisch und enthält viel Rauschen. Für eine exakte und erschöpfende Messung des Bias verwenden Sie bitte die Option -e.

  • Mit -p und einem Pattern oder mit einer Shared Library, die eine Funktion hash() enthält, sowie mit -l, können Sie die zu prüfende Funktion festlegen.
  • Für eine präzise, erschöpfende Prüfung von 64-Bit-Hashes gibt es keinen Test, da dieser zu lange dauern würde.

Auswahl invertierbarer Operationen

Verwendet werden folgende invertierbare Operationen:

  • x = ~x;
  • x ^= constant;
  • x *= constant | 1; (nur ungerade Konstanten)
  • x += constant;
  • x ^= x >> constant;
  • x ^= x << constant;
  • x += x << constant;
  • x -= x << constant;
  • x <<<= constant; (Linksrotation)
  • x = bswap(x) (Austausch von High- und Low-Byte)

Technisch gesehen ist x = ~x durch x ^= constant abgedeckt. Dennoch ist ~x als Sonderfall einzigartig und besonders nützlich.

16-Bit-Hashes

Für 16-Bit-Hashes gibt es aufgrund abweichender Randbedingungen ein separates Tool namens hp16.

  • Anders als beim 32-/64-Bit-Prospector ist diese Implementierung vollständig portabel und läuft auf fast jedem System.
  • Die Erstellung und Bewertung von 128 KiB-S-boxen ist ebenfalls möglich.
  • Da 16-Bit-Hashes auf Maschinen ohne schnellen Multiplikationsbefehl besonders nützlich sein könnten, kann während der Suche auf bestimmte Operationen verzichtet werden (-m, -r).

Einige interessante Ergebnisse:

  • 2-Runden-xorshift-multiply-Hash
  • 3-Runden-xorshift-multiply-Hash
  • Multiplikationsfreie Hashes (nur xorshift-add)

Eine gute 3-Runden-xorshift-Hashfunktion (kurze Suche mit hp16 -Xn3) kommt einer guten S-box (hp16 -S) nahe.

Bei 16-Bit-Operationen sollte man die Integer-Promotion-Regeln von C beachten. Das im Programm ausgegebene C-Programm achtet darauf, 16-Bit-Operationen bei Bedarf auf unsigned int zu promoten.

GN⁺-Kommentar

  • Die Sicherheit von Hash-Funktionen spielt sowohl in der Kryptografie als auch in der Computersicherheit eine große Rolle, daher könnte ein solches Suchwerkzeug der Forschung sehr hilfreich sein. Besonders interessant ist, dass es durch zufällige Explorationen Hash-Funktionen mit niedrigem Bias findet.

  • Allerdings ist die Sicherheit einer Hash-Funktion nicht allein durch statistische Eigenschaften garantiert. Kryptografische Hash-Funktionen müssen außerdem gegen Pre-image-, second pre-image- und Kollisionangriffe robust sein, sodass dafür weitere Analysen nötig sind.

  • 16-Bit-Hash-Funktionen dürften in eingeschränkten Umgebungen wie IoT- oder Embedded-Systemen nützlich sein. Beeindruckend ist es, dass auf CPUs ohne Multiplikationsbefehl Hashes allein mit ADD/XOR/SHIFT möglich sind.

  • Die Anwendung heuristischer Suchverfahren wie Hill Climbing oder genetischer Algorithmen bei der Hash-Entwicklung ist ebenfalls eine frische Idee. Da KI-Technik zunehmend in die Kryptografie einfließt, könnten solche Optimierungstechniken künftig eine noch wichtigere Rolle spielen.

  • Dennoch ist es wegen der Grenzen von Hash-Funktionen nicht möglich, gute Avalanche-Eigenschaften automatisch als kryptografische Sicherheit zu interpretieren; das ist offenbar eine Grenze dieses Projekts. Dennoch kann dieses Tool dabei helfen, bestehende Hash-Funktionen zu analysieren und zu verbessern.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-06
Hacker-News-Kommentar
  • Gründe, warum ihm der Code dieses Entwicklers gefällt
    • JSON-Bibliothek, Options-Parsing-Bibliothek, branchfreier UTF-8-Decodierer, lock-free Stack und Trie-Bibliothek werden erwähnt.
    • Die Tatsache, dass diese Bibliotheken alle unter der Unlicense veröffentlicht sind, gefällt ihm ebenfalls.
  • Kommentar des MurmurHash-Entwicklers
    • Er fand es interessant, dass die multiply-shift-xor-Operation lange zuverlässig funktioniert hat.
  • Gedanken zur automatisierten Suche nach Hash-Funktionen
    • Es wäre sinnvoll, die Ausgabe automatisch mit SMHasher3 zu bewerten.
      • Für die Geschwindigkeit könnten nur einige Tests verwendet werden, um schnell fehlschlagen zu können.
    • Eine Erweiterung auf 64- und 128-Bit-Hashes wäre ebenfalls sinnvoll (obwohl der Suchraum größer ist).
    • In der Rain-Bibliothek wurde Node.js-Code erstellt, um den Avalanche-Effekt bei der Multiplikation mit einer 64-Bit-Primzahl zu messen.
  • Teilt die Erfahrung, 1brc in Go umgesetzt zu haben
    • Er versuchte, eine maßgeschneiderte perfekte Hash-Funktion zu finden, die jede Station ohne Kollision in einen eigenen Bucket platziert, gab es aber auf, da die Regel vorschreibt, dass die Hash-Funktion vor dem Programmstart nicht an die Daten angepasst werden darf.
    • Er erstellte ein Testwerkzeug, das Zufallskonstanten testet und auf Basis der Anzahl kollidierender Buckets und Kollisionen die bisher beste Konstante ausgibt.
      • Bei einer Auslastung von etwa 40 % konnte er auf nur einen Bucket mit nur 2 kollidierenden Werten reduzieren.
      • Er fand es interessant, dass ähnliche Werte für die Anzahl der Verschiebungspositionen unabhängig von anderen Konstanten in der besten Performance-Konstante auftauchten.
  • Bitte um Erklärung, warum dieser Code spannend ist und wofür er verwendet werden kann
  • Nachfrage, was der Code genau macht, ob er die beste Hash-Funktion findet, und falls nicht, warum sich die beste Hash-Funktion bei jedem Lauf verändert.
  • Nachfrage nach dem Mechanismus, der gute Hash-Funktionen für einen bestimmten Bereich von Ganzzahlen findet
    • Zum Beispiel wenn man Werte zwischen 10.000 und 200.000 kennt und diese in eine optimale Anzahl von Hash-Buckets hashen möchte.
  • Es wurde angemerkt, dass es zwar mathematisch Vorteile hat, Operationen auf reversible Vorgänge zu beschränken, aber viele Möglichkeiten auszuschließen.
    • Sie dachten über perfektes Hashing nach, wenn die Eingabemenge im Voraus bekannt ist.
    • Normalerweise werden normalerweise Konstanten-Arrays verwendet, aber wenn die Eingabe bereits kleine Integer sind, wollten sie wissen, ob man sie weiter komprimieren kann.
    • Etwa 100 Basisoperationen wurden aufgeschrieben, aber nach einer gewissen Zeit wurde es zu langweilig, das Projekt weiterzuverfolgen.
  • Die Nutzung derselben Konstanten für beide Multiplikationen wurde erwähnt, da sich dadurch der Code verkleinern und die Berechnung etwas schneller werden könnte.
  • Obwohl anerkannt wird, dass diese Funktionen für kryptografische Vorgänge ungeeignet sind, wird gefragt, welchen Einfluss der gemessene "Bias" auf die Kryptoanalyse hat
    • Er war neugierig, ob jemand, der mit differentieller Kryptographie vertraut ist, das erklären kann.
    • Er war neugierig, ob ein niedriger Bias in einer Hash-Funktion einen Kryptoangriff mit weniger Runden oder Berechnungen vereiteln könnte.
    • Er war neugierig, ob dieses Tool dabei helfen könne, bessere kryptografische Hash-Funktionen zu finden.
  • Ähnliches Projekt vorgestellt
    • Die Qualität der Funktion ist besser, aber es ist langsamer (da ein Interpreter verwendet wird)
    • Dennoch wurde keine Funktion gefunden, die besser ist als bestehende Hash-Funktionen