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

24

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

Thomas Owens
źródło
1
Twoje wrażenie jest prawidłowe - na tym polega różnica. Częścią, w której się mylisz, jest to, że jest to OGROMNA różnica w praktyce. Jedną rzeczą jest znalezienie dwóch dowolnych elementów, które mają kolizję, a drugą jest znalezienie kolizji dla określonego tekstu jawnego. Na przykład, jeśli chcesz sfałszować określoną wiadomość, nie ma sensu dokonywać fałszowania egzystencjalnego - potrzebujesz innej wiadomości, która łączy się z tym samym co wiadomość, którą przechwyciłeś.
Adrian Petrescu,
@Adrian Petrescu: Czy mógłbyś udzielić odpowiedzi i być może rozwinąć ją nieco dalej? Dodać takie rzeczy, na przykład, kiedy każda (zapewniająca sytuację do ataku preimage, ale nie do ataku kolizyjnego) najlepiej nadaje się?
Thomas Owens,

Odpowiedzi:

27

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 eH.(m)mmH.(m)H.(m){usmirname,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{usmirnzammi,pzassworre}H(input)=?H(password)1/2nnPierwszym 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 dH(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 ) dH(m)=mdmodpqpqdm=mpq+m . I tak przeciwnik znalazł kolizję, w której obliczenia były niewielkie lub żadne.H(mpq+m)=(mpq+m)dmodpq=mdmodpq

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)reodoummintH.(reodoummint). 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 )reH.(re)=H.(reodoummint) 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 } ) = { 0m1m2)H.(m1)=H.(m2)) 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 ) .fa({0,1})={0,1}nO(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 bbbH.(b)=H.(b)bbb. 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.

Ross Snider
źródło
To pięknie wyjaśnione. O wiele więcej matematyki, niż szukałem, ale bardzo doceniam wysiłek - śledziłem cię przez cały czas. Dzięki.
Thomas Owens,
I wow. Kolega z RIT.
Thomas Owens,
1
Jak leci Thomas? Myślę, że miałeś fizykę z moim przyjacielem Alanem Meekinsem. Miło widzieć ludzi z RIT tutaj! Dziękujemy również za zaakceptowanie odpowiedzi.
Ross Snider
Całkiem dobre. Jeśli zamierzasz być w pobliżu kampusu jesienią i interesujesz się bezpieczeństwem, być może uda nam się to nadrobić osobiście. Tego lata robiłem pewne prace związane z bezpieczeństwem (stosowanie stenografii, steganizy, szyfrowania klucza publicznego, podpisów cyfrowych) i chciałbym usłyszeć o stronie teoretycznej (tak bardzo, jak mnie to interesuje - nie mam czas lub zaplecze matematyczne, aby przejrzeć wiele artykułów na ten temat).
Thomas Owens,
[email protected]
Ross Snider
2

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

Jukka Suomela
źródło
1

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.


źródło
2
To z pewnością prawda! Ups Początkowo korzystałem z problemu z logami dyskretnymi, a później edytowałem szczegóły schematu. Dobry chwyt Nie jestem pewien, czy stanowi to nową odpowiedź - prawdopodobnie lepiej byłoby zostawić jako komentarz pod moją odpowiedzią.
Ross Snider