MD5 Considered Harmful Today

Urmăresc de ceva vreme progresul făcut în direcția „spargerii” algoritmului MD5. Și nu o dată m-am contrazis cu oamenii care susțineau că a fost deja spart. De ce? Pentru că „posibilitatea găsirii unor coliziuni random” nu echivalează cu „posibilitatea găsirii unor coliziuni pentru un text dat”, sau (și mai important) cu „posibilitatea realizării unui atac pe baza acestor coliziuni”.

Ei bine, iată că a fost făcut și acest ultim pas. Astăzi a fost anunțat ceea ce este (din câte știu eu) primul atac „real-world” bazat pe vulnerabilitățile MD5. Un grup de cercetători au reușit să obțină un certificat „fals”, care apare în browsere ca fiind emis de un CA comercial. Ca urmare, certificatul este recunoscut și acceptat ca valid de către browser-ele web.

Mai mult – certificatul emis este un certificat de CA intermediar. Ca urmare, toate certificatele semnate ulterior folosind acest certificat vor fi recunoscute și acceptate ca valide de către browsere!

Da, cercetarea nu s-a bazat numai pe vulnerabilitățile MD5-ului. S-a bazat și pe anumite vulnerabilități din implementarea CA-ului (numere de secvență liniare, moment predictibil al emiterii certificatului, path length lipsă în CA-ul root, etc). Totuși, faptul că atacul a reușit (timpul necesar pentru calcul fiind de numai câteva zile!!) înseamnă că într-adevăr perioada de utilitate a MD5-ului s-a terminat.

Aș spune că este momentul să ne căutăm alți algoritmi de hashing, dar…. nu prea avem alternative. SHA-1 este mai secure, dar și el are o serie de vulnerabilități (nu de aceeași anvergură, dar vulnerabilități nevertheless). Ca urmare, și el va trebui înlocuit până în 2010 (recomandare NIST).

Cu ce? Încă nu știm. Și eu (ca și mulți alții) consider că soluția cea mai bună ar fi organizarea unei competiții de tipul celei organizate pentru algoritmii de criptare în 1997 (competiție în urma căreia a apărut AES-ul).

Detaliile despre atac le găsiți aici. Credits go to LifeTester, care se pare că în loc să se gândească la anul nou stă și citește despre MD5 pe ‘Net. 🙂

