RC4

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 juli 2018; kontroller kräver 19 redigeringar .

RC4 (från engelska  Rivest cipher 4 eller Rons kod ), även känd som ARC4 eller ARCFOUR ( påstådd RC4 ) är ett strömchiffer som ofta används i olika informationssäkerhetssystem i datornätverk (till exempel i SSL- och TLS-protokoll , trådlösa säkerhetsalgoritmer WPAochWEP- ).

Chifferet är utvecklat av RSA Security och kräver en licens för att använda det .

RC4-algoritmen, som alla strömchiffer , är byggd kring en pseudo- slumpmässig bitgenerator . Nyckeln skrivs till generatoringången och pseudoslumpmässiga bitar läses vid utgången. Nyckellängden kan vara från 40 till 2048 bitar [1] . De genererade bitarna har en enhetlig fördelning .

De viktigaste fördelarna med chiffer:

RC4 är ganska sårbart om:

Dessa faktorer, såväl som sättet på vilket det används, kan göra ett kryptosystem osäkert (som WEP ).

Historik

RC4 -strömchifferet skapades 1987 av Ronald Rivest från RSA Security . Förkortningen "RC4" står officiellt för "Rivest cipher 4" eller " Rivest cipher " ("4" är versionsnumret; se RC2 , RC5 , RC6 ; RC1 publicerades aldrig; RC3 utvecklades, men en sårbarhet hittades i den ), men det anses ofta vara en förkortning för " Rons kod " (" Rons kod ") [2] .

I sju år var chiffret en affärshemlighet , och en exakt beskrivning av algoritmen gavs först efter att ett sekretessavtal undertecknats , men i september 1994 skickades dess beskrivning anonymt till Cypherpunks e -postlista [ 3 ] .  Snart publicerades en beskrivning av RC4 på usenets nyhetsgrupp " sci.crypt ". Därifrån hittade källkoden sin väg till många webbplatser på Internet . Den publicerade algoritmen producerade chiffertexter vid utgången som matchade chiffertexterna som producerades av den ursprungliga RC4. Ägare av lagliga kopior av RC4 -källkoden bekräftade identiteten för algoritmerna med skillnader i notation och programstruktur.

Eftersom denna algoritm är känd är den inte längre en affärshemlighet . Namnet "RC4" är dock ett varumärke som tillhör RSA Security . För att undvika eventuella anspråk från varumärkesägaren hänvisas chiffret ibland till som "ARCFOUR" eller "ARC4", med hänvisning till engelskan.  en påstådd RC4  är en "förmodad" RC4 (eftersom RSA Security inte officiellt har publicerat algoritmen).

RC4-krypteringsalgoritmen används i vissa allmänt använda krypteringsstandarder och protokoll (till exempel WEP , WPA , SSL och TLS ).

RC4 blev populär tack vare:

I USA är den rekommenderade nyckellängden för hushållsbruk 128 bitar. Ett avtal mellan SPA ( s oftware publishers a ssociation )  och den amerikanska regeringen tillät export av RC4-chiffer med en nyckellängd på upp till 40 bitar. 56-bitars nycklar är tillåtna att användas av utländska filialer av amerikanska företag [4] .

Beskrivning av algoritmen

Kärnan i strömchifferalgoritmen består av en funktion - en pseudo- slumpmässig bitgenerator ( gamma ), som producerar en ström av nyckelbitar (nyckelström, gamma, sekvens av pseudo-slumpmässiga bitar).

krypteringsalgoritm.

  1. Funktionen genererar en bitsekvens ( ).
  2. Sekvensen av bitar sammanlänkas sedan med klartexten ( ) med hjälp av modulo två summation (xor) operationen . Resultatet är en chiffertext ( ):

.

