Hachage universel

En mathématiques et en informatique, le hachage universel, en anglais universal hashing, (dans un algorithme probabiliste ou un bloc de données) est une méthode qui consiste à sélectionner aléatoirement une fonction de hachage dans une famille de fonctions de hachages qui ont certaines propriétés mathématiques. Cela permet de minimiser la probabilité de collision de hachage. Plusieurs familles de fonctions de hachages sont connues (pour hacher des entiers, des chaînes de caractères ou des vecteurs), et leur calcul est souvent très efficace. Le hachage universel a de nombreux usages en informatique, par exemple dans l’implémentation des tables de hachage, les algorithmes probabilistes et le chiffrement de données.

Introduction

Supposons que nous désirions associer des clés provenant de l'univers $U$ à des fragments binaires $m$ (indexés $[m]=\{0,\dots ,m-1\}$). L'algorithme devra gérer des ensembles de données $S\subseteq U$ à partir des $|S|=n$ clés, qui n'est pas connu à l'avance. Habituellement le but du hachage est de minimiser le nombre de collisions (clés de $S$ qui ont la même image par la fonction). Une fonction de hachage déterministe ne peut pas offrir la garantie contre la création intentionnelle de collision si la taille de $U$ est plus grande que la taille de $m\cdot n$ par l'adversaire pour choisir $S$ de telle sorte qu'il soit l'antécédent d'un fragment. Cela donne un ensemble de clés qui donnent toutes le même hash, rendant le hachage virtuellement inutile. De plus une fonction de hachage déterministe ne se prête pas au rehachage qui peut être nécessaire si un trop grand nombre de collisions a été constaté.

La solution à ces problèmes est de choisir la fonction de hachage de manière aléatoire à partir d'une famille de fonctions de hachage. Une famille de fonctions $H=\{h:U\to [m]\}$ est appelée famille universelle si $\forall x,y\in U,~x\neq y:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m}}$.

En d'autres mots, deux clés prises au hasard dans l'univers ont une probabilité au plus de $1/m$ de donner une collision quand la fonction $h$ est tirée aléatoirement de $H$. C'est la probabilité à laquelle on s'attendrait si la fonction de hachage attribuait un hash de manière aléatoire à chaque clé. Parfois la définition est élargie pour accepter une probabilité de collision en $O(1/m)$. Ce concept a été introduit par Larry Carter et Mark N. Wegman (en) en 1977, et a trouvé de nombreuses applications en informatique). Si on a une borne supérieure $\epsilon <1$ sur la probabilité de collision, on parle de fonctions $\epsilon$-presque universelles.

Beaucoup mais pas toutes les fonctions de hachages universelles vérifient la propriété plus forte de différence uniforme :

$\forall x,y\in U,~x\neq y$, si $h$ est tiré aléatoirement parmi $H$, la différence $h(x)-h(y)~{\bmod {~}}m$ est uniformément distribuée dans $[m]$.

Notez que la définition de l'universalité ne s’intéresse qu'aux cas de collisions ($h(x)-h(y)=0$) alors que la propriété de différence uniforme est plus forte.

De façon similaire, une famille universelle peut être XOR-universelle si $\forall x,y\in U,~x\neq y$, la valeur de $h(x)\oplus h(y)~{\bmod {~}}m$ est uniformément distribué dans $[m]$ avec $\oplus$ l'opération ou exclusif bit à bit. Ceci n'est possible que dans le cas où $m$ est une puissance de deux.

Une autre condition plus forte que l'universalité est l'indépendance par paires : Cette propriété est obtenue si $\forall x,y\in U,~x\neq y$ on a la probabilité que $x,y$ donne une paire de hashs $z_{1},z_{2}$ soit la même que si cette paire de hash était calculée d'une manière parfaitement aléatoire : $P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}$. L'indépendance par paire est parfois appelée universalité forte.

Une autre propriété est l'uniformité. On dit qu'une famille est uniforme si tous les hashs possibles sont équiprobables en d'autres termes $P(h(x)=z)=1/m$ pour toute valeur de hash $z$. L'universalité n'implique pas l'uniformité mais l'universalité forte si.

À partir d'une famille vérifiant la propriété de distance uniforme on peut créer une famille de fonctions de hachage fortement universelle de fonction de hachage, c'est-à-dire une famille de fonction de hachage indépendantes deux à deux en ajoutant à chaque fonction de la famille mère une constante aléatoire uniformément distribuée à valeurs dans $[m]$. Si $m$ est une puissance de 2, on peut créer cette famille indépendante par une opération XOR avec une constante aléatoire uniformément distribuée. Étant donné que le décalage d'une constante n'a pas forcément d'importance dans certaines applications (par exemple les tables de hachage), la distinction nette entre la propriété de distance uniforme et l'indépendance paire à paire n'est pas toujours effectuée.

Pour certaines applications comme les tables de hachage, il est important que les bits les moins significatifs du hash soient eux aussi universels. Quand une famille est fortement universelle, cette propriété est garantie : si $H$ est une famille fortement universelle avec $m=2^{L}$ alors la famille faite avec les fonctions $h{\bmod {2^{L'}}}$ pour $h\in H$ est également fortement universelle pour $L'\leq L$. Cette propriété n'est pas vraie en général pour les familles universelles. Par exemple la famille faites avec les fonctions identité $h(x)=x$ est clairement universelle mais la famille faite des fonctions $h(x)=x{\bmod {2^{L'}}}$ ne l'est pas.

UMAC, Poly1305 (en)-AES et quelques autres algorithmes de codes d'authentification de message se basent sur le hachage universel. Dans ces applications, le logiciel sélectionne une nouvelle fonction de hachage pour chaque message, basé sur un identifiant unique généré pour le hachage du message.

Plusieurs implémentations de tables de hachage utilisent le hachage universel. Dans ces applications, typiquement, le logiciel ne prend une nouvelle fonction de hachage que s'il note que trop de clés ont produit une collision; sinon la même fonction de hachage reste utilisée. Certains schémas de résolution de collision, comme le hachage dynamique parfait, changent de fonction de hachage à la première collision observée. Les autres méthodes de résolution de collision comme la méthode du coucou et le 2-choice hashing, autorisent un certain nombre de collisions avant de changer de fonction de hachage.

Garanties mathématiques

Pour n'importe quel ensemble $S$ de $n$ clés, utiliser une famille universelle garantit les propriétés suivantes :

1. Pour tout $x$ de $S$, le nombre de clés pour le hash $h(x)$ est $n/m$. En implémentant des tables de hachage par un chaînage, ce nombre est proportionnel au temps de calcul pour une opération basée sur une clé (recherche, insertion ou suppression).
2. Le nombre de paires de clé $x,y$ de $S$ qui produisent des collisions ($x\neq y$ et $h(x)=h(y)$) est majoré par $n(n-1)/2m$ qui est de l'ordre de $O(n^{2}/m)$. Dans le cas du hachage de $n^{2}$ entrées, il y a une probabilité supérieure à 1/2 de n'avoir aucune collision.
3. Le nombre de clés qui dans les fragments de au moins $t$ clés est majoré par $2n/(t-2(n/m)+1)$. Ainsi la capacité de chaque fragment est limitée à trois fois la taille moyenne ($t=3n/m$), le nombre total de clés dans les fragments qui dépassent la moyenne est au plus $O(m)$. Cette propriété ne tient que pour une famille de fonctions de hachage où la probabilité de collision est majorée par $1/m$. Si une définition plus faible est utilisée et qu'on se contente d'une majoration en $O(1/m)$, alors ce résultat n'est plus valable.

Les garanties ci-dessus sont valables pour n'importe quel ensemble $S$ donné, elles tiennent même si le jeu de données à hacher a été sélectionné par un attaquant. Cependant, comme l'attaquant crée son jeu de données avant que l'algorithme n'ait fait sa sélection de fonction de hachage aléatoire, si l'attaquant peut deviner les fonctions qui seront sélectionnées par l'algorithme, la sélection aléatoire n'apporte rien par rapport au hachage déterministe.

La deuxième et la troisième garantie sont typiquement utilisées en conjonction avec un rehachage. Par exemple, un algorithme probabiliste peut être sélectionné pour un taux de collision attendu de $O(n)$. Si trop de collisions sont observées, un autre algorithme $h$ de la famille est sélectionné de manière aléatoire et le traitement est répété. L'universalité garantit que le nombre de répétition est une variable aléatoire géométrique.

Constructions

Étant donné que les informations sont représentées en machine par des mots, les hachages peuvent être réduit à trois situations : un mot (un entier, integer en anglais) ; un vecteur de mots de taille fixée ; et un vecteur de taille variable assimilé à une chaîne de mots informatiques/caractères (string en anglais).

Hachage d'entiers

