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

https://stackoverflow.com/questions/34595

09-06-2019
|

Question

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 compris qu'il était assez difficile de créer une bonne fonction de hachage.En règle générale, pour éviter les collisions, mon professeur a dit ceci :

function Hash(key)
  return key mod PrimeNumber
end

(mod est l'opérateur % en C et langages similaires)

avec le nombre premier correspondant à la taille de la table de hachage.Je comprends que c'est une fonction plutôt bonne pour éviter les collisions et rapide, mais comment puis-je en créer une meilleure ?Existe-t-il de meilleures fonctions de hachage pour les clés de chaîne par rapport aux clés numériques ?

La solution

Pour effectuer des recherches "normales" dans des tables de hachage sur pratiquement 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 toute autre chose plus avancée, alors YMMV.Si vous voulez juste une fonction de hachage à usage général pour une recherche dans une table de hachage, alors c'est ce que vous recherchez.

Autres conseils

Il n’existe pas de « bonne fonction de hachage » pour les hachages universels (éd.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.Il s'agit d'un hachage cryptographique et ce n'est pas du tout bon pour les tables de hachage, ce que vous voulez probablement dire.

Les tables de hachage ont des exigences très différentes.Néanmoins, il est difficile de trouver une bonne fonction de hachage universellement, car différents types de données exposent différentes informations pouvant être hachées.En règle générale, il est bon de considérer tous informations qu'un type contient également.Ce n’est pas toujours facile ni même possible.Pour des raisons de statistiques (et donc de collision), il est également important de générer une bonne répartition sur l'espace du problème, c'est-à-diretous les objets 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 grand rôle dans le hachage car pour ~ 90 % des objets, ce chiffre sera 0.Il est bien plus important de laisser les trois derniers chiffres déterminer le hachage.

De même, lors du hachage de chaînes, il est important de prendre en compte tous les caractères – sauf lorsqu'on sait à l'avance que les trois premiers caractères de toutes les chaînes seront identiques ;les considérer est alors un gaspillage.

C'est d'ailleurs un des cas où je conseille de lire ce que dit Knuth dans L'art de la programmation informatique, vol.3.Une autre bonne lecture est celle de Julienne Walker L'art du hachage.

Les fonctions de hachage ont deux objectifs principaux :

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

Il est impossible de recommander un hash sans savoir à quoi vous l’utilisez.

Si vous créez simplement 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 sont totalement inutiles pour cela, vous feriez mieux d'utiliser un variation du FNV.FNV permet une meilleure dispersion (et donc moins de collisions) qu'un simple mod principal comme vous l'avez mentionné, et il est plus adaptable aux différentes tailles d'entrée.

Si vous utilisez les hachages pour masquer et authentifier des informations publiques (comme le hachage d'un mot de passe ou d'un document), vous devez alors utiliser l'un des principaux algorithmes de hachage examinés par le public. Le salon des fonctions de hachage est un bon point de départ.

Ceci est un bon exemple et aussi un exemple de la raison pour laquelle vous ne voudriez jamais en écrire un.Il s'agit d'un hachage Fowler/Noll/Vo (FNV) qui est à la fois un génie informatique et un 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 générale est de ne pas rouler soi-même.Essayez d'utiliser quelque chose qui a été minutieusement testé, par exemple SHA-1 ou quelque chose du genre.

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

Étant donné le hachage d'un message, il est informatiquement impossible pour un attaquant de trouver un autre message de telle sorte que leurs hachages soient identiques.
Étant donné une paire de messages, m' et m, il est informatiquement impossible d'en trouver deux tels que h(m) = h(m')

Les deux cas sont pas le même.Dans le premier cas, il existe un hachage préexistant pour lequel vous essayez de trouver une collision.Dans le deuxième cas, vous essayez de trouver n'importe lequel deux messages qui se heurtent.La deuxième tâche est nettement plus facile en raison du « paradoxe » de l’anniversaire.

Lorsque les performances ne constituent 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 hachage.Si vous utilisez quelque chose de fort dès le départ, vous vous protégerez contre ceux-ci.

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

Un hasch plus moderne tel que Whirpool est un meilleur choix.Il ne souffre pas de ces attaques par extension de message et utilise les mêmes mathématiques qu'AES utilise pour prouver sa 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) chiffrement par bloc dans une fonction de compression unidirectionnelle (jamais essayé auparavant), comme AES en mode Miyaguchi-Preenel.Le problème, c'est qu'il faut :

1) avoir une intraveineuse.Essayez d'utiliser les 256 premiers bits des parties fractionnaires de la constante de Khinchin ou quelque chose comme ça.2) avoir un schéma de remplissage.Facile.Barrow-le à partir d'un hachage 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 pcb).

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow