RC4

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. juli 2018; checks kræver 19 redigeringer .

RC4 (fra det engelske  Rivest cipher 4 eller Rons kode ), også kendt som ARC4 eller ARCFOUR ( påstået RC4 ) er en stream cipher , der er meget udbredt i forskellige informationssikkerhedssystemer i computernetværk (for eksempel i SSL- og TLS-protokoller , trådløse sikkerhedsalgoritmer WPA-ogWEP- ).

Chifferen er udviklet af RSA Security og kræver en licens for at bruge den .

RC4-algoritmen er, som enhver stream-chiffer , bygget op omkring en pseudo-tilfældig bit - generator . Nøglen skrives til generatorens input, og pseudo-tilfældige bits læses ved udgangen. Nøglængden kan være fra 40 til 2048 bit [1] . De genererede bits har en ensartet fordeling .

De vigtigste fordele ved chifferen:

RC4 er ret sårbar, hvis:

Disse faktorer, såvel som den måde, det bruges på, kan gøre et kryptosystem usikkert (såsom WEP ).

Historie

RC4 -strømchifferet blev oprettet i 1987 af Ronald Rivest fra RSA Security . Forkortelsen "RC4" står officielt for "Rivest cipher 4" eller " Rivest cipher " ("4" er versionsnummeret; se RC2 , RC5 , RC6 ; RC1 blev aldrig offentliggjort; RC3 blev udviklet, men der blev fundet en sårbarhed i den ), men det betragtes ofte som en forkortelse for " Rons kode " (" Rons kode ") [2] .

I syv år var chifferen en forretningshemmelighed , og en nøjagtig beskrivelse af algoritmen blev først givet efter underskrivelse af en fortrolighedsaftale , men i september 1994 blev dens beskrivelse anonymt sendt til Cypherpunks mailingliste [ 3] .  Snart blev en beskrivelse af RC4 offentliggjort på usenet nyhedsgruppen " sci.crypt ". Derfra fandt kildekoden vej til mange websteder på internettet . Den offentliggjorte algoritme producerede chiffertekster ved outputtet , der matchede chifferteksterne produceret af den originale RC4. Ejere af lovlige kopier af RC4 -kildekoden bekræftede identiteten af ​​algoritmerne med forskelle i notation og programstruktur.

Da denne algoritme er kendt, er den ikke længere en forretningshemmelighed . Imidlertid er navnet "RC4" et varemærke tilhørende RSA Security . For at undgå mulige krav fra varemærkeindehaveren , omtales chifferen nogle gange som "ARCFOUR" eller "ARC4", med henvisning til engelsk.  en påstået RC4  er en "formodet" RC4 (fordi RSA Security ikke officielt har offentliggjort algoritmen).

RC4-krypteringsalgoritmen bruges i nogle udbredte krypteringsstandarder og -protokoller (for eksempel WEP , WPA , SSL og TLS ).

RC4 blev populær takket være:

I USA er den anbefalede nøglelængde til husholdningsbrug 128 bit. En aftale mellem SPA ( s oftware publishers a sociation )  og den amerikanske regering tillod eksport af RC4-cifre med en nøglelængde på op til 40 bit. 56-bit nøgler er tilladt at blive brugt af udenlandske filialer af amerikanske virksomheder [4] .

Beskrivelse af algoritmen

Kernen i strømchifferalgoritmen består af en funktion - en pseudo-tilfældig bitgenerator ( gamma ), som producerer en strøm af nøglebit (nøglestrøm, gamma, sekvens af pseudo-tilfældige bits) .

krypteringsalgoritme.

  1. Funktionen genererer en bitsekvens ( ).
  2. Sekvensen af ​​bit sammenkædes derefter med klarteksten ( ) ved hjælp af modulo to summation (xor) operationen . Resultatet er en chiffertekst ( ):

.

dekrypteringsalgoritme.

  1. Nøglebitstrømmen (nøglestrømmen) genskabes (gendannes) ( ).
  2. Nøglens bitstrøm tilføjes til chifferteksten ( ) med " xor " operationen . På grund af egenskaberne ved xor - operationen er outputtet den originale (ukrypterede) tekst ( ):

