Czy plik można złośliwie zmienić w sposób, który zachowuje oryginalny skrót SHA-1?

Zgodnie z tym artykułem i wieloma innymi, SHA-1 nie jest bezpieczny.

W moim przypadku nie martwię się hasłami ani certyfikatami cyfrowymi. Niepokoi mnie integralność plików.

Czy możliwe jest złośliwe zmodyfikowanie pliku (np. Obrazu ISO lub pliku wykonywalnego) w sposób, który:

• Zachowuje skrót SHA-1 w oryginalnym pliku i
• Utrzymuje ogólną zawartość i działanie pliku (ale oczywiście obejmuje teraz złośliwą zawartość, która nie istniała pierwotnie)

Z mojego punktu widzenia zmiana pliku w sposób powodujący kolizję SHA-1 sprawiłaby, że plik byłby całkowicie bezużyteczny. ISO byłoby całkowicie uszkodzone, lub plik wykonywalny byłby tak całkowicie zakodowany, że nawet nie byłby plikiem wykonywalnym.

Ale moim zdaniem może to być źle. Do tej pory nie znalazłem niczego w wyszukiwaniach Google dotyczących dalszego przydatności SHA-1 do weryfikacji plików. Jakieś spostrzeżenia?

Nikt jeszcze tego nie zrobił dla SHA-1. Jest to teoretycznie możliwe, ale wciąż niepraktyczne. Raporty o niepewności w SHA-1 po prostu oznaczają, że poziom bezpieczeństwa nie jest tak wysoki, jak byśmy tego chcieli, a to oznacza, że ​​nie mamy tylu lat, zanim będziemy musieli się tym martwić, jak nam się wydawało.

Trudniej jest stworzyć plik z tym samym skrótem SHA-1 co dany plik, niż samemu stworzyć dwa pliki z tym samym skrótem SHA-1. I o ile wiemy, nikt na świecie nie wykonał jeszcze tego łatwiejszego zadania. To nie znaczy, że jutro nie może się to zdarzyć.

Jest to teoretycznie możliwe, ale jeszcze tego nie zrobiono.

To, czego szukasz, nazywa się „kolizją skrótu”: dwoma plikami z tym samym skrótem. Kryptograficzne kody skrótu, takie jak SHA-1, są ogólnie zaprojektowane, aby to utrudnić. Ponieważ SHA-1 jest 160-bitowym kodem, potrzeba około 2 ^ 159 brutalnych prób znalezienia duplikatu. Jeśli zostanie znaleziony algorytm, który niezawodnie radzi sobie lepiej niż w przypadku kryptograficznego skrótu, jest on uznawany za „uszkodzony”.

MD-5 jest przykładem bardzo zepsutego skrótu. Miał on mieć siłę 128 bitów, co wymagało średnio 2 ^ 127 prób. Ponieważ nadużywając znanych luk w zabezpieczeniach, rzeczywista liczba potrzebnych prób może wynosić nawet 2 ^ 47. To jest DUŻO mniejsze niż 2 ^ 127. W rzeczywistości zostało to zrobione w niecały dzień w nowoczesnym klastrze komputerowym.

Podaję ten przykład, ponieważ jest to najbliżej tego, jak chcesz użyć SHA-1. Nie jest to jednak najczęstsze podejście stosowane w kryptoanalizie, aby mieć pewność, że skróty nie zostaną złamane. Zwykle pozwalają one na kolizję między dwoma plikami wybranymi przez atakującego, zamiast wybierać jeden plik i atakującego, który chce go dopasować. Ten rodzaj ataku ma tę zaletę, że jest łatwiejszy do porównania. Jeśli uważam, że „trudno” złamać twój plik, czy to oznacza, że ​​inny plik jest podobnie silny? Ten atak, w którym atakujący może wybrać oba pliki, zapewnia, że ​​złapiemy najgorsze z najgorszych.

