Technique d'exploration automatisée de fonctions de hachage d’entiers

Hash Function Prospector

Cet outil est un petit utilitaire pour la recherche automatisée de fonctions de hachage d’entiers. Il sélectionne aléatoirement parmi 9 opérations réversibles et génère des milliards de fonctions de hachage entières. Les fonctions générées sont compilées par JIT, et leur comportement Avalanche est évalué. La meilleure fonction actuelle est ensuite affichée en syntaxe C.

• Score Avalanche : nombre moyen de bits de sortie qui restent inchangés lorsqu’un bit d’entrée est inversé. Un score faible est meilleur. L’idéal est 0. Autrement dit, en inversant un seul bit d’entrée, chaque bit de sortie devrait être inversé avec une probabilité de 50 %.
• Prospector peut générer des fonctions de hachage entières 32 bits et 64 bits. Consultez -h pour connaître toutes les options. À cause du compilateur JIT, seul x86-64 est pris en charge, mais les fonctions trouvées peuvent être utilisées partout.

Fonctions de hachage découvertes

Il y a deux classes utiles de fonctions de hachage découvertes par Prospector et d’autres utilitaires d’aide présents ici. Les deux utilisent une structure xorshift-multiply-xorshift, mais le nombre de tours est différent.

Fonctions en 2 tours

TheIronBorn a utilisé une optimisation combinatoire pour trouver les meilleurs paramètres connus pour cette structure.

• Cette permutation 2 tours de 32 bits a un biais particulièrement faible et bat même, de peu, le finalizer 32 bits de MurmurHash3.
• La structure de la fonction de hachage a été découverte par Prospector, et les paramètres sont optimisés par hill climbing et algorithme génétique.

Il existe d’autres constantes 2 tours encore plus peu biaisées, dont certaines sont meilleures que lowbias32.

Fonctions en 3 tours

En ajoutant un tour supplémentaire de multiply-xorshift à cette structure, il est possible d’atteindre la limite théorique de biais avec des paramètres choisis avec soin. Par exemple, cette fonction de hachage est indiscernable d’une PRF parfaite.

• triple32 résout également le problème hash(0) = 0 et réduit davantage le biais.
• Il existe également davantage de constantes 3 tours à faible biais.

Mesure précise du biais

Le mode -E évalue le biais d’une fonction de hash donnée (-p ou -l). Par défaut, Prospector utilise une estimation pour évaluer rapidement le biais d’une fonction, mais cette estimation est non déterministe et les résultats contiennent beaucoup de bruit. Pour mesurer précisément et de manière exhaustive le biais, utilisez l’option -e.

• Avec -p et un pattern ou avec -l et une bibliothèque partagée contenant une fonction hash(), vous pouvez définir la fonction à tester.
• Il n’y a pas de test exact et exhaustif pour les fonctions de hachage 64 bits, car il est trop long.

Sélection des opérations réversibles

Les opérations réversibles suivantes sont utilisées :

• x = ~x;
• x ^= constant;
• x *= constant | 1; (seuls les constantes impaires)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (rotation à gauche)
• x = bswap(x) (échanger l’octet de poids fort et de poids faible)

Techniquement, x = ~x est couvert par x ^= constant. Toutefois, ~x a un comportement unique et est particulièrement utile.

Hachage 16 bits

Les contraintes sont différentes pour le hachage 16 bits, donc un outil distinct hp16 existe pour générer ces fonctions.

• Contrairement à Prospector 32/64 bits, cette implémentation est entièrement portable et fonctionne sur presque tous les systèmes.
• Elle permet également de générer et d’évaluer une S-box de 128 KiB.
• Les hachages 16 bits étant probablement plus nécessaires sur des machines sans multiplication rapide, certaines opérations peuvent être omises pendant la recherche (-m, -r).

Quelques résultats intéressants :

• Hachage xorshift-multiply en 2 tours
• Hachage xorshift-multiply en 3 tours
• Hachage sans multiplication (utilisant uniquement xorshift-add)

Un bon hash xorshift en 3 tours (recherche courte via hp16 -Xn3) se rapproche d’une bonne S-box (hp16 -S).

Lorsqu’on manipule des opérations 16 bits, il faut prêter attention aux règles de promotion d’entier du C. Le programme C produit par cet outil veille, quand nécessaire, à promouvoir les opérations 16 bits vers unsigned int.

Avis de GN⁺

• La sécurité des fonctions de hachage joue un rôle crucial en cryptographie et en sécurité informatique, et un tel outil d’exploration devrait être très utile à la recherche. Il est particulièrement intéressant de pouvoir découvrir des fonctions à faible biais via une recherche aléatoire.

• Cependant, la sécurité d’une fonction de hachage ne peut être garantie uniquement par des propriétés statistiques. Un hash cryptographique doit aussi résister à de nombreuses attaques, comme la PreImage Resistance, la Second PreImage Resistance, la Collision Resistance, etc., donc une analyse supplémentaire semble nécessaire.

• Les fonctions de hachage 16 bits devraient être utiles dans des environnements contraints comme l’IoT ou les systèmes embarqués. Il est impressionnant qu’il soit possible de créer des fonctions de hachage avec uniquement des opérations ADD/XOR/SHIFT afin de fonctionner aussi sur des CPU sans instruction de multiplication.

• L’application de techniques de recherche heuristique comme le hill climbing ou les algorithmes génétiques à la conception de fonctions de hachage est une idée intéressante. Les tentatives d’intégrer l’IA à la conception d’algorithmes cryptographiques se multiplient, et ce type d’optimisation jouera probablement un rôle de plus en plus important.

• Cela étant dit, même si une fonction a de bonnes caractéristiques Avalanche, il est difficile de prétendre à sa sûreté cryptographique, et c’est là une limite du projet. Néanmoins, ce type d’outil peut aider à analyser et améliorer les défauts des fonctions de hachage existantes.

[GN⁺]

Avis de Hacker News

• Ce que le développeur en question aime dans son code
  • Les bibliothèques JSON, bibliothèques d’analyse d’options, décodeur UTF-8 sans branchement, pile lock-free, bibliothèque trie, etc.
  • Le fait que ces bibliothèques soient toutes publiées sous Unlicense.
• Commentaire du développeur de MurmurHash
  • Il exprime qu’il est intéressant que l’opération multiply-shift-xor ait résisté si longtemps.
• Réflexions partagées sur la recherche automatique de fonctions de hachage
  • Il pense qu’il serait bon de les évaluer automatiquement en les couplant avec SMHasher3
    • pour n’utiliser que certains tests afin de gagner en vitesse et échouer rapidement
  • Il pense aussi qu’il serait bon d’étendre à des hashs 64 et 128 bits (même si l’espace de recherche est plus grand)
  • Il a écrit du code NodeJS dans la bibliothèque Rain pour mesurer l’effet avalanche des multiplications par des nombres premiers 64 bits
• Partage d’une expérience d’implémentation du problème 1brc en Go
  • Il a essayé de trouver une fonction de hachage parfaite sur mesure pour placer chaque station dans son propre bucket sans collision, mais il a abandonné à cause de la règle interdisant de personnaliser la fonction de hachage en fonction des données avant le démarrage du programme
  • Il a construit un outil de test vérifiant des constantes aléatoires et affichant la meilleure constante trouvée jusqu’à présent selon le nombre de buckets en collision et le nombre de collisions
    • il a pu réduire à un seul bucket n’ayant que 2 valeurs en collision avec un taux de remplissage d’environ 40 %
    • il lui a semblé intéressant de constater que des valeurs semblables au nombre de positions de décalage étaient incluses dans la meilleure constante de performance, indépendamment des autres constantes
• Une demande d’explication sur ce qui rend ce code intéressant et son usage prévu
• Des questions sur ce que fait exactement ce code, sur le fait de rechercher la meilleure fonction de hachage, et sinon pourquoi la meilleure fonction de hachage change à chaque exécution
• Une demande d’information sur le mécanisme pour trouver de bonnes fonctions de hachage pour une gamme donnée de valeurs entières
  • Par exemple en connaissant les valeurs entières entre 10 000 et 200 000, et en voulant les hacher vers le nombre optimal de buckets
• Il a fait valoir que restreindre les opérations à celles qui sont inversibles a des avantages mathématiques, mais en exclut beaucoup d’options
  • Il a pensé au hachage parfait avec un ensemble d’entrées connu à l’avance
  • En général, il utilise des tableaux de constantes, mais voulait savoir si l’on peut compresser davantage quand les entrées sont déjà de petits entiers
  • Il avait rédigé une liste d’environ 100 opérations de base, mais a laissé tomber le projet car c’était trop monotone
• Il a suggéré qu’utiliser la même constante pour deux multiplications peut réduire la taille du code et rendre les calculs légèrement plus rapides
• Reconnaissant que ces fonctions ne conviennent pas à la cryptographie, il demande quel impact les biais mesurés peuvent avoir sur l’analyse cryptographique
  • Curieux de savoir si quelqu’un familier avec la cryptographie différentielle peut l’expliquer
  • Il se demande si un hash à faible biais peut rendre inefficace l’analyse cryptographique avec moins de rounds ou de calculs
  • Il se demande si cet outil peut aider à trouver de meilleures fonctions de hachage cryptographiques
• Présentation d’un projet similaire
  • La qualité des fonctions est meilleure (l’interpréteur est utilisé, donc c’est plus lent)
  • Mais il n’a pas trouvé de fonction meilleure que les fonctions de hachage existantes