Costruzione di Merkle-Damgård

In crittografia, la costruzione di Merkle-Damgård è un metodo per costruire delle funzioni crittografiche di hash resistenti alle collisioni utilizzando delle funzioni a compressione a senso unico. Questa particolare costruzione è stata utilizzata nell'implementazione di molti algoritmi di hash, come ad esempio MD5 e SHA-1.

Storia

La costruzione Merkle–Damgård venne descritta nella tesi di dottorato di Ralph Merkle nel 1979. Successivamente, Ralph Merkle e Ivan Damgård dimostrarono, in modo indipendente, che se viene utilizzato un appropriato schema di padding e la funzione di compressione è resistente alle collisioni, allora anche la funzione di hash è resistente alle collisioni.

Descrizione

La funzione di hash Merkle-Damgård applica, inizialmente, una funzione a riempimento MD-compliant per creare un input la cui dimensione è un numero fisso (esempio: 512 o 1024). Questo avviene perché le funzioni di compressione non sono in grado di gestire input di dimensioni arbitrarie. La funzione di hash, successivamente, suddivide il risultato in blocchi di dimensioni fisse e li processa uno alla volta con la funzione di compressione, ogni volta combinando l'input con l'output del blocco precedente. Per fare in modo che la costruzione risultasse sicura, Merkle e Damgård proposero di riempire i messaggi con un padding che codificasse la lunghezza del messaggio originario. Questo passaggio viene chiamato lunghezza di padding o rafforzamento di Merkle–Damgård.

Schema che raffigura la costruzione Merkle–Damgård

Nel modello, la funzione di compressione unidirezionale è denominata $f$, essa si occupa di trasformare due input di lunghezza fissa in un output della stessa dimensione degli input di partenza. L'algoritmo parte con un valore iniziale fisso, denominato vettore di inizializzazione (VI). Per ogni blocco del messaggio, la funzione di compressione $f$ prende il risultato fino ad ora ottenuto e lo combina con il suddetto messaggio producendo un risultato intermedio. L'ultimo blocco, infine, è riempito con degli "zero" e con dei bit che rappresentano la lunghezza dell'intero messaggio.

Per rafforzare l'hash ulteriormente, il risultato finale viene, in alcuni casi, alimentato attraverso una funzione di finalizzazione. La funzione di finalizzazione può avere molteplici scopi, come ad esempio la compressione di uno stato interno più grande (l'ultimo risultato) in un output più piccolo o per garantire un effetto di mescolamento migliore nei bit della somma di hash. La funzione di finalizzazione è spesso costruita usando la funzione di compressione.

Caratteristiche di sicurezza

La popolarità di questa costruzione è dovuta al fatto (provato da Merkle e Damgård) che se la funzione di compressione unidirezionale $f$ è resistente alle collisioni, allora lo sarà anche la funzione di hash costruita utilizzando tale modello. Sfortunatamente, questa costruzione possiede anche delle proprietà indesiderabili:

• Gli attacchi alla seconda preimmagine contro messaggi di dimensione elevata sono più efficienti di quelli a forza bruta.
• Le multicollisioni (tanti messaggi con il medesimo hash) possono essere trovati con poco lavoro in più rispetto alle semplici collisioni.
• Gli "herding attacks", i quali combinano la costruzione a cascata per la ricerca di multicollisioni con le collisioni trovate in un dato prefisso. Questo permette di costruire documenti collidenti.
• Estensione di lunghezza: dato l'hash $H(X)$ di un input ignoto $X$ è facile trovare il valore $H({\textrm {pad}}(X)\parallel Y)$, dove ${\textrm {pad}}$ è la funzione di padding dell'hash. È quindi possibile trovare gli hash degli input relativi ad $X$ anche se quest'ultimo rimane ignoto. Gli attacchi di estensione di lunghezza sono stati utilizzati per attaccare alcuni schemi di autenticazione di famosi servizi commerciali come, ad esempio, quello utilizzato da Flickr.

Bibliografia

• Daniele Venturi, Crittografia nel Paese delle Meraviglie, collana UNITEXT, Springer Milan, 2012, DOI:10.1007/978-88-470-2481-6, ISBN 978-88-470-2480-9.
• (EN) Ralph Merkle, Secrecy, Authentication, and Public Key Systems (PDF), giugno 1979.
• (EN) Jonathan Katz e Yehuda Lindell, Introduction to modern cryptography, 2ª ed., ISBN 978-1-4665-7026-9, OCLC 893721520.