Google rompe lo SHA-1

Esistono diversi algoritmi di hashing e, per definizione, questi devono fare una cosa sola: fornendo in ingresso dati di dimensione arbitraria, restituiscono dati di dimensione fissa e valore preciso; questa semplice logica ha permesso di utilizzare algoritmi di questo tipo per diverse cose: dalla verifica di genuinità di un file (avete mai verificato la iso scaricata di una distribuzione?), alla possibilità di verificare l'autenticazione di un utente senza doversi salvare la password, fino alla ricerca di pattern ripetuti nel DNA umano.

Insomma, che sia l'md5, lo sha-1 o lo sha-256 questi algoritmi per funzionare devono garantire due cose: se passo un file ottengo una stringa di caratteri (chiamato hash o checksum):

• Quello stesso file, dato in pasto allo stesso algoritmo, genererà sempre la stessa stringa di caratteri;
• Non esiste alcun altro file che generi la stessa stringa di caratteri

Ora, tra i vari algoritmi, lo SHA-1 è uno dei più conosciuti, anche perchè sono più di 20 anni che è stato pubblicato; certo, oramai è "quasi" in disuso, dopo che nel 2005 alcuni criptoanalisti lo dichiararono non sicuro trovando attacchi di tipo bruteforce (tentando ovvero tutte le possibili combinazioni) in grado di determinare i dati sorgenti di uno specifico hash. Questo ha spinto Mozilla, Microsoft, Google e Apple a definire che entro la fine di quest'anno i loro rispettivi browser non avrebbero più accettato autenticazioni con questo algoritmo.

Ma, in che senso Google ha rotto l'algoritmo? In parole povere, dopo 2 anni di ricerca intensiva (e grazie alla potenza di calcolo a cui pochi hanno accesso) è riuscita a trovare due file PDF differenti che, dati in pasto a quell'algoritmo, generano lo stesso hash.

Il risultato, come accennavamo poco fa, è stato raggiunto anche grazie alla potenza di calcolo che hanno potuto sfruttare i ricercatori:

• Nove quintiglioni (si, avete letto bene, 9.223.372.036.854.775.808) di calcoli di hash SHA-1 in totale
• 6.500 anni di computazione CPU per portare a termine il primo attacco
• 110 anni di computazione GPU per portare a termine il secondo

Il che, se paragonati ai circa 12 milioni di anni di computazione GPU necessaria per portare l'attacco di tipo bruteforce scoperto nel 2005, fa si di poter rompere l'algoritmo 100.000 volte più velocemente.

Insomma, numeri da far girare la testa [cit.]
Per l'analisi completa (con tanto di pdf che causano il problema), vi rimandiamo all'annuncio ufficiale di Google.

Molti hanno discusso su questo, ed essendo questo algoritmo ancora largamente utilizzato nel sistema di versionamento git, ha detto la sua anche il buon Torvalds:

I haven't seen the attack yet, but git doesn't actually just hash the data, it does prepend a type/length field to it. That usually tends to make collision attacks much harder

Non ho ancora visto l'attacco, ma git non esegue l'hash solo dei dati, aggiunge un campo tipo/lunghezza prima dei dati stessi. Questo tendenzialmente rende la realizzazione di attacchi a collisione più difficile

Quindi, possiamo dormire sonni tranquilli? O no?

Leggi il contenuto originale su Mia mamma usa Linux!