Funzioni di hash

Una funzione di hash $h$, o message digest function, è una funzione che mappa un messaggio arbitrariamente lungo in una stringa di lunghezza prefissata, cercando di far in modo che da questa stringa non si possa risalire al messaggio che l'ha generata. La lunghezza della stringa finale è direttamente correlata con la sicurezza della funzione di hash, perché più una stringa è lunga, minore sarà la probabilità di trovare due messaggi con lo stesso digest, con la stessa stringa finale.

La stringa $d=h(m)$ può essere vista come l'impronta digitale del messaggio, teoricamente irripetibile.

Ciò che si chiede da una funzione di hash è:

1. l'efficienza computazionale, perché il messaggio $m$ potrebbe essere molto lungo;
2. la probabilità che accada $d=h(m)$ per un qualsiasi messaggio casuale $m$ deve essere $2^{-n}$, dove il digest è lungo $n$ bit.
3. one way property o preimage resistance: dato il digest $d$, dev'essere computazionalmente impossibile calcolare il messaggio che l'ha generato;
4. dato il messaggio $m$ tale per cui $d=h(m)$, deve essere computazionalmente impossibile trovare un altro messaggio $m'$ tale per cui $h(m)=h(m')=d$;
5. deve essere computazionalmente impossibile trovare due messaggi $m'$ ed $m''$ che collidono, qualunque sia il loro digest.

Teorema: Paradosso dei gemelli, o birthday problem

Dato un numero $n$ di bit ed un digest in uno spazio di dimensione $2^{n}$, quanti messaggi devono essere scelti per avere il 50% di possibilità di trovarne almeno 2 che collidono, cioè che hanno lo stesso digest?

$2^{\frac {n}{2}}$

Chiave delle funzioni di hash

Le funzioni di hash possono essere con o senza chiave; se sono senza chiave, vengono chiamate Modification Detection Code (MDC), altrimenti sono chiamate Message Authentication Code (MAC).

Lo scopo degli MDC è garantire la protezione d'integrità dei dati, cioè garantire che il messaggio $m$ di cui si possiede il digest è proprio quello che si sta leggendo. Nel caso in cui si abbia a che fare con dei MAC, allora gli scopi sono non solo la protezione di integrità, ma anche l'autenticazione dell'autore del messaggio.

Nel caso dei MAC, si ha una chiave, quindi si ha

$d=h_{k}(m)$

Possibili attacchi ad un MAC, oltre a quelli per gli MDC (che restano validi), possono essere:

1. calcolare la chiave $k$ a partire da un numero sufficiente di digest $d_{i}$;
2. conoscendo un sufficiente numero di $d_{i}=h_{k}(m_{i})$, calcolare il corretto valore di $d_{j}=h_{k}(m_{j})$ senza conoscere la chiave;
3. trovare due messaggi $m$ e $m'$ tali per cui $h_{k}(m)=h_{k}(m')=d$.

Se nel caso degli algoritmi di cifratura simmetrici lo scopo principale è fare in modo che il miglior modo di leggere un messaggio senza conoscere la chiave sia provare tutte le chiavi, nel caso degli algoritmi MDC lo scopo principale è fare in modo che trovare due messaggi che collidono significhi calcolare almeno $2^{\frac {n}{2}}$ hash, dove $n$ è la lunghezza dell'hash stesso.

Modification Detection Codes

Gli algoritmi MDC devono avere alcune proprietà, tra cui:

• preimage resistance, deve essere impossibile calcolare il messaggio a partire dal digest. Questa proprietà è importante, perché tra gli usi che si fa degli MDC c'è quello dell'autenticazione, dove l'utente si autentica al server mandando il digest

$d=h(challenge|key)$

dove la challenge è una stringa casuale di bit imposta dal server (cosa da non fare, è troppo pericolosa).

• weak collision resistance, deve essere impossibile, dato $d=h(m)$, trovare un messaggio $m'$ tale per cui $d=h(m')$. Questo fatto è essenziale per le cosiddette firme digitali. Quello che si fa, infatti, è andare a firmare il digest del messaggio (che di solito è più corto del messaggio stesso), in modo tale da non rendere il calcolo della firma e la verifica un lavoro troppo oneroso per i calcolatori (pensiamo, ad esempio, al chip integrato in una smartcard, ha pochissima potenza computazionale). Se l'MDC non è sicuro da attacchi di questo tipo, allora sarà facile trovare un messaggio arbitrario che risulti esser stato firmato da qualcuno.

• strong collision resistance, deve essere impossibile trovare una qualsiasi coppia di messaggi $m'$ ed $m''$ che abbiano qualsivoglia digest $d'=d''$. Questo fatto è importante perché l'attaccante potrebbe avere qualche potere sul messaggio da firmare; in questo caso, vale la regola che (se l'MDC è sicuro) la resistenza della funzione di hash è direttamente proporzionale alla lunghezza del digest.

• one-way property, deve essere impossibile ricavare il testo del messaggio $m$ a partire dal suo digest $d$. Perché un MDC offra questa proprietà, ci deve essere una dimostrazione; ad oggi, non esiste alcuna dimostrazione che provi questa proprietà per nessun MDC usato, se non sotto certe ipotesi non sempre verificate; nonostante questo, può essere dimostrata la complessità computazionale minima per ricostruire il messaggio, dato il digest.

Funzioni di hash iterative

Quello che si fa con le funzioni iterative è dividere il messaggio in blocchi e continuare a comprimere questi blocchi fino a raggiungere la lunghezza finale del digest.

La funzione di compressione lavora su $q$ bit, quindi servono $t$ iterazioni della funzione per avere il risultato in $n$ bit da dare alla trasformazione finale $g$. La funzione è

$r_{i}=f(x_{i},r_{i-1})$

dove il primo elemento è un vettore di inizializzazione $IV$, che può essere un valore predefinito (non deve essere casuale, altrimenti la funzione non sarebbe ripetibile), oppure una funzione del messaggio stesso.

Metodo Matyas-Meyer-Oseas

Il metodo di Matyas, Meyer e Oseas prevede di sfruttare un algoritmo di cifratura a blocchi per costruire l'MDC. La funzione di compressione $f$, quindi, sarà:

La funzione $w()$ si occupa di creare la chiave per l'algoritmo di cifratura, a partire prima dall'IV e successivamente dal testo cifrato, occupandosi di ridurre o aumentare in maniera deterministica il numero $n$ di bit. La funzione di cifratura E_k sarà come quelle che abbiamo già visto nel capitolo dei criptosistemi simmetrici.

Questa soluzione non è la più adatta, visto che gli algoritmi di cifratura sono pensati per altri scopi e sono, di norma, meno efficienti di altri algoritmi progettati per costruire un MDC. Inoltre, la dimensione dell'hash sarà limitata dalla dimensione del blocco dell'algoritmo di cifratura: per esempio, col DES sarà di 64 bit.

Message digest 5

L'algoritmo MD5 è stato pubblicato nel 1991 con l'RFC 1321, ed è il successore dell'MD4. Per questo protocollo

• il messaggio $m$ può avere qualsiasi dimensione;
• la lunghezza del digest è di 128 bit;
• la funzione di compressione lavora con blocchi di dati da 512 bit.

Per ovviare al fatto che il messaggio potrebbe non essere lungo esattamente un multiplo della dimensione del blocco $q$, si ha un padding di questo tipo:

$|messaggio|1|00000\cdots 0|lunghezza-del-messaggio|$

Quindi, il testo passato alla funzione di compressione è composto da

• il messaggio da proteggere;
• un bit a $1$;
• tanti $0$ quanto è necessario
• la lunghezza del messaggio, espressa in 64 bit. Da questo limite si ha che, se la lunghezza del messaggio è superiore, il numero contenuto in questo campo sarà espresso in modulo 64, cioè

$lunghezza=lunghezza-del-messaggio\cdot \mod (64)$

Nell'algoritmo MD5 non è prevista la trasformazione finale $g$, la funzione di compressione restituisce digest di 128 bit.

MD5 è molto veloce, ma la sua sicurezza sta diminuendo progressivamente. Nel 1996 è stato dimostrato che servono soltanto $2^{45}$ tentativi prima di trovare due messaggi che collidono, al posto di $2^{\frac {128}{2}}=2^{64}$, cioè un numero molto più basso. Con un processore P4 a 1,6 GHz (quindi, alla portata di tutti) bastano 8 ore per trovare due messaggi che collidono.

Esempio pratico: MD5 in GNU/linux

Per calcolare il digest MD5 di un qualsiasi_file, in GNU/linux è disponibile il comando md5sum, contenuto nel pacchetto coreutils. Per eseguire il comando sul file di testo qualsiasi_file contenente la parola wikiversità si usa il comando

$ md5sum qualsiasi_file

da cui si ottiene

318bde3b9a0fb0127d0864b6c2fa0ff1 qualsiasi_file

Secure Hashing Algorithm 1

SHA-1 è un algoritmo MDC pubblicato nel 1993 con l'RFC 3174. Si ha:

• il messaggio deve essere lungo al massimo $2^{64}$ bit;
• il risultato del digest è lungo $n=160bit$
• la dimensione del blocco della funzione di compressione è 512 bit.

SHA-1 è poco più lento di MD5, ma in compenso è considerato più sicuro. Oltre a SHA-1, esistono SHA-256, SHA-384 e SHA-512. Anche la sicurezza di SHA-1, come quella di MD5, sta scendendo. Ad oggi, sono necessari $2^{69}$ tentativi per trovare due messaggi che collidano (comunque, più del limite teorico di MD5), mentre dovrebbero essere

$2^{\frac {160}{2}}=2^{80}$.

Esempio: SHA-1 in GNU/linux

Per calcolare il digest SHA-1 di un file, in GNU/linux è disponibile il comando sha1sum contenuto nel pacchetto coreutils. Per eseguire il comando sul file di testo qualsiasi_file contenente la parola wikiversità si usa il comando

$ sha1sum qualsiasi_file

da cui si ottiene

bf7206323c6340aa269e75f7231544886611d59b qualsiasi_file

Ad oggi, MD5 è ancora molto usato. Usare SHA-1 è meglio che usare MD5, ma nel caso in cui si vogliano garanzie in più per il futuro, è meglio usare SHA-256 o superiori.

Performance degli MDC

Con un processore P4 a 2,1 GHz, si riesce a calcolare la somma MD5 ad una velocità di

• 1716 Mbps con MD5;
• 609 Mbps con SHA-1;
• 409 Mbps con SHA-256;
• 186 Mbps con DES.

Message Authentication Codes

Un algoritmo MAC può essere derivato da un MDC, semplicemente inserendo anche la chiave $k$ all'interno del messaggio che si va a firmare. Ci sono diversi approcci:

Chiave in coda al messaggio

$d=MAC_{k}(m)=MDC(m|k)$

Usare questo approccio non è una buona idea. Supponiamo che un attaccante abbia a disposizione due messaggi che collidono con l'MDC, cioè esistono $m'$ ed $m''$ tali per cui

