Ondrej Sevecek's Blog

Mnohdy se setkávám se strachem ze starších kryptografických heší (hash) jako je SHA-1, nebo MD5 nebo MD4. Lidé by rádi měli všude SHA2 (tedy například SHA-256 nebo i silnější). Jenže to vždycky nelze, kvůli kompatibilitě se staršími aplikacemi.

SHA2 umí až Windows XP SP3, navíc různé jejich funkce potřebují ještě samostatné aktualizace na výžádání (například autoenrollment vyžaduje záplatu KB968730). Windows Server 2003 také potřebuje aktualizaci na vyžádání (KB938397), jen SP2 vám sám o sobě nepomůže. System Center Configuration Manager 2007 v Native Mode umí SHA2 až na Windows Server 2008/R2 a Windows Vista/7 bez ohledu na záplaty. Windows Phone 7 je první telefon s SHA2 podporou. Nedávno jsem zaznamenal problém s TMG 2010 při SSL inspekci, který je zřejmě způsoben také SHA2 certifikáty. IPSec umí pro AH a ESP používat SHA2 signatury až od Windows 7 a Windows Server 2008/R2. Čipové karty s tím mají problémy. IOS Security dokument vůbec o SHA-2 nehovoří, všechno je jenom SHA-1. A prostě vůbec :-)

Pojďme se tedy zamyslet, jestli jsou ty starší SHA-1 a MD5 opravdu tak strašně nebezpečné. A porovnejme je s běžnou bezpečností normální intranetové sítě. Uvidíte, že i když jsou známy některé jejich problémy, mnohé intranety jsou pořád ještě o hooodně slabší :-)

Neříkám, že já nechci SHA2, samozřejmě. Ale myslím, že není potřeba tlačit na jedné straně na pilu a na druhé nechat dveře rozvalené. Viz. jeden můj známý. Je děsně bohatej, tak si nechal na svůj dům namontovat neprůstřelné dveře s pěti zámky, kódovým zámkem a kamerou a kdoví čím ještě. A nějak zapomněl, že dozadu má francouzské okno. Takže hádejte, kudy asi přišli?

Budeme řešit tedy praktickou bezpečnost, nikoliv nějaké hardcore kryptografické speciality.

Problémy heší

Každý hešovací algoritmus má základní problém zvaný kolize. Ke každé heši vždycky existuje nekonečno (prostě více) různých textů, které mají tuto stejnou heš. Pokud jsou tyhle kolize čistě aritmetické, tak mě to moc nevadí. Aritmetická kolize například k dlužnímu úpisu vypadá jako náhodná břečka. Tedy rozhodně ne jako dlužní úpis.

Pokud něco podepíšu SHA-1, tak krom několika známých konkrétních heší, jsou všechny další pokusy čistě aritmetické. K digitálnímu certifikátu s SHA-1 podpisem se dá najít něco, co jako certifikát rozhodně nevypadá. A to ještě ne nijak snadno - viz. dále.

MD5 má něco horšího. Jde udělat útok tzv. choosen-prefix. Existuje známý prostor heší, které mají jednoduše nalezitelné kolize (viz. známý případ z roku 2008 za použití 200 Sony 3 PlayStation). A to ještě "pěkné kolize". Takže k dlužnímu úpisu najdete další dlužní úpis, například s nějakou jinou částkou (asi docela náhodnou, aby se to pěkně dopočetlo, ale to už by mi bylo jedno, jestli mi někdo dluží 10 milionů, nebo 10 385 110,39 USD :-). Aby vám to vyšlo, museli byste ale někomu půjčit tak, aby ten dlužní úpis měl přávě jednu z těch "pěkných" MD5 signatur.

Takže by bylo potřeba vědět dopředu, co přesně se bude později podepisovat (dlužní úpis, nebo třeba certifikát). Kolik tomu člověku musíte půjčit, aby výsledná heš byla "pěkná". Tohle šlo dříve dělat v případě MD5 certifikátů, pokud autority nedávaly do vydávaných certifikátů náhodné sériové číslo.

Podívejte se klidně, všechny web servery dneska mají certifikáty s náhodným sériovým číslem. Autorita tím jednoduše brání, aby žadatel věděl dopředu, co se bude podepisovat. Navíc certifikační autority si vygenerují sériové číslo takové, aby se náhodou netrefily do té "pěkné MD5 ani SHA-1 heše".

U heší nás tedy už zajímají jenom aritmetické kolize a náročnost, jak je zjistit.

Standard, které mi o tom skutečně něco řekne

Ten nám dává organizace NIST (National Institute of Standards and Technology), jehož doporučeními se řídí US administrativa, armáda a vůbec všichni, tedy i Windows. Jedná se o jejich algorithm advisory (přesněji NIST Special Publication 800-57 March, 2007).

