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

Il n'y a pas une telle chose comme une "bonne fonction de hachage" universel hachages (ed. Oui, je sais qu'il y a quelque chose comme le "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 il n'est pas du tout bon pour les tables de hachage que vous voulez probablement dire.

ont des exigences très différentes. Mais quand même, trouver une bonne fonction de hachage universellement est difficile parce que différents types de données exposent différentes informations qui peuvent être hachurées. En règle générale, il est bon de considérer tous informations qu'un type détient é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 de problème, c'est-à-dire tous les objets possibles. Cela signifie que lorsque le hachage des nombres entre 100 et 1050 il n'est pas bon de laisser le chiffre le plus significatif jouer un grand rôle dans le hachage parce que 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 des chaînes, il est important de considérer tous les caractères – sauf s'il est connu à l'avance que les trois premiers caractères de toutes les chaînes seront les mêmes; considérer ceux-ci est alors une perte.

c'est en fait l'un des cas où je conseille de lire ce que Knuth doit say in The Art of Computer Programming , vol. 3. Une autre bonne lecture est de Julienne Walker " The Art of Hashing .

il y a deux buts principaux des fonctions de hachage:

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

il est impossible de recommander un hachage sans savoir à quoi il sert.

si vous faites juste une table de hachage dans un programme, alors vous n'avez pas besoin de vous soucier de la réversibilité ou de la possibilité de hacker l'algorithme... SHA-1 or AES est tout à fait inutile pour cela, vous seriez mieux d'utiliser un variation de la FNV . FNV permet une meilleure dispersion (et donc moins de collisions) qu'un simple premier mod comme vous l'avez mentionné, et il est plus adaptable aux différentes tailles d'entrée.

si vous utilisez les hachures pour cacher et authentifier des informations publiques (telles que le hachage d'un mot de passe, ou d'un document), alors vous devriez utiliser l'un des algorithmes majeurs de hachage vérifié par un examen public. de La Fonction de Hachage Salon est un bon endroit pour commencer.

ceci est un exemple d'un bon et aussi un exemple de pourquoi vous ne voudriez jamais en écrire un. C'est un Hash Fowler / Noll / Vo (FNV) qui est à parts égales génie informatique et voodoo pur:

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

Edit:

• 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 dans le hachage. J'ai ajusté l'algorithme en conséquence.

je dirais que la principale règle est de ne pas rouler votre propre. Essayez d'utiliser quelque chose qui a été testé en profondeur, par exemple SHA-1 ou quelque chose dans le même sens.

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

1. étant donné le hachage d'un message, il est infaisable pour un attaquant de trouver un autre message tel que leurs hachages sont identiques.

2. avec une paire de messages, m' et m, il est infaisable de trouver deux tels que h (m) = h (m')

les deux cas sont pas le même. Dans le premier cas, il y a un hachage préexistant pour lequel vous essayez de trouver une collision. Dans le second cas, vous essayez de trouver n'importe quel deux messages qui entrent en collision. La deuxième tâche est nettement plus facile en raison du paradoxe de l'anniversaire."

lorsque la performance n'est pas un grand problème, vous devez toujours utiliser une fonction de hachage sécurisée. Il y a des attaques très intelligentes qui peuvent être effectuées en forçant les collisions dans une table de hachage. Si vous utilisez quelque chose de fort dès le début, vous vous protéger contre ces.

N'utilisez pas MD5 ou SHA-1 dans les nouveaux modèles. La plupart des cryptographes, moi y compris, les considéreraient comme cassés. La principale source de faiblesse dans ces deux conceptions est que la seconde propriété, que j'ai décrit ci-dessus, ne tient pas pour ces constructions. Si un attaquant peut générer deux messages m et m', que les deux de hachage à la même valeur qu'ils peuvent utiliser ces messages contre vous. SHA-1 et MD5 souffrent également d'attaques d'extension de message, qui peuvent affaiblir fatalement votre application si vous n'êtes pas prudent.

un hash plus moderne comme Whirpool est un meilleur choix. Il ne souffre pas de ces attaques d'extension de message et utilise les mêmes mathématiques que AES utilise pour prouver la sécurité contre une variété d'attaques.

Espère que ça aide!

ce que vous dites ici est que vous voulez en avoir un qui utilise une résistance à la collision. 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:



Un 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 rembourrage. Facile. Barrow il provient 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 qui reccomends lookup2) essayez aussi MurmurHash, c'est rapide (vérifiez ceci: .16 cpb).