Dotaz: Použití HASH (proč MD5, a jak uhoudnout pouzitou techniku)

[polo23]

Ahoj, chtel bych se zeptat na par veci ohledne pouziti hashovacich funkci. 1) Zajima me proc se jeste porad pouziva MD5 kdyz ta je uz dlouhou dobu oznacena za nevyhovujici. Co me trochu vydesilo bylo kdyz jsem si precetl ze v souboru /etc/shadow zacina heslo 1$1 tak to znamena ze hesla jsou ulozena jako MD5 hash. Muze mi nekdo vysvetlit proc v dnesni dobe Linux nepouziva napr SHA?

Dalsi vec co mi neleze do hlavy... Kdysi jsem se kdysi zajimal o sifrovani v Truecrypt tak jsme si rikal ze kdyz AES ma 256 bitu tak kde se berou kdyz zadam jako heslo napr "aaa" a= v ASCII 8bit cili dohromady by to pak bylo AES 24bit coz je smesne. Bylo mi receno ze kdyz v Truecryptu zadam heslo tak se vytvori nejprve hash a to je vlastne ten klic. Cili z "aaa" se vytvori 256bit HASH a ten je pouzit pro AES. Kdyz chci heslo do truecryptu prolomit mam nasledujici moznosti:

1) Zacnu zadavat vsechny mozne kombinace klice konce se zrejme nedockam pac je to 2 na 256 kombinaci.

2) Donesu si tabulku zhashovanych hesel a zacnu moje hashe porovnavat s tema co jsem "ukradl" pri shode si jen zjistim jakemu retezci znaku patri a mam heslo. Co mi vsak neni jasne je to jaky hashovaci algoritmus pouzit pac kdyz budu mit tabulku hashu SHA a prijdu k systemu kde je hash ulozen jako MD5 tak je mi ma tabulka asi na prd ze?

3) slovnikovy utok

4) Zkouset zadavat kombinace vsech moznych hesel(coz by melo byt kratsi jak zkouseni zadavat vsechny kombinace 256bitovych klicu). Pri predpokladu ze uzivatele pouzivaji max 9 mistna hesla...

Odpovědi

[Filip Jirsák]

Zajima me proc se jeste porad pouziva MD5 kdyz ta je uz dlouhou dobu oznacena za nevyhovujici.

Protože se používá ve spoustě aplikací a ve spoustě případů interakce. Zvlášť v druhém případě je často nutné nejprve upravit protokol, aby uměl předávat i informaci o použitém druhu hashovací funkce, pak upravit obě či více aplikací, které takto komunikují, a pak teprve můžete hashovací funkci změnit.

Co me trochu vydesilo bylo kdyz jsem si precetl ze v souboru /etc/shadow zacina heslo 1$1 tak to znamena ze hesla jsou ulozena jako MD5 hash. Muze mi nekdo vysvetlit proc v dnesni dobe Linux nepouziva napr SHA?

To ale není chyba Linuxu, ale vás jako správce příslušného počítače – podívejte se, co máte nastavené v /etc/login.defs (nebo jeho obdobě, vizte man 5 passwd).

2) Donesu si tabulku zhashovanych hesel a zacnu moje hashe porovnavat s tema co jsem "ukradl" pri shode si jen zjistim jakemu retezci znaku patri a mam heslo. Co mi vsak neni jasne je to jaky hashovaci algoritmus pouzit pac kdyz budu mit tabulku hashu SHA a prijdu k systemu kde je hash ulozen jako MD5 tak je mi ma tabulka asi na prd ze?

To je nesmysl. Hash, který slouží jako klíč k šifrování, samozřejmě není nikde uložen, takže jej nemůžete ukrást. Že se hash počítá ze zadaného hesla je jenom user-friendly vlastnost programu, aby vás nenutil pamatovat si hash. Nic vám nebrání vzít zdrojáky a upravit je tak, aby na vstupu očekával rovnou hash. Z toho už je snad jasné, že ten hash nesmí být někde uložen.

3) slovnikovy utok

