Specjaliści o bezpieczeństwie algorytmu SHA-1
O komentarz do sprawy złamania algorytmu haszującego SHA-1 poprosiliśmy Bartosza Żółtaka – specjalistę z dziedziny kryptografii, odktywcę funkcji VMPC, Krzysztofa Maćkowiaka – autora serwisu kryptografia.com oraz Wojciecha Wileńskiego z firmy Unizeto.
Zdaniem Bartosza Żółtaka atak robi naprawdę duże wrażenie, a publikacje na jego temat mogą zostać przedstawione na jednej z najbliższych konferencji kryptograficznych.
Praca budzi respekt wobec grupy kryptologów z Shandong University w Chinach. Miesiąc temu kryptolog światowej sławy Vincent Rijmen (współautor algorytmu AES!) opublikował na łamach IACR ePrint archive swoje wyniki, w których znalazł kolizje w SHA-1 zredukowanej do 53 rund wymagającą 2^71 operacji. Jednocześnie stwierdził: „Jest jasne, że jesteśmy ciągle daleko od znalezienia choćby teoretycznego ataku na pełne SHA-1”.
Wynik naukowców z Chin nie tylko ma złożoność mniejszą niż wynik Rijmena
sprzed miesiąca (2^69 vs 2^71), ale także odnosi się do pełnego SHA-1. Co więcej dla zredukowanego do 58 rund SHA-1 zespół z Chin znalazł atak o złożoności zaledwie 2^33.
Zwróćmy uwagę, że 2^33 to tylko około 8,5 miliarda operacji! Złamać 58-rundową SHA-1 można więc na poczekaniu przy użyciu domowego komputera!
Jeśli chodzi o atak na pełną funkcją SHA-1, wymagający 2^69 operacji, to jest to wynik wstrząsająco dobry, ale na szczęście wykonanie takiej liczby operacji nie jest już w zasięgu domowych komputerów. Do oszacowania użyłem symulatora łamania haseł programu VMPC Data Securuty i otrzymałem, że – dla przykładu – dysponując 1000 komputerami 2GHz (obliczającymi 2 mld funkcji SHA-1 na sekundę)musielibyśmy liczyć około 5 lat, aby uzyskać kolizję. Ale wyższe moce są już dostępne. Dlatego myślę, że mamy poważny problem, ale też mamy trochę czasu na to, aby opracować nową funkcję hashującą.
Nie ma też powodów do paniki (np. gdyby 2^33 odnosiło się do pełnej SHA-1 – powody by były), ale wynik i tak robi niesamowite wrażenie. Życie SHA-1 jako bezpiecznej funkcji hashującej jest już zakończone. Bardzo interesująca będzie teraz obserwacja rozwoju nowych koncepcji funkcji hashujących. Myślę, że możemy oczekiwać wielu nowych propozycji na kolejnych konferencjach kryptograficznych.
Nigdy nie szedłem w tym kierunku, ale teoretycznie rodzina algorytmów VMPC, a dokładniej algorytm inicjowania klucza VMPC-KSA, posiada właściwości (efekt dyfuzji), które mogą pozwolić użyć go jako funkcji hashującej w połączeniu z szyfrem VMPC i algorytmem VMPC-MAC. Być może wobec takich wydarzeń przedstawię także swoją propozycję.
Komentarz Krzysztofa Maćkowiaka z serwisu kryptografia.com w sprawie złamania SHA-1:
Zadaniem funkcji haszujących, zwanych również funkcjami skrótu jest obliczenie z dowolnego ciągu danych, skrótu o stałej długości. Ważnym elementem tych funkcji jest unikalność obliczanego skrótu, czyli zagwarantowanie, iż dany skrót jest unikalny dla konkretnej wiadomości. Wykrycie dwóch wiadomości, których wynikiem jest ta sama funkcja skrótu, określane jest mianem kolizji i świadczy o słabości algorytmu. Jednokierunkowa funkcja skrótu zapewnia dodatkowo, iż niemożliwe jest wygenerowanie wiadomości źródłowej na podstawie skrótu.
Do najpopularniejszych algorytmów haszujących zaliczamy:
MD5,
SHA-1 oraz
RIPEMD-160.
Algorytm MD5 należy do serii algorytmów zaprojektowanych przez Ronalda Rivesta i został zaprojektowany w celu zastąpienia algorytmu MD4. Wykazano wiele słabości algorytmu MD4 (analiza Hansa Dobbertina). Z kryptoanalizą algorytmu MD4 można zapoznać się w pracy magisterskiej Daniela Jasionowskiego. Algorytm MD5 został opracowany w 1991 roku i zapewnia większe bezpieczeństwo niż jego poprzednik. Skrót generowany przez ten algorytm ma długość 128 bitów.
W 1996 roku Dobbertin zaprezentował analizę kolizji funkcji haszującej algorytmu MD5, co spowodowało, iż zaczęto zalecać wykorzystywanie algorytmów SHA-1 oraz RIPEMD-160. W marcu 2004 roku powstał rozproszony projekt nazywany MD5CRK. Twórcą projektu był Jean-Luc Cooke i jego współpracownicy. Projekt miał na celu wykorzystanie stacji roboczych ochotników komunikujących się z wykorzystaniem Internetu w celu znalezienia kolizji dla algorytmu MD5. Projekt zakończył się sukcesem i wykazał, że dysponując bardzo dużą mocą obliczeniową możliwe jest podrabianie generowanych podpisów.
Dopiero prace badawcze chińskich naukowców Xiaoyun Wang, Dengguo Fen, Xuejia Lai i Hongbo Yu w pełni wykazały słabość algorytmu MD5. 17 sierpnia 2004 opublikowali oni analityczny algorytm ataku, dzięki któremu do podrobienia podpisu wystarczyła godzina działania klastrowego komputera IBM P690. Opublikowali oni również informacje na temat słabości algorytmów MD4, Haval-128 oraz RIPEMD-160.
Artykuł opisujący atak chińskich kryptologów na algorytm MD5 opublikowany został również w najnowszym numerze czasopisma Hakin9.
Także w zeszłym roku francuski kryptolog Antoine Joux zaprezentował przykładową kolizję dla algorytmu SHA-0 a słabość tego algorytmu opisana została również przez izraelskich kryptologów, z których jeden – Eli Biham – znany jest z wielu innych ataków na algorytmy kryptograficzne.
Na początku roku 2005 w związku z rozwojem badań nad kryptoanalizą algorytmu SHA-1 Narodowy Instytut Standardów i Technologii (NIST) przedstawił oficjalną propozycję odnośnie zastąpienia szeroko używanej funkcji haszującej SHA-1 silniejszą i mocniejszą funkcją SHA-256 lub SHA-512. Nowe mocniejsze funkcje znajdą zastosowanie m.in. w agencjach rządowych oraz podpisach cyfrowych.
Funkcja SHA-1 oblicza z wiadomości o maksymalnej długości 2^64 bitów, skrót o stałej długości 160-bitów a dokładna specyfikacja tego algorytmu dostępny jest na stronie http://www.itl.nist.gov/fipspubs/fip180-1.htm a opis po polsku znaleźć można także na stronie http://e-handel.mm.com.pl/crypto/opis_algorytmu_sha.htm.
Atak brutalny dla tego algorytmu wymaga wykonania 2^80 operacji. Najnowszy atak chińskich kryptologów Xiaoyun Wang, Yiqun Lisa Yin, i Hongbo Yu ogranicza liczbę wymaganych operacji do 2^69. Mimo, że może się wydawać to niewielką redukcją to jest to bardzo znacząca różnica. Należy zwrócić uwagę, iż 2^70 operacji oznacza dwa razy więcej operacji niż 2^69. Czyli liczba wymaganych operacji została zmniejszona 2048 razy (2^11).
Bez wątpienia jest to w tej chwili najbardziej efektywny atak na ten algorytm. Dodatkowo naukowcy wykazali, iż znalezienie kolizji dla algorytmu SHA-0 wymaga 2^39 operacji, natomiast dla algorytmu SHA-1 ograniczonego do 58 rund do 2^33 operacji. Ta złożoność nie gwarantuje bezpieczeństwa a wygenerowanie kolizji dla tych algorytmów możliwe jest z wykorzystaniem zwykłych stacji roboczych. Liczba 2^69 operacji nadal pozostaje trudna do zrealizowania na pojedynczych maszynach. Mając jednak do dyspozycji 200 000 maszyn z procesorem 2GHz, które mogą obliczyć 2 miliardy funkcji SHA-1 na sekundę, znalezienie kolizji będzie trwało 1475739 sekund czyli zaledwie 17 dni.
Wydaje się, że zebranie takiej ilości maszyn z wykorzystaniem ochotników i Internetu jest całkiem realne a projekt podobny do MD5CRK może przynieść oczekiwany sukces.
Aktualnie pozostaje, idąc za zaleceniami NISTu proponować algorytmy SHA-256 lub SHA-512, jednak trzeba pamiętać, iż zaprezentowany atak, ze względu na taką samą budowę proponowanych algorytmów może również ograniczyć liczbę wymaganych operacji w celu znalezienia kolizji dla tych algorytmów, jednak w tym przypadku osiągnięty wynik powinien nadal zapewniać wysoki poziom bezpieczeństwa.
Z dalszymi komentarzami należy się jeszcze wstrzymać, przynajmniej do czasu opublikowania szczegółów przeprowadzonego ataku. Na pewno odkrycie chińskich kryptologów jest znaczące i może mieć duży wpływ na wykorzystywane algorytmy, a także rozwój innych algorytmów funkcji skrótu w najbliższym czasie.
Komentarz Wojciecha Wileńskiego z firmy Unizeto w sprawie złamania SHA-1:
Zakładając, że wstępne wyniki prac nad złamaniem algorytmu SHA-1
znajdą potwierdzenie, wynik naukowców z Shandong University in China można uznać za budzący uznanie. Z podejmowaniem jakichkolwiek decyzji należy jednak poczekać do momentu opublikowania wyników prac i zweryfikowania naszych domysłów. Efekt tych prac musi odnieść oddźwięk dwojakiego rodzaju. Po pierwsze w świecie kryptologów.
Kolejna bariera została złamana – tak jak przyszedł „czas” na algorytm MD2, MD4 i MD5, tak rozwijająca się technologia i wiedza człowieka rozprawiły się z algorytmem SHA-1. Zaznaczyć jednak należy, że używanie SHA-1 przestałoby być bezpieczne tylko jako funkcji skrótu. Tym samym stosowanie jej w PRF lub HMAC wciąż jest bezpieczne. Co dalej?
Niezmiennie to samo – poprzeczka dla kryptoanalityków zostanie zawieszona na wyższym poziomie. Chińscy naukowcy przejdą do historii. Wysunięte zostaną propozycje funkcji hashujących, które będą stanowić nowe wyzwanie dla maszyn obliczeniowych oraz kryptoanalityków (np. SHA-512). Po drugie na rynku komerycjnym związanym z szerokopojętym podpisem elektronicznym.
Jakie zmiany może spowodować? Jak słusznie zauważył Peter Gutmann, dwuznaczność ogłoszonego komunikatu powoduje, że bardziej prawdopodobne jest, iż wyniki badań dotyczą tzw. funkcji miażdżących, które wykorzystywane są m.in. w pełnym SHA-1. Tak więc znalezienie kolizji w pełnym SHA-1 wciąż jest trudne z matematycznego punktu widzenia. Tym samym wciąż trudne pozostaje sfałszowanie podpisu elektronicznego. Mimo to zakładając jednak, że mamy do czynienia z kolizjami w pełnym SHA-1, to jest to moment do wyrażenia uznania dla kryptologów chińskich. Nie ma natomiast powodu do paniki.
Po ogłoszeniu nowego standardu algorytmu dla funkcji skrótu, trzecie zaufne strony – centra certyfikacji zaktualizują swoje polityki certyfikacji o nowe algorytmy (SHA-1 zostałby zastąpiony np. SHA-512). Producenci oprogramowania zaktualizują mechanizmy tworzenia podpisu elektronicznego za pomocą ich aplikacji i udostępnią aktualizacje swoim klientom. Użytkownik nie odczuje zmian funkcjonalnych. Być może nie wszyscy spodziwaliśmy się, że osiągnięcie wyniku kolizji w pełnym SHA-1 na poziomie 2^69 operacji może stać się tak szybko. Istnieją inne funkcje skrótu, które są powszechnie uznane za bezpieczne (już przywoływana SHA-512, czy też SHA-256 i inne.). Umarł Król, niech żyje król.
Jeżeli chodzi o istniejące już dokumenty elektroniczne, które już są opatrzone podpisem elektronicznym (SHA1+RSA): dla takich właśnie sytuacji przewidziane zostały mechanizmy konserwacji podpisu elektronicznego, które powinno posiadać bez wyjątku, każde dobre archiwum dokumentów elektronicznych.
Książki o kryptografii:
Sekrety kryptografii
Kryptografia w praktyce
Zobacz również:
SHA-1 złamany!
SHA-1 na emeryturę
– Złamano (ECC)2-109
– Matematycy złamali RSA-576
– Łamanie szyfru RC5-72 – minął rok
– Algorytm szyfrowania w Płatniku złamany
– 109-bitowe szyfrowanie złamane
– Przełom w szyfrowaniu
– 64-bitowe szyfrowanie złamane po 4 latach
– Algorytm szyfrowania AES jako standard do produktów IPSec
– Optimus producentem i dystrybutorem urządzenia szyfrującego IPSec
– Intel szyfruje
– Szyfr UOP’u
– Specyfikacja szyfru Camelia
– Moduł szyfrowania dysku dla Linuxa
– Nowy system szyfrujący