RC4 er faktisk en klasse af algoritmer defineret af blokstørrelsen (herefter S-box ). Parameteren n er ordlængden for algoritmen og angiver længden af ​​S-boksen . Normalt er n = 8, men til analyseformål kan du reducere det. For at forbedre sikkerheden skal du dog øge denne værdi. Der er ingen modsætning i algoritmen for at øge størrelsen af ​​S-boksen . Med en stigning i n , lad os sige op til 16 bit, bliver elementerne i S-boksen 65.536, og følgelig vil den indledende iterationstid blive øget. Krypteringshastigheden vil dog stige [5] .

Den interne tilstand af RC4 er repræsenteret som et array af størrelse 2 n og to tællere. Arrayet er kendt som S-boksen og vil blive omtalt som S. Det indeholder altid en permutation af de 2n mulige betydninger af ordet. De to tællere er betegnet med iog j.

RC4 initialisering består af to dele:

  1. S-boks initialisering ;
  2. pseudo-tilfældig ordgenerering K.

S-box initialisering

Algoritmen er også kendt som "key-scheduling algorithm" eller "KSA". Denne algoritme bruger en nøgle leveret af brugeren, gemt i Key, og som har en længde på Lbytes. Initialisering begynder med at fylde arrayet S, derefter blandes dette array af permutationer bestemt af nøglen. Da kun én handling udføres på S, skal påstanden holde, at den Saltid indeholder det samme sæt værdier, som blev givet ved den indledende initialisering ( S[i] := i ).

