Quelle est la différence entre une deuxième attaque de pré-image et une attaque par collision?

24

Wikipedia définit une deuxième attaque de pré-image comme:

étant donné un message fixe m1, trouvez un message différent m2 tel que hachage (m2) = hachage (m1).

Wikipedia définit une attaque par collision comme:

trouver deux messages différents arbitraires m1 et m2 tels que hachage (m1) = hachage (m2).

La seule différence que je peux voir est que dans une deuxième attaque de pré-image, m1 existe déjà et est connu de l'attaquant. Cependant, cela ne me semble pas significatif - l'objectif final est toujours de trouver deux messages qui produisent le même hachage.

Quelles sont les différences essentielles dans la façon dont une deuxième attaque de pré-image et une attaque par collision sont effectuées? Quelles sont les différences de résultats?

(En passant, je ne peux pas taguer cette question correctement. J'essaie d'appliquer les tags "collision de pré-image de sécurité de cryptographie" mais je n'ai pas assez de réputation. Quelqu'un peut-il appliquer les tags appropriés?)

Thomas Owens
la source
1
Votre impression est correcte - c'est la différence. La partie où vous avez tort est que c'est une énorme différence dans la pratique. C'est une chose de pouvoir trouver deux choses qui ont une collision, et c'en est une autre de pouvoir trouver une collision pour un texte en clair spécifique. Par exemple, si vous voulez usurper un message particulier, il est inutile de pouvoir commettre une falsification existentielle - vous avez besoin d'un autre message qui hache la même chose que le message que vous avez intercepté.
Adrian Petrescu
@Adrian Petrescu: Pourriez-vous répondre à cette question et peut-être en développer davantage? Ajouter des éléments tels que lorsque chacun (vous fournissez une situation pour l'attaque de pré-image, mais pas pour l'attaque par collision) est le mieux adapté?
Thomas Owens

Réponses:

27

Je peux motiver la différence pour vous avec des scénarios d'attaque.

Dans une première attaque de pré-image , nous demandons à un adversaire, ne que de , de trouver ou quelques tels que = . Supposons qu'un site Web stocke dans ses bases de données au lieu de . Le site Web peut toujours vérifier l'authenticité de l'utilisateur en acceptant son mot de passe et en comparant (avec une probabilité de pour certains grands pour les faux positifs). Supposons maintenant que cette base de données soit divulguée ou soit autrement comprimée. Une première attaque pré-imagem m H ( m ) H ( m ) { u s e r n a m e , H ( p a s s w o r d ) } { u s e r n a m e , p a s s w o r d } H ( i nH(m)mmH(m)H(m){usernuneme,H(punesswor)}{usernuneme,punesswor}une / deux n nH(jenput)=?H(punesswor)1/2nnest la situation où un adversaire n'a accès qu'à un résumé de message et essaie de générer un message qui hache à cette valeur.

Lors d'une deuxième attaque pré-image , nous permettons à l'adversaire d'avoir plus d'informations. Plus précisément, non seulement nous lui donnons mais nous lui donnons également . Considérons la fonction de hachage où et sont de grands nombres premiers et est une constante publique. Évidemment, pour une première attaque de pré-image, cela devient le problème RSA et on pense qu'il est difficile. Cependant, dans le cas de la deuxième attaque de pré-image, trouver une collision devient facile. Si l'on fixe ,m H ( m ) = m dH(m)mp q d m = m p q + m H ( m p q + m ) = ( m p q + m ) dH(m)=mmodpqpqm=mpq+mH(mpq+m)=(mpq+m)modpq=mmodpq. Et donc l'adversaire a trouvé une collision avec peu ou pas de calcul.

