Second preimage resistance

Second preimage resistance (odporność na znalezienie drugiego przeciwobrazu) – właściwość funkcji kryptograficznej H, taka że dla danej wiadomości m1 nieznana jest żadna szybka metoda znalezienia takiego m2 różnego od m1, że ich skróty są sobie równe.

Brak second preimage resistance implikuje brak odporności na kolizje. Brak preimage resistance implikuje brak second preimage resistance. Obie implikacje są tylko w jedną stronę.

Jeśli funkcja nie ma własności preimage resistant, to nie jest też second preimage resistant; dla danej wiadomości m1 liczymy skrót h, po czym go odwracamy, znajdując takie m2, że H(m2) = h = H(m1). Ponieważ przestrzeń wiadomości jest o wiele większa od przestrzeni skrótów, z prawdopodobieństwem bliskim 1 m1 i m2 są różne.

Można łatwo zbudować funkcję skrótu, która jest preimage resistant, ale nie jest second preimage resistant. Weźmy na przykład następującą funkcję:

  • dzielimy wejście na dwie połowy, A i B,
  • wynikiem jest SHA1(A). B nie ma wpływu na wynik.

Funkcja ta nie jest second preimage resistant, mając m1 możemy znaleźć inną wiadomość o tym samym skrócie zmieniając dowolne bity drugiej połowy wiadomości. Jednak o ile nie złamiemy SHA1 nie potrafimy znając tylko skrót h znaleźć takiej wiadomości m, że H(m)=h.

Związek z odpornością na kolizje

edytuj

Jeśli funkcja nie ma własności second preimage resistant, potrafimy dla danego m1 znaleźć takie inne m2 że mają one równe skróty. Para taka stanowi kolizje, więc funkcja nie jest odporna na kolizje.

Możemy łatwo zbudować funkcje skrótu, która nie jest odporna na kolizje, ale jest second preimage resistant. Weźmy dowolną bezpieczną funkcję skrótu (np. SHA1) i obetnijmy jej wynik do k bitów, tak żebyśmy potrafili wykonać   obliczeń wartości funkcji skrótu, ale już nie  

Taka sytuacja ma obecnie miejsce dla   w przedziale (orientacyjnie) od 80 do nawet 128. Na granicy tej kategorii jest więc m.in. najpopularniejsza funkcja skrótu MD5.

Linki zewnętrzne

edytuj