Ten rodzaj ataku pozwala na interesującą sztuczkę zwaną „ atakiem urodzinowym ”. Krótko mówiąc, użycie ataku urodzinowego zmniejsza siłę algorytmu o połowę, więc SHA-1 wymaga 2 ^ 80 prób (średnio), a MD5 wymaga 2 ^ 64 prób (średnio). Są to odpowiednio połowa z 160 i 128.

SHA-1 ma znane ataki, które zmniejszają jego siłę z 2 ^ 80 do 2 ^ 69. To nie będzie miało dla ciebie większego znaczenia. 2 ^ 69 prób to długi czas.

Jednak z historii odkryliśmy, że algorytmy mieszające nie są łamane spontanicznie, ale raczej z czasem. Nikt nie łamie algorytmu takiego jak MD-5, biorąc go z 2 ^ 64 na 2 ^ 47 w ciągu nocy. Dzieje się to z czasem, ponieważ wiele osób publikuje artykuły na temat matematyki, której używają przeciwko niemu. Zwykle można obserwować, jak złożoność ataków spada powoli od początku algorytmu (gdzie najlepszym atakiem jest zwykle atak urodzinowy).

Fakt, że obserwujemy pewne zmiany w zderzeniach, sugeruje, że SHA-1 widzi światło na końcu tunelu. Nadal jest silny, ale może być chęć przejścia na najnowszą SHA-3, która jest obecnie znacznie bezpieczniejsza.

Powinieneś naprawdę podejmować takie decyzje z perspektywy modelu zagrożenia. Ile szkód może wyrządzić atakujący, jeśli dostanie jedną z tych kolizji. Czy atakujący mają dzieciaki z dostępem do kilku laptopów, czy rządy z całymi klastrami superkomputerów do ich dyspozycji. Jak duże jest okno czasowe, w którym atakujący musi złamać skrót, zanim nie zostanie on użyty (wiele zastosowań kryptografii wymaga „zmiany warty”, takiej jak rotacja hasła). Wszystko to wpłynie na to, jak poważnie musisz brać pod uwagę kolizje.

Błędy w SHA-1 omówione w tym artykule są bardzo specyficzne: pozwalają atakującym stworzyć dwie rzeczy, które mają tę samą wartość (to się nazywa „atakiem kolizyjnym”). Jednak atak kolizyjny wymaga od atakującego kontroli obu zaangażowanych plików. Jeśli atakujący nie kontroluje oryginalnego pliku, atak kolizyjny nie pozwala mu znaleźć innego pliku o tej samej wartości skrótu.

Powodem, dla którego ma to znaczenie dla TLS / SSL (i ogólnie podpisów) jest to, że za ich pomocą atakujący często może kontrolować oba pliki. Certyfikat TLS jest w większości tworzony przez osobę, która o to poprosi (bity, których nie kontrolują, są często przewidywalne), więc kolizje pozwalają im stworzyć legalny i nielegalny certyfikat, uzyskać legalny podpis i przesłać podpis.

W przypadku plików ta sama sytuacja nie zawsze ma zastosowanie. Jeśli obawiasz się, że osoba tworząca plik jest atakującym (np. Dostanie jedną rzecz niezależnie zweryfikowaną jako dobrą, a następnie wyśle ​​ci ładunek zła z tym samym hashem), atak SHA-1 ma zastosowanie i powinieneś spojrzeć w kierunku wycofania go (choć nie jest to jeszcze krytyczne, jak wspomniał David Schwartz). Jeśli oryginalny plik jest zaufany, osoba atakująca nie może zastosować obecnie znanych ataków SHA-1, chociaż nadal możesz pomyśleć o wycofaniu go, jeśli możesz (jeśli masz wybór, użyj skrótu bez znanych ataków, takich jak SHA- 2).

