Dwa gwoździe do trumny SHA‑1 wbite w SVN. Linus mówi jednak – bez paniki!

Już w 2005 roku zespół chińskich matematyków podkierownictwem Xiaoyun Wana wykazał, że SHA-1 nie jest wolne odkolizji, innymi słowami można stworzyć algorytm, który znajdziekolizje (dwa różne pliki o takim samym kryptograficznym skrócie)szybciej, niż czysto siłowy atak. Jak to jest możliwe? FunkcjaSHA-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 nawejściu, a skończoną liczbę wyników funkcji na wyjściu, tooznacza to, że istnieje nieskończenie wiele możliwych kolizji.Siłowe ich znalezienie oznaczania konieczność przeszukania 280przypadkowych ciągów, by znaleźć wśród nich jedną parę, którazwróci nam taką samą wartość. 280 to jednak ogromna liczba,ponad 1,2 kwadryliona (1,2×1024), więcej niż atomów wewszechświecie.

Opracowana przez Chińczyków metoda, bazująca na wcześniejszychtechnikach opracowanych na potrzeby ataków na funkcje haszująceSHA-0 i MD5, znacząco osłabiła wymogi ataków – znalezieniekolizji w ten sposób wymagało 269 operacji. W szczególnościzaprezentowano kolizję dla 58 cykli SHA-1 (całość to 80 cykli) zapomocą już „tylko” 233 operacji. Kolejne ulepszeniaprzychodziły rok po roku – zespół Xiaoyun Wanga obniżyłpoprzeczkę dla całości do 263, potem francuscy matematycyChristophe De Canniere i Christian Rechberger pokazali kolizję dla64 cykli za pomocą 235 operacji, wreszcie zaś rosyjski matematykJewgienij 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 znalezionobłąd… Postęp sprowadzał się do poszukiwania mocy obliczeniowej.

Z punktu widzenia matematyków SHA-1 było już jednak złamane.To ci okropni inżynierowie czuli się bezpiecznie, zakładając żeok. 9,2×1018 operacji to dużo i można spać spokojnie.

Zaprezentowany w ostatni czwartek artykułbadaczy z Centrum Wiskunde & Informatica Amsterdam i GoogleResearch pt. The first collision for full SHA-1 nie jest tujakoś przełomowy od strony teoretycznej. Z tego co piszą już wabstrakcie, wysiłek obliczeniowy potrzebny do znalezienia kolizjijest równoważny 263,1 operacji – zajął 6,5 tys. lat pracy CPU i100 lat pracy GPU. Przełomowe są zasoby, jakimi dysponowali badaczei optymalizacje, jakie zastosowali, by wykorzystać rozproszoneklastry obliczeniowe. Ich sukces dowiódł, że napastnik dysponującysuperkomputerami może bezpieczeństwo SHA-1 złamać.

Co najważniejsze, nie musi być NSA, to może być każdy, kto wkieszeni ma trochę pieniędzy. Koszt wynajęcia chmury Amazon EC2 (ito w godzinach szczytu) do przeprowadzenia tej operacji wyniósłbybowiem 560 tys. dolarów. Pomogła tu ogromnie możliwośćwykorzystania w obliczeniach GPU, a konkretnie układów K40 Nvidii.Zużywając jedynie 2,5 raza więcej energii niż 10-rdzeniowy XeonE5-2650, układ taki był 25-krotnie wydajniejszy od procesora Intela(ciekawostką niech będzie, że prototyp ataku opracowywano na„domowej” karcie graficznej GTX 970).

To osiągnięcie naukowe nie zostało udokumentowane kodemźródłowym, ludzie z Google potraktowali je bowiem jako konkretnezagrożenie dla bezpieczeństwa sieci (i nic dziwnego, do dziśmożemy spotkać urzędy certyfikacji wydające certyfikaty SSL nabazie SHA-1 – i to mimo tego, że wiodące przeglądarki przestałytakie certyfikaty akceptować). Kod zostanie ujawniony za trzymiesiące, zgodnie z polityką odpowiedzialnych ujawnień prowadzonąprzez firmę. Póki co ze strony shattered.iomożemy sobie jedynie pobrać dwa „zderzone” pliki PDF iprzetestować swoje pliki, czy czasem nie były częścią ataku.

