RC4 - RC4

RC4
General
Designeri Ron Rivest ( RSA Security )
Publicat pentru prima dată S-a scurs în 1994
(proiectat în 1987)
Detalii cifrate
Dimensiuni cheie 40–2048 biți
Dimensiunea statului 2064 biți (1684 efectiv)
Runde 1
Viteză 7 cicluri pe octet pe RC4 original
pretins modificat Pentium pe Intel Core 2: 13,9 cicluri pe octet

În criptografie , RC4 (Rivest Cipher 4, cunoscut și sub numele de ARC4 sau ARCFOUR, care înseamnă Alleged RC4, vezi mai jos) este un flux de cifrare . Deși este remarcabil pentru simplitatea și viteza în software, au fost descoperite mai multe vulnerabilități în RC4, ceea ce îl face nesigur. Este deosebit de vulnerabil atunci când începutul fluxului de taste de ieșire nu este eliminat sau când sunt folosite chei non-aleatorii sau conexe. Utilizările deosebit de problematice ale RC4 au dus la protocoale foarte nesigure , cum ar fi WEP .

Începând cu 2015, se speculează că unele agenții criptologice de stat ar putea avea capacitatea de a sparge RC4 atunci când sunt utilizate în protocolul TLS . IETF a publicat RFC 7465 pentru a interzice utilizarea RC4 în TLS; Mozilla și Microsoft au emis recomandări similare.

Au fost făcute mai multe încercări de consolidare a RC4, în special Spritz, RC4A, VMPC și RC4 + .

Istorie

RC4 a fost proiectat de Ron Rivest de la RSA Security în 1987. Deși este denumit oficial „Rivest Cipher 4”, acronimul RC este, în mod alternativ, înțeles ca „Codul lui Ron” (vezi și RC2 , RC5 și RC6 ).

RC4 a fost inițial un secret comercial , dar în septembrie 1994 o descriere a acestuia a fost postată anonim pe lista de distribuție Cypherpunks . În curând, a fost postat pe grupul de știri sci.crypt , unde a fost analizat în câteva zile de Bob Jenkins. De acolo s-a răspândit pe multe site-uri de pe Internet. Codul scurs a fost confirmat a fi autentic, deoarece rezultatul său s-a dovedit a se potrivi cu cel al software-ului proprietar care utilizează RC4 licențiat. Deoarece algoritmul este cunoscut, nu mai este un secret comercial. Numele RC4 este marcă comercială, astfel încât RC4 este adesea denumit ARCFOUR sau ARC4 (ceea ce înseamnă presupus RC4 ) pentru a evita problemele mărcii comerciale. RSA Security nu a lansat niciodată oficial algoritmul; Cu toate acestea, Rivest a legat articolul din Wikipedia în engleză despre RC4 în propriile sale note de curs în 2008 și a confirmat istoria RC4 și codul său într-o lucrare din 2014 a lui.

RC4 a devenit parte a unor protocoale și standarde de criptare utilizate în mod obișnuit, cum ar fi WEP în 1997 și WPA în 2003/2004 pentru carduri wireless; și SSL în 1995 și succesorul său TLS în 1999, până când a fost interzis pentru toate versiunile TLS de RFC 7465 în 2015, din cauza atacurilor RC4 care slăbeau sau rupeau RC4 utilizate în SSL / TLS. Principalii factori ai succesului RC4 într-o gamă atât de largă de aplicații au fost viteza și simplitatea sa: implementările eficiente atât în ​​software cât și în hardware au fost foarte ușor de dezvoltat.

Descriere

RC4 generează un flux pseudorandom de biți (un flux de chei ). La fel ca în cazul oricărui cod de flux, acestea pot fi folosite pentru criptare prin combinarea acestuia cu textul clar folosind bit-wise exclusive-or ; decriptarea se efectuează în același mod (deoarece exclusiv sau cu date date este o involuție ). Acest lucru este similar cu tamponul unic, cu excepția faptului că se utilizează biți pseudorandom generați , mai degrabă decât un flux pregătit.

Pentru a genera fluxul de chei, cifrul folosește o stare internă secretă care constă din două părți:

  1. O permutare a tuturor celor 256 octeți posibili (notat "S" mai jos).
  2. Două indicatoare de 8 biți (notate „i” și „j”).

Permutarea este inițializată cu o cheie cu lungime variabilă , de obicei între 40 și 2048 biți, utilizând algoritmul de planificare a cheilor (KSA). Odată ce acest lucru a fost finalizat, fluxul de biți este generat utilizând algoritmul de generare pseudo-aleatorie (PRGA).

