Pierwsza praktyczna kolizja SHA-1 i co to dla wszystkich oznacza
23 lutego 2017 o 15:27 w kategorii Top Adam dodał
Google właśnie ogłosiło pierwszą praktyczna kolizję funkcji skrótu SHA-1. Dla udowodnienia, że do kolizji doszło, opublikowało dwa pliki PDF, które mimo różnej zawartości produkują identyczny skrót SHA-1. Co to jednak oznacza?
Funkcja skrótu to w skrócie algorytm, który oblicza wartość właściwą dla danego pliku czy też po prostu ciągu znaków. W założeniu wartość ta powinna być unikatowa dla danego ciągu i najmniejsza zmiana tego ciągu powinna spowodować istotną zmianę wyniku funkcji skrótu. Na przykład skrót SHA-1 dla dwóch wariantów nazwy naszej witryny będzie wyglądał tak:
SHA1(ZaufanaTrzeciaStrona) = e4110a0be14297fbd055c254e32f9e0c922a21b1 SHA1(zaufanatrzeciastrona) = a0482ace24a7ef0083b933b62758ab5ef22586d5 1 2 SHA1(ZaufanaTrzeciaStrona) = e4110a0be14297fbd055c254e32f9e0c922a21b1 SHA1(zaufanatrzeciastrona) = a0482ace24a7ef0083b933b62758ab5ef22586d5
Funkcje skrótu umożliwiają na przykład porównywanie, czy mamy do czynienia z takimi samymi plikami bez oglądania ich znak po znaku – jeśli różnią się ich skróty, to i pliki powinny być różne. Tak samo identyczny skrót powinien oznaczać, że także plik jest identyczny. I tak z reguły jest – dopóki ktoś nie wymyśli, jak stworzyć dwa różne pliki o takim samym skrócie. Ten los właśnie spotkał funkcję SHA-1, a skutki tego wydarzenia są dość istotne.
Funkcja SHA-1 powstała w roku 1995 i już po 10 latach jej istnienia pojawiły się pierwsze prace teoretyczne opisujące, jak można doprowadzić do tzw. kolizji – czyli wygenerowania dwóch plików dających ten sam skrót. Prace teoretyczne pozostawały jednak teoretyczne przez 12 lat, choć zdawano sobie sprawę z tego, że droga od teorii do praktyki jest coraz krótsza. Dzisiaj Google ogłosiło, że wspólnie z holenderskim instytutem naukowym przeprowadziło praktyczny atak, generując dwa pliki PDF o tym samym skrócie SHA-1.
Co to oznacza
Wszystko zależy od tego, o jakim zastosowaniu skrótu SHA-1 mówimy. Jednym z najważniejszych (i potencjalnie niosących największe zagrożenie) jest użycie skrótu SHA-1 w certyfikatach SSL witryn WWW. Odnalezienie kolizji oznacza, że dla certyfikatów opartych o SHA-1 ktoś znający sposób doprowadzenia do kolizji mógłby wygenerować fałszywy certyfikat, który przeglądarki uznałyby za prawdziwy. Zatem kolizja SHA-1 może dać atakującemu możliwość podsłuchania i modyfikacji zaszyfrowanego ruchu WWW. Dlaczego jednak nie powinniśmy z tego powodu panikować? Powodów jest kilka.
Po pierwsze odnalezienie kolizji nikogo nie zaskoczyło. Certyfikaty SHA-1 od paru lat są już wycofywane i uznawane za przestarzałe. Google w swojej przeglądarce Chrome od stycznia tego roku automatycznie uznaje je za niebezpieczne i ostrzega przed nimi użytkowników. Lada moment dołączy do niego Firefox.
Po drugie żadna instytucja wydająca certyfikaty SSL nie powinna już wydawać certyfikatów opartych na SHA-1. Co prawda był przypadek firmy, które spróbowała to zrobić, antydatując certyfikat, ale została szybko wykryta i jej kariera w branży się skończyła – przeglądarki przestały ufać jej certyfikatom.
Po trzecie przeprowadzenie kolizji nie jest trywialne – jak wskazuje Google, wymaga najpierw 6500 lat pracy procesora CPU, a następnie 110 lat pracy procesora GPU (oczywiście alternatywą jest np. zapędzenie do pracy 6500 CPU i 110 GPU na rok). Wobec powszechnej dostępności technik obliczeniowych można przyjąć, że jest to atak do przeprowadzenia dla średnio zasobnego atakującego, jednak ciągle jest poza zasięgiem np. większości studentów.
Wg Mikko koszt jednej kolizji oszacować można na okolice 2-3 milionów PLN. Co ciekawe w 2012 Bruce Schneier pisał, że w 2017 koszt takiego ataku wyniesie zaledwie kilkaset tysięcy dolarów.
It would cost around $500,000-$800,000 to replicate the computational effort Google did to break SHA-1 (at list prices). Hat tip: @frank_be. https://t.co/9siCHd1yi2 — Mikko Hypponen (@mikko) February 23, 2017
Gdzie jeszcze możemy mieć potencjalny problem z kolizją SHA-1? Funkcją tą mogą posługiwać się systemy backupowe do sprawdzania, czy dany plik uległ modyfikacji, platformy podpisów cyfrowych dokumentów (tu mamy spore ryzyko dla wiarygodności podpisu, skoro można zmodyfikować podpisany dokument i dalej zachowa on prawidłowość podpisu), aktualizacje oprogramowania podpisywane cyfrowo czy wszystkie inne sumy kontrolne, gdzie ufamy funkcji SHA-1.
Gdzie problem nie jest poważny? Raczej możemy nadal podawać funkcje skrótu złośliwych plików w wersji SHA-1 (tak jak i MD5), chyba, że obawiamy się, że ktoś będzie nam chciał spłatać figla i poświęcić trochę zasobów by wyprodukować inny plik o tej samej sumie. Na podstawie samej sumy nie podejmowalibyśmy się automatycznego kasowania pliku z systemu – lecz do wyszukiwania w Google nadal będzie ona przydatna.
Warto także zauważyć, że polisa ubezpieczeniowa samochodu z poniższego zdjęcia powinna znacznie podrożeć.
Co dalej?
Wydaje się, że przeglądarki problem już w znakomitej większości rozwiązały. Mamy nadzieję, że publikacja Google pomoże także wyeliminować SHA-1 z innych mechanizmów uwierzytelniania i weryfikacji treści. Na szczęście następców nie brakuje – mamy chociażby ciągle solidne SHA-256 czy względnie nowe SHA-3. Więcej o samym ataku możecie przeczytać w serwisie Shaterred.io.
Co ciekawe, publiczna nagroda za przeprowadzenie kolizji, ufundowana przez Petera Todda w wysokości ok. 2,5 BTC została dzisiaj odebrana.
'''Udało się wygenerować kolizję hashów SHA-1 z różnych plików.'''

Google ogłosiło kolizję funkcji skrótu SHA-1. Dla dwóch plików PDF o różnej zawartości udało się wygenerować taki sam hash.

Funkcje skrótu wykorzystywane są m.in. do tworzenia sum kontrolnych plików lub cyfrowych podpisów, a także certyfikatów SSL. Może to oznaczać różne problemy z bezpieczeństwem, jednak w większości stosuje się już nowsze niż SHA-1 algorytmy, np. SHA-256 lub SHA-3.

Nad złamaniem algorytmu Google współpracowało z Centrum Wiskunde & Informatica.