RC4 - RC4

RC4
Generale
Designer Ron Rivest ( RSA Security )
Pubblicato per la prima volta Trapelato nel 1994
(progettato nel 1987)
Dettaglio cifratura
Dimensioni delle chiavi 40–2048 bit
Dimensione dello stato 2064 bit (1684 effettivo)
turni 1
Velocità 7 cicli per byte su presunto RC4 originale Pentium
modificato su Intel Core 2: 13,9 cicli per byte

In cryptography , RC4 (Rivest Cipher 4 noto anche come ARC4 o ARCFOUR significa RC4 Presunto, vedi sotto) è un cifrario a flusso . Sebbene sia notevole per la sua semplicità e velocità nel software, sono state scoperte molteplici vulnerabilità in RC4, rendendolo insicuro. È particolarmente vulnerabile quando l'inizio del flusso di chiavi di output non viene scartato o quando vengono utilizzate chiavi non casuali o correlate. Usi particolarmente problematici di RC4 hanno portato a protocolli molto insicuri come WEP .

A partire dal 2015, si ipotizza che alcune agenzie crittografiche statali possano possedere la capacità di violare RC4 quando utilizzate nel protocollo TLS . IETF ha pubblicato RFC 7465 per vietare l'uso di RC4 in TLS; Mozilla e Microsoft hanno emesso raccomandazioni simili.

Sono stati fatti numerosi tentativi per rafforzare RC4, in particolare Spritz, RC4A, VMPC e RC4 + .

Storia

RC4 è stato progettato da Ron Rivest di RSA Security nel 1987. Sebbene sia ufficialmente chiamato "Rivest Cipher 4", l'acronimo RC è in alternativa inteso come "Ron's Code" (vedi anche RC2 , RC5 e RC6 ).

RC4 era inizialmente un segreto commerciale , ma nel settembre 1994 una sua descrizione fu inviata anonimamente alla mailing list dei Cypherpunks . È stato presto pubblicato sul newsgroup sci.crypt , dove è stato analizzato in pochi giorni da Bob Jenkins. Da lì si è diffuso in molti siti su Internet. Il codice trapelato è stato confermato essere autentico poiché è stato riscontrato che il suo output corrisponde a quello del software proprietario che utilizza RC4 con licenza. Poiché l'algoritmo è noto, non è più un segreto commerciale. Il nome RC4 è un marchio registrato, in modo da RC4 viene spesso definito come ARCFOUR o ARC4 (che significa presunta RC4 ) per evitare di problemi di marchio. RSA Security non ha mai rilasciato ufficialmente l'algoritmo; Rivest, tuttavia, si è collegato all'articolo di Wikipedia in inglese su RC4 nelle sue note del corso nel 2008 e ha confermato la storia di RC4 e del suo codice in un suo articolo del 2014.

RC4 è diventato parte di alcuni protocolli e standard di crittografia comunemente usati, come WEP nel 1997 e WPA nel 2003/2004 per le schede wireless; e SSL nel 1995 e il suo successore TLS nel 1999, fino a quando non è stato vietato per tutte le versioni di TLS da RFC 7465 nel 2015, a causa degli attacchi RC4 che indeboliscono o violano RC4 utilizzato in SSL/TLS. I fattori principali del successo di RC4 su una gamma così ampia di applicazioni sono stati la sua velocità e semplicità: implementazioni efficienti sia nel software che nell'hardware erano molto facili da sviluppare.

Descrizione

RC4 genera un flusso pseudocasuale di bit (un keystream ). Come con qualsiasi cifrario a flusso, questi possono essere usati per la crittografia combinandoli con il testo in chiaro usando bit-wise exclusive-or ; la decrittazione viene eseguita allo stesso modo (poiché l'esclusivo-o con dati dati è un'involuzione ). Questo è simile all'one-time pad tranne per il fatto che vengono utilizzati bit pseudocasuali generati , anziché un flusso preparato.

Per generare il keystream, il cifrario fa uso di uno stato interno segreto che consiste di due parti:

  1. Una permutazione di tutti i 256 byte possibili (indicata sotto "S").
  2. Due puntatori all'indice a 8 bit (indicati con "i" e "j").

La permutazione viene inizializzata con una chiave di lunghezza variabile , tipicamente compresa tra 40 e 2048 bit, utilizzando l' algoritmo di schedulazione della chiave (KSA). Una volta completata questa operazione, il flusso di bit viene generato utilizzando l' algoritmo di generazione pseudo-casuale (PRGA).

Algoritmo di pianificazione delle chiavi (KSA)

L' algoritmo di pianificazione della chiave viene utilizzato per inizializzare la permutazione nell'array "S". "keylength" è definito come il numero di byte nella chiave e può essere compreso nell'intervallo 1 ≤ keylength ≤ 256, tipicamente tra 5 e 16, corrispondente a una lunghezza della chiave di 40 – 128 bit. Innanzitutto, l'array "S" viene inizializzato con la permutazione dell'identità . S viene quindi elaborato per 256 iterazioni in modo simile al PRGA principale, ma allo stesso tempo mescola anche i byte della chiave.

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

Algoritmo di generazione pseudo-casuale (PRGA)

La fase di ricerca di RC4. Il byte di output viene selezionato cercando i valori di S[i] e S[j] , sommandoli modulo 256 e quindi utilizzando la somma come indice in S ; S(S[i] + S[j]) viene utilizzato come byte del flusso di chiavi, K.

Per tutte le iterazioni necessarie, il PRGA modifica lo stato ed emette un byte del keystream. In ogni iterazione, il PRGA:

  • incrementi i
  • cerca l' i- esimo elemento di S , S[ i ] e lo aggiunge a j
  • scambia i valori di S[ i ] e S[ j ] quindi usa la somma S[ i ] + S[ j ] (modulo 256) come indice per recuperare un terzo elemento di S (il valore keystream K sotto)
  • quindi ORed esclusivo bit per bit ( XORed ) con il byte successivo del messaggio per produrre il byte successivo del testo cifrato o del testo in chiaro.

Ogni elemento di S viene scambiato con un altro elemento almeno una volta ogni 256 iterazioni.

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Quindi, questo produce un flusso di K[0],K[1],... che sono XOR 'ed con il testo in chiaro per ottenere il testo cifrato . Quindi testo cifrato[ l ] = testo in chiaro[ l ] ⊕ K[ l ] .

Generatori di numeri casuali basati su RC4

Diversi sistemi operativi includono arc4random, un'API originata da OpenBSD che fornisce l'accesso a un generatore di numeri casuali originariamente basato su RC4. In OpenBSD 5.5, rilasciato a maggio 2014, è arc4randomstato modificato per utilizzare ChaCha20 . Anche le implementazioni di arc4random in FreeBSD , NetBSD e libbsd di Linux usano ChaCha20. Secondo le pagine di manuale fornite con il sistema operativo, nella versione 2017 dei suoi sistemi operativi desktop e mobile , Apple ha sostituito RC4 con AES nella sua implementazione di arc4random. Le pagine man per il nuovo arc4random includono il backronym "A Replacement Call for Random" per ARC4 come mnemonico, poiché fornisce dati casuali migliori di rand() .

I nuovi generatori di numeri casuali proposti sono spesso paragonati al generatore di numeri casuali RC4.

Diversi attacchi a RC4 sono in grado di distinguere il suo output da una sequenza casuale .

Implementazione

Molti cifrari a flusso sono basati su registri a scorrimento a feedback lineare (LFSR), che, sebbene efficienti nell'hardware, lo sono meno nel software. Il design di RC4 evita l'uso di LFSR ed è ideale per l'implementazione del software, poiché richiede solo manipolazioni di byte. Utilizza 256 byte di memoria per l'array di stato, da S[0] a S[255], k byte di memoria per la chiave, da chiave[0] a chiave[k-1] e variabili intere, i, j e K. L'esecuzione di una riduzione modulare di un valore modulo 256 può essere eseguita con un AND bit per bit con 255 (che equivale a prendere il byte di ordine inferiore del valore in questione).

Vettori di prova

Questi vettori di test non sono ufficiali, ma sono convenienti per chiunque provi il proprio programma RC4. Le chiavi e il testo in chiaro sono ASCII , il flusso di chiavi e il testo cifrato sono in esadecimale .

Chiave Keystream Testo in chiaro testo cifrato
Chiave EB9F7781B734CA72A719 Testo in chiaro BBF316E8D940AF0AD3
Wiki 6044DB6D41B7 pedia 1021BF0420
Segreto 04D46B053CA87B59 Attacco all'alba 45A01F645FC35B383552544B9BF5

Sicurezza

A differenza di un moderno cifrario a flusso (come quelli in eSTREAM ), RC4 non accetta un nonce separato accanto alla chiave. Ciò significa che se una singola chiave a lungo termine deve essere utilizzata per crittografare in modo sicuro più flussi, il protocollo deve specificare come combinare il nonce e la chiave a lungo termine per generare la chiave di flusso per RC4. Un approccio per risolvere questo problema consiste nel generare una chiave RC4 "nuova" eseguendo l' hashing di una chiave a lungo termine con un nonce . Tuttavia, molte applicazioni che utilizzano RC4 concatenano semplicemente chiave e nonce; Il programma chiave debole di RC4 dà quindi origine ad attacchi chiave correlati , come l' attacco Fluhrer, Mantin e Shamir (che è famoso per aver infranto lo standard WEP ).

Poiché RC4 è un cifrario a flusso , è più malleabile dei comuni cifrari a blocchi . Se non viene utilizzata insieme a un codice di autenticazione del messaggio forte (MAC), la crittografia è vulnerabile a un attacco di capovolgimento dei bit . Il cifrario è anche vulnerabile a un attacco di cifratura a flusso se non implementato correttamente.

È degno di nota, tuttavia, che RC4, essendo un cifrario a flusso, è stato per un periodo di tempo l'unico cifrario comune immune all'attacco BEAST del 2011 su TLS 1.0 . L'attacco sfrutta una nota debolezza nel modo in cui la modalità di concatenamento di blocchi di cifratura viene utilizzata con tutti gli altri cifrari supportati da TLS 1.0, che sono tutti cifrari a blocchi.

Nel marzo 2013, ci sono stati nuovi scenari di attacco proposti da Isobe, Ohigashi, Watanabe e Morii, così come AlFardan, Bernstein, Paterson, Poettering e Schuldt che utilizzano nuovi bias statistici nella tabella delle chiavi RC4 per recuperare il testo in chiaro con un gran numero di crittografie TLS.

L'uso di RC4 in TLS è vietato dalla RFC 7465 pubblicata nel febbraio 2015.

I pregiudizi di Roos e la ricostruzione chiave dalla permutazione

Nel 1995, Andrew Roos ha osservato sperimentalmente che il primo byte del keystream è correlato ai primi tre byte della chiave e i primi pochi byte della permutazione dopo il KSA sono correlati a una combinazione lineare dei byte della chiave. Questi pregiudizi sono rimasti inspiegabili fino al 2007, quando Goutam Paul, Siddheshwar Rathi e Subhamoy Maitra hanno dimostrato la correlazione keystream-chiave e in un altro lavoro Goutam Paul e Subhamoy Maitra hanno dimostrato le correlazioni permutazione-chiave. Quest'ultimo lavoro ha utilizzato anche le correlazioni chiave di permutazione per progettare il primo algoritmo per la ricostruzione completa della chiave dalla permutazione finale dopo il KSA, senza alcuna ipotesi sulla chiave o sul vettore di inizializzazione . Questo algoritmo ha una probabilità di successo costante in un tempo che è la radice quadrata della complessità della ricerca esaustiva della chiave. Successivamente, sono stati eseguiti molti altri lavori sulla ricostruzione delle chiavi dagli stati interni di RC4. Subhamoy Maitra e Goutam Paul hanno anche mostrato che i pregiudizi di tipo Roos persistono anche quando si considerano indici di permutazione annidati, come S[S[i]] o S[S[S[i]]] . Questi tipi di pregiudizi sono utilizzati in alcuni dei successivi metodi di ricostruzione chiave per aumentare la probabilità di successo.

