Comprendre la faiblesse de collision sha-1

Question

Selon diverses sources, les attaques à la recherche de collisions sha-1 ont été améliorés à 2^52 opérations:

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

Ce que je voudrais savoir est l'implication de ces découvertes sur des systèmes qui ne sont pas attaqués. Signification si je hash données aléatoires, quelles sont les probabilités statistiques d'une collision? Autrement dit, les recherches récentes indiquent-elles qu'une attaque d'anniversaire par force brute a plus de chances de trouver des collisions qui ont été initialement proposées? Certaines publications, comme celle ci-dessus, indiquent que l'obtention d'une collision SHA-1 par force brute nécessiterait 2^80 opérations. La plupart des sources disent que 2^80 est un nombre théorique (je suppose parce qu'aucune fonction de hachage n'est vraiment distribuée parfaitement même sur son espace de résumé).

Alors, est-ce que l'une des faiblesses de collision annoncées sha1 dans la distribution de hachage fondamentale? Ou les chances accrues de collision sont-elles seulement le résultat d'attaques mathématiques guidées?

Je me rends compte qu'à la fin c'est juste un jeu de cotes, et que c'est un changement infinitésimalement petit que vos premier et deuxième messages vont entraîner une collision. Je me rends également compte que même 2^52 est un nombre vraiment grand, mais je veux toujours comprendre les implications pour un système non attaqué. Alors s'il vous plaît ne répondez pas avec "ne vous inquiétez pas à ce sujet".

Answer 1

Le résultat annoncé dans votre lien est une attaque, une séquence d'étapes soigneusement choisies par algorithme qui génèrent des collisions avec une probabilité plus grande qu'une attaque aléatoire. Ce n'est pas une faiblesse dans la distribution de la fonction de hachage. Eh bien, d'accord, c'est le cas, mais pas du genre qui fait qu'une attaque aléatoire probable de l'ordre de 2^52 réussisse.

Si personne n'essaye de générer des collisions dans vos sorties de hachage, ce résultat ne vous affecte pas.

Answer 2

Les bonnes fonctions de hachage sont résistantes à 3 types d'attaques différents (comme l'indique l'article).

La résistance la plus importante dans un sens pratique est la 2ème résistance pré-image. Cela signifie fondamentalement donné un message M1 et Hash (M1) = H1, il est difficile de trouver un M2 tel que Hash (M2) = H1.

Si quelqu'un trouvait un moyen de le faire efficacement, ce serait mauvais. De plus, une attaque 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 pré-image ou d'une seconde attaque pré-image, mais simplement d'une attaque par collision. Pour répondre à votre question, aucune attaque de force brute n'a plus de chance de trouver des collisions. Ce que cela signifie, c'est que la méthode de la force brute naïve, combinée avec les méthodes des chercheurs, aboutit à trouver des collisions après 2^52. Une attaque par force brute standard prend encore 2^80.

Answer 3

La question clé est "Est-ce que l'attaquant peut modifier à la fois les messages m1 et m2"? Si c'est le cas, l'attaquant doit trouver m1, m2 tel 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 à sa secrétaire de taper le message "Je le vendrai pour 10 millions de dollars".Le secrétaire de l'intrigue crée 2 documents: "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 de 10, modifie les deux messages en ajoutant des espaces, en capitalisant mots etc, modifie x, jusqu'à ce que hash (m1) = hash (m2). Maintenant, le secrétaire montre le bon message m1 au vendeur, et il le signe à l'aide de sa clé privée, ce qui entraîne le hachage h. La secrétaire passe le message et envoie (m2, h). Seul le vendeur a accès à sa clé privée et donc il ne peut pas répudier et dire qu'il n'a pas signé le message.

Pour SHA1, qui génère 160 bits, l'attaque d'anniversaire réduit la complexité à 2^80. Cela devrait être sûr pendant 30 ans ou plus. Nouvelle réglementation gouvernementale, les spécifications 4G 3Gpp commencent à exiger SHA256. Mais si dans votre cas d'utilisation, l'attaquant ne peut pas modifier les messages (pré-image ou deuxième scénario de pré-image), alors pour SHA1 la complexité est de 2^160. Devrait être sûr pour l'éternité sauf si une attaque non-brute-force est découverte.