Attaque sur les fonctions de hachage qui ne satisfont pas la propriété à sens unique

Question

Je révisais pour un cours de sécurité informatique et je suis bloqué sur une des questions précédentes. Voici ce:

  

Alice ($ A $) veut envoyer un court message $ M $ à Bob ($ B $) en utilisant un secret partagé S_ $ {ab} $ pour authentifier que le message est venu d'elle. Elle propose d'envoyer un seul message avec deux pièces:   $$ A \ B: \ quad M, h (M \ mathbin \ parallèle S_ {ab}) $$   où $ h $ est une fonction de hachage et $ \ $ parallèle représente la concaténation.

     

  
1. Expliquez soigneusement ce que Bob fait pour vérifier que le message est venu d'Alice, et pourquoi (à l'exception des propriétés de $ h $), il peut le croire.
  
2. Supposons que $ h $ ne satisfait pas la propriété à sens unique et il est possible de générer des pré-images. Expliquer ce qu'est un attaquant peut faire et comment.
  
3. Si la génération d'images pré-est relativement temps, suggère une contre-mesure simple d'améliorer le protocole sans changer $ h $.
  

Je crois que je connais le premier. Bob a besoin de prendre un hachage du message reçu avec sa clé partagée et de comparer ce hachage avec le hachage reçue d'Alice, si elles correspondent alors cela devrait prouver Alice l'a envoyé.

Je ne suis pas sûr au sujet des deux deuxième questions cependant. Pour le second, la réponse serait qu'un attaquant peut simplement obtenir le message d'origine donné un hachage? Je ne sais pas comment cela se fait bien.

Answer 1

  

Pour la seconde, la réponse serait qu'un attaquant peut simplement obtenir le message d'origine donné un hachage?

Eh bien, le message $ M $ est déjà donné à l'adversaire (il est envoyé à Bob sur un canal non sécurisé), il a donc besoin de trouver pas. Pour briser le système dont il a besoin d'envoyer une nouvelle paire M $ ^ *, h (M ^ * \ | S_ {ab}) $ tel que Bob accepte M $ ^ * \ ne M $ que le message envoyé par Alice.

Pour la deuxième question: S'il est facile de générer des images de pré-$ h $, l'adversaire pourrait être en mesure d'apprendre la clé secrète $ S_ {ab} $ de $ h (M \ | S_ {ab}) $ brisant ainsi le système.
. ^{(Notez que ce pourrait ne pas être trivial Le processus d'inversion pourrait sortie M_1 $, S_1 $ tels que $ h (M \ | S_ {ab}) = h (M_1 \ | S_1) $, mais ce n'est pas utile l'adversaire .. de plus, si l'adversaire à nouveau essayer d'inverser $ h $, il pourrait obtenir le même pré-image.)}

Pour la troisième question: On suppose maintenant inverser $ h $ prend beaucoup de temps, donc nous allons faire plus difficile la vie de l'adversaire en l'obligeant à inverser plusieurs fois afin de briser le système. Par exemple, utiliser le hachage $ k fois de $ $ h (h (h (.... h (M \ |. S_ {ab}) ..)) $ D'autres solutions existent aussi bien

.