4) Zkouset zadavat kombinace vsech moznych hesel(coz by melo byt kratsi jak zkouseni zadavat vsechny kombinace 256bitovych klicu). Pri predpokladu ze uzivatele pouzivaji max 9 mistna hesla...

3) a 4) je totéž, a samozřejmě nemusíte zadávat hesla, ale můžete (asi po drobné úpravě programu) zadávat přímo hashe. A seznam hashů ke slovníkovým heslům určitě půjde snadno najít na internetu. Bezpečnost čehokoli, co je závislé na heslu, ale samozřejmě závisí na tom, jak silné heslo je – pokud použijete krátké heslo ze slovníku, je to vždycky problém, a žádné hashování tomu nezabrání. Pro Truecrypt tedy nemá funkce použitá pro hashování hesla prakticky žádný bezpečnostní význam – stačí, pokud je dostatečně náhodná, tj. problém by byl, pokud by pro různé vstupy dávala stejné nebo podobné výsledky, takže byste onu oblast 2²⁵⁶ kombinací mohl zredukovat třeba na 2¹⁶ nebo tak něco. To, že pro MD5 existuje popsaný způsob hledání kolizí (tj. dokážete pro zadané heslo převedené na MD5 hash najít jiného heslo, které vede na stejný hash), nemá žádný význam – důležitý a tajný je právě až ten hash, a vy si můžete zdrojáky snadno upravit tak, abyste zadával přímo ten hash, takže pokud víte hash, nepotřebujete k němu hledat odpovídající heslo.

[polo23]

V souboru login.defs jsem nenasel zadnou direktivu jak zmenit hashovaci funkci, ani jsem nevygooglil:( Jeste bych se chtel zeptat kdyz v tom truecryptu neni ani heslo ani hash ulozen jak tedy truecrypt pozna po zadani hesla ze vse je ok a ze ma sifrovat/desifrovat?

[Filip Jirsák]

V mém man passwd se píše, že tam je možné nastavit ENCRYPT_METHOD na DES, MD5, SHA256 nebo SHA512. Možná mám jinou verzi těchto utilit a PAMu.

Jeste bych se chtel zeptat kdyz v tom truecryptu neni ani heslo ani hash ulozen jak tedy truecrypt pozna po zadani hesla ze vse je ok a ze ma sifrovat/desifrovat?

Zkusí tím hashem příslušný oddíl/soubor rozšifrovat, a když ve výsledku najde svou hlavičku, je vše OK, když ji tam nenajde, je buď špatně heslo/hash, nebo se pokoušíte rozšifrovat něco, co není zašifrováno TrueCryptem. Heslo ani hash samozřejmě nikde uložen být nemůže, jinak by si ho útočník jednoduše přečetl.

[Tarmaq]

nevim jak je to u truecryptu, ale normalne muzes cokoliv desifrovat spatnym klicem, jen ti nevylezou ty spravny data ;]

[polo23]

No tak to je mi jasne ze by mi z toho vylezl gulas:) Jinak pane Jirsák dekuji za vysvetleni. Zase jsem o neco moudrejsi:)

[stativ]

Protože se to nastavuje v PAM a ne v login.defs (tam se to myslím nastavovalo před příchodem PAM).

[polo23]

Dobry den, od doby napsani tohoto prispevku se mi par veci rozlezelo v hlave a mel bych jets ejednu otazku ohledne zjisteni hesla z ukoristeneho HASHe.

Mejme OS at Linux nebo Windows. Oba maji hesla zhashovana a tyto hashe ulozeny. Dejme tomu ze jsou oba stroje vypnute. Ja si vezmu program ktery ma databazi hashu a k nim prirazena prislusna hesla. Tento program budu mit na bootovatelnem CD(V praxi se pouziva treba Ophcrack). Nobootuju nactu soubor s hashem a zacnu hash ktery jsem dostal z OS porovnavat s tabulkou kterou mam na tom CD. Pri shode mam heslo. To je jasne a logicke.

To co mi ale neleze do hlavy je nasledujici vec. Dejme tomu ze v tech OS je pouzito MD5 ale hashe na CD byly vytvoreny pomoci napr pomoci SHA256. Potom zakonite kdyz najdu v me tabulce hash ktery odpovida tomu co je ulozen v OS tak je mi to k nicemu pac "heslo" ktere je v me tabulce prirazeno k hashi neni stejne jako skutecne heslo do OS a to proto ze hashe byly vytvoreny kazdy jinou metodou(funkci). Uvedu jednoduchy priklad: Heslo do systemu je Pavel, MD5 je aaasssdddfff. Na boot CD mam SHA256 hash aaasssdddfff ten vsak odpovida retezci napr. Petr. A to proto ze byla pouzita jina Hashovaci technika. Z toho plyne ze pokud chci na nejaky system takto zautocit pak musim zakonite znat HASH funkci prislusneho systemu.

 

Je ma teorie spravna?

[Semo]

Nobootuju nactu soubor s hashem a zacnu hash ktery jsem dostal z OS porovnavat s tabulkou kterou mam na tom CD. Pri shode mam heslo.

Preto sa pouziva "solenie" hesiel ("salt" v jazyku zapadnych sudruhov). Ku novemu heslu sa pri hashovani este prida nahodny retazec a zahashuje sa az toto zretazenie. Tento nahodny retazec je potom ulozeny spolu s hashom. Pri overovani hesla sa ku zadanemu retazcu prida salt, zahashuje sa a porovna s ulozenym hashom. Nepomoze to proti bruteforce, pretoze ked uz utocnik ziska hash, tak ma aj salt a moze skusat. Ale pomoze to proti slovnikovemu utoku, pretoze nie je technicky mozne, mat tabulku hashov pre vsetky 9 miestne hesla osolene vsetkymi moznymi nahodnymi saltmi.

Mam nejasny pocit, ze pred par rokmi bolo velke halo, ze Win 2k alebo XP nesolili hesla, takze po nabootovani z nejakej vhodne liveky sli hadat hesla len podla slovnika stiahnutelneho z webu.

Z toho plyne ze pokud chci na nejaky system takto zautocit pak musim zakonite znat HASH funkci prislusneho systemu.

Vzhladom na to, ze aj system, na ktory utocis si musi byt vedomy ako ma si ma ukladat hashe a overovat hesla, tak to niekde ma zapisane. A ked sa uz dostanes ku databazi hashov, tak sa pravdepodobne dokazes dostat aj ku tomu nastaveniu. (Navyse z tvaru hashu sa da vcelku spolahlivo uhadnut cim to bolo hashovane. Napr. vdaka znackam typu $!$ a pod.)

[polo23]

A ten salt se pouziva ve vsech OS? Podle me je to k nicemu pac pri soleni vznikne retezec ktery je akorat delsi jak heslo a z toho se udela hash. Jak jsem uz ale napsal mam tabulku hashu takze dany retezec najdu. Jediny problem bude separovat heslo od saltu ale to uz nebude nijak narocne. Muzete mi jest enapsat kde je takovy salt ulozeny-? V /etc/shadow nic takoveho neni. Diky

[dustin]

Ty máš tabulku všech možných MD5 hashů?

[polo23]

No ja ne ale treba SW OPHCRACK ma tabulku hashu a k nim prirazenych posloupnosti znaku. Myslim ze tam jsou vsechny hashe pro kombinace 9 znaku - takze pokud heslo neni delsi jak 9 znaku pak odpovidam ano mam.

[Andrej Herceg]

Ak sa používa salt, 9 znakov je dosť málo.

[Michal Kubeček]

Jenže to je dost velký rozdíl. Budete-li brát těch devět znaků nad 26-znakovou abecedou (malá písmena), dostanete 5.4E12 možností, bude-li to nad 62-znakovou abecedou (malá a velká písmena, číslice), bude to 1.4E16 možností, dokonce i při 256 znacích jste pořád na 4.7E21 možnostech. Všech MD5 hashů je ale 3.4E38. S ohledem na salt si to ale všechno ještě přenásobte 2^48 (adi 2.8E14).

Mimochodem, vaše tvrzení se mi zdá krajně nepravděpodobné, protože už při nejmenší variantě (26 znaků bez saltingu) by ta tabulka při 25 B na položku (16 hash, 9 heslo) musela mít 123 TB. Jistě, trochu by to šlo zkomprimovat, ale nevěřím, že tak zásadně, aby to stačilo k rozumné použitelnosti.