dekrypteringsalgoritm.

  1. Nyckelbitströmmen (nyckelströmmen) återskapas (återskapas) ( ).
  2. Nyckelns bitström läggs till chiffertexten ( ) med " xor " operationen . På grund av egenskaperna för xor- operationen är utdata den ursprungliga (okrypterade) texten ( ):

RC4 är faktiskt en klass av algoritmer som definieras av blockstorleken (nedan kallad S-box ). Parametern n är ordlängden för algoritmen och anger längden på S-boxen . Vanligtvis är n = 8, men för analysändamål kan du minska den. Men för att förbättra säkerheten måste du öka detta värde. Det finns ingen motsägelse i algoritmen för att öka storleken på S-boxen . Med en ökning av n , låt oss säga upp till 16 bitar, blir elementen i S-boxen 65 536 och följaktligen kommer den initiala iterationstiden att ökas. Krypteringshastigheten kommer dock att öka [5] .

Det interna tillståndet för RC4 representeras som en array med storleken 2 n och två räknare. Arrayen är känd som S-boxen och kommer att kallas S. Den innehåller alltid en permutation av de 2n möjliga betydelserna av ordet. De två räknarna betecknas med ioch j.

RC4-initiering består av två delar:

  1. S-box- initiering ;
  2. generering av pseudo-slumpmässiga ord K.

S-box- initiering

Algoritmen är också känd som "nyckelschemaläggningsalgoritm" eller "KSA". Denna algoritm använder en nyckel som tillhandahålls av användaren, lagrad i Key, och som har en längd på Lbyte. Initiering börjar med att fylla arrayen S, sedan blandas denna array av permutationer som bestäms av nyckeln. Eftersom endast en åtgärd utförs på Småste påståendet gälla att den Salltid innehåller samma uppsättning värden som gavs vid den initiala initieringen ( S[i] := i ).

