La probabilité de collisions SHA1

Étant donné un ensemble de 100 chaînes de longueur égale, comment pouvez-vous quantifier la probabilité qu'un SHA1 digest de collision pour les chaînes est peu probable... ?

  • clarifier, comment pouvez-vous avoir " différents mais égaux de la longueur des chaînes?
  • sont de longueur égale, mais différentes chaînes
  • Je suis en supposant que les cordes sont à moins de 20 octets de long. Sinon, évidemment, les chances seraient plus élevés de collision. 🙂
  • pourquoi est-ce évident? Je ne sais pas si c'est vrai
  • doh, lors de la re-lecture, c'est parfaitement clair.
  • Cette question est pertinente à cette question: sites.google.com/site/itstheshappening Au moins une collision a été trouvé.

InformationsquelleAutor eastafri | 2009-12-08
  1. 143

    La probabilité de collisions SHA1

    Sont de 160 bits des valeurs de hachage généré
    par SHA-1 est suffisamment large pour assurer la
    empreintes digitales de chaque bloc est unique?
    En supposant aléatoire des valeurs de hachage avec une
    distribution uniforme, une collection de
    n les différents blocs de données et d'une table de hachage
    la fonction qui génère de b bits, la
    la probabilité p qu'il y aura un
    ou plus de collisions est délimitée par les
    nombre de paires de blocs multiplié
    par la probabilité qu'une paire de
    entreront en collision.

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

    • En conclusion, la probabilité d'une collision est de l'ordre de 10^-45. Qui est très, très peu probable.
    • Mais SHA-1 n'est pas une distribution uniforme, il pourrait être plus grand que cette limite supérieure. Je doute que cette équation n'est pas correct. Les moins l'ÉGALITÉ.
    • Cette réponse ne prend pas en compte les chinois découverte en 2005, où ils sont en mesure de produire des collisions en 2^69 itérations plutôt que le 2^80 projetée par la force brute schneier.com/blog/archives/2005/02/sha1_broken.html
    • Il est important de ne pas confondre accidentelle hash collision et contradictoire de la collision de la chasse. Le premier est la probabilité que le hachage de deux éléments entrent en collision, et suivant la formule ci-dessus (bien que, comme l'a souligné Kamel, la distribution n'est pas parfaitement uniforme et donc la probabilité est vraisemblablement plus élevé). Ce dernier est utilisé intentionnellement essayer de trouver des collisions, et s'appuie sur la découverte et l'exploitation des faiblesses dans la table de hachage. Des empreintes cryptographiques tentative pour être robuste contre de telles attaques, mais elles sont souvent trop pour le plus simple de hachage applications (pas de transmission de secrets d'affaires).
    • Il serait bon de savoir comment ils sont arrivés à cette formule...
    InformationsquelleAutor Peter
  2. 5

    Bien, la probabilité de collision serait:

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

    Pense de la probabilité de collision de 2 éléments dans un espace de 10. Le premier élément est unique avec une probabilité de 100%. La deuxième est unique avec une probabilité de 9/10. De sorte que la probabilité d'être unique, c'est 100% * 90%, et la probabilité de collision est:

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

    Il est assez peu probable. Vous devez avoir beaucoup plus de chaînes pour être une possibilité éloignée.

    Prendre un coup d'oeil à la table sur cette page sur Wikipédia; il suffit d'interpoler entre les lignes de 128 bits et 256 bits.

    InformationsquelleAutor Anthony Mills
  3. 3

    C'est Problème D'Anniversaire - l'article donne une belle approximations qui font qu'il est assez facile d'estimer la probabilité. Probabilité réelle va être très très très faible voir cette question pour un exemple.

    InformationsquelleAutor sharptooth