r   e   k   l   a   m   a
r   e   k   l   a   m   a

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

Strona główna AktualnościBEZPIECZEŃSTWO

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.

r   e   k   l   a   m   a

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

Dwa identyczne gwoździe do trumny

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

Co najważniejsze, nie musi być NSA, to może być każdy, kto w kieszeni ma trochę pieniędzy. Koszt wynajęcia chmury Amazon EC2 (i to w godzinach szczytu) do przeprowadzenia tej operacji wyniósłby bowiem 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 Xeon E5-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 konkretne zagrożenie dla bezpieczeństwa sieci (i nic dziwnego, do dziś możemy spotkać urzędy certyfikacji wydające certyfikaty SSL na bazie SHA-1 – i to mimo tego, że wiodące przeglądarki przestały takie certyfikaty akceptować). Kod zostanie ujawniony za trzy miesiące, zgodnie z polityką odpowiedzialnych ujawnień prowadzoną przez firmę. Póki co ze strony shattered.io możemy sobie jedynie pobrać dwa „zderzone” pliki PDF i przetestować 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 niezwykle szybka (szybsza od SHA-1) i przynajmniej tak samo bezpieczna jak SHA-3.

Git nie musi się spieszyć, ale SVN już tak

Stworzony przez Linusa Torvaldsa system kontroli wersji git wykorzystywany jest nie tylko w rozwoju Linuxa, ale i setek innych projektów software’owych. Nic więc dziwnego, że to Linusa zapytano o zdanie w kwestii odkrycia kolizji w SHA-1, standardowo przez 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-1 jak ludzie chcą powiedzieć? Prawdopodobnie nie – pisał Torvalds.

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

Tymczasem… ktoś wgrał te dwa pliki PDF, wygenerowane jako dowód kolizji w SHA-1 do systemu kontroli wersji 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 takie skolidowane pliki psują SVN na dobre. Nawet po usunięciu tych plików, system kontroli wersji 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 WebKit jest podatny na atak typu cache poisoning z wykorzystaniem kolizji SHA-1 i wgrał te dwa plik PDF, nie spodziewając się, że mogą one wykończyć sam system kontroli wersji. Administratorzy SVN póki co mogą ratować się narzędziem, które blokuje możliwość wgrania skolidowanych plików. Według jego twórców poradzi sobie ze wszystkimi kolizjami, nie tylko z tymi PDF-ami.

Bez histerii, ale…

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

Napastnik musiałby umieścić się bezpośrednio między kryptograficznym skrótem a opisywaną przez niego zawartością. Nikt zaś nie potrafi wziąć na celownik dowolnego skrótu, generując dla niego równoważny plik (tzw. atak pre-image). To nie jest możliwe nawet dla MD5. Najlepszy taki atak japońskich matematyków jest kompletnie niepraktyczny, ma złożoność na poziomie 2123,4. Biorąc zaś pod uwagę to, że bezpieczeństwo gita nie 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 kodzie Linuksa.

© dobreprogramy
r   e   k   l   a   m   a
r   e   k   l   a   m   a

Komentarze

r   e   k   l   a   m   a
r   e   k   l   a   m   a
Czy wiesz, że używamy cookies (ciasteczek)? Dowiedz się więcej o celu ich używania i zmianach ustawień.
Korzystając ze strony i asystenta pobierania wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.