för i från 0 till 255 S[i] := i endfor j := 0 för i från 0 till 255 j := ( j + S[i] + Tangent[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 byt S[i] och S[j] endfor

Pseudo-slumpmässiga ordgenerering K

Denna del av algoritmen kallas en pseudo- slumpsekvensgenerator ( p seudor  andom generation a lgorithm , PRGA ) . RC4-nyckelströmsgeneratorn permuterar värdena som är lagrade i . I en RC4-cykel bestäms ett n -bitars ord från nyckelströmmen. I framtiden kommer nyckelordet att läggas till modulo två med den klartext som användaren vill kryptera, och chiffertexten erhålls. SK

jag := 0 j := 0 medan generation loop: i := (i + 1) mod 256 j := ( j + S[i] ) mod 256 byt S[i] och S[j] t := (S[i] + S[j]) mod 256 K := S[t] genererat pseudo-slumpmässigt ord K (för n = 8 kommer en byte att genereras) under tiden

Säkerhet

Till skillnad från moderna chiffer (som eSTREAM ), använder RC4 inte en nonce (från engelska nonce - "number that can only be used once" - ett nummer som bara kan användas en gång) tillsammans med nyckeln. Detta innebär att om en nyckel ska användas över tid för att kryptera flera strömmar, måste kryptosystemet som använder RC4 själv kombinera tillfället och den långsiktiga nyckeln för att producera en strömnyckel för RC4. En möjlig lösning är att generera en ny nyckel för RC4 med hjälp av en hashfunktion för den långsiktiga nyckeln och en nonce . Men många applikationer som använder RC4 sammanfogar helt enkelt nyckeln och nonce . På grund av detta och den svaga nyckelschemaläggningen som används i RC4 kan applikationen bli sårbar [6] [7] [8] . Därför har det blivit utfasat av många programvaruföretag som Microsoft . Till exempel saknar Microsofts .NET Framework en implementering av RC4.

Här kommer några attacker på chiffer och metoder för skydd mot dem att övervägas.

Rooses forskning och återhämtning av nyckeln från permutationen

1995 observerade Andrew Roos experimentellt att den första byten av nyckelströmmen är korrelerad med de första tre byten av nyckeln, och de första byten av permutationen efter nyckelschemaläggningsalgoritmen ( eng  . KSA ) är korrelerade med någon linjär kombination nyckelbytes [9] . Dessa fördomar bevisades inte förrän 2007, när Paul, Rafi och Maitrae bevisade att nyckel och nyckelström är korrelerade. Paul och Maitre bevisade också korrelationen mellan permutationen och nyckeln. Det senare arbetet använder också nyckel - permutationskorrelation för att generera den första fullständiga nyckelåterställningsalgoritmen från den sista permutationen efter KSA, utan att göra antaganden om nyckeln och initialiseringsvektorn ( IV , initial vector ) . Denna algoritm har en konstant sannolikhet att lyckas över tid, vilket är kvadratroten av brute-force-komplexiteten. Mycket arbete har gjorts på sistone för att återställa nyckeln från det interna tillståndet hos RC4.   

Attack av Fluhrer, Mantin och Shamir (FMS)

2001 publicerade Fluhrer, Mantin och Shamir en artikel om sårbarheten hos RC4-nyckelschemat. De visade att de första byten i en nyckelström bland alla möjliga nycklar inte är slumpmässiga. Från dessa bytes är det med stor sannolikhet möjligt att få information om vilken chiffernyckel som används. Och om en långtidsnyckel och en nonce helt enkelt limmas ihop för att skapa en RC4-chiffernyckel, så kan denna långtidsnyckel erhållas genom att analysera ett tillräckligt stort antal meddelanden krypterade med denna nyckel [10] . Denna sårbarhet och vissa relaterade effekter utnyttjades för att bryta WEP- kryptering på trådlösa IEEE 802.11 -nätverk . Detta visade behovet av att ersätta WEP så snart som möjligt , vilket ledde till utvecklingen av en ny trådlös säkerhetsstandard, WPA .

Kryptosystemet kan göras immunt mot denna attack genom att kassera början av nyckelströmmen. Således kallas den modifierade algoritmen "RC4-drop[n]", där n är antalet byte från början av nyckelströmmen som ska kasseras. Det rekommenderas att använda n = 768, en försiktig uppskattning är n = 3072[11] [12] .

Attacken är baserad på svagheten i initialiseringsvektorn . Genom att känna till det första pseudo-slumpmässiga ordet Koch minmatningsnyckelbyten Key, genom att använda en svaghet i pseudoslumpordsgenereringsalgoritmen K, kan man erhålla m + 1inmatningsnyckelbyten. Genom att upprepa stegen erhålls den fullständiga nyckeln. När man attackerar WEP , n = 8 IVhar for formen (B; 255; N), där B - från 3 till 8, och Nvalfritt nummer . För att fastställa cirka 60 varianter av N skulle det ta cirka 4 miljoner paket att fångas upp. [tio]

Klein Attack

2005 presenterade Andreas Klein en analys av RC4-chifferet där han påpekade den starka korrelationen mellan nyckeln och RC4-nyckelströmmen. Klein analyserade attackerna i den första omgången (liknande PMS-attacken), i den andra omgången och deras möjliga förbättringar. Han föreslog också några ändringar av algoritmen för att förbättra chifferns styrka. Speciellt hävdar han att om du vänder på cykelns riktning i nyckelschemaalgoritmen, så kan du göra chifferet mer motståndskraftigt mot attacker som FMS [1] .

Kombinatoriskt problem

2001 var Adi Shamir och Itzhak Mantin de första som ställde till ett kombinatoriskt problem relaterat till antalet möjliga in- och utgångar från RC4-chifferet. Om av alla möjliga 256 element i chifferns interna tillstånd, xelement från tillståndet ( x ≤ 256) är kända, då, om vi antar att de återstående elementen är noll, är det maximala antalet element som kan erhållas med den deterministiska algoritmen i de kommande 256 omgångarna är också lika med x. 2004 bevisades detta antagande av  Souradyuti Paul och Bart Preneel [ 13 ] . 

Attack of Vanhof and Pissens (2015)

Sommaren 2015 demonstrerade Mathy Vanhoef och Frank Piessens från universitetet i Leuven i Belgien en riktig attack mot TLS-protokollet , som använder RC4 för att kryptera överförd data [14] . Idén med att hacka är baserad på MITM- principen . Genom att bädda in i en dataöverföringskanal genererar angriparen ett stort antal förfrågningar till servern, vilket tvingar den att returnera cookies som svar , krypterade med samma nyckel. Med ungefär 9x2 27 ~ 2 30 {plaintext, ciphertext} par till hands kunde angriparen återställa nyckeln och därför de krypterade cookies baserade på de statistiska metoderna av Fluhrer-McGrew och ABSAB med en sannolikhet på 94%. Den praktiska tiden som spenderades var cirka 52 timmar, medan den övre uppskattningen av den erforderliga tiden vid tiden för demonstrationen var cirka 72 timmar [15] .

RC4 mods

Tidigare övervägdes attacker baserade på korrelationen mellan de första byten i chiffertexten och nyckeln. Sådana svagheter i algoritmen kan lösas genom att kassera den initiala delen av chiffertexten [16] . Det är säkert att kassera de första 256, 512, 768 och 1024 byten. Studier av början av chiffertexten utfördes för att visa opålitligheten hos ett visst antal första bytes, vilket kan leda till att en angripare får en krypteringsnyckel. Flera modifieringar av RC4 har föreslagits som utför uppgiften att förbättra säkerheten vid användning av algoritmen: RC4A, VMPC , RC4+.

RC4A

2004 såg Souradyuti Pauls och Bart Preneels arbete ljuset, som föreslog en modifiering av RC4A [17] .

För RC4A används två S-boxar istället för en, som i RC4, betecknad med S₁och S₂. För dem används två räknare, j₁respektive j₂. Räknaren i, som för RC4, används i singular för hela algoritmen. Algoritmexekveringsprincipen förblir densamma, men det finns ett antal skillnader:

  1. S₁är en parameter för S₂.
  2. För en iteration, det vill säga för en indexökning i, genereras två byte med chiffertext.

Algoritm:

jag := 0 j₁ := 0 j₂ := 0 medan generation loop: i := i + 1 j1:= (j1 + S1[i]) mod 256 byt S₁[i] och S₁[j₁] I₂ := (S1[i] + S₁[j1]) mod 256 utgång  := S₂[I₂] j2 = (j2 + S2[i]) mod 256 byt S₂[i] och S₂[j₂] I1 = (S2[i] + S2[j2]) mod 256 utgång  := S1[I1] under tiden

Krypteringshastigheten för denna algoritm kan ökas genom parallellisering .

RC4+

2008 utvecklades och föreslogs RC4+-modifieringen. Författarna Subhamoy Maitra och Goutam Paul modifierade initieringen av S-boxen (KSA+) med hjälp av 3-nivås scrambling. Dessutom modifierades den pseudo-slumpmässiga ordgenereringsalgoritmen (PRGA+) [18] .

Algoritm:

Alla aritmetiska operationer utförs mod 256. Symbolerna "<<" och ">>" anger bitskiftningar till vänster respektive höger. Symbolen "⊕" anger operationen " exklusive ELLER " medan Generation loop: i := i + 1 a := S[i] j := j + a b := S[j] S[i] := b (byttade S[i] och 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 ] under tiden

Implementering

Många strömchiffer är baserade på linjära återkopplingsskiftregister ( LFSR ) .  Detta gör det möjligt att uppnå högeffektiva implementeringar av chiffer i form av en integrerad krets (hårdvaruimplementering), men komplicerar mjukvaruimplementeringen av sådana chiffer. Eftersom RC4-chifferet inte använder LFSR och är baserat på byte-operationer är det bekvämt att implementera det i mjukvara. En typisk implementering exekverar 8 till 16 maskininstruktioner per byte text, så en mjukvaruimplementering av chiffret bör vara snabb [19] .

Kryptosystem och protokoll som använder RC4

Ordet "(variabel)" betyder att RC4 är en av flera krypteringsalgoritmer som kan användas av systemet.

Se även

Anteckningar

  1. ↑ 1 2 Klein A. Attacker mot RC4-strömchifferet  (odefinierat)  // Design, koder och kryptografi. - 2008. - T. 48 , nr 3 . - S. 269-286 . - doi : 10.1007/s10623-008-9206-6 .
  2. ↑ Rivest FAQ (nedlänk) . Hämtad 15 oktober 2009. Arkiverad från originalet 15 juli 2017. 
  3. ↑ Tack Bob Anderson . Cypherpunks e -postlista (9 september 1994). Hämtad 28 maj 2007.
  4. ↑ RSA Laboratories - 3.6.2 Vad är RC2?
  5. ↑ Bruce Schneier. Tillämpad kryptografi. andra upplagan. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 16 oktober 2013. Arkiverad från originalet 16 november 2012. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Svaga nycklar i RC4 (nedlänk) . Hämtad 7 november 2012. Arkiverad från originalet 18 juni 2012. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Svagheter i nyckelschemaläggningsalgoritmen för RC4  (neopr.)  // Föreläsningsanteckningar i datavetenskap. - 2001. - T. 2259 . - S. 1-24 . - doi : 10.1007/3-540-45537-X_1 . Arkiverad från originalet den 7 september 2008.
  11. ↑ I. Mironov. (Inte så) slumpmässiga blandningar av 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)" . Databas med " Standard namngivning av kryptografisk algoritm ".
  13. ↑ Souradyuti Paul, Bart Preneel. En ny svaghet i RC4 Keystream-generatorn och ett tillvägagångssätt för att förbättra chifferns säkerhet  //  Lecture notes in data science : journal. - 2004. - Vol. 3017 . - S. 245-259 . - doi : 10.1007/b98177 .
  14. ↑ RC4 NOMORE
  15. ↑ Hackare visade en praktisk metod för att hacka RC4
  16. ↑ Ilya Mironov (2002-06-01), (Not So) Random shuffles of RC4 , Advances in cryptology - CRYPTO 2002 , vol. 2442, Föreläsningsanteckningar i datavetenskap, Springer-Verlag, sid. 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 a Approach to Improve Security of the Chipher , Fast Software Encryption, FSE 2004 , vol. 3017, Lecture Notes in Computer Science, Springer-Verlag, sid. 245–259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), Analys av RC4 och förslag till ytterligare lager för bättre säkerhetsmarginal , Framsteg i kryptologi - INDOCRYPT 2008 , vol. 5365, Lecture Notes in Computer science, Springer-Verlag, sid. 27–39, Cryptology ePrint Archive: Report 2008/396, ISBN 3-540-89753-4 , doi : 10.1007/978-3-540-89754-5_3 
  19. ↑ RSA Laboratories - 3.6.3 Vad är RC4?
  20. ↑ Svar arkiverade 24 mars 2010 på Wayback Machine på frågor från användare av Opera miniwebbläsare .
  21. ↑ RFC 4757 . RC4- HMAC kerberos-krypteringstyperna som används av Microsoft Windows .
  22. ↑ PDF & PDF/A-programvara | PDF Tools AG | Premium PDF-teknik Arkiverad 3 november 2005.
  23. ↑ Skypes krypteringsprocedur delvis exponerad . www.h-online.com. Hämtad 8 juli 2010. Arkiverad från originalet 6 november 2012.

Länkar

 Symmetriska kryptosystem
Streama chiffer
Feistel nätverk
SP nätverk
Övrig