Hash sempre più vulnerabili, ma la firma digitale non è a rischio

di Corrado Giustozzi - 07.03.02

Solo sei mesi fa commentavamo su queste colonne l'importante risultato di un gruppo di ricercatori cinesi che aveva dimostrato la vulnerabilità della venerabile funzione hash denominata MD5 (si veda Hash vulnerabili, ma la firma digitale resta sicura), e di nuovo urge tornare sull'argomento a causa di un recente annuncio che si prospetta ancor più significativo: la scoperta che anche la funzione SHA-1, sinora ritenuta piuttosto robusta, soffre invece di vulnerabilità che rendono assai più facile del previsto la scoperta di collisioni al suo interno.

L'annuncio è stato fatto da un gruppo di ricercatori cinesi che comprende alcuni di coloro che avevano a suo tempo scoperto la vulnerabilità di MD5, e come già avvenuto l'altra volta è stato accompagnato da un esempio pratico di collisione ma non dalla spiegazione del metodo impiegato per ottenerla. Le scarne note che accompagnano il comunicato, tuttavia, fanno riferimento alla scoperta di un metodo di carattere generale, basato sui risultati ottenuti in precedenza non solo dal gruppo in questione ma anche da vari altri ricercatori impegnati nella crittanalisi delle funzioni hash.

La notizia di questa scoperta ha fatto rapidamente il giro del mondo, suscitando reazioni moderatamente preoccupate nella comunità di addetti ai lavori; è poi finita, di seconda o terza mano, su alcuni media che l'hanno distorta e divulgata coi soliti toni catastrofisti. Il fatto è che, a differenza di MD5 che già da anni era sospettato di essere vulnerabile, SHA-1 veniva considerato ancora sufficientemente robusto; inoltre, al contrario di MD5, SHA-1 è un componente chiave di praticamente tutti i sistemi di firma digitale "forte", ossia quelli aventi valore legale, compreso quello italiano.

L'annuncio di una sua vulnerabilità sembra dunque minare alla base la validità dell'intera costruzione della firma digitale, gettando l'ennesimo sospetto su una tecnologia già assai bersagliata e criticata da più parti. Ancora una volta, dunque, è il caso di cercare di fare un po' di chiarezza sulla reale portata dell'annuncio dei ricercatori cinesi: e lo faremo valutandone separatamente l'indubbia importanza sul piano teorico e la sua tutto sommato scarsa (per ora!) ricaduta su quello pratico.

Il rischio di collisione

Nell'articolo citato in precedenza avevamo già avuto l'occasione di descrivere in sufficiente dettaglio l'importanza delle funzioni hash all'interno dei sistemi di firma digitale, illustrando anche il concetto di collisione e spiegando perché l'eventuale possibilità di generare collisioni a piacimento renderebbe totalmente inefficace, anche da un punto di vista legale, il meccanismo di firma digitale così com'è attualmente adottato in tutto il mondo. Evitiamo dunque di ripetere qui tali concetti, rimandando gli interessati all'articolo in questione. Oggi ci soffermeremo invece maggiormente sulla questione della probabilità di collisione, che costituisce il punto principale di tutte le discussioni in merito alla robustezza o meno delle varie funzioni hash e di SHA-1 in particolare.

Contrariamente a quanto spesso ritengono i profani, le funzioni hash non sono in grado di "non avere" collisioni in senso generale: ciò è anzi del tutto impossibile da ottenere! Esse invece sono costruite per minimizzare la probabilità che si verifichino delle collisioni, sia in modo casuale che specialmente in modo intenzionale. La differenza è sottile ma importantissima, e non solo sul piano teorico ma soprattutto su quello pratico.

Vediamo innanzitutto perché non può esistere una funzione hash "perfetta", ossia del tutto priva di collisioni. Per farlo sfrutteremo quello che alcuni qui da noi chiamano "teorema dei cassetti", e gli anglosassoni chiamano invece "pigeonhole principle" ossia "principio delle cassettine per piccioni". Supponete di avere N cassettine, tutte vuote, e di disporre di P piccioni che dovete inserirvi dentro come più vi piace: l'unica condizione cui dovete sottostare è che in ogni cassettina vi può stare al massimo un piccione. È ovvio che potrete riuscire nel vostro compito solo se P≤N, ossia se i piccioni sono in numero inferiore o al più uguale a quello delle cassettine; in caso contrario, nonostante tutti i vostri sforzi di riorganizzare le cose, ci sarà sempre almeno una cassettina che conterrà più di un piccione. Si tratta di un principio talmente evidente e banale da sembrare inutile anche il solo parlarne, ma è molto potente e costituisce il fondamento di molti dei ragionamenti che faremo.

Ebbene, nel caso delle funzioni hash i piccioni sono tutti i possibili input (ossia tutti i possibili documenti) mentre le cassettine sono tutti i possibili output, ossia i valori che la funzione in questione può fornire a fronte dei vari possibili input. Ricordando che una funzione hash produce in uscita una stringa di lunghezza fissa e predeterminata (20 byte nel caso di SHA-1), si vede subito che il numero di cassettine a nostra disposizione, per quanto grande, è tuttavia finito: per la precisione, nel caso di SHA-1, esse sono 2¹⁶⁰ che in notazione ordinaria si scrive come un 1 seguito da 48 zeri! Quanti sono invece i piccioni, ossia i possibili documenti che possiamo dare in ingresso alla nostra funzione? Basta poco per convincersi che sono in numero infinito: infatti, se non poniamo un limite alla lunghezza di un documento, ogni possibile combinazione di byte può essere considerata tale e dunque costituire un potenziale e lecito input per la nostra funzione hash. Siccome un numero infinito è senz'altro maggiore di un numero finito, per quanto grande possa essere quest'ultimo, per il principio dei cassetti ne consegue che nessuna funzione hash potrà mai riuscire ad infilare infiniti piccioni in un numero finito di cassettine senza che in qualcuna di esse finiscano due o più ospiti, ossia senza ottenere collisioni. Ciò equivale a dire che non possono esistere funzioni hash "teoricamente perfette".

Sul piano pratico, tuttavia, le cose sono molto più abbordabili. Infatti il numero di possibili cassettine a nostra disposizione è talmente alto che risulta estremamente improbabile che due piccioni qualsiasi vadano a finire per caso nella stessa cassettina. Quanto improbabile? Si può facilmente calcolare. La teoria ci dice che la probabilità che avvenga una collisione per caso è proporzionale alla radice quadrata del numero di cassettine. Ossia, se avete cento cassettine e iniziate a lanciare contro di esse degli oggetti in modo puramente casuale, in media ci vorranno solo dieci lanci perché si verifichi una collisione, ossia accada che l'oggetto appena lanciato finisca in una cassettina già occupata da un oggetto lanciato in precedenza.

È un valore molto basso, tanto che il principio matematico sotteso a tale risultato viene generalmente chiamato paradosso in quanto dà adito a risultati che sembrano contravvenire il buon senso (ne è un esempio il famoso "paradosso del compleanno"). Nel caso di SHA-1, dunque, la probabilità che due messaggi presi a caso diano lo stesso hash è di una su 2⁸⁰; detto in altre parole, in media è necessario lanciare 2⁸⁰ piccioni (questo numero si scrive come 1 seguito da 24 zeri) prima che due di essi capitino per caso nella stessa cassettina. Sembra dunque che ci sia margine a sufficienza per stare tranquilli: se infatti tutta la popolazione della terra si mettesse a generare documenti in numero di mille al secondo, lavorando per ventiquattr'ore al giorno durante tutto l'anno senza interruzioni, in media ci vorrebbero più di seimila anni di tentativi continuati per vedere la prima collisione!

Bene, questo numero di 2⁸⁰ è la misura teorica del numero di tentativi che servono per forzare SHA-1 mediante un attacco a forza bruta, ossia svolto appunto provando sistematicamente tutte le possibili combinazioni di input fino ad incappare fortuitamente in una collisione. In qualche modo dunque esso ci dà l'idea della robustezza di SHA-1, ossia dello sforzo computazionale che occorre fare per trovare una collisione. Quello che hanno dimostrato i cinesi è che, nel caso di SHA-1, la robustezza effettiva dell'algoritmo non coincide, come invece si pensava, con quella teorica ma è assai più ridotta: in particolare è possibile ottenere una collisione dopo "solo" 2⁶⁹ tentativi. Ho scritto "solo" tra virgolette perché si tratta di un numero ancora molto grande: si scrive infatti come 5 seguito da venti zeri!

Tuttavia esso rappresenta un miglioramento di oltre duemila volte nella capacità di attacco verso SHA-1, il che costituisce un risultato tanto importante quanto inaspettato. Oggi come oggi 2⁶⁹ operazioni di hash sono tante anche per un supercomputer, il quale potrebbe impiegare mesi o anni di calcolo per svolgerle; ma considerando la legge di Moore, secondo cui a parità di costo dell'hardware la potenza di calcolo raddoppia ogni 18 mesi, è ipotizzabile che da qui a pochi anni risulti tecnicamente possibile ed economicamente conveniente costruire un supercomputer specializzato in grado di generare collisioni in tempi ragionevoli, dell'ordine cioè dei giorni, il che renderebbe davvero inutilizzabile SHA-1 come funzione hash per la firma digitale.

La portata pratica

Ma lasciamo adesso la teoria e passiamo alla pratica. Tutto ciò che abbiamo visto sinora, per quanto importantissimo in linea di principio, è tuttavia ancora ben lontano dal rappresentare una reale e soprattutto immediata minaccia agli attuali sistemi di firma digitale. Se anche le cose stessero come le abbiamo viste, infatti, la minaccia rimane comunque ancora al di là da venire: c'è probabilmente tutto il tempo di adottare un algoritmo di hash più robusto di SHA-1 prima che questo possa essere considerato realmente compromesso. Tra l'altro esistono già possibili candidati: l'algoritmo europeo RIPEMD-160, ad esempio, è ancora totalmente immune da attacchi noti ed in più è già tecnicamente previsto e legalmente valido all'interno della normativa italiana.

Inoltre il NIST (National Institute of Science and Technology) americano sta già da qualche tempo valutando alcune versioni estese di SHA-1, denominate SHA-256 e SHA-512, che non dovrebbero soffrire delle vulnerabilità identificate in SHA-1.
In più la teoria ci viene una volta tanto in aiuto grazie ad un ordine diverso di considerazioni, che mitigano l'impatto della scoperta dei cinesi. Tutto ciò che essi hanno dimostrato, infatti, è di aver scoperto un metodo efficiente per trovare contemporaneamente due messaggi, M₁ e M₂, che collidono generando lo stesso hash. Ma questo non è generalmente ciò che serve per sovvertire il meccanismo di firma digitale: un malintenzionato infatti ha bisogno di trovare un messaggio M che generi un hash prefissato, ossia che collida nei confronti di un messaggio già esistente e dotato di un hash ben preciso.

E questo, fortunatamente, è un compito molto più difficile rispetto all'altro! La teoria ci dice infatti che in questo caso il numero di tentativi è proporzionale non alla radice quadrata ma alla metà del numero di possibili valori, il che riporta la questione grosso modo alle condizioni iniziali. Certo, nessuno ci dice che il metodo di analisi sviluppato dai ricercatori cinesi non consenta in qualche modo di semplificare anche questo diverso tipo di ricerca: ma almeno per il momento loro non ne hanno fatto menzione, e comunque anche se così fosse la difficoltà computazionale dell'attacco rimarrebbe sempre sufficientemente elevata sia in termini relativi che soprattutto in termini assoluti.

Adelante Pedro, ma con giudizio.

Che conclusioni si possono trarre da tutte queste considerazioni? Per dirla con le efficaci parole di un ricercatore americano: è scattato un allarme antincendio, ed anche se non si vede fumo e non si sente odore di bruciato conviene tuttavia avviarsi, con calma e ordine, verso l'uscita di sicurezza. Potrebbe essere un falso allarme, comunque non conviene rischiare; d'altronde non c'è alcun segno di reale ed imminente emergenza, e dunque non è necessario precipitarsi in una disordinata fuga per la salvezza.

Diciamo dunque che la scoperta dei ricercatori cinesi non ha fatto altro che accorciare i tempi di un processo che comunque era già delineato, quello di un passaggio verso funzioni hash più robuste di quelle attualmente in uso. Va considerato infatti che la teoria delle funzioni hash è relativamente recente, e gli studi degli ultimi anni avevano già portato in luce diverse vulnerabilità concettuali in molte fra le prime funzioni ad essere state identificate; l'esperienza recente, arricchita anche dal contributo che vi daranno i cinesi quando pubblicheranno i dettagli del loro metodo, consentirà senz'altro ai ricercatori di definire funzioni hash più robuste ed efficaci di quelle attuali.

Nel frattempo, a meno di nuovi ed al momento imprevedibili progressi sul piano teorico, SHA-1 rimarrà ancora per qualche tempo sufficientemente robusto per la maggior parte degli utilizzi pratici cui è destinato.