Dňa 23.2.2017 bola publikovaná historicky prvá verejne známa kolízia hashovacieho algoritmu SHA-1, prezentovaná tímom expertov z CWI Amsterdam a Google. Tento „bug“, ako je v poslednej dobe zvykom, dostal vlastné meno aj s webom. Kolízia bola prezentovaná na dvoch PDF súboroch, ktoré mali pri otvorení iný obsah, no ich SHA-1 hash mal totožnú hodnotu. Algoritmus využíva aj napríklad elektronický podpis.
Ukážka kolízie SHA-1 na 2 PDF súboroch (zdroj: https://shattered.io)
Čo táto kolízia znamená pre bezpečnosť softvéru používajúceho SHA-1? Algoritmus sa používa používa vo veľkom množstve projektov ako GIT, SVN, BitTorrent alebo aj pri elektronických podpisoch. Je SHA-1 mŕtve?
Použitie SHA-1 je v štátnej správe zakázané od roku 2010. Existujúce nástroje neponúkajú možnosť vytvoriť podpis pomocou tohto algoritmu. Prakticky to zabraňuje zneužitiu existujúcej kolízie na vytvorenie nových kolíznych dokumentov. Podvrhnutie starších dokumentov, popísaných pomocou funkcie SHA-1, je pomocou súčasného útoku (tzv. “collison-attack”) reálne nemožné - prakticky útok tejto kategórie (tzv. “pre-image attack”) nebol publikovaný ani pre staršiu hashovaciu funkciu MD5.
Ak chcete vedieť prečo, čítajte ďalej - opíšeme si v skratke princíp hashovacích funkcií, typy útokov a detaily aktuálneho útoku.
Hashovacia funkcia je algoritmus, ktorý z ľubovoľne dlhého vstupu (pod tým si môžeme prestaviť čokoľvek v elektronickej podobe, napr. textový reťazec, dokument, súbor) vygeneruje výstup o fixnej dĺžke.
Dobrá hashovacia funkcia má spĺnať nasledovné vlastnosti:
Výpočtovo nemožné znamená, že aj keď poznáme algoritmus, ktorý by našiel výsledok (napr. skúsiť všetky možnosti - útok hrubou silou), tak je to časovo príliš náročné aby sa jednalo o praktický útok. Náročnosť útoku plným prehľadaním na nájdenie kolízie v SHA-1, pri použití rovnakej výpočtovej sily ako použil Google, je 100 000 rokov. Dokonalá hashovacia funkcia je teda digitálny odtlačok z dát, ktorý je nemožné sfalšovať.
MD5, SHA-1 a SHA-2 sú najznámejšie a donedávna aj najpoužívanejšie hashovacie funkcie. Všetky sú navrhnuté podobným spôsobom, ktorý sa nazýva Merkle–Damgård konštrukcia. Zľahka objasníme ako táto konštrukcia funguje, aby sme následne mohli vysvetliť existujúce útoky na tieto funkcie.
Hashovacie funkcie interne pracujú nad konkrétnou dĺžkou vstupu, tzv. dĺžkou bloku. Dĺžka bloku pre MD5 a SHA-1 a SHA-256 (najpoužívanejšia varianta SHA-2) je 512 bitov.
Okrem vstupného bloku hashovacia funkcia berie aj ďalší vstup - takzvaný inicializačný vektor. Ten nastavuje interný stav funkcie a ovplyvňuje výsledok. Po skombinovaní oboch vstupov funkcia vráti hash danej dĺžky.
Aby mohla hashovacia funkcia spracovať aj väčší vstup ako dĺžka bloku, používa sa práve Merkle–Damgård konštrukcia. Postup fungovania je nasledovný:
Schéma fungovania hashovacích funkcí s konštrukciou Merkle–Damgård (zdroj: Wikipedia)
V kryptografii sa definuje odolnosť hashovacích funkcií podľa týchto 3 kategórií:
Kategórie sú zoradené podľa náročnosti vytvorenia útoku na funkciu s touto vlastnosťou, od najjednoduchšej po najzložitejšiu. Nájsť kolíziu bez obmedzenia na hodnotu vstupu alebo výstupného hashu je výrazne jednoduchšie kvôli javu nazývanému narodeninový paradox. Ten sa dá demonštrovať pomocou nasledujúcej otázky:
Koľko ľudí musí byť v jednej miestnosti, aby bola pravdepodobnosť, že aspoň jedna dvojica má narodeniny v ten istý deň, aspoň 50%?
Matematicky (alebo experimentovaním) sa dá ukázať, že priemerne stačí len 23 osôb. Ak by sme chceli mať istotu, potrebujeme aspoň 366 osôb. Podobný princíp funguje aj v prípade hashovacích funkcií - ak má funkcia výstup o dĺžke 2n, tak na nájdenie prvej kolízie nám stačí v priemere vyskúšať 2n/2 vstupov. Pre funkciu s dĺžkou výstupu 16 bitov (216, 65536 možných hashov) stačí vyskúšať 28, teda 256 rôznych vstupov.
Spomínaný útok na SHA-1 sa radí do kategórie collision-attacks. Výskumníci publikovali kolízny blok (veľkosti 64 bajtov), ktorého SHA-1 hash je totožný. Náročnosť výpočtu bola približne 263 SHA-1 výpočtov, v porovnaní s brute-force útokom (zložitosť 280) je to asi 130 000 krát rýchlejší útok.
Kolízia na blokoch však funguje len v prípade, že pred kolíznym blokom funkcia spracovala konkrétny prefix, v tomto prípade je to hlavička PDF, pre ktorú bola táto kolízia vypočítaná. Matematicky zápis je nasledovný:
SHA1(P + C1 + S) = SHA1(P + C2 + S)
P je prefix obsahujúci PDF hlavičku, C1 a C2 sú kolízne bloky a S je ľubovoľný suffix. Z princípu konštrukcie Merkle–Damgård vyplýva, že na hodnote suffixu nezáleží, pretože interný stav funkcie po spracovaní častí P + C1 a P + C2 bude nastavený na rovnakú hodnotu. Tým pádom môžeme suffix nahradiť ľubovoľnými dátami a hash výsledného súboru bude rovnaký.
Odlišná situácia však nastáva v prípade, že máme známu hodnotu hashu a k nej hľadáme kolízny vstup - definícia pre-image útoku. Typicky príklad sú zahashované heslá v databáze. Na nájdenie hesla, ktoré má rovnaký hash ako pôvodné heslo, v prípade SHA-1 neexistuje lepšia metóda ako brute-force, čo má zložitosť 2160. To je so súčasným výkonom výpočtovo nemožné.
MD5 je staršia funkcia z tej istej rodiny hashovacích funkcií. Prvý kolízny útok bol publikovaný v roku 2004. Najnovší útok z roku 2013 má zložitosť 218, takýto výpočet beží na bežnom domácom počítači menej ako sekundu. Okrem kolízneho útoku bol na MD5 publikovaný aj tzv. chosen-prefix collision attack, teda kolízia so zvoleným prefixom. Jej dôsledky sú ešte závažnejšie, pretože umožňuje pre dva odlišné prefixy p1 a p2 nájsť správy m1 a m2 také, že platí:
md5(p1 + m1) = md5(p2 + m2)
Tento útok bol v roku 2008 reálne demonštrovaný pri sfalšovaní X.509 certifikátu (rozdielne prefixy obsahovali rôzne identity). V praxi využil tento útok malware Flame.
Zaujímavé je, že ani pre MD5 nebol doteraz publikovaný žiadny praktický pre-image útok. Najlepší možný útok má zložitosť 2123,4, čo je stále len teoretický útok. Situácia je teda podobná ako pri SHA-1.
Mohlo by sa zdať, že zneužitie súčasnej SHA-1 kolízie je čisto teoretické. Výpočet ďalšej kolízie je stále pomerne náročný a drahý, Googlu to trvalo rok a odhadovaná cena je minimálne na $100 000. V posledných dňoch sa však objavilo viacero zaujímavých aplikácií:
Elektronický podpis je v skutočnosti ďalšou aplikáciou hashovacích funkcií v kryptografii. Pri podpisovaní dát sa nepodpisujú celé dáta, ale hash týchto dát. Elektronický podpis teda využíva kombináciu hashovacej funkcie (napr. SHA-1, SHA-256) a podpisovej schémy (napr. využívajúca algoritmy RSA alebo DSA). Bezpečnosť elektronického podpisu z veľkej časti závisí na bezpečnosti použitej hashovacej funkcie. V prípade kolízie je aj hodnota podpisu rovnaká a teda nezaručuje autenticitu dát.
Konečne sa dostávame aj k praktickej stránke a to k detailom ZEPu a toho či nájdená kolízia SHA-1 ohrozuje bezpečnosť podpísaných dokumentov.
Dobrou správou je, že potencionálna zraniteľnosť SHA-1 je známa minimálne od roku 2005, kedy boli publikované prvé útoky. Od toho roku sa použitie SHA-1 neodporúčalo. Na Slovensku toto reflektovala vyhláška NBÚ 135/2009 Z.z., ktorá upravovala okrem iného aj použitie algoritmu SHA-1 v štátnej správe:
„Certifikované produkty pre zaručený elektronický podpis, využívajúce podpisové schémy s asymetrickým šifrovým algoritmom RSA s parametrom MinModLen 1024 bitov alebo nižším a certifikované produkty, využívajúce hašovaciu funkciu SHA-1, je možné používať do uplynutia doby platnosti certifikátu produktu, najdlhšie však do 31. decembra 2009.“
Od 1.1.2010 je teda používanie SHA-1 v štátnej správe zakázané.
Ako by teoreticky vyzeral útok, ktorý by chcel využiť nájdenú kolíziu v SHA-1? Prepokladajme, že útočník (Mallory) má záujem získať zaručený elektronický podpis obete (Alica) pre PDF dokument v ktorom sa tvrdí, že Alica prevádza na Malloryho celý svoj majetok. Mallory musí najskôr požiadať Alicu, aby podpísala úplne iný dokument s nesúvisiacim obsahom. Tento dokument by bol však špeciálne pripravený a obsahoval by predpripravený kolízny blok. Po získaní podpisu by útočník zamenil dokument za iný s druhým kolíznym blokom. Podpis takého dokumentu by bol rovnaký a validný. Tento príklad je zjednodušený a neuvažuje ďalšie scenáre, napr. že existujúce formáty podpisov (CAdES, XAdES, PAdES) môžu pred podpisovaním pridávať do dokumentu ďalšie dáta (ak by sa menil prefix podpisovaných dát, kolízny útok by nefungoval).
Každopádne útok je v tomto prípade nepoužiteľný, pretože žiadny certifikovaný nástroj dnes možnosť použiť SHA-1 neponúka. Platný elektronický podpis dokumentu s kolíznym blokom teda útočník od cudzej osoby nezíska.
Ako je to teda s podvrhovaním starších dokumentov podpísaných pred rokom 2010? Ak vlastníme takýto dokument, vieme obsah pôvodného dokument a jeho hash. Chceme vytvoriť iný dokument s tým istým hashom, čo je definícia „pre-image” útoku. Vytvorenie kolízneho dokumentu je teda nerealizovateľné a podobný útok sa v najbližšej dobe ani nepredpokladá. Prakticky by boli voči podobnému útoku dokonca chránené aj dokumenty s podpisom využívajúcim algoritmus MD5, kedže ani tu žiadny praktický „pre-image” útok neexistuje.
Existujúca kolízia SHA-1 má reálne bezpečnostné dopady už dnes a útoky na túto funkciu sa budú časom len zlepšovať. Ak teda zvažujete, ktorú hashovaciu funkciu použiť, odporúčame SHA-2 alebo SHA-3. Na druhú stranu, existujúce elektronické podpisy vytvorené pomocou SHA-1 sú v dohľadnej dobe v bezpečí, čo sa týka aj zaručeného elektronického podpisu na Slovensku.
