Timing Attack ad RSA

        L’ RSAREF 2.0 è stato rilasciato dalla RSA Laboratories nel 1994. Questa libreria è stata presa come un’implementazione di riferimento per diversi schemi comuni crittografici.  Nella libreria RSAREF 2.0 sono incluse gli algoritmi per l’accordo di chiavi Diffie-Hellman e la firma RSA. 

        In entrambi i casi, l’esponenziazione modulare è trattata attraverso la funzione NN-ModExp. Il pseudo-codice della funzione NN-modExp è dato dalla figura 3.

---------------------------------------------------------------------------------------------------

INPUT: M, N, d = (d_n−1d_n−2 . . . d₁d₀)₂

OUTPUT: S = M^d  mod N

 1 m1 ← M mod N

2 m2 ← m1 * M mod N

3 m3 ← m2 * M mod N

4 S ← 1

5 for j = n − 1 . . . 0 by 2 do

6         S ← S ²  mod N

7         S ← S ² mod N

8         if (d_jd_j−1)₂  <> S then

9                    S ← S * m_(djdj−1)2 mod N

10 return S

---------------------------------------------------------------------------------------------------

                        Figura 3: Metodo left-to-right per il calcolo dell'esponenziazione modulare 

        Un’idea sbagliata molto comune sul timing attack è che esso determina solo se è eseguita o no una condizione moltiplicativa. Se fosse stato così, allora l’attacco non avrebbe successo contro l’algoritmo di figura 3. Conoscendo che una moltiplicazione è eseguita in un particolare ciclo iterativo, eliminerebbe soltanto uno dei quattro possibili valori per la coppia rilevante dei bit dell’esponente.  

        Per determinare il valore di una coppia dei bit dell’esponente è necessario conoscere quali operandi sono usati nella condizione moltiplicativa. Il timing attack è capace di esplodere la variazione dei tempi nelle moltiplicazioni e nel quadrato.

        Supponiamo che Alice e Oscar comunicano con un protocollo di firme usando i propri PC. Quando Oscar spedisce un messaggio ad Alice, Alice usa le routine di RSAREF e la sua coppia di chiavi private (N,d) per firmare. Alice allora spedisce la sua firma a Oscar. Oscar, intanto, memorizza il tempo T_i che Alice impiega per rispondere, dopo che egli ha spedito ad Alice il messaggio M_i.

        Ci sono diversi fattori che contribuiscono al valore di T_i, infatti ritornando alla figura 3, il tempo richiesto per eseguire le istruzioni da 1 a 4, danno una contribuzione che denotiamo con c_i.   Inoltre nel ciclo della figura 3, per un particolare valore di j, il tempo richiesto per eseguire le linee 6, 7 e 9 anch’esse contribuiscono a T_i . Denotiamo queste ultime condizioni con r_i,j,s_i,j,t_i,j rispettivamente.

Notiamo che r_i,j e s_i,j sono valori strettamente positivi, ma t_i,j potrebbe valere zero. Altri fattori, come errori di misurazione e distanza di trasmissione, contribuiscono anche a T_i e possono essere trattati come sorgenti di errore. Denotiamo queste contribuzioni con e_i. A questo punto, possiamo scrivere:

        I bit dell’esponente segreto di Alice influenza il valore di quasi tutti i componenti in questa somma. Per un particolare valore di j, gli operandi usati nelle due operazioni quadratiche sono completamente determinate dal valore dei bit dell’esponente d_n-1,d_n-2,....,d_j+2,d_j+1.  

        Gli operandi usati nei passi della moltiplicazione sono affetti da questi stessi bit così come i bit d_jd_j-1. Così, gli esponenti r_i,j,s_i,j,t_i,j  sono tutti influenzati dai bit dell’esponente. Il valore di c_i è influenzato soltanto dal valore di M_i.

        Consideriamo il primo ciclo iterativo di NN-ModExp. Usando un PC identico ad Alice, Oscar può simulare e temporizzare i quattro possibili insiemi di calcoli che Alice esegue nel primo ciclo iterativo quando firma il messaggio M. Effettivamente, Oscar genera quattro candidati per il valore di c_i+r_i,n-1+s_i,n-1+t_i,n-1. Per costruire ogni candidato, Oscar può semplicemente firmare il messaggio M_i quattro volte usando gli esponenti 00, 01, 10 e 11, espressi in forma binaria.             

        Denotiamo con  il tempo richiesto per queste quattro firme, dove i primi due indici indicano il relativo messaggio e il ciclo iterativo, mentre l’ultimo indice rappresenta un’ipotesi per i bit d_n-1d_n-2. Oscar può, quindi, costruire la seguente tabella:

        In una delle quattro colonne, Oscar ha simulato le operazioni che saranno le stesse di Alice, eseguite alla fine del primo ciclo iterativo. In una di queste colonne, il valore candidato di Oscar sarà più vicino a c_i+r_i,n-1+s_i,n-1+t_i,n-1 degli altri tre candidati. Dall’analisi nella seguente sezione, vediamo che, con un’alta probabilità, questo produrrà che la varianza[1] della colonna corretta sia più piccola delle altre. Confrontando le quattro varianze ottenute, Oscar può determinare il valore di d_n-1d_n-2.  

        La prossima coppia di bit dell’esponente, d_n-3d_n-4, possono essere dedotti calcolando i tempi dei quattro possibili insiemi di calcoli che Alice ha eseguito prima della fine del secondo ciclo iterativo. Per ogni messaggio, Oscar può misurare il tempo preso per firmare M_i usando i quattro esponenti d_n-1d_n-200, d_n-1d_n-201, d_n-1d_n-210 e d_n-1d_n-211. Denotiamo il tempo richiesto per queste quattro firme con .

Oscar allora può ricostruire la sua tabella in cui le righe hanno la forma:

Inoltre, Oscar calcola la varianza di ogni colonna per determinare i valori attuali dei bit. Il 

valore delle altre coppie di bit può essere deciso a turno, usando una tabella simile.