Hlavní navigace

SHA-1 není bezpečná, Google ukázal kolizi

Petr Krčmář

Deset let poté, co byla ukázána slabina hašovací funkce SHA-1, je k dispozici první reálný útok. Google společně s CWI oznámil, že objevil funkci, která stotisíckrát urychluje nalezení kolize.

Google oznámil, že se mu podařilo prolomit bezpečnost hašovací funkce SHA-1. Od první publikované slabiny po úspěšný útok tak uběhlo deset let. Dva roky trvalo vědcům z CWI Institute in Amsterdam a společnosti Google, než dokončili práci na slabině a přinesli důkaz toho, že kolizní funkce existuje a významně urychluje útok. Detaily popisuje dokument The first collision for full SHA-1 [PDF].

Hašovací funkce hrají v moderní kryptografii naprosto zásadní roli, používají se při elektronickém podepisování dokumentů, ověřování certifikátů v prohlížeči, správě kódu v repozitářích nebo třeba vyhledávání duplicitních souborů na disku. Bezpečnost závisí na tom, že není možné najít dva dokumenty se stejným otiskem jinak, než hrubou silou. Zároveň každá změna dokumentu vyvolá nepredikovatelnou změnu otisku. Zašifrujete otisk a získáte elektronický podpis konkrétního dokumentu.

Google nyní předvedl takzvanou kolizní funkci, která umožňuje v relativně krátkém čase vytvořit dva kolizní dokumenty (kolize prvního řádu). Jinými slovy je možné vytvořit dva různé dokumenty, které mají stejný otisk SHA-1. Samozřejmě je možné postupovat hrubou silou a upravovat v dokumentu náhodná data, ale takový útok by na moderním grafickém procesoru zabral 12 000 000 let.

Google společně s CWI představil útok SHAttered, kterým je možné tento čas zkrátit sto tisíckrát. Na stovce grafických procesorů tak dokážete vytvořit kolizní dokumenty během jednoho roku. Může jít pochopitelně o jakýkoliv druh dat, ideální jsou však takové formáty, ve kterých je možné neomezeně upravovat nadbytečnou výplň a tím měnit výsledný otisk – PDF, TLS certifikát, Exif v JPEG a podobně.

Náročnost prolomení hašovacích funkcí

S takovým nástrojem je možné obecně vytvořit dva libovolné dokumenty, které budou mít stejný otisk. Pokud elektronicky podepíšeme jeden z nich, bude podpis platný i pro druhý dokument. Při ověření pak nevzniknou žádné pochyby, protože ověřovaný dokument má správný otisk a tedy i podpis. Můžeme tak například vytvořit dvě smlouvy, nechat protistranu podepsat jednu z nich a poté podpis použít na druhé, která pro nás bude třeba výhodnější.

Příklad jako důkaz

Google se řídí vlastními pravidly pro zveřejňování bezpečnostních slabin, která stanovují lhůtu 90 dnů mezi oznámením chyby a zveřejněním konkrétního kódu. V tuto chvíli tedy není k dispozici utilita, kterou by bylo možné okamžitě nasadit a vytvořit kolizní dokument. Google to ale udělal za nás a jako důkaz zveřejnil dva dokumenty ve formátu PDF: shattered-1.pdf a shattered-2.pdf.

Obrázek dvou odlišných dokumentů

Oba dokumenty mají shodnou velikost, ale liší se barvou pozadí. Rozhodně jde o dva různé soubory. Přesto mají stejné otisky SHA-1.

$ sha1sum *
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
$ sha256sum *
2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  shattered-1.pdf
d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  shattered-2.pdf

Vědci tvrdí, že k realizaci útoku potřebovali provést 9×1018 hašování pomocí SHA-1. V první fázi útoku potřebovali 6500 let procesorového výkonu a na druhou fázi už stačilo jen 110 let výkonu grafického procesoru.

Test prozradí manipulovaný dokument

Google sice nezveřejnil samotný kód k provedení útoku, ale nabídl testovací utilitu, která spočítá otisky SHA-1 a zároveň detekuje kolizní dokument. Konkrétně to, zda je daný soubor jednou ze součástí kolizního útoku. Pokud nechcete utilitu instalovat, můžete využít webové rozhraní na webu Shattered.io, které stejný test provede. Pravděpodobnost falešné pozitivity je podle autorů 2-90.

Není třeba panikařit

Nutno dodat, že není důvod k žádné panice. O slabinách hašovací funkce SHA-1 se ví více než deset let organizace NIST už ji dvanáct let nedoporučuje [PDF], od roku 2010 se považuje za zastaralou a nedostatečně bezpečnou.

Na to už velká část počítačového světa zareagovala a například pravidla konsorcia CA/Browser Forum už od 1. ledna 2016 znemožňují vydávání nových certifikátů s otisky SHA-1. Prohlížeče na to reagují a například aktuální Chrome 56 už certifikáty s SHA-1 označuje za nebezpečné (privátní certifikáty bude možné používat ještě dva roky). Firefox by měl velmi brzy přijít se stejným řešením. Bohužel to platí pouze pro globálně důvěryhodné autority, ale existuje celá řada starých systémů, které používají vlastní řetězce důvěry a staví na SHA-1.

Bohužel hašovací funkce SHA-1 je rozšířená do mnoha dalších koutů počítačového světa a slouží k autorizaci dokumentů, podepisování software nebo je napevno zadrátovaná do nejrůznějších aplikací. Nejkřiklavějším příkladem je verzovací systém Git, kde je SHA-1 základním stavebním kamenem. Je zde tedy teoretické riziko, že nalezení kolize umožní útočníkovi propašovat do repozitáře závadný obsah. Není to však úplně jednoduché. Na problematiku kolize v Gitu odpovídal už před časem Linus Torvalds.

Není to zdaleka první hašovací funkce, která byla prohlášena za slabou a později zlomena. Připomeňme, že dříve velmi populární MD5 byla v roce 1996 označena za nedoporučovanou a v roce 2004 byla nalezena první kolize. V roce 2005 pak český kryptolog Vlastimil Klíma přišel s vylepšeným algoritmem schopným hledat kolize na běžném počítači v řádu hodin. O rok později pak přišel s metodou zvanou tunelování, díky které byl schopen hledat kolize do minuty.

Naštěstí je možné stále používat kombinaci SHA-1 a MD5. Obě hašovací funkce jsou sice slabé a byly u nich nalezeny kolize, ale neexistuje (zatím?) způsob, jak vytvořit dva dokumenty, které by byly kolizní při použití obou funkcí zároveň. Přesto je velmi dobrý nápad přejít na bezpečnější alternativy jako SHA-256.

Našli jste v článku chybu?