Crittografia: funzioni hash sotto la lente dei ricercatori

In occasione dell’evento californiano “Crypto 2008”, appena conclusosi, crittografi e crittoanalisti hanno presentato i progressi raggiunti negli attacchi alle funzioni hash.
Ad essere preso di mira è stato, in particolare, lo standard GOST il cui utilizzo è stato reso obbligatorio negli uffici governativi russi. I ricercatori datisi appuntamento a Santa Barbara hanno mostrato il primo attacco pratico utilizzando varianti ridotte dell’algoritmo SHA-1 tali da permettere di risalire alla password partendo dall’hash.

Un team di esperti formato da studiosi austriaci e polacchi hanno scoperto una vulnerabilità insita nella funzione di hash che è stata quindi sfruttata per condurre l’attacco a buon fine. I ricercatori sono riusciti a generare una “collisione” in un tempo 2^23 volte minore rispetto a quanto atteso inizialmente.

Le funzioni hash, a partire da un testo di lunghezza arbitraria, generano una stringa di lunghezza fissa. La trasformazione operata funziona in un solo senso: non è quindi possibile, dalla stringa generata, risalire al testo iniziale.
In certo senso, si può dire che le funzioni hash non impiegano alcuna chiave crittografica.
L’hash rappresenta una sorta di “impronta digitale” (fingerprint) del contenuto di un file ed è solitamente usata per attestare che lo stesso file non sia stato alterato da virus, malware oppure per l’intervento di un malintenzionato. All’”impronta digitale” viene attribuito anche il nome di message digest, checksum o valore di hash.

Molti sistemi operativi ricorrono a funzioni hash per memorizzare in modo sicuro elenchi di password od altre informazioni sensibili.

Le funzioni di hash sono talvolta non ben comprese ed alcune fonti affermano che due file non possano mai avere lo stesso valore di hash (”message digest“). Quest’asserzione, infatti, è falsa. Si consideri una funzione di hash che genera un “message digest” da 128 bit. Ci sono, ovviamente, 2^128 possibili valori di hash. I file che esistono, però, sono certamente ben più di 2^128 (sono considerabili in numero pari all’infinito). Ne consegue che possono esistere file con il medesimo valore di hash.

La difficoltà, quindi, consiste nell’individuare due file con il medesimo valore di hash.
Quando due messaggi producono un identico hash, si parla di “collisione“. La qualità di una funzione di hash è misurata in base alla difficoltà nell’individuazione di due testi che generino una collisione.
Perché un algoritmo di hashing “cada in disgrazia” è sufficiente che un gruppo di crittografi o di esperti informatici riesca a generare una collisione. E’ questo ciò che è accaduto, in passato, per gli algoritmi SNEFRU, MD2, MD4 ed MD5, tutti oggi considerati insicuri.

Nel caso di GOST, tuttavia, non è ancora possibile parlare di un attacco possibile su larga scala poiché sono richieste notevoli risorse computazionali per portarlo a termine.