Fast die schnellste tragbare 64-Bit-Hash-Funktion mit anständiger Qualität.
Dies ist eine Übersetzung des Originalartikels von Leonid Yuriev .
Anstelle eines HaftungsausschlussesIch werde die Definition von Hash-Funktionen zusammen mit der detaillierten Auflistung der Eigenschaften und Anforderungen für ihre kryptografische Anwendung weglassen und davon ausgehen, dass der Leser entweder über die erforderlichen Mindestkenntnisse verfügt oder diese nachlesen wird . Es sollte auch beachtet werden, dass ich im Folgenden über nicht-kryptografische (nicht für die Kryptografie geeignete) Hash-Funktionen sprechen werde, sofern nicht ausdrücklich anders angegeben.
BanalitätenHashing wird in vielen Algorithmen verwendet, und fast immer ist die effizienteste (schnelle) Datenverarbeitung erforderlich, zusammen mit einem bestimmten Mindestmaß an Hashing-Qualität. Hier bedeutet der Begriff „Qualität“ zunächst eine Art „Zufälligkeit“ (Stochastizität) in Bezug auf die Ausgangsdaten. Etwas seltener werden zusätzliche Anforderungen gestellt, wie z. B. Widerstand gegen absichtliche Kollisionserzeugung oder Irreversibilität.
Ein bisschen langweiliger seinAus Gründen der Klarheit ist es notwendig, das Konzept der „Qualität“ der Hash-Funktion und den Rest der Anforderungen etwas detaillierter zu definieren:
Basisqualität und Lawineneffekt : Durch Ändern eines oder mehrerer beliebiger Bits in einem beliebigen Satz von Quelldaten ändert sich jedes Bit des Ergebnisses mit einer Wahrscheinlichkeit von ½.
- Irreversibilität oder erster Vorbildwiderstand: Die Unmöglichkeit, die Originaldaten oder einzelnen Bits aus dem Hash-Ergebnis zu erhalten.
- Widerstand gegen Kollisionen erster Ordnung und / oder Widerstand vor dem zweiten Bild: die Schwierigkeit, den Originaldatensatz zu finden / anzupassen, um ein bestimmtes Ergebnis oder einen Teil davon zu erhalten, auch wenn der ursprüngliche Datensatz bekannt ist.
- Widerstand gegen Kollisionen zweiter Ordnung: Die Schwierigkeit, zwei verschiedene Datensätze zu finden / anzupassen, die das gleiche Ergebnis oder eine Übereinstimmung eines signifikanten Teils ergeben würden.
Ohne lange Zitate der zugrunde liegenden Mathematik kann Folgendes zusammengefasst werden:
- Das Erfüllen aller oben genannten Anforderungen bei gleichzeitiger Gewährleistung einer hohen Leistung ist ein ziemlich schwieriges Problem, dessen Lösung uns eine gute kryptografische Hash-Funktion geben würde. Aber wir werden das noch nicht tun.
- Die Bereitstellung der Grundqualität erfordert eine ausreichend große Anzahl von ALU-Operationen. Einfach ausgedrückt, Qualität geht immer Kompromisse mit der Geschwindigkeit ein.
- Um ein qualitativ hochwertiges Ergebnis mit einer Bitbreite zu erhalten, die größer als die Bitbreite von ALU-Operationen ist, muss die Anzahl der Mischungen und damit die grundlegenden ALU-Operationen um mehr als das Mehrfache erhöht werden.
- Im Allgemeinen erfordert das Erstellen einer schnellen Hash-Funktion das Erreichen eines gewichteten Kompromisses zwischen Geschwindigkeit, Qualität und Ergebnisbitness .
Daher kann ich sagen, dass t1ha als Ergebnis der Suche nach einem Kompromiss zwischen Qualität und Geschwindigkeit entstanden ist, wobei gleichzeitig die Fähigkeiten moderner Prozessoren und die bereits gefundenen Methoden (arithmetisch-logische Kombinationen) zum Mischen und Verteilen von Abhängigkeiten berücksichtigt wurden ( Lawineneffekt).
Die Basisversion von t1ha ist eine der schnellsten portablen Hash-Funktionen zum Erstellen von Hash-Tabellen und anderen verwandten Anwendungen. Die Basisversion von t1ha konzentriert sich auf 64-Bit-Little-Endian-Architekturen, verwendet einen 64-Bit-Salt-Wert (Seed) und erzeugt ein 64-Bit-Ergebnis, das die Verstärkung durch Schlüssellänge und Seed umfasst. Es ist erwähnenswert, dass t1ha absichtlich so ausgelegt ist, dass es 0 für Null-Eingabedaten zurückgibt (ein Schlüssel mit einer Größe von Null und einem Startwert von Null).
Beantwortung der beliebtesten Fragen64-Bit-Operationen : Vielleicht sollte angemerkt werden, dass es die 64-Bit-Operationen sind, die Geschwindigkeit und Qualität bieten, ohne die Portabilität zu beeinträchtigen. Je breiter die Ziffernkapazität von Rechenoperationen ist, desto mehr Lawineneffekte erzeugen sie und desto besser mischen sie die Daten. Darüber hinaus ist die Datenverarbeitung bei sonst gleichen Bedingungen sicherlich um 8 Byte schneller als um 4. Auf der anderen Seite sind auf vielen modernen Prozessoren genau 64-Bit-Operationen nativ verfügbar und können mehr oder weniger angemessen in 32- übersetzt werden. Bit diejenigen. Alle anderen Optionen, einschließlich SIMD- Vorgängen, zwingen uns, die Portabilität und / oder Geschwindigkeit auf nicht nativen Plattformen stark zu beeinträchtigen.
64-Bit-Ergebnis : Um Hash-Tabellen zu erstellen, reicht in vielen Fällen ein Ergebnis mit geringerer Bitbreite aus. Sogar 32 Bit können mehr als ausreichend sein. Bei Verwendung von 64-Bit-Operationen ist das 64-Bit-Ergebnis jedoch natürlich. Gleichzeitig können Sie mit einem 64-Bit-Hash-Ergebnis von ausreichend hoher Qualität schnell einen Vergleich auf Nichtgleichheit und mit guter Genauigkeit einen Vergleich auf Gleichheit durchführen.
Die obige "Magie" des Ersetzens von Vergleichen kann unklar und unnötig erscheinen, oder sie kann die Geschwindigkeit des Hashings nur durch Datenlokalität um eine Größenordnung erhöhen , d. H. Weniger CPU-Cache-Verschmutzung. Einfach ausgedrückt kann man eine Hash-Tabellenstruktur so erstellen, dass die berechneten Hash-Werte nebeneinander liegen (in Cache-Zeilen gepackt). Die CPU würde dann nur dann die realen Daten erfassen, wenn die Hashwerte übereinstimmen. In diesem Fall ermöglichen die 64-Bit-Werte von t1ha das bestmögliche Ergebnis . Davon abgesehen bieten 128 Bit keinen Vorteil mehr, während es immer möglich ist, weniger von 64 Bit zu nehmen.
Vergleich mit HighwayHash : Ich habe gemischte Gefühle in Bezug auf dieses inoffizielle Projekt von Google-Mitarbeitern .
- Einerseits hat es guten Code und eine ausgezeichnete technische Implementierung. Andererseits ist HighwayHash als möglicherweise kryptografisch stark positioniert (mindestens gleich SipHash ). In HighwayHash gibt es einige Manipulationen, mit denen wir erwarten können, dass das Ergebnis nicht schlecht wird. Es gibt jedoch keine Beweise, die es uns erlauben würden, dies zuverlässig zu sagen. Der vorgelegte Beweis für "Stärke" beruht auf den Ergebnissen statistischer Tests, die jedoch nicht reproduzierbar sind (irgendwann habe ich mir sogar einen etwas überflüssigen Kommentar erlaubt).
- HighwayHash ist nur auf x86_64 mit AVX2 oder SSE41 sehr schnell. Ist es nicht einfacher, nur die AES-NI- oder SHA-Beschleunigung zu verwenden?
Wenn alles gut geht, werden der t1ha-Suite zusätzliche Optionen hinzugefügt (hauptsächlich für die Ergebnisbitness) und für E2K optimiert. Damit möchte ich das Thema Vergleiche mit HighwayHash abschließen.
Qualität
Die Bewertung der Qualität einer Hash-Funktion in allen Aspekten kann sehr schwierig sein. Dies kann entweder analytisch oder durch Implementierung verschiedener statistischer Tests erfolgen. Leider ist der analytische Ansatz für die Bewertung von Hash-Funktionen mit einem Kompromiss zwischen Qualität und Geschwindigkeit nicht sehr effektiv. Darüber hinaus ist eine vergleichende analytische Bewertung solcher Funktionen tendenziell subjektiv.
Im Gegensatz dazu können statistische Tests klare quantitative Schätzungen liefern. Für solche Zwecke gibt es bewährte Testpakete wie SMHasher . Für t1ha sind die Ergebnisse einfach - alle t1ha-Optionen bestehen alle Tests ohne Kommentare. Andererseits sollte man nicht davon ausgehen, dass t1ha Eigenschaften aufweist, die über die für die Zielanwendung erforderlichen hinausgehen (Erstellen von Hash-Tabellen).
Die Anzahl der Kollisionen auf allen Ebenen (Varianten) von t1ha entspricht dem Geburtstagsparadoxon . Um es genau zu formulieren: Die Kollisionswahrscheinlichkeit in t1ha entspricht der Wahrscheinlichkeit des Zusammentreffens zufälliger diskreter Werte mit entsprechender Bitigkeit.
Eine ähnliche Wahrscheinlichkeit von Kollisionen wird bei allen hochwertigen Hash-Funktionen beobachtet. Dies ist jedoch nur eine Wahrscheinlichkeit, sodass die tatsächliche Anzahl von Kollisionen für jeden spezifischen Datensatz variieren kann.
Nach der Erstveröffentlichung dieses Artikels stellte Yves Orton fest , dass das erste t1ha1() nicht immer das strenge Lawinenkriterium erfüllt . Dieser Nachteil ist für gezielte Anwendungen von t1ha1() unbedeutend und aus praktischer Sicht nicht t1ha1() . Dieser Nachteil wird jedoch in der nächsten Stufe / Variante t1ha2() beseitigt, die ursprünglich geplant war, um eine etwas höhere Qualität bereitzustellen. Auf neuen Prozessoren, die aktuelle Versionen von Compilern verwenden, ist t1ha2() im Durchschnitt einen Zyklus schneller als t1ha1() , und in den übrigen Fällen kann es einen Zyklus langsamer sein. Es ist erwähnenswert, dass t1ha2() zusätzlich einen Stream-Hashing-Modus und ein 128-Bit-Ergebnis bietet.
Die Leser würden sich sicherlich über eine gründliche und gründliche Analyse der Qualität und / oder Stärke von t1ha freuen . Basierend auf den Ziel- t1ha- Anwendungsbereichen scheint dies jedoch überflüssig zu sein. Kurz gesagt, Geschwindigkeit war uns wichtiger, auch bei kurzen Tasten. Daher wurde ein Mehrrundenmischen nicht berücksichtigt. Die vorliegende t1ha- Version spart Zyklen und liefert ein 64-Bit-Ergebnis - es ist praktisch sinnlos, den gefundenen Kompromiss auf andere Weise als statistisch zu messen, und die Ergebnisse sind einfach gut.
Benchmarks
In Bezug auf den Anspruch, " der Schnellste " zu sein. Es ist wichtig zu beachten, dass es offensichtlich nicht wahrscheinlich ist, dass es eine Hash-Funktion gibt, die gleichzeitig nützlich und auf allen Plattformen / Architekturen die schnellste ist. Verschiedene Prozessoren verfügen über unterschiedliche Befehlssätze und führen ähnliche Befehle mit unterschiedlichen Wirkungsgraden aus. Offensichtlich kann die " universell schnellste " Funktion höchstwahrscheinlich nicht erstellt werden. Es scheint jedoch akzeptabel, den Begriff "the
am schnellsten »für eine Funktion, die portabel und gleichzeitig am schnellsten ist, zumindest auf der gängigsten Plattform (x86_64), während die Wahrscheinlichkeit gering ist, auf einem modernen Prozessor mit einem anständigen optimierenden Compiler zu verlieren.
Der Quellcode des Projekts enthält einen Test, der sowohl die Richtigkeit des Ergebnisses überprüft als auch die Geschwindigkeit jeder implementierten Variante misst. Gleichzeitig können auf x86 abhängig von den Fähigkeiten des Prozessors (und des Compilers) zusätzliche Funktionsvarianten überprüft und Messungen in Prozessorzyklen durchgeführt werden.
Darüber hinaus enthält die Projektwebsite Tabellen mit den Ergebnissen von Leistungsmessungen über eine modifizierte Version von SMHasher von Reini Urban . Mit einem bestimmten Compiler kann man alle Zahlen überprüfen und / oder Ergebnisse auf einem bestimmten Prozessor erhalten.
Hier können Sie t1ha mit einigen seiner engsten Konkurrenten vergleichen.
Hashing von Kurztasten (Durchschnitt für 1..31 Bytes).
Schauen Sie sich die rechte Spalte "Cycles / Hash" an (kleiner ist besser) :
| Funktion | MiB / Sekunde | Zyklen / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Fasthash64 | 5578.06 | 43.42 |
| CityHash64 | 11041,72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Metrohash | 11808,92 | 46.33 |
Hashing lange Schlüssel (256 Kb).
Schauen Sie sich die mittlere Spalte „MiB / Sekunde“ an (größer ist besser) :
| Funktion | MiB / Sekunde | Zyklen / Hash |
|---|
| t1ha | 12228.80 | 35,55 |
| Farmhash64 | 12145.36 | 60.12 |
| CityHash64 | 11041,72 | 51,77 |
| xxHash64 | 11123.15 | 56,17 |
| Spooky64 | 11820.20 | 60,39 |
Varianten von t1ha
Entwicklung von t1ha Das erste dieser Ziele bestand darin, eine schnelle tragbare Funktion von ausreichend hoher Qualität für die Erstellung von Hash-Tabellen zu erhalten.
Dann wollten wir die schnellste Version der Hash-Funktion haben, die ein Ergebnis von vergleichbarer Qualität liefert, aber so weit wie möglich an die Zielplattform angepasst wurde. Beispielsweise arbeitet die Basisversion von t1ha mit einer Little-Endian-Bytereihenfolge, weshalb für Big-Endian-Architekturen mit unvermeidlichem Leistungsverlust eine Konvertierung erforderlich ist. Warum also nicht unnötige Vorgänge auf einer bestimmten Zielplattform loswerden? Auf diese Weise wurden mehrere weitere Optionen hinzugefügt:
- Vereinfachte Version für 32-Bit-Plattformen, sowohl für kleine als auch für große Endianer.
- Variante mit AES-NI-Anleitung, jedoch ohne AVX.
- Zwei Varianten mit den Anweisungen AES-NI und AVX.
Später wurde klar, dass mehr Optionen für verschiedene Anwendungen erforderlich sein würden, einschließlich unterschiedlicher Bitbreitenergebnisse, Qualitäts- und Haltbarkeitsanforderungen. Diese Vielfalt erforderte eine ordnungsgemäße Systematisierung. Dies wurde erreicht, indem das Namensschema geändert wurde, in dem das numerische Suffix die „Ebene“ der Funktion angibt:
t1ha0() - ist die schnellste Option für den aktuellen Prozessor.t1ha1() - ist die tragbare 64-Bit-Basisversion von t1ha.t1ha2() - ist eine tragbare 64-Bit-Version mit etwas mehr Bedenken t1ha2() Qualität.t1ha3() - ist eine schnelle tragbare 128-Bit-Version für Fingerabdrücke.- usw.
In diesem Schema wird angenommen, dass t1ha0() ein Dispatcher ist, der die Umleitung abhängig von der Plattform und den Fähigkeiten des aktuellen Prozessors implementiert. Zusätzlich kann die Verwendung der Suffixe "_le" und "_be" für eine explizite Wahl zwischen der Little-Endian- und der Big-Endian-Variante eingeführt werden. So gibt es unter dem Schild „t1ha“ jetzt mehrere Hash-Funktionen, und diese Familie wird in Zukunft wachsen, einschließlich einer für das russische E2K „Elbrus“ optimierten Version.
Eine allgemeine Vorstellung des aktuellen Satzes von Funktionen und ihrer Eigenschaften kann durch Betrachten der eingebauten Testausgabe ( make check ) erfasst werden. Es ist anzumerken, dass alle Funktionen alle SM Hasher-Tests bestehen und die Leistung der AES-NI-Varianten je nach Prozessormodell stark variiert:
Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz
Ein bisschen über die interne StrukturUm ein wenig detaillierter zu werden, wird t1ha nach dem Merkle-Damgård-Schema („Wipe-Pipe“ -Version) gebaut, wobei die Datengröße und der Startwert verstärkt werden. Innerhalb der Hauptkomprimierungsschleife wird ein 256-Bit-Status mit derselben Größe des Eingabeblocks verwendet. Darüber hinaus gibt es für jeden Datenoperanden zwei Injektionspunkte mit Kreuzbestäubung. Nach Abschluss des Komprimierungszyklus wird der 256-Bit-Zustand auf 128 Bit komprimiert.
Bei der Ausführung der oben genannten Aktionen werden 64-Bit-Operationen verwendet, die in den Mischern ARX (Add-Rotate-Xor) und MUX / MRX (Mul-Rotate-Xor) kombiniert sind. Es ist wichtig, dass alle diese Berechnungen so erstellt werden, dass die Möglichkeit der parallelen Ausführung der meisten Vorgänge und des engen Packens von U-Ops sowohl in die Pipeline als auch in x86_64-Ausführungseinheiten gewährleistet ist. Dadurch wird eine ausreichend gute Qualität mit nahezu maximaler Hash-Rate für lange Schlüssel erreicht.
Es ist anzumerken, dass die Komprimierungsschleife nur für Blöcke mit ausreichender Größe ausgeführt wird. Wenn weniger Daten vorhanden sind, besteht der 128-Bit-Zwischenzustand nur aus der Schlüsselgröße und dem Salt-Wert.
Dann wird das verbleibende Ende der Daten in Teilen von 64 Bit abwechselnd mit den Hälften des 128-Bit-Zustands gemischt. Schließlich wird der Zustand gemischt und gleichzeitig auf ein 64-Bit-Ergebnis komprimiert. Ein wichtiges Merkmal von t1ha ist hier die Verwendung eines Mischers, der auf einer breiten Multiplikation basiert (128-Bit-Produkt von zwei 64-Bit-Multiplikatoren). Dies ermöglicht eine gute Mischqualität mit einem guten Lawineneffekt und weniger Vorgängen. Obwohl eine breite Multiplikation eine relativ teure Operation ist, ermöglichen weniger solcher Operationen t1ha, kurze Schlüssel in einer rekordarmen Anzahl von Prozessorzyklen zu verarbeiten.
Es ist zu beachten, dass der Mischer, der auf einer breiten Multiplikation und einem exklusiven ODER basiert, nicht perfekt ist. Obwohl t1ha alle SMHasher- Tests besteht, versteht der Autor die Konsequenzen der Nichtinjektivität . Trotzdem scheint die resultierende Qualität rational ausreichend zu sein, und die Entwicklungspläne für die t1ha-Linie spiegeln bereits die Absicht wider, etwas höhere Qualitätsoptionen bereitzustellen.
Weitere Informationen und Quellcode finden Sie hier .
Danke fürs Lesen!