Timing Attack ad RSA
|
Timing Attack ad RSA
|
|
|
Prima di descrivere come difendersi dal timing attack, consideriamo prima due
altri approcci comuni verso lo sviluppo di contromisure.
Il primo e il metodo più ovvio, è assicurarsi che tutte le operazioni girino
in un ammontare di tempo costante. Sfortunatamente, è difficile perseguire
quest’obiettivo. Le ottimizzazioni dei compilatori e della memoria possono
introdurre variazioni di tempo non attesi, i quali sfuggono al controllo delle
implementazioni. Trattenere il risultato di un’operazione fino a che uno
specifico ammontare di tempo terminerà, può sembrare un approccio promettente,
ma la lunghezza del ritardo aggiunto può essere determinato, attraverso il
consumo di alimentazione del sistema o dell’uso della CPU. Inoltre, usando
questo metodo degraderemo l’efficienza del sistema, poiché tutte le
operazioni si comporterebbero come se stessero processando degli input nel caso peggiore. Allora, si potrebbe eseguire la moltiplicazione in ogni ciclo iterativo dell’algoritmo left-to-rigth come in figura 4, il quale non rende costante l’esecuzione del tempo dell’algoritmo.
La variabilità
nell’operazione della moltiplicazione e del quadrato rimarranno ancora e
questo può essere scoperto. --------------------------------------------------------------------------------------------------- INPUT:
M,
N, d = (dn−1dn−2
. . . d1d0)2 OUTPUT:
S
= Md
mod N 1 S ← 1 2
for j = n − 1 .
. . 0 do 3 S ← S 2 mod N 4
T
← S
·M mod N 5
if dj = 1 then 6
S ← T 7
return S --------------------------------------------------------------------------------------------------- Figura
4: Questa modifica dell’algoritmo left-to-rigth è
Come menzionato in precedenza, il timing attack può determinare quali operandi
sono usati in ogni passo dell’algoritmo e al percorso dell’esecuzione. Se l’operazione di moltiplicazione e d’elevazione al quadrato sono eseguite in un tempo costante, allora il tempo per un’esponenziazione modulare sarebbe correlata soltanto dall’ampiezza di Hamming dell’esponente. Per esponenti casuali, l’ampiezza di Hamming non rileva, in media, molte informazioni circa il suo valore. La moltiplicazione di Montgomery è eseguita in un tempo quasi costante, ma c’è una piccola sorgente di variabilità risultante da una sottrazione condizionale.
RSA con la
moltiplicazione di Montgomery è vulnerabile al timing attack [11].
Il secondo metodo è aggiungere rumore al tempo di esecuzione delle varie
operazioni. L’effetto desiderato è quello di incrementare il numero richiesto
di misure dei tempi in modo tale che l’attacco diventi impraticabile. Il
nostro metodo d’attacco e la successiva analisi ha ipotizzato che gli effetti
di rumore fossero insignificanti, ma questo non potrebbe essere il caso.
Inserendo dei ritardi casuali si produce una sorgente di rumore, ma questo
ridurrà l’efficienza se la media del ritardo è abbastanza larga.
Per sconfiggere il timing attack, gli sviluppatori devono preventivare un
attaccante dall’apprendere gli input per un’operazione vulnerabile. Nel caso di RSA, se
Oscar non conoscesse il valore della base usata nell’esponenziazione
modulare, allora la corrispondente informazione di timing non può essere usata.
La struttura algebrica di ZN permette che i messaggi siano
blindati [12
] prima di essere firmati. Piuttosto che firmare il messaggio
Alice, adesso, calcola
messaggio M. La convenienza di questa tecnica dipende interamente dai dettagli del crittosistema, ma molti sistemi a chiave pubblica hanno una struttura algebrica a richiesta.
|
|
|
