Quelle est la plus courte paire de chaînes qui provoque une collision MD5?

Question

Jusqu'à ce que la longueur de la chaîne est-il possible d'utiliser MD5 hash sans avoir à vous soucier de la possibilité d'une collision?

Ce ne serait sans doute être calculé par la génération d'un hachage MD5 pour chaque chaîne de caractères dans un jeu de caractères particulier, en augmentant la longueur, jusqu'à ce qu'un hachage apparaît pour la deuxième fois (collision). La longueur maximale possible d'une chaîne sans collision aurait alors un caractère de moins que la plus longue de la collision paire.

A déjà été testés pour le MD5, SHA1, etc?

Answer 1

Mise à jour

Ironie du sort, quelques semaines après que j'ai posté la réponse précédente, les deux chercheurs Chinois, Tao Xie et Dengguo Feng, a publié un nouveau bloc unique de collision MD5. J'étais pas au courant de ce papier jusqu'à maintenant. Un seul MD5 bloc signifie que la taille de saisie est de 64 octets ou 512 bits. Notez que les entrées sont pour la plupart les mêmes, qui ne diffèrent que de 2 bits.

Leur méthodologie ne sera pas publiée jusqu'en janvier 2013, mais leur collision peut être vérifiée maintenant, en utilisant des nombres à partir de l'étude:

>>> from array import array
>>> from hashlib import md5
>>> input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array('I', [x^y for x,y in zip(input1,
    [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'
>>> md5(input2).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'

Mise à jour: Le livre a été publié en Mars 2013: Tao Xie et Fanbao Liu et Dengguo Feng - Rapide Collision Attaque sur MD5

Toutefois, si vous avez plus d'espace pour jouer avec, les collisions de quelques kilo-octets sont plus rapides à calculer, ils peuvent être calculées à l'intérieur des heures sur n'IMPORTE quel ordinateur.

Vieille réponse

Le précédent le plus court de collision utilisé au moins deux MD5 blocs de valeur de l'entrée -- c'est de 128 octets, 1 024 bits. Un préfixe dans le premier bloc peut être choisie arbitrairement par l'attaquant, le reste devrait être calculé et apparaissent comme du charabia.

Voici un exemple de deux entrées en collision, vous pouvez essayer vous-même en Python:

>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = 'Oded Goldreich\nOded Goldreich\nOded Goldreich\nOded Go' + unhexlify(
... 'd8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956')
>>> len(input1)
128
>>> md5(input1).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'
>>> input2 = 'Neal Koblitz\nNeal Koblitz\nNeal Koblitz\nNeal Koblitz\n' + unhexlify(
... '75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956')
>>> md5(input2).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'

La production de ces deux entrées a pris 2 jours sur un 215-nœud Playstation 3 cluster, par Mark Stevens :)

Answer 2

Les mathématiques de l' anniversaire paradoxe de faire le point d'inflexion de la probabilité de collision-peu-près à sqrt(N), où N est le nombre de catégories distinctes en fonction de hachage, donc pour un hachage de 128 bits, vous obtenez environ 64 bits vous êtes modérément susceptibles d'avoir 1 collision. Donc je suppose que pour la série complète de 8 chaînes d'octets, il est un peu susceptible d'avoir un impact, et pour les 9 chaînes d'octets, il est extrêmement probable.

edit: ce qui suppose que l'algorithme de hashage MD5 provoque une cartographie de l'entrée bytestring à la sortie de hachage qui est proche de "l'aléatoire". (par rapport à celui qui distribue les chaînes de façon plus égale entre les hachages, auquel cas il serait plus près de 16 octets.)

Aussi pour des chiffres plus précis réponse, si vous regardez l'une des approximations pour le calcul de la probabilité de collision, vous obtenez

p(k) ≈ 1 - e^{-k(k-1)/(2*2128)} où k = la taille de l'espace des entrées possibles = 2^m où l'entrée bytestring est de m bits.

l'ensemble des 8 chaînes d'octets: p(2⁶⁴) ≈ 1 - e^-0.5 ≈ 0.3935

l'ensemble des 9 chaînes d'octets: p(2⁷²) ≈ 1 - e^{-2144/(2*2128)} = 1 - e^-215 = 1 - e^-32768 ≈ 1

Notez également que ces assumer la complète ensemble de m/8 chaînes d'octets. Si vous utilisez uniquement des caractères alphanumériques, vous auriez besoin de plus d'octets pour obtenir une probable collision.

Answer 3

Je ne crois pas que cela a été fait, mais il pourrait être une expérience intéressante. Il n'a pas vraiment de sens pour toute utilisation de ces fonctions de hachage que je suis au courant, sauf pour PKCS1 signatures. Si vous êtes à la chaîne est plus petite que la sortie de la taille du bloc, alors ne prenez pas la peine de hachage. Ensuite, vous avez la garantie d'unicité.

EDIT: ahh, mais pour les mots de passe que vous avez besoin de cette fonctionnalité.

Answer 4

Je doute si il n'y a aucune longueur utile où vous n'allez pas avoir d'éventuelles collisions. Ces algorithmes ne sont pas vraiment utilisés à cette fin. Il est destiné à essayer d'être unique pour de légers changements dans les données (comme des fichiers corrompus) plutôt que d'unique à travers tous les jeux de données.