Comprendre la faiblesse de la collision sha-1
selon diverses sources, les attaques à la recherche de collisions sha-1 ont été améliorées à 2^52 opérations:
http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252 /
ce que j'aimerais savoir, c'est l'implication de ces découvertes sur des systèmes qui ne sont pas attaqués. Ce qui signifie que si je hachais des données aléatoires, quelles sont les chances statistiques d'une collision? Dit d'une autre manière, ne l' des recherches récentes indiquent qu'une attaque d'anniversaire par la force brute a une plus grande chance de trouver des collisions qui ont été proposées à l'origine?
certains écrits, comme celui ci-dessus, disent que l'obtention d'une collision SHA-1 par la force brute nécessiterait 2^80 opérations. La plupart des sources disent que 2 ^ 80 est un nombre théorique (je suppose que parce qu'aucune fonction de hachage n'est vraiment distribué parfaitement même sur son espace de digestion).
ainsi que l'une des collisions sha1 annoncées des faiblesses dans la distribution fondamentale du hash? Ou la probabilité accrue de collision n'est-elle que le résultat d'attaques mathématiques guidées?
je me rends compte qu'en fin de compte, ce n'est qu'un jeu de hasard, et qu'il s'agit d'un changement infime que vos premier et deuxième messages résulteront en une collision. Je me rends également compte que même le chiffre de 2^52 est très élevé, mais je veux encore comprendre les implications pour un système qui n'est pas attaqué. Donc merci de ne pas répondre à "ne pas s'en soucier".
3 réponses
le résultat annoncé dans votre lien est une attack , une séquence d'étapes minutieuses, choisies algorithmiquement qui génèrent des collisions avec une plus grande probabilité qu'une attaque aléatoire. Ce n'est pas une faiblesse dans la distribution de la fonction de hachage. C'est vrai, mais pas du genre à faire en sorte qu'une attaque au hasard soit de l'ordre de 2^52 pour réussir.
si personne n'essaie de générer des collisions dans vos sorties de hachage, ce résultat ne vous affectent.
bien bonnes fonctions de hachage sont résistantes à 3 types différents d'attaques (comme l'indique l'article).
la résistance la plus importante d'un point de vue pratique est la deuxième résistance pré-image. Cela signifie essentiellement que pour un message M1 et Hash(M1)=H1, il est difficile de trouver un M2 tel que Hash (M2)=H1.
si quelqu'un trouve un moyen de le faire efficacement, ce serait mauvais. En outre, une attaque de préimage n'est pas sensible au paradoxe de l'anniversaire, puisque le message M1 est fixé pour nous.
il ne s'agit pas d'une attaque de pré-image ou d'une seconde attaque de pré-image, mais simplement d'une attaque de recherche de collision. Pour répondre à votre question, non une attaque par la force brute n'a pas plus de chance de trouver des collisions. Cela signifie que la méthode naïve de la force brute, combinée aux méthodes des chercheurs, permet de trouver des collisions après 2^52. Une attaque par la force brute standard prend encore 2^80.
la question clé est"L'attaquant peut-il Modifier les messages m1 et m2?". Si oui, l'attaquant doit trouver m1, m2, tels que hash(m1) = hash(m2). C'est l'attaque d'anniversaire et la complexité réduit considérablement --- devient racine carrée. Si la sortie de hachage est de 128 bits (MD5), la complexité est de 2^64, bien à portée de main avec la puissance de calcul actuelle.
l'exemple habituel donné est que le vendeur demande à son secrétaire de taper message "je vais le vendre pour 10 millions Dollar." Le Secrétaire intrigant crée 2 documents l'un qui dit "je vais le vendre pour 10 millions de dollars" et un autre qui dit "je vais le vendre pour x millions de dollars", où x est beaucoup moins que 10, modifie les deux messages en ajoutant des espaces, en majuscules mots etc, modifie x, jusqu'à hachage(m1) = hachage(m2). Maintenant, le Secrétaire montre le message m1 correct au vendeur, et il le signe en utilisant sa clé privée, résultant en hash H. Le Secrétaire échange le message et envoie (m2, h). Seul le le vendeur a accès à sa clé privée et donc il ne peut pas nier et dire qu'il n'a pas signer le message.
pour SHA1, qui produit 160 bits, l'attaque d'anniversaire réduit la complexité à 2^80. Cela devrait être sans danger pendant 30 ans ou plus. Nouvelle réglementation gouvernementale, 4G 3GPP specs commencent à exiger SHA256.
mais si dans votre cas d'utilisation, l'attaquant ne peut pas modifier les deux messages (préimage ou second préimage scénarios), alors pour SHA1 le la complexité est de 2 ^ 160. Devrait être en sécurité pour l'éternité à moins qu'une attaque non-violente ne soit découverte.