Cette section se réfère au cas du hachage d'entiers qui tiennent dans un mot machine. Dans ce cas les opérations addition, multiplication, et division sont exécutées directement sur le processeur et coûtent très peu de ressources. À partir de ce point on considère l'univers à hacher $U=\{0,\dots ,m-1\}$.

La proposition initiale de Carter et Wegman était de choisir un entier premier $p\geq m$ et définir

$h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m$

où $a,b$ est un couple d'entiers choisis aléatoirement modulo $p$ avec $a\neq 0$. (Cela correspond à un pas d'itération d'un générateur congruentiel linéaire.)

Pour vérifier que $H=\{h_{a,b}\}$ est bien une famille universelle, notez que $h(x)=h(y)$ ne tient que si

$ax+b\equiv ay+b+i\cdot m{\pmod {p}}$

pour un certain entier $i$ compris entre $0$ et $(p-1)/m$. Si leur différence, $x\neq y$, est non nulle et possède un inverse modulo $p$. Chercher $a$ revient à résoudre :

$a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}$.

Il y a $p-1$ choix possibles pour $a$ ($a=0$ est exclu) et pour $i$pris dans l'intervalle autorisé, il y a $\lfloor (p-1)/m\rfloor$ valeurs pour les côtés droits et gauche. La probabilité de collision est alors de

$\lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m$.

Une autre manière de prouver que $H$ est une famille universelle passe par la notion de distance statistique. On écrit la différence $h(x)-h(y)$ comme :

$h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}$.

Étant donné que $x-y$ est non nul et que $a$ est uniformément distribué dans $\{1,\dots ,p\}$, on déduit que $a(x-y)$ modulo $p$ est aussi uniformément distribué dans $\{1,\dots ,p\}$. La distribution de $(h(x)-h(y))~{\bmod {~}}m$ est ainsi presque uniforme, avec une différence de probabilité au maximum de $\pm 1/p$ entre les échantillons. Il en résulte que la distance statistique à une famille uniforme est $O(m/p)$, qui devient négligeable quand $p\gg m$.

La famille la plus simple de fonctions de hachage, $h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m$, est seulement approximativement universelle : $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ pour tout $x\neq y$. De plus, cette analyse est assez fine ; Carter et Wegman ont montré que $\Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)$ pour tout $(p-1)~{\bmod {~}}m=1$.

Éviter le calcul modulaire

La méthode la plus populaire dans le hachage d'entier est la méthode « multiplie et décale » décrit par Dietzfelbinger et al. en 1997. En évitant l'arithmétique modulaire, cette méthode est plus simple à implémenter et est significativement plus rapide en pratique (usuellement plus rapide d'un facteur 4)).

Cette méthode suppose que le nombre de fragments binaires soit une puissance de deux, $m=2^{M}$. Soit $w$ le nombre de bits dans un mot machine. Les fonctions de hachage sont paramétrées par des entiers positifs impairs $a<2^{w}$ (qui tiennent dans un mot de $w$ bits). Pour calculer $h_{a}(x)$, on multiplie $x$ par $a$ modulo $2^{w}$ et ensuite on garde les $M$ bits de poids fort du résultat comme hash. En notation mathématique cela s'écrit :

$h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}$

et peut être implémenté dans un langage de la famille du C par le code :

$h_{a}(x)=$ (unsigned) (a*x) >> (w-M)

Ce schéma ne satisfait pas la propriété de différence uniforme et est seulement $2/m$-presque-universel ; pour tout $x\neq y$, $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$.

Pour comprendre le comportement de la fonction de hachage, remarquez que si $ax{\bmod {2}}^{w}$ et $ay{\bmod {2}}^{w}$ ont les mêmes 'M' bits de poids fort alors $a(x-y){\bmod {2}}^{w}$ n'a que des 1 ou que des 0 dans ses 'M' bits de poids fort (cela dépend du maximum entre $ax{\bmod {2}}^{w}$ et $ay{\bmod {2}}^{w}$). Supposons maintenant que les bits de poids faible de $x-y$ apparaissent en position $w-c$. Comme $a$ est un entier impair et que les entiers impairs possèdent un inverse dans l'anneau $Z_{2^{w}}$, on déduit que $a(x-y){\bmod {2}}^{w}$ sera uniformément distribué parmi les entiers de $w$ bits avec le bit de poids le plus faible situé à la position $w-c$. La probabilité que ces bits soient tous égaux à 0 ou à 1 est donc au plus de $2/2^{M}=2/m$. D'autre part si $c<M$, alors les M bits de poids fort de $a(x-y){\bmod {2}}^{w}$ contiennent des 0 et des 1 et on est certain que $h(x)\neq h(y)$. Finalement, si $c=M$ alors le bit $w-M$ de $a(x-y){\bmod {2}}^{w}$ vaut 1 et $h_{a}(x)=h_{a}(y)$ si et seulement si les bits $w-1,\ldots ,w-M+1$ valent également 1, ce qui arrive avec la probabilité de $1/2^{M-1}=2/m$.