6 Comments »

  1. Vlad Said,

    December 31, 2008 @ 1:06

    Totusi, cred ca solutia md5(md5(something)) este inca valabila, intrucat chiar daca ai facut coliziune pe primul md5, pentru al doilea nu sti nici textul, nici hash-ul

  2. bogd Said,

    December 31, 2008 @ 9:56

    @Vlad: nu, nu este o soluție. A funcționat pentru DES, pentru că la 3DES se foloseau 3 chei diferite. Nu funcționează la algoritmi de hash, pentru că practic întotdeauna când folosești MD5 ȘTII textul original (ideea este tocmai ca ambele părți să calculeze hash-ul pe textul original, și să verifice dacă este același). Ca urmare, poți oricând să calculezi md5(text), și să aplici atacul de mai sus.

    Luăm același exemplu, al certificatului digital. Știu textul certificatului, și pot să generez un alt certificat astfel incat md5(real_cert)==md5(fake_cert). Atunci in mod sigur md5(md5(real_cert))==md5(md5(fake_cert)) – am funcția de hash care primește 2 intrări identice. Game over 🙂

  3. UberGeek » Blog Archive » Hash Competition Said,

    December 31, 2008 @ 11:07

    […] Ei bine, iată că se întâmplă! Concursul este deja deschis, și s-au primit 64 de propuneri. Cel mai probabil vom avea un standard undeva prin 2012. Not a moment too soon, aș putea spune […]

  4. tb Said,

    January 3, 2009 @ 19:16

    salve şi La mulţi ani.
    cine ştie destul de în detaliu ce face şi ştie SHA-1 şi la fel şi SHA-2 ar trebui să cunoască faptul că SHA-x precum şi MD-5 fac parte din acceaşi familie din punct de vedere constructiv.

    Oricum, apropos de contraziceri, (că tot ai tu tendinţa să zici că RSA şi MD5 sigure (cel puţin aveai până de curând)) , uită-te la nsa suite B (http://www.nsa.gov/ia/Industry/crypto_suite_b.cfm) să vezi ce e recomandat pentru criptare, semnătură, hash.
    Criptare – AES
    Schimb de chei – ECDH
    Semnătură – ECDSA
    hash- SHA – 256 şi SHA-384.
    Have fun în lumea asta mirifică

  5. bogd Said,

    January 3, 2009 @ 19:38

    1) Am mai spus-o si eu – SHA-1 are și el vulnerabilitățile lui (deși este „încă secure”). Iar SHA-2 este înrudit cu SHA-1, ca urmare o vulnerabiliate majoră din SHA-1 poate afecta și SHA-2.

    Aș evita totuși formularea „SHA-X”, pentru că ea include și SHA-3, despre care încă nu știm ce va fi exact 🙂

    2) De RSA nu am zis nimic – în afară de „nu cunosc până acum vulnerabilități majore și/sau atacuri reușite la adresa RSA”. Ai vreun contraexemplu?

    3) Din păcate, link-ul respectiv nu specifică _de ce_ s-a preferat ECC față de algoritmii „clasici” cu cheie publică. Spune doar „peste 1024 bits, decât să creștem dimensiunea cheii, preferăm să trecem la ECC”. Any ideas why?

  6. tb Said,

    January 18, 2009 @ 14:40

    Să le luăm pe rând, deci.
    1) cu SHA-X mă refeream la SHA-1 şi SHA-2, dar ai dreptate, formularea ar trebui evitată pentru că induce ambiguitate.
    2) Momentan nu există (din câte ştiu eu) atacuri point-and-click asupra RSA.
    În schimb din ce ştiu, există algoriti din ce în ce mai eficienţi (de la complexitate subexponenţială , îndreptându-se cu paşi mici, dar siguri spre polinomială) de factorizare. Cel mai eficient acum ştiu eu că sunt GNFS (un ciur generalizat). Apoi existenţa algoritmului lui Shor care are complexitate polinomială (dar pe calculatoare cuantice), existenţa testului de primalitate AKS care are complexitate polinomială (pe calculatoarele actuale) nu fac să întărească încrederea în sistemul RSA.

    Alte indicii în privinţa faptului că RSA nu mai e ce a fost ar fi faptul că RSA factoring challenge nu mai e activă, faptul că cei de la NSA au exclus RSA din toate suitele de algoritmi pentru documente de tip top secret la nivel guvernamental.

    Cam asta e ce se ştie. În plus nu uita că serviciile de securitate din întreaga lume dezvoltă algoritmi şi tehnici care nu sunt publicate. Că or fii mai bune sau mai rele nu ştiu, dar există probabilitatea ca ei să fi dezvoltat algoritmi cel puţin la fel de buni ca cei publici.

    Nu m-aş mira ca folosind tehnici gen programare asistată de GPU (vezi CUDA) cu o investiţie minimă de vreo 10k-20k dacă eşti destul de competent şi motivat să se poată executa un atac cu succes asupra RSA. Şi să ne fie cu iertare, dar 10-20k comparativ cu profitul obţinut nu e mare lucru.

    3) Povestea cu ECC e lungă şi complicată (din punct de vedere matematic).
    O să încerc mai jos să enumăr diferenţele şi avantajele ECC vs RSA şi DSA.
    Pe scurt, RSA sau ElGamal (pe care e bazat DSA-ul) lucrează pe singur corp (Galois ).
    În cazul ECC, pentru fiecare comunicare securizată (semnătură, criptare) se poate folosi o altă curbă. Avantajul constă că în momentul de faţă s-au găsit vulnerabilităţi doar pentru curbe foarte specifice şi în concluzie, dacă se găseşte o vulnerabilitate pentru o curbă folosită într-un loc, e puţin probabil să se găsească în acelaşi timp şi pentru altă curbă folosită în altă parte.
    Revenind la vulnerabilităţile ştiute, se ştie că există nişte curbe care trebuiesc evitate şi există în momentul de faţă algoritmi eficienţi pentru detectarea acestora rapid şi eficient în momentul generării curbei.
    Ca eficienţă , se presupune că o semnătură ECDSA pe 160 biţi e la fel de sigură ca una DSA pe 1024 biţi. Asta numai ca dimensiune. Dar şi ca eficienţă a calculelor, generarea cheii de semnătură , precum şi operaţiunile de semnare şi verificare a semnăturii, merg mai repede folosind ECDSA.
    Dacă vrei un “de ce ” mult mai detaliat, trebuie intrat mai mult în partea matematică şi necesită ceva mai mult timp.

RSS feed for comments on this post · TrackBack URI

Leave a Comment