[limit_false]

Jak již psal někdo přede mnou, Ophcrack používá rainbow tables. V případe hesel se solí by předgenerované rainbow tabulky museli být vygenerovány pro všechny kombinace solí s heslama (lze to nahlížet i jako by salt byla součástí hesla). Salt k heslu přidá navíc cca 48 bitů entropie.

Vygenerování tabulky pro "solená" hesla délky 9 je teoreticky možné, ale trvalo by to neskutečně dlouho (proti nesoleným) a nejspíš by to nebylo moc kam uložit.

Navíc, k MD5 pořád není známý second preimage attack, kdy k pevně danému hashi X najdete správu M, která má stejný hash. Zatím jde "jenom" velice rychle nalézt dvě zprávy M1 a M2, které mají stejný hash X' (first preimage attack). Navíc to funguje pro libovolný inicializační vektor. Na lámání hesel to ale moc použitelné (zatím) není.

[limit_false]

BTW Teoretický limit výpočetní síly je dnes něco málo pod 2⁶⁴ operací. Jinak řečeno kousek od nalezení kolize SHA-1 hrubou sílou (birthday attack).

[Michal Kubeček]

Samotná hrubá síla by potřebovala 2^80, těch 2^64 je díky teoretickým výsledkům založeným na analýze algoritmu.

[Andrej Herceg]

Ak sa nemýlim, tak salt je časť za prefixom a pred prvým znakom $. Teda napr. v $1$xxxxxx$yyyyyyyyyyyyyyyyyyyyy je salt tá xxxxxx časť.

[polo23]

To znamena ze kdyz jsem si nastavil SHA512 pak to znamena ze hash bude mit 512/8=64 znaku. Cili yyyyyyyyyyyyyyyyyyyyy bude mit 64 znaku. V mem pripade jsme jich napocital pres 80 takze si rikam kde je asi chyba.

[Andrej Herceg]

Tých znakov by malo byť 86. To, že ich nie je 64, ale ich je 86 je spôsobené tým, že to v tom súbore musí byť text a teda sa nemôže použiť celý rozsah. Využívajú sa len znaky 0-9A-Za-z.

62^86 = 1.3986e154
256^64  = 1.3408e154

(z čoho je jasné, že sa tam ten 512 bitový hash zmestí)

[Michal Kubeček]

Využívajú sa len znaky 0-9A-Za-z.

Ještě lomítko a (pokud vaše tečka byla gramatická) tečka - potřebujete abecedu o 64 znacích. V principu to u všech algoritmů funguje tak, že se hash rozseká na šestibitové bloky (na konci se to doplní nulovými bity) a každý blok se zakóduje jedním znakem z té abecedy. Takže např. 128-bitový MD5 hash se doplní na 132 bitů, rozseká na 22 šestibitových bloků a ty se zakódují jako 22 znaků. U SHA-512 to vychází na zmíněných 86 znaků.

Na podobném principu je založeno třeba base-64 (nebo starší uuencode), jen používá jinou abecedu a trochu jinak řeší padding, protože tam nemáte a priori danou délku.

[Semo]

MD5 vyraba 128-bitove vysledky. Pokial je schopne vyprodukovat vsetky mozne 128-bitove cisla t.j. zobrazenie je "na", to neviem ci plati), tak by si musel mat tabulku o 2^128 polozkach. Co je cca 3.4x10^38. Ak by sme predpokladali, ze jednu moznost overis v jedinom takte procesora (co je dost nerealne ale budiz), mas 3GHz CPU, tak ti to bude trvat cca 3.6x10^21 rokov. Paralelizovat sa to da sice dobre, ale aj keby si si spravil botnet s miliardou 8 jadrovych pocitacov, tak ti to potrva cca 450 miliard rokov. Vela stastia.

[polo23]

Tak to co pises ma logiku ale neumim si vysvetlit jak je teda mozne ze napr SW Ophcrack zjisti max 9 mistne heslo jak z windows tak z linuxu behem par minut...

[Michal Kubeček]

Stačí se podívat na hlavní stránku projektu, kde se píše, že Ophcrack používá tzv. rainbow tables, což zdaleka neznamená kompletní tabulky všech možných hashů.

[Michal Kubeček]

Mimochodem, prohlížím ty stránky pozorně a není tam ani slovo o tom, že by ten nástroj uměl zjišťovat linuxová hesla. A podle FAQ to ani s hesly z Windows Vista není tak růžové, jak nám to tu prezentujete.

[polo23]

Omlouvam se mensi mystifikaci... mel jsem za to ze to umi i Linux hesla. Na to jsou ale jine softy jako John The Ripper a dalsi. jinak diky za vysvetleni ohledne tech hashu.

[dustin]

John je fajn, ale i krátké (6 znaků) ale netriviální heslo bude lámat spousty dnů/týdnů, pokud dříve netípneš.

[deadmail]

V systeme Windows (urcite v XP) sa salt nepouziva, navyse sa vzdy hashuje zvlast po 7 znakoch. Teda desifrovat 14 znakove heslo je len dva krat take tazke ako rozsifrovat heslo o 7 znakoch, asymptoticky teda heslo dlhsie ako 7 znakov nezvysuje obtiaznost rozsifrovania ...

[stativ]

Obvykle to poznáš podle délky a v případě /etc/shadow podlo toho, čím začíná ($1 MD5, $6 SHA-512 etc.)

[Jendа]

Z toho plyne ze pokud chci na nejaky system takto zautocit pak musim zakonite znat HASH funkci prislusneho systemu.

No, když už máš to LiveCD nabootované a / připojený (abys mohl přečíst /etc/shadow), tak to heslo na roota můžeš klidně změnit nebo do toho systému můžeš nainstalovat nějaký backdoor...

[eoj]

Zajima me proc se jeste porad pouziva MD5 kdyz ta je uz dlouhou dobu oznacena za nevyhovujici.
Jak kde.

Co me trochu vydesilo bylo kdyz jsem si precetl ze v souboru /etc/shadow zacina heslo 1$1 tak to znamena ze hesla jsou ulozena jako MD5 hash.
Takze asi muze byt pouzit i jiny algoritmus.

Muze mi nekdo vysvetlit proc v dnesni dobe Linux nepouziva napr SHA?
Proto.

[Bilbo]

1)Ve chvili, kdy se nekdo dostane k tomu, aby si precetl /etc/shadow tak uz ma prava roota a zadna hesla znat nepotrebuje - v tu chvili je to uz (skoro) jedno :)

MD5 je sice derave, ale porad lepsi nez stary DESovsky crypt, ktery sebedelsi heslo nejdrive orizl na 8 znaku (takze to pak jde louskat celkem jednoduse :)

Pokud vim, neni problem vyrobit dva soubory/retezce se stejnym hashem, ale zatim nevim o utoku, kde by k danemu hashi sel nejak snadno (= lepe nez hrubou silou) vytvorit retezec, ktery mu odpovida.

4) Max 9mistna hesla? Na sifrovani disku se pouzivaji o dost delsi, truecrypt ma doporucene minimum asi 20 znaku, paranoidni jedinci pouzivaji jeste o dost delsi hesla. Ty samozrejme nejsou ve slovniku a asi budou krome malych a velkych pismen obsahovat i cislice a ruzne specialni znaky :)

[Radovan Garabík]

Re 1) Každá aspoň trochu inteligentná konfigurácia spúšťa programy, overujúce heslá ako GID shadow, bez práva roota (man unix_chkpwd). Keď niekto nabúra takýto program, maximálne si tak môže prečítať shadow a do systému sa nedostane (pravda, kým neuhádne heslá z hashov...)

[Michal Kubeček]

Ještě bych doplnil:

5. To, čemu se říká MD5 při hashování hesel, není ve skutečnosti obyčejná MD5, ale algoritmus, který MD5 používá jako svou součást. Máte-li vhodnou verzi John-the-Ripper, je zajímavé porovnat si výsledky 'john -test' pro "FreeBSD MD5" a "Raw MD5".