Algoritm de planificare cheie (KSA)

Cheie de programare algoritm este folosit pentru a inițializa permutare în matrice „S“. "lungime cheie" este definită ca numărul de octeți din cheie și poate fi în intervalul 1 ≤ lungime cheie ≤ 256, de obicei între 5 și 16, corespunzând unei lungimi cheie de 40 - 128 biți. În primul rând, matricea „S” este inițializată la permutarea identității . S este apoi procesat pentru 256 de iterații într-un mod similar cu PRGA principal, dar amestecă și octeți ai cheii în același timp.

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

Algoritm de generare pseudo-aleatorie (PRGA)

Etapa de căutare a RC4. Octetul de ieșire este selectat căutând valorile lui S [i] și S [j] , adăugându-le împreună modulul 256 și apoi folosind suma ca index în S ; S (S [i] + S [j]) este folosit ca octet al fluxului cheie, K.

Pentru câte iterații sunt necesare, PRGA modifică starea și generează un octet al fluxului de chei. În fiecare iterație, PRGA:

  • măriri i
  • caută elementul i al lui S , S [ i ] și adaugă asta la j
  • schimbă valorile lui S [ i ] și S [ j ] apoi folosește suma S [ i ] + S [ j ] (modulul 256) ca index pentru a prelua un al treilea element al lui S (valoarea fluxului de chei K de mai jos)
  • apoi bited exclusiv ORed ( XORed ) cu următorul octet al mesajului pentru a produce următorul octet fie al textului cifrat, fie al textului simplu.

Fiecare element al lui S este schimbat cu un alt element cel puțin o dată la 256 de iterații.

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

Astfel, aceasta produce un flux de K [0], K [1], ... care sunt XOR 'ed cu textul simplu pentru a obține textul cifrat . Deci text cifrat [ l ] = text simplu [ l ] ⊕ K [ l ] .

Generatoare de numere aleatorii bazate pe RC4

Mai multe sisteme de operare includ arc4random, un API originar din OpenBSD care oferă acces la un generator de numere aleatoare bazat inițial pe RC4. În OpenBSD 5.5, lansat în mai 2014, a arc4randomfost modificat pentru a utiliza ChaCha20 . Implementările arc4random în FreeBSD , NetBSD și libbsd Linux folosesc, de asemenea, ChaCha20. Conform paginilor de manual livrate împreună cu sistemul de operare, în versiunea din 2017 a sistemelor sale de operare desktop și mobile , Apple a înlocuit RC4 cu AES în implementarea arc4random. Pagini Man pentru noul arc4random includ backronym „Un apel pentru înlocuire aleatorie“ pentru ARC4 ca mnemonic, deoarece oferă date mai bune decat aleatoare rand () nu.

Noile generatoare de numere aleatorii propuse sunt adesea comparate cu generatorul de numere aleatorii RC4.

Mai multe atacuri asupra RC4 sunt capabile să distingă ieșirea sa de o secvență aleatorie .

Implementare

Multe cifre de flux se bazează pe registre de schimbare cu feedback liniar (LFSR), care, deși sunt eficiente în hardware, sunt mai puțin în software. Proiectarea RC4 evită utilizarea LFSR-urilor și este ideală pentru implementarea software-ului, deoarece necesită doar manipulări de octeți. Folosește 256 de octeți de memorie pentru matricea de stare, S [0] până la S [255], k octeți de memorie pentru cheie, cheia [0] până la cheie [k-1] și variabile întregi, i, j și K. Efectuarea unei reduceri modulare de o anumită valoare modulo 256 se poate face cu un bit și cu 255 (care este echivalent cu luarea octetului de ordine joasă a valorii în cauză).

Vectorii de testare

Acești vectori de testare nu sunt oficiali, dar convenabili pentru oricine își testează propriul program RC4. Cheile și textul simplu sunt ASCII , fluxul de taste și textul cifrat sunt în hexazecimal .

Cheie Keystream Text simplu Text cifrat
Cheie EB9F7781B734CA72A719 ... Text simplu BBF316E8D940AF0AD3
Wiki 6044DB6D41B7 ... pedia 1021BF0420
Secret 04D46B053CA87B59 ... Atacă în zori 45A01F645FC35B383552544B9BF5

Securitate