Cette analyse est difficile, comme on peut le constater avec les exemples $x=2^{w-M-2}$ et $y=3x$. Pour obtenir une fonction de hachage 'vraiment' universelle, on peut utiliser la méthode multiplie et additionne.

$h_{a,b}(x)=((ax+b){\bmod {2}}^{w})\,\mathrm {div} \,2^{w-M}$

qui peut être implémenté en langages de la famille du C par

$h_{a,b}(x)=$ (unsigned) (a*x+b) >> (w-M)

où $a$ est un entier pair positif tiré aléatoirement, $a<2^{w}$, et $b$ un entier positif tiré aléatoirement $b<2^{w-M}$. Avec ce choix de $a$ et $b$, $\Pr\{h_{a,b}(x)=h_{a,b}(y)\}\leq 1/m$ pour tout $x\not \equiv y{\pmod {2^{w}}}$. Ceci diffère légèrement, mais sur un point important, de l'erreur de traduction de l'article en anglais.

Hachage de vecteurs

Cette section concerne le hachage de vecteur de mots dont la longueur est fixée à l'avance. Interpréter l'entrée comme un vecteur ${\bar {x}}=(x_{0},\dots ,x_{k-1})$ de $k$ mots machine (entiers de $w$ bits chacun). Si $H$ est une famille universelle qui vérifie la propriété de différence uniforme, la famille suivante, trouvée par Carter et Wegman, possède également la propriété de différence uniforme (et donc est universelle) :

$h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m$, où chaque $h_{i}\in H$ est choisi de manière aléatoire et indépendante.

Si $m$ est une puissance de deux, la somme peut être remplacée par une opération ou exclusif.

En pratique si l'arithmétique en double précision est disponible, on utilise la famille de fonction de hachage « multiplie et décale ». On initialise la fonction avec un vecteur ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ d'entiers pairs de $2w$ bits de long. Ensuite si le nombre de fragments est $m=2^{M}$, avec $M\leq w$

$h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$.

Il est possible de diviser le nombre de multiplication par 2, ce qui se traduit par un calcul à peu près deux fois plus rapide en pratique. Initialiser la fonction de hachage avec un vecteur ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ de nombres entiers impairs chacun de $2w$ bits de long. La famille de hachage ainsi produite est universelle :

$h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$.

Si les opérations en double précision ne sont pas disponibles, on peut interpréter l'entrée comme un vecteur de demi-mots (des entiers de $w/2$ bits de longs). L'algorithme va alors utiliser $\lceil k/2\rceil$ multiplications, avec k le nombre de demi mots du vecteur. Ainsi l'algorithme tourne à un "taux" d'une multiplicatio par mot d'entrée.

Ce schéma peut également être utilisé pour hacher des entiers en considérant que leurs bits sont un vecteur d'octets. Dans cette variante, la technique est appelée hachage tabulaire et fournit une alternative pratique aux fonctions de hachage universelle basées sur des multiplications.

L'universalité forte à grande vitesse est également possible. Initialiser la fonction de hachage avec un vecteur ${\bar {a}}=(a_{0},\dots ,a_{k})$ d'entiers pris au hasard de $2w$ bits de long. Calculer :

$h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}$.

Le résultat est fortement universel sur $w$ bits. Expérimentalement cette méthode consomme 0.2 cycle CPU par octet sur les dernières puces Intel pour $w=32$.

Hachage de chaînes

Cette section vise le cas de vecteur de mots de taille variable. Si la taille de la chaîne peut être majorée par un petit nombre, il est préférable d'utiliser la méthode avec des vecteurs de taille définie en complétant la chaîne à hacher par des zéros au besoin. L'espace mémoire requis pour le calcul est la longueur maximale de la chaîne, mais le temps de calcul dépend uniquement de la longueur de $h(s)$. Tant qu'on interdit les zéros dans la chaîne, on peut ignorer le remplissage d'une chaîne par des zéros terminaux sans que la propriété d'universalité en soit affectée. Noter que si on autorise la présence de zéros dans la chaîne alors le problème d'ajout de zéros terminaux se règle en choisissant d'ajouter un caractère non nul, qui balisera la fin de la chaîne à toutes les chaînes en entrée avant le traitement.

