Quand est-il sûr d'utiliser une fonction de hachage cassé?

Question

Il est trivial d'utiliser une fonction de hachage sécurisée comme SHA-256, et en continuant à utiliser MD5 pour la sécurité est un comportement irresponsable. Cependant, il y a des complexités de la vulnérabilité de la fonction de hachage que je voudrais mieux comprendre.

Collisions ont été généré pour MD4 et MD5 . Selon le NIST, MD5 est pas une fonction de hachage sécurisée. Il ne faut 2 ³⁹ opérations pour générer une collision et ne devrait jamais être utilisé pour les mots de passe . Cependant SHA-1 est vulnérable à un attaque de collision similaire où une collision se trouve dans 2 ⁶⁹ opérations, alors que la force brute est 2 ⁸⁰ . Personne n'a généré une collision SHA-1 et NIST énumère encore SHA-1 comme message sécurisé fonction digest .

Alors, quand est-il sûr d'utiliser une fonction de hachage cassé? Même si une fonction est cassé, il peut encore être « assez grand ». Selon Schneier une fonction de hachage vulnérable à une attaque de collision peut encore être utilisé comme HMAC . Je crois que c'est parce que la sécurité d'un HMAC dépend de sa clé secrète et une collision ne peut être trouvé que cette clé est obtenue. Une fois que vous avez la clé utilisée dans un HMAC il est déjà cassé, donc c'est discutable. Quelles sont les faiblesses fonction de hachage porterait atteinte à la sécurité d'un HMAC?

Profitons de cette propriété un peu plus loin. Devient-il alors sûr d'utiliser un message très faible digest comme MD4 pour les mots de passe si un sel est ajouté au début du mot de passe? Gardez à l'esprit les attaques MD4 et MD5 sont préfixant attaques, et si un sel est préfixé alors un attaquant ne peut pas contrôler le préfixe du message. Si le sel est vraiment un secret, et on ne sait pas à l'attaquant, alors est-ce important si elle est ajouté au mot de passe? Est-il sûr de supposer qu'un attaquant ne peut pas générer une collision jusqu'à ce que le message entier a été obtenu?

Connaissez-vous d'autres cas où une fonction de hachage cassé peut être utilisé dans un contexte de sécurité sans introduire une vulnérabilité?

(S'il vous plaît poster preuves à l'appui, car il est génial!)

Answer 1

En fait les collisions sont plus faciles que ce que vous énumérez sur les deux MD5 et SHA-1. les collisions MD5 peuvent être trouvés dans le temps équivalent à 2 ^26.5 opération (où une "opération" est le calcul de MD5 sur un court message). Voir cette page pour certains détails et une mise en œuvre de l'attaque (I écrit ce code; il trouve une collision dans un délai moyen de 14 secondes sur un 2,4 GHz Core 2 x 86 en mode 64 bits)

.

De la même façon, la meilleure attaque connue sur SHA-1 est à peu près 2 ⁶¹ opérations, non 2 ⁶⁹ . Il est encore théorique (pas de collision réelle a été produit encore), mais il est dans le domaine du possible.

En ce qui concerne la sécurité: implications sur les fonctions de hachage sont généralement dit avoir trois propriétés:

