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ę.
Związek z preimage resistance
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
iB
, - 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
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
- RFC 4270 „Attacks on Cryptographic Hashes in Internet Protocols”