Quelle est la probabilité que les 4 premiers octets de hachage MD5 calculées à partir du contenu des fichiers entrent en collision?

Question

Il s'agit d'une question combinatoire avec une théorie des algorithmes de hachage requis.

Disons que l'entrée peut être n'importe quelle séquence aléatoire d'octets de 30 kb à 5 Mo de taille (je suppose que cela fait pas mal de combinaisons de valeurs d'entrée :))

Quelle est la probabilité que les 4 premiers octets (ou les premiers n octets) d'un hachage MD5 calculé à partir de la séquence d'octets seront les mêmes pour les fichiers distincts?

Dans le cas où cela ne peut pas être calculé spécifiquement pour le hachage MD5, alors quelle est la probabilité que toute fonction de hachage qui génère des hachages de congé M-Otet distribués uniformément calculera le hachage avec la collision sur les noctuels n pour les premiers octets pour une plage d'entrées donnée?

Answer 1

En l'absence de plus d'informations sur la probabilité des valeurs d'octets, je serais le jour où il est de 1 sur 2 ^ 32.

ÉDITER. En effet, 1 sur 2 ^ 16 si vous prenez les personnages hexadécimaux au lieu des octets purs.

ÉDITER Basé sur le commentaire:

MD5 peut-il être considéré comme uniforme que les valeurs calculées sont absolument aléatoires?

L'algorithme de hachage MD5 est conçu de sorte qu'un petit changement dans l'entrée se traduit par un hachage complètement différent, donc je dirais que les octets de hachage MD5 sont distribués avec une probabilité égale (je ne parierais rien de toute façon). Quoi qu'il en soit, vous pouvez appliquer un post-traitement à votre hachage (par exemple, vous pouvez utiliser clés MD5) pour augmenter son aléatoire (et le rendre plus sûr, d'ailleurs, puisque Les hachages simples MD5 se sont révélés peu sûrs).

Answer 2

Pour une fonction de hachage idéale, les sorties sont réparties uniformément, de sorte que les chances de deux collisions sont un en 2 ^ 32. Le paradoxe d'anniversaire, cependant, nous dit que si nous comparons toutes les paires de hachages, nous devrions nous attendre à voir une collision une fois que nous avons 2 ^ 16 hachages, alors ne comptez pas sur seulement 4 octets sur la base que "J'ai beaucoup moins de 4 milliards de valeurs".

MD5 n'est pas une fonction de hachage idéale, comme nous le savons, mais les faiblesses sont quelque peu accessoires ici: trouver une collision sur 4 octets est bien dans le domaine d'une attaque brute-force raisonnable, il n'est donc pas nécessaire de recourir aux faiblesses cryptographiques. Si vous êtes uniquement préoccupé par des données choisies au hasard, vous n'allez pas voir un écart statistique significatif par rapport au hasard.

Answer 3

Si vous êtes intéressé par les chances de deux entrées particulières ayant le même hachage de 4 octets, alors c'est seulement 1/2 ^ 32. Si vous êtes intéressé par les chances de deux entrées sur un ensemble de x entrées totales ayant les mêmes chances, cela reste assez bas jusqu'à ce que vous commencez à approcher 2 ^ 16 = 65536 entrées distinctes dans votre ensemble, où elle atteint près de 50% ( Ce phénomène est connu comme le paradoxe d'anniversaire).

En général, l'un des critères d'une fonction de hachage est utile cryptographiquement est l'uniformité de tous les bits.

Answer 4

Les chances d'une collision dans un hachage N bits sont d'environ 1 sur 2 ^ (n / 2) en raison du paradoxe d'anniversaire - donc environ 1 sur 2 ^ 16 dans ce cas. Si, pour une raison quelconque, vous faisiez référence à l'utilisation de 32 bits du codage hexagonal, bien sûr, ce ne serait que les 16 premiers bits réels, donc les chances d'une collision serait d'environ 1 sur 2 ^ 8.

Étant donné un fichier fixe spécifique, les chances que tout autre fichier choisi au hasard aura le même hachage que ce fichier est d'environ 2 ^ n. En termes de hachage cryptographique, la différence entre celles-ci est la première est une collision, l'autre est un préimage.

À cette taille de hachage, les faiblesses de MD5 sont assez hors de propos car les attaques les plus connues sur MD5 prennent environ 2 ^ 32 calculs, tandis que l'on peut générer une collision dans un hachage de 32 bits idéalement sécurisé dans environ 2 ^ 16 calculs (depuis par En choisissant simplement des entrées aléatoires, vous avez 1 sur 2 ^ 16 chances d'une collision, donc après environ 2 ^ 16 de supposer aléatoires, vous aurez probablement trouvé une paire d'entrées en collision).

Answer 5

Les hachages MD5 sont généralement des hexadécimaux, il y a donc 16 valeurs possibles pour chaque octet. Par conséquent, pour quatre octets, il y a 16 * 16 * 16 * 16 = 65536 combinaisons possibles, ce qui rend la probabilité d'une collision de hachage 1: 65536.

Answer 6

MD5 est hexadécimal, donc chaque personnage peut être l'un des 16 allèles. Alors ça ferait 16^n

Pour 4 caractères, cela fait 65536 combinaisons possibles possibles.