Quelles sont les chances que deux messages ont le même MD5 et le même SHA1 digérer?

Question

Étant donné deux messages différents, A et B (peut-être 20 à 80 caractères d'un texte, si la taille de l'importance à tous), quelle est la probabilité que la somme MD5 d'Un est la même que la somme MD5 de B et le SHA1 d'une empreinte de Un est le même que le SHA1 d'une empreinte de B? C'est:

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

N'assumons aucune intention malveillante, c'est à dire, que les messages ne sont pas sélectionnés dans le but de trouver un "clash". Je veux juste savoir les chances que cela se produise naturellement.

Je pense que les chances sont "astronomiquement faible", mais je ne suis pas sûr de la façon de vérifier cela.

Plus d'informations: la taille de la piscine de messages possibles est restreint, mais volumineux (plusieurs centaines de millions de dollars). Le paradoxe d'anniversaire situations exactement ce que je suis inquiet.

Answer 1

En supposant répartition uniforme dans la gamme de MD5 et SHA-1 hachages pour des chaînes aléatoires (ce qui n'est pas le cas), et en supposant que nous parlons uniquement de deux chaînes et ne parlons pas d'un pool de chaînes de caractères (donc nous éviter d'anniversaire-paradoxe-type de complexité):

Un hachage MD5 est de 128 bits, et SHA-1 est de 160. Avec les hypothèses ci-dessus, deux chaînes A et B ont une probabilité de collision P si les deux hachages entrent en collision. Donc

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

Et

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

Donc

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

Encore une fois, si vous avez une piscine de chaînes et que vous essayez de déterminer les probabilités de collisions avec la piscine, vous êtes dans le domaine de l' anniversaire paradoxe et cette probabilité j'ai calculé ici ne s'applique pas. Que et les tables de hachage ne sont pas aussi uniforme qu'ils devraient l'être. En réalité, vous allez avoir beaucoup plus élevé le taux de collision, mais il sera toujours en minuscule.

---

MODIFIER

Car vous avez affaire à un anniversaire paradoxe de la situation, appliquer la même logique que la solution au paradoxe d'anniversaire. Regardons du point de vue d'une seule fonction de hachage:

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

Imaginons que nous avons un nombre encore plus agréable de hachages comme 2^29 (environ 530 millions de dollars).

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

En bref, je ne veux même pas y penser sur le calcul de ce nombre. Je ne suis même pas sûr de savoir comment vous pouvez aller de l'estimation. Vous aurez au moins besoin d'une précision arbitraire calculateur qui permet de gérer d'énormes factorielles sans mourir.

Notez que les probabilités va suivre une courbe qui commence à 0 lors de l' N = 1 or 2, pour atteindre 1 lors de l' N >= 2^288, de forme similaire à la une sur la page de Wikipedia pour le paradoxe d'anniversaire.

Le paradoxe d'anniversaire atteint P = .5 lorsque N = 23. En d'autres termes, la probabilité de collision est de 50% lorsque N est de 6% de S. Si échelles (je ne sais pas si c'est le cas), cela signifie qu'il y aura 50% de chances de collision lorsque vous avez 6% de 2^288 les tables de hachage. 6% de 2^288 est d'environ 2^284. Votre valeur de N (plusieurs centaines de millions de dollars) est nulle part près de ce. Il est pratiquement négligeable par rapport à votre S, donc je ne pense pas que vous ayez de quoi s'inquiéter. Les Collisions ne sont pas très probable.

Answer 2

un avenant à Welbog post:

Les Ratios de grande factorielles peuvent être calculées sans l'aide de précision arbitraire de l'arithmétique, en utilisant l' approximation de Stirling:

n! ≈ sqrt(2nn) * (n/e)ⁿ

Donc (S!)/(S^N * (S - N)!) ≈ sqrt(2nS)/sqrt(2π(S-N))*(S/e)^S/((S-N)/e)^{-S N}/S^N

= sqrt(S/(S-N)) * (S/(S-N))^S-N * e^-N

= sqrt(1 + α) * (1 + α)^S-N * e^-N où α = N/(S-N) est petit.

Le rapprochement (1+a/n)^nx ≈ e^ax détient que n → ∞ (ou au moins devient très grand)

** cela signifie donc (1+(N/(S-N)))^S-N ≈ e^N S-N >> N.

Je voudrais donc s'attendre à ce que

(S!)/(S^N * (S - N)!) ≈ sqrt(1 + N/(S-N)) * e^N * e^-N = sqrt(1 + N/(S-N)) pour les S-N >> N....

sauf que c'est plus grand que 1... donc, l'un des approximations n'est pas assez bon. :p

(** mise en garde: N/S doit être petit: pour N=22,S=365, il est désactivé par un facteur de 2)

Answer 3

Si la taille du message n'est pas limitée, la chance se rapproche de 100% à l'infini, comme il existe un nombre infini de messages possibles et un nombre fini de possible les tables de hachage.

(note: edition à la question rend moins pertinente)

Answer 4

Généralement, lorsque l'on choisit de N éléments au hasard, il est plus facile de calculer le nombre de collisions que la probabilité de collision. Le nombre de collisions ne peut pas être plus petite que la probabilité de collision, il peut souvent être utilisé comme limite supérieure.

Supposons que p est la probabilité pour que deux choisi au hasard éléments entrent en collision. Si nous choisissons N éléments aléatoires puis il y a N*(N-1)/2 paires d'éléments et donc le nombre de collisions est

p * N * (N-1)/2.

E. g., si nous supposons que la probabilité de collision pour les deux MD5 et SHA1 est p=2^-288 puis même après choisissant au hasard 2¹⁰⁰ éléments nous encore attendre seulement environ 2^-89 collisions.

Un autre exemple: si nous choisissons 2³⁰ éléments aléatoires et seulement calculer le MD5. En supposant qu'une collision entre deux hachages MD5 est p=2^-128 cela donne un nombre de 2^-59 pour le nombre de collisions. C'est pourquoi, même la probabilité que le hachage MD5 entre en collision de deux entrées est déjà très faible.

Answer 5

La réponse choisie est incorrect parce qu'il utilise la mauvaise probabilités. J'ai passé une bonne partie de aujourd'hui à la recherche de cette (vous pouvez sorta voir mon processus de pensée dans les commentaires à cette réponse), et de croire à la réelle réponse est la suivante (pour l'anniversaire de l'attaque d'un peu plus de messages que ceux dont vous parlez):

2^-61 * 2^-18 = une collision en une fois toutes les 2^79.

Et c'est si c'est OK pour il suffit de multiplier ces probabilités (je ne suis pas sûr de ça).

C'est faisable (moins de deux mois et diminue chaque année) par des super-ordinateurs d'aujourd'hui.

Notez que ceci est basé sur suffisamment grandes piscines de messages (pour faire le paradoxe d'anniversaire significatif). C'est également le scénario vous dit que vous étiez préoccupé.

Maintenant, une situation différente, c'est de trouver une collision pour une paire de hachages (SHA1 et MD5) d'un spécifique de message. Cela vous mènera à la sortie de bday paradoxe territoire et est un ordre de grandeur plus difficile. Je ne suis pas sûr si c'est 2^(-61*2)*2^(-18*2) ou quelque chose d'autre. Si quelqu'un sait ce que c'est, merci de poster un commentaire à cette réponse (serait super apprécié!).

Maintenant, vous demandez:

Étant donné deux messages différents, A et B (peut-être 20 à 80 caractères d'un texte, si la taille de l'importance à tous)

Oui, une question de taille. Cliquez sur le lien pour la 2^-18 figure et vous verrez que la valeur est de deux blocs d'entrées. En MD5, un bloc d'entrée est de 512 octets. 20-80 caractères de texte est trop petit pour ça, et la seule valeur de blocage est de 2^41.

Ainsi, pour que la quantité de données, vous obtenez 2^-61 (je pense) * 2^-41 = 2^-102.

Donc, pour que la taille, il semble à l'abri (lien contient figure de double de courant bitcoin hashrate de SHA256: 46626.93 TH/sec).