Výzkumníci z francouzského státního institutu pro výzkum informatiky a automatizace (INRIA) a Nanyangské technologické univerzity (Singapur) vylepšený na algoritmus SHA-1, který významně usnadňuje vytváření dvou různých dokumentů se stejnými hash hodnotami SHA-1. Podstata metody spočívá ve zjednodušení operace plného vyhledávání kolizí v SHA-1 na , při kterém k kolizi dochází za přítomnosti určitých prefixů, bez ohledu na ostatní data v souboru. Jinými slovy, lze vypočítat dva předdefinované prefixy a pokud jeden připojíme k jednomu dokumentu a druhý k druhému — výsledné hash hodnoty SHA-1 pro tyto soubory budou stejné.
Tento typ útoku stále vyžaduje obrovské výpočty a hledání prefixů zůstává složitější než běžné vyhledávání kolizí, ale praktická efektivita výsledku je výrazně vyšší. Pokud předtím byl nejrychlejší metodou hledání prefixů kolizí v SHA-1 provést 277,1 operací, nová metoda snižuje počet výpočtů na rozmezí 266,9 až 269,4. Při této úrovni výpočtů je odhadovaná cena útoku méně než sto tisíc dolarů, což je pro tajné služby a velké korporace přijatelné. Pro srovnání, pro hledání běžné kolize je nutné provést přibližně 264,7 operací.
V Google možností generovat různé PDF soubory se stejným hashem SHA-1 finta se sloučením dvou dokumentů do jednoho souboru, přepínáním viditelné vrstvy a posunem značky výběru vrstvy do oblasti vzniku kolize. Při podobných nákladech na zdroje (na hledání první kolize SHA-1 Google strávil rok výpočtů na clusterech s 110 GPU) nová metoda umožňuje dosáhnout shody SHA-1 pro dvě libovolné datové sady. Z praktického hlediska je možné připravit TLS certifikáty, ve kterých se uvádějí různé domény, ale shodují se hashe SHA-1. Taková možnost umožňuje nekalému certifikačnímu úřadu vytvořit certifikát pro digitální podpis, který lze použít k autorizaci falešných certifikátů na libovolné domény. Problém lze také využít k narušení protokolů, které se spoléhají na absenci kolizí, jako jsou TLS, SSH a IPsec.
Navržená strategie hledání prefixů pro kolize předpokládá rozdělení výpočtů na dvě etapy. V první etapě se provádí vyhledávání bloků, které jsou na pokraji kolize, pomocí vkládání náhodných proměnných řetězců do předem stanovené cílové množiny rozdílů. Ve druhé etapě na úrovni jednotlivých bloků se získané řetězce rozdílů porovnávají s kolizními dvojicemi stavů, s použitím metod tradičních útoků pro hledání kolizí.
I přes to, že teoretická možnost útoku na SHA-1 byla prokázána již v roce 2005 a první kolize byla ve skutečnosti v roce 2017, SHA-1 stále zůstává v oběhu a je zahrnuta v některých standardech a technologiích (TLS 1.2, Git atd.). Hlavním cílem provedené práce bylo poskytnout další silný argument pro okamžité přerušení používání SHA-1, zejména v certifikátech a digitálních podepsáních.
Dále lze poznamenat kryptoanalýzy blokových šifrovacích algoritmů , vyvinutých NSA a v roce 2018 schválených jako standard .
Výzkumníkům se podařilo vyvinout metodu obnovy soukromého klíče na základě dvou známých párů z otevřeného textu a šifrového textu. Při omezených výpočetních zdrojích na nalezení klíče je zapotřebí od několika hodin do několika dnů. Teoretický úspěšnost útoku je odhadována na 0.25, zatímco praktická úspěšnost pro existující prototyp je 0.025.
Zdroj: opennet.ru
