Ataki urodzinowe i kolizyjne

W grupie 23 osób prawdopodobieństwo, że dwoje z nich ma urodziny tego samego dnia, przekracza 50%. W grupie 70 osób przekracza 99,9%. Matematycznie: w zbiorze o rozmiarze N prawdopodobieństwo kolizji przekracza 50% po około ~√N próbach. To jest granica urodzinowa.

Dla n-bitowej funkcji skrótu kolizję (H(m1) = H(m2), m1 ≠ m2) można znaleźć za pomocą około 2^{n/2} losowych prób. Dla SHA-256 (256-bitowego) znalezienie kolizji wymaga około 2^{128} operacji — jest obliczeniowo niewykonalne. Dla MD5 (128-bitowego) jest to około 2^{64} operacji — na granicy wykonalności.

Ogólne znajdowanie kolizji: wygeneruj 2^{n/2} losowych wiadomości, oblicz ich skróty, posortuj je według wartości skrótu i znajdź duplikaty. Pamięć O(2^{n/2}). Algorytm Rho (wyszukiwanie cyklu Floyda) zmniejsza zużycie pamięci do O(1) przy takim samym koszcie czasowym. Równoległe wyszukiwanie kolizji van Oorschota-Wienera skraca czas dzięki wykorzystaniu sprzętu.

Praktyczne kolizje MD5 znaleźli Wang i in. (2004), używając kryptoanalizy różnicowej — nie ataku urodzinowego. Dwie różne wiadomości o długości 1024 bitów mogą w ciągu kilku sekund otrzymać identyczny skrót MD5. Hertzbleed i kolizje z wybranym prefiksem umożliwiają tworzenie kolizji certyfikatów. MD5 jest całkowicie złamany pod względem odporności na kolizje.

Bardziej zaawansowany wariant: dla dwóch dowolnych prefiksów P1 i P2 znajdź przyrostki S1 i S2 takie, że H(P1||S1) = H(P2||S2). Stevens i in. (2017) znaleźli kolizje MD5 z wybranym prefiksem. Użyto ich do utworzenia złośliwego certyfikatu CA z prawidłowym podpisem MD5. W rezultacie wycofano MD5 z użycia przy certyfikatach.

SHAttered firmy Google (2017) była pierwszą praktyczną kolizją SHA-1. Dwa różne pliki PDF miały ten sam skrót SHA-1. Wymagało to 2^{63.1} obliczeń funkcji kompresującej SHA-1 — równowartość 6500 lat pracy CPU i 110 lat pracy GPU. Koszt wyniósł około 110 000 USD. Przeglądarki wycofały obsługę certyfikatów SHA-1 w 2017 roku.

W przypadku funkcji skrótu Merkle-Damgarda (MD5, SHA-1, SHA-2), jeśli zna się H(m), można obliczyć H(m||padding||m') bez znajomości m. Łamie to konstrukcje MAC, takie jak H(secret||message). Rozwiązanie: należy używać HMAC (wykorzystującego wewnętrzne i zewnętrzne dopełnienie) albo SHA-3 (konstrukcja gąbczasta, odporna na rozszerzenie długości).

Odporność na kolizje: znalezienie dowolnych dwóch różnych wiadomości o tym samym skrócie wymaga pracy rzędu 2^{n/2}. Odporność na drugi preobraz: mając m, znalezienie m' ≠ m o tym samym skrócie wymaga pracy rzędu 2^n. Odporność na preobraz: znalezienie dowolnej wiadomości dla danego skrótu wymaga pracy rzędu 2^n. Kolizje są zawsze najsłabszym ogniwem.

Jeśli MAC wykorzystuje funkcję skrótu podatną na kolizje, atakujący, który potrafi znaleźć kolizje w H, może fałszować kody MAC. HMAC-MD5 uważa się za bezpieczny mimo kolizji MD5, ponieważ konstrukcja HMAC wymaga ataków na preobraz, a nie samych kolizji. Jednak w nowych systemach należy odchodzić od HMAC-MD5.

Joux (2004) wykazał, że w przypadku funkcji skrótu Merkle-Damgarda znalezienie kolizji 2^k-krotnych (2^k wiadomości o tym samym skrócie) wymaga jedynie k razy tyle pracy co znalezienie pojedynczej kolizji, a nie k razy tyle pracy jak przy niezależnym wyszukiwaniu. Potęguje to podatności połączonych funkcji skrótu (H1(m)||H2(m) nie jest tak silne, jak mogłoby się wydawać).

Należy używać SHA-256 lub SHA-3 do tworzenia skrótów odpornych na kolizje. MD5 i SHA-1 należy omijać w każdym zastosowaniu związanym z bezpieczeństwem. W przypadku MAC-ów należy używać HMAC-SHA-256 lub HMAC-SHA-3. Do haszowania haseł należy stosować Argon2, a nie bezpośrednio SHA-2. Gdy wymagana jest odporność na rozszerzenie długości, zawsze należy używać SHA-3.

W przybliżeniu ile obliczeń funkcji skrótu potrzeba, aby znaleźć kolizję w n-bitowej funkcji skrótu?

Atak urodzinowy znajduje kolizje skrótu przy nakładzie pracy rzędu 2^{n/2}. MD5 ma praktyczne kolizje z wybranym prefiksem, a SHA-1 został złamany w 2017 roku. Ataki z rozszerzeniem długości łamią naiwne kody MAC w postaci H(key||msg). Należy używać SHA-256 lub SHA-3, a do uwierzytelniania wiadomości — HMAC. Następnie: ataki meet-in-the-middle.