Spre deosebire de un cod de flux modern (cum ar fi cele din eSTREAM ), RC4 nu ia o nonce separată alături de cheie. Aceasta înseamnă că, dacă o singură cheie pe termen lung trebuie utilizată pentru a cripta în siguranță mai multe fluxuri, protocolul trebuie să specifice cum să se combine cheia nonce și cheia pe termen lung pentru a genera cheia fluxului pentru RC4. O abordare pentru a aborda acest lucru este de a genera o cheie RC4 „proaspătă” prin hashing o cheie pe termen lung cu un nonce . Cu toate acestea, multe aplicații care utilizează RC4 pur și simplu concatenează cheia și nonce; Programul cheie slab al RC4 dă naștere la atacuri cheie conexe , cum ar fi atacul Fluhrer, Mantin și Shamir (care este renumit pentru încălcarea standardului WEP ).

Deoarece RC4 este un cifru de flux , este mai maleabil decât cifrele bloc comune . Dacă nu este utilizat împreună cu un cod puternic de autentificare a mesajelor (MAC), atunci criptarea este vulnerabilă la un atac de întoarcere de biți . Cifrul este, de asemenea, vulnerabil la un atac de criptare a fluxului, dacă nu este implementat corect.

Cu toate acestea, este de remarcat faptul că RC4, fiind un cifru de flux, a fost pentru o perioadă de timp singurul cifru comun care a fost imun la atacul BEAST din 2011 asupra TLS 1.0 . Atacul exploatează o slăbiciune cunoscută în modul în care modul de înlănțuire a blocurilor de cifrare este utilizat cu toate celelalte cifre suportate de TLS 1.0, care sunt toate cifrele de blocuri.

În martie 2013, au existat noi scenarii de atac propuse de Isobe, Ohigashi, Watanabe și Morii, precum și AlFardan, Bernstein, Paterson, Poettering și Schuldt, care utilizează noi tendințe statistice în tabelul de chei RC4 pentru a recupera textul clar cu un număr mare de criptări TLS.

Utilizarea RC4 în TLS este interzisă de RFC 7465 publicat în februarie 2015.

Biasurile lui Roos și reconstrucția cheie din permutare

În 1995, Andrew Roos a observat experimental că primul octet al fluxului de chei este corelat cu primii trei octeți ai cheii și primii câțiva octeți ai permutării după KSA sunt corelați cu o combinație liniară a octeților cheii. Aceste prejudecăți au rămas inexplicabile până în 2007, când Goutam Paul, Siddheshwar Rathi și Subhamoy Maitra au dovedit corelația keystream-cheie și într-o altă lucrare Goutam Paul și Subhamoy Maitra au dovedit corelațiile permutare-cheie. Ultima lucrare a folosit, de asemenea, corelațiile permutare-cheie pentru a proiecta primul algoritm pentru reconstrucția completă a cheii de la permutarea finală după KSA, fără nicio presupunere asupra cheii sau a vectorului de inițializare . Acest algoritm are o probabilitate constantă de succes într-un timp care este rădăcina pătrată a complexității exhaustive a căutării cheii. Ulterior, au fost efectuate multe alte lucrări privind reconstrucția cheie din stările interne RC4. Subhamoy Maitra și Goutam Paul au arătat, de asemenea, că prejudecățile de tip Roos persistă chiar și atunci când se iau în considerare indici de permutare cuibăriți, cum ar fi S [S [i]] sau S [S [S [i]]] . Aceste tipuri de prejudecăți sunt utilizate în unele dintre metodele cheie ulterioare de reconstrucție pentru creșterea probabilității de succes.

Ieșiri părtinitoare ale RC4

Fluxul de chei generat de RC4 este influențat în diferite grade față de anumite secvențe, făcându-l vulnerabil la atacuri distincte . Cel mai bun astfel de atac se datorează lui Itsik Mantin și Adi Shamir care au arătat că al doilea octet de ieșire al cifrului a fost orientat spre zero cu probabilitatea 1/128 (în loc de 1/256). Acest lucru se datorează faptului că, dacă al treilea octet al stării inițiale este zero, iar al doilea octet nu este egal cu 2, atunci al doilea octet de ieșire este întotdeauna zero. O astfel de prejudecată poate fi detectată observând doar 256 de octeți.

Souradyuti Paul și Bart Preneel de la COSIC au arătat că primul și al doilea octeți ai RC4 erau, de asemenea, părtinitori. Numărul de eșantioane necesare pentru a detecta această prejudecată este de 2 25 octeți.

Scott Fluhrer și David McGrew au arătat, de asemenea, astfel de atacuri care distingeu fluxul cheie al RC4 de un flux aleatoriu dat de un gigabyte de ieșire.