Maintenant supposons qu'il faille hacher ${\bar {x}}=(x_{0},\dots ,x_{\ell })$, sans qu'on puisse avoir d'estimation correcte de $\ell$. Une famille de hachage universelle traite la chaîne $x$ comme les coefficients d'un polynôme modulo un grand nombre premier. Si $x_{i}\in [u]$, soit $p\geq \max\{u,m\}$ un nombre premier, on définit :

$h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{i}{\big )}{\bmod {~}}p\right)$, où $a\in [p]$ est uniformément aléatoire et $h_{\mathrm {int} }$ est tiré aléatoirement d'une famille aléatoire universelle qui indexe l'ensemble des entiers $[p]\mapsto [m]$.

En utilisant les propriétés de l'arithmétique modulaire, la formule ci-dessus peut être calculée sans produire de grands nombres par le code suivant :

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

L'algorithme ci-dessus est également connu en tant que fonction de hachage multiplicative. En pratique l'opérateur modulo et le paramètre p peuvent être évités tous les deux simplement en autorisant les entiers à dépasser leur taille maximale (overflow) car cette opération est équivalente à un modulo MAX_INT_VALUE + 1 dans beaucoup de langages de programmation. Ci-dessous, un tableau de valeurs choisies pour initialiser h dans quelques implémentations populaires.

Implementation	INITIAL_VALUE	a
Bernstein's hash function djb2	5381	33
STLPort 4.6.2	0	5
La fonction de hachage de Kernighan et Ritchie	0	31
java.lang.String.hashCode()	0	31

Soient deux chaînes ${\bar {x}},{\bar {y}}$ et $\ell$ la taille de la plus longue des deux ; pour les besoins de l'analyse on supposera que la seconde chaîne est complétée par des zéros jusqu'à atteindre la longueur $\ell$. Une collision avant d'appliquer $h_{\mathrm {int} }$ implique que $a$ est une racine du polynôme dont les coefficients sont ${\bar {x}}-{\bar {y}}$. Ce polynôme a au plus $\ell$ racines modulo $p$, donc la probabilité de collision est au plus de $\ell /p$. La probabilité de collision à travers l'aléa $h_{\mathrm {int} }$ descend la probabilité totale de collision à ${\frac {1}{m}}+{\frac {\ell }{p}}$. Ainsi si le nombre premier $p$ est suffisamment grand comparé à la longueur des chaînes à hacher, la famille est très proche d'une famille universelle (en termes de distance statistique).

Éviter l'arithmétique modulaire

Pour limiter la consommation de ressources par les calculs d'arithmétique modulaire, deux astuces sont utilisées en pratique :

1. On peut choisir le nombre premier $p$ proche d'une puissance de 2, un nombre premier de Mersenne par exemple. Cela permet d'implémenter les opérations de modulo sans utiliser de division (en utilisant des opérations plus rapides comme les additions et les décalages de bits). Par exemple sur des architectures modernes on peut travailler avec $p=2^{61}-1$, alors que les $x_{i}$ sont stockés sur 32 bits.
2. On peut appliquer un hachage vectoriel sur des blocs de données de l'entrée. Par exemple, on hache l'entrée par vecteurs de 16 mots et on applique le hachage de chaîne aux $\lceil k/16\rceil$ hashs obtenus. Le hachage de chaîne, très lent, étant appliqué à un ensemble de données significativement plus petit le calcul devient presque aussi rapide que le hachage vectoriel.
3. On peut choisir une puissance de deux comme diviseur ce qui permet de réduire l'opération modulo à un masquage de bits plus rapide que les divisions. La famille de fonctions NH utilise cette méthode.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Universal_hashing » (voir la liste des auteurs).

Voir aussi

Articles connexes

• K-independent hashing (en)
• Rolling hash (en)
• Tabulation hashing (en)
• MinHash (en)
• Fonction de hachage universelle à sens unique
• Suite à discrépance faible
• Fonction de hachage parfait

Bibliographie

(en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition]

Liens externes

(en) Open Data Structures - Section 5.1.1 - Multiplicative Hashing