Google ukázal, že podepsanou smlouvu lze zfalšovat. Vytvořil první reálnou kolizi SHA-1

Hashovací funkce slouží k vytvoření otisku zdrojového souboru. Stojí na čtyřech pilířích:

• Nehledě na velikost vstupních dat se vždy vytvoří otisk o stejné délce.
• Úpravou původních dat se otisk změní neodhadnutelným způsobem.
• Z otisku nelze vytvořit původní data.
• Otisk dvou různých souborů by se měl vždy lišit. Nalezení dvou souborů se stejným otiskem je velmi nepravděpodobné, ale ne nemožné. Pokud by jeden otisk odpovídal dvěma různým souborům, označujeme tento stav jako kolizi.

V minulosti byly objeveny první kolize u hashovací funkce MD5, zásadně tomu pomohl i český kryptolog Vlastimil Klíma. Po MD5 se přecházelo na účinnější SHA-1, který vytváří pevný otisk o délce 160 bitů. Nicméně již v roce 2005 byl objeven první teoretický útok, který by dovolil kolizi vytvořit. Tím se funkce stala potenciálně nebezpečnou. Americký Národní institut standardů a technologie už proto od roku 2011 SHA-1 nedoporučuje a nabádá k přechodu na SHA-256.

Google našel kolizi SHA-1

Google mu dává za pravdu. Jeho tým Research Security se spojil s kryptology z nizozemské Centrum Wiskunde & Informatica a vytvořil první reálně zneužitou kolizi. Útok označili jako SHAttered (mj. v překladu jako rozbité) a věnovali mu stránku shattered.io.

V domácích podmínkách byste pro vytvoření kolize potřebovali desítky let.

Prolomení SHA-1 brute-force metodou by jednomu GPU trvalo 12 milionů let. SHAttered je 100 000× rychlejší. K nalezení kolize mu stačilo „jen“ devět triliónů SHA-1 výpočtů (přesně 9 223 372 036 854 775 808). Na jednom procesoru by výpočty zabraly 6500 let, na jednom GPU 110 let. Výzkumníci ale pochopitelně použili farmu s minimálně stovkami čipů (Google číslo ani dobu výpočtu neupřesnil).

V domácích podmínkách je nalezení kolize stále nerealizovatelné, ale dnes si lze pronajmout výpočetní kapacitu v cloudu. Útok by ale i tak stál stovky tisíc dolarů. Důležité však je, že první reálná kolize existuje a teď už se může jen optimalizovat.

Kde se SHA-1 používá?

Všude. Patrně jde stále o nejrozšířenější hashovací funkci. Slouží k digitálním podpisům dokumentů, e-mailů, stojí na něm kontrola verzí Gitu, využívá se pro vyhledávání duplicitních souborů na disku nebo při rozdílových zálohách, jsou jím ověřovány softwarové aktualizace, donedávna se ještě ve velkém používal pro ověření TLS/SSL certifikátů. Chrome od verze 56 již označí weby s HTTPS a SHA-1 za nezabezpečené. Stejný krok letos učiní i Firefox a Edge.

SHA-1 se dnes používá skoro všude

Díky relativní dostupnosti kolizí SHA-1 je možné vytvořit dva soubory se stejným otiskem. Útočníci by mohli zfalšovat certifikáty označující pravost souborů nebo softwarových aktualizací. Vytvořit lze dvě verze smlouvy. Jednu podepíšete, na druhou (méně výhodnou) bude váš podpis možné přenést.

Na web shattered.io Google vystavil dva dokumenty v PDF, které se částečně liší, ale jejich SHA-1 otisk je stejný. Na stránkách je také formulář, do něhož můžete vložit soubor a nechat jej ověřit, jestli na něm byl kolizní útok proveden. Google zatím nástroj a kód SHAtteredu nezveřejnil, učiní tak až za 90 dní.

Dva odlišné dokumenty, jeden otisk

Kvůli nákladným výpočtům je dnes nereálné, aby někdo úmyslně kolizi SHA-1 zneužil. Přesto ale první reálný důkaz musí donutit vydavatele certifikátů a tvůrce softwaru, aby začali přecházet na pokročilejší SHA-256 nebo SHA-3.