Sicurezza a 80 bit e tempo di attacco

La domanda in gran parte si riduce a:

Che cosa significa $ n $ -bit sicurezza in pratica per un dato valore di $ n $ ?

TL; DR: sicuro come un buon codice simmetrico con una chiave $ n $ -bit.

Non esiste una singola definizione più precisa, anche se ci limitiamo agli aggressori che utilizzano la classica computer (piuttosto che computer quantistici), come fa questa risposta.

Un significato generalmente accettato è che si ritiene che il numero di “passaggi” per rompere il sistema sia $ 2 ^ n $ ; o più precisamente che la probabilità di rompere il sistema con $ s $ “passi” non è nota per essere maggiore di $ s \, 2 ^ {- n} $ con qualsiasi metodo per qualsiasi $ s $ . Tuttavia “passi” e “interruzione” non sono definiti con precisione.

In teoria della crittografia simmetrica, “passo” è tipicamente considerato come unesecuzione del codice con una nuova chiave. In questo modo, un cifrario ideale con una chiave di $ n $ bit ha $ n $ -bit di sicurezza, sotto brute force key search. Quando passiamo alla pratica, gli aggressori non sono vincolati alla ricerca di chiavi di forza bruta e la definizione di un “passaggio” deve diventare un numero di sotto-passaggi paragonabile in numero e costo computazionale ai sotto-passaggi richiesti per uno esecuzione della cifratura con una nuova chiave per un testo in chiaro delle dimensioni della chiave . Con questa definizione, un codice pratico con una chiave di $ n $ bit ha al massimo $ n $ – bit di sicurezza e mira a quellideale.

Quando si passa agli hash, la definizione di un passaggio potrebbe diventare un numero di passaggi secondari paragonabili per numero e costo di calcolo ai passaggi secondari richiesti per lhashing di un nuovo messaggio della dimensione delloutput hash .

Uno dei molti problemi con quanto sopra è che non cè accordo se dobbiamo contare o meno il costo della memoria e degli accessi alla memoria nel costo computazionale. La cosa sicura dal punto di vista di un utente è non contarlo, ma questo può essere di fondamentale importanza per un attaccante.

La definizione di “passaggi” diventa ancora più oscura quando si parla di crittografia asimmetrica come RSA.In teoria, i “passi” potrebbero essere un calcolo nella struttura algebrica usata per il criptosistema; come, per RSA, una valutazione della moltiplicazione modulare $ (a, b) \ mapsto a \, b \ bmod N $ per un numero intero arbitrario $ a $ e $ b $ in $ [0, N) $ , dove $ N $ è il modulo pubblico. Ma ci sono problemi a spostarlo nella pratica, in particolare per RSA: lattacco più noto è quello di fattorizzare il modulo pubblico $ N $ utilizzando GNFS , il cui costo computazionale è dominato da operazioni che hanno poca somiglianza con la moltiplicazione modulare, e dal costo pratico dominato dalla memoria e dagli accessi alla memoria. Il che riporta luso alla vaga definizione nel TL; DR.

come calcolare il tempo di attacco a questo schema di crittografia di sicurezza a 80 bit, come RSA di sicurezza a 80 bit utilizzando un tipo di CPU?

“RSA di sicurezza a 80 bit” non deve essere inteso come RSA con un pubblico a 80 bit modulo $ N $ , che è insicuro a livello terminale. Se avessimo la dimensione di $ N $ , potremmo stimare la difficoltà in base a quella e allesperienza precedente (vedi questo e i suoi collegamenti). Ma non lo facciamo, e non cè consenso sulla dimensione di $ N $ per RSA con sicurezza a 80 bit: viene spesso citato 1024 bit, ma a seconda dellipotesi , ea chi chiedi, è grossolanamente troppo o troppo poco. Quindi la cosa migliore è ignorare che stiamo parlando di RSA e tornare a: tutto il tempo necessario per rompere una buona crittografia simmetrica con un 80 bit chiave.

Il che ci porta a: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequenza } \ times \ text {Number-of-CPUs}} $$ dove $ n $ è il livello di sicurezza in bit, $ k $ è una stima del numero di cicli della CPU per valutare un buon codice utilizzando un algoritmo ultra-ottimizzato e $ p $ è la probabilità residua di successo di un avversario. A seconda della prospettiva, potremmo prendere $ k = 1 $ (che evita di esaminare i dettagli), $ k = 32 $ (perché è ancora meno che nei migliori attacchi contro buoni cifrari che utilizzano un computer generico), o molto di più. A seconda della prospettiva, possiamo prendere $ p = 1 $ (più prudente dal punto di vista di un utente legittimo), $ p = 1/2 $ (che restituisce il tempo previsto nel caso di un cifrario a blocchi), o un $ p $ più piccolo se vogliamo un margine di sicurezza¹.

Ad esempio, con $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , otteniamo $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , ovvero circa 8 anni. In altre parole, le nostre 1000 CPU hanno solo una minima probabilità di successo contro la crittografia simmetrica a 80 bit, fino a quando non diventano tecnicamente obsolete.

Daltra parte, 1000 CPU sono una piccola frazione di CPU in tutto il mondo e il mining di bitcoin mostrano in modo conclusivo che la crittografia a 80 bit non è più sufficiente contro gli avversari con le capacità di progettare ASIC, costruirli in quantità enormi e sostenere i costi energetici per il loro funzionamento; vedi questo .

¹ Il termine $ p $ in la formula è la più prudente dal punto di vista di un utente legittimo, ma fa sì che $ \ text {Time} $ venga sottostimata in molti scenari di attacco. Ad esempio, in ricerca di collisioni, il termine corretto sarebbe più simile a $ \ sqrt p $ .