Usa più computer per una forza bruta più veloce [duplicato]

27

Ultimamente ho visto Mr. Robot e non riesco a smettere di pensare perché è stato così difficile decifrare i file crittografati usando la crittografia AES con una chiave a 256 bit.
Diciamo che l'unico metodo per trovare la chiave è attraverso la forza bruta.
Non possiamo impostare un computer per la forza bruta a partire dalla prima chiave possibile, e un altro per iniziare dall'ultima chiave possibile, e forse alcuni computer per provare i tasti nel mezzo?
Non ridurrebbe drammaticamente il tempo?

    
posta Mero55 05.03.2016 - 17:16
fonte

3 risposte

70

Certo è possibile, ma in realtà non aiuta. Il numero di possibilità è troppo grande.

Considera che una chiave a 256 bit ha 2 valori 256 possibili. Questo è 12 x 10 76 , o 12 seguiti da 76 zeri. Se generosamente supponiamo che un computer possa testare un trilione (cioè 10 12 ) chiavi possibili al secondo, e che abbiamo un trilione di computer (da dove li otterremo?) Eseguendo la ricerca chiave, impiegherà 12 secondi 10 76 / (10 12 ✕10 12 ) per cercare l'intero spazio delle chiavi. Sono 12 secondi 10 52 . Poiché ci sono solo 3.155.760.000 secondi in un secolo, ci vorranno approssimativamente 4 x 10 43 secoli per provare tutte le possibili chiavi. C'è una probabilità del 50% che trovi la chiave solo per metà tempo.

È così che viene progettata la crittografia. Il numero di possibilità è troppo grande per essere spezzato nel tempo che è interessante per gli umani.

    
risposta data 05.03.2016 - 17:41
fonte
40

Ho fatto un calcolo su questo una volta. Supponiamo che AES possa essere rotto solo usando la forza bruta. Chiaramente avremo bisogno di un contatore, che conta da 0 a 2 256-1 , e in media dovrà contare fino a 2 255 . L'esecuzione di questo contatore richiede energia. Quanta energia ci vuole?

A quanto pare, qui c'è un limite termodinamico, il principio di Landauer. Ad una data temperatura, c'è una quantità minima di energia che si può impiegare per impostare un bit (1 bit di entropia), perché se non spendiamo così tanta energia, possiamo effettivamente diminuire l'entropia del sistema, che è termodinamicamente impossibile. L'energia necessaria è kT ln 2, dove k è la costante di Boltzman (1.38 × 10 -23 J / K) e T è la temperatura in kelvin. Ovviamente vogliamo farlo nel modo più economico possibile, quindi facciamo i calcoli a 3 kelvin, che è approssimativamente la temperatura della radiazione di fondo dell'universo. Non possiamo essere più cool di così senza spendere più energia per raffreddare il sistema di quanto avremmo speso a lanciare i bit! Questo attacca il costo dell'energia di lanciare un po 'a 2.87 × 10 -23 J / bit.

Ora, quanti bit flip abbiamo bisogno? La risposta sarà molto, quindi per mantenere le quantità di energia in termini comprensibili dall'uomo, vorrei semplificare il problema. Invece di risolvere AES-256, facciamo finta di risolvere AES-192, che richiede solo il conteggio fino a 2 191 . Quindi, quanti colpi di testa abbiamo bisogno? Se contiamo in binario normale, potremmo dover capovolgere più bit per incremento del contatore. Questo è fastidioso da calcolare, quindi facciamo finta di poter fare questo contatore con Codici Gray , che capovolgono solo un bit per incremento.

Incrementando un contatore 2 191 volte, a 2.87 × 10 -23 J / bit produce 9 × 10 34 J. Questo è un sacco di energia. Infatti, se vado su una delle mie pagine preferite di Wikipedia, Ordine di grandezza (energia) , noi vedi che l'energia emessa dal nostro sole ogni anno è 1.2 × 10 34 J. Esatto. L'esecuzione del contatore che sarebbe al centro del processo di interruzione di AES richiederebbe la somma totale di quasi un decennio dell'output energetico del sole. Tutto.

Ora se rivisitiamo il problema originale di AES-256, i costi energetici aumentano di 2 64 . Quindi quel contatore prenderebbe 1,6 × 10 54 J. Ancora una volta, osservando l'Ordine di Magnitudine (energia), scopriamo che l'energia di massa visibile totale nella galassia della Via Lattea è 4 × 10 58 J. Quindi, se dovessi convertire lo 0,004% dell'energia totale di massa della galassia (cioè convertire tutta la massa in energia usando E = mc 2 ), potresti eseguire un contatore che può contare da 0 a 2 255 .

Questo è il motivo per cui uno non forza mai un algoritmo crittografico moderno. Le quantità di energia richieste sono letteralmente al livello di "morte termica dell'universo".

    
risposta data 05.03.2016 - 19:59
fonte
3

Non è solo possibile, le persone lo hanno fatto con successo. Ma solo con tasti molto brevi.

distributed.net è riuscito a rompere una crittografia RC5 a 64 bit nel 2002 utilizzando una rete distribuita di computer. I computer erano per lo più PC di livello consumer di proprietà di volontari che hanno installato un programma per scricchiolare le chiavi in background. Questo faceva parte di sfida chiave segreta RSA - un contest di RSA Labs per decrittografare i messaggi crittografati con chiavi molto più brevi di quelle che useresti nel mondo reale.

"After over four years of effort, hundreds of thousands of participants, and millions of cpu-hours of work, Distributed.net has brute forced the key to RSA Security's 64 bit encryption challenge"

Hanno iniziato un altro progetto per vincere la sfida RSA 72-bit nel 2003. 13 anni dopo, stanno ancora calcolando e non hanno nemmeno testato il 4% dello spazio delle chiavi .

Ricorda che queste sono versioni estremamente semplificate di RSA. La lunghezza della chiave raccomandata per RSA-RC5 nel mondo reale è almeno 128 bit. Ogni ulteriore bit raddoppia il tempo di calcolo, quindi questi approcci distribuiti sono ancora ad anni luce di distanza dall'attacco di qualsiasi crittografia del mondo reale.

    
risposta data 07.03.2016 - 11:42
fonte

Leggi altre domande sui tag