À peu près la fonction de hachage portable 64 bits la plus rapide avec une qualité décente.
Il s'agit d'une traduction de l' article original de Leonid Yuriev .
Au lieu d'une clause de non-responsabilitéJe vais omettre la définition des fonctions de hachage ainsi que la liste détaillée des propriétés et des exigences de leur application cryptographique, et je suppose que le lecteur a les connaissances minimales nécessaires ou qu'il les lira . Il convient également de noter que je parlerai ci-après de fonctions de hachage non cryptographiques (ne conviennent pas à la cryptographie), sauf indication contraire explicite.
BanalitésLe hachage est utilisé dans de nombreux algorithmes, et presque toujours le traitement de données le plus efficace (rapide) est requis, avec un certain niveau minimum de qualité de hachage. Ici, le terme «qualité» signifie tout d'abord une sorte de «hasard» (stochasticité) par rapport aux données initiales. Un peu moins souvent, des exigences supplémentaires sont imposées, telles que la résistance à la génération délibérée de collisions ou l'irréversibilité.
Pour être un peu plus fastidieuxPour plus de clarté, il est nécessaire de définir un peu plus en détail le concept de «qualité» de la fonction de hachage et le reste des exigences:
Qualité de référence et effet d'avalanche : la modification d'un ou plusieurs bits arbitraires dans un ensemble arbitraire de données source entraîne une modification de chaque bit du résultat avec une probabilité de ½.
- Irréversibilité ou première résistance à la pré-image: l'impossibilité d'obtenir les données originales ou les bits individuels du résultat de hachage.
- Résistance aux collisions de premier ordre et / ou deuxième résistance à la pré-image: la difficulté de trouver / ajuster l'ensemble de données d'origine pour obtenir un résultat spécifié ou une partie de celui-ci, y compris lorsque l'ensemble de données initial est connu.
- Résistance aux collisions de second ordre: la difficulté de trouver / ajuster deux ensembles de données différents qui donneraient le même résultat ou une correspondance d'une partie significative.
En omettant de longues citations des mathématiques sous-jacentes, il peut être résumé:
- Satisfaire à toutes les exigences ci-dessus tout en garantissant des performances élevées est un problème assez difficile à résoudre, ce qui nous donnerait une bonne fonction de hachage cryptographique. Mais nous n'allons pas encore le faire.
- La fourniture d'une qualité de base nécessite un nombre suffisamment important d'opérations ALU. En termes simples, la qualité est toujours compromise avec la vitesse.
- L'obtention d'un résultat de haute qualité avec une largeur de bit supérieure à la largeur de bit des opérations ALU nécessite plus d'une multiplication par plusieurs du nombre de mélanges, et donc des opérations ALU de base.
- En général, la création d'une fonction de hachage rapide implique la réalisation d'un compromis pondéré entre la vitesse, la qualité et le résultat bitness .
Par conséquent, je peux dire que t1ha est apparu à la suite de la recherche d'un compromis entre la qualité et la vitesse, en tenant compte à la fois des capacités des processeurs modernes et des méthodes déjà trouvées (combinaisons arithmétiques et logiques) de mélange et de propagation des dépendances ( effet avalanche).
La version de base de t1ha est l'une des fonctions de hachage portables les plus rapides pour la construction de tables de hachage et d'autres applications connexes. La version de base de t1ha se concentre sur les architectures little-endian 64 bits, prend une valeur de sel 64 bits (seed) et produit un résultat 64 bits, qui comprend le renforcement par la longueur de clé et le seed. Il convient de noter que t1ha est intentionnellement conçu pour renvoyer 0 pour des données d'entrée nulles (une clé de taille zéro et de zéro graine).
Répondre aux questions les plus fréquentesOpérations 64 bits : Il convient peut-être de noter que ce sont les opérations 64 bits qui offrent vitesse et qualité sans nuire à la portabilité. En fait, plus la capacité numérique des opérations arithmétiques est large, plus elles produisent d'effet avalanche et mieux elles mélangent les données. De plus, le traitement des données, toutes choses étant égales par ailleurs, est certainement plus rapide de 8 octets que de 4. D'autre part, des opérations exactement 64 bits sont nativement disponibles sur de nombreux processeurs modernes et peuvent être plus ou moins correctement traduites en 32- les petits. Toutes les autres options, y compris les opérations SIMD , nous obligent à sacrifier considérablement la portabilité et / ou la vitesse sur des plates-formes non natives.
Résultat 64 bits : pour construire des tables de hachage, dans de nombreux cas, un résultat de largeur de bit plus petit suffit. Même 32 bits peuvent être plus que suffisants. Cependant, lorsque vous utilisez des opérations 64 bits, le résultat 64 bits vient naturellement. Dans le même temps, un résultat de hachage 64 bits de qualité suffisamment élevée vous permet d'effectuer rapidement une comparaison pour la non-égalité et avec une bonne précision de comparer pour l'égalité.
La "magie" ci-dessus de remplacer les comparaisons peut sembler peu claire et inutile, ou elle peut augmenter la vitesse de hachage d'un ordre de grandeur uniquement au moyen de la localisation des données, c'est-à-dire moins de pollution du cache du processeur. Autrement dit, on peut construire une structure de table de hachage de telle manière que les valeurs de hachage calculées se trouvent côte à côte (regroupées dans des lignes de cache). Le CPU ne récupère alors les données réelles que si les valeurs de hachage correspondent. Et dans ce cas, les 64 bits de t1ha permettent d'obtenir le meilleur résultat possible . Cela étant dit, 128 bits ne fourniront plus d'avantage, tandis que prendre moins de 64 bits est toujours possible.
Comparaison avec HighwayHash : J'ai des sentiments mitigés sur ce projet non officiel des employés de Google .
- D'une part, il a un bon code et une excellente implémentation technique. D'un autre côté, HighwayHash est positionné comme possiblement fort cryptographiquement (au moins égal à SipHash ). À l'intérieur de HighwayHash, il y a pas mal de manipulations qui nous permettent de nous attendre à ce que le résultat ne soit pas mauvais. Cependant, il n'y a aucune preuve qui nous permettrait de le dire de manière fiable. La preuve de «force» fournie se résume aux résultats des tests statistiques, mais sans pouvoir les reproduire (à un moment donné, je me suis même permis un commentaire quelque peu superflu).
- HighwayHash est vraiment rapide uniquement sur x86_64 avec AVX2 ou SSE41. N'est-il pas plus facile alors d'utiliser simplement l'accélération AES-NI ou SHA?
Si tout se passe bien, des options supplémentaires seront ajoutées à la suite t1ha (principalement pour le résultat bitness) et optimisées pour E2K. Sur ce, je voudrais clore le sujet des comparaisons avec HighwayHash.
La qualité
L'évaluation de la qualité d'une fonction de hachage sous tous ses aspects peut être assez difficile. Cela peut se faire soit analytiquement, soit en mettant en œuvre divers tests statistiques. Malheureusement, l'approche analytique n'est pas très efficace pour évaluer les fonctions de hachage avec un compromis entre qualité et rapidité. De plus, une évaluation analytique comparative de ces fonctions a tendance à être subjective.
En revanche, les tests statistiques peuvent fournir des estimations quantitatives claires. À ces fins, il existe des packages de test éprouvés, tels que SMHasher . Pour t1ha , les résultats sont simples - toutes les options de t1ha réussissent tous les tests sans aucun commentaire. En revanche, il ne faut pas supposer que t1ha possède des propriétés supérieures à celles qui sont nécessaires pour l'application cible (création de tables de hachage).
Le nombre de collisions à tous les niveaux (variantes) de t1ha correspond au paradoxe d'anniversaire . Pour le formuler strictement - la probabilité de collision en t1ha correspond à la probabilité de coïncidence de valeurs discrètes aléatoires avec le bitness correspondant.
Une probabilité de collision similaire est observée dans toutes les fonctions de hachage de haute qualité. Cependant, il ne s'agit que de probabilité, de sorte que le nombre réel de collisions peut varier pour chaque ensemble de données spécifique.
Après la première publication de cet article, Yves Orton a découvert que le premier t1ha1() ne répond pas toujours au critère strict des avalanches . Cet inconvénient est insignifiant pour les applications ciblées de t1ha1() et imperceptible d'un point de vue pratique. Cependant, cet inconvénient est éliminé dans le prochain niveau / variante t1ha2() , qui était initialement prévu pour fournir une qualité légèrement supérieure. Sur les nouveaux processeurs, qui utilisent les versions actuelles des compilateurs, t1ha2() est en moyenne un cycle plus rapide que t1ha1() , et dans le reste des cas, il peut être un cycle plus lent. Il convient de noter que t1ha2() offre en outre un mode de hachage de flux et un résultat de 128 bits.
Les lecteurs apprécieraient certainement une analyse approfondie et approfondie de la qualité et / ou de la force du t1ha . Cependant, sur la base des zones d'application t1ha cibles, cela semble redondant. En termes simples, la vitesse était plus importante pour nous, même pour les touches courtes. Par conséquent, le mélange à plusieurs tours n'a pas été envisagé. La version t1ha actuelle permet d' économiser sur les cycles et donne un résultat 64 bits - il est pratiquement inutile de mesurer le compromis trouvé autrement que statistiquement, et ses résultats sont tout simplement bons.
En faitJe viens de suivre mes collègues de Google sur la façon dont ils fournissent leur preuve statistique
Repères
Concernant la prétention d'être " la plus rapide ". il est important de noter qu'il est évidemment peu probable qu'il existe une fonction de hachage qui soit à la fois utile et la plus rapide sur toutes les plateformes / architectures. Différents processeurs ont différents ensembles d'instructions disponibles et exécutent des instructions similaires avec différentes efficacités. De toute évidence, la fonction " universellement la plus rapide " ne peut très probablement pas être créée. Cependant, il semble acceptable d'utiliser le terme
le plus rapide »pour une fonction qui est portable et en même temps la plus rapide, au moins sur la plate-forme la plus courante (x86_64), tout en ayant peu de chance de perdre sur n'importe quel processeur moderne avec un compilateur d'optimisation décent.
Le code source du projet comprend un test qui vérifie à la fois l'exactitude du résultat et mesure la vitesse de chaque variante implémentée. En même temps, sur x86, en fonction des capacités du processeur (et du compilateur), des variantes de fonctions supplémentaires peuvent être vérifiées et les mesures sont effectuées en cycles de processeur.
En outre, le site Web du projet contient des tableaux avec les résultats des mesures de performance via une version modifiée de SMHasher de Reini Urban . On peut revérifier tous les chiffres et / ou obtenir des résultats sur un processeur spécifique en utilisant un compilateur spécifique.
Ici, vous pouvez comparer t1ha avec certains de ses concurrents les plus proches.
Hachage de touches courtes (moyenne de 1 à 31 octets).
Regardez la colonne de droite "Cycles / Hash" (plus petite est meilleure) :
| Fonction | Mio / seconde | Cycles / 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 |
Hachage de clés longues (256 Ko).
Regardez la colonne du milieu "MiB / Second" (plus c'est gros, mieux c'est) :
| Fonction | Mio / seconde | Cycles / 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 |
Variantes de t1ha
Développement de t1ha Le premier de ces objectifs était d'obtenir une fonction portable rapide de qualité suffisamment élevée pour construire des tables de hachage.
Ensuite, nous voulions avoir la version la plus rapide de la fonction de hachage qui donnerait un résultat de qualité comparable mais qui serait autant que possible adaptée à la plateforme cible. Par exemple, la version de base de t1ha fonctionne avec un ordre d'octets petit- boutien , ce qui nécessite une conversion pour les architectures grand-boutiens avec une perte de performances inévitable. Alors pourquoi ne pas se débarrasser des opérations inutiles sur une plateforme cible spécifique? De cette façon, plusieurs autres options ont été ajoutées:
- Version simplifiée pour les plates-formes 32 bits, petites et grandes.
- Variante utilisant les instructions AES-NI, mais sans AVX.
- Deux variantes utilisant les instructions AES-NI et AVX.
Plus tard, il est devenu clair que davantage d'options conçues pour diverses applications seraient nécessaires, y compris des résultats de largeur de mèche différents, des exigences de qualité et de durabilité. Cette diversité nécessite une systématisation appropriée. Ceci a été réalisé en changeant le schéma de nommage, dans lequel le suffixe numérique indique le «niveau» de la fonction:
t1ha0() - est l'option la plus rapide pour le processeur actuel.t1ha1() - est la version 64 bits portable de base de t1ha.t1ha2() - est une version portable 64 bits avec un peu plus de souci de qualité.t1ha3() - est une version portable rapide de 128 bits pour les empreintes digitales.- etc.
Dans ce schéma, on suppose que t1ha0() est un répartiteur qui implémente la redirection en fonction de la plate-forme et des capacités du processeur actuel. De plus, l'utilisation des suffixes "_le" et "_be" pour un choix explicite entre les variantes little-endian et big-endian peut être introduite. Ainsi, sous l'enseigne «t1ha», il y a maintenant plusieurs fonctions de hachage, et cette famille va grandir dans le futur, y compris une version optimisée pour l'E2K russe «Elbrus».
Une idée générale de l'ensemble actuel des fonctions et de leurs propriétés peut être saisie en regardant la sortie de test intégrée ( make check ). Il convient de noter que toutes les fonctions réussissent tous les tests SM Hasher et que les performances des variantes AES-NI varient considérablement en fonction du modèle de processeur:
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
Un peu sur la structure internePour approfondir un peu plus les détails, t1ha est construit selon le schéma de Merkle-Damgård (version «wipe-pipe») avec un renforcement à partir de la taille des données et de la valeur de départ. À l'intérieur de la boucle de compression principale, un état de 256 bits est utilisé, avec la même taille du bloc d'entrée. De plus, pour chaque opérande de données, il existe deux points d'injection avec pollinisation croisée. À la fin du cycle de compression, l'état 256 bits est compressé à 128 bits.
Lors de l'exécution des actions ci-dessus, des opérations 64 bits, combinées dans les mélangeurs ARX (Add-Rotate-Xor) et MUX / MRX (Mul-Rotate-Xor), sont utilisées. Il est important que tous ces calculs soient construits de manière à garantir la possibilité d'exécution parallèle de la plupart des opérations et un compactage des opérations opérationnelles à la fois dans le pipeline et dans les unités d'exécution x86_64. De ce fait, une qualité suffisamment bonne est obtenue avec un taux de hachage presque maximal pour les touches longues.
Il convient de noter que la boucle de compression ne fonctionne que pour des blocs de taille suffisante. S'il y a moins de données, l'état intermédiaire de 128 bits consistera uniquement en la taille de clé et la valeur de sel.
Ensuite, la queue restante des données est mélangée en portions de 64 bits alternativement aux moitiés de l'état 128 bits. Enfin, l'état est mélangé et compressé simultanément en un résultat 64 bits. Une caractéristique importante de t1ha ici est l'utilisation d'un mélangeur basé sur une multiplication large (produit 128 bits de deux multiplicateurs 64 bits). Cela permet un mélange de bonne qualité avec un bon effet d'avalanche et moins d'opérations. Même si une multiplication large est une opération relativement coûteuse, moins de telles opérations permettent à t1ha de traiter des clés courtes dans un nombre record de cycles de processeur.
Il convient de noter que le mélangeur basé sur une large multiplication et un OU exclusif n'est pas parfait. Bien que t1ha réussisse tous les tests SMHasher , l'auteur comprend les conséquences de la non-injectivité ). Néanmoins, la qualité qui en résulte semble être rationnellement suffisante, et les plans de développement de la ligne t1ha reflètent déjà l'intention de proposer des options de qualité légèrement supérieures.
Vous pouvez trouver plus d'informations et le code source ici .
Merci d'avoir lu!