W ciągu tych trzech miesięcy wszystkie usługi, które polegająna SHA1 do uwierzytelniania i podpisywania danych, powinny przejśćna bezpieczniejsze funkcje haszujące. Sugeruje się SHA256 i SHA-3,ale naszym zdaniem znacznie ciekawszym (choć nieco egzotycznym)wyborem może być BLAKE2 –bazująca na SHA3 i szyfrze ChaCha funkcja, która jest niezwykleszybka (szybsza od SHA-1) i przynajmniej tak samo bezpieczna jakSHA-3.

Stworzony przez Linusa Torvaldsa system kontroli wersji gitwykorzystywany jest nie tylko w rozwoju Linuxa, ale i setek innychprojektów software’owych. Nic więc dziwnego, że to Linusazapytano o zdanie w kwestii odkrycia kolizji w SHA-1, standardowoprzez git wykorzystywanej. Zdanie okazało się… lekceważące.*Wątpię, by niebo spadło gitowi na głowę. Czy chcemy przejśćna inną funkcję haszującą? Tak. Czy to „koniec gry” dla SHA-1jak ludzie chcą powiedzieć? Prawdopodobnie nie – *pisałTorvalds.

Linus podkreślił, że gitwykorzystuje dodatkowo mechanizm kodowania rozmiaru pliku, przez cokolizja obiektów gita będzie znacznie trudniejsza, co więcej,można wprowadzić dodatkowe testy, które utrudnią ukrycie się wsfałszowanych plikach.

Tymczasem… ktoś wgrał te dwa plikiPDF, wygenerowane jako dowód kolizji w SHA-1 do systemu kontroliwersji silnika renderującego WebKit. Bazuje on na Apache SVN(Subversion), wykorzystując niebezpieczną funkcję do śledzenia iłączenia zduplikowanych plików. Okazało się, że takieskolidowane pliki psująSVN na dobre. Nawet po usunięciu tych plików, system kontroliwersji nie mógł wstać. Obecnie nie przyjmuje dalszych commitów –i nie bardzo wiadomo, jak naprawić tak popsute repozytorium.

Prawdopodobnie nie była to złośliwość,lecz raczej krótkowzroczność. Ktoś chciał sprawdzić, czy WebKitjest podatny na atak typu cache poisoning z wykorzystaniem kolizjiSHA-1 i wgrał te dwa plik PDF, nie spodziewając się, że mogą onewykończyć sam system kontroli wersji. Administratorzy SVN póki comogą ratować się narzędziem,które blokuje możliwość wgrania skolidowanych plików. Wedługjego twórców poradzi sobie ze wszystkimi kolizjami, nie tylko ztymi PDF-ami.

Zanim potępimy Linusa zanieostrożność, trzeba pamiętać, że medialna histeria to niematematyczna teoria. Na infografikach można oczywiście narysowaćsobie, jak to cyberprzestępca łatwo podmienia np. plik aktualizacjisystemu operacyjnego plikiem ze złośliwym kodem, ale to w wypadkugita nie działa w ten sposób.

Napastnik musiałby umieścić siębezpośrednio między kryptograficznym skrótem a opisywaną przezniego zawartością. Nikt zaś nie potrafi wziąć na celownikdowolnego skrótu, generując dla niego równoważny plik (tzw. atakpre-image). To nie jest możliwe nawet dla MD5. Najlepszy taki atakjapońskichmatematyków jest kompletnie niepraktyczny, ma złożoność napoziomie 2123,4. Biorąc zaś pod uwagę to, że bezpieczeństwo gitanie zależy od SHA-1, właściwie funkcję tę stosuje się użytkowo,nie ma co się martwić, że nagle ktoś podrobi commity w kodzieLinuksa.