Caracterizarea completă a unui singur pas al RC4 PRGA a fost realizată de Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra și Goutam Paul. Având în vedere toate permutările, acestea demonstrează că distribuția ieșirii nu este uniformă dat fiind i și j și, în consecință, informațiile despre j sunt întotdeauna scurse în ieșire.

Fluhrer, Mantin și Shamir atacă

În 2001, Fluhrer , Mantin și Shamir au făcut o nouă și surprinzătoare descoperire : peste toate tastele RC4 posibile, statisticile pentru primii câțiva octeți de flux de chei de ieșire sunt puternic non-aleatorii, scurgând informații despre cheie. Dacă cheia nonce și pe termen lung sunt pur și simplu concatenate pentru a genera cheia RC4, această cheie pe termen lung poate fi descoperită analizând un număr mare de mesaje criptate cu această cheie. Acest efect și efectele conexe au fost apoi utilizate pentru a sparge criptarea WEP („confidențialitate echivalentă prin cablu”) utilizată cu rețelele fără fir 802.11 . Acest lucru a provocat o luptă pentru o înlocuire bazată pe standarde pentru WEP pe piața 802.11 și a dus la efortul IEEE 802.11i și WPA .

Protocoalele se pot apăra împotriva acestui atac aruncând porțiunea inițială a fluxului de chei. Un astfel de algoritm modificat se numește în mod tradițional „RC4-drop [ n ]”, unde n este numărul de octeți inițiali de flux de chei care sunt scăpați . Valoarea implicită SCAN este n = 768 octeți, dar o valoare conservatoare ar fi n = 3072 octeți.

Atacul Fluhrer, Mantin și Shamir nu se aplică SSL bazat pe RC4, deoarece SSL generează cheile de criptare pe care le folosește pentru RC4 prin hashing, ceea ce înseamnă că diferite sesiuni SSL au chei fără legătură.

Atacul lui Klein

În 2005, Andreas Klein a prezentat o analiză a cifrului fluxului RC4, arătând mai multe corelații între fluxul cheie RC4 și cheia. Erik Tews , Ralf-Philipp Weinmann și Andrei Pychkine au folosit această analiză pentru a crea aircrack-ptw, un instrument care fisurează RC4 de 104 biți utilizat în WEP pe 128 de biți în mai puțin de un minut. În timp ce atacul Fluhrer, Mantin și Shamir au folosit aproximativ 10 milioane de mesaje, aircrack-ptw poate rupe tastele de 104 biți în 40.000 de cadre cu probabilitate de 50% sau în 85.000 de cadre cu probabilitate de 95%.

Problemă combinatorie

O problemă combinatorie legată de numărul de intrări și ieșiri ale cifrului RC4 a fost pusă pentru prima dată de Itsik Mantin și Adi Shamir în 2001, prin care, din totalul de 256 de elemente în starea tipică a RC4, dacă x numărul de elemente ( x ≤ 256 ) sunt cunoscute doar (toate celelalte elemente pot fi presupuse goale), atunci numărul maxim de elemente care pot fi produse deterministic este, de asemenea, x în următoarele 256 runde. Această conjectură a fost pusă la sfârșit în 2004, cu o dovadă formală dată de Souradyuti Paul și Bart Preneel .

Atacul Royal Holloway

În 2013, un grup de cercetători în domeniul securității informațiilor din cadrul Grupului de securitate a informațiilor de la Royal Holloway, Universitatea din Londra, a raportat un atac care poate deveni eficient folosind doar 2 34 de mesaje criptate. Deși nu este încă un atac practic în majoritatea scopurilor, acest rezultat este suficient de apropiat de unul încât a condus la speculații că este plauzibil că unele agenții criptologice de stat ar putea avea deja atacuri mai bune care fac RC4 nesigur. Având în vedere că, începând cu 2013, o cantitate mare de trafic TLS folosește RC4 pentru a evita atacurile asupra cifrelor bloc care utilizează înlănțuirea blocurilor cifrate , dacă există aceste atacuri ipotetice mai bune, atunci acest lucru ar face ca combinația TLS-cu-RC4 să fie nesigură împotriva acestor atacatori în un număr mare de scenarii practice.

În martie 2015, cercetătorul Royal Holloway a anunțat îmbunătățiri ale atacului lor, oferind un atac de 2 26 împotriva parolelor criptate cu RC4, așa cum este utilizat în TLS.

Atac Bar-mitzvah

În Black Hat Asia 2015, Itsik Mantin a prezentat un alt atac împotriva SSL folosind cifrul RC4.

NOMORE atac

