md5(md5()) vs md5()

[moubik]

Ma uitam peste codul de la e107 si vroiam sa aflu daca am cookie-ul cum pot sa aflu parola initiala.

Parola in baza de date este un MD5() al parolei introduse de user.

Cookie-ul contine MD5() introdusa initial de user

=> cookie = md5(md5(parola))

Si asa a inceput cearta.

Idea sustinuta de aramdune:

md5(md5()) este mai weak decat md5()

Ideea sustinuta de mine e exact invers.

Argumente:

MD5()

O parola in general are 8 caractere si de obicei contine doar litere (aici vorbim de userii normali, nu ma intereseaza ce marime au ale voastre )

Criptata cu md5 dureaza brut aproximativ 14h la o viteza de 4Mh/s (Milioane hash-uri pe secunda) sa fie sparta

Deci pentru a se calcula e nevoie sa se genereze 25^8 combinatii = 152.587.890.625

O parola mai secure si mai populara printre noi este parola de aproximativ 14 caractere cu litere si cifre.

Pentru a fi sparta e nevoie de aproximativ 5 ani la aceeasi viteza

Numarul de combinatii este 35^14 = 4.139.545.122.369.384.765.625

MD5(MD5())

Deci se face MD5 de o parola arbitrara si din acest hash se mai obtine inca un MD5.

Ok. Aici ce se intampla ?

exemplu:

md5(1) => 2

md5(2) => 3

Stim ca hash-ul este de marime 32 de bytes si contine numai caractere hexa.

Pentru a sparge primul hash avem 16^32 combinatii = 340.282.366.920.938.463.463.374.607.431.768.211.456

Aici se intampla o chestie interesanta (aramdune mi-a atras atentia aici) apare hash collision.

Ce inseamna hash collision?

Pentru a raspunde trebuie sa explicam cele 2 tipuri de criptare.

Nu stiu denumirile standard, eu le spun unidirectionala si bidirectionala.

O sa prezint cele 2 tipuri de criptari prin matematica simpla.

Bidirectionala

Avem 2 functii:

x:A -> B , f(x)=y

x:B -> A , g(x)=y

si proprietatile

f(x)=y

g(y)=x

g() este inversa functiei f()

=> f() este functie bijectiva: pentru orice x din A exista un singur y in B pentru care f(x)=y

Asta inseamna ca putem cripta si decripta informatia fiecare cu cate o functie dedicata cu complexitate O(1)

observatii:

A poate sa fie egal cu B

f() poate sa fie egal cu g() => cazul xor

Aceasta este o prezentare foarte simplista a genului acesta de criptari. De obicei se mai folosesc si key de criptare.

Exemple de criptari: DES, 3DES, RSA, AES

Unidirectionala

Avem o singura functie:

x:A -> B , f(x)=y

Aceasta functie cripteaza informatia, dar nu poate fi obtinuta printr-o functie cu complexitate O(1)

Functia f() nu mai este bijectiva, deci pentru orice x din A exista mai multe variabile in B astfel incat f(x)=y

Deci daca stim pe y, singura metoda de a-l afla pe x este sa facem bruteforce.

Practic incercam toate elementele din x care apartin multimii A pana cand f(x)=y si astfel am gasit solutia.

Exemple de criptari: SHA1, SHA2, MD4, MD5, RC4

Aici apare partea interesanta si anume Hash Collision.

Hash Collision

Pentru ca la criptarea MD5 avem intotdeauna un rezultat de marime de 32 de caractere si o multime de 16 (0-9,a-f)

avem numar limitat de elemente pe care putem sa le obtinem prin criptarea de date.

Si mai exact:

Numar maxim de rezultate ale criptarii MD5 este:

16^32 combinatii = 340.282.366.920.938.463.463.374.607.431.768.211.456

Ce rezultat are acest lucru?

Daca criptam 16^32 +1 texte diferite SIGUR avem 2 hash-uri care sunt identice.

Inseamna ca exista x1 si x2 din multimea A astfel incat f(x1)=f(x2)

Acesta este hash collision.

Care este problema cu acest lucru ?

Exemplu:

Tu iti criptezi o parola. Parola ta este x , criptata rezulta f(x)=y.

Deci parola ta este x, hash-ul este y.

Eu incerc sa o sparg pentru a castiga acces in site-ul protejat de acea parola.

Pentru ca exista hash collision exista sansa ca eu sa gasesc un x1 ( x1 este diferit de x) din multimea A

care sa indeplineasca conditia f(x1)=y

Asta inseamna ca eu cu acel x1, pot sa intru pe site-ul securizat de tine.

-------------------------------------------------------------------------------------------------------

Si acum ne intoarcem la intrebarea MD5(MD5()) este mai putin sigur decat MD5() ?

Raspunsul evident este NU!

Avem cazul MD5()

Prin MD5

1 => 2

Atacatorul are valoarea 2.

Pentru a se afla 1 facem bruteforce si chiar daca dam de un hash collision, acesta ne ajuta.

Pe noi ne intereseaza ca orice criptam sa dea rezultatul 2.

