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

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?)

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 $H(m)$$m$$m'$$H(m')$$H(m)$$\{username, H(password)\}$$\{username, password\}$une / deux n$H(input) =? H(password)$$1/2^n$$n$est 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 $H(m)$$m$p q d m ′ = m p q + m H ( m p q + m ) = ( m p q + m ) $H(m) = m^d \mod{pq}$$p$$q$$d$$m' = mpq + m$$H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$. 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(document)$$document$$H(document)$$d'$$H(d') = H(document)$

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$m_1$$m_2$$H(m_1) = H(m_2)$$f(\{0,1\}^*) = \{0,1\}^n$$O(2^n)$$O(sqrt(2^n)) = O(2^{n/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 ′$b$$b'$$H(b) = H(b')$$b'$$b'$$b$. 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.

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

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.