Kdo prolomil algoritmus SHA-1 a co to znamená pro Bitcoin?

Svět kryptografie žije v poslední době zprávami o tom, že výzkumníci Google a CWI Amsterdam úspěšně uměle vygenerovali dva různé soubory se stejným hashem. Podle kryptografických standardů tak protokol SHA-1 zdiskreditovali. Ale co to znamená v lidské řeči a jaké jsou důsledky pro bitcoinovou síť?

Nesrovnalosti hashů

Jak vysvětluje například Wikipedie, hash (jedním z příkladů je právě SHA-1) je matematická funkce, která vezme data různé velikosti, zpracuje je a vrátí textový řetězec pevné, předem stanovené délky. Jednou z nejdůležitějších funkcí hashů je porovnání, zda jsou dvě různé sady dat (soubory) stejné. Porovnáme-li tedy dva soubory s různými názvy a vyjde-li nám stejný hash, pak jsme si doteď mohli být jisti, že tyto dva soubory jsou totožné. Hashe pro identifikaci souborů často používaly systémy pro sdílení souborů, jako byl DC++, Kazaa, nebo třeba torrenty.

Dále se hashe v současnosti používají pro identifikaci uživatele tak, aby druhá strana neznala jeho heslo. Uživatel zadá heslo při vytvoření účtu na internetu, v systému se pak vytvoří hash tohoto hesla a ten se uloží. Jakmile se uživatel přihlašuje ke svému účtu, tak je jeho zadané heslo znovu zahashováno, hash je srovnán s hashem uloženým v databázi, a pokud se shodují, pustí uživatele do systému. Systém tak nezná uživatelovo heslo, a v případě, že jej uživatel ztratí, je nutný jeho reset. Pokud vám tedy nějaký systém mailem pošle vaše zapomenuté heslo, pak navrhujeme, abyste z tohoto systému rychle vycouvali – není totiž bezpečný.

Ale zpět k porovnání dvou souborů – doteď platilo, že dva soubory se stejným hashem jsou totožné, protože by stačilo změnit jediný znak v souboru a hash se změní také. Z toho dále plyne, že když mají dva různé soubory stejný hash, dojde k problémům.

Z hlediska matematických zákonů, kterými se hashovací funkce samozřejmě řídí, muselo nevyhnutelně jednoho krásného dne ke kolizi dojít, protože množství vstupních dat je potenciálně nekonečné, ale výstupní řetězec má pevnou délku a tudíž je také omezen nějakým maximálním množstvím kombinací (i když v případě hashe o délce desítek znaků je jich vážně mnoho).

Pro bezpečnou hashovací funkci je ale pravděpodobnost takového scénáře tak malá, že v praxi není možné udělat takové množství výpočtů, abychom se do ní strefili.

Důležité na výzkumu Google a CWI je to, že dokázali najít mnohem efektivnější metodu, jak uměle vytvořit kolizi, než jen naslepo hádat. Popravdě stotisíckrát efektivnější metodu. Právě díky její efektivitě je nyní algoritmus SHA-1 oficiálně zdiskreditován.  Na detaily se můžete podívat v angličtině na SHAttered.io.

Odměna za prolomení SHA-1

23. února 2017 bylo oznámeno, že dlouhou dobu vypsaná odměna za prolomení SHA-1 byla nárokována. Tuto odměnu – původně vypsanou kvůli zjištění zranitelnosti algoritmu SHA-1 – vypsal na fóru Bitcoin Talk v září 2013 kryptografický výzkumník Peter Todd, ale do minulého týdne zůstala netknutá. Todd tuto výzvu zaprogramoval do skriptu, který umožní komukoli převést odměnu v BTC z adresy, kde jsou uložené, na adresu podle vlastního výběru, a to za předpokladu, že bude někdo schopen odeslat dvě zprávy různého obsahu, které ale budou mít stejný výsledný hash (použije-li se SHA-1, samozřejmě). K Toddovi se pak připojili i další přispěvatelé, takže na dané adrese se sešlo celkem 2,5 Bitcoinu, tj. cca 75.000 kč.

Podle výzkumníka je z načasování nároku – těsně po oznámení o vytvořené kolizi – jasné, že o odměnu si neřekli původní výzkumníci z Google a CWI, ale někdo, kdo jen využil jejich výzkum a příležitost. Todd uvedl:

„Kdyby to byli sami autoři, čekal bych, že si odměnu vyzvednou těsně před publikací svého výzkumu. Tak to ale nebylo.“

Důsledky pro Bitcoin

Je velice důležité si zde říci, že bitcoinový protokol nepracuje s algoritmem SHA-1, ale s mnohem bezpečnějším SHA-256, takže bitcoinová síť není touto zprávou nijak zasažena. Nicméně kromě obohacení neznámého příjemce odměny se přeci jen tato zpráva týká i jádrových vývojářů BTC.  Systém správy verzí (Git) používá totiž SHA-1 ke generování hashů pro účely potvrzování.

„Následky nejsou takové, abychom museli hned přestat používat Git“, uvádí Todd, „ale bude teď mnohem důležitější kontrolovat práci ostatních lidí, protože třetí strana se takto může pokusit vám podstrčit malware“.

Problém je v tom, že útočník může teoreticky vytvořit dvě různé verze kódu, které budou mít stejný hash. K tomu ovšem máme ještě dost daleko, když vezmeme v úvahu, kolik výpočetního výkonu je potřeba k vytvoření duplicity. Výzkumníci také zřejmě vytvořili náhodný pdf soubor, nesnažili se tedy podstrčit do pdf konkrétní obsah tak, aby to vedlo ke stejnému hashi dvou různých souborů pdf.

Stejně jako na prolomení SHA-1 vypsal Todd odměnu i na prolomení algoritmů RIPE MD160 a SHA-256. Oba dva jsou pro integritu bitcoinového protokolu klíčové. Kdyby byly zpochybněny, byl by to pravděpodobně konec Bitcoinu. Todd se loučí slovy:

„Pokud tu odměnu dokážete vybrat, pak navrhuji, abyste získané Bitcoiny utratili maximálně rychle!“.

Související

PŘIDEJTE SE DO DISKUZE