Ok, ho capito. Ecco una mini-spiegazione di come funziona sta roba.
Sia
H una funzione di hash,
m un messaggio e
h un digest (output della funzione di hash). Tra le altre caratteristiche, una funzione di hash
H crittograficamente sicura deve garantire:
- Resistenza alla preimmagine: scelto un digest h dev'essere computazionalmente infattibile trovare un messaggio m tale che H(m)=h. Ovvero se conosco un digest non devo essere in grado di scoprire qual'è un possibile messaggio che l'ha generato.
- Resistenza alla collisione: dev'essere computazionalmente infattibile trovare due messaggi m1 e m2 tali che H(m1)=H(m2). Ovvero anche se mi disinteresso ad attaccare un particolare digest, non devo essere in grado di trovare due messaggi che collidono.
Se md5 non garantisse la resistenza alla preimmagine sarebbe tutto molto semplice: ci inventiamo un digest
h della giusta lunghezza (128 bit = 16 char), creiamo una gif che ci mostra a schermo
h e aggiungiamo dei bit "spazzatura" per fare in modo che
md5(gif)=h. Tutto molto bello, però attualmente non conosciamo attacchi alla preimmagine per md5.
La resistenza alle collisioni è qualcosa di molto più difficile da garantire (ho già parlato del birthday attack:
1,
2) e md5 non è più resistente da questo punto di vista. È proprio questo che hanno fatto: se ne sono infischiati di quale sia l'hash generato, hanno creato delle collisioni e hanno creato l'immagine di conseguenza.
Ma prima di arrivarci ci servono altre due premesse:
- L'algoritmo md5 lavora su blocchi multipli di 512 bit (64 char). Quando applichi md5 ad un messaggio di lunghezza arbitraria, a questo viene aggiunto un padding (qualcosa di poco più complesso di una sfilza di 0) per fare in modo che la lunghezza del messaggio sia di k*64 caratteri.
- Dato un messaggio formato da k*64 caratteri, l'algoritmo md5 lo spezza in k parti da 64 caratteri l'uno, m=(m1,m2,...,mk). L'algoritmo md5 lavora su m1 in modo indipendente, arriva quasi fino in fondo, ma prima di sputare fuori il digest fa uno XOR con m2 e ripete la generazione del digest utilizzando dei registri di stato inizializzati con la roba ottenuta da questo XOR (che ha il compito di mischiare m1 con m2). Long story short: la conseguenza di sta roba che vi ho spiegato alla buona è che se H(m1)=H(m2) allora H(m1+s)=H(m2+s). Questo non è valido in generale, ma è valido per md5 (e anche altre funzioni di hash, tra cui SHA-1).
Come hanno fatto?
- I caratteri possibili sono 16 (0-9 + A-F), quindi crei 16 gif, ognuna con un carattere diverso.
- Prendi le 8 coppie (gif0, gif1), (gif2, gif3), ..., (gifE, gifF) e per ogni coppia crei una collisione. Ovvero aggiungi dei bit spazzatura ad ogni gif in modo tale da ottenere delle gif modificate (mgif) tali per cui: md5(mgif1)=md5(mgif2), md5(mgif2)=md5(mgif3), ..., md5(mgifE)=md5(mgifF).
- Prendi le 4 coppie (mgif1~mgif2, mgif3~mgif4), (mgif5~mgif6, mgif7~mgif8), (mgif9~mgifA, mgifB~mgifC), (mgifC~mgifD, mgifE~mgifF) e per ogni coppia crei una collisione.
- Prendi le 2 coppie (mgif1~mgif2~mgif3~mgif4, mgif5~mgif6~mgif7~mgif8) e (mgif9~mgifA~mgifB~mgifC, mgifC~mgifD~mgifE~mgifF) e per ogni coppia crei una collisione.
- prendi la coppia (mgif1~mgif2~mgif3~mgif4~mgif5~mgif6~mgif7~mgif8, mgif9~mgifA~mgifB~mgifC~mgifC~mgifD~mgifE~mgifF) e crei una collisione.
- Hai una 16 way collision: 16 gif diverse che sputano fuori lo stesso digest md5. Calcoli l'hash md5(mgif1+mgif2+...+mgifE+mgifF) e componi la gif che rispecchia il digest ottenuto. Non sei tu a scegliere cosa mostrare, ma ti adegui a quello che md5 ti mostra.
Note:
- I vari mgif si evolvono ad ogni passaggio, vedetela come mgif += nuova_spazzatura. Non ho voluto appesantire troppo il messaggio, ma l'mgif2 che vedete al punto 2 è ovviamente diverso dall'mgif2 che vedete al punto 6.
- Quando dico cose tipo mgif1~mgif2 non intendo dire che sono uguali, ma che sono equivalenti: non importa quale dei due prendi, la spazzatura che crei per uno va bene anche per l'altro.
- Puoi aggiungere spazzatura al formato gif, perché questo formato permette di includere dei comment extensions block, con altri formati questa "magia" potrebbe essere impossibile.
- Il fatto che appaia un'animazione è dovuto al formato gif, da quel che ho capito la ottieni gratuitamente. Quasi come se fosse un effetto collaterale.
Tutto questo è applicabile anche a SHA-1, tuttavia:
- L'attacco mostrato da Google è chosen-preifx: ti trovano una collisione a patto che i messaggi siano adeguatamente simili (hanno sfruttato il PDF header), non è detto che gif ti permetta di farlo (ho troppo sonno per documentarmi adesso).
- Google ha stimato che per trovare una collisione ci vogliono: 6,500 years of single-CPU computations and 110 years of single-GPU computations (link). Per md5 ci vogliono 30 secondi con l'hardware di uno smartphone (anche qui ha stimato google, non è un numero inventato). Qui parliamo di trovare tante collisioni.
Insomma, è ancora troppo presto per sprecare risorse da centinaia di migliaia di dollari per chiedersi se si può fare il giochetto della gif. Quando (e se) i crittografi troveranno un attacco per SHA-1 che sia fattibile anche per "l'hacker di inforge" allora avrà senso parlarne, ma per adesso accontentiamoci di sapere che è fattibile per qualcuno trovare una collisione in SHA-1. Gif o non gif, questo fatto è ben più che sufficiente per farci capire che chi sta ancora usando SHA-1 avrebbe dovuto switchare a SHA-3 già da tempo.
PS.
È tarda notte pure per me e mi sono documentato solo oggi su come funziona sta roba, potrebbero esserci errori un po' ovunque, ma la sostanza dovrebbe essere quella. Ovviamente se c'è qualcosa che non vi torna non fatevi scrupoli a segnalarlo.