for i fra 0 til 255 S[i] := i endfor j := 0 for i fra 0 til 255 j := ( j + S[i] + Key[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 swap S[i] og S[j] endfor

Pseudo-tilfældig ordgenerering K

Denne del af algoritmen kaldes en pseudo-tilfældig sekvensgenerator ( p seudor  andom generation a lgorithm , PRGA ) . RC4-nøglestrømsgeneratoren permuterer værdierne gemt i . I en RC4-cyklus bestemmes ét n -bit ord fra nøglestrømmen. I fremtiden vil nøgleordet blive tilføjet modulo to med den klartekst, som brugeren ønsker at kryptere, og chifferteksten opnås. SK

jeg := 0 j := 0 mens generationsløkke: i := (i + 1) mod 256 j := ( j + S[i] ) mod 256 swap S[i] og S[j] t := (S[i] + S[j]) mod 256 K := S[t] genereret pseudo-tilfældigt ord K (for n = 8 vil en byte blive genereret) endwhile

Sikkerhed

I modsætning til moderne cifre (såsom eSTREAM ), bruger RC4 ikke en nonce (fra engelsk nonce - "number that can only be used once" - et tal, der kun kan bruges én gang) sammen med nøglen. Det betyder, at hvis én nøgle skal bruges over tid til at kryptere flere streams, skal kryptosystemet, der bruger RC4 selv, kombinere lejligheden og den langsigtede nøgle for at producere en stream-nøgle til RC4. En mulig løsning er at generere en ny nøgle til RC4 ved hjælp af en hash -funktion af den langsigtede nøgle og en nonce . Men mange applikationer, der bruger RC4, sammenkæder simpelthen nøglen og nonce . På grund af dette og den svage nøgleplanlægning, der bruges i RC4, kan applikationen blive sårbar [6] [7] [8] . Derfor er det blevet forældet af mange softwarevirksomheder såsom Microsoft . For eksempel mangler Microsofts .NET Framework en implementering af RC4.

Her vil nogle angreb på chifferen og metoder til beskyttelse mod dem blive overvejet.

Rooses forskning og gendannelse af nøglen fra permutationen

I 1995 observerede Andrew Roos eksperimentelt, at den første byte af nøglestrømmen er korreleret med de første tre bytes af nøglen, og de første par bytes af permutationen efter nøgleplanlægningsalgoritmen ( eng  . KSA ) er korreleret med en eller anden lineær kombination af nøglebytes [9] . Disse skævheder blev ikke bevist før 2007, hvor Paul, Rafi og Maitrae beviste, at nøgle og nøglestrøm er korrelerede. Paul og Maitre beviste også sammenhængen mellem permutationen og nøglen. Sidstnævnte arbejde bruger også nøgle-permutationskorrelation til at generere den første komplette nøglegendannelsesalgoritme fra den sidste permutation efter KSA, uden at foretage antagelser om nøglen og initialiseringsvektoren ( IV , initial vector ) . Denne algoritme har en konstant sandsynlighed for succes over tid, hvilket er kvadratroden af ​​brute-force kompleksiteten. Meget arbejde er blevet gjort på det seneste for at gendanne nøglen fra den interne tilstand af RC4.   

Angreb af Fluhrer, Mantin og Shamir (FMS)

I 2001 udgav Fluhrer, Mantin og Shamir et papir om RC4-nøgleskemaets sårbarhed. De viste, at de første bytes af en nøglestrøm blandt alle mulige nøgler ikke er tilfældige. Fra disse bytes er det med stor sandsynlighed muligt at få information om den anvendte chiffernøgle. Og hvis en langtidsnøgle og en nonce blot limes sammen for at skabe en RC4-krypteringsnøgle, så kan denne langtidsnøgle opnås ved at analysere et tilstrækkeligt stort antal meddelelser krypteret med denne nøgle [10] . Denne sårbarhed og nogle relaterede effekter blev udnyttet til at bryde WEP- kryptering på IEEE 802.11 trådløse netværk . Dette viste behovet for at erstatte WEP så hurtigt som muligt , hvilket førte til udviklingen af ​​en ny trådløs sikkerhedsstandard, WPA .

Kryptosystemet kan gøres immunt over for dette angreb ved at kassere begyndelsen af ​​nøglestrømmen. Den modificerede algoritme kaldes således "RC4-drop[n]", hvor n er antallet af bytes fra begyndelsen af ​​nøglestrømmen, der skal kasseres. Det anbefales at bruge n = 768, et konservativt skøn er n = 3072[11] [12] .

Angrebet er baseret på svagheden af ​​initialiseringsvektoren . Ved at kende det første pseudo-tilfældige ord Kog minputnøglebytes Key, ved at bruge en svaghed i pseudo-tilfældig ordgenereringsalgoritmen K, kan man få m + 1inputnøglebyten. Ved at gentage trinene opnås den fulde nøgle. Når man angriber WEP , for n = 8 IVhar formen (B; 255; N), hvor B - fra 3 til 8, og et hvilket som Nhelst tal . For at bestemme omkring 60 varianter af N, ville det tage omkring 4 millioner pakker at blive opsnappet. [ti]

Klein Attack

I 2005 præsenterede Andreas Klein en analyse af RC4-chifferet, hvori han påpegede den stærke sammenhæng mellem nøglen og RC4-nøglestrømmen. Klein analyserede angrebene i første runde (svarende til PMS-angrebet), i anden runde og deres mulige forbedringer. Han foreslog også nogle ændringer til algoritmen for at forbedre chifferens styrke. Især hævder han, at hvis du vender retningen af ​​cyklussen i nøgleskemaalgoritmen, så kan du gøre chifferen mere modstandsdygtig over for angreb som FMS [1] .

Kombinatorisk problem

I 2001 var Adi Shamir og Itzhak Mantin de første til at udgøre et kombinatorisk problem relateret til antallet af mulige input og output af RC4-chifferet. Hvis ud af alle mulige 256 elementer i chifferens interne tilstand, xelementer fra tilstanden ( x ≤ 256) kendes, så, hvis vi antager, at de resterende elementer er nul, er det maksimale antal elementer, der kan opnås med den deterministiske algoritme i de næste 256 runder er også lig med x. I 2004 blev denne antagelse bevist af  Souradyuti Paul og Bart Preneel [ 13 ] . 

Attack of Vanhof and Pissens (2015)

I sommeren 2015 demonstrerede Mathy Vanhoef og Frank Piessens fra University of Leuven i Belgien et reelt angreb på TLS-protokollen , som bruger RC4 til at kryptere transmitterede data [14] . Ideen om at hacke er baseret på MITM- princippet . Ved at integrere i en datatransmissionskanal genererer angriberen et stort antal anmodninger til serveren, hvilket tvinger den til at returnere cookies som svar , krypteret med den samme nøgle. Med omkring 9x2 27 ~ 2 30 {plaintext, ciphertext} par ved hånden, var angriberen i stand til at gendanne nøglen og derfor de krypterede cookies baseret på de statistiske metoder fra Fluhrer-McGrew og ABSAB med en sandsynlighed på 94%. Den praktiske brugte tid var omkring 52 timer, mens den øvre vurdering af den nødvendige tid på demonstrationstidspunktet var omkring 72 timer [15] .

RC4 mods

Tidligere blev angreb baseret på korrelationen af ​​de første bytes af chifferteksten og nøglen overvejet. Sådanne svagheder ved algoritmen kan løses ved at kassere den indledende del af chifferteksten [16] . Det er sikkert at kassere de første 256, 512, 768 og 1024 bytes. Undersøgelser af begyndelsen af ​​chifferteksten blev udført for at vise upålideligheden af ​​et vist antal første bytes, hvilket kan føre til, at en angriber får en krypteringsnøgle. Adskillige modifikationer af RC4 er blevet foreslået, der udfører opgaven med at forbedre sikkerheden ved brug af algoritmen: RC4A, VMPC , RC4+.

RC4A

I 2004 så arbejdet af Souradyuti Paul og Bart Preneel lyset, som foreslog en ændring af RC4A [17] .

Til RC4A anvendes to S-bokse i stedet for én, som i RC4, betegnet med S₁og S₂. Til dem bruges to tællere j₁hhv j₂. Tælleren i, som for RC4, bruges i ental for hele algoritmen. Algoritmeudførelsesprincippet forbliver det samme, men der er en række forskelle:

  1. S₁er en parameter for S₂.
  2. For én iteration, det vil sige for én indeksforøgelse i, genereres to bytes chiffertekst.

Algoritme:

jeg := 0 j₁ := 0 j₂ := 0 mens generationsløkke: i := i + 1 j1:= (j1 + S1[i]) mod 256 swap S₁[i] og S₁[j₁] I₂ := (S₁[i] + S₁[j₁]) mod 256 output  := S₂[I₂] j2 = (j2 + S2[i]) mod 256 swap S₂[i] og S₂[j₂] I1 = (S2[i] + S2[j2]) mod 256 output  := S1[I1] endwhile

Krypteringshastigheden af ​​denne algoritme kan øges ved parallelisering .

RC4+

I 2008 blev RC4+ modifikationen udviklet og foreslået. Forfatterne Subhamoy Maitra og Goutam Paul ændrede initialiseringen af ​​S-boksen (KSA+) ved hjælp af 3-niveaus scrambling. Også den pseudo-tilfældige ordgenereringsalgoritme (PRGA+) [18] blev ændret .

Algoritme:

Alle aritmetiske operationer udføres mod 256. Symbolerne "<<" og ">>" angiver bitskift til henholdsvis venstre og højre. Symbolet "⊕" angiver operationen " eksklusive ELLER " mens Generation loop: i := i + 1 a := S[i] j := j + a b := S[j] S[i] := b (byttet S[i] og S[j]) S[j] := a c := S[ i<<5 ⊕ j>>3 ] + S[ j<<5 ⊕ i>>3 ] output ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ] endwhile

Implementering

Mange strømcifre er baseret på lineære feedback-skifteregistre ( LFSR ) .  Dette gør det muligt at opnå højeffektive implementeringer af chifferen i form af et integreret kredsløb (hardwareimplementering), men komplicerer softwareimplementeringen af ​​sådanne chiffer. Da RC4-chifferet ikke bruger LFSR og er baseret på byte-operationer, er det praktisk at implementere det i software. En typisk implementering udfører 8 til 16 maskininstruktioner pr. tekstbyte , så en softwareimplementering af chifferen bør være hurtig [19] .

Kryptosystemer og protokoller ved hjælp af RC4

Ordet "(variabel)" betyder, at RC4 er en af ​​flere krypteringsalgoritmer, der kan bruges af systemet.

Se også

Noter

  1. ↑ 1 2 Klein A. Angreb på RC4-strømchifferet  (udefineret)  // Designs, koder og kryptografi. - 2008. - T. 48 , nr. 3 . - S. 269-286 . - doi : 10.1007/s10623-008-9206-6 .
  2. ↑ Rivest FAQ (downlink) . Hentet 15. oktober 2009. Arkiveret fra originalen 15. juli 2017. 
  3. ↑ Tak Bob Anderson . Cypherpunks mailingliste (9. september 1994). Hentet 28. maj 2007.
  4. ↑ RSA Laboratories - 3.6.2 Hvad er RC2?
  5. ↑ Bruce Schneier. Anvendt kryptografi. anden version. John Wiley & sønner. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 16. oktober 2013. Arkiveret fra originalen 16. november 2012. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Svage taster i RC4 (downlink) . Hentet 7. november 2012. Arkiveret fra originalen 18. juni 2012. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Svagheder i nøgleplanlægningsalgoritmen for RC4  (neopr.)  // Forelæsningsnoter i datalogi. - 2001. - T. 2259 . - S. 1-24 . - doi : 10.1007/3-540-45537-X_1 . Arkiveret fra originalen den 7. september 2008.
  11. ↑ I. Mironov. (Ikke så) tilfældige blandinger af RC4  (neopr.)  // Lecture Notes in Computer Science. - 2002. - T. 2442 . - S. 304-319 . - doi : 10.1007/3-540-45708-9_20 .
  12. ↑ "RC4-drop(nbytes)" . " Standard kryptografisk algoritmenavngivning " database.
  13. ↑ Souradyuti Paul, Bart Preneel. En ny svaghed i RC4 Keystream-generatoren og en tilgang til forbedring af chifferens sikkerhed  //  Lecture notes in computer science : journal. - 2004. - Bd. 3017 . - S. 245-259 . - doi : 10.1007/b98177 .
  14. ↑ RC4 NOMORE
  15. ↑ Hackere viste en praktisk metode til at hacke RC4
  16. ↑ Ilya Mironov (2002-06-01), (Ikke så) Tilfældige blandinger af RC4 , Advances in cryptology - CRYPTO 2002 , vol. 2442, Forelæsningsnotater i datalogi, Springer-Verlag, s. 304–319, Cryptology ePrint-arkiv: Rapport 2002/067, ISBN 3-540-44050-X , doi : 10.1007/3-540-45708-9_20 
  17. ↑ Souradyuti Paul & Bart Preneel (2004), A New Weakness in the RC4 Keystream Generator and an Approach to Improve Security of the Cipher , Fast Software Encryption, FSE 2004 , vol. 3017, Lecture Notes in Computer Science, Springer-Verlag, s. 245-259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), Analyse af RC4 og forslag om yderligere lag for bedre sikkerhedsmargin , Fremskridt i kryptologi - INDOCRYPT 2008 , vol. 5365, Lecture Notes in Computer science, Springer-Verlag, s. 27–39, Cryptology ePrint Archive: Rapport 2008/396, ISBN 3-540-89753-4 , doi : 10.1007/978-3-540-89754-5_3 
  19. ↑ RSA Laboratories - 3.6.3 Hvad er RC4?
  20. ↑ Svar Arkiveret 24. marts 2010 på Wayback Machine til spørgsmål fra brugere af Opera mini- browseren .
  21. ↑ RFC 4757 . RC4- HMAC kerberos krypteringstyper, der bruges af Microsoft Windows .
  22. ↑ PDF & PDF/A-software | PDF Tools AG | Premium PDF-teknologi Arkiveret 3. november 2005.
  23. ↑ Skypes krypteringsprocedure delvist afsløret . www.h-online.com. Hentet 8. juli 2010. Arkiveret fra originalen 6. november 2012.

Links

 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet