Second preimage resistance
Z Wikipedii
Second preimage resistance (odporność na znalezienie drugiego przeciwobrazu) to właściwość funkcji kryptograficznej H, taka że dla danej wiadomości m1 nie znana jest żadna szybka metoda znalezienia takiego m2 różnego od m1, że ich hasze 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ę.
[edytuj] Związek z preimage resistance
Jeśli funkcja nie jest preimage resistant, to nie jest też second preimage resistant; dla danej wiadomości m1 liczymy hasz 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 haszy, z prawdopodobieństwem bliskim 1 m1 i m2 są różne.
Można łatwo zbudować funkcję haszującą, 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 haszu zmieniając dowolne bity drugiej połowy wiadomości. Jednak o ile nie złamiemy SHA1 nie potrafimy znając tylko hasz h znaleźć takiej wiadomości m, że H(m)=h
[edytuj] Związek z odpornością na kolizje
Jeśli funkcja nie jest second preimage resistant, potrafimy dla danego m1 znaleźć takie inne m2 że mają one równe hasze. Para taka stanowi kolizje, więc funkcja nie jest odporna na kolizje.
Możemy łatwo zbudować funkcje haszującą, która nie jest odporna na kolizje, ale jest second preimage resistant. Weźmy dowolną bezpieczną funkcję haszującą (np. SHA1) i obetnijmy jej wynik do k bitów, tak żebyśmy potrafili wykonać 2k / 2 obliczeń wartości funkcji haszującej, ale już nie 2k.
Taka sytuacja ma obecnie miejsce dla k w przedziale (orientacyjnie) od 80 do nawet 128. Na granicy tej kategorii jest więc m.in. najpopularniejsza funkcja haszująca MD5.
