SHA-1 è stato seriamente violato. Non una versione a round ridotti. Non una
versione semplificata. Proprio SHA-1.

Il team di ricerca di Xiaoyun Wang, Yiqun Lisa Yin, e Hongbo Yu (per la
maggior parte dell'Università di Shandong in Cina) ha fatto quietamente
circolare uno studio che descrive i loro risultati:

collisioni nello SHA-1 completo in 2^69 operazioni hash, molto meno del
numero di operazioni (2^80) dell'attacco brute-force basate sulla lunghezza
hash.

collisioni in SHA-0 in 2^39 operazioni.

collisioni nello SHA-1 a 58 round in 2^33 operazioni.

Questo attacco va ad aggiungersi ai precedenti attacchi ai danni di SHA-0 e
SHA-1, ed è un risultato di crittanalisi davvero, davvero importante. Il
primo attacco contro SHA-1 più veloce del brute-force.

Lo scorso settembre scrissi di SHA e del bisogno di rimpiazzarlo. A parte i
dettagli del nuovo attacco, ogni cosa che dissi allora è ancora valida. Di
seguito riporterò brani da quell'articolo, integrandoli con nuovo materiale
ove appropriato.

"Le funzioni one-way hash sono un costrutto crittografico utilizzato in
svariate applicazioni. Vengono usate congiuntamente ad algoritmi a chiave
pubblica sia per la crittografia che per le firme digitali. Vengono usate
per verifiche di integrità. Vengono usate nel processo di autenticazione.
Presentano tutta una serie di applicazioni in una grande varietà di
protocolli. Molto più degli algoritmi di crittografia, le funzioni one-way
hash sono i veri "cavalli da lavoro" della crittografia moderna.

Nel 1990 Ron Rivest inventò la funzione hash MD4. Nel 1992 migliorò la
funzione MD4 e sviluppò un'altra funzione hash: MD5. Nel 1993 la National
Security Agency pubblicò una funzione hash molto simile alla MD5, chiamata
SHA (Secure Hash Algorithm). In seguito, nel 1995, riferendosi a una
vulnerabilità appena scoperta e su cui si rifiutò di divulgare informazioni,
la NSA effettuò un cambiamento a SHA. Il nuovo algoritmo fu chiamato SHA-1.
Oggi SHA-1 è la funzione hash più diffusa, e MD5 è ancora usata nelle
applicazioni più vecchie.

Le funzioni one-way hash dovrebbero avere due proprietà. La prima è che sono
a senso unico (one way): questo significa che è semplice prendere un
messaggio e calcolare il valore hash, ma è impossibile prendere un valore
hash e ricreare il messaggio originale (con "impossibile" intendo dire "che
non può essere fatto in un intervallo di tempo ragionevole"). La seconda
proprietà è che sono libere da collisioni. Ciò significa che è impossibile
trovare due messaggi che producano lo stesso identico valore hash. Il
ragionamento crittografico che sta dietro a queste due proprietà è piuttosto
sottile, ed invito i lettori più curiosi ad approfondire l'argomento sul mio
libro "Applied Cryptography".

Rompere una funzione hash significa dimostrare che una di quelle due
proprietà, o entrambe, non sono vere."

Il mese scorso, tre crittografi cinesi hanno dimostrato che SHA-1 non è
esente da collisioni. Ovvero, hanno sviluppato un algoritmo che trova
collisioni più velocemente rispetto al brute force.

SHA-1 produce uno hash a 160 bit, cioè ogni messaggio viene "sminuzzato" in
numeri da 160 bit. Posto che esiste un numero infinito di messaggi che si
combinano ad ogni possibile valore, vi è un numero infinito di collisioni
possibili. Ma dato che il numero di hash possibili è così elevato, le
probabilità di trovarne uno per caso sono talmente basse da essere
trascurabili (una su 2^80, per la precisione). Se si sono "hashati" 2^80
messaggi casuali, se ne troverà una coppia che presenta un hash allo stesso
valore. Questo è il sistema "brute force" (forza bruta) di trovare
collisioni, e dipende unicamente dalla lunghezza del valore hash. "Rompere"
la funzione hash significa essere in grado di trovare collisioni in una
maniera più veloce di questa ed è quello che hanno fatto i matematici
cinesi.

Loro possono trovare collisioni in SHA-1 in calcoli 2^69, circa 2000 volte
più velocemente del metodo brute force. Al momento, con la tecnologia
attuale, siamo al limite estremo di fattibilità. Il confronto tra due immani
calcoli illustra meglio questo punto.

Nel 1999, un gruppo di crittografi costruì un cracker per violare DES. Era
in grado di compiere 2^56 operazioni DES  in 56 ore. Costruire il
dispositivo costò 250.000 dollari, anche se potevano essere realizzati dei
duplicati del costo dell'ordine di 50-75.000 dollari. Estrapolando quella
macchina usando la Legge di Moore, una macchina simile costruita oggi
potrebbe compiere 2^60 operazioni in 56 ore e 2^69 operazioni in tre anni e
un quarto. Oppure, una macchina che venisse a costare 25-38 milioni di
dollari potrebbe svolgere 2^69 operazioni nello stesso intervallo di 56 ore.

Sul lato software, il principale calcolo comparabile è una chiave di ricerca
2^64 condotta da distributed.net e conclusasi nel 2002. Un articolo l'ha
messa in questo modo: "Nel corso della competizione, 331.252 utenti hanno
partecipato mettendo a disposizione i cicli non utilizzati dei propri
processori per scoprire la chiave. Dopo 1757 giorni (4,81 anni), un
partecipante in Giappone ha scoperto la chiave vincente". Secondo la Legge
di Moore, quel calcolo oggi si sarebbe svolto in un quarto del tempo (o
avrebbe richiesto un quarto del numero di computer utilizzati), per cui oggi
un numero di operazioni pari a 2^69 impiegherebbe un tempo otto volte
maggiore, o richiederebbe otto volte il numero di macchine.

"L'importanza di questi risultati dipende da chi siete. Se siete un
crittografo, si tratta di una cosa enorme. Pur non essendo rivoluzionari,
questi risultati rappresentano passi avanti sostanziali in questo campo. Le
tecniche descritte dai ricercatori saranno probabilmente destinate ad avere
altre applicazioni, e di conseguenza sarà meglio essere in grado di
progettare sistemi sicuri. Questo è il modo con cui la scienza crittografica
procede: si impara a ideare nuovi algoritmi rompendo altri algoritmi. In
più, gli algoritmi provenienti dalla NSA vengono considerati una specie di
scienza aliena: giungono da una razza superiore e senza spiegazioni alcune.
Una qualsiasi crittanalisi che ha buon esito contro un algoritmo della NSA è
un dato interessante nell'eterna questione di quanto siano davvero in gamba
là dentro.

Per l'utente medio di Internet queste novità non sono particolarmente
preoccupanti. Nessuno violerà firme digitali né leggerà messaggi cifrati
tanto presto usando queste tecniche. L'universo elettronico non è meno
sicuro di quanto non lo fosse prima di questi annunci.

Ma c'è un vecchio detto all'interno della NSA: 'Gli attacchi diventano ogni
giorno migliori; non peggiorano mai'". Proprio come l'attacco operato questa
settimana si serve di altri studi che hanno descritto attacchi contro
versioni semplificate di SHA-1, SHA-0, MD4 e MD5, altri ricercatori si
serviranno di questi risultati. L'attacco contro SHA-1 continuerà a
migliorare mano a mano che altri lo studieranno e svilupperanno tecniche più
veloci, ottimizzazioni, ecc. e la Legge di Moore andrà avanti, rendendo
anche l'attacco odierno più veloce e raggiungibile.

Jon Callas, CTO di PGP, ha descritto il tutto in modo ancora migliore: "È
tempo di camminare, non di correre, verso le uscite di emergenza. Non si
vede ancora il fumo, ma gli allarmi antincendio sono già stati lanciati". Si
tratta, sostanzialmente, di quel che io sostenevo lo scorso agosto.

"È venuto il momento per tutti di abbandonare SHA-1. Fortunatamente ci sono
delle alternative. Il NIST (National Institute of Standards and Technology)
offre già degli standard per funzioni hash più lunghe e più difficili da
rompere: SHA-224, SHA-256, SHA-384 e SHA-512. Sono già standard governativi
e possono già essere usate. Questo è un ottimo tappabuchi, ma mi piacerebbe
vedere dell'altro.

Mi piacerebbe vedere il NIST indire e orchestrare una competizione mondiale
per la creazione di una nuova funzione hash, così come fecero per fare in
modo che il nuovo algoritmo crittografico AES rimpiazzasse DES. Il NIST
dovrebbe pubblicare una richiesta di algoritmi e condurre una serie di turni
d'analisi, in cui la comunità esamina le varie proposte con lo scopo di
stabilire un nuovo standard.

Moltissime delle funzioni hash che abbiamo, e tutte quelle d'uso più comune,
sono basate sui principi generali di MD4. Abbiamo senza dubbio imparato
moltissime cose sulle funzioni hash negli ultimi dieci anni, e credo che si
possa iniziare ad applicare queste conoscenze per creare qualcosa di ancor
più sicuro."

Le funzioni hash sono le primitive di crittografia meno capite e le tecniche
di hashing sono molto meno sviluppate di quelle di crittografia.
Regolarmente si scoprono risultati sorprendenti nel campo dell'hashing. C'è
un mio studio, scritto insieme a John Kelsey, che descrive un algoritmo per
trovare second preimages con SHA-1 [ una second preimage di un input (s,t) è
una password s' <> s per la quale F(s,t)=F(s',t) ndt ] -- una tecnica che si
generalizza per quasi tutte le altre funzioni hash -- in 2^106 operazioni:
molto meno rispetto alle 2^160 operazioni necessarie per il metodo brute
force. Questo attacco è completamente teorico e neanche lontanamente
pratico, ma dimostra che abbiamo ancora molto da imparare sull'hashing.

È chiaro rileggendo quanto da me scritto lo scorso settembre che mi
aspettavo un risultato come quello odierno, ma non così velocemente e non
certo in maniera così impressionante. I crittografi cinesi meritano grande
stima per il loro lavoro, e dobbiamo metterci al lavoro per sostituire SHA.


Un riassunto dello studio (lo studio completo non è ancora disponibile):


Il mio articolo originario:


Lo standard NIST per SHA-224, SHA-256, SHA-384, e SHA-512:


Il mio studio sulle second-preimages:


Altre news sulla funzione hash:
Due certificati X-509 con identici hash MD5:

Collisioni MD5 più veloci (otto ore su un computer a 1,6 GHz):