Construcție Merkle-Damgård

În criptografie , construcția Merkle-Damgård este o metodă de construire a funcțiilor hash criptografice rezistente la coliziune utilizând funcții de compresie unidirecționale . Această construcție specială a fost utilizată în implementarea multor algoritmi hash, cum ar fi MD5 , SHA1 și SHA2 .

Construcția Merkle - Damgård a fost descrisă în teza de doctorat a lui Ralph Merkle din 1979. Ralph Merkle și Ivan Damgård au demonstrat că, dacă se folosește o schemă de umplere adecvată și funcția de compresie este rezistentă la coliziune , atunci și funcția hash va fi rezistentă.

Funcția hash Merkle-Damgård aplică inițial o funcție de umplere conformă cu MD pentru a crea o intrare a cărei dimensiune este un număr fix (exemplu: 512 sau 1024). Acest lucru se datorează faptului că funcțiile de compresie nu pot gestiona intrări de dimensiuni arbitrare. Funcția hash împarte rezultatul în blocuri de dimensiuni fixe și le procesează pe rând cu funcția de compresie, combinând de fiecare dată intrarea cu ieșirea blocului anterior. Pentru ca construcția să sune în siguranță, Merkle și Damgård au propus să umple mesajele cu o căptușeală care codifică lungimea mesajului original. Acest pas se numește Merkle - Damgård lungime de umplere sau armare.

Diagrama care arată clădirea Merkle - Damgård

În model, funcția de compresie unidirecțională este numită $f$ ${\ displaystyle f}$ $f$ , se ocupă cu transformarea a două intrări de lungime fixă într-o ieșire de aceeași dimensiune ca intrările de pornire. Algoritmul începe cu o valoare inițială fixă, numită vectorul de inițializare (VI). Pentru fiecare bloc al mesajului, funcția de compresie $f$ ${\ displaystyle f}$ $f$ preia rezultatul obținut până acum și îl combină cu mesajul menționat anterior producând un rezultat intermediar. În cele din urmă, ultimul bloc este umplut cu „zerouri” și cu biți care reprezintă lungimea întregului mesaj.

Pentru a consolida hashul în continuare, rezultatul final este, în unele cazuri, alimentat printr-o funcție de finalizare. Funcția de finalizare poate avea mai multe scopuri, cum ar fi comprimarea unei stări interne mai mari (ultimul rezultat) într-o ieșire mai mică sau pentru a asigura un efect de amestecare mai bun în biții de sumă hash. Funcția de finalizare este adesea construită folosind funcția de compresie.

Caracteristici de securitate

Popularitatea acestei construcții se datorează faptului (dovedit de Merkle și Damgård ) că dacă funcția de compresie unidirecțională $f$ ${\ displaystyle f}$ $f$ este rezistent la coliziune , deci funcția hash construită folosind acel model va fi și ea. Din păcate, această construcție posedă și proprietăți nedorite:

Atacurile la a doua pre-imagine împotriva mesajelor mari sunt mai eficiente decât cele cu forță brută.
Multicolisiunile (multe mesaje cu același hash) pot fi găsite cu puțin mai multă muncă decât coliziuni simple.
„ Atacurile de pășunat ”, care combină construcția în cascadă pentru căutarea multicoliziunilor cu coliziunile găsite într-un prefix dat. Acest lucru vă permite să creați documente care se ciocnesc.
Extensie de lungime : dat hash $H(X)$ ${\ displaystyle H (X)}$ $H (X)$ a unei intrări necunoscute $X$ ${\ displaystyle X}$ $X$ este ușor să găsești valoarea $H({\textrm {pad}}(X)\parallel Y)$ ${\ displaystyle H ({\ textrm {pad}} (X) \ parallel Y)}$ ${\ displaystyle H ({\ textrm {pad}} (X) \ parallel Y)}$ , unde este ${\textrm {pad}}$ ${\ displaystyle {\ textrm {pad}}}$ ${\ displaystyle {\ textrm {pad}}}$ este funcția de umplere hash. Apoi este posibil să găsiți hashurile intrărilor legate de $X$ ${\ displaystyle X}$ $X$ deși acesta din urmă rămâne necunoscut. Atacurile de extensie de lungime au fost folosite pentru a ataca unele scheme de autentificare a unor servicii comerciale celebre, cum ar fi cel folosit de Flickr .

Portal de criptografie

Portal de securitate IT