În 2015, cercetătorii de securitate de la KU Leuven au prezentat noi atacuri împotriva RC4 atât în TLS, cât și în WPA-TKIP . Denumit atacul Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE), este primul atac de acest gen care a fost demonstrat în practică. Atacul lor împotriva TLS poate decripta un cookie HTTP sigur în 75 de ore. Atacul împotriva WPA-TKIP poate fi finalizat într-o oră și permite unui atacator să decripteze și să injecteze pachete arbitrare.

Variante RC4

După cum sa menționat mai sus, cea mai importantă slăbiciune a RC4 vine din programul cheie insuficient; primii octeți de ieșire dezvăluie informații despre cheie. Acest lucru poate fi corectat prin simpla aruncare a unei porțiuni inițiale a fluxului de ieșire. Aceasta este cunoscută sub numele de RC4-drop N , unde N este de obicei un multiplu de 256, cum ar fi 768 sau 1024.

Au fost făcute mai multe încercări de consolidare a RC4, în special Spritz, RC4A, VMPC și RC4 + .

RC4A

Souradyuti Paul și Bart Preneel au propus o variantă RC4, pe care o numesc RC4A.

RC4A folosește două matrici de stare S1 și S2 și doi indici j1 și j2 . De fiecare dată când i este incrementat, sunt generați doi octeți:

  1. În primul rând, algoritmul de bază RC4 este realizat folosind S1 și j1 , dar în ultimul pas, S1 [ i ] + S1 [ j1 ] este căutat în S2 .
  2. În al doilea rând, operația se repetă (fără a incrementa i din nou) pe S2 și j2 , iar S1 [S2 [ i ] + S2 [ j2 ]] este emis.

Astfel, algoritmul este:

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

Deși algoritmul a necesitat același număr de operații pe octet de ieșire, există un paralelism mai mare decât RC4, oferind o posibilă îmbunătățire a vitezei.

Deși mai puternic decât RC4, acest algoritm a fost, de asemenea, atacat, Alexander Maximov și o echipă de la NEC dezvoltând modalități de a distinge rezultatul său de o secvență cu adevărat aleatorie.

VMPC

Compoziția permutării modificate variabil (VMPC) este o altă variantă RC4. Folosește programul de taste similar cu RC4, cu j: = S [(j + S [i] + tastă [i mod keylength]) mod 256] iterație de 3 × 256 = 768 ori mai degrabă decât 256, și cu o iterație suplimentară opțională de 768 pentru a încorpora un vector inițial. Funcția de generare a ieșirii funcționează după cum urmează:

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

Acest lucru a fost atacat în aceleași lucrări ca RC4A și poate fi distins în 2 38 octeți de ieșire.

RC4 +

RC4 + este o versiune modificată a RC4 cu o programare cheie trifazată mai complexă (durând de aproximativ trei ori mai mult decât RC4 sau același lucru cu RC4-drop512) și o funcție de ieșire mai complexă care efectuează patru căutări suplimentare în S pentru fiecare ieșire de octeți, durând aproximativ 1,7 ori mai mult decât RC4 de bază.

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

Acest algoritm nu a fost analizat în mod semnificativ.

Spritz

În 2014, Ronald Rivest a ținut o discuție și a co-scris o lucrare despre o reproiectare actualizată numită Spritz . Un accelerator hardware al Spritz a fost publicat în Secrypt, 2016 și arată că, din cauza mai multor apeluri imbricate necesare pentru a produce octeți de ieșire, Spritz funcționează destul de lent în comparație cu alte funcții hash, cum ar fi SHA-3 și cea mai cunoscută implementare hardware a RC4.

Algoritmul este:

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

Valoarea w , este relativ primă cu dimensiunea matricei S. Deci, după 256 de iterații ale acestei bucle interioare, valoarea i (incrementată cu w fiecare iterație) a luat toate valorile posibile 0 ... 255 și fiecare octet din matricea S a fost schimbat cel puțin o dată.

La fel ca alte funcții de burete , Spritz poate fi utilizat pentru a construi o funcție hash criptografică, un generator de biți deterministic aleatoriu ( DRBG ), un algoritm de criptare care acceptă criptarea autentificată cu date asociate (AEAD) etc.

În 2016, Banik și Isobe au propus un atac care poate distinge Spritz de zgomotul aleatoriu.

Protocoale bazate pe RC4

În cazul în care un protocol este marcat cu „(opțional)”, RC4 este unul dintre cifrele multiple pe care sistemul le poate configura.

Vezi si

Referințe

Lecturi suplimentare

linkuri externe

RC4 în WEP