-
In questa sezione, voglio dare alcuni esempi di stream cipher che vengono effettivamente utilizzati
-
Inizierò con due vecchi esempi che in realtà non
-
si suppone vengano utilizzati in nuovi sistemi. Comunque, essi sono ancora piuttosto largamente utilizzati
-
e quindi voglio citarne semplicemente i nomi, in modo che voi possiate famigliarizzare con
-
questi concetti. Il primo stream cipher di cui voglio parlarvi è chiamato RC4, progettato
-
nel lontano 1987. Ve ne darò una descrizione ad alto livello e quindi
-
parleremo di alcune debolezze di RC4 e ci fermeremo lì. RC4 utilizza
-
un seme di lunghezza variabile; qui ho presentato un esempio dove sono stati utilizzati 128
-
bit come lunghezza del seme, che verrà utilizzato come chiave per lo stream cipher.
-
La prima cosa che fa, è espandere la chiave segreta di 128 but in un 2.048 bit, che
-
verranno utilizzati come stato interno per il generatore. Quindi, una volta che questa espansione è stata terminata,
-
esso esegue in pratica un loop molto semplice, dove ogni iterazione produce come
-
output un byte. Quindi, essenzialmente, voi potete far eseguire il generatore per
-
quanto tempo vogliate e generare un byte alla volta. Ora, RC4 è in pratica, come ho detto,
-
largamente popolare. Viene utilizzato in realtà piuttosto comunemente nel protocollo HTTPS.
-
In questi giorni, ad esempio, Google usa RC4 nel suo HTTPS. Viene utilizzato anche nel WEP, come abbiamo
-
discusso nell'ultima sezione, ma ovviamente in WEP esso è usato in maniera sbagliata e
-
il modo in cui viene utilizzato in WEP è assolutamente insicuro. Così, nel corso degli anni,
-
sono state trovate alcune debolezze in RC4 a, di conseguenza, si raccomanda che i nuovi progetti
-
non usino in effetti RC4, ma piuttosto un generatore pseudo-random più moderno, come
-
discuteremo verso la fine della sezione. QUindi, lasciatemi citare due delle debolezze.
-
La prima si trova (è qualcosa di bizzarro, fondamentalmente): se guardate al secondo byte
-
dell'output di RC4. Risulta che il secondo byte è leggermente polarizzato. Se RC4 fosse
-
completamente random, la probabilità che il secondo byte sia zero
-
sarebbe esattamente l'inverso di 256. Ci sono 256 possibili byte, la probabilità che
-
sia zero dovrebbe essere uno su 256. Succede invece che per RC4 la probabilità sia
-
in effetti due su 256, che significa che se usate l'output di RC4 per criptare un
-
messaggio, il secondo byte sia possibilmente non criptato del tutto. In altre parole, esso
-
sarà in XOR con zero due volte la probabilità che si suppone debba succedere.
-
Quindi, due su 256 invece che uno su 256. E, tra l'altro, dovrei dire che non c'è
-
nulla di speciale circa il secondo byte. Risulta però che anche il primo e il terzo byte
-
sono anche polarizzati. E' infatti ora raccomandato che se intendete usare RC4
-
ciò che dovreste fare è in pratica ignorare i primi 256 byte dell'output e giusto
-
iniziare usando l'output del generatore iniziando dal byt 257. La prima coppia
-
di byte risultano essere polarizzati, quindi semplicemente ignorateli. Il secondo attacco che
-
venne scoperto è che in effetti, se guardate a un output molto lungo di RC4, capita che
-
sia più facile ottenere la sequenza 00. In altre parole, è più facile
-
che otteniate sedici bit (due byte) di zero di quanto dobbiate. Di nuovo, se RC4
-
fosse completamente random, la probabilità di vedere zero, zero sarebbe esattamebte il quadrato di 1/256.
-
Risulta che RC4 è leggermente polarizzato e la polarizzazione sia il cubo di 1/256.
-
Risulta che questa polarizzazione in effetti inizi dopo che diversi GByte di dati siano stati prodotti
-
da RC4. Ma ciononostante, questo è qualcosa che può essere usato per predirre il generatore e
-
in definitiva può essere usato per distinguere l'output del generatore
-
da una vera sequenza casuale. Fondamentalmente, il fatto che zero, zero appaia più spesso
-
di quanto dovrebbe è il discriminante. E quindi nell'ultima sezione abbiamo parlato degli
-
attacchi basati su chiavi connesse che sono stati usati per attaccare WEP, che in pratica dicono che se
-
qualcuno usa chiavi che sono strettamente connesse l'una con l'altra, allora è in effetti possibile
-
recuperare la chiave principale. Quindi queste sono debolezze che sono conosciute per RC4 e quindi
-
si raccomanda che nuovi sistemi in effetti non usino RC4 e invece usino
-
generatori pseudo-casuali moderni. OK, il secondo esempio che voglio darvi è uno
-
stream cipher usato per criptare film DVD malamente scardinato. Quando comprate un DVD
-
in negozio, il film è criptato usando uno stream cipher chiamato
-
sistema di scrambling del contenuto (CSS, Content Scrambling System). CSS risulta essere uno stream cipher malamente scardinato,
-
e possiamo scardinarlo molto semplicemente. Ora voglio mostrarvi come funziona l'algoritmo di attacco.
-
Faro' in modo di mostrarvi un esempio di algoritmo di attacco, ma,
-
in effetti, ci sono molti system che fondamentalmente usano questo attacco per decrittare
-
DVD criptati. Lo stream cipher CSS è basato su qualcosa che piace
-
ai progettisti hardware. E' progettato per essere uno stream cipher che si suppone
-
sia facilmente implementabile in hardware ed è basato su un meccanismo chiamato registro di scorrimento a retroazione
-
lineare. Un registro a scorrimento con retroazione lineare è fondamentalmente un registro
-
che consiste in celle, dove ogni cella contiene un bit.
-
Ciò che succede è che ci sono rubinetti in alcune celle (non tutte), cioè certe
-
possizioni vengono chiamate "rubinetti". Questi rubinetti alimentano uno XOR e quindi
-
ad ogni colpo di clock, il registro scorre di un bit a sinistra. L'ultimo bit di sinistra viene scartato
-
e quindi il primo bit diventa il risultato di questo XOR. Potete quindi vedere che
-
questo è un meccanismo molto semplice da implementare e in hardware impiega veramente
-
pochi transistors. Giusto lo scorrimento, lo scarto dell'ultimo bit e l'aggiunta di un but
-
che diventa lo XOR di alcuni bits precedenti. Ciò che serve a questo registro è
-
fondamentalmente lo stato iniziale.
-
E questo è la base di un certo numero di stream ciphers. Qui vengono presentati alcuni esempi.
-
Come ho detto, la crittografia dei DVD usa due registri di questo tipo. Vi mostrerò come funziona tra un secondo.
-
Per quanto riguarda la crittografia GSM, ci sono algoritmi chiamati A51 e A52. E questi
-
usano tre registri di questo tipo. La crittografia Bluetooth è un algoritmo chiamato E zero. Questi sono tutti
-
stream ciphers, ed usano tutti quattro registri di questo tipo. Risulta che tutti questi cifratori sono stati scardinati malamente ed
-
in realtà non dovrebbero assolutamente essere considerati attendibili per traffico cifrato, ma sono tutti
-
implementati in hardware, quindi è alquanto difficile oggi cambiare ciò che viene fatto in hardware.
-
Ma il più semplice di tutti, CSS, in realtà ha un attacco carino che funziona su di esso, quindi lasciatemi
-
descrivere come funziona questo attacco. Prima di tutto vediamo come effettivamente funziona CSS.
-
la chiave di CSS è di cinque bytes, cioè 40 bits (5 volte 8 bit è 40 bit).
-
La ragione per cui hanno dovuto limitarsi a solo 40 bitsè che la cifratura dei DVD è stata progettata
-
in tempi in cui la legislazione per l'esportazione negli US permetteva solo di esportare algoritmi
-
di cifratura dove la chiave fosse solo di 40 bits. Quindi i progettisti di CSS
-
erano già limitati a chiavi molto, motlo corte. Solo 40 bits. Quindi il loro progetto funziona
-
in questo modo. Fondamentalmente, CSS usa due registri a scorrimento. Uno è a 17 bit. In altre parole
-
il registro contiene 17 bit. E l'altro è di 25 bit.
-
un pò più lungo, 25 bit. E il modo in cui questi registri vengono alimentati
-
è il seguente. Quindi la chiave per la cifratura, fondamentalmente è come segue.
-
Si inizia con un uno, che viene concatenato con i primi due byte
-
della chiave. E questo è lo stato iniziale del registro.
-
Il secondo registro fondamentalmente viene inizializzato nello stesso modo.
-
uno concatenato con gli ultimi tre byte della chiave. E questo
-
viene caricato nello stato iniziale del registro. Potete vedere che i primi due byte
-
sono 16 bit, più il primo 1, che sono 17 bit in tutto, mentre il secondo
-
registro è di 24 bit più un 1 che fa 25 bit. Notate che abbiamo usato tutti i cinque bit
-
della chiave. Quindi questi registri vengono fatti scorrere per otto cicli, generando
-
8 bit di output. Quindi questi bit vanno un un sommatore che fa in pratica una
-
somma modulo 256. Corretto, questa è un blocco di addizione modulo 256. C'è inoltre un'altra cosa
-
che succede. Infatti Infatti... viene aggiunto anche una parte derivante
-
dal blocco precedente. Ma questo non è importante. Questo è un dettaglio che non è rilevante.
-
OK, qundi in ogni blocco notate che facciamo un'addizione modulo 256
-
e stiamo ignorando la parte derivante dal blocco precedente, che però è semplicemente l'addizione di uno 0 o un 1
-
all'addizione del blocco successivo. OK? Quindi in pratica questo produce un byte per ciclo.
-
OK, quindi questo byte viene ovviamente usato, messo in XOR con il relativo
-
byte del film che è stato criptato. OK, quindi questo è uno stream cipher molto semplice e
-
impiega molto poco hardware per essere implementato. Viene eseguito velocemente, persino su
-
hardware molto economico e può criptare film. Risulta che questo sia facilmente scardinabile in un tempo
-
proporzionale a 2 alla 17. Lasciatemi mostrare come.
-
Supponiamo che voi intercettiate il film. Quindi abbiamo un
-
film criptato e voi volete decrittarlo. Quindi, diciamo che questo e completamente criptato in modo
-
che non abbiate alcuna idea di cosa ci sia dentro. Comunque, si da il caso che, poichè
-
la cifratura DVD usa file MPEG, succede che voi sappiate il prefisso del
-
file in chiaro, diciamo una ventina di byte. Bene, sappiamo che se fate lo XOR
-
di queste due cose insieme, cioè in altre parole, fate lo XOR qui,
-
Ciò che ottenete è il segmento iniziale del PRG. Quindi voi ottenete
-
i primi 20 byte dell'output del CSS, l'output di questo PRG. OK, quindi
-
ora questo è ciò che faremo. Abbiamo i primi 20 bytes dell'output. Ora
-
faremo ciò che segue. Tentiamo tutti i 2^17 possibili valori del primo
-
registro. OK? Quindi tutti i 2^17 valori. Per ogni tentativo, cioè
-
per ognuno di questi 2^17 valori iniziali del registro, faremo scorrere
-
i registri per venti byte, ok? Quindi genereremo 20 byte di output da questo
-
primo registro, assumendo... per ognuno dei 2^17 possibili settaggi.
-
Ora, considerate che conosciamo l'output completo del sistema CSS, Quindi ciò cjhe possiamo fare è
-
prendere questo output che conosciamo e sottrarlo dai venti byte che
-
abbiamo ottenuto dal primo registro. Se in effetti il nostro tentativo per lo stato iniziale del primo registro
-
è corretto, ciò che dovremmo ottenere sono i primi 20 byte del
-
secondo registro. Giusto? Perchè questo è per definizione l'output del sistema CSS.
-
Ora, risulta che guardando la sequenza di 20 byte, è molto semplice
-
dire se questa sequenza di 20 byte è uscita dal secondo registro oppure no. Se non lo è
-
sappiamo che il nostro tentativo per il primo registro a 17 bit era
-
incorretto e quindi andiamo avanti con il prossimo tentativo per il registro a 17 bit e
-
quindi quello successivo e così via. Finchè alla fine indoviniamo lo stato iniziale corretto
-
pòer il registro a 17 bit e quindi siamo arrivati, vedremo che
-
i 20 byte che otteniamo come output candidato dal registro a 25 bit è
-
in effetti un possibile output per il registro a 25 bit. E ora, non solo abbiamo
-
imparato il corretto stato iniziale per il registro a 17 bit, noi avremo anche
-
imparato il corretto stato iniziale del registro a 25 bit. E quindi possiamo predirre l'output
-
rimanente del CSS e, ovviamnte, usando questo, possiamo decrittare il resto del
-
film. Possiamo recuperare la rimanente parte in chiaro. Ok. Questo è ciò
-
di cui abbiamo parlato prima. L'ho spiegato un pò velocemente, ma, spero, chiaramente.
-
Stiamo per fare un esercizio come compito a casa su questo tipo di stream ciphers
-
e voi potrete capire come questi algoritmi di attacco
-
funzionano. Dovrei dire che ci sono diversi sistemi open-source oggi che in realtà
-
usano questo metodo per decrittare dati criptati con CSS. OK, quindi ora che abbiamo visto due
-
esempi deboli, spostiamoci verso esempi migliori, e in particolare
-
i generatori pseudo-random che vengono da quello che viene chiamato il Progetto eStream. Questo è un
-
progetto che si è concluso nel 2008 e che ha qualificato cinque diversi stream
-
cipher, ma qui voglio presentarne solo uno. Prima di tutto, i parametri per
-
questi stream cipher sono un pò diversi da quelli a cui siamo abituati. Questi
-
stream cipher di norma hanno un seme. Ma inoltre hanno anche ciò
-
che viene chiamato un nonce e vedremo come viene usato un nonce tra giusto un minuto. Quindi,
-
si prendono due input, un seme e un nonce. Vedremo come viene usato un nonce tra
-
giusto un secondo. Si produce ovviamente un output molto grande, quindi n è ora
-
molto, ma molto più grande di s. Ora, quando dico nonce, cosa intendo è un valore che non si ripeterà
-
mai finchè rimane fissata la chiave. Spiegherò tutto questo tin maggiori
-
dettagli tra giusto un secondo. Ma per ora, pensate solo ad esso come ad un valore unico che mai
-
si ripeta finchè la chiave è la stessa. E quindi, ovviamente, una volta che avete questo PRG (generatore pseudo-causale)
-
potrete cifrare e otenere uno stream cipher come prima, eccetto che ora, come vedete, il
-
PRG prende come input sia la chiave che il nonce. E la proprietà del nonce è
-
che la coppia (k,r), cioè (chiave,nonce) non si ripete mai. Non viene
-
mai usata più di una volta. Quindi la conclusione è che potete riusare la chiave,
-
riusare la chiave, perchè il nonce rende la coppia unica, perchè k ed r sono usati
-
solo una volta. Cioè sono unici. Ok, quindi questo nonce è qualcosa come uno stratagemma simpatico che
-
ci risparmia la necessità di utilizzare una nuova chiave ogni volta. ok, l'esempio particolare
-
che proviene da eStream che voglio mostrarvi è chiamato Salsa20. E' uno
-
stream cipher che è stato progettato per implementazioni sia hardware che software.
-
E' piuttosto interessante. Capite che alcni stream ciphers sono
-
progettati per implementazioni software, come RC4. Tutto ciò che fa è progettato per rendere
-
l'implementazione software molto veloce, mentre altri stream ciphers sono progettati
-
per l'hardware, come il CSS, usando un registro di scorrimento che è particolarmente progettato per rendere
-
l'implementazione hardware molto economica. La cosa interessante in questo senso è che
-
esso è progettato in modo che sia semplice da implementare in hardware e che la sua
-
implementazione software sia anche molto veloce. Quindi lasciatemi spiegare come funziona Salsa. Bene, Salsa
-
prende chiavi a 128 o a 256 bit. Spiegherò solo la versione di Salsa a 128 bit.
-
Quindi, questo è il seme. E prende anche un nonce, come prima, che
-
risulta essere di 64 bit. Quindi genera un output lungo. Ora, come funziona
-
realmente? Bene, la funzione stessa è definita nel modo seguente. Fondamentalmente, data
-
la chiave e il nonce, esso genererà una sequenza pseudorandom molto lunga.
-
cioè lunga quanto necessario. E lo farà usando questa funzione che chiamerò
-
H. Questa funzione H prende tre input. Fondamentalmente la chiave, il seme,
-
il nonce r e un contatore che incrementa passo passo. Cioè va
-
da zero a uno, due, tre, quattro finchè serve. Ok? Quindi, fondamentalmente,
-
calcolando questo H su questi k ed r, ma usando questo contatore incrementale, possiamo ottenere
-
una sequenza che è lunga quanto ci serve. Quindi, tutto ciò che devo fare è descrivere come funziona questa funzione
-
H. Ora, lasciatemi fare questo per voi. Il modo in cui funziona è il seguente. Bene, partiamo
-
espandendo gli stati in qualcosa di piuttosto largo che è lungo 64 byte
-
e lo facciamo nel modo seguente. Fondamentalmente prendiamo una costante all'inizio, quindi
-
c'è una tao di zero, fatta di quattro bytes, cioè è una costante di quattro byte. Le specifiche di Salsa vi
-
danno il valore per questa tao di zero. Quindi mettiamo k in 16
-
bytes. Quindi mettiamo un'altra costante. Di nuovo di quattro byte. E, come ho detto,
-
la specifica specifica anche questa costante fissa. Quindi mettiamo
-
il nonce, che è di otto byte. Quindi mettiamo l'indice. Questo è il contatore zero,
-
uno, due, tre, quattro che è di nuovo fatto da otto byte. Quindi mettiamo un'altra costante
-
tau due, che sono altri quattro byte. Quindi mettiamo la chiave di nuovo, che fanno
-
altri sedici byte. E quindi infine mettiamo la terza costante, tau tre, che sono
-
altri quattro byte. Ok, quindi, come ho detto, se sommato tutto questo, vedete che ottenete 64 byte.
-
Quindi, fondamentalmente, abbiamo sepanso la chiave e il nonce e il contatore fino a 64
-
byte. Fondamentalmente la chiave viene ripetuta due volte. E quindi quello che facciamo è applicare
-
la funzione. Chiamerò questa funzione h piccolo. Ok, qindi applichiamo questa funzione h piccolo.
-
E questa è una funzione che è uno a uno, quindi mappa 64 byte in 64 byte. E'
-
una funzione completamente invertibile, ok? Quindi, questa funzione h è, come ho detto, una
-
funzione invertibile. Quindi, dato l'iinput voi ottenete l'output e dato
-
l'output voi potete ritornare all'input. Ed è progettata specificatamente in questo modo, quindi è a - facilmente
-
implementabile in hardware e b- su un x86 è estremamente facile da implementare, perchè
-
x86 ha questo insieme di istruzioni SSE2 che supporta tutte le operazioni di cui avete bisogno per fare
-
questa funzione. Ed è molto, molto veloce. Di conseguenza, Salsa è uno stream cipher molto veloce.
-
E queste operazioni vengono fatte ancora e ancora. Quindi si applica la funzione
-
h ancora e si ottiengono altri 64 bytes. E via di seguito, fondamentalmente
-
lo si fa dieci volte. ok, l'intera operazione è quindi ripetere 10 volte, cioè applicare
-
10 volte la funzione h. Quindi, di per se stessa, non è in effetti molto random.
-
Non sembra random perchè, come abbiamo detto, H è completamente invertibile. Quindi dato
-
l'output finale, è mlto semplice invertire h e quindi tornare indietro agli input originali
-
e quindi verificare che l'input ha la struttura corretta. Quindi si fa un'altra
-
cosa, che è fondamentalmente un XOR tra gli input e gli output finali. In realtà,
-
scusate, non è uno XOR. è in effetti un'addizione. Quindi fate un'addizione parola per parola.
-
Quindi se ci sono 64 byte, fate un'addizione parola per parola a passi di 4 byte
-
e alla fine ottenete l'output di 64 byte e questo è tutto. Questo è l'intero generatore
-
pseudo-random. Quindi questa è l'intera funzione h piccolo. E, come ho
-
spiegato, questa intera costruzione è la funzione H grande. E quindi calcolate
-
H grande incrementando il contatore I da zero, uno, due, tre in avanti. E questo
-
vi fornirà una sequenza pseudo-casuale che è lunga quanto vi serve. E
-
fondamentalmente, non ci sono attacchi significativi su questo algoritmo. Questo ha una sicurezza che è
-
molto vicina a 2 alla 128. edremo cosa significa questo più tardi.
-
E' uno stream cipher molto veloce, sia in hardware che in software. E, per quanto possiamo dirne,
-
esso sembra impredicibile quanto richiesto per uno stream cipher. Quindi
-
dovrei dire che il progetto eStream effettivamente ha cinque stream cipher come
-
questo. Ho scelto Salsa20 perchè pernso sia il più elegante. Ma posso darvi
-
alcuni parametri di performance. Potete vedere che questi sonoparametri di performance su
-
una macchina x86 a 2.2 GHz. E potete vedere che RC4 è effettivmente
-
il più lento. Perchè essenzialmente, beh esso non sfrutta
-
l'hardware. Esso fa solo operazioni su byte. E quindi ci sono molti cicli sprecati
-
che non vengono utilizzati. Ma i candidati eStream, sia Salsa che l'altro dandidato
-
chiamato Sosemanuk, questi sono i finalisti eStream. Questi sono
-
in effetti gli stream ciphers che sono stati approvati dal progetto eStream. Potete vedere che
-
hanno raggiunto una velocità significativa. Questo è 643 MB/s su questa
-
architettura, più del necessario per un video e questi sono in effetti velocità piuttosto impressionanti
-
E quindi, ora avete visto esempi di due vecchi stream ciphers che non dovrebbero più essere usati,
-
compresi gli attacchi su questi stream ciphers. Avete anche visto come sono fatti i moderni stream ciphers
-
con questo nonce. E vedete i numeri di performance per questi
-
moderni stream ciphers. Quindi se vi capita di avere bisogno di uno stream cipher potreste usare uno dei
-
finalisti del progetto eStream. In particolare potreste usare qualcosa come Salsa.