Pourquoi XOR est-il la méthode par défaut pour combiner les hachages ?

Question

Disons que vous avez deux hachages H(A) et H(B) et vous voulez les combiner. J'ai lu qu'une bonne façon de combiner deux hachages est de XOR les, par exemple XOR( H(A), H(B) ) .

La meilleure explication que j'ai trouvée est abordée brièvement ici sur ces pages directives sur les fonctions de hachage :

L'association XOR de deux nombres dont la distribution est à peu près aléatoire donne un autre nombre dont la distribution est encore à peu près aléatoire*, mais qui dépend maintenant des deux valeurs.
...
* A chaque bit des deux nombres à combiner, un 0 est émis si les deux bits sont égaux, sinon un 1. En d'autres termes, dans 50% des combinaisons, un 1 sera émis. Ainsi, si les deux bits d'entrée ont chacun une chance sur deux d'être 0 ou 1, il en sera de même pour le bit de sortie.

Pouvez-vous expliquer l'intuition et/ou les mathématiques derrière la raison pour laquelle XOR devrait être l'opération par défaut pour combiner les fonctions de hachage (plutôt que OR ou AND, etc.) ?

Answer 1

En supposant des entrées uniformément aléatoires (1 bit), la distribution de probabilité de la sortie de la fonction ET est de 75%. 0 et 25 %. 1 . Inversement, OR est de 25 %. 0 et 75 %. 1 .

La fonction XOR est de 50%. 0 et 50 %. 1 Il permet donc de combiner des distributions de probabilité uniformes.

On peut le constater en écrivant des tables de vérité :

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

Exercice : Combien de fonctions logiques de deux entrées de 1 bit ? a et b ont cette distribution de sortie uniforme ? Pourquoi la fonction XOR est-elle la plus adaptée à l'objectif énoncé dans votre question ?

Answer 2

En dépit de ses propriétés pratiques de mélange de bits, XOR est pas un bon moyen de combiner des hachages grâce à sa commutativité. Imaginez ce qui se passerait si vous stockiez les permutations de {1, 2, , 10} dans une table de hachage de 10 tuples.

Un bien meilleur choix est m * H(A) + H(B) où m est un grand nombre impair.

Crédit : Le combineur ci-dessus est une astuce de Bob Jenkins.

Answer 3

Xor est peut-être la façon "par défaut" de combiner des hachages, mais la réponse de Greg Hewgill montre aussi pourquoi elle comporte des pièges : Le xor de deux valeurs de hachage identiques est égal à zéro. Dans la vie réelle, les hachages identiques sont plus fréquents qu'on ne l'aurait cru. Vous pourriez alors constater que dans ces cas de figure (pas si rares), les hachages combinés résultants sont toujours les mêmes (zéro). Les collisions de hachage seraient beaucoup, beaucoup plus fréquentes que prévu.

Dans un exemple inventé, vous pourriez combiner les mots de passe hachés des utilisateurs de différents sites Web que vous gérez. Malheureusement, un grand nombre d'utilisateurs réutilisent leurs mots de passe, et une proportion surprenante des hachages résultants est nulle !

Answer 4

Il y a quelque chose que je veux explicitement souligner pour les autres qui trouvent cette page. AND et OR limitent la sortie comme BlueRaja - Danny Pflughoe essaie de le souligner, mais peuvent être mieux définis :

Je veux d'abord définir deux fonctions simples que j'utiliserai pour expliquer tout cela : Min() et Max().

Min(A, B) renvoie la valeur la plus petite entre A et B, par exemple : Min(1, 5) renvoie 1.

Max(A, B) renverra la valeur la plus grande entre A et B, par exemple : Max(1, 5) renvoie 5.

Si on vous donne : C = A AND B

Alors vous pouvez trouver que C <= Min(A, B) Nous le savons parce qu'il n'y a rien que vous puissiez faire ET avec les bits 0 de A ou B pour en faire des 1. Ainsi, chaque bit zéro reste un bit zéro et chaque bit un a une chance de devenir un bit zéro (et donc une valeur plus petite).

Avec : C = A OR B

C'est le contraire qui est vrai : C >= Max(A, B) Avec cela, nous voyons le corollaire de la fonction AND. Tout bit qui est déjà à un ne peut pas être transformé par la fonction ET en un zéro, il reste donc à un, mais chaque bit à zéro a une chance de devenir un, et donc un nombre plus grand.

Cela implique que l'état de l'entrée applique des restrictions sur la sortie. Si vous faites un ET avec 90, vous savez que la sortie sera égale ou inférieure à 90, quelle que soit l'autre valeur.

Pour XOR, il n'y a pas de restriction implicite basée sur les entrées. Dans certains cas particuliers, si vous effectuez un XOR d'un octet avec 255, vous obtenez l'inverse, mais n'importe quel octet peut en sortir. Chaque bit a une chance de changer d'état en fonction du même bit dans l'autre opérande.

Answer 5

Si vous XOR une entrée aléatoire avec une entrée biaisée, la sortie est aléatoire. Il n'en va pas de même pour AND ou OR . Exemple :

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

Comme le mentionne @Greg Hewgill, même si les deux les entrées sont aléatoires, en utilisant AND ou OR entraînera une sortie biaisée.

La raison pour laquelle nous utilisons XOR sur quelque chose de plus complexe est que, eh bien, il n'y a pas besoin : XOR fonctionne parfaitement, et c'est incroyablement rapide.