En mathématiques et en informatique, le hachage universel, en anglais , (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 à des fragments binaires (indexés ). L'algorithme devra gérer des ensembles de données à partir des clés, qui n'est pas connu à l'avance. Habituellement le but du hachage est de minimiser le nombre de collisions (clés de 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 est plus grande que la taille de par l'adversaire pour choisir 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 est appelée famille universelle si .

En d'autres mots, deux clés prises au hasard dans l'univers ont une probabilité au plus de de donner une collision quand la fonction est tirée aléatoirement de . 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 . Ce concept a été introduit par Larry Carter et . en 1977, et a trouvé de nombreuses applications en informatiqueVoir par exemple .). Si on a une borne supérieure sur la probabilité de collision, on parle de fonctions -presque universelles.

Beaucoup mais pas toutes les fonctions de hachages universelles vérifient la propriété plus forte de différence uniforme : , si est tiré aléatoirement parmi , la différence est uniformément distribuée dans .

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

De façon similaire, une famille universelle peut être XOR-universelle si , la valeur de est uniformément distribué dans avec l'opération ou exclusif bit à bit. Ceci n'est possible que dans le cas où 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 on a la probabilité que donne une paire de hashs soit la même que si cette paire de hash était calculée d'une manière parfaitement aléatoire : . 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 pour toute valeur de hash . 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 . Si 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 est une famille fortement universelle avec alors la famille faite avec les fonctions pour est également fortement universelle pour . Cette propriété n'est pas vraie en général pour les familles universelles. Par exemple la famille faites avec les fonctions identité est clairement universelle mais la famille faite des fonctions ne l'est pas.

UMAC, -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 de clés, utiliser une famille universelle garantit les propriétés suivantes : Pour tout de , le nombre de clés pour le hash est . 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). Le nombre de paires de clé de qui produisent des collisions ( et ) est majoré par qui est de l'ordre de . Dans le cas du hachage de entrées, il y a une probabilité supérieure à 1/2 de n'avoir aucune collision. Le nombre de clés qui dans les fragments de au moins clés est majoré par .. Ainsi la capacité de chaque fragment est limitée à trois fois la taille moyenne (), le nombre total de clés dans les fragments qui dépassent la moyenne est au plus . Cette propriété ne tient que pour une famille de fonctions de hachage où la probabilité de collision est majorée par . Si une définition plus faible est utilisée et qu'on se contente d'une majoration en , alors ce résultat n'est plus valable.

Les garanties ci-dessus sont valables pour n'importe quel ensemble 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 . Si trop de collisions sont observées, un autre algorithme 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étitions 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, 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 ( 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 .

La proposition initiale de Carter et Wegman était de choisir un entier premier et définir

où est un couple d'entiers choisis aléatoirement modulo avec . (Cela correspond à un pas d'itération d'un générateur congruentiel linéaire.)

Pour vérifier que est bien une famille universelle, notez que ne tient que si

pour un certain entier compris entre et . Si leur différence, , est non nulle et possède un inverse modulo . Chercher revient à résoudre : .

Il y a choix possibles pour ( est exclu) et pour pris dans l'intervalle autorisé, il y a valeurs pour le côté droit. La probabilité de collision est alors de

.

Une autre manière de prouver que est une famille universelle passe par la notion de distance statistique. On écrit la différence comme :

.

Étant donné que est non nul et que est uniformément distribué dans , on déduit que modulo est aussi uniformément distribué dans . La distribution de est ainsi presque uniforme, avec une différence de probabilité au maximum de entre les échantillons. Il en résulte que la distance statistique à une famille uniforme est , qui devient négligeable quand .

La famille la plus simple de fonctions de hachage, , est seulement approximativement universelle : pour tout . De plus, cette analyse est assez fine ; Carter et Wegman ont montré que pour tout .

É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, . Soit le nombre de bits dans un mot machine. Les fonctions de hachage sont paramétrées par des entiers positifs impairs (qui tiennent dans un mot de bits). Pour calculer , on multiplie par modulo et ensuite on garde les bits de poids fort du résultat comme hash. En notation mathématique cela s'écrit :

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

(unsigned) (a*x) >> (w-M)

Ce schéma ne satisfait pas la propriété de différence uniforme et est seulement -presque-universel ; pour tout , .

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

Cette analyse est difficile, comme on peut le constater avec les exemples et . Pour obtenir une fonction de hachage 'vraiment' universelle, on peut utiliser la méthode multiplie et additionne.

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

(unsigned) (a*x+b) >> (w-M)

où est un entier pair positif tiré aléatoirement, , et un entier positif tiré aléatoirement . Avec ce choix de et , pour tout .. Ceci diffère légèrement, mais sur un point important, de l'erreur de traduction de l'article en anglais..

Hachage de vecteurs