Perché non utilizzare chiavi cifrate più grandi?

195

RSA Security utilizza comunemente chiavi di dimensioni 1024-bit, 2048-bit o anche 3072-bit. E la maggior parte degli algoritmi simmetrici solo tra 112-bit e 256-bit. Mi rendo conto che le chiavi attuali sono abbastanza sicure per l'hardware di oggi, ma man mano che i computer diventano più veloci, non dovremmo considerare una dimensione della chiave follemente grande come un milione qualcosa di simile per proteggerci dai super computer che non sono ancora stati inventati?

Quindi, in altre parole, quali sono le conseguenze della scelta di una chiave di cifratura troppo grande e perché ognuno limita le dimensioni della chiave?

    
posta Koning 13.12.2012 - 12:48
fonte

8 risposte

77

Il motivo per cui le chiavi RSA sono così piccole è che:

With every doubling of the RSA key length, decryption is 6-7 times times slower.

Quindi questo è solo un altro dei compromessi tra sicurezza e convenienza. Ecco un grafico:

Fonte: link

    
risposta data 13.12.2012 - 13:00
fonte
301

Ho tirato fuori la mia copia di Applied Cryptography per rispondere a questa criptazione simmetrica, 256 è abbondante e probabilmente lo farò essere per molto tempo. Schneier spiega;

Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38 × 10−16 erg/K, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2 K would consume 4.4 × 10−16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21 × 1041 ergs. This is enough to power about 2.7 × 1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

L'audacia è la mia aggiunta.

Nota: questo esempio presuppone che esista un algoritmo di crittografia "perfetto". Se puoi sfruttare i punti deboli dell'algoritmo, lo spazio chiave potrebbe ridursi e ti ritroverebbero con meno meno bit della tua chiave.

Presuppone inoltre che la generazione della chiave sia perfetta - producendo 1 bit di entropia per bit di chiave. Questo è spesso difficile da ottenere in un contesto computazionale. Un meccanismo di generazione imperfetto potrebbe produrre 170 bit di entropia per una chiave a 256 bit. In questo caso, se il meccanismo di generazione della chiave è noto, la dimensione dello spazio forza bruta viene ridotta a 170 bit.

Supponendo che i computer quantistici siano fattibili, tuttavia, qualsiasi chiave RSA sarà rotta usando l'algoritmo di Shor. (Vedi link )

    
risposta data 13.12.2012 - 16:53
fonte
65

Per un AES è stato creato per tre dimensioni chiave 128, 192 or 256 bits .

Attualmente, la forzatura bruta di 128 bit non è nemmeno vicina al possibile. Ipoteticamente, se una chiave AES avesse 129 bit, sarebbe necessario impiegare il doppio della forza bruta per una chiave a 129 bit rispetto a una chiave a 128 bit. Ciò significa che chiavi più grandi di 192 bit e 256 bit richiederebbero molto più tempo per attaccare. Ci sarebbe voluto così tanto tempo per forzare una di queste chiavi che il sole avrebbe smesso di bruciare prima che la chiave fosse realizzata.

2^256=115792089237316195423570985008687907853269984665640564039457584007913129639936

Questo è un grande numero. Ecco quante possibilmente ci sono le chiavi. Supponendo che la chiave sia casuale, se la dividi per 2 hai quante chiavi ci vorranno in media per la forza bruta AES-256

In un certo senso, abbiamo le chiavi di cifratura davvero grandi di cui stai parlando. L'intero punto di una chiave simmetrica è di renderlo irrealizzabile alla forza bruta. In futuro, se l'attacco di una chiave a 256 bit diventa possibile, le chiavi aumenteranno sicuramente, ma questo è un bel po 'lungo la strada.

Il motivo per cui le chiavi RSA sono molto più grandi delle chiavi AES è perché sono due tipi di crittografia completamente diversi. Ciò significa che una persona non attaccherebbe una chiave RSA allo stesso modo in cui attaccherebbe una chiave AES.

Attaccare le chiavi simmetriche è facile.

  1. Inizia con un bitstring 000...
  2. Decifra il testo cifrato con quel bitstring.
  3. Se riesci a leggerlo, ci sei riuscito.
  4. Se non riesci a leggerlo, incrementa il bitstring

L'attacco a una chiave RSA è diverso ... perché la crittografia / decodifica RSA funziona con grandi numeri semi-primi ... il processo è math . Con RSA, non devi provare ogni possibile stringa di bit. Provi molto meno di 2^1024 o 2^2048 bitstrings ... ma non è ancora possibile fare bruteforce. Questo è il motivo per cui i tasti RSA e AES differiscono per dimensioni. [ 1 ]

Per riassumere tutto e rispondere alla tua domanda in 1 frase. Non abbiamo bisogno di chiavi simmetriche ridicolmente grandi perché abbiamo già delle chiavi simmetriche ridicolmente grandi. La crittografia a 256 bit suona wimpy rispetto a qualcosa come una RSA Key a 2048 bit, ma gli algoritmi sono diversi e non possono essere realmente confrontati "bit per bit" come quello. In futuro, se ci sarà bisogno di chiavi più lunghe, ci saranno nuovi algoritmi sviluppati per gestire chiavi più grandi. E se mai volessimo andare più grandi sull'hardware attuale, sarebbe semplicemente un compromesso temporale. Chiave più grande significa tempo di decrittazione più lungo significa comunicazione più lenta. Questo è particolarmente importante per un cifrario poiché il tuo browser internet stabilirà e quindi userà una chiave simmetrica per inviare informazioni.

    
risposta data 13.12.2012 - 13:30
fonte
8

Tempo di elaborazione, puro e semplice. Tutto nella sicurezza è un atto di equilibrio tra il bisogno di sicurezza (tenere fuori le persone cattive) e l'usabilità (lasciando entrare la brava gente). La crittografia è un'operazione costosa di elaborazione anche con hardware dedicato per eseguire i calcoli.

Semplicemente non vale la pena di andare oltre un certo livello di sicurezza per la maggior parte degli scopi perché i trade offs diventano esponenzialmente più difficili da usare mentre offrono quasi nessun beneficio tangibile (poiché la differenza tra un miliardo di anni e cento miliardi di anni non è significativo in termini pratici).

Inoltre, come per RSA vs AES, questa è la natura della crittografia simmetrica contro asimmetrica. In parole semplici, con la crittografia simmetrica (dove c'è una chiave condivisa), non c'è nulla da cui iniziare a indovinare, quindi è molto difficile. Per la crittografia asimmetrica come RSA, stai divulgando un'informazione (la chiave pubblica) che è correlata alla chiave di decrittazione (la chiave privata). Mentre la relazione è "molto difficile" da calcolare, è molto più debole di non avere alcuna informazione su cui lavorare. Per questo motivo, le chiavi di dimensioni maggiori sono necessarie per rendere più difficile il problema di ottenere una chiave privata da una chiave pubblica, mentre si cerca di limitare la difficoltà dei problemi matematici relativi alla crittografia e alla decrittografia.

    
risposta data 13.12.2012 - 15:09
fonte
7

In un certo senso, esistono già algoritmi che utilizzano tali chiavi "follemente grandi". Si chiama one-time pad . Nessuno li usa veramente nella pratica, tuttavia, poiché richiedono una chiave per la lunghezza del messaggio che si desidera crittografare e il materiale chiave non può mai essere riutilizzato (a meno che non si desideri che il testo cifrato diventi banalmente irrinunciabile). Dato che lo scopo della crittografia è convertire un grande segreto (il testo in chiaro) in un piccolo segreto (la chiave), gli OTP sono utili solo in scenari molto specifici e altamente specializzati. Potresti anche trasmettere il testo in chiaro in modo sicuro, perché avrai bisogno di un canale di trasmissione altrettanto sicuro per il materiale della chiave.

In tutta onestà, le OTP hanno un caso d'uso specifico. Cioè, quando hai bisogno di sicurezza dimostrabile in un ambiente in cui hai accesso a un canale di comunicazione sicuro a un certo punto, ma devi trasmettere un messaggio in sicurezza in un secondo momento.

L'OTP è provabilmente sicuro perché correttamente usato e con materiale chiave generato correttamente, qualsiasi testo in chiaro decrittografato è ugualmente probabile, e nulla su una parte del materiale chiave (dovrebbe) fornire informazioni su altre parti del materiale chiave o come decodificare altre parti del messaggio. In teoria è facile, ma terribilmente difficile da attuare nella pratica. Tutt'al più cerchi segreti militari di alta qualità o possibilmente .

Per la maggior parte delle persone, da 128 a 256 bit simmetrici o da 2048 a 4096 bit (assumendo qualcosa come RSA) le chiavi asimmetriche sono abbastanza numerose, per ragioni già descritte da Rell3oT , Alexander Shcheblikin , lynks e altri. Chiunque voglia attaccare una chiave equivalente a 256 bit attaccherà comunque il crittosistema, non la crittografia. ( Link XKCD obbligatorio. ) Gli attacchi PRNG hanno funzionato in modo errato altrimenti correttamente implementati e crittograficamente protetti in precedenza, e uno sarebbe pazzo a pensare che è successo per l'ultima volta.

    
risposta data 13.12.2012 - 17:20
fonte
5

Aggiungendo ulteriori prove al "perché rallenta le risposte inutilmente", sembra che il tempo di esecuzione di AES non cresca più velocemente di RSA quando la lunghezza della chiave aumenta (e RC6 cresce ancora più lentamente), ma è ancora un Il 16% di tempo di esecuzione aumenta alla doppia lunghezza della chiave, in base al link .

    
risposta data 13.12.2012 - 15:30
fonte
4

Il tempo di elaborazione è già stato menzionato. Anche in questo senso il tempo necessario per generare una chiave RSA dovrebbe essere menzionato separatamente, poiché è MOLTO più costoso per le chiavi più lunghe, poiché è necessario trovare numeri primi di circa la metà della dimensione della chiave RSA desiderata.

Un altro argomento è lo spazio, i. e. la quantità di dati generati. I cifrari asimmetrici e simmetrici operano su blocchi. Anche una firma su un byte ha bisogno del numero di bit della chiave RSA, i. e. 256 byte per una chiave da 2048 bit. Stessa situazione con le dimensioni dei blocchi degli algoritmi simmetrici, che cresce anche con la lunghezza della chiave. Anche se questo non sembra un argomento a prima vista, alcuni dispositivi severamente limitati come le smart card dovrebbero gestire questo (ancora il contenitore più sicuro per la chiave privata) e ci sono molte applicazioni che devono memorizzare un sacco di firme, certificati, crittogrammi, ecc. In realtà questo è uno dei motivi per la crittografia a curve ellittiche, dal momento che sta inserendo più sicurezza in meno bit.

    
risposta data 13.12.2012 - 16:38
fonte
2

L'OP ha chiesto: " Quindi, in altre parole, quali sono le conseguenze della scelta di una chiave di cifratura troppo grande ...? " Una chiave a 256 bit è molto potente, come dimostrato dal commenti qui; tuttavia, una chiave molto sicura (che è una buona cosa) semplicemente causerà a una persona / e malvagia / e di trovare una debolezza altrove nel sistema.

    
risposta data 17.12.2012 - 15:48
fonte

Leggi altre domande sui tag