Il mascheramento è efficace per contrastare gli attacchi ai canali laterali?

Question

Sto lavorando con un codice di crittografia a chiave pubblica bigint. È sicuro utilizzare il mascheramento bit per bit per garantire che i tempi di calcolo e gli indirizzi di memoria accessibili siano indipendenti dai valori dei dati?

Questa tecnica è vulnerabile agli attacchi dei canali laterali in base a tempi di istruzione, potenza, emissioni RF o altre cose di cui non sono a conoscenza? (Per avere un riferimento, io sono a conoscenza di tecniche come RSA accecante, scala CE Montgomery, cache di vampate di calore, e così via.)

---

Esempio di codice semplice (C/C++):

uint a = (...), b = (...); 
if (a < b) 
    a += b; 

Ora tradotto da usare tempo costante mascheratura:

uint a = (...), b = (...); 
uint mask = -(uint)(a < b); 
a = ((a + b) & mask) | (a & ~mask); 

noti che a < b è 0 o 1, e la maschera è 0x00000000 o 0xFFFFFFFF.

---

Analogamente, per un'operazione di alto livello (C++):

Integer x = (...); 
if (x.isFoo()) 
    x.doBar(); 

è la seguente traduzione sicuro accettabile?

Integer x = (...); 
uint mask = -(uint)x.isFoo(); // Assume this is constant-time 
Integer y(x);     // Copy constructor 
y.doBar();      // Assume this is constant-time 
x.replace(y, mask);   // Assume this uses masking 

Answer 1

Questa tecnica può essere può essere sicuro ... se le operazioni che assumiamo richiedono tempo costante davvero fare, e se il compilatore non cambia il codice per fare qualcos'altro invece.

In particolare, diamo un'occhiata al vostro primo esempio:

uint a = (...), b = (...); 
uint mask = -(uint)(a < b); 
a = ((a + b) & mask) | (a & ~mask); 

vedo due modi un po 'plausibili in cui questo potrebbe mancare per l'esecuzione in tempo costante:

1. I il confronto a < b potrebbe richiedere o meno tempo costante, a seconda del compilatore (e della CPU). Se è compilato con una semplice manipolazione di bit, potrebbe essere un tempo costante; se è compilato per usare un salto condizionato, potrebbe non esserlo.

2. A livelli di ottimizzazione elevati, è possibile che un compilatore troppo intelligente possa rilevare ciò che accade (ad esempio dividendo il codice in due percorsi in base al confronto e ottimizzandoli separatamente prima di unirli nuovamente) e "ottimizzare" rientra nel codice temporale non costante che stavamo cercando di evitare.

   (Naturalmente, è anche possibile che un compilatore sufficientemente intelligente potrebbe ottimizzare il codice tempo apparentemente non costante ingenuo in un'operazione a tempo costante, se si pensa che sarebbe più efficiente!)

Un possibile modo per evitare il primo numero potrebbe essere quella di sostituire il confronto con la manipolazione po 'esplicito, come in:

uint32_t a = (...), b = (...); 
uint32_t mask = -((a - b) >> 31); 
a = ((a + b) & mask) | (a & ~mask); 

si noti tuttavia che questo è equivalente soltanto al vostro codice originale se possiamo essere sicuri che a e b differiscono di meno di 2 . Se questo non è garantito, avremmo dovuto lanciare le variabili in un tipo più lungo prima della sottrazione, ad esempio:

uint32_t mask = (uint32_t)(((uint64_t)a - (uint64_t)b) >> 32); 

Detto questo, anche questo non è infallibile, come il compilatore potrebbe ancora decidere di trasformare questo codice in qualcosa che non è tempo costante. (Per esempio, la sottrazione a 64 bit su una CPU a 32 bit potrebbe potenzialmente prendere tempo variabile a seconda che ci sia un prestito o no — che è proprio quello che stiamo cercando di nascondere, qui.)

In generale, la unico modo per assicurarsi che tali perdite di sincronizzazione non si verificano è quello di:

1. ispezionare il codice assembly generato manualmente (ad esempio, alla ricerca di istruzioni di salto dove non si aspettava), e

2. in realtà confronta il codice per verificare che lo faccia, ind e, prendi lo stesso tempo per correre indipendentemente dagli input.

Ovviamente, avrete anche bisogno di fare questo separatamente per ogni combinazione della piattaforma di compilatore e di destinazione che si desidera supportare.

Answer 2

Può essere abbozzato usando adesivo o altre tecniche in codice perché i compilatori fare ogni sorta di ottimizzazioni che non siete spesso a conoscenza. Alcuni dei metodi che hai citato nel tuo post originale sono molto meglio.

Come regola generale utilizzare librerie di crittografia ben note perché dovrebbero essere indurite contro gli attacchi dei canali laterali. In caso contrario, puoi spesso trasformare le informazioni, elaborarle e quindi trasformare i risultati. Questo può funzionare particolarmente bene con la crittografia a chiave pubblica in quanto è spesso omomorfica.