Attacco del compleanno

Un attacco del compleanno è un tipo di attacco crittografico utilizzato per la crittanalisi degli algoritmi di cifratura; è così chiamato perché sfrutta i princìpi matematici del paradosso del compleanno nella teoria delle probabilità.

L'attacco del compleanno si può riassumere brevemente come segue: data una funzione f, lo scopo dell'attacco è quello di trovare 2 numeri $x_{1},x_{2}$ tali che $f(x_{1})=f(x_{2})$. Tale coppia di valori $x_{1},x_{2}$ è chiamata collisione. Il metodo utilizzato per trovare una collisione è semplicemente quello di valutare la funzione f per differenti valori di input che possono essere scelti casualmente o pseudo-casualmente fino a che non si ottiene lo stesso risultato. A causa del paradosso del compleanno questo metodo può essere molto efficiente: specificatamente, se una funzione $f(x)$ restituisce i valori del suo codominio $H$ con identica probabilità e la dimensione del codominio $H$ (ossia il numero di valori possibili) è sufficientemente grande, dopo aver valutato la funzione per circa $1.25\cdot {\sqrt {H}}$ differenti argomenti, c'è il 50% di probabilità di ottenere una coppia di valori distinti $x_{1}$ e $x_{2}$ per cui valga $f(x_{1})=f(x_{2})$.

Princìpi matematici

Consideriamo il seguente esperimento. Da un insieme di valori $H$ scegliamo $n$ valori uniformemente a caso, consentendo quindi anche ripetizioni degli stessi. Poniamo $p(n;H)$ la probabilità che durante l'esperimento almeno un valore sia scelto più di una volta. La probabilità può essere approssimata a

$p(n;H)\approx 1-e^{-(n(n-1))/2\cdot H}\approx 1-e^{-n^{2}/{2\cdot H}},$

Poniamo adesso $n(p;H)$ come il più piccolo numero dei valori che abbiamo scelto, tale che la probabilità che possiamo aspettarci di trovare una collisione sia almeno $p$. Invertendo l'espressione qui sopra, troviamo la seguente approssimazione

$n(p;H)\approx {\sqrt {2\cdot H\cdot \ln \left({1 \over 1-p}\right)}},$

ed assegnando la probabilità di trovare una collisione a 0,5 arriviamo a

$n(0.5;H)\approx 1.1774{\sqrt {H}}$.

Poniamo $Q(H)$ come il numero previsto di valori che dobbiamo scegliere prima di trovare la prima collisione. Il numero può essere approssimato da

$Q(H)\approx {\pi \over 2}{\sqrt {H}}.$

Come esempio, se viene usato un hash di 64 bit, ci sono approssimativamente 1,8 × 10¹⁹ differenti risultati. Se sono tutti equamente probabili (nel migliore dei casi), allora occorreranno approssimativamente "solo" 5,1 × 10⁹ tentativi per generare una collisione utilizzando la forza bruta. Questo valore è chiamato vincolo del compleanno e per codici di n bit può essere calcolato come $2^{n/2}$. Altri esempi sono i seguenti:

Bit	Possibili risultati (H)	Probabilità desiderata della collisione casuale (p)
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
32	4,3 × 109	2	2	2	2,9	93	2,9 × 103	9,3 × 103	5,0 × 104	7,7 × 104	1,1 × 105
64	1,8 × 1019	6,1	1,9 × 102	6,1 × 103	1,9 × 105	6,1 × 106	1,9 × 108	6,1 × 108	3,3 × 109	5,1 × 109	7,2 × 109
128	3,4 × 1038	2,6 × 1010	8,2 × 1011	2,6 × 1013	8,2 × 1014	2,6 × 1016	8,3 × 1017	2,6 × 1018	1,4 × 1019	2,2 × 1019	3,1 × 1019
256	1,2 × 1077	4,8 × 1029	1,5 × 1031	4,8 × 1032	1,5 × 1034	4,8 × 1035	1,5 × 1037	4,8 × 1037	2,6 × 1038	4,0 × 1038	5,7 × 1038
384	3,9 × 10115	8,9 × 1048	2,8 × 1050	8,9 × 1051	2,8 × 1053	8,9 × 1054	2,8 × 1056	8,9 × 1056	4,8 × 1057	7,4 × 1057	1,0 × 1058
512	1,3 × 10154	1,6 × 1068	5,2 × 1069	1,6 × 1071	5,2 × 1072	1,6 × 1074	5,2 × 1075	1,6 × 1076	8,8 × 1076	1,4 × 1077	1,9 × 1077

