Le funzioni di hash spiegate

Quando scarichi un software e confronti una checksum, accedi con una password, firmi un documento o aggiungi un blocco a Bitcoin, all'opera c'è una funzione di hash. Trasforma qualsiasi quantità di dati in una breve impronta di dimensione fissa, il digest, in un modo che non si può annullare né falsificare. L'idea è semplice, ma i requisiti di un buon hash sono severi, e due dei più diffusi, MD5 e SHA-1, non li hanno superati.

Due messaggi che differiscono per una lettera entrano in una funzione di hash ed escono come due digest SHA-256 completamente diversi, con i bit invertiti evidenziati in una griglia
Due messaggi che differiscono per una lettera entrano in una funzione di hash ed escono come due digest SHA-256 completamente diversi, con i bit invertiti evidenziati in una griglia

Un'impronta per i dati

Una funzione di hash prende un input di qualsiasi lunghezza e restituisce un digest di lunghezza fissa: 256 bit per SHA-256, scritti come 64 cifre esadecimali. Lo stesso input dà sempre lo stesso digest, quindi il digest può rappresentare i dati. Se due file hanno lo stesso digest SHA-256 puoi essere certo che siano identici, e se un bit di un download si è danneggiato, il suo digest non corrisponde più a quello indicato da chi lo pubblica. Poiché gli input possibili sono molti più dei digest, molti input devono per forza condividere ciascun digest; un buon hash rende semplicemente impossibile trovarne anche uno solo.

Tre promesse

Un hash crittografico fa tre promesse. Resistenza alla preimmagine: dato un digest, non si riesce a trovare un input che lo produca. Resistenza alla seconda preimmagine: dato un input, non si riesce a trovare un altro input con lo stesso digest. Resistenza alle collisioni: non si riesce a trovare nessuna coppia di input con lo stesso digest. Per un hash ideale di n bit gli attacchi migliori consistono nell'indovinare: circa 2ⁿ tentativi per una preimmagine e circa 2ⁿᐟ² per una collisione. Un hash si dice violato quando qualcuno trova un metodo molto più veloce di così.

L'effetto valanga

Cambia un bit dell'input e ogni bit del digest dovrebbe invertirsi con probabilità di un mezzo, indipendentemente dagli altri. Allora una piccola modifica del messaggio produce un digest che sembra del tutto scollegato, e il digest non rivela nulla su quale parte dell'input sia cambiata. SHA-256 ci riesce eseguendo 64 round che ruotano, sommano e combinano le sue otto parole da 32 bit, così che nel giro di pochi round ogni bit dell'input ha influenzato ogni parola. Una semplice somma dei byte, invece, cambia esattamente della stessa quantità di cui è cambiato l'input, e quindi rivela tutto.

Dentro SHA-256

SHA-256 per prima cosa riempie il messaggio: aggiunge un bit 1, degli zeri e la lunghezza del messaggio, finché il totale non è un multiplo di 512 bit. Poi elabora il messaggio 512 bit alla volta. Ogni blocco viene esteso in 64 parole, che vengono mescolate in uno stato di otto parole da 32 bit, partendo da valori fissi ricavati dalle radici quadrate dei primi otto numeri primi. Lo stato dopo l'ultimo blocco è il digest. Questa struttura a catena, che prende il nome da Ralph Merkle e Ivan Damgård, è comune a MD5, SHA-1 e SHA-512; il più recente SHA-3, standardizzato nel 2015, usa una costruzione diversa chiamata spugna.

Ralph Merkle al Singularity Summit del 2007. La costruzione a catena usata da SHA-256 porta il suo nome e quello di Ivan Damgård.
Ralph Merkle al Singularity Summit del 2007. La costruzione a catena usata da SHA-256 porta il suo nome e quello di Ivan Damgård.

L'attacco del compleanno

