Kliknąłeś w wilka brawo !

Z hukiem media internetowe ogłosiły koniec funkcji haszującej SHA-1, powszechnie wykorzystywanej w weryfikacji autentyczności plików, łatek aktualizacji czy nawet certyfikatów SSL. Problem w tym, że SHA-1 było skończone już od wielu lat. Zaprezentowanie w zeszłym tygodniu pierwszej realnej kolizji plików, tj. dwóch PDF-ów, które mając taki sam kryptograficzny skrót, a różną zawartość, było nieuchronne. Nieuchronność tę po prostu lekceważono, zlekceważył ją nawet Linus Torvalds – i to w dzień przedstawienia tych felernych plików. A teraz kolizja w SHA-1 wykończyła system kontroli wersji silnika WebKit.

Już w 2005 roku zespół chińskich matematyków pod kierownictwem Xiaoyun Wana wykazał, że SHA-1 nie jest wolne od kolizji, innymi słowami można stworzyć algorytm, który znajdzie kolizje (dwa różne pliki o takim samym kryptograficznym skrócie) szybciej, niż czysto siłowy atak. Jak to jest możliwe? Funkcja SHA-1 zwraca z dowolnego źródłowego ciągu danych 160-bitowy skrót (hash). Jako że mamy nieskończoną liczbę możliwych ciągów na wejściu, a skończoną liczbę wyników funkcji na wyjściu, to oznacza to, że istnieje nieskończenie wiele możliwych kolizji. Siłowe ich znalezienie oznaczania konieczność przeszukania 280 przypadkowych ciągów, by znaleźć wśród nich jedną parę, która zwróci nam taką samą wartość. 280 to jednak ogromna liczba, ponad 1,2 kwadryliona (1,2×1024), więcej niż atomów we wszechświecie.

Opracowana przez Chińczyków metoda, bazująca na wcześniejszych technikach opracowanych na potrzeby ataków na funkcje haszujące SHA-0 i MD5, znacząco osłabiła wymogi ataków – znalezienie kolizji w ten sposób wymagało 269 operacji. W szczególności zaprezentowano kolizję dla 58 cykli SHA-1 (całość to 80 cykli) za pomocą już „tylko” 233 operacji. Kolejne ulepszenia przychodziły rok po roku – zespół Xiaoyun Wanga obniżył poprzeczkę dla całości do 263, potem francuscy matematycy Christophe De Canniere i Christian Rechberger pokazali kolizję dla 64 cykli za pomocą 235 operacji, wreszcie zaś rosyjski matematyk Jewgienij Grecznikow rozszerzył atak Francuzów na 73 cykle z 80. Potem trochę sprawa ucichła – teoretycznych przełomów nie było, w pracy z 2009 roku w której sugerowano złożoność 252 znaleziono błąd… Postęp sprowadzał się do poszukiwania mocy obliczeniowej.