$MDC(m')=MDC(m'')=d$

In questo caso, si avrà sicuramente

$MAC_{k}(m'|k)=MAC_{k}(m''|k)$

dal momento che la chiave $k$ viene usata soltanto all'ultima iterazione dell'algoritmo. A questo punto, all'attaccante basta convincere qualcuno a firmare il messaggio $m'$ (cosa non difficile) per avere il messaggio $m''$ firmato.

Chiave in testa al messaggio

$d=MAC_{k}(m)=MDC(k|m)$

Anche in questo caso, non abbiamo il MAC ideale. Infatti, risulta molto facile ricavare il digest $d'=MAC_{k}(m')$ a partire da un digest $d=MAC_{k}(m)$, dove si ha $m'=m|x$, con $x$ un testo a piacere. Questo fatto non è immediatamente sfruttabile se l'MDC inserisce del padding, però è molto rischioso, non è sicuro.

Chiave in testa ed in coda ad un messaggio, MD5 envelope

Questo algoritmo è standardizzato dalla RFC 1828. Si tratta di usare l'algoritmo MD5 con

$MAC_{k}(m)=MD5(k|p|m|k)$

dove $p$ è il padding necessario per avere un messaggio che sia multiplo di 512 bit. La chiave $k$ viene usata sia all'inizio che alla fine dell'MD5, in modo tale che il suo effetto si faccia sentire su tutto il digest e non si possa aggiungere del nuovo testo in coda.

Per quanto riguarda le performance, sono pari ad MD5 e, quindi, ottime; il problema è che, con un sufficiente numero di coppie $<d_{i},m_{i}>$, un attaccante può arrivare a scoprire la $k$. Questo fatto non è impossibile, visto che sia il digest (la firma) sia il messaggio firmato sono spesso disponibili su internet, pubblicamente. Ancora una volta, meglio non usare l'algoritmo MD5 envelope.

MAC basati su funzioni di hash

Con la sigla HMAC si indicano tutte quelle funzioni MAC derivate da un algoritmo MDC secondo le specifiche dello standard RFC 2104. Si ha

$MAC_{k}(m)=HMAC-MDC_{k}(m)=MDC((k\oplus 0\cdots )\oplus c_{1}|MDC(k|0\cdots )\oplus c_{2}|m))$

dove le grandezze $c_{1}$ e $c_{2}$ sono delle costanti. La sicurezza di questo protocollo è stata dimostrata dagli autori, quindi l'attacco più efficace risulta essere proprio quello per tentativi.

Esempio: Attacco ad un MAC di tipo HMAC

• Trudy osserva un numero sufficiente di coppie $<d_{i},m_{i}>$, fin quando trova due messaggi $m_{i}\neq m_{j}$ con la stessa firma (collisione).
• Trudy calcola il messaggio $m_{3}=m_{1}|x$ e chiede ad Alice di firmarlo, in modo tale da ottenere

$d_{3}=MAC_{k}(m_{1}|x)$

• Trudy è in grado di calcolare, senza conoscere la chiave $k$, la firma

$d_{2}=MAC_{k}(m_{2}|x)$

Questo attacco è possibile, ma impraticabile. Consideriamo di usare HMAC-MD5: Trudy dovrà memorizzare almeno $2^{64}$ blocchi da 512 bit, tutti generati con la stessa chiave. Si tratta di $2^{73}$ bit, cioè

$2^{70}$ byte -> $2^{60}$ kB -> $2^{50}$ MB -> $2^{40}$ GB -> $2^{30}$ TB

Considerando una connessione a 10Gbps (cioè, 10 volte superiore alla velocità limite delle più moderne schede di rete cablate), servirebbero circa 25000 anni per avere il 50% di probabilità di successo. Quindi, HMAC è il MAC da usare, è dimostrato essere sicuro.

Collegamenti esterni

• RFC 1321, algoritmo MD5 (in inglese) (5/12/2008 verificato funzionante)
• Elenco di attacchi che si possono compiere al protocollo MD5 (in inglese) (5/12/2008 verificato funzionante)
• RFC 3174, algoritmo SHA-1 (in inglese) (5/12/2008 verificato funzionante)
• RFC 1828, algoritmo MD5 envelope (in inglese) (5/12/2008 verificato funzionante)
• RFC 2104, algoritmi HMAC (in inglese) (5/12/2008 verificato funzionante)