In un gruppo di 23 persone la probabilità che due compiano gli anni lo stesso giorno supera di poco un mezzo, anche se l'anno ha 365 giorni, perché ciò che conta è il numero di coppie, che cresce con il quadrato della dimensione del gruppo. Le collisioni di un hash seguono la stessa regola. Tra 2ᵏ digest possibili, ci si aspetta una collisione dopo circa √(π/2 · 2ᵏ) input casuali. Per 32 bit sono circa 82.000 input, trovati in un attimo; per 128 bit sono circa 2⁶⁴, alla portata di grandi sforzi di calcolo. Ecco perché i 128 bit di MD5 non sono mai stati generosi, e perché SHA-256 raddoppia la lunghezza per offrire una sicurezza di 128 bit.

MD5 e SHA-1: violati

Ron Rivest progettò MD5 nel 1991, e la NSA progettò SHA-1, pubblicato nel 1995. Nel 2004 Xiaoyun Wang e i suoi colleghi mostrarono come creare rapidamente collisioni MD5, e nel 2008 alcuni ricercatori le usarono per falsificare un certificato di cui i browser web si fidavano. Il software di spionaggio Flame, nel 2012, sfruttò una collisione MD5 per spacciarsi per un aggiornamento Microsoft. SHA-1 cadde nel 2017, quando Google e il CWI Amsterdam pubblicarono due file PDF diversi con lo stesso digest SHA-1, dopo circa 2⁶³ calcoli. Entrambi vanno ancora bene per individuare errori accidentali, ma non per nulla che un attaccante potrebbe prendere di mira.

Dove si usano gli hash

Le firme digitali firmano l'hash di un documento invece del documento stesso. Git identifica ogni file e ogni commit con il suo hash, e i miner di Bitcoin cercano intestazioni di blocco il cui doppio hash SHA-256 inizi con una lunga serie di zeri. I siti web non dovrebbero mai memorizzare le password, ma solo un loro hash; però, poiché le persone scelgono password corte, quell'hash deve essere lento e con salt, con metodi come bcrypt, scrypt o Argon2, così che tirare a indovinare diventi costoso. Anche le checksum come CRC-32, usate nei file ZIP, nelle immagini PNG ed Ethernet, sono hash, progettati per individuare il rumore anziché gli attaccanti.

Provalo tu

Apri il laboratorio delle funzioni di hash per calcolare l'hash del tuo testo con SHA-256, SHA-512, SHA-1, MD5, CRC-32 e una somma dei byte giocattolo. Cambia un carattere e conta i bit invertiti, esegui il test della valanga su mille modifiche di un bit per vedere la curva a campana attorno a metà del digest, e trova vere collisioni sui primi bit di un digest, da 8 a 32, per vedere all'opera l'attacco del compleanno.

Domande frequenti

Calcolare un hash è come cifrare?

No. La cifratura è fatta per essere annullata da chi possiede la chiave; l'hash non ha chiave e nessuno può annullarlo. La cifratura mantiene segreto un messaggio, mentre un hash fornisce solo un'impronta che ti permette di verificare un messaggio che hai già.

Quanto tempo servirebbe per trovare una collisione SHA-256?

Con l'attacco del compleanno, circa 2¹²⁸ hash, un numero di 39 cifre. Anche se tutti i computer della Terra non facessero altro, servirebbe immensamente più tempo dell'età dell'universo. Non si conosce nessuna scorciatoia.

Perché due hash dello stesso testo non sono mai diversi?

Una funzione di hash è deterministica: non ha casualità né chiave, quindi gli stessi byte danno sempre lo stesso digest. Piccole differenze che non si vedono, come uno spazio finale, un diverso carattere di fine riga o un'altra forma Unicode di una lettera accentata, producono invece un digest diverso.

Che cos'è un salt?

Un valore casuale memorizzato accanto all'hash di una password e mescolato in esso. Così due utenti con la stessa password ottengono hash diversi, e un attaccante non può usare un'unica tabella precalcolata di password comuni per tutti gli account.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il laboratorio delle funzioni di hash