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.