Timing Attack ad RSA

Sia j₀  un particolare valore di j  nell’algoritmo left-to-rigth di figura 3, e sia . Oscar procede con il timing attack riempendo le colonne della tabella con valori della forma , dove g è l’ipotesi per il valore dei bit d_j0d_j0-1 dell’esponente. Assumendo che Oscar ha determinato correttamente il valore dei bit d_n-1d_n-2....d_j0+2d_j0+1 , abbiamo:

dove  è un valore candidato per t_i,j0 . Se g=0  allora , altrimenti .  Quindi, noi abbiamo:

Allora si può verificare che il valore  è una misura corretta del tempo presa da Alice per calcolare la moltiplicazione alla linea 9 della figura 3 quando j=j₀ , oppure non lo è. Se è corretto, allora  è uguale a t_i,j0 , e allora:

Se non è corretto, allora  solitamente non è uguale a t_i,j0 , così non ci saranno cancellazioni. Oscar può usare la statistica per determinare se questa cancellazione avviene o no e quindi verificare l’ipotesi su g.

La sottrazione del termine  influenza la varianza di una colonna dei dati. Per vedere ciò, trattiamo le misure dei tempi come occorrenze di variabili casuali. La variabile casuale T descrive quanto tempo è necessario per firmare un messaggio in Z_N, usando d, l’esponente privato di Alice. La variabile casuale  descrive quanto tempo è necessario per esponenziare un messaggio usando gli n-j₀ bit più significativi di d , nel quale sono state aggiunte le ipotesi di due bit (dipendenti dal valore di g).

La variabile casuale r ed s descrive quanto tempo serve per eseguire il quadrato di un elemento di

Assumendo che il tempo per il calcolo del quadrato e della moltiplicazione nei cicli successivi sono indipendenti da ognuno e dall’errore, la varianza della variabile casuale  quando l’ipotesi di g è corretta, vale:

La variabile l è un intero che è determinato dal numero di coppie di bit prese da d  che non sono uguali a 00 (per un valore casuale di d, l è approssimativamente uguale a ). Ricordiamo che la variabili casuali r ed s descrivono il tempo necessario per fare un’operazione di calcolo del quadrato.

Così, r ed s sono identicamente distribuite e la varianza di  può in futuro essere semplificata a:

Quando il valore di g  ipotizzato è scorretto, allora ci sono due possibilità per la varianza di , dipendente dal valore di g. Ricordiamo che, nel caso g sia scorretto, si ha::

.

Innanzitutto, supponiamo che entrambi t_i,j0 e  sono diversi da zero. Allora, il valore  è la differenza di due occorrenze (solitamente non uguali) della variabile casuale t. Poiché la varianza della variabile casuale t-t è data da Var(t)+Var(-t)=2*Var(t), abbiamo nelle colonne della relativa tabella:

Poi, supponiamo che una tra t_i,j0 o  è zero, allora, per ogni colonna di dati con questa proprietà, si ha:

.

In questo modo, la colonna dei dati basata su una corretta ipotesi ha una varianza che è Var(t) oppure 2*Var(t) più bassa delle altre colonne di dati. La varianza campione, S², è una buona stima della varianza effettiva e noi potremmo presentare una stima euristica della probabilità che questa statistica distinguerà la corretta colonna.

Per sviluppare la nostra stima, prima introduciamo alcune note e consideriamo due argomenti che sono stati stabiliti in molti testi introduttivi della probabilità [10 ]. Scriviamo ~ per indicare che la variabile casuale X è normalmente distribuita con la media µ e la varianza . La media di una variabile casuale X è anche denotata con E(X). Se Y è una variabile casuale espressa come Y=aX+b, dove a e b sono costanti, e ~ , allora ~ . Se ~ e ~ , dove X e Y sono indipendenti, allora ~ .

La colonna dei dati nella tabella di Oscar, che corrisponde ad una corretta ipotesi, ha una varianza attesa di Var(e)+(j₀-2)Var(s)+l*Var(t). C’è una seconda colonna nella tabella di Oscar che ha una varianza attesa di Var(e)+(j₀-2)Var(s)+(l+1)*Var(t) . Queste due varianze differiscono per il valore di Var(t). Supponiamo che esiste una terza colonna di dati con varianza attesa Var(e)+(j₀-2)Var(s)+(l+2)*Var(t). In questo caso la varianza differisce dalla prima colonna per un valore di 2*Var(t).

La probabilità di successo del test statistico di Oscar, che consiste nel calcolare S², è più basso quando egli la calcola alla prima e seconda colonna, opposto a quando la applica alla prima e terza colonna. Quindi, noi deriviamo una stima di questa probabilità di successo nel caso peggiore. Una stima della probabilità in altri casi, può essere ricavata in modo simile.

Supponiamo che r,s,t siano normalmente distribuite. Denotiamo con  la distribuzione di r ed s, e denotiamo con  la distribuzione di t. Entrambi:

                 e           

sono normalmente distribuite e i dati nelle colonne corrette e incorrette della tabella sono distribuite in accordo alle seguenti somme:

                  e              

Entrambe le somme di queste variabili casuali sono normalmente distribuite. Denotiamo la distribuzione del primo con  e notiamo che .

Supponiamo che abbiamo un totale di k  misure di tempo accurate. Siano X₁,X₂,...,X_k e Y₁,Y₂,...,Y_k le variazioni normali standard corrette ed errate rispettivamente. Se gli effetti di errore sono insignificanti, possiamo modellare i dati in due colonne come:

Per semplificare la nostra notazione, poniamo  e . Vogliamo stimare quanto segue:

Le variabili V_i e W_i sono normalmente distribuite con le media di µ₀ e µ_0+t rispettivamente. Così, se k è grande, allora  e . Usando questa approssimazione ci dà:

Ora, consideriamo alcune nozioni del calcolo delle probabilità. L’identità Var(X)=E(X²)-E(X)² visualizza che E(X_i²)=1 e E(Y_i²)=1, poiché X_i e Y_i  sono normalmente distribuite. A questo punto,  e noi useremo questo valore per approssimare . Poiché X_i e Y_i sono indipendenti, E(X_i,Y_i)=E(X_i)E(Y_i)=0.

Ancora, Var(X_i,Y_i)=E(X_i²Y_i²)-(E(X_iY_i))²=E(X_i²Y_i²)=E(X_i²)E(Y_i²)=1. Applicando il teorema del limite centrale, allora  segue, approssimativamente, la distribuzione di N(0,k). Se Z è una variazione standard normale, la probabilità di successo di Oscar, nel caso peggiore, è approssimativamente:

dove  è l’area situata sotto la curva normale standard da  a . Riapplicando i passi della nostra approssimazione, possiamo stimare la probabilità di successo di Oscar in un caso alternativo, quale:

Notiamo che, come ci aspettavamo, la probabilità è più grande del primo caso.

Ricordiamo che  e ipotizzando che , abbiamo che . Adesso:

Questa è la probabilità di successo, e in ognuno dei due casi, dipende dai valori di . In questo modo, Oscar procede con il timing attack, facendo variare j₀ da n-1 a 1. Vengono recuperati più bit dell’esponente segreto, j₀ decrementa, e così la probabilità di successo incrementa. Ancora, considerando molte misure sui tempi, k  incrementa, così la probabilità di successo incrementa anch’essa.