Jaka jest różnica między drugim atakiem preimage a atakiem kolizyjnym?

Wikipedia definiuje drugi atak preimage jako:

biorąc pod uwagę ustaloną wiadomość m1, znajdź inną wiadomość m2, taką jak hash (m2) = hash (m1).

Wikipedia definiuje atak zderzeniowy jako:

znajdź dwa dowolne różne komunikaty m1 i m2 takie, że hash (m1) = hash (m2).

Jedyną różnicą, którą widzę, jest to, że w drugim ataku preimage m1 już istnieje i jest znany atakującemu. Nie wydaje mi się to jednak znaczące - ostatecznym celem jest znalezienie dwóch komunikatów, które wytwarzają ten sam skrót.

Jakie są zasadnicze różnice w sposobie przeprowadzania drugiego ataku preimage i ataku kolizji? Jakie są różnice w wynikach?

(Nawiasem mówiąc, nie mogę poprawnie otagować tego pytania. Próbuję zastosować tagi „kolizja zabezpieczenia przed kryptografią przed obrazem”, ale nie mam wystarczającej reputacji. Czy ktoś może zastosować odpowiednie tagi?)

Mogę zmotywować dla ciebie różnicę za pomocą scenariuszy ataku.

W pierwszym ataku preimage prosimy przeciwnika, któremu podano tylko , aby znalazł m lub trochę m ′, tak aby H ( m ′ ) = H ( m ) . Że witryna przechowuje { ù s e r n o m e , H ( t y y W O R d ) } w swojej bazie danych zamiast { ù s $H(m)$$m$$m'$$H(m')$$H(m)$$\{username, H(password)\}$ . Witryna nadal może zweryfikować autentyczność użytkownika, akceptując hasło i porównując H ( i n p u t ) = ? H ( P y y W O r d ) (z prawdopodobieństwem 1 / 2 n niektórych dużych n fałszywie dodatnich). Załóżmy teraz, że ta baza danych wyciekła lub jest w inny sposób skompromitowana. ZA$\{username, password\}$$H(input) =? H(password)$$1/2^n$$n$Pierwszym atakiem na obraz jest sytuacja, w której przeciwnik ma dostęp tylko do podsumowania wiadomości i próbuje wygenerować wiadomość mieszającą się z tą wartością.

W drugim ataku preimage pozwalamy przeciwnikowi uzyskać więcej informacji. W szczególności nie tylko dajemy mu ale także dajemy mu m . Rozważ funkcję skrótu H ( m ) = m $H(m)$$m$ gdzie p i q są dużymi liczbami pierwszymi, a d jest stałą publiczną. Oczywiście w przypadkupierwszego ataku typu preimagestaje się to problemem RSA i uważa się go za trudny. Jednak w przypadkudrugiego ataku preimageznalezienie kolizji staje się łatwe. Jeśli ustawimy 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$ . I tak przeciwnik znalazł kolizję, w której obliczenia były niewielkie lub żadne.$H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$

Chcielibyśmy funkcja jednokierunkowa mieszania się odporne na drugi atak preimage ponieważ systemów podpisu cyfrowego, w którym to przypadku jest uważana informacja publiczna i przedostaje się (przez poziom pośredni) z każda kopia dokumentu. Tutaj atakującemu ma dostęp zarówno do d o, c U m e n t i H ( d o, c u m e n t $H(document)$$document$$H(document)$. Jeśli osoba atakująca może wymyślić wariant oryginalnego dokumentu (lub całkowicie nową wiadomość) taki że H ( d ′ ) = H ( d o c u m e n t $d'$$H(d') = H(document)$ mógłby publikuje jego dokument, tak jakby oryginalny podpisujący.

Atak kolizji pozwala przeciwnik jeszcze więcej możliwości. W tym schemacie prosimy przeciwnika (czy mogę go nazwać Bobem), aby znalazł jakieś dwie wiadomości i m 2, takie, że H ( m 1 ) = H ( m 2 ) . Z uwagi na zasadę szufladki i paradoks urodzinowy nawet „idealne” funkcje skrótu są kwadratowo słabsze w przypadku ataków kolizyjnych niż ataki preimage. Innymi słowy, biorąc pod uwagę nieprzewidywalną i nieodwracalną funkcję podsumowania wiadomości f ( { 0 , 1 } ∗ ) = { $m_1$$m_2$$H(m_1) = H(m_2)$ który zajmuje czas O ( 2 n ) do brutalnej siły, kolizję zawsze można znaleźć w oczekiwanym czasie O ( s q r t ( 2 n ) ) = O ( 2 n / 2 ) .$f(\{0,1\}^*) = \{0,1\}^n$$O(2^n)$$O(sqrt(2^n)) = O(2^{n/2})$

Bob może wykorzystać atak kolizyjny na wiele sposobów. Oto jeden z najprostszych: Bob znajduje kolizję między dwoma binariami i b ′ ( H ( b ) = H ( b ′ ) ) w taki sposób, że b jest prawidłową poprawką bezpieczeństwa systemu Microsoft Windows, a b ' jest złośliwym oprogramowaniem. (Bob działa w systemie Windows). Bob wysyła swoją łatkę bezpieczeństwa do łańcucha dowodzenia, gdzie za skarbcem podpisują kod i wysyłają plik binarny do użytkowników systemu Windows na całym świecie, aby naprawić błąd. Bob może teraz kontaktować się i infekować wszystkie komputery z systemem Windows na całym świecie za pomocą b ′ i podpisu, który Microsoft obliczył dla $b$$b'$$H(b) = H(b')$$b'$$b'$$b$. Poza tego rodzaju scenariuszami ataku, jeśli uważa się, że funkcja skrótu jest odporna na kolizję, to funkcja skrótu jest również bardziej odporna na preimage.

Ataki zderzeniowe mogą być znacznie łatwiejsze, ale jeśli się powiedzą, są znacznie mniej przydatne.

Problem, który Ross wymienia jako dyskretny log, jest w rzeczywistości zupełnie innym problemem, problemem RSA, który jest znacznie bardziej związany z obliczaniem korzeni niż z logiem dyskretnym.