• Non preimage: donnée y , il ne devrait pas être possible de trouver x tels que h (x) = y
• Pas de seconde préimage: donnée x ₁ , il ne devrait pas être possible de trouver x ₂ (distinct de x ₁ ) tel que h (x ₁ ) = h (x ₂ ) .
• collision Non: il ne devrait pas être possible de trouver x ₁ et x ₂ (distinct de de l'autre) de sorte que h (x ₁ ) = h (x ₂ ) .

Pour une fonction de hachage avec n -bits, il y a des attaques génériques (qui fonctionnent quelles que soient les détails de la fonction de hachage) dans 2 ⁿ opérations pour les deux premières propriétés, et 2 ^{n / 2} opérations pour le troisième. Si, pour une fonction de hachage donnée, une attaque se trouve, qui, en exploitant les détails spécifiques de la façon dont la fonction de hachage fonctionne, trouve une pré-image, une seconde préimage ou d'une collision plus rapide que l'attaque générique correspondant, alors la fonction de hachage est dit être "cassé".

Cependant, tous les usages de fonctions de hachage reposent sur les trois propriétés. Par exemple, les signatures numériques commencent en hachant les données qui doit être signé, et la valeur de hachage est utilisée dans le reste de l'algorithme. Cela repose sur la résistance à préimages et deuxième préimages, mais les signatures numériques ne sont pas, en soi, impacté par des collisions. Collisions peut être un problème dans certains scénarios de signature spécifique, où l'attaquant peut choisir les données qui doit être signé par la victime (essentiellement, l'attaquant calcule une collision, a un message signé par la victime, et la signature devient valable pour l'autre message aussi bien). Cela peut être contrecarrée par préfixer quelques octets aléatoires au message signé avant de calculer la signature (l'attaque et la solution où a démontré dans le contexte des certificats X.509).

HMAC la sécurité repose sur une autre propriété que la fonction de hachage doit remplir; à savoir que la « fonction de compression » (la brique élémentaire sur laquelle la fonction de hachage est construite) agit comme Fonction pseudo-aléatoire (PRF). Les détails sur ce PRF est sont assez techniques, mais, grosso modo, un PRF doit être impossible à distinguer d'une Aléatoire Oracle . Un oracle aléatoire est modélisé comme une boîte noire qui contient un gnome, quelques dés et un grand livre. Sur certaines données d'entrée, le gnome sélectionner une sortie aléatoire (avec les dés) et écrit dans le livre le message d'entrée et la sortie qui a été choisi au hasard. Le gnome utilise le livre pour vérifier s'il a vu déjà le même message d'entrée: le cas échéant, le gnome retourne la même sortie que précédemment. Par construction, vous pouvez ne rien savoir au sujet de la sortie d'un oracle au hasard sur un message donné jusqu'à ce que vous essayez.

Le modèle de l'oracle aléatoire permet la preuve de la sécurité HMAC à quantifier dans invocations du PRF. En fait, les états preuve que HMAC ne peut être rompu sans invoquer le PRF un grand nombre de fois, et par « énorme » Je veux dire informatiquement infeasible.

Malheureusement, nous n'avons pas au hasard Oracles, dans la pratique, nous devons utiliser les fonctions de hachage. Il n'y a pas de preuve que les fonctions de hachage existent vraiment, avec la propriété PRF; En ce moment, nous ne disposons que des candidats, à savoir les fonctions pour lesquelles nous ne pouvons pas prouver (encore) que leurs fonctions de compression ne sont pas PRF.

Si la fonction de compression est un PRF puis la fonction de hachage est automatiquement résistant aux collisions. Cela fait partie de la magie du PRF. Par conséquent , si nous pouvons trouver des collisions pour une fonction de hachage, alors nous savons que la fonction de compression interne n'est pas un PRF. Cela ne se transforme pas les collisions dans une attaque contre HMAC. Être en mesure de générer des collisions à volonté ne contribue pas à briser HMAC. Cependant, ces collisions démontrent que la preuve de la sécurité associée à HMAC ne s'applique pas. La garantie est nulle. C'est tout de même qu'un ordinateur portable. Ouvrir le boîtier ne se casse pas nécessairement la machine, mais après, vous êtes sur votre propre

Dans le Kim-Biryukov-Preneel-Hong article de certaines attaques contre HMAC sont présenté, en particulier une attaque de faux sur HMAC-MD4. L'attaque exploite les faiblesses de MD4 (ses « faiblesses ») qui en font un non-PRF. Des variantes des mêmes faiblesses ont été utilisés pour générer des collisions sur MD4 (MD4 est complètement cassé, certaines attaques génèrent des collisions plus rapidement que le calcul de la fonction de hachage lui-même!). Ainsi, les collisions ne signifie pas l'attaque HMAC, mais les deux attaques se nourrissent de la même source. Notez, cependant, que l'attaque de faux a coûté 2 ⁵⁸ , qui est assez élevé (pas de faux réelle a été produit, le résultat est encore théorique), mais sensiblement plus faible que la résistance niveau attendu de HMAC (avec une fonction de hachage robuste avec un n -bits, HMAC doit résister à 2 ⁿ facteur de travail; n = 128 pour MD4).

Ainsi, alors que les collisions ne le font pas en soi impliquent des faiblesses sur HMAC, ils sont de mauvaises nouvelles. En pratique, les collisions sont un problème pour les configurations très peu. Mais savoir si les collisions affectent un usage donné des fonctions de hachage est assez délicate, qu'il est tout à fait imprudent de continuer à utiliser une fonction de hachage pour laquelle les collisions ont été démontrées.

Pour SHA-1, l'attaque est encore théorique, et SHA-1 est largement déployée. La situation a été décrite comme ceci: «. L'alarme est activée, mais il n'y a pas de feu ou de fumée visible Il est temps de marcher vers les sorties - mais pas d'exécuter »

Pour plus d'informations sur le sujet, commencez par lire le chapitre 9 du Manuel de Cryptographie appliquée , par Menezes, van Oorschot et Vanstone, un incontournable pour l'apprenti cryptographe (à ne pas confondre avec « Cryptographie appliquée » par B. Schneier, qui est une introduction bien écrite, mais loin d'être aussi complet que le " Manuel ").

Answer 2

La seule fois où il est sûr d'utiliser une fonction de hachage est brisée lorsque les conséquences d'une collision sont inoffensives ou trivial, par exemple lors de l'attribution des fichiers dans un seau sur un système de fichiers.

Answer 3

Lorsque vous ne vous inquiétez pas s'il est sûr ou non.

Sérieusement, il ne prend pas d'effort supplémentaire pour utiliser une fonction de hachage sécurisée dans toutes les langues à peu près, et impact sur les performances est négligeable, donc je ne vois pas pourquoi vous ne.

[Modifier après avoir lu réellement votre question]

  

Selon Schneier une fonction de hachage vulnérable à une attaque de Collsion peut encore être utilisé comme HMAC. Je crois que c'est parce que la sécurité d'un HMAC dépend de sa clé secrète et une collision ne peut être trouvé que cette clé est obtenue.

En fait, il est essentiellement parce que l'être en mesure de générer une collision pour un hachage ne vous permet pas nécessairement par une collision pour le hash-of-a-hachage (combiné avec le XORing utilisé par HMAC).

  

Devient-il alors sûr d'utiliser un message très faible pour digérer comme md4 mots de passe si un sel est perpended au mot de passe?

Non, pas si le hachage a preimage attaque qui vous permet de préfixer données l'entrée. Par exemple, si le hachage était H(pass + salt), nous aurions besoin d'une crise qui nous permet préimage de trouver pass2 telle que H(pass2 + salt) = H(pass + salt).

Il y a eu append attaques dans le passé, donc je suis sûr que les attaques de PREPEND sont possibles.

Answer 4

Télécharger des sites utilisent hachage MD5 comme une somme de contrôle pour déterminer si le fichier a été endommagé pendant le téléchargement, et je dirais un hachage cassé est assez bon pour cette fin.

Disons que MITM décide de modifier le fichier (disons une archive zip ou un exe). Maintenant, l'attaquant doit faire deux choses -

1. Trouver une collision de hachage et de créer un fichier modifié sur ce
2. Assurez-vous que le fichier nouvellement créé est également un exe valide ou une archive zip

Avec un hachage cassé, 1 est un peu plus facile. Mais faire en sorte que la collision se réunit en même temps d'autres propriétés connues du fichier est informatiquement trop cher.

Ceci est tout à fait ma propre réponse, et je pourrais être terriblement mal.

Answer 5

La réponse dépend entièrement de ce que vous utilisez pour. Si vous avez besoin d'empêcher quelqu'un produire une collision avec quelques millisecondes je serais moins inquiet que si vous avez besoin d'empêcher quelqu'un produire une collision dans quelques décennies.

Quel problème vous en train d'essayer de résoudre?

Answer 6

La plupart des soucis sur l'utilisation de quelque chose comme MD4 un mot de passe est lié moins aux attaques actuellement connues, que le fait qu'une fois qu'il a été analysé au point que la génération de collision est facile, il est généralement présumé être beaucoup plus probable que quelqu'un sera en mesure d'utiliser ces connaissances pour créer une crise preimage -. et quand / si cela se produit, essentiellement toutes les utilisations possibles de cette fonction de hachage deviennent vulnérables