La tabella mostra il numero di hash n(p) necessari per ottenere la probabilità di successo specificata, assumendo che tutti gli hash sono ugualmente possibili. Come paragone, il tasso di bit errati non correggibili di un hard disk varia da 10⁻¹⁸ a 10⁻¹⁵ [1]. In teoria, l'MD5, con il suo hash lungo 128 bit, dovrebbe ricadere all'interno di tale intervallo fino ad 820 miliardi di documenti, anche se i suoi possibili output sono molto di più.

Implicazioni in crittografia

È facile vedere che se gli output della funzione sono distribuiti in modo diseguale, allora una collisione può essere trovata molto più velocemente. La nozione di bilanciamento di una funzione di hash quantifica la resistenza della funzione agli attacchi del compleanno e permette di stimare la vulnerabilità di popolari hash come l'MDx e l'SHA (Bellare e Kohno, 2004).

Le firme digitali possono essere vulnerabili ad un attacco del compleanno. Un messaggio $m$ è generalmente firmato prima calcolando $f(m)$, dove $f$ è una funzione crittografica di hash, e poi usando una qualche chiave segreta per firmare $f(m)$. Supponiamo che Oscar voglia imbrogliare Bob inducendolo a firmare un contratto fraudolento. Oscar prepara un contratto $m$ corretto ed uno $m'$ fraudolento. Oscar trova poi un certo numero di punti nel contratto per cui $m$ può essere modificato senza cambiarne il significato, ad esempio inserendo delle virgole, delle linee vuote, uno o due spazi dopo una frase, sostituendo dei sinonimi ecc. Combinando queste modifiche, Oscar può creare un notevole numero di varianti di $m$ che sono in pratica tutti contratti corretti. In maniera simile, crea anche un gran numero di varianti del contratto fraudolento $m'$. Alla fine, Oscar applica la funzione di hash a tutte queste varianti finché non trova una variante del contratto corretto ed una variante di quello fraudolento che hanno lo stesso valore di hash, cioè $f(m)=f(m')$. A questo punto, Oscar presenta a Bob la versione corretta per la firma. Dopo che Bob lo ha firmato, Oscar prende la firma e l'attacca al contratto fraudolento. Adesso la firma "prova" che Bob ha firmato il contratto fraudolento.

Questo modo di operare differisce leggermente dall'originale paradosso del compleanno dato che Oscar non guadagna nulla dall'ottenere due contratti corretti o due contratti fraudolenti con lo stesso hash. La strategia ottimale di Oscar è quella di generare coppie costituite da un contratto corretto ed uno fraudolento. Oscar compara ogni coppia appena generata con tutte le altre, cioè compara l'hash della copia corretta con gli hash di tutte le precedenti copie fraudolente, ed il nuovo contratto fraudolento con gli hash di tutti i precedenti contratti corretti (senza preoccuparsi di comparare l'hash del contratto fraudolento generato con tutti gli hash dei precedenti contratti fraudolenti né l'hash del contratto corretto generato con tutti gli hash dei precedenti contratti corretti). Le equazioni del paradosso del compleanno si applicano con n che assume il valore del numero di coppie (il numero di hash che Oscar deve generare è 2n).

Per evitare questo attacco la lunghezza dell'output di una funzione di hash utilizzata in uno schema di firma digitale deve poter essere grande abbastanza in modo che l'attacco del compleanno divenga computazionalmente non fattibile: in genere, siamo nell'ordine del doppio del numero di bit necessari per prevenire un classico attacco a forza bruta.

L'algoritmo rho di Pollard è un esempio di algoritmo che utilizza un attacco del compleanno per il calcolo di logaritmi discreti.

Bibliografia

• Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks - EUROCRYPT 2004
• Bruce Schneier: Applied Cryptography, seconda edizione

Voci correlate

• Attacco meet-in-the-middle

Collegamenti esterni

• (EN) Eric W. Weisstein, Birthday Attack, su MathWorld, Wolfram Research.
• "What is a digital signature and what is authentication?" dalle FAQ crittografiche di RSA
• Michael Wiener e Paul C. van Oorschot: "Parallel collision search with cryptanalytic applications" Archiviato il 30 dicembre 2008 in Internet Archive.