Avem cazul MD5(MD5())

Prin MD5

1 => 2

2 => 3

Atacatorul are valoarea 3.

Si pentru a castiga acces trebuie sa-l aflam pe 1 sau sa dam de un hash collision din care sa rezulte 2.

El prima oara trebuie sa afle valorile pentru care MD5(x) = 3

Aici hash collision nu ne mai ajuta, chiar ne incurca.

Si de ce:

Atacatorul incercand sa faca bruteforce ajunge la mai multe rezultate (datorita hash collision):

2, 4, 5 si 6

El nu stie care este rezultatul adevarat si astfel trebuie sa le sparga pe toate pentru a ajunge la 1.

DECI: md5(md5()) este mult mai sigur decat md5()

[Guest flama]

./hoolyshit

mi'a luat foarte mult sa urmaresc doar firul la ce ai zis imi aduce aminte de olimpiade oricum foarte buna gandirea si demonstratzia gg daca e proprie

[kw3rln]

frumoase argumente.. bv

[moubik]

este proprie, bineinteles

si am avut treaba cu olimpiadele nationale de info ... mi-au format gandirea

a durat ceva pana a bagat cineva in seama threadu asta.

[dranaxum]

hmm

Nu stiu denumirile standard, eu le spun unidirectionala si bidirectionala.

It's easy: one-way, two-way

Daca criptam 16^32 +1 texte diferite SIGUR avem 2 hash-uri care sunt identice.

Se aplica, cu alte cuvinte, principiul cutiei (anyway e doar ca o completare).

Bravo pt articol, e pe intelesul tuturor (seniori/juniori in acest domeniu).

App. da-mi un pm, daca vrei, cu id-ul tau ca si eu am avut treaba/cred ca o sa mai am cu ONI.

Offtopic: Da, ONI iti formeaza gandirea algoritmica si incepi sa te gandesti si la solutiile optime nu numai la faptul ca ai rezolvat problema. Iar intr-o lume virtuala unde optimizarea incepe sa treaca pe planul doi (vezi necesitatea de multa viteza pt procesor), este nevoie de asa ceva DAR daca nu este combinata si cu lucrul practic : software-uri, aplicatii mici va iesi, parerea mea, un mic(mare) haos.

[vladiii]

Bravo moubik ! Interesanta gandire...

OffTopic: As putea spune ca si matematica dezvolta mult gandirea la problemele de informatica (am avut si sper ca o sa mai am tangente cu ONM, si cand spun tangente, spun medalii).

Bafta!

[em]

Da, inteleg

[michee]

m-am trezit si eu sa bag articolu in seama dupa atata vreme.......

da foarte frumos demonstrat, bv moubik! Mi-a amintit de problemele de combinatorica de prin clasa a11a parca , m-am chinuit putin dar in cele din urma am reusit. O mica adaugare ptr cei care poate nu au inteles

DE CE SUNT 16 ^ 32 REZULTATE care se pot obtine dintr-un md5("de ceva")

Pentru ca avem 16 cifre hexa care se pot "aseza" pe 32 de pozitii.....deci....

16*16*16.........*16(de 32 ori). Combinatorica de baza, clasa a11a(cred).

Daca aveam 10 cifre pe 32 de pozitii ==> 10 ^ 32.

[cryptoforus]

Salut,

Putea fi calculat mai lejer luand in considerare faptul ca un hash md5 este exprimat pe 128 de biti deci 2^128.

Nu pot spune ca exista un motiv matematic pentru care md5(md5) este mai sigur decat o singura trecere prin hash dar exista cateva avantaje practice.

Unul este cel expus de voi cu coliziunile, altul ar fi faptul ca nu prea sunt rainbow tables calculate pentru hashuri, majoritatea sunt pentru parole in clar.

[ÐÒ&]

deasemenea nrul 35 vine de la cele 26 litere ale alfabetului + 9 cifre

o spun ca o completare pentru cei care le este confuz acest articol(care de altfel mi se pare cel mai serios de pe acest site).

deasemenea pt a intelege mai bine ce inseamna hash collision.

o sa fac o analogie cu functia modul

|-2| = 2.

f_modul(-2)=2 dar si f_modul(2) = 2.

asta daca o definim pt tot |R adica toate numerele reale.se intampla ca functia sa nu fie injectiva(adica pt 2 valori din domeniu ne "returneaza" aceasi valoare din "codomeniu").daca i-am restirctiona domeniul pe numere reale atunci ar fi injectiva.

despre chestia cu invers.

de exemplu Xor(sau exclusiv).Ea este ceva de genu

0 0 - 0

0 1 - 1

1 1 - 0

1 0 - 1

puteti cripta ceva cu chestia asta executand operatia pe bitii respectivi..

daca incercam sa o criptam incaodata ajungem la rezultatul initail.

deci de ex de 3 x 5x 7 x un impar de ori.

sper ca v am lamurit cu unele notiuni

de ex avem o cheie standard..un "bit cu care facem operatia de disjunctie pt fiecare cifra"

xor(text) = y.

xor^-1(y) = text.