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'un SHA1 collision pour les cordes est peu probable ...?

Answer 1

  

sont les valeurs de hachage 160 bits générés   par SHA-1 assez grand pour assurer la   empreintes digitales de chaque bloc est unique?   En supposant que les valeurs de hachage aléatoires avec   une distribution uniforme, un ensemble de   n différents blocs de données et une table de hachage   fonction qui génère b bits, la   la probabilité p que il y aura une   ou plusieurs collisions est délimitée par la   nombre de paires de blocs multiplié   par la probabilité qu'une paire donnée   va entrer 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)

Considérez la probabilité d'une collision de 2 objets dans un espace 10. Le premier élément est unique avec une probabilité de 100%. Le deuxième est unique avec une probabilité de 10/09. Ainsi, la probabilité d'être à la fois unique 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)

Il est assez peu probable. Vous devriez avoir beaucoup plus de chaînes pour qu'il soit possible à distance.

Jetez un oeil à la table sur cette page sur Wikipédia ; juste interpoler entre les rangées de 128 bits et 256 bits.

Answer 3

C'est anniversaire problème - l'article fournit des approximations belles qui le rendent assez facile d'estimer la probabilité. probabilité réelle sera très très très faible - voir cette question pour un exemple.