Was ist der Unterschied zwischen einem zweiten Preimage-Angriff und einem Kollisionsangriff?

Wikipedia definiert einen zweiten Preimage-Angriff als:

Wenn eine feste Nachricht m1 gegeben ist, finde eine andere Nachricht m2, so dass Hash (m2) = Hash (m1) ist.

Wikipedia definiert einen Kollisionsangriff als:

finde zwei willkürlich verschiedene Nachrichten m1 und m2, so dass Hash (m1) = Hash (m2) ist.

Der einzige Unterschied, den ich sehen kann, ist, dass in einem zweiten Preimage-Angriff m1 bereits existiert und dem Angreifer bekannt ist. Das scheint mir jedoch nicht von Bedeutung zu sein - das Endziel besteht immer noch darin, zwei Nachrichten zu finden, die denselben Hash erzeugen.

Was sind die wesentlichen Unterschiede bei der Durchführung eines zweiten Preimage-Angriffs und eines Kollisionsangriffs? Was sind die Unterschiede in den Ergebnissen?

(Abgesehen davon kann ich diese Frage nicht richtig kennzeichnen. Ich versuche, die Tags "Cryptography Security Pre-Image Collision" anzuwenden, habe aber nicht genug Reputation. Kann jemand die entsprechenden Tags anwenden?)

Ich kann den Unterschied für Sie mit Angriffsszenarien motivieren.

In einem ersten Preimage-Angriff bitten wir einen Gegner, der nur hat, oder einige zu finden so dass = . Angenommen, eine Website speichert in ihren Datenbanken anstelle von . Die Website kann weiterhin die Authentizität des Benutzers überprüfen, indem das Kennwort akzeptiert und (mit einer Wahrscheinlichkeit von für einige große für falsche Positive). Nehmen wir nun an, diese Datenbank ist durchgesickert oder anderweitig komprimiert. Ein erster Preimage-Angriffm 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\}$1 / 2 n$H(input) =? H(password)$$1/2^n$$n$Dies ist die Situation, in der ein Gegner nur Zugriff auf einen Nachrichtenauszug hat und versucht, eine Nachricht zu generieren, die mit diesem Wert hascht.

In einem zweiten Preimage-Angriff lassen wir dem Gegner mehr Informationen zu. Insbesondere geben wir ihm nicht nur sondern auch . Man betrachte die Hash-Funktion wobei und große Primzahlen sind und eine öffentliche Konstante ist. Offensichtlich wird dies für einen ersten Preimage-Angriff zum RSA-Problem und gilt als schwierig. Im Falle des zweiten Preimage-Angriffs wird es jedoch leicht, eine Kollision zu finden. Wenn man , istm 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}$. Und so hat der Gegner eine Kollision mit wenig bis gar keiner Berechnung gefunden.

Wir möchten, dass One-Way-Hash-Funktionen aufgrund von Schemata für digitale Signaturen resistent gegen Second-Pre-Image-Angriffe sind. In diesem Fall wird als öffentliche Information betrachtet und (durch eine Indirektionsebene) mit jeder Kopie des Dokuments weitergegeben. Hier hat ein Angreifer Zugriff auf und . Wenn der Angreifer eine Variation des Originaldokuments (oder eine völlig neue Nachricht) so dass , könnte er sein Dokument veröffentlichen, als wäre er der ursprüngliche Unterzeichner.$H(document)$$document$$H(document)$$d'$$H(d') = H(document)$

Ein Kollisionsangriff bietet dem Gegner noch mehr Möglichkeiten. In diesem Schema bitten wir den Gegner (kann ich ihn Bob nennen?), Zwei beliebige Nachrichten und so dass . Aufgrund des Pigeonhole-Prinzips und des Geburtstagsparadoxons sind selbst 'perfekte' Hash-Funktionen quadratisch schwächer für Kollisionsangriffe als Preimage-Angriffe. Mit anderen Worten, wenn eine unvorhersehbare und irreversible Nachrichtenauszugsfunktion die Zeit benötigt, um Gewalt anzuwenden, kann eine Kollision auftreten immer in der erwarteten Zeit gefunden werden .m 2 H ( m 1 ) = H ( m 2 ) f ( { 0 , 1 } ∗ ) = { 0 , 1 } n O ( 2 n$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 kann einen Kollisionsangriff auf viele Arten zu seinem Vorteil nutzen. Hier ist eine der einfachsten: Bob findet eine Kollision zwischen zwei Binärdateien und ( ), sodass b ein gültiger Microsoft Windows-Sicherheitspatch und Malware ist. (Bob arbeitet für Windows). Bob schickt seinen Sicherheitspatch die Befehlskette hoch, wo sie hinter einem Tresor den Code signieren und die Binärdatei an Windows-Benutzer auf der ganzen Welt senden, um einen Fehler zu beheben. Bob kann jetzt mit und der Signatur, die Microsoft für berechnet hat , alle Windows-Computer auf der ganzen Welt kontaktieren und infizierenb ' H ( b ) = H ( b ' ) b ' b '$b$$b'$$H(b) = H(b')$$b'$$b'$$b$. Über diese Art von Angriffsszenarien hinaus ist es auch wahrscheinlicher, dass eine Hash-Funktion vor dem Bild geschützt ist, wenn angenommen wird, dass sie kollisionssicher ist.

Kollisionsangriffe mögen viel einfacher sein, aber wenn sie erfolgreich sind, sind sie viel weniger nützlich.

Das Problem, das Ross als das Problem des diskreten Protokolls bezeichnet, ist in Wirklichkeit ein ganz anderes Problem, das RSA-Problem, das viel mehr mit der Berechnung von Roots als mit dem diskreten Protokoll zusammenhängt.