Timing Attack ad RSA
|
Timing Attack ad RSA
|
|
|
L'idea Un’operazione fondamentale usata nel crittosistema RSA
è l’esponenziazione modulare. Essa è usata sia per cifrare sia per decifrare
oppure per firmare blocchi di messaggio. Quando RSA è stata introdotta, gli
inventori hanno suggerito un algoritmo basato su operazioni ripetitive
d’elevazione al quadrato e di moltiplicazione (fig 2). --------------------------------------------------------------------------------------------------- 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
if dj = 1 then 5
S ← S ·M mod N 6
return S --------------------------------------------------------------------------------------------------- Figura 2: algoritmo left-to-rigth La figura 2 descrive l’algoritmo left-to-rigth per il calcolo dell'esponenziazione modulare. In input abbiamo il messaggio M, il modulo RSA, ovvero N, e l’esponente privato d. L'espressione in base 2 esprime il fatto che l'esponente privato d è espresso in forma binaria. L’esponente privato d è rappresentato usando al più n bit, dove n è la lunghezza dei bit del modulo RSA, ovvero N, che abbiamo usato nel paragrafo precedente, mentre l’output S rappresenta la firma digitale del messaggio M. Inoltre dobbiamo considerare, che questo algoritmo è usato ipotizzando che il messaggio M è minore del modulo N. Kocher ha fatto alcune
importanti osservazioni sull’algoritmo del quadrato e del multiplo, infatti in
figura 2 la condizione espressa alla linea 4 causa l’esecuzione del percorso
di quest’algoritmo in base al valore dell’esponente. In ogni ciclo di
iterazione, se il bit rilevante di d
è 1, allora sono eseguiti entrambi il modulo del quadrato e del multiplo (linea
3 e 5 rispettivamente); se il bit rilevante è 0 è eseguita solo il modulo del
quadrato (linea 3). In questo modo, l’ammontare di calcolo richiesto, e quindi
il tempo di esecuzione, per completare gli n cicli iterativi è influenzato dal
valore dell’esponente.
Se un attaccante osserva e
confronta il tempo di esecuzione di diversi cicli iterativi nell’algoritmo
left-to-rigth, potrebbe essere in grado di dedurre il valore dei
corrispondenti bit dell’esponente. Questa tecnica, quando è applicata contro
un’operazione di firme RSA, rileverà i bit della chiave segreta del
firmatario. Il timing attack di Kocher
descrive come un attaccante può usare il tempo totale di esecuzione
dell’algoritmo per dedurre i bit dell’esponente privato. Questa informazione
sul tempo può essere facilmente osservata da un attaccante passivo.
Supponiamo che un utente
malintenzionato, Oscar, spedisce una serie di richieste di firme ad un PC che implementa l’algoritmo RSA, usando l’algoritmo ripetuto
left-to-right. L’attacco, poi, procede in modo che
Oscar recupera i bit di d, uno alla
volta. Poiché
d < N
ed
n
è la lunghezza dei bit di N,
la rappresentazione binaria di
d può contenere degli zero precedenti, ma per semplificare la nostra discussione
assumeremo che
dn-1=1. Usando la conoscenza delle
caratteristiche fisiche del PC destinatario, Oscar simula su un PC identico (ad esempio con stesso processore, stessa RAM cache,etc.) il tempo
ti
preso per calcolare
Mi2 * Mi mod N per ognuno dei messaggi conosciuti.
Il valore di Mi influenza l’ammontare di tempo
richiesto per eseguire questo calcolo. Kocher nota che, quando dn-2=1, i 2 insiemi { ti } e { Ti} sono correlati. Per esempio, se ti è molto più grande di quello atteso, allora anche Ti deve essere più grande di quello atteso. Se
dn-2=0, allora i 2 insiemi si comportano come variabili casuali indipendenti.
Misurando la correlazione Oscar può decidere il valore di dn-2. A questo punto Oscar conosce il valore di
S all’inizio del 3° ciclo
iterativo. Per prendere dn-3
Oscar ricostruisce l’insieme
{
ti
}
, simulando il tempo preso dal PC per calcolare S * M mod N, dove il valore di S è conosciuto, e compare con
l’insieme
{Ti}. Oscar
continua allo stesso modo per recuperare i rimanenti bit di d.
|
|
|
