Stream ciphers usati nel mondo reale (20 min)

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.