Nous aimerions que les fonctions de hachage unidirectionnelles soient résistantes aux attaques de deuxième image avant en raison des schémas de signature numérique, auquel cas est considéré comme une information publique et est transmis (via un niveau d'indirection) avec chaque copie du document. Ici, un attaquant a accès à la fois au et à . Si l'attaquant peut proposer une variation du document d'origine (ou un message entièrement nouveau) tel que il pourrait publier son document comme s'il était le signataire d'origine.d o c u m e n t H ( d o c u m e n t ) d H ( d ) = H ( d o c u m e n t )H(ocument)ocumentH(ocument)H()=H(ocument)

Une attaque par collision offre à l'adversaire encore plus de possibilités. Dans ce schéma, nous demandons à l'adversaire (puis-je l'appeler Bob?) De trouver deux messages et tels que . En raison du principe du pigeonhole et du paradoxe d'anniversaire, même les fonctions de hachage «parfaites» sont quadratiques plus faibles aux attaques par collision que les attaques de pré-image. En d'autres termes, étant donné une fonction de résumé de message imprévisible et irréversible qui met à la force brute, une collision peut toujours être trouvé dans le temps prévu .m 2 H ( m 1 ) = H ( m 2 ) f ( { 0 , 1 } ) = { 0 , 1 } n O ( 2 n ) O ( s q r t ( 2 n ) ) = O ( 2 n / 2 )m1m2H(m1)=H(m2)F({0,1})={0,1}nO(2n)O(sqrt(2n))=O(2n/2)

Bob peut utiliser une attaque par collision à son avantage de plusieurs façons. Voici l'un des plus simples: Bob trouve une collision entre deux binaires et ( ) de telle sorte que b est un correctif de sécurité Microsoft Windows valide et est un malware. (Bob fonctionne pour Windows). Bob envoie son correctif de sécurité en haut de la chaîne de commandement, où derrière un coffre-fort, ils signent le code et expédient le binaire aux utilisateurs Windows du monde entier pour corriger une faille. Bob peut désormais contacter et infecter tous les ordinateurs Windows du monde entier avec et la signature que Microsoft a calculée pourb H ( b ) = H ( b ) b b bbbH(b)=H(b)bbb. Au-delà de ces types de scénarios d'attaque, si une fonction de hachage est considérée comme résistante aux collisions, cette fonction de hachage est également plus susceptible d'être résistante à la pré-image.

Ross Snider
la source
C'est magnifiquement expliqué. Beaucoup plus de mathématiques que je ne cherchais, mais j'apprécie beaucoup l'effort - je vous ai suivi tout au long de chacun. Merci.
Thomas Owens
Et wow. Un autre étudiant du RIT.
Thomas Owens
1
Comment ça va Thomas? Je pense que vous aviez de la physique avec mon ami Alan Meekins. C'est bien de voir des gens RIT ici! Merci également d'avoir accepté la réponse.
Ross Snider
Assez bon. Si vous allez être sur le campus à l'automne et que vous êtes intéressé par la sécurité, nous pouvons peut-être vous rattraper en personne. J'ai fait quelques travaux de sécurité appliquée (application de sténographie, de stéganalyse, de chiffrement à clé publique, de signatures numériques) cet été et j'aimerais entendre parler du côté théorique (autant que cela m'intéresse - je n'ai pas le temps ou connaissances mathématiques pour passer en revue de nombreux articles sur le sujet).
Thomas Owens
[email protected]
Ross Snider
2

Les attaques par collision peuvent être beaucoup plus faciles, mais en cas de succès, beaucoup moins utiles.

Jukka Suomela
la source
1

Le problème que Ross mentionne comme étant le problème du journal discret est en réalité un problème tout à fait différent, le problème RSA, qui est beaucoup plus lié aux racines de calcul qu'au journal discret.


la source
2
C'est certainement vrai! Oops. À l'origine, j'ai utilisé le problème du journal discret et j'ai ensuite édité les détails du schéma. Bonne prise. Je ne suis pas sûr que cela constitue une nouvelle réponse - il était probablement plus approprié de laisser un commentaire sous ma réponse.
Ross Snider