RC4 Analysis and Cryptanalysis

From UIC

RC4

Infos
Author:	quequero
Email:
Website:	http://quequero.org
Date:	26/03/2007 (dd/mm/yyyy)
Level:
Language:	Italian
Comments:	Wonko the Sane was now simply waiting for the end of the world - Little realizing that it had already been and gone. Updated on: April 2007

RC4 Distinguisher

Abstract

Nel corso di questo articolo impareremo a conoscere nel dettaglio RC4, il famosissimo stream-cipher creato da Ron Rivest, analizzeremo entrambe le sue componenti (KSA e PRGA) ed useremo le conoscenze acquisite per montare degli attacchi crittanalitici contro l'algoritmo. Non sono richieste particolari conoscenze per quel che riguarda la parte di analisi, ma per quella di crittanalisi sarà necessaria un po' di dimistichezza col calcolo combinatorio e con il calcolo delle probabilità.

RC4

RC4 è un algoritmo crittografico creato nel 1987 da Ron Rivest, uno dei padri fondatori della RSA Security. Rimase un segreto industriale fino a 1994 quando un anonimo benefattore pubblicò in formato anonimo l'algoritmo sul famigerato NG sci.crypt. Questa versione di RC4 venne rinominata subito ARC4, se vi piace potete leggerla Arcfour, la A sta per alleged ovvero "presunto", dal momento che la RSA in effetti non ha mai rilasciato l'algoritmo in maniera ufficiale. La seconda ragione è semplicemente che RC4 è un marchio registrato di RSA, per cui si è pensato bene di usare un nome libero da royalties.

Stream Ciphers

RC4 è un "semplicissimo" generatore di numeri pseudo-casuali, ovvero un PRNG (Pseudo-Random Number Generator), vale a dire che dato un seed in ingresso è in grado di produrre una serie numerica univoca, e che ad un'analisi statistica appare come una serie di numeri generati in maniera casuale. La differenza tra un PRNG ed un RNG (Random Number Generator) è che il primo riproduce la stessa sequenza di numeri pseudo-casuali se il seed (la password) utilizzato è lo stesso, mentre il secondo produrrà continuamente una serie differente di numeri... Senza considerare che un RNG reale non ha bisogno di alcun seed.
Ma a cosa serve un generatore di numeri casuali, e perché è utile in crittografia? La risposta è semplice: se effettuiamo lo XOR tra i numeri casuali generati da RC4 ed un altro set di dati, ad esempio un documento, otterremo un terzo set di dati che sarà indistinguibile da un flusso di dati casuali. Mi spiego meglio, poniamo che:

• R = {r₁, r₂, r₃, ... , r_n} siano n byte casuali generati da RC4
• P = {p₁, p₂, p₃, ... , p_n} siano n byte che fanno parte di un nostro testo
• C = {c₁, c₂, c₃, ... , c_n} siano gli n byte risultanti dalla cifratura di P con R

La cifratura (e la decifratura) saranno semplicemente il risultato di questa operazione:

• C = R ^ P

Ovvero ogni byte di R viene xorato (ho usato il simbolo: ^) con P in modo da ottenere un byte cifrato C.
Se conoscete le proprietà dello Xor (e se non le conoscete siete obbligati a leggere la mia introduzione allo Xor) saprete anche che:

• A ^ B = C
• C ^ B = A
• C ^ A = B

Per cui ripetendo la stessa identica operazione sull'insieme di dati cifrati C, avendo lo stesso stream R di dati casuali, saremo in grado di invertire la crittografia per riottere i dati originali:

• C ^ R = P

Questo procedimento di cifratura byte-a-byte (ma potrebbe anche essere bit-a-bit) viene utilizzato principalmente da quella famiglia di algoritmi denominati: stream-ciphers, ovvero cifrari a flusso. L'altra metà del cielo crittografico è rappresentata dai block-ciphers, ovvero cifrari a blocchi che invece di cifrare un byte per volta ne cifrano un blocco (128bit, 256bit etc...).
Ma questa non è l'unica differenza, RC4 infatti può benissimo operare su word più ampie o anche più piccole, se opera sui singoli byte è soltanto perché in questo modo è ottimizzato per le CPU attuali, ma possiamo senza problemi ingrandire o rimpicciolire sia l'array di stato che gli indici. La differenze più importanti sono in effetti queste:

1. Gli stream-cipher sono tempo-varianti, ovvero generano keystream che evolve man mano che si procede con la cifratura (in maniera indipendente dal testo da cifrare), ad esempio RC4 aggiorna il suo stato interno ogni volta che richiediamo un byte di keystream
2. Gli stream-cipher sono simmetrici: per decifrare il testo basta xorare il keystream con i dati. Per decifrare il testo basta generare lo stesso keystream, e quindi xorarlo con i dati cifrati per riottenere quelli in chiaro.

Mentre i block-cipher hanno le seguenti caratteristiche:

1. Sono tempo-invarianti, ovvero il loro stato interno non dipende dal numero di richieste di cifratura che vengono fatte.
2. Sono asimmetrici, nella maggior parte dei casi le routine di cifratura e decifratura sono differenti. Nel caso delle Reti di Feistel le routine sono le stesse, ma percorse in senso inverso (dalla prima all'ultima nella cifratura, e dall'ultima alla prima nella decifratura).

RC4 è chiaramente uno stream-cipher, quindi a parità di seed otterremo sempre lo stesso stream casuale, e saremo quindi in grado di cifrare e decifrare dati a nostro piacimento.
Se siete vagamente avvezzi alla crittografia, avrete intuito una notevole somiglianza con gli OTP (One Time Pad), ovvero quegli algoritmi che utilizzano una chiave generata in maniera assolutamente casuale, lunga quanto i dati in chiaro, per eseguire la cifratura tramite Xor. In questo caso la comodità di RC4 è notevole, per cifrare un file di 1Gb con un OTP avremmo bisogno di una chiave lunga 1Gb, con RC4 abbiamo bisogno di una password lunga solo qualche carattere per generare uno stream lungo quanto vogliamo... Un vantaggio non da poco che, come ci insegnano gli OTP, ha però i suoi drawbacks.
Ora che sappiamo come funziona uno stream-cipher e in cosa consista la cifratura, passiamo alla spiegazione dettagliata di RC4.

RC4... In dettaglio

Prima di poter utilizzare RC4 è necessario inizializzare lo stato tramite la password fornita dall'utente, e soltanto poi sarà possibile leggere il keystream prodotto. Lo stato dell'algoritmo è definito semplicemente da un box per le permutazioni, grande 256 byte e da due indici grandi un byte ognuno (vi ricordo di nuovo che possiamo ingrandire o rimpicciolire, in maniera concorde, sia la box che i contatori), l'equivalente C, inserito in una struttura, è il seguente:

Il box S contiene una permutazione di tutti i byte, sappiamo che un byte è composto da 8-bit che possono assumere solo due valori: 0 o 1. Se la matematica non ci tradisce, allora un byte può avere soltanto: 2^8 - 1 = 255 stati diversi, quindi un byte potrà assumere valori che vanno da 0 a 255, e non oltre.
Una permutazione non è altro che un modo di combinare un gruppo di oggetti, per cui una permutazione di byte sarà semplicemente uno dei tanti modi possibili di combinare questa serie lunga 256 byte, ad esempio:

• 0 1 2 3 4...
• 0 2 1 4 3...
• 1 4 3 2 0...

Sono delle permutazioni... In quante sequenze uniche è possibile permutare un gruppo di 256 byte? Parecchie: 256!, cioe' 256 fattoriale, ovvero: 256 * 255 * 254 * 253 etc... 256! = 8 * 10⁵⁰⁶, un numerello decisamente interessante, tenetelo a mente.
Gli altri due indici, che come vedete sono definiti come unsigned char, quindi grandi 1 byte, potranno assumere valori che vanno da 0 a 255. Adesso che sappiamo cosa descrive lo stato interno dell'algoritmo, passiamo alla spiegazione dell'algoritmo di inizializzazione della S-box.

KSA (Key Scheduling Algorithm)

La fase di inizializzazione viene portata a termine in due stage, nel primo la S-box viene inizializzata con la permutazione identità, ovvero la permutazione naturale:

• 0 1 2 3 4 5... 255

Ecco il codice del primo stage, per semplicità tralascio il codice che alloca la memoria e che inizializza alcune variabili:

Il codice è davvero immediato, vengono inizializzati i due contatori presenti nella struttura che descrive lo stato interno dell'algoritmo, e poi viene inizializzata la S-box come già detto in precedenza. Il secondo stage è decisamente più interessante:

Questa seconda fase inizializza la S-box con una permutazione univoca basata sulla password inserita dall'utente, che come possiamo vedere può esser lunga da 1 a 256 byte. È chiaro dunque il ruolo cruciale giocato dalla password, che aggiunge entropia alla permutazione della S-box. Notiamo anche che ogni valore di S[] viene scambiato almeno una volta per loop, magari anche con se stesso, per cui l'effetto valanga (una piccola variazione della password, anche di un solo bit, causa un grosso cambiamento nell'ordine della permutazione) è decisamente rapido anche grazie al fatto che l'operazione di swap è altamente non-lineare. Possiamo tradurre in pseudo-codice questa prima fase di inizializzazione dello stato interno dell'RC4:

Ovviamente:

• K[] è l'array che contiene la chiave
• l è la lunghezza della chiave

Passiamo ora all'analisi dell'algoritmo per la generazione del keystream.

PRGA (Pseudo-Random Generation Algorithm)

L'algoritmo per la generazione del keystream è in realtà estremamente simile al KSA, vediamolo prima in C:

E poi nel solito pseudo-codice:

Il codice in se non è complesso e questo lo rende meraviglioso (almeno ai miei occhi :)), ma l'eleganza è una dote naturale di Rivest, come vedremo in seguito nell'analisi di RC6. Quello che accade è semplice: i esegue un loop continuo ed assume valori che vanno da 0 a 255, il valore di j viene invece influenzato dal valore presente nella S-box, che ricordiamo esser stata inizializzata tramite la nostra password, quindi sarà essenzialmente random. Lo step successivo è quello di aggiornare lo stato della S-box scambiando tra loro S[i] e S[j], quindi viene generato il byte del keystream che si ottiene sommando in modulo i due valori appena swappati, ed utilizzando questo indice per prelevare il rispettivo valore dalla S-box:

Sicurezza di RC4

Fino a pochi anni fa questo algoritmo era ritenuto sicuro, principalmente perché la sua semplicità di design non aveva creato problemi di analisi, e la dimensione del suo vettore di stato aveva reso inapplicabili molti degli attacchi utilizzati al tempo.
I primi segni di cedimento sono stati evidenziati nel 1995 da Roos¹ che riuscì a trovare una classe di chiavi particolarmente deboli (la sicurezza veniva ridotta di 5-bit, quindi usando una chiave di 40-bit era come se se ne stesse usando una di 35) e poi di nuovo nel 2000, quando Fluhrer e McGrew² resero noto un attacco che era in grado di distinguere un flusso di dati random, da uno stream RC4, con soli 2^30 byte (poco più di un giga!) di dati. Poco dopo venne presentato da Mantin e Shamir³ un secondo attacco che sotto determinate condizioni era in grado di distinguere uno stream RC4, da uno stream di dati random, in soli 2^8 byte!
Soltanto pochi mesi dopo, gli autori dei due attacchi: Scott Fluhrer, Itsik Mantin, e Adi Shamir⁴ presentarono al mondo un paper che fece luce su alcune vulnerabilità di RC4, e che immediatamente contribuì a rendere famigerato il WEP per la sua blanda sicurezza.
La prima riguarda l'algoritmo del KSA, si dimostra infatti che per una data classe di chiavi pochi bit influenzano lo stato della S-box. Nell'esempio riportato dal paper, utilizzando una chiave di 48-bit si trova che 6-bit determinano lo stato dei primi 252-bit della permutazione... Una riduzione non indifferente.
Dallo studio degli OTP abbiamo imparato che non si deve per nessun motivo riutilizzare due volte lo stesso keystream, e per evitare ciò normalmente la chiave segreta viene concatenata con un vettore di inizializzazione (IV), scelto casualmente e trasmesso in chiaro, che serve semplicemente a generare un keystream sempre diverso. Conoscendo l'IV (come nel caso del WEP/WPA) possiamo, con un attacco statistico, riuscire a derivare i byte della chiave utilizzata per inizializzare la S-box.
Sono state evidenziate ulteriori vulnerabilità in cui l'utilizzo di una chiave molto lunga (vicina ai 256-bit) può compromettere comunque la sicurezza dell'algoritmo. Perciò astenetevi dall'utilizzare RC4 e se proprio dovete farlo prendete questi quattro accorgimenti:

1. Utilizzate chiavi non più corte di 40-bit e non più lunghe di 128-bit (in caso: troncate la chiave).
2. Scartate sempre i primi 1024-byte di keystream prodotti, in questo modo l'attacco di complessità 2^8, visto in precedenza, non sarà più applicabile.
3. Evitate di concatenare l'IV, ma utilizzate un hash crittografico dell'IV+Password.
4. Se il primo byte della chiave sommato al secondo da 0 (in modulo 256) scartate quella chiave.

C'e' da dire che non esiste (ancora) un attacco in grado di crackare RC4 in un tempo molto inferiore a quello necessario per il bruteforce, tuttavia le vulnerabilità riscontrate possono fornire importanti informazioni sia sulla chiave utilizzata, che sui contenuti cifrati. Ma nonostante queste vulnerabilità fossero note il WEP, che è un prodotto relativamente recente, fa comunque uso di RC4 nella maniera più sbagliata possibile. Anche il protocollo SSL utilizza RC4, sebbene sia stato implementato in maniera più sicura, rispettando alcuni dei criteri che ho suggerito poco sopra.

Un po' di crittanalisi

Itsik Mantin come tesi di master (supervisionata niente poco di meno che da Shamir, la S di RSA) effettuò un'analisi approfondita di RC4 in cerca di qualche falla sfuggita, non ne trovò nessuna anche se riuscì a trovare ulteriori bias nel keystream che ora andremo ad esaminare.

Bias sul Secondo Byte di Output

Sappiamo che un byte può assumere valori che vanno da 0 a 255, quindi la probabilità che assuma casualmente un dato valore x sarà: 1/256. Il secondo byte del keystream di RC4 è affetto da un pesante bias, c'è infatti una probabilità di 1/128 che il secondo byte, data una chiave casuale, sia 0. Dimostriamo quello che stiamo dicendo, per prima cosa riprendiamo il PRGA in modo da averlo sott'occhio, e poi prendiamo carta e penna:

Supponiamo che al primo round del PRGA:

1. S[2] = 0
2. S[1] != 2

Vediamo quindi cosa accade durante il round 1, precisamente esamineremo le prime due righe del while(), i numeri in alto indicano la posizione nella S-box, quelli nelle cellette sono i numeri contenuti al relativo indice, quindi S[2] = 0 etc...:

Conosciamo i e sappiamo che j è inizialmente uguale a 0, quindi esaminiamo cosa accade dopo lo Swap() e qual'e' l'output del primo round:

Quindi X ed Y si sono appena scambiati di posto. Ma non possiamo prevedere il primo byte perché è casuale e strettamente dipendente dalla chiave.
Proseguiamo col secondo round:

Abbiamo appena dimostrato che indipendentemente da X il secondo byte di output è uguale a 0 se S[2] = 0, dimostriamo anche la necessità di avere S[1] != 2, torniamo al round di partenza:

Ed esaminiamo la prima fase per intero:

Passiamo quindi al secondo round:

In questo caso il teorema non è chiaramente valido perché lo 0 viene spostato prima di poter essere utilizzato come output, in tutti gli altri casi invece lo è. Ma a livello di probabilità quanto pesa questo bias? Lo vediamo subito applicando la formula degli eventi condizionati che abbiamo imparato tutti al corso di probabilità :). Definiamo prima un paio di cose:

• P[b2 = 0] è la probabilità di ottenere uno zero come secondo byte
• S[x] è il valore della S-box al primo round (cioe' proprio dopo il KSA)

Procediamo:

• P[b2 = 0] = P[b2 = 0 | S[2] = 0] * P[S[2] = 0] + P[b2 = 0 | S[2] != 0] * P[S[2] != 0] = 1 * 1/N + (1 - 1 /N) * 1/N = 1/N * (1 + 1 - 1/N) = 2/N - 1/N² circa uguale a 2/N

Se ancora non avete capito cosa sono 1/N e 1 - 1/N:

• Ogni 1/N chiavi otterremo come secondo byte di output uno 0, nel nostro caso l'eventualità accadrà con una probabilità di 1/256 (che è abbastanza intuitivo)
• Ma ora restano 1 - 1/N chiavi nell'insieme in cui avremo uno 0 come secondo byte con una probabilità di 1/N perché assumiamo che la distribuzione sia casuale.

In effetti vedendola così si nota la presenza di un secondo piccolo bias.... Che di fatto esiste ma, manco a farlo di proposito, dopo pochi round arriva un terzo bias che elimina tutti gli effetti del secondo (mi ricorda un po' la puntata dei Simpson dove Burns va a farsi visitare e gli trovano tutte le malattie del mondo, solo che sono talmente tante che praticamente si scannano tra di loro e Burns non ne risente per nulla ;p).
Ma torniamo a noi, provate ad aprire l'RC4 Distinguisher che trovate nello zip, avviatelo con:

Il programma genererà 2 set di 5000 keystream lunghi 1 byte (quindi quasi 10kbyte di dati), il primo usando un generatore crittografico pseudo-casuale, ed il secondo utilizzando RC4, ogni volta con una chiave di 128-bit differente e casuale. Al termine verrà stampata un'analisi dove verranno mostrate le varie distribuzioni di probabilità, quindi il programma cercherà di distinguere lo stream RC4 in base ai dati raccolti. Il secondo stream è RC4 per cui se la risposta è "Second stream seems to be from RC4" allora il riconoscimento sarà avvenuto con successo:

Ovviamente i sorgenti sono inclusi, quindi potete vedere cosa succede nel programma e come vengono calcolati i vari valori, potete compilare il programma sia su windows tramite VC++, gcc-cygwin, dev-c++, sia sulle piattaforme *nix tramite g++. Vedrete anche che 400 keystream sono sufficienti per riconoscere con un buon grado di accuratezza uno stream RC4, ma si può scendere anche fino a 200 se all'analisi si aggiunge il calcolo degli altri bias scoperti.

Attacco al Primo Byte di Output

Tra tutti gli attacchi pubblici verso RC4 il più interessante è, sotto vari aspetti, quello che consente di ricostruire la chiave partendo dalla conoscenza di una limitata parte della stessa. Ora probabilmente starete pensando: "beh è un attacco puramente accademico, perché quando mai capita che conosciamo parte della chiave segreta???"... In realtà capita spesso, dove? Nel WEP tanto per dirne una :), come abbiamo già detto è assolutamente fondamentale utilizzare keystream sempre differenti, per far ciò si utilizza un IV, cioe' un vettore di inizializzazione (casuale!) che viene combinato con la chiave per ottenere una nuova chiave segreta, grazie alla quale il keystream sarà sempre diverso, senza che l'utente debba cambiare la chiave per ogni pacchetto. L'IV se usato bene rafforza la cifratura (come accade su SSL) se usato male (WEP/WPA e migliaia di altri protocolli meno diffusi) ne mina la sicurezza in maniera impressionante.
A questo punto è lecito assumere che conosciamo parte della chiave, ad esempio nel caso del WEP l'IV viene inviato in chiaro, ed è lungo 24-bit cioe' 3 byte. Sappiamo anche che il primo byte di output dipende esclusivamente da 3 valori della S-box, infatti al termine del KSA la situazione è questa (indipendentemente se c'è un IV di mezzo o meno):

Vuol dire che il valore del primo byte dipende soltanto da tre valori della S-box: X, D e Z, più precisamente il byte Z sarà sempre il primo byte di output. In particolare Mantin definisce alcuni stati come risolti se per l'indice i valgono contemporaneamente le seguenti condizioni:

1. È maggiore o uguale di 1
2. È maggiore o uguale di S[1] (cioe' X)
3. È maggiore o uguale di X + S[X] (cioe' X + D)

Per capire il significato di queste condizioni basta guardare lo stato della S-box disegnato poco sopra. Se tutti e tre sono vere, allora esiste una probabilità pari a: e^-3 (cioe' circa il 5%) che nessuno di questi elementi (S[1], S[X], S[X+D]) parteciperà ad ulteriori swap all'interno del PRGA durante la produzione del primo byte del keystream. In tal caso potremo derivare il primo byte proprio tramite: S[1], S[X] e S[X+D], e se tutti e tre sono distinti allora sarà proprio S[X+D] il primo byte del keystream. Però il 95% delle volte questo non accade, e con il byte di output non ci facciamo niente... Senza considerare che il byte del keystream sarà stato xorato col payload del pacchetto per cifrarlo, e poi il primo byte, essendo appunto primo, viene prodotto solo una volta.
In pratica stiamo cercando di fare a botte con un gorilla avendo una mano legata al piede ed usando come arma una pistola spara elastici, giusto? Non del tutto, ecco perché:

1. Una probabilità del 5% è abbastanza forte da apparire evidente con soli 60 IV, in verità sarebbe bastata anche una probabilità molto più bassa.
2. È vero che il byte del keystream è xorato con il payload, ma noi conosciamo sempre il primo byte del pacchetto perché fa parte di LLC (benedetti protocolli ;p), sapendo il suo valore (M) e sapendo il valore del byte cifrato (C) possiamo ottenere il byte del keystream (K) semplicemente facendo: C ^ M = K, quindi non ci manca nulla.
3. Non ho capito se l'abbiano fatto di proposito o meno, ma il WEP prevede che ad ogni pacchetto RC4 venga re-inizializzato con la nuova coppia IV+Chiave... Questo significa che ogni pacchetto dati contiene sempre il primo byte di output.

Ecco che la nostra lotta con una pistola spara elastici si è trasformata in una lotta ad armi pari: noi con il Vulcan ed il gorilla... Nella nebbia spero :p.
Conoscendo l'IV possiamo iniziare ad attaccare un byte della chiave, se definiamo con K[] l'array contenente l'intera chiave (cioe' l'IV + la chiave segreta) e con I la lunghezza in word dell'IV (normalmente pari a 3), allora per attaccare il byte B, cioe' per derivare: K[I + B], dovremo cercare quegli IV che dopo il round I (I + 1 = 4) presentano le seguenti caratteristiche:

1. S_I[1] < I
2. S_I[1] + S_I[S_I[1]] = I + B

A questo punto avremo una probabilità pari a: e^-2B/N di trovarci in uno stato risolto dopo I + B round, e questo possiamo verificarlo simulando l'algoritmo su un qualunque pc con i dati appena ricavati. Ma a ben guardare (provate con carta e penna) possiamo fare un'assunzione importante sul valore di j al round I + B:

• j_{I + B} = j_{I + B - 1} + K[B] + S_{I + B - 1}[I + B]
• S_{I + B}[I + B] = S_{I + B - 1}[j_{I + B}]

Se non vi siete persi, allora facendo due conti (o come dice Mantin: con un po' di algebra) se conosciamo:

1. j_{I + B - 1}
2. S_{I + B - 1}
3. Ed il primo byte di output (che chiamiamo Out)

Per il discorso fatto sopra possiamo assumere che con buona probabilità avremo:

• K[B] = S^-1_{I + B - 1}[Out] - j_{I + B - 1} - S_{I + B - 1}[I + B]

Ma prima abbiamo detto che il 5% delle volte: Out = S_{I + B}[I + B] e quindi con un numero sufficiente di IV siamo in grado di risalire a K[B], chiaramente dovremo ripetere lo stesso procedimento per tutti i byte della chiave... Un complimento sentito a Mantin, solo dopo averci messo le mani capisco perché ha impiegato due anni per arrivare a queste 4 righe!!!
Quest'ultima parte non è stata semplice, tuttavia montare l'attacco è decisamente semplice visto che è sufficiente cercare soltanto gli IV che si presentano in una determinata forma e far fare il resto alle più semplici leggi della statistica :).
La situazione non cambia se l'IV è più lungo (anzi, con un IV di 16 byte basta osservare la metà dei pacchetti rispetto a quanti ne servono con un IV di 3 byte) o se viene accodato alla chiave. Se invece l'IV viene xorato con la chiave è comunque possibile montare un attacco.

Klein's Attack

Grazie all'attacco di Mantin (l'FMS anzi), sappiamo che preso un IV con le seguenti caratteristiche: A+3, N-1, X, esiste una forte correlazione tra il primo byte del keystream ed un byte della chiave, la probabilità è di circa 1/e. Ma Klein è riuscito a trovare, nel 2006, una forte correlazione tra i valori osservabili assunti da i ed S[(S[i] + S[j])] e lo stato interno dell'algoritmo rappresentato da j, S[i] e S[j]. Questa correlazione, come vedremo, porta immediatamente ad un secondo attacco crittanalitico. Prendiamo l'ultima del PRGA, ovvero:

E dividiamola in due stage:

Assumiamo che lo stato interno della S-box sia una distribuzione uniforme, ovvero che non ci siano bias e che ogni byte abbia una probabilità P = 1/n di apparire in una determinata posizione, allora dal primo teorema di Klein possiamo dire che:

• P(S[j] + S[k] = i mod n) = 2/n
• P(S[j] + S[k] = i mod n | S[j] = x) = 2/n per tutti gli x da 0 a n - 1

E per ogni c != i abbiamo che:

• P(S[j] + S[k] = c mod n) = (n - 2)/n(n - 1)
• P(S[j] + S[k] = c mod n | S[j] = x) = (n - 2)/n(n - 1) per tutti gli x da 0 a n - 1

Nelle implementazioni classiche di RC4 n = 256, in più abbiamo visto che la distribuzione dello stato interno non è perfettamente casuale, per cui il teorema appena visto lo possiamo considerare come una buona approssimazione, se volete la dimostrazione allora fate riferimento al paper originale, perché è inutile riportarla anche qui.
Riprendiamo nuovamente il KSA e vediamo cosa succede nel primo step:

Durante il primo step vediamo che j assume questo valore:

• j = 0 + S[0] + K[0] = S[0] + K[0] = K[0]

Poi c'è lo swap, quindi:

• S[i] = S[K[0]]
• S[j] = S[0] = 0

Nel secondo step:

• j = K[0] + S[1] + K[1]
• S[j] = S[1]

Quindi possiamo dedurre il valore di S[1] al secondo step:

• S[1] = K[0] + S[1] + K[1] = K[0] + K[1] + 1

Questo è sempre vero ad eccezione di 4 casi:

1. K[0] = 1, K[1] = 0: allora S[1] = 0
2. K[0] = 1, K[1] != 0, n - 1: allora S[1] = K[0] + K[1]
3. K[0] != 1, K[1] != n - 1: allora S[1] = 0
4. K[0] != 1, K[0] + K[1] = n - 1: allora S[1] = K[1]

Esaminiamo ora il caso in cui l'IV è accodato alla chiave, per un K[0] fissato, il valore di S[1] è funzione di K[1], ed è facilissimo da ricavare. In tutti gli step successivi S[1] non verrà mai cambiato, a meno che j non diventi uguale ad 1, e come abbiamo visto in precedenza, la probabilità che questo accada durante uno step è di: 1 - 1/n. A questo punto possiamo assumere che se la chiave è lunga n, allora la probabilità che S[1] non cambi è pari a: (1 - 1/n)^n-2 che è circa uguale a 1/e. Per chiavi più corte questa probabilità non è valida ma varia leggermente, quindi assumiamo 1/e soltanto come una buona approssimazione di cio' che può accadere. Ora sappiamo che il valore di S[1] dipende da K[0] e K[1] con la probabilità appena calcolata, e vogliamo applicare il teorema di Klein. Definiamo come S[k] il valore S[S[i] + S[j]]] che corrisponde al byte di output al termine del PRGA, e come abbiamo enunciato prima:

• S[j] = 1 - S[k] mod n con una probabilità di 2/n

E quindi possiamo fare una nuova stima statistica:

• P(t = 1 - S[k] mod n) = 1/e * 2/n + (1 - 1/e) * (n - 2)/n(n - 1) = 1.36/n

Il secondo addendo, se non fosse chiaro, indica la probabilità che S[1] != K[0] + K[1] + 1.

Procedura di attacco
Osserveremo quindi il primo byte x_i del keystream prodotto da RC4 e calcoleremo t_i = 1 - x_i e sapremo che di tutti i t quelli che assumono il valore corretto per il recupero della chiave sono circa 1.36/n, tutti gli altri valori avranno una frequenza di 1/n o minore. Ma quanti IV dobbiamo osservare per risalire alla chiave? Klein ha risolto numericamente il problema ed ha trovato che è necessario ottenere 25.000 IV per un recupero corretto, e questo rappresenta un notevole miglioramento rispetto all'FMS che ne richiedeva 1.000.000. Ora sappiamo come recuperare K[0] e K[1], ma possiamo procedere analogamente con tutti gli altri byte, ad esempio per trovare K[2] troveremo che esiste una sola funzione f tale che t = f(K[0], K[1], K[2]) ed è facile da calcolare, poi riapplicando il teorema di Klein possiamo trovare il byte a cui siamo interessati, e così via per tutti i restanti byte. Questo approccio è valido sia quando l'IV precede la chiave, sia quando l'IV segue la chiave, anzi il procedimento appena illustrato è ancora più semplice da applicare quando l'IV è anteposto alla chiave (ovvero nella maggior parte dei casi) perché già conosciamo K[0..2].
Klein prosegue nella descrizione di questo attacco in modalità cipher-text only, ovvero quando non siamo in grado di risalire al primo byte del keystream, in questo caso possiamo comunque scoprire la chiave ascoltando, nella maggior parte dei casi, 1.000.000 di pacchetti, come nel caso di FMS ma in questo caso assumiamo di non conoscere il keystream.

Conclusioni

RC4 è un algoritmo di indubbia eleganza e semplicità, tuttavia quest'ultimo fattore lo rende vulnerabile a quegli attacchi che abbiamo visto fin'ora. In realtà il keystream prodotto presenta molti altri bias, l'utilizzo di chiavi lunghe è sconsigliato dal momento che chiavi lunghe simili, generano anche keystream simili, e l'algoritmo ha una bassa resistenza ai related key attacks. Esistono anche svariate classi di chiavi deboli, e stati in cui RC4 non può mai trovarsi. Con questo non voglio dire che sia inusabile, ma va sicuramente utilizzato seguendo i consigli dati nella fase di analisi, e dove possibile andrebbe sostituito con algoritmi più recenti e più sicuri.
Secondo le teorie attuali sembra che non sia possibile creare stream-cipher più sicuri di un block-cipher, per cui RC4 potrebbe anche essere l'ultimo stream-cipher davvero importante che vedremo nel corso dei prossimi anni.

Bibliografia

• A. Roos. A class of weak keys in the RC4 stream cipher, 1995.
• Scott Fluhrer, David A. McGews, Statistical analysis of the alleged RC4 keystream generator, 2000.
• I. Mantin and A. Shamir. A practical attack on broadcast RC4, 2001.
• Scott Fluhrer, Itsik Mantin, and Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4, 2001.