W odpowiedzi na „kolizja nie będzie użyteczna” - chociaż atak nie wymaga od atakującego uzyskania użytecznej kolizji, generalnie nie jest wcale tak trudno zmienić „kolizję” w „użyteczną kolizję”. Wiele formatów plików ma dość miejsca, w którym możesz mieć wszystko, co chcesz, bez wpływu na funkcjonalność pliku; atakujący może zazwyczaj to zmodyfikować, aby uzyskać kolizję (jeśli kolizje są praktycznie możliwe do znalezienia), zachowując funkcjonalną część taką, jaką chcą. Różnica między „atakiem akademickim” a „atakiem praktycznym” może być duża; różnica między „każdą kolizją” a „użyteczną kolizją” jest na ogół znacznie mniejsza.

Poważniejszym problemem, niezwiązanym z wyborem algorytmu, jest sposób uzyskiwania skrótu. Wszystko, co robi skrót, to przesunięcie problemu z „pobierz prawdziwy plik” na „uzyskaj prawdziwą wartość skrótu;” wartość skrótu wysłana z tego samego serwera i tego samego typu połączenia co plik jest całkowicie bezwartościowa przeciwko złośliwej modyfikacji (każdy atakujący, który może manipulować plikiem, może manipulować hashem). Skróty są do tego przydatne tylko wtedy, gdy możesz ufać hashowi bardziej niż plikowi; chociaż czasami tak jest (torrenty, mirrory), często są używane, gdy tak nie jest. Dlatego powinieneś być bardzo ostrożny za każdym razem, gdy używasz skrótów do weryfikacji integralności.

Trzeba odróżnić atak kolizji i ataku preimage . Znalezienie dwóch dowolnych komunikatów o tej samej wartości jest atakiem kolizyjnym.
Zastąpienie jednego konkretnego podanego komunikatu (tutaj: plikiem wykonywalnym) innym komunikatem o tym samym haszu jest (drugim) atakiem na obraz.

SHA-1 jest zepsuty, o ile atak kolizji można wykonać w 2 ⁵² operacjach, zgodnie z artykułem z Wikipedii, który nie podaje cytatu dla tej liczby (najlepszy atak, który, jak wiem, jest naprawdę wiarygodny, to atak Marca Stevensa , co wymaga 2 ⁶⁰ operacji). Ale niech zakładają ten pesymistyczny przypadek 2 ⁵² .

Jest to niepokojące, ponieważ atak na taką skalę jest nie tylko teoretycznie możliwy, ale wręcz doskonale wykonalny w ciągu jednego dnia na platformie z wieloma GPU. Jest to oczywiście problem w przypadku aplikacji, w których będą działać „dowolne dwa” komunikaty. Nawet liczba 2 ⁶⁰ podana przez Stevensa (256 razy więcej pracy) jest całkowicie wykonalna, jeśli atakujący jest skłonny rzucić dodatkowe pieniądze na problem lub jest skłonny spędzić rok.
Jest to dokładnie taka rzecz, która nie uniemożliwi fałszowaniu certyfikatów osobom zaangażowanym w szpiegostwo lub cyberprzestępczość.

Teraz atak preimage ma wykładnik, który jest dwa razy większy, więc zakładając 2 ⁵² dla ataku zderzeniowego, byłoby to 2 ¹⁰⁴ operacji, co jest zupełnie innym boiskiem.

Jest to nie tylko niepraktyczne (maszyna, która jest miliard razy szybsza niż maszyna wspomniana w poprzednim akapicie, nadal zajmuje około 6 milionów lat), ale biorąc pod uwagę nasze mizerne sposoby generowania energii, jest to całkowicie niemożliwe.

Wykonanie tak ogromnych obliczeń wymagałoby źródła energii, które jest znacznie większe niż wszystko, na co możemy sobie pozwolić, aby poświęcić na jedną operację. Nie, niezupełnie źródło energii wielkości Słońca, ale wciąż dość duże .

Możesz realistycznie oczekiwać, że uzyskasz od 10 do 50 GFLOPS z jednego Wata. Zakładając, że dzieje się coś cudownego, a procesory stają się w ciągu nocy około kilka tysięcy razy bardziej energooszczędne, można założyć 1 SHA ≈ 1 FLOP (dość optymistyczne!). Oznaczałoby to, że aby wykonać 2 ¹⁰⁴ obliczenia wartości skrótu w ciągu 10 lat, potrzebujesz elektrowni o mocy 10 ¹² W. Aby przeprowadzić atak w ciągu 1 roku, potrzebujesz elektrowni o mocy 10 ¹³ W. To około 50 razy więcej niż wszystkie elektrownie jądrowe w USA, Francji i Japonii mogą wyprodukować razem, tylko do wykuwania jednego haszu.

Tak się nie stanie , istnieją znacznie łatwiejsze sposoby osiągnięcia tego samego celu (wykorzystanie serwera przechowującego oryginalny skrót i jego zastąpienie, szantażowanie kogoś itp.).

Ogólny punkt artykułu zwaną w tej kwestii jest: SHA1 jest przestarzała i powinna być stopniowo wycofywane, gdy jest jeszcze czas, aby zrobić to sprawnie. W niektórych obszarach czas ucieka, ponieważ Google i Microsoft egzekwują terminy.

Ogólna zasada dotycząca przestarzałej technologii:

• Jeśli tworzysz nowy projekt lub dodajesz funkcje, nie używaj go (SHA1).
• Jeśli utrzymujesz coś starego, zaplanuj, kiedy chcesz go wymienić (SHA1).

Cytat podsumowujący z posta na blogu z 2012 r. Bruce'a Schneiera: „Chodzi o to, że my w społeczności musimy rozpocząć migrację od SHA-1 i teraz do SHA-2 / SHA-3”.

W części pytania dotyczącej skrótu mieszającego SHA-1 rozwiązano kilka odpowiedzi.

Jednak duża część tego zależy od typu pliku, z którym pracujemy:

Utrzymuje ogólną zawartość i działanie pliku (ale oczywiście obejmuje teraz złośliwą zawartość, która nie była pierwotnie zmieniona)

Co to oznacza, różni się znacznie w zależności od tego, co wykrywa zmiany:

• Jeśli jest to podpisany plik wykonywalny, a nie (rozsądna) szansa: musiałbyś jakoś uzyskać dwie kolizje skrótu: SHA-1 pliku i wewnętrzny podpis .exe.
• Jeśli jest to plik wykonywalny niepodpisany, .com, dll niepodpisany lub podobny, ich widelce zasobów można dodać w sposób, który nie zmieni ich działania, a zatem można (ostatecznie) uzyskać kolizję skrótu, która nie jest wykrywalna przez „normalne” operacja.
• Jeśli jest to plik kodu źródłowego lub podobna struktura (.cs, .c, .h, .cpp, .rb, .yml, .config, .xml, .pl, .bat, .ini), dodatki, modyfikacje lub usunięcia można ograniczyć do poprawnej składni komentarza, tak aby zmiana nie była zauważalna przez większość zastosowań (kompilacja lub uruchomienie, nie otwieranie go za pomocą edytora tekstu).
• Jeśli jest to format .iso, .zip lub inny format kontenera, jest to również mało prawdopodobne, ponieważ większość losowych zmian spowoduje uszkodzenie kontenera. Można to zrobić: dodać fałszywy wpis pliku lub zmienić zawartość w kontenerze i sprawdzić go ponownie, ale dodajesz warstwę złożoności i dodajesz dodatkowy czas na sprawdzenie wyniku, a także masz ograniczony stopień swobody względem jak i jaka treść może zostać zmieniona.
• Jeśli jest to tekst lub format tekstowy, można je zmienić prawie w dowolny sposób, pozostając jednocześnie „poprawnym” plikiem, chociaż zawartość prawdopodobnie będzie zauważalna.
• W wielu formatach, takich jak .rtf, .doc, .html, .xslx i innych formatach znaczników, można je dodawać lub modyfikować w sposób, który będzie niewykrywalny przez analizatory składni, a więc inny niż długość (lub nawet o ograniczonej długości , mniej swobody) pliki mogą zostać zmienione, aby (ostatecznie) uzyskać kolizję skrótu, jednocześnie będąc nie tylko prawidłowym plikiem, ale nie zauważalnie zmienionym w jakikolwiek sposób, który byłby widoczny dla typowych aplikacji, z którymi byłyby używane.

Pozostaje ci tylko to, jak uzyskać kolizje w dowolnej strukturze, która nie jest uszkodzona, i być może w pewnym stopniu niewykrywalna:

1. Wprowadź wszelkie pożądane zmiany funkcjonalne (np. Wstawienie złośliwej zawartości) i wprowadź dodatkowe zmiany, aby zachować ważność określonego formatu pliku
2. Dodaj sekcję, która będzie niefunkcjonalna (między blokami komentarzy, na samym końcu pliku tekstowego ze zwrotem karetki 3k, izoluj bieżący blok komentarza)
3. Dodaj lub wybierz znak / punkt kodowy / bajt do modyfikacji i wypróbuj każdą możliwą prawidłową kombinację (na przykład nie każda kombinacja bajtów jest ważna dla różnych kodowań).
4. Przelicz skrót, sprawdź, czy kolizja pasuje.
5. jeśli nie, przejdź 3.

Załóżmy, że masz super szybki komputer i mały plik, taki że modyfikacja prawidłową sekwencją bajtów i ponowne obliczenie wartości skrótu zajmuje 1 milisekundę (prawdopodobnie wymaga specjalnego sprzętu). Jeśli rozkład skrótu jest całkowicie losowy i rozłożony w całym zakresie, przy każdej 2^160próbie otrzymasz kolizję z SHA-1 (brutalne wymuszenie).

2^160/1000/60/60/24/365.24 
= 4.63x10^37 years 
= 46,300,000,000,000,000,000,000,000,000,000,000,000 years 
= 46 undecillion years.

Ale hej, spróbujmy 2^60i 2^52wersje, i udawać, że pozwala nam zmodyfikować plik w dowolny sposób możemy jak (nie) i że oni też mogą być wykonane w 1ms każdą okazję:

2^52 yields 142,714 years 
/*humans might still be around to care, but not about these antiquated formats*/
2^60 yields 3.65x10^7 years = 36,500,000 years 
/*machines will probably have taken over anyway*/

Ale hej, możesz mieć szczęście. Naprawdę, naprawdę więcej szczęścia niż cuda, które ludzie nazywają cudami.

Nie do końca, możesz spełnić jeden z tych warunków naraz, ale nie oba. Możliwe jest uzyskanie tego samego skrótu dla dwóch różnych plików, ale ktoś może zmienić plik, a następnie spróbować uzyskać ten sam skrót, jest prawie niemożliwe, ponieważ z tego co wiem

Tak to mozliwe. Pomyśl, jak wirusy działają na plikach EXE. Ładunek złośliwego oprogramowania jest dołączany do oryginalnego pliku EXE, dzięki czemu program nadal robi to, co pierwotnie zrobił, ale rozprzestrzenia się również jako wirus. Teraz, aby zachować ten sam skrót, potrzebujesz dodatkowej specjalnie spreparowanej wyściółki .

Oznacza to, że plik byłby większy. Ale w przypadku EXE może uda ci się usunąć trochę rzadziej używanego kodu, aby program działał tylko na początku. W przypadku JPEG można dodatkowo skompresować obraz lub użyć innego obrazu całkowicie. W przypadku ISO można usunąć zestawy plików. Obliczenia wymagane do odtworzenia skrótu byłyby trudniejsze i być może matematycznie niemożliwe w określonych przypadkach, ale ogólnie byłyby możliwe.