Je tu úžasná tabulka (comparable algorithm strenghts) porovnávající síly různých algoritmů k jakési standardní bitové síle. Cca to znamená, kolik výpočetních cyklů ve formě 2^X byste museli udělat, abyste našli aritmetickou kolizi (nebo klíč v případě šifrovacích algoritmů). Tabulku najdete v kapitole 5.6.1. v první části Recommendation for Key Management – Part 1: General dokumentu.

Jeji zjednodušená a zkompilovaná verze je tu (poznámka MD5 a MD4 není přímo v NIST standardu, protože jsou definována jiným, otevřeným standardem podle RFC):

Co to tedy znamená? No SHA-1 je 80bitová bezpečnost. To znamená, že k nalezení čistě aritmetické břečka-kolize by bylo potřeba 2^80 výpočtů. MD5 je dokonce silnější a to s bezpečností 112bitovou (MD5 a MD4 viz. článek zde, sloupeček second-preimage).

Tabulka je super na porovnání různých algoritmů. Je zbytečné dávat AES-256 (256 bitová bezpečnost), když k tomu používáte jen SHA-256 (128 bitová bezpečnost). Nemá valnou cenu generovat certifikační autoritu s 4096 RSA klíčem (více jak 128bitová bezpečnost, když podpis je SHA-1 (80bitová bezpečnost). A tak podobně.

Porovnejme to s bezpečností Windows hesel

Naše intranety stojí ovšem primárně na bezpečnosti hesel. Uživatelé i správci je ve velké většině používají k přihlašování. Samozřejmě, měli byste mít čipové, ale to je prozatím hudba budoucnosti, než si lidé uvědomí, že jejich data si to zaslouží.

Takže jaká je bezpečnost třeba 8znakového hesla? Hesla ve Windows jsou uložena ve formě MD4 heše. Tuhle heš můžete získat z lokálních databází, lokálních přihlašovacích keší, ze síťové NTLM a Kerberos komunikace, nebo z databáze Active Directory. A řekněme, že je budeme krekovat.

Takže budu mít MD4 heš a k tomu budu muset generovat různá hesla délky 8 znaků a počítat MD4 heš. Jakmile se trefím, jupí, mám heslo (nebo kolizi, ale to mi k přihlášení bude stačit). Pro další výpočet uvažujme, že MD4 je stejně časově náročné a složité vypočítat, jako jiné heše (ve skutečnosti je SHA-1 ještě asi 10x časově náročnější a MD4 má jen 64bitovou složitost).

Kolik je možných 8znakových hesel? Na každé pozici můžeme dát 25 malých, 25 velkých znaků, 10 číslic a řekněmě 20 speciálních znaků například. To je celkem 80 znaků na každou pozici (a to při nejlepším, 80% hesel na světě je pouze alfanumerických).

Počet možných hesel je tedy 80^8 = 1 677 721 600 000 000. Berme, že statisticky to heslo uhádneme za polovinu pokusů, tzn. 80^8 / 2. Takže jaká je to mocnina dvojky?

2^x = 80^8 / 2
x * log 2 = log (80^8 / 2)
x = log (80^8 / 2) / log 2
x = 50

Z výpočtu plyne, že 8znakové heslo má složitost jen 50bitovou (nebo spíše ještě menší). V následující tabulce to máte pěkně shrnuto pro různé délky hesel:

Před závěrem

Takže pokud vaše síť používá množství hesel, která jsou slabší, než řekněme 12 znaků, libovolné podpisy certifikátů a dokumentů provedené pomocí SHA-1 jsou silnější. Na čem tedy stojí bezpečnost? No na heslech přece. A SHA-1 je hoodně v pohodě.

V tabulce je také pěkně vidět, proč jsou čipové karty spolu s certifikátem RSA 2048 tak bezpečné - protože jsou porovnatelné s alespoň 18 znakovým heslem (no, dobrá, chtělo by to ale lepší heš, jako třeba SHA-256 :-)

Na úplný závěr

Dobře, tak to jsou bitové bezpečnosti. A jak je tedy prakticky rychlé, kreknout takové 8 znakové, nebo 12 znakové heslo (a potažmo SHA-1 podpis)?

Když použijete ElcomSoft Distributed Password Recovery, který umí lámat MD4 heše na grafických procesorech (GPU) a to ještě navíc na více strojích současně, tak můžete dosáhnout něčeho jako 23 dnů na jednom stroji pro 8 znakové heslo. Následující tabulka to shrnuje pro větší délky hesla:

Takže přiznejme si. Je SHA-1 opravdu tak nebezpečná? Samozřejmě, pokud můžete, běžte do něčeho silnějšího, ale opatrně, možná budete mít problémy s kompatibilitou.