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
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.
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.
Komentarze
„mamy chociażby ciągle solidne SHA-256 czy względnie nowe SHA-3”
a co z SHA-512?
SHA-256 i SHA-512 to dwie wersje tego samego algorytmu, o różnej długości wartości wyjściowej.
Nie.
Tak :) https://en.wikipedia.org/wiki/SHA-2
„W założeniu wartość ta powinna być unikatowa dla danego ciągu” – to stwierdzenie co najmniej nieprecyzyjne, a co do zasady błędne. Skoro funkcja skrótu przetwarza ciąg wejściowy o dowolnej długości w ciąg wyjściowy o stałej, zawsze takiej samej długości, to z samego tego faktu wynika, że ten zamknięty zbiór wartości wyjściowych nie może w sposób unikatowy reprezentować dowolnej ilości ciągów wejściowych dowolnej długości.
A mógłbyś rozwinąć swoją dysertację, gdyż nie do końca zrozumiałem…
W teorii Maciej ma rację – mająć nieskończenie dużo ciągów wejściowych i skończenie dużo ciągów wyjściowych (ograniczenie długości i zakresu używanych znaków) kiedyś coś wywoła kolizję. Tak samo jak małpa stukająca w klawisze kiedyś napisze Pana Tadeusza wspak. W wykładzie na wydziale matematyki pewnie bym poprawił, ale na potrzeby Czytelników z3s myślę że istniejący opis wystarczy, a kto chce, ten sobie doczyta w komentarzach.
Dlaczego tylko w teorii? Przecież każda funkcja skrótu z natury ma tą wadę, dla ciągów węjsciowych >= jej wynikowi. W kolejnych generacjach zwiększana jest jedynie trudność celowego uzyskania takiej kolizji poprzez wydłużenie ciągu wyjściowego i/lub skomplikowanie procesu obliczania (zwiększenie potrzebnej mocy do uzyskania pojedynczego skrótu).
W teorii, bo w praktyce ataki które przy wykorzystaniu całej mocy obliczeniowej świata zajmują więcej niż czas do śmierci termicznej wszechświata można uznać za mało praktyczne.
Owszem – ataki tak, ale już przypadkowe kolizje mogą się jak najbardziej zdarzyć i nie mamy na to wpływu
Biorąc pod uwagę, że wartości generujących kolizję jest nieskończoność, to należałoby jednak zachować powściągliwość przy stawianiu tez o unikalności. Tak jak napisali przedmówcy – kwestią innego rodzaju jest możliwość znalezienia kolizji. A już wygenerowanie jej tak jak tutaj – to dodatkowa trudność (w sensie spreparowanie drugiego dokumentu tak, żeby pasowały skróty).
Hasła w bazie dla Exima mam w SHA1. Jak RZyć?
.. a nie to nie ten portal.
wpisujcie miasta gdzie ktoś używa sha-1
warszawa[*]
hej hej, certyfikaty można relatywnie łatwo zmigrować, ale dlaczego nikt nie zwrócił uwagi jakie to ma konsekwencje jeżeli chodzi o git-a! Jest tyle publicznie dostępnych open sourcowych projektów wykorzystywanych popularnie nawet w systemach o wysokiej potrzebie bezpieczeństwa, że umiejętny atak przeprowadzony na repozytorium spowoduje trudne do przewidzenia konsekwencje w bliżej nieokreślonej przyszłości. Załóżmy że jakimś cudem plik o takim samym sha1 nie zostanie zuploadowany do zdalnego repozytorium, tylko zostanie wzięta stara wersja o takim samym sha1. Co jeżeli mimo wszelkiej ostrożności testy przejdą poprawnie?!
Ktoś już to sprawdził.
https://stackoverflow.com/questions/9392365/how-would-git-handle-a-sha-1-collision-on-a-blob
Nie przejmowałbym się tym jednak za bardzo. Stworzyć bloba, który będzie miał taki sam hash to jedno, ale stworzyć takiego, którego zawartość będzie miała sens (np. będzie backdoorem), to już zupełnie inna para kaloszy.
To można odwrotnie, przygotować paczkę backdoorów, zobaczyć jaki jest dla nich (związanych z nimi blobami) hash i szukać odpowiednika w publicznie dostępnych repo :) odpowiedni blob wcale nie musi być „świeży”
wtedy to już chyba pozostanie się tylko modlić
Ekspertem nie jestem, ale wydaje mi się, że podrobiony plik powinien mieć fragment o wysokiej entropii i to prawdopodobnie na końcu pliku. Więc może to być metoda na wyszukiwanie fałszywek w plikach mających zwykle dość małą entropię. Złe kody źródłowe tak wykryjesz, paczki już niekoniecznie, choć fałszywki powinny mieć trochę zbędnych dla archiwizera danych.
Git od dawna pozwala na podpisywanie tagów, a trochę krócej (ale to już też liczone w latach) na podpisywanie commitów za pomocą PGP/GPG. Samo PG/GPG też od dawna wspiera algorytmy silniejsze niż SHA-1.
Używasz git-a w środowisku „o wysokiej potrzebie bezpieczeństwa”? – zadbaj o odpowiednio bezpieczne klucze, oraz odpowiedni proces podpisywania i SPRAWDZANIA repozytorium przed wykorzystaniem :)
Ciekawie opisane jest to w tej historii: https://mikegerwitz.com/papers/git-horror-story
jemu nie chodziło o podpisywanie czy jakieś certyfikowanie zawartości ale o to że git pod spodem nadaje plikom nazwy które są funkcją skrótu i zakłada się że różne pliki dadzą różne nazwy – jeżeli będziesz chciał zapisać plik którego skrót już istnieje to albo się po prostu nie zapisze albo… hmm… czy w takim razie git jest w stanie wykryć kolizję?
Podpis commita nic nie zmienia w tej sytuacji, gdyż sygnatura jest umieszczana w nagłówku commita, a potem wyliczany jest hash. Teoretycznie więc sygnatura przed niczym nie zabezpiecza, bo teoretycznie możesz wygenerować taką, która spowoduje kolizję.
Oznacza to nic. Bo może i umiemy wygenerować kolizję, ale by przeprowadzić taką formę „ataku” na Gita potrzeba tzw. preimage attack, a tego nikt nie uzyskał nawet dla MD5.
„Czyli wygenerowania dwóch plików dających ten sam skrót.” – chyba miało być dwóch różnych plików
Najciekawsze w tym wszystkim jest jedno pytanie, którego jeszcze nikt publicznie nie zadał: kto w Google poza autorami, i od kiedy, wiedział o trwających pracach oraz ich przypuszczalnych wynikach?
Na blogu Google Security można powiem zauważyć wzmiankę, że usługi Google są już zabezpieczone. W dzień ogłoszenia newsa!
A zatem zachodzi podejrzenie, że Google znało wyniki tych badań (prowadzonych we współpracy z publiczną instytucją, za publiczną kasę!) dużo wcześniej i zastosowało je komercyjnie podczas, gdy podmioty konkurencyjne takiej możliwości nie miały.
Wg mnie sprawa kwalifikuje się do prokuratury. Co najmniej do zbadania, czy nie doszło do przestępstwa (bo prawa holenderskiego nie znam, więc nie chcę mówić, że na pewno doszło, niemniej jednak sprawa jest wysoce podejrzana).
Google napisał, że jest zabezpieczony całkiem, czy że zrezygnował z certyfikatów opartych o SHA-1? Zresztą skoro od 12 lat wiedziano, że ten dzień kiedyś nadejdzie to każdy mógł się zabezpieczyć wcześniej.
Czytaj ze zrozumieniem, o możliwości takiej kolizji wiedziano już dawno, po prostu pokazano jednoznaczny dowód na to, każda osoba/instytucja/cokolwiek dbająca o bezpieczeństwo zapewne wcześniej również się przed tym zabezpieczyła…
Może Ty też czytaj ze zrozumieniem i zwróć uwagę na to, jak Google się zabezpieczył. Nie rezygnacją z SHA-1, o nie…
bardzo proszę o wyjaśnienie
Nie, to jest zupełnie nieciekawe. W artykule napisane jest wyraźnie, że uczelnia przeprowadziła badania wraz z Google. To znaczy, że Google partycypowało w tych badaniach. Dostarczyło pieniądze, infrastrukturę lub inne zasoby.
To zupełnie normalne, że jeśli jednostka naukowa prowadzi badania we współpracy z prywatnym podmiotem, to ten konkretny podmiot będzie miał ich wyniki szybciej.
Taka jest cena za to, że prywatny sektor współfinansuje publiczne badania.
Powołajmy komisję śledczą!
A tak na poważnie:
może i wykorzystywali wyniki, kilka dni wcześniej przed publikacją, ale dzięki publikacji udowodnili, że atak jest możliwy (nie tylko teoretycznie).
Może dzięki temu, kilka instytucji zaniecha korzystania z SHA-1.
A być może, ktoś w Google ruszył głową i wiedząc, że jego koledzy pracują nad atakiem, zakasał rękawy i zabezpieczył wszystko co się da, aby nie było wstydu w dniu publikacji wyników?
wiekszosc dystrybucji linuksowych weryfikuje swoje binarki przez sha512 ale Microsoft do dzisiaj topornie wspiera juz dawno przestarzaly i wadliwy sha1 w swoich oficjalnych aktualizacjach i plikach msdn
„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”
czy chodzi tu o StartCom i WoTrust?
czytałem akurat dziś o tym w ramach poszukiwania darmowego wystawcy podpisu poczty ;)
Tak.
OK, mogliście w sumie napisać nazwy, komu to szkodzi ;)
natomiast, Outlook nadal uważa certyfikaty s/mime za zaufane – nie wiem czy firma wróciła do gry, czy naprawili błędne certyfikaty, w każdym razie, wydają darmowe i płatne nadal
pytanie pozakonkursowe i niezwiązane z głównym tematem – jakiego wystawcę cert. ssl polecicie? tani, za rozsądne pieniądze lub za free…
Let’s Encrypt?
Co do tego co dalej, to może kiedyś pojawić się takie ogłoszenie na czarnym rynku:
„Wygeneruję dopełnienie pliku tak, żeby kolidował w SHA1 z biblioteką systemową. Cena XXX BTC…”
Autorzy wirusów pod MS Windows z pakietami pseudo-bezpieczeństwa analizującymi pliki po skrótach byliby bardzo zadowoleni. A wiadomo jak „zabezpieczone” są komputery np. w biurach, może gdzieś właśnie fałszywe poczucie bezpieczeństwa daje taki kupa-antywirus?
IMHO te 2-3mln PLN to mocno przeszacowane. Cena zapewne za wynajęcie klastra na rok. Ale po co robić samemu coś, co mogą zrobić inni :-) Wystarczy grupa zapaleńców i po pół roku mamy prawie za darmo (distributed.net ma ponad 300k członków, czyli ~300k CPU)
Albo dobry odpowiednio liczny botnet
” jak wskazuje Google, wymaga najpierw 6500 lat pracy procesora CPU, a następnie 110 lat pracy procesora GPU”
nie „następnie”, tylko „albo”. 6500 lat pracy CPU = 110 lat pracy GPU, ktoś nie zrozumiał artykułu
„6,500 years of CPU computation to complete the attack first phase
110 years of GPU computation to complete the second phase”
Nie wiem jaki artykuł cytujesz, chyba Sekuraka. Ja widzę „This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations”.
Cytuje oryginalną publikację Google zlinkowaną w artykule. https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
@Alf
Czekaj czekaj – czy wlasnie cytujesz cos, co obala twoja teorie? „6,500 years of single-CPU computations _and_ 110 years of single-GPU computations” – ja tam widze „and”, a nie „or”. ;)
Tak tak, tłumacz wszystko słowo w słowo, a zaliczysz epicki fajl.
Ale przecież nawet na zdrowy rozum „liczenie najpierw na CPU, a dopiero potem (czego?) na GPU” nie ma sensu. CPU liczą z grubsza, a GPU z dokładnością?
Polecam http://shattered.io/static/shattered.pdf, dla ułatwienia – strony 14 i 15. A jeśli naprawdę nie chce Ci się czytać (a najwyraźniej tak jest) to atak miał dwie fazy i każdy była przeprowadzona na innych procesorach (CPU vs GPU).
wszystko jest xorem :(
Ja bym te 2 miliony zainwestował w dedykowany układ ASIC to pewnie by sie szybko zwróciło , podobnie było z ewolucją koparek kryptowalut:
CPU – > GPU -> ASIC
A takie trywialne pytanie, czy nie wystarczy badać pliku za pomocą dwóch niezależnych funkcji skrótu? Np SHA-256 i CRC-64 ? Wygenerowanie pliku, który wywoła kolizję w jednym algorytmie jest chyba niemożliwe żeby kolidowało w zupełnie innym.
Niestety jest możliwe. Taki scenariusz wymaga po prostu znacznie większej ilości obliczeń; tak ogólnikowo, ilości jak powyżej w artykule ale podniesionej do kwadratu.
Z teoretycznego punktu widzenia, istnienie pliku, który będzie wywoływał kolizję w dwu różnych algorytmach jest praktycznie pewne.
Jeżeli przestrzeń wynikowa funkcji A jest zbiorem liczności a, przestrzeń wynikowa funkcji B jest zbiorem liczności b, a przestrzeń argumentów jest nieskończenie duża, oczywistym jest, że jeśli weźmiemy podzbiór przestrzeni argumentów o liczności większej niż a*b będziemy mieć co co najmniej b+1 argumentów dających taki sam skrót w funkcji A.
Z tego w sposób oczywisty wynika, że z tych co najmniej b+1 argumentów co najmniej dwa dadzą ten sam skrót w funkcji B.
Oczywiście praktyczna strona generacji takiej kolizji to zupełnie inna sprawa. Zwłaszcza gdybyśmy chcieli nie tylko wygenerować jakąkolwiek „podwójną kolizję” (znaleźć dwa elementy o tych samych skrótach), ale znaleźć element podwójnie kolidujący do elementu danego. Oczywiście sytuacja komplikuje się jeszcze bardziej, jeśli chcemy, żeby do kompletu znaleziony element miał sens „biznesowy”.
Rozumowanie można w prosty sposób rozszerzać na dowolną skończoną liczbę różnych funkcji skrótu.
Czy ktoś z Was zauważył, że oba te pliki pdf mają dokładnie ten sam rozmiar w bajtach? Podobnie jak pliki exe w pewnym przykładzie kolizji md5. O co tutaj chodzi? Dodatkowo w tym jednym pdf tylko kolor tła został zmieniony a nie treść. Może ktoś to wyjaśnić?
500000$(czyli kilkaset tysięcy) to więcej niż 2 miliony złotych, więc nie rozumiem fragmentu „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.”
Jak widać każde zaeinezceipzeb
można złamać, więc trzeba zmieniać zabezpieczenia zanim ktoś je złamie.
2.5 BTC za koszt produkcji 2 plików, który wynosi 2-3 mln dolarów… Co to za nagroda?
W plikach jest różne ok. 80 znaków, czyli 0,0002 zawartości pliku. Jakim cudem to tak zrobili?
Nie do końca rozumiem pytanie – w plikach jest 0.0002 zawartości pliku?
Ale ogólnie to można robić hash length extension, i jeśli dopiszesz takie same dane do dwóch plików z tym samym hashem to hash dalej ma taką samą wartość.
Do tego dochodzi fakt, że najprawdopodobniej kolidujący sumą SHA-1 ciąg/plik będzie najprawdobodobniej zupełnie nieczytelny i niepodobny do oryginału.
Dla przykładu:
Mamy zdanie: „Ala ma kota.”
Generujemy SHA-1: „43fd70009a97a7d311c5644047ccc700f8d08a9d”.
Następnie generujemy sobie ciąg o tym samym SHA-1.
Jest mocno nieprawdopodobne, że ów ciąg będzie w formie „Bartek ma psa”, czy też w ogóle będzie się składał z jakichkolwiek sensownych słów. Byłoby to coś bardziej na kształt „NJFA*($#FANWF(AfA430j”.
Tak więc owe przykładowe pliki pdf, poza nazwą i SHA-1 (suma nie bierze pod uwagę nazwy pliku, jedynie treść) byłyby skrajnie do siebie niepodobne.
Pomijam już rozważanie możliwości podmianki pliku pdf na podobny, ale ze złośliwymi makrami.
Proszę rzucić okiem na ten link:
https://extensions.openoffice.org/en/project/cryptographic-hash-functions-uno-component-openofficeorg
Gość nie otrzymał odpowiedzi dlaczego funkcja skrótu SHA-1 daje PRAWIE poprawny wynik dla argumentu: noe.dekkerf29ru6ap
it gives me:
accf66bbda7debaf7813a8dd9827c1ca29adb3e
a tymczasem wynik powinien wyglądać tak:
0accf66bbda7debaf7813a8dd9827c1ca29adb3e
Niby DROBNA!!! różnica bo brakuje pierwszego znaku – zera na początku.
Problem stanie się istotny, gdy zechcemy wykonać dużą ilość kolejnych przekształceń. Czy podobne niespodzianki mogą wystąpić np w SHA-256? Ten błąd występuje po implementacji dodatku o OpenOffice, LibreCalc dodatku Cryptographic.oxt
Drobna uwaga, jak ktoś będzie próbować zainstalować ten dodatek i nie będzie chciało działać, to proszę pamiętać, że prawidłowa składnia funkcji to =TEXTHASH(„test”;”SHA-1″) – w środku jest średnik!