Étant donné un ensemble de 100 chaînes différentes de longueur égale, comment pouvez-vous quantifier la probabilité qu'une collision de condensé SHA1 pour les chaînes soit improbable ...?Probabilité des collisions SHA1
-ce que les 160 bits des valeurs de hachage générées par SHA-1 suffisamment grand pour assurer l'empreinte de chaque bloc est unique? En supposant que les valeurs de hachage aléatoire avec une distribution uniforme, une collection de N blocs de données différentes et une fonction de hachage qui génère des b bits, la probabilité p que il y aura une ou plusieurs collisions est limitée par le nombre de paires de blocs multiplié par la probabilité qu'une paire donnée entre en collision.
(source: http://bitcache.org/faq/hash-collision-probabilities)
En conclusion, la probabilité d'une collision est de l'ordre de 10^-45. C'est très, * très * peu probable. –
Mais SHA-1 n'est pas une distribution uniforme, elle pourrait être plus grande que cette limite supérieure. Je doute que cette équation ne soit pas correcte. Au moins l'égal. – Kamel
Cette réponse ne prend pas en compte la découverte chinoise en 2005 où ils sont capables de produire des collisions en 2^69 itérations plutôt que les 2^80 projetées par force brute https://www.schneier.com/blog/archives /2005/02/sha1_broken.html – Djarid
C'est Birthday Problem - l'article fournit de bonnes approximations qui facilitent l'estimation de la probabilité. La probabilité réelle sera très très très faible - voir this question pour un exemple.
Eh bien, la probabilité d'une collision serait de 1 - ((2^160 - 1)/2^160) * ((2^160 - 2)/2^160) * ... * ((2^160 - 99)/2^160). Pensez à la probabilité d'une collision de 2 éléments dans un espace de 10. Le premier élément est unique avec une probabilité de 100%. La seconde est unique avec une probabilité de 9/10. Donc, la probabilité que les deux soient uniques est de 100% * 90%, et la probabilité d'une collision est de 1 - (100% * 90%), ou 1 - ((10 - 0)/10) * ((10 - 1)/10), ou 1 - ((10 - 1)/10).
C'est assez improbable. Vous devriez avoir beaucoup plus de chaînes pour que ce soit une possibilité lointaine.
Regardez le tableau sur this page on Wikipedia; Il suffit d'interpoler entre les lignes pour 128 bits et 256 bits.
clarifier les choses, comment pouvez-vous avoir des chaînes 'de longueurs différentes mais égales'? – KevinDTimm
@kevindtimm "a", "b", "c" sont de longueur égale mais de chaînes différentes –
Je suppose que les chaînes ont une longueur d'au moins 20 octets. Sinon, évidemment, les chances seraient plus élevées d'une collision. :) –