Badacze z francuskiego państwowego instytutu badań w informatyce i automatyce (INRIA) oraz Uniwersytetu Nanyang w Singapurze usprawniony na algorytmie SHA-1, znacznie ułatwiającym tworzenie dwóch różnych dokumentów z identycznymi haszami SHA-1. Istota metody sprowadza się do zoptymalizowania operacji pełnego dopasowania kolizji w SHA-1 do , w którym kolizja występuje przy obecności określonych prefiksów, niezależnie od pozostałych danych w zestawie. Innymi słowy, można obliczyć dwa z góry określone prefiksy i jeśli jeden dołączy się do jednego dokumentu, a drugi do drugiego — wynikiem będą identyczne hasze SHA-1 dla tych plików.
Ten rodzaj ataku wciąż wymaga ogromnej mocy obliczeniowej, a dobór prefiksów pozostaje trudniejszy niż w przypadku standardowych kolizji, ale praktyczna efektywność wyniku jest znacznie wyższa. Jeśli do tej pory najszybsza metoda wyszukiwania prefiksów kolizji w SHA-1 wymagała wykonania 277,1 operacji, to nowa metoda redukuje liczbę obliczeń do zakresu od 266,9 do 269,4. Przy takim poziomie obliczeń szacunkowy koszt ataku wynosi mniej niż sto tysięcy dolarów, co jest w zasięgu służb specjalnych oraz dużych korporacji. Dla porównania, wyszukiwanie standardowej kolizji wymaga około 264,7 operacji.
W Google możliwości generowania różnych plików PDF z identycznym haszem SHA-1 sztuczka polegająca na połączeniu w jeden plik dwóch dokumentów, przełączając widoczny warstwę i przesuwając znacznik wyboru warstwy w obszarze wystąpienia kolizji. Przy zbliżonych kosztach zasobów (na wyszukiwanie pierwszej kolizji SHA-1 Google poświęcił rok obliczeń na klastrze z 110 GPU) nowa metoda pozwala osiągnąć zgodność SHA-1 dla dwóch dowolnych zestawów danych. Praktycznie można przygotować certyfikaty TLS, w których wymienione są różne domeny, ale hasze SHA-1 są identyczne. Taka możliwość pozwala nieuczciwemu centrum certyfikacji stworzyć certyfikat do podpisu cyfrowego, który można wykorzystać do autoryzacji fikcyjnych certyfikatów dla dowolnych domen. Problem ten może być również wykorzystany do kompromitacji protokołów, które opierają się na braku kolizji, takich jak TLS, SSH i IPsec.
Proponowana strategia poszukiwania prefiksów dla kolizji zakłada podział obliczeń na dwa etapy. W pierwszym etapie wykonywane jest poszukiwanie bloków znajdujących się na granicy kolizji poprzez wstawianie losowych zmiennych łańcuchów do z góry określonego celu różnic. W drugim etapie, na poziomie poszczególnych bloków, uzyskane łańcuchy różnic są porównywane z prowadzącymi do kolizji parami stanów, przy użyciu metod tradycyjnych ataków na kolizje.
Mimo że teoretyczna możliwość ataku na SHA-1 została udowodniona już w 2005 roku, a w praktyce pierwsza kolizja została w 2017 roku, SHA-1 nadal pozostaje w użyciu i jest objęty niektórymi standardami i technologiami (TLS 1.2, Git itd.). Głównym celem wykonanej pracy było dostarczenie jeszcze jednego mocnego argumentu za natychmiastowym zaprzestaniem stosowania SHA-1, szczególnie w certyfikatach i podpisach cyfrowych.
Dodatkowo można zaznaczyć kryptoanalizy blokowych szyfrów , opracowanych przez NSA USA i w 2018 roku zatwierdzonych jako standard .
Badaczom udało się opracować metodę odzyskiwania klucza prywatnego na podstawie dwóch znanych par z otwartego tekstu i szyfrogramu. Przy ograniczonych zasobach obliczeniowych, czas potrzebny na złamanie klucza wynosi od kilku godzin do kilku dni. Teoretyczny współczynnik skuteczności ataku oceniany jest na 0.25, a praktyczny dla istniejącego prototypu — 0.025.
Źródło: opennet.ru
