Il s'agit d'une question de combinatorisation avec une théorie dans les algorithmes de hachage requises.
Disons que l'entrée peut être une séquence aléatoire d'octets 30 ko à 5 Mo de taille (je suppose que cela fait quelques combinaisons de valeurs d'entrée :))
Quelle est la probabilité que les 4 premiers octets (ou les premiers n octets) d'un hachage de MD5 calculé à partir de la séquence d'octets soient les mêmes pour les fichiers distincts?
Si cela ne peut pas être calculé spécifiquement pour le hachage MD5, quelle est la probabilité que toute fonction de hachage qui génère des hachages de M-octets uniformément distribuées calculera hachage avec une collision sur les premiers n octets pour une plage d'entrées donnée?
6 Réponses :
En l'absence de plus d'informations sur la probabilité de valeurs d'octets, je voudrais le jour 1 sur 2 ^ 32.
MD5 peut être considéré comme un uniforme
que les valeurs calculées sont
absolument aléatoire?
L'algorithme de hachage MD5 est conçu de manière à ce qu'un petit changement dans l'entrée entraîne un hachage complètement différent, je dirais donc 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 Keyed MD5 ) pour augmenter son aléatoire (et la rendre plus sécurisée, à la manière, depuis Les hachages de MD5 ordinaires ont été prouvés être insécurité ).
?? Changer la représentation des octets en caractères hexadécimaux change les probabilités. Cela ne calcule pas.
Eh bien, cela dépend de "les 4 premiers octets" signifiant le premier réel 4 octets ou les 4 premiers chiffres de la représentation hexagonale du hachage.
Merci pour la clarification. Votre réponse (et autre que dire 1/65536 est la probabilité) prendre en compte le paradoxe anniversaire?
@Marek: Le paradoxe d'anniversaire s'applique aux collections, pas de paires. La chance donnée ici est correcte pour une paire de fichiers. Puisque nous ne savons pas combien de fichiers il y a au total, la chance totale est inconnue.
Les hachages MD5 sont typiquement 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, faisant la probabilité d'une collision de hachage 1: 65536.
Ils sont affichés à des humains en hexadécimales, mais sont calculés comme 4 dordes, il se réfère donc au premier Dword. qui est 4 octets == 2 ^ 32
Merci pour une réponse rapide. Cependant, cela prend-il en compte des propriétés spécifiques de MD5? Le MD5 peut-il être considéré comme un uniforme qu'une valeur calculée est absolument aléatoire? La probabilité de collision n'est-elle pas plus grande spécifiquement pour MD5 par rapport à la fonction de hachage idéale qui est absolument uniforme?
À condition que l'entrée soit «absolument aléatoire», il est raisonnable de supposer que la production serait «absolument aléatoire» également. Les fonctions de hachage sont conçues pour être uniformes, donc en pratique, il est prudent d'assumer l'uniformité, à moins que l'entrée ne soit spécifiquement conçue pour provoquer des collisions avec la fonction de hachage donnée.
MD5 est hexadécimal, chaque caractère peut donc être l'un des 16 allèles.
Donc cela ferait Pour 4 caractères, cela fait 65536 combinaisons différentes possibles. 16 ^ n
Pour une fonction de hachage idéale, les sorties sont réparties de manière uniforme, de sorte que les chances de deux collisions sont un sur 2 ^ 32. Le paradoxe d'anniversaire nous dit cependant que si nous comparons toutes les paires de hashes, nous devrions nous attendre à voir une collision une fois que nous avons 2 ^ 16 hachage, en moyenne - ne comptez donc 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 raisonnable de force brute, donc il n'y a donc pas besoin de recourir à faiblesses cryptographiques. Si vous n'êtes préoccupant que de données choisies au hasard, vous n'allez pas voir une déviation statistique importante du hasard.
Si vous êtes intéressé par les chances de deux entrées particulières ayant le même hachage de 4 octets, il ne suffit que 1/2 ^ 32. Si vous êtes intéressé par les chances de deux entrées d'un ensemble de X Entrées totales ayant les mêmes chances, cela reste assez faible jusqu'à ce que vous commencez à approcher 2 ^ 16 = 65536 entrées distinctes dans votre ensemble, où il 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 à être cryptographique est l'uniformité de tous les bits.
Les chances d'une collision dans un hachage N-bits sont d'environ 1 sur 2 ^ (n / 2) en raison de la Paradoxe d'anniversaire - donc environ 1 sur 2 ^ 16 dans ce cas. Si, pour une raison quelconque, vous vous référez à utiliser 32 bits de l'encodage hexagonal, ce ne serait bien sûr que les 16 premiers bits réels, alors les chances d'une collision seraient d'environ 1 sur 2 ^ 8.
Compte tenu d'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 hashes cryptographiques, la différence entre ceux-ci est la première est une collision, l'autre est un prétimage.
à cette taille de hachage, les faiblesses de MD5 sont assez non pertinentes car les attaques les plus connues sur MD5 prennent environ 2 μm de calcul, tandis que l'on peut générer une collision dans un hachage 32 bits idéalement sécurisé en environ 2 ^ 16 (Depuis simplement choisir des entrées aléatoires, vous avez 1 chance sur 2 ^ 16 de collision, donc après environ 2 ^ 16 Guessé aléatoires, vous aurez probablement trouvé une paire d'entrées en collision).
+1. Une bonne réponse, la distinction entre trouver une collision (complexité paradoxe anniversaire) et un autre fichier que les hachages au même digest (deuxième prétimage) sont importants.
Clarification: Veuillez ne pas commenter la sécurité de MD5. Le problème que j'essaie de résoudre est comment détecter des fichiers identiques, pas la sécurité liée à la sécurité.
La récente mise en œuvre de ZFS DÉDUCTION a conduit à des idées intéressantes; Les collisions de hachage ont causé une attaque intéressante là-bas. Si vous pouvez connaître un fichier que vous venez de créer est identique à un autre fichier, vous vaincre efficacement System System Security. En fait, le système de fichiers insécurité Il y avait une conséquence directe de SHA256 Security - Si vous aviez des hachage de SHA256 identiques, vous savez à peu près que vous aviez des fichiers identiques.
Pouvez-vous s'il vous plaît clarifier ce que vous voulez dire avec des octets? Quand un hachage commence par "E8: F0: D3: 03: ..." Les quatre premiers octets "E 8 F 0" ou "E8 F0 D3 03"?
Je suis surpris qu'aucun des commentaires n'a mentionné ici la question de l'en-tête de fichier. Si vous travaillez avec un type commun comme Excel, Word, AutoCAD, JPG, etc., ils ont connu des en-têtes de fichiers qui seraient probablement considérablement augmenter le taux de collision.