Uscite polarizzate dell'RC4

Il flusso di chiavi generato da RC4 è distorto in varia misura verso determinate sequenze, rendendolo vulnerabile ad attacchi distinti . Il miglior attacco di questo tipo è dovuto a Itsik Mantin e Adi Shamir che hanno mostrato che il secondo byte di output del cifrario era polarizzato verso lo zero con probabilità 1/128 (invece di 1/256). Ciò è dovuto al fatto che se il terzo byte dello stato originale è zero e il secondo byte non è uguale a 2, il secondo byte di output è sempre zero. Tale bias può essere rilevato osservando solo 256 byte.

Souradyuti Paul e Bart Preneel di COSIC hanno mostrato che anche il primo e il secondo byte dell'RC4 erano distorti. Il numero di campioni richiesti per rilevare questo bias è di 2 25 byte.

Anche Scott Fluhrer e David McGrew hanno mostrato tali attacchi che distinguevano il keystream dell'RC4 da un flusso casuale dato un gigabyte di output.

La caratterizzazione completa di un singolo passaggio di RC4 PRGA è stata eseguita da Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra e Goutam Paul. Considerando tutte le permutazioni, dimostrano che la distribuzione dell'output non è uniforme dati i e j e, di conseguenza, l'informazione su j è sempre trapelata nell'output.

Fluhrer, Mantin e Shamir attaccano

Nel 2001, una nuova e sorprendente scoperta è stata fatta da Fluhrer , Mantin e Shamir : su tutte le possibili chiavi RC4, le statistiche per i primi byte del keystream di output sono fortemente non casuali, perdendo informazioni sulla chiave. Se la chiave nonce e quella a lungo termine vengono semplicemente concatenate per generare la chiave RC4, questa chiave a lungo termine può essere scoperta analizzando un gran numero di messaggi crittografati con questa chiave. Questo e gli effetti correlati sono stati quindi utilizzati per violare la crittografia WEP ("wired equivalent privacy") utilizzata con le reti wireless 802.11 . Ciò ha causato una corsa per una sostituzione basata su standard per WEP nel mercato 802.11 e ha portato allo sforzo IEEE 802.11i e WPA .

I protocolli possono difendersi da questo attacco scartando la porzione iniziale del keystream. Tale algoritmo modificato è tradizionalmente chiamato "RC4-drop[ n ]", dove n è il numero di byte del keystream iniziale che vengono eliminati. L'impostazione predefinita di SCAN è n = 768 byte, ma un valore conservativo sarebbe n = 3072 byte.

L'attacco Fluhrer, Mantin e Shamir non si applica a SSL basato su RC4, poiché SSL genera le chiavi di crittografia che utilizza per RC4 tramite hashing, il che significa che diverse sessioni SSL hanno chiavi non correlate.

L'attacco di Klein

Nel 2005, Andreas Klein ha presentato un'analisi del cifrario a flusso RC4 che mostrava più correlazioni tra il keystream RC4 e la chiave. Erik Tews , Ralf-Philipp Weinmann e Andrei Pychkine hanno utilizzato questa analisi per creare aircrack-ptw, uno strumento che cracca RC4 a 104 bit utilizzato in WEP a 128 bit in meno di un minuto. Mentre l'attacco Fluhrer, Mantin e Shamir ha utilizzato circa 10 milioni di messaggi, aircrack-ptw può violare chiavi a 104 bit in 40.000 frame con il 50% di probabilità o in 85.000 frame con il 95% di probabilità.

Problema combinatorio

Un problema combinatorio relativo al numero di ingressi e uscite del cifrario RC4 è stato posto per la prima volta da Itsik Mantin e Adi Shamir nel 2001, per cui, su un totale di 256 elementi nello stato tipico di RC4, se x numero di elementi ( x ≤ 256 ) sono solo noti (tutti gli altri elementi possono essere assunti vuoti), quindi anche il numero massimo di elementi che possono essere prodotti in modo deterministico è x nei successivi 256 round. Questa congettura è stata messa a tacere nel 2004 con una prova formale data da Souradyuti Paul e Bart Preneel .

Attacco Royal Holloway

Nel 2013, un gruppo di ricercatori di sicurezza presso l'Information Security Group presso Royal Holloway, Università di Londra, ha segnalato un attacco che può diventare efficace utilizzando solo 2 34 messaggi crittografati. Sebbene non sia ancora un attacco pratico per la maggior parte degli scopi, questo risultato è sufficientemente vicino a quello che ha portato a ipotizzare che sia plausibile che alcune agenzie crittografiche statali possano già avere attacchi migliori che rendono insicuro RC4. Dato che, a partire dal 2013, una grande quantità di traffico TLS utilizza RC4 per evitare attacchi ai cifrari a blocchi che utilizzano il concatenamento di blocchi di cifratura , se questi ipotetici attacchi migliori esistono, ciò renderebbe la combinazione TLS-con-RC4 insicura contro tali aggressori in un gran numero di scenari pratici.

Nel marzo 2015 il ricercatore al Royal Holloway ha annunciato miglioramenti per il loro attacco, fornendo un 2 26 attacco contro le password cifrate con RC4, come usato in TLS.

Attacco Bar-mitzvah

Sul Black Hat Asia 2015, Itsik Mantin ha presentato un altro attacco contro SSL utilizzando la cifratura RC4.

NESSUN attacco

Nel 2015, i ricercatori della sicurezza di KU Leuven hanno presentato nuovi attacchi contro RC4 sia in TLS che in WPA-TKIP . Soprannominato l'attacco Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE), è il primo attacco del suo genere che è stato dimostrato nella pratica. Il loro attacco contro TLS può decifrare un cookie HTTP sicuro entro 75 ore. L'attacco contro WPA-TKIP può essere completato entro un'ora e consente a un utente malintenzionato di decrittografare e iniettare pacchetti arbitrari.

Varianti RC4

Come accennato in precedenza, il punto debole più importante di RC4 deriva dall'insufficienza della pianificazione delle chiavi; i primi byte di output rivelano informazioni sulla chiave. Questo può essere corretto semplicemente scartando una parte iniziale del flusso di output. Questo è noto come RC4-drop N , dove N è tipicamente un multiplo di 256, come 768 o 1024.

Sono stati fatti numerosi tentativi per rafforzare RC4, in particolare Spritz, RC4A, VMPC e RC4 + .

RC4A

Souradyuti Paul e Bart Preneel hanno proposto una variante RC4, che chiamano RC4A.

RC4A utilizza due array di stato S1 e S2 e due indici j1 e j2 . Ogni volta che i viene incrementato, vengono generati due byte:

  1. Innanzitutto, l'algoritmo RC4 di base viene eseguito utilizzando S1 e j1 , ma nell'ultimo passaggio si cerca S1[ i ]+S1[ j1 ] in S2 .
  2. In secondo luogo, l'operazione viene ripetuta (senza incrementare nuovamente i ) su S2 e j2 e viene emesso S1[S2[ i ]+S2[ j2 ]] .

L'algoritmo è quindi:

All arithmetic is performed modulo 256
i := 0
j1 := 0
j2 := 0
while GeneratingOutput:
    i := i + 1
    j1 := j1 + S1[i]
    swap values of S1[i] and S1[j1]
    output S2[S1[i] + S1[j1]]
    j2 := j2 + S2[i]
    swap values of S2[i] and S2[j2]
    output S1[S2[i] + S2[j2]]
endwhile

Sebbene l'algoritmo richieda lo stesso numero di operazioni per byte di output, il parallelismo è maggiore rispetto a RC4, fornendo un possibile miglioramento della velocità.

Sebbene più forte di RC4, anche questo algoritmo è stato attaccato, con Alexander Maximov e un team di NEC che hanno sviluppato modi per distinguere il suo output da una sequenza veramente casuale.

VMPC

La composizione di permutazione modificata in modo variabile (VMPC) è un'altra variante di RC4. Utilizza una pianificazione delle chiavi simile a RC4, con j := S[(j + S[i] + key[i mod keylength]) mod 256] che itera 3 × 256 = 768 volte anziché 256 e con 768 iterazioni aggiuntive opzionali incorporare un vettore iniziale. La funzione di generazione dell'uscita opera come segue:

All arithmetic is performed modulo 256.
i := 0
while GeneratingOutput:
    a := S[i]
    j := S[j + a]
    
    output S[S[S[j] + 1]]
    Swap S[i] and S[j]          (b := S[j]; S[i] := b; S[j] := a))
    
    i := i + 1
endwhile

Questo è stato attaccato negli stessi giornali di RC4A e può essere distinto entro 2 38 byte di output.

RC4 +

RC4 + è una versione modificata di RC4 con un programma chiave trifase più complesso (che impiega circa tre volte il tempo di RC4, o lo stesso di RC4-drop512) e una funzione di output più complessa che esegue quattro ricerche aggiuntive nella S array per ogni uscita di byte, impiegando circa 1,7 volte il tempo di base RC4.

All arithmetic modulo 256.  << and >> are left and right shift,  is exclusive OR
while GeneratingOutput:
    i := i + 1
    a := S[i]
    j := j + a
    
    Swap S[i] and S[j]               (b := S[j]; S[j] := S[i]; S[i] := b;)
    
    c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3]
    output (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]
endwhile

Questo algoritmo non è stato analizzato in modo significativo.

Spritz

Nel 2014, Ronald Rivest ha tenuto un discorso e ha co-scritto un documento su una riprogettazione aggiornata chiamata Spritz . Un acceleratore hardware di Spritz è stato pubblicato su Secrypt, 2016 e mostra che a causa di più chiamate nidificate necessarie per produrre byte di output, Spritz si comporta piuttosto lentamente rispetto ad altre funzioni hash come SHA-3 e l'implementazione hardware più nota di RC4.

L'algoritmo è:

All arithmetic is performed modulo 256
while GeneratingOutput:
    i := i + w
    j := k + S[j + S[i]]
    k := k + i + S[j]
    swap values of S[i] and S[j]
    output z := S[j + S[i + S[z + k]]]
endwhile

Il valore w , è relativamente primo rispetto alla dimensione dell'array S. Quindi, dopo 256 iterazioni di questo ciclo interno, il valore i (incrementato di w ogni iterazione) ha assunto tutti i possibili valori 0...255 e ogni byte nell'array S è stato scambiato almeno una volta.

Come altre funzioni spugna , Spritz può essere utilizzato per creare una funzione hash crittografica, un generatore di bit casuali deterministico ( DRBG ), un algoritmo di crittografia che supporta la crittografia autenticata con dati associati (AEAD), ecc.

Nel 2016, Banik e Isobe hanno proposto un attacco in grado di distinguere lo Spritz dal rumore casuale.

Protocolli basati su RC4

Laddove un protocollo è contrassegnato con "(opzionalmente)", RC4 è uno dei più cifrari che il sistema può essere configurato per utilizzare.

Guarda anche

Riferimenti

Ulteriori letture

link esterno

RC4 in WEP