Hash vulnerabili, ma la firma digitale resta sicura

di Corrado Giustozzi - 09.09.04

La notizia, divulgata a ridosso dello scorso ferragosto, non è giunta al grande pubblico perché troppo tecnica per essere compresa dai giornalisti nostrani, i quali peraltro in quei giorni avevano ben altre cose a cui pensare; ma ha tuttavia messo parecchio in subbuglio il mondo degli “addetti ai lavori”: uno dei mattoni fondamentali della firma digitale, ossia la “funzione hash” MD5, è stata infatti dimostrata “inaffidabile” da un gruppo di ricercatori cinesi. Si tratta di un risultato grave ed importante, anche se non del tutto inatteso, che obbligherà quantomeno a ridefinire alcuni meccanismi operativi dei sistemi di firma digitale attualmente utilizzati in tutto il mondo.

Naturalmente a questo annuncio sono seguiti gli inevitabili commenti catastrofisti da parte dei soliti poco informati che, un po’ costruendo castelli virtuali sui pochissimi dettagli disponibili, ed un po’ facendo allegramente confusione con un differente ancorché contemporaneo annuncio da parte di altri ricercatori, hanno sbrigativamente sentenziato l’ennesimo tracollo dei meccanismi di firma digitale. Ovviamente le cose non stanno così, e l’annuncio dei ricercatori cinesi, pur importante dal punto di vista teorico, non mette tuttavia a repentaglio un bel nulla. Vale comunque la pena di dedicare qualche minuto a chiarire come stanno per davvero le cose.

Le funzioni hash

Ogni sistema di firma digitale, come noto, è composto di due “mattoni” essenziali: un’infrastruttura di crittografia a chiave pubblica ed una funzione hash. Quest’ultima consiste in una particolare trasformazione matematica che, applicata al documento da firmare, ne genera la cosiddetta impronta: ossia un “riassunto” costituito da un numero assai ridotto (e costante) di bit, che rappresenta univocamente il documento di partenza. È proprio questa “impronta”, come più volte abbiamo avuto modo di illustrare in passato, che viene cifrata con la chiave privata del firmatario per produrre quella che si definisce la firma digitale associata al documento di origine.

Bene. Affinché il tutto funzioni realmente, e la firma digitale risultante possieda effettivamente quelle caratteristiche che le sono richieste per avere piena validità legale, è necessario che la funzione hash utilizzata goda di alcune importanti proprietà. In parole semplici, senza scomodare definizioni matematiche formali, possiamo dire che una buona funzione hash deve essere “non invertibile” e “priva di collisioni”. La prima proprietà significa semplicemente che data un’impronta (ossia un hash di un documento) non deve essere possibile ricavare il documento da cui essa deriva; la seconda significa che non deve essere possibile trovare due documenti diversi che producano la medesima impronta.

Va chiarito subito che queste auspicate “impossibilità” devono intendersi in senso pratico e non teorico. Le impronte sono infatti costituite da un numero finito di bit, e dunque sono anch’esse in numero finito, mentre i possibili documenti che si possono teoricamente produrre sono in numero infinito; dunque è fisicamente impossibile “mappare” un numero infinito di documenti su un numero finito di impronte senza avere associazioni multiple (o, come si dice tecnicamente, “collisioni”). Tuttavia è possibile scegliere adeguatamente le cose in modo che il numero di possibili impronte sia estremamente elevato, e dunque la probabilità di una collisione, voluta o casuale, sia così ridotta da diventare del tutto trascurabile.

Le funzioni hash che si utilizzano nella pratica sono tutte di questo tipo. Esse producono solitamente un’impronta di 160 bit, e dunque sono in grado di discriminare fra 2¹⁶⁰ documenti; e questo è un numero incredibilmente grande, che si scrive come un 1 seguito da 48 zeri. Per avere un’idea di cosa ciò significhi basti dire che se nella nostra Galassia vi fossero cento miliardi di pianeti abitati, ciascuno con dieci miliardi di abitanti, ed ogni abitante producesse un miliardo di documenti al secondo, per esaurire il conteggio occorrerebbe comunque un tempo superiore all’età stimata del nostro Universo!

Naturalmente però non basta che la funzione produca un valore di questa lunghezza, occorre anche che essa effettivamente generi valori diversissimi tra loro al variare del documento in ingresso, e soprattutto che tali valori non siano “facilmente” riconducibili al documento di partenza. In pratica la funzione deve essere tale da far risultare “praticamente impossibile” sia creare ad arte un documento che produca proprio un determinato hash noto a priori, sia creare ad arte due documenti diversi che producano lo stesso hash (collisione). Se così non fosse, le conseguenze sarebbero davvero molto gravi.

Il problema delle collisioni

Se infatti fosse possibile trovare facilmente collisioni nella funzione hash utilizzata in un dato sistema di firma digitale, allora un malintenzionato potrebbe “falsificare” un documento mantenendone apparentemente valida la firma, e per di più questa truffa non sarebbe rivelabile né tantomeno dimostrabile. Inutile dire che ciò, ovviamente, minerebbe alla base tutto il meccanismo della firma digitale. Vediamo come.

Supponiamo dunque che l’onesta Alice debba cento euro al disonesto Bob, e acconsenta a firmare digitalmente una ricevuta che attesti il suo debito. Bob, che sa come trovare collisioni nella funzione hash utilizzata nel sistema di firma digitale da essi prescelto, prepara i seguenti due documenti: nel primo scrive “Io Alice devo 100€ a Bob” e nel secondo scrive “Io Alice devo 10.000€ a Bob”. Dopodiché modifica ad arte i due documenti, ad esempio apportando adeguate variazioni nella formattazione o aggiungendo opportunamente del testo, in maniera tale che essi producano la stessa impronta.
A questo punto Bob consegna ad Alice il primo documento, quello veritiero, ed Alice dopo averlo esaminato lo firma volentieri. Ma Bob, non appena entrato in possesso della firma di Alice, si reca da un giudice e gli chiede di emettere un’ingiunzione di pagamento nei confronti di Alice per la cifra di diecimila euro, portando a riprova della sua richiesta il secondo documento e la firma di Alice relativa al primo documento.

Il giudice, per verificare la veridicità dell’affermazione di Bob, non fa altro che controllare la validità della firma digitale di Alice: egli dunque decifra tale firma con la chiave pubblica di Alice, ottenendo l’impronta del documento originario; quindi calcola ex novo l’impronta del documento presentato da Bob; ed infine confronta le due impronte così ottenute. Esse ovviamente coincidono, quindi il giudice deve necessariamente concludere che il documento di Bob è autentico e dare così credito alla tesi da egli falsamente sostenuta.
Grazie alla collisione, dunque, Bob ha eluso il meccanismo di sicurezza della firma digitale riuscendo a perpetrare una truffa perfetta ai danni di Alice.

Funzioni senza collisioni?

Per scongiurare questo rischio, le funzioni hash solitamente utilizzate nella pratica sono accuratamente progettate e faticosamente controllate affinché risultino quanto più possibile prive di collisioni. Il che, attenzione, non significa che non ne possano produrre in assoluto: ma solo che la probabilità che ciò avvenga per caso sia infinitesimale, e che inoltre risulti estremamente difficile produrre collisioni in modo intenzionale.

Ciò che alcuni ricercatori cinesi hanno mostrato questa estate, in una delle sessioni informali tenute nell’ambito della conferenza CRYPTO ’04, è di possedere un metodo generale per generare facilmente collisioni in alcune fra le più note e diffuse funzioni hash, in particolare quelle denominate MD5 e RIPEMD. E’ importante sottolineare subito che entrambe queste funzioni erano già da tempo, per così dire, sul banco degli imputati: infatti già da diversi anni altri ricercatori avevano pubblicato dei lavori di analisi teorica che gettavano seri dubbi sull’affidabilità di tali funzioni, pur senza dimostrare in modo certo la loro effettiva debolezza. Inoltre la scarsa lunghezza dell’impronta da esse generata (128 bit per entrambe) era già da parecchio tempo giudicata insufficiente a prevenire efficacemente quegli attacchi “a forza bruta” resi ormai possibili dalle enormi potenze di calcolo dei moderni computer. I cinesi dunque non hanno fatto altro che produrre una prova pratica ed incontrovertibile di quanto già si sospettava, peraltro senza fornire alcuna descrizione del metodo di attacco da essi sviluppato.

Sul piano pratico l’annuncio dei cinesi non cambia molto lo stato delle cose. La funzione MD5 infatti, pur essendo da anni uno standard Internet (RFC1321) era già da tempo “sconsigliata”; essa dunque, benché ancora largamente diffusa ed utilizzata in molti ambiti, non viene praticamente più impiegata in applicazioni realmente critiche. Per la funzione RIPEMD le cose stanno ancora meglio: essa infatti, a seguito della scoperta di alcune debolezze teoriche, era già stata ufficialmente abolita e sostituita, sin dal 1996, con la più evoluta e robusta RIPEMD-160 la quale utilizza una struttura matematica più robusta ed inoltre produce un’impronta dalla lunghezza di 160 bit anziché 128.

La sicurezza della firma digitale non è a rischio

Per quanto riguarda il paventato rischio che i sistemi di firma digitale possano “crollare” a seguito della scoperta dei ricercatori cinesi, dunque, non c’è proprio alcuna preoccupazione. Il loro attacco infatti, seppur rilevante sul piano teorico, riguarda funzioni hash obsolete o comunque non utilizzate nella pratica in applicazioni sensibili. Esso inoltre non sembra essere facilmente estensibile alle funzioni hash realmente utilizzate, le quali si basano su strutture matematiche differenti e verosimilmente più robuste.

In particolare vale la pena di ricordare che la legge italiana ammette come valide solo le firme che utilizzano le funzioni hash SHA-1 e RIPEMD-160. Si tratta di due funzioni note e studiate da tempo, considerate molto robuste e caratterizzate entrambe da un’impronta di 160 bit. RIPEMD-160, come detto poc’anzi, è nata proprio per risolvere alcune debolezze teoriche identificate nella sua prima definizione; essa, per la cronaca, è anche uno standard europeo essendo stata appositamente sviluppata nell’ambito del progetto RIPE (RACE Integrity Primitives Evaluation) dell’Unione Europea. Altrettanto affidabile appare anche l’altra funzione, sviluppata nientemeno che dalla famosa/famigerata NSA per divenire uno standard federale statunitense (la sigla sta infatti per Secure Hash Standard); anch’essa tra l’altro nasce come miglioramento di una versione precedente, detta SHA o SHA-0, di cui corregge una vulnerabilità teorica la cui natura non è peraltro mai stata divulgata al pubblico.

Come se ciò non bastasse, va infine sottolineato che il metodo di generazione delle collisioni messo a punto dai ricercatori cinesi non potrebbe comunque portare a truffe come quella delineata in precedenza: esso infatti non consente affatto di produrre un documento di senso compiuto avente un hash desiderato, che è ciò che serve per “falsificare” una firma. Al contrario, esso permette solo di generare simultaneamente una coppia di documenti “privi di senso” (ossia costituiti da sequenze caotiche di bit) e per di più assai simili tra loro (con soli pochi bit di differenza situati in posizioni critiche predeterminate), i quali producono sì un medesimo hash, il quale però non può in alcun modo essere scelto a priori. Ciò conferma ancora una volta come la scoperta dei ricercatori cinesi, pur assumendo un grande valore sul piano della teoria, non abbia praticamente quasi alcuna rilevanza su quello della pratica.

Certo non bisogna commettere l’errore di abbassare la guardia e riposare sugli allori, crogiolandosi in un falso senso di sicurezza. Il risultato dei cinesi ha infatti dimostrato che la struttura matematica di MD5 (e di molte altre funzioni hash ad essa simili) è intrinsecamente debole, e di questo si deve tenere conto nella progettazione delle nuove e future funzioni hash. Inoltre altri risultati, presentati quasi contemporaneamente da ricercatori israeliani e francesi, hanno dimostrato l’esistenza pratica di collisioni in SHA-0 (che peraltro già si sapeva essere teoricamente debole); e benché tale metodo di attacco non sembri in alcun modo applicabile a SHA-1, purtuttavia induce a prendere alcune cautele. Ad esempio i tempi sembrano maturi affinché, sfruttando tutte le conoscenze teoriche ottenute in questi ultimi anni, si possa pensare alla definizione di una nuova funzione hash standard robusta ed efficace, che possa durare almeno per un decennio. Ma certamente non c’è urgenza di farlo: a meno di improvvisi ed inattesi sviluppi dell’analisi teorica, infatti, le funzioni hash attualmente in uso sembrano sufficientemente robuste da poter garantire la sicurezza pratica dei meccanismi di firma digitale ancora per diversi anni.