Qu’est-ce qu’une bonne fonction de hachage?

Qu’est-ce qu’une bonne fonction de hachage? J’ai vu beaucoup de fonctions de hachage et d’applications dans mes cours sur les structures de données à l’université, mais j’ai surtout trouvé que c’était assez difficile de faire une bonne fonction de hachage. En règle générale, pour éviter les collisions, mon professeur a déclaré que:

function Hash(key) return key mod PrimeNumber end 

(le mod est l’opérateur% en C et les langages similaires)

avec le nombre premier pour être la taille de la table de hachage. Je trouve que c’est une bonne fonction pour éviter les collisions et une rapidité, mais comment puis-je en améliorer une? Existe-t-il de meilleures fonctions de hachage pour les clés de chaîne contre les touches numériques?

Pour faire des recherches de tables de hachage “normales” sur n’importe quel type de données – celle de Paul Hsieh est la meilleure que j’ai jamais utilisée.

http://www.azillionmonkeys.com/qed/hash.html

Si vous vous souciez de la sécurité cryptographique ou de tout autre élément plus avancé, alors YMMV. Si vous voulez juste une fonction de hachage générique pour une recherche de table de hachage, alors c’est ce que vous cherchez.

Il n’y a pas de «bonne fonction de hachage» pour les hachages universels (ed. Oui, je sais qu’il existe un «hachage universel», mais ce n’est pas ce que je voulais dire). Selon le contexte, différents critères déterminent la qualité d’un hachage. Deux personnes ont déjà mentionné SHA. Ceci est un hachage cryptographique et ce n’est pas du tout bon pour les tables de hachage que vous voulez probablement dire.

Les tables de hachage ont des exigences très différentes. Cependant, trouver une bonne fonction de hachage est difficile car différents types de données exposent des informations différentes qui peuvent être hachées. En règle générale, il est bon de considérer toutes les informations qu’un type détient également. Ce n’est pas toujours facile ou même possible. Pour des raisons de statistiques (et donc de collision), il est également important de générer une bonne répartition entre les problèmes, c’est-à-dire tous les objects possibles. Cela signifie que lors du hachage de nombres compris entre 100 et 1050, il ne sert à rien de laisser le chiffre le plus significatif jouer un rôle important dans le hachage car pour environ 90% des objects, ce chiffre sera de 0. les chiffres déterminent le hachage.

De même, lors du hachage de chaînes de caractères, il est important de prendre en compte tous les caractères, sauf lorsque l’on sait à l’avance que les trois premiers caractères de toutes les chaînes seront les mêmes. compte tenu de ceux-ci est alors un déchet.

C’est en fait l’un des cas où je conseille de lire ce que Knuth a à dire dans The Art of Computer Programming , vol. 3. Une autre bonne lecture est The Art of Hashing de Julienne Walker.

Les fonctions de hachage ont deux objectives principaux:

  • pour disperser les points de données uniformément dans n bits.
  • pour identifier en toute sécurité les données d’entrée.

Il est impossible de recommander un hachage sans savoir pour quoi vous l’utilisez.

Si vous ne faites qu’une table de hachage dans un programme, vous n’avez pas à vous soucier de la réversibilité ou du piratage de l’algorithme … SHA-1 ou AES est complètement inutile pour cela. une variation de FNV . FNV permet une meilleure dispersion (et donc moins de collisions) qu’un simple mod de base comme vous l’avez mentionné, et il est plus adaptable à différentes tailles d’entrées.

Si vous utilisez les hachages pour masquer et authentifier des informations publiques (telles que le hachage d’un mot de passe ou d’un document), vous devez utiliser l’un des principaux algorithmes de hachage approuvés par le public. Le Hash Function Lounge est un bon endroit pour commencer.

Ceci est un exemple d’une bonne et aussi un exemple de pourquoi vous ne voudriez jamais en écrire un. C’est un hack de Fowler / Noll / Vo (FNV) qui est à égalité de génie informatique et de pur vaudou:

 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; } 

Modifier:

  • Landon Curt Noll recommande sur son site l'algorithme FVN-1A par rapport à l'algorithme FVN-1 original: l'algorithme amélioré disperse mieux le dernier octet du hachage. J'ai ajusté l'algorithme en conséquence.

Je dirais que la règle de base est de ne pas rouler les vôtres. Essayez d’utiliser quelque chose qui a été testé de manière approfondie, par exemple SHA-1 ou quelque chose du genre.

Une bonne fonction de hachage a les propriétés suivantes:

  1. Étant donné le hachage d’un message, il est impossible sur le plan informatique pour un attaquant de trouver un autre message de manière à ce que leurs hachages soient identiques.

  2. Étant donné une paire de message, m ‘et m, il est irréalisable de trouver deux telles que h (m) = h (m’)

Les deux cas ne sont pas les mêmes. Dans le premier cas, il existe un hachage préexistant pour lequel vous essayez de trouver une collision. Dans le second cas, vous essayez de trouver deux messages qui entrent en collision. La deuxième tâche est beaucoup plus facile grâce au “paradoxe” de l’anniversaire.

Là où la performance n’est pas un problème majeur, vous devez toujours utiliser une fonction de hachage sécurisée. Il existe des attaques très intelligentes qui peuvent être effectuées en forçant des collisions dans un hash. Si vous utilisez quelque chose de fort dès le départ, vous vous en protégerez.

N’utilisez pas MD5 ou SHA-1 dans les nouvelles conceptions. La plupart des cryptographes, y compris moi, les considéreraient comme cassés. La principale source de faiblesse dans ces deux conceptions est que la deuxième propriété, que j’ai décrite ci-dessus, ne tient pas pour ces constructions. Si un attaquant peut générer deux messages, m et m ‘, tous deux hachant à la même valeur, ils peuvent utiliser ces messages contre vous. SHA-1 et MD5 souffrent également d’attaques d’extension de messages, ce qui peut fatalement affaiblir votre application si vous ne faites pas attention.

Un hash plus moderne tel que Whirpool est un meilleur choix. Il ne souffre pas de ces attaques d’extension de messages et utilise les mêmes méthodes mathématiques que celles utilisées par AES pour prouver la sécurité contre diverses attaques.

J’espère que cela pourra aider!

Ce que vous dites ici, c’est que vous voulez en avoir un qui utilise une résistance aux collisions. Essayez d’utiliser SHA-2. Ou essayez d’utiliser un (bon) bloc de chiffrement dans une fonction de compression à sens unique (jamais essayé auparavant), comme AES en mode Miyaguchi-Preenel. Le problème avec cela est que vous devez:

1) avoir un IV. Essayez d’utiliser les 256 premiers bits des parties fractionnaires de la constante de Khinchin ou quelque chose comme ça. 2) avoir un système de remplissage. Facile. Faites-le passer d’un hash comme MD5 ou SHA-3 (Keccak [prononcé ‘ket-chak’]). Si vous ne vous souciez pas de la sécurité (quelques autres l’ont dit), regardez FNV ou lookup2 de Bob Jenkins (en fait je suis le premier à recommander lookup2) Essayez aussi MurmurHash, c’est rapide (vérifiez ceci: .16 cpb ).