Probabilité de collisions SHA1

Question

Étant donné un ensemble de 100 chaînes différentes de longueur égale, comment pouvez-vous quantifier la probabilité qu'une collision du condensé SHA1 pour les chaînes soit peu probable... ?

Answer 1

Les valeurs de hachage de 160 bits générées par SHA-1 sont-elles assez grandes pour garantir que l'empreinte digitale de chaque bloc est unique ? En supposant des valeurs de hachage aléatoires avec une distribution uniforme, une collection de n blocs de données différents et une fonction de hachage de hachage qui génère b bits, la probabilité p qu'il y ait une ou plusieurs ou plusieurs collisions est limitée par le nombre de paires de blocs multiplié par la probabilité qu'une paire donnée donnée entre en collision.

(source : http://bitcache.org/faq/hash-collision-probabilities )

Answer 2

Eh bien, la probabilité d'une collision serait :

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

Pensez à la probabilité d'une collision de 2 objets dans un espace de 10. Le premier objet est unique avec une probabilité de 100%. Le second est unique avec une probabilité de 9/10. Donc la probabilité que les deux soient uniques est 100% * 90% et la probabilité d'une collision est :

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

C'est assez peu probable. Il faudrait que vous ayez beaucoup plus de cordes pour que ce soit une possibilité infime.

Jetez un coup d'œil au tableau sur cette page sur Wikipédia ; il suffit d'interpoler entre les lignes pour 128 bits et 256 bits.

Answer 3

C'est Problème d'anniversaire - l'article fournit de belles approximations qui permettent d'estimer assez facilement la probabilité. La probabilité réelle sera très très très faible - cf. cette question pour un exemple.