kolizia-sha-1

Kolízia v SHA-1, aké sú dopady na elektronický podpis?

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.

sha-1 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.

Čo je to hash?

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:

  • Pre rovnaký vstup vždy vráti rovnaký výstup.
  • Je rýchla.
  • Z hodnoty hashu je výpočtovo nemožné zistiť, aká bola pôvodná hodnota (tzv. jednosmerná funkcia).
  • Je výpočtovo nemožné nájsť 2 rozdielne vstupy, ktoré majú rovnaký hash.
  • Malá zmena vo vstupných dátach spôsobí veľkú zmenu vo výstupných dátach.

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, SHA-2

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ý:

  1. Celý vstup sa rozdelí na bloky s dĺžkou 512 bitov.
  2. Ak dĺžka vstupu nie je násobkom hodnoty dĺžky bloku, použije sa tzv. padding-schéma a chýbajúce bity sa doplnia.
  3. Vstup sa spracúva po postupne po blokoch. Výstup z hashu predchádzajúceho bloku sa použije na inicializovanie stavu hashovacej funkcie ďalšieho bloku. Na inicializáciu stavu pri výpočte prvého bloku sa použije fixný inicializačný vektor.
  4. Konečný hash je výstup funkcie po spracovaní posledného bloku.

sha-1 Schéma fungovania hashovacích funkcí s konštrukciou Merkle–Damgård (zdroj: Wikipedia)

Útoky - teória

V kryptografii sa definuje odolnosť hashovacích funkcií podľa týchto 3 kategórií:

  • Collision resistance Tzv. odolnosť voči kolíziám. Znamená to, že je nemožné nájsť 2 ľubovoľné vstupy, ktoré majú rovnaký hash.
  • Pre-image resistance Ak máme daný hash, je nemožné nájsť pôvodný vstup hashovacej funkcie.
  • Second pre-image resistance Pre daný vstup je nemožné nájsť iný vstup s rovnakým hashom.



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.

SHA-1 je SHAttered

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ý.

Pre-image útok

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é.

Porovnanie s MD5

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.

Čo s jedinou kolíziou?

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í:

  • Služba na generovanie kolíznych PDF súborov. Principiálne využíva existujúce kolízne PDF s tým, že nahradí vložené obrázky vlastnými. Limit na veľkosť obrázka je 64 kB, aby boli vygenerované súbory validné PDF dokumenty.
  • Podobným trikom boli vygenerované kolízne HTML súbory.
  • SVN repozitár využíva SHA-1 na detekciu kolízií. V prípade uloženia kolíznych súborov do SVN repozitára sa repozitár znefunkční kvôli nekonzistencii.
  • BitTorrent využíva SHA-1 na autentifikáciu prenášaných dát. BitErrant demonštruje ako vygenerovať rovnaký .torrent súbor pre dva rôzne súbory s využitím SHA-1 kolízie.

Využitie hashu pri podpisovaní

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.

Bezpečnosť ZEPu (zaručeného elektronického podpisu)

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.

Keep calm and carry on

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.

About the author

Citadelo
Citadelo je dom plný etických hackerov na vašej strane. Pomáhame otestovať ich informačnú bezpečnosť. Podrobte svoje IT prostredie výzve a odhaľte, do akej miery sú vaše citlivé dáta chránené.
Zobraziť viac od autora

Related posts

Citadelo Security Evening - jeseň 2017

Blog | | Citadelo
Hackerské tipy, odhalenie zraniteľnosti s medzinárodným dopadom a ako ukradnúť milióny. Nie, to nie sú názvy filmov, ale témy prednášok, ktoré odzneli na Citadelo Security Evening (CSE)
Zobraziť

WPA2 prelomená. Viete ako ochrániť svoje dáta?

Blog | | Citadelo
Bezpečnostný analytik Mathy Vanhoef zverejnil širokej verejnosti vážnu bezpečnostnú chybu vo WPA2 protokole. WPA2 protokol sa bežne používa na šifrovanie komunikácie pri použití Wi-Fi, jeho predchodcovia sú WPA a WEP.
Zobraziť

Odhalili sme zraniteľnosť CMS Made Simple

Blog | | Citadelo
CMS Made Simple je voľne dostupný, open source CMS. Pozreli sme sa bližšie na zraniteľnosť CMS Made Simple a o výsledok sme sa s vami podelili.
Zobraziť

Úspešne sme absolvovali certifikáciu OSCP

Blog | | Citadelo
OSCP je skúška, ktorá preverí teoretické aj praktické znalosti. Narozdiel od iných skúšok, OSCP a jej úspešné absolvovanie hovorí o určitej znalosti držitela certifikátu.
Zobraziť