RC4

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. července 2018; kontroly vyžadují 19 úprav .

RC4 (z anglického  Rivest cipher 4 nebo Ron's code ), také známý jako ARC4 nebo ARCFOUR ( údajně RC4 ) je proudová šifra široce používaná v různých systémech zabezpečení informací v počítačových sítích (například v protokolech SSL a TLS , algoritmech bezdrátového zabezpečení Sítě WPAaWEP ).

Šifru vyvinula společnost RSA Security a k jejímu použití je zapotřebí licence .

Algoritmus RC4, stejně jako každá proudová šifra , je postaven na generátoru pseudonáhodných bitů . Klíč se zapíše na vstup generátoru a na výstupu se čtou pseudonáhodné bity. Délka klíče může být od 40 do 2048 bitů [1] . Generované bity mají rovnoměrné rozložení .

Hlavní výhody šifry:

RC4 je docela zranitelný, pokud:

Tyto faktory, stejně jako způsob, jakým se používá, mohou způsobit, že kryptosystém nebude bezpečný (jako je WEP ).

Historie

Proudovou šifru RC4 vytvořil v roce 1987 Ronald Rivest z RSA Security . Zkratka „RC4“ oficiálně znamená „Rivest cipher 4“ nebo „ Rivest cipher “ („4“ je číslo verze; viz RC2 , RC5 , RC6 ; RC1 nebyl nikdy publikován; RC3 byl vyvinut, ale byla v něm nalezena zranitelnost ), ale často se považuje za zkratku pro " Ronův kód " (" Ronův kód ") [2] .

Po sedm let byla šifra obchodním tajemstvím a přesný popis algoritmu byl poskytnut až po podepsání smlouvy o mlčenlivosti , ale v září 1994 byl její popis anonymně zaslán do e- mailové konference Cypherpunks [ 3 ] .  Brzy byl popis RC4 zveřejněn na diskusní skupině usenet " sci.crypt ". Odtud si zdrojový kód našel cestu na mnoho stránek na internetu . Publikovaný algoritmus vytvořil na výstupu šifrové texty, které odpovídaly šifrovým textům vytvořeným původním RC4. Vlastníci legálních kopií zdrojového kódu RC4 potvrdili identitu algoritmů s rozdíly v notaci a programové struktuře.

Protože je tento algoritmus znám, již není obchodním tajemstvím . Název „RC4“ je však ochrannou známkou společnosti RSA Security . Aby se předešlo případným nárokům ze strany vlastníka ochranné známky , šifra je někdy označována jako „ARCFOUR“ nebo „ARC4“ s odkazem na angličtinu.  údajný RC4 je "domnělý" RC4  (protože RSA Security oficiálně nezveřejnila algoritmus).

Šifrovací algoritmus RC4 se používá v některých široce používaných šifrovacích standardech a protokolech (například WEP , WPA , SSL a TLS ).

RC4 se stal populární díky:

V USA je doporučená délka klíče pro domácí použití 128 bitů. Dohoda mezi SPA ( sdružení vydavatelů oftwaru )  a vládou USA umožnila export šifer RC4 s délkou klíče až 40 bitů. 56bitové klíče mohou používat zahraniční pobočky amerických společností [4] .

Popis algoritmu

Jádro algoritmu proudové šifry tvoří funkce - generátor pseudonáhodných bitů ( gama ), který vytváří proud klíčových bitů (tok klíčů, gama, sekvence pseudonáhodných bitů).

šifrovací algoritmus.

  1. Funkce generuje bitovou sekvenci ( ).
  2. Posloupnost bitů je pak zřetězena s otevřeným textem ( ) pomocí operace modulo dva součtu (xor) . Výsledkem je šifrovaný text ( ):

.

dešifrovací algoritmus.

  1. Tok bitů klíčů (tok klíčů) je znovu vytvořen (regenerován) ( ).
  2. Bitový proud klíče je přidán do šifrového textu ( ) pomocí operace " xor " . Vzhledem k vlastnostem operace xor je výstupem původní (nešifrovaný) text ( ):

RC4 je vlastně třída algoritmů definovaná velikostí bloku (dále jen S-box ). Parametr n je délka slova pro algoritmus a udává délku S-boxu . Obvykle je n = 8, ale pro účely analýzy jej můžete snížit. Chcete-li však zlepšit zabezpečení, musíte tuto hodnotu zvýšit. V algoritmu pro zvětšení velikosti S-boxu není žádný rozpor . Se zvýšením n , řekněme až na 16 bitů, se prvky v S-boxu stanou 65 536 a v souladu s tím se prodlouží počáteční doba iterace. Zvýší se však rychlost šifrování [5] .

Vnitřní stav RC4 je reprezentován jako pole velikosti 2 n a dva čítače. Pole je známé jako S-box a bude označováno jako S. Vždy obsahuje permutaci 2n možných významů slova. Dva čítače jsou označeny ia j.

Inicializace RC4 se skládá ze dvou částí:

  1. inicializace S-boxu ;
  2. pseudonáhodné generování slov K.

Inicializace S-boxu

Algoritmus je také známý jako „algoritmus rozvrhování klíčů“ nebo „KSA“. Tento algoritmus používá klíč dodaný uživatelem, uložený v Key, a mající délku Lbajtů. Inicializace začíná vyplněním pole S, poté je toto pole zamícháno permutacemi určenými klíčem. Protože se na , provádí pouze jedna akce S, musí tvrzení platit, že Svždy obsahuje stejnou sadu hodnot, která byla zadána při počáteční inicializaci ( S[i] := i ).

pro i od 0 do 255 S[i] := i endfor j:= 0 pro i od 0 do 255 j := ( j + S[i] + Key[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 vyměnit S[i] a S[j] endfor

Pseudonáhodné generování slov K

Tato část algoritmu se nazývá generátor pseudonáhodné sekvence ( p seudor  andom generation a lgorithm , PRGA ) . Generátor keystreamu RC4 permutuje hodnoty uložené v . V jednom cyklu RC4 je určeno jedno n - bitové slovo z toku klíčů. V budoucnu bude klíčové slovo přidáno modulo dva s otevřeným textem, který chce uživatel zašifrovat, a získá se šifrovaný text. SK

i:= 0 j:= 0 zatímco generovací smyčka: i := (i + 1) mod 256 j:= (j + S[i]) mod 256 vyměnit S[i] a S[j] t:= (S[i] + S[j]) mod 256 K := S[t] vygenerováno pseudonáhodné slovo K (pro n = 8 bude vygenerován jeden bajt) endwhile

Zabezpečení

Na rozdíl od moderních šifer (jako je eSTREAM ), RC4 nepoužívá spolu s klíčem nonce (z anglického nonce - "číslo, které lze použít pouze jednou" - číslo, které lze použít pouze jednou). To znamená, že pokud má být jeden klíč použit v průběhu času k šifrování více streamů, kryptosystém využívající RC4 sám musí kombinovat příležitost a dlouhodobý klíč, aby vytvořil streamový klíč pro RC4. Jedním z možných řešení je vygenerování nového klíče pro RC4 pomocí hašovací funkce dlouhodobého klíče a nonce . Nicméně mnoho aplikací používajících RC4 jednoduše zřetězí klíč a nonce . Kvůli tomu a slabému plánování klíče používané v RC4 se aplikace může stát zranitelnou [6] [7] [8] . Proto byl zamítnut mnoha softwarovými společnostmi, jako je Microsoft . Například Microsoft .NET Framework postrádá implementaci RC4.

Zde budou zváženy některé útoky na šifru a způsoby ochrany proti nim.

Rooseův výzkum a obnovení klíče z permutace

V roce 1995 Andrew Roos experimentálně pozoroval, že první bajt toku klíčů koreluje s prvními třemi bajty klíče a prvních pár bajtů permutace po algoritmu pro plánování klíčů ( angl  . KSA ) koreluje s nějakou lineární kombinací . klíčových bajtů [9] . Tyto předsudky byly prokázány až v roce 2007, kdy Paul, Rafi a Maitrae dokázali, že klíč a klíčový proud spolu souvisí. Paul a Maitre také dokázali korelaci permutace a klíče. Tato práce také používá korelaci klíč-permutace ke generování prvního úplného algoritmu obnovy klíče z poslední permutace po KSA, aniž by se dělaly předpoklady o klíči a inicializačním vektoru ( IV , počáteční vektor ) . Tento algoritmus má konstantní pravděpodobnost úspěchu v průběhu času, což je druhá odmocnina složitosti hrubé síly. V poslední době bylo vykonáno mnoho práce na obnovení klíče z vnitřního stavu RC4.   

Útok Fluhrera, Mantina a Shamira (FMS)

V roce 2001 Fluhrer, Mantin a Shamir publikovali článek o zranitelnosti klíčového plánu RC4. Ukázali, že první bajty toku klíčů mezi všemi možnými klíči nejsou náhodné. Z těchto bajtů je možné s vysokou pravděpodobností získat informaci o použitém šifrovacím klíči. A pokud se dlouhodobý klíč a nonce jednoduše slepí dohromady a vytvoří se šifrovací klíč RC4, pak lze tento dlouhodobý klíč získat analýzou dostatečně velkého počtu zpráv zašifrovaných pomocí tohoto klíče [10] . Tato chyba zabezpečení a některé související účinky byly zneužity k prolomení šifrování WEP v bezdrátových sítích IEEE 802.11 . To ukázalo potřebu co nejdříve nahradit WEP , což vedlo k vývoji nového bezdrátového bezpečnostního standardu WPA .

Kryptosystém může být vůči tomuto útoku imunní tím, že zahodí začátek klíčového proudu. Upravený algoritmus se tedy nazývá "RC4-drop[n]", kde n je počet bajtů od začátku toku klíčů, které mají být vyřazeny. Doporučuje se použít n = 768, konzervativní odhad je n = 3072[11] [12] .

Útok je založen na slabosti inicializačního vektoru . Když známe první pseudonáhodné slovo Ka mbajty vstupního klíče Key, lze pomocí slabiny v algoritmu generování pseudonáhodných slov Kzískat m + 1bajt vstupního klíče. Opakováním kroků získáte úplný klíč. Při útoku na WEP má for n = 8 IVtvar (B; 255; N), kde B - od 3 do 8 a Nlibovolné číslo . K určení asi 60 variant N by bylo potřeba zachytit asi 4 miliony paketů. [deset]

Klein Attack

V roce 2005 představil Andreas Klein analýzu šifry RC4, ve které poukázal na silnou korelaci mezi klíčem a keystreamem RC4. Klein analyzoval útoky v prvním kole (obdoba útoku PMS), ve druhém kole a jejich možná vylepšení. Navrhl také některé změny v algoritmu, aby se zlepšila síla šifry. Konkrétně tvrdí, že pokud obrátíte směr cyklu v algoritmu klíče rozvrhu, můžete šifru učinit odolnější vůči útokům, jako je FMS [1] .

Kombinatorický problém

V roce 2001 byli Adi Shamir a Itzhak Mantin první, kdo nastolil kombinatorický problém související s počtem možných vstupů a výstupů šifry RC4. Pokud jsou ze všech možných 256 prvků vnitřního stavu šifry známy xprvky ze stavu ( x ≤ 256), pak, pokud předpokládáme, že zbývající prvky jsou nulové, maximální počet prvků, které lze získat deterministickým algoritmem v dalších 256 kol se také rovná x. V roce 2004 tento předpoklad prokázali Souradyuti  Paul a Bart Preneel [ 13 ] . 

Attack of Vanhof and Pissens (2015)

V létě 2015 předvedli Mathy Vanhoef a Frank Piessens z University of Leuven v Belgii skutečný útok na protokol TLS , který využívá RC4 k šifrování přenášených dat [14] . Myšlenka hackování je založena na principu MITM . Vložením do kanálu pro přenos dat útočník generuje velké množství požadavků na server a nutí jej, aby v odpovědi vrátil soubory cookie zašifrované stejným klíčem. S přibližně 9x2 27 ~ 2 30 páry {plaintext, ciphertext} po ruce se útočníkovi podařilo obnovit klíč a tedy i zašifrované soubory cookie na základě statistických metod Fluhrer-McGrew a ABSAB s pravděpodobností 94 %. Praktická doba strávená byla asi 52 hodin, přičemž horní odhad potřebné doby v době demonstrace byl asi 72 hodin [15] .

RC4 mody

Dříve byly zvažovány útoky založené na korelaci prvních bajtů šifrového textu a klíče. Takové slabiny algoritmu lze vyřešit vyřazením počáteční části šifrového textu [16] . Je bezpečné zahodit prvních 256, 512, 768 a 1024 bajtů. Byly provedeny studie začátku šifrového textu, aby se prokázala nespolehlivost určitého počtu prvních bajtů, což může vést k tomu, že útočník získá šifrovací klíč. Bylo navrženo několik modifikací RC4, které plní úlohu zvýšení bezpečnosti při použití algoritmu: RC4A, VMPC , RC4+.

RC4A

V roce 2004 spatřila světlo práce Souradyuti Paul a Bart Preneel, která navrhla modifikaci RC4A [17] .

Pro RC4A jsou použity dva S-boxy místo jednoho, jako u RC4, označené S₁a S₂. Pro ně se používají dva čítače, j₁resp j₂. Čítač i, stejně jako u RC4, se pro celý algoritmus používá v jednotném čísle. Princip provádění algoritmu zůstává stejný, ale existuje řada rozdílů:

  1. S₁je parametr pro S₂.
  2. Pro jednu iteraci, tedy pro jedno zvýšení indexu i, se vygenerují dva bajty šifrového textu.

Algoritmus:

i:= 0 j₁ := 0 j₂ := 0 zatímco generovací smyčka: i := i + 1 j₁ := ( j₁ + S₁[i] ) mod 256 vyměnit S₁[i] a S₁[j₁] I₂ := ( S₁[i] + S₁[j₁] ) mod 256 výstup  := S₂[I₂] j2 = (j2 + S2[i]) mod 256 vyměňte S2[i] a S2[j₂] I₁ = ( S₂[i] + S₂[j₂] ) mod 256 výstup  := S₁[I₁] endwhile

Rychlost šifrování tohoto algoritmu lze zvýšit paralelizací .

RC4+

V roce 2008 byla vyvinuta a navržena modifikace RC4+. Autoři Subhamoy Maitra a Goutam Paul upravili inicializaci S-boxu (KSA+) pomocí 3-úrovňového kódování. Také byl upraven algoritmus generování pseudonáhodných slov (PRGA+) [18] .

Algoritmus:

Všechny aritmetické operace se provádějí mod 256. Symboly "<<" a ">>" označují bitové posuny doleva a doprava. Symbol "⊕" označuje operaci " exkluzivní NEBO " při generační smyčce: i := i + 1 a := S[i] j := j + a b := S[j] S[i] := b (prohozené S[i] a S[j]) S[j] := a c := S[ i<<5 ⊕ j>>3 ] + S[ j<<5 ⊕ i>>3 ] výstup ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ] endwhile

Implementace

Mnoho proudových šifer je založeno na lineárních zpětnovazebních posuvných registrech ( LFSR ) .  To umožňuje dosáhnout vysoce efektivní implementace šifry ve formě integrovaného obvodu (hardwarová implementace), ale komplikuje softwarovou implementaci takových šifer. Protože šifra RC4 nepoužívá LFSR a je založena na bajtových operacích, je vhodné ji softwarově implementovat. Typická implementace provádí 8 až 16 strojových instrukcí na bajt textu, takže softwarová implementace šifry by měla být rychlá [19] .

Kryptosystémy a protokoly využívající RC4

Slovo "(proměnná)" znamená, že RC4 je jedním z několika šifrovacích algoritmů, které může systém používat.

Viz také

Poznámky

  1. ↑ 1 2 Klein A. Útoky na proudovou šifru RC4  (nedefinováno)  // Návrhy, kódy a kryptografie. - 2008. - T. 48 , č. 3 . - S. 269-286 . - doi : 10.1007/s10623-008-9206-6 .
  2. ↑ Rivest FAQ (downlink) . Získáno 15. října 2009. Archivováno z originálu 15. července 2017. 
  3. ↑ Děkuji Bob Anderson . Seznam adresátů Cypherpunks (9. září 1994). Staženo 28. května 2007.
  4. ↑ RSA Laboratories - 3.6.2 Co je RC2?
  5. ↑ Bruce Schneier. Aplikovaná kryptografie. druhé vydání. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 16. října 2013. Archivováno z originálu 16. listopadu 2012. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Slabé klíče v RC4 (downlink) . Získáno 7. listopadu 2012. Archivováno z originálu 18. června 2012. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Slabé stránky v klíčovém plánovacím algoritmu RC4  (neopr.)  // Poznámky k přednáškám z informatiky. - 2001. - T. 2259 . - S. 1-24 . - doi : 10.1007/3-540-45537-X_1 . Archivováno z originálu 7. září 2008.
  11. ↑ I. Mironov. (Ne tak) náhodné míchání RC4  (neopr.)  // Poznámky k přednáškám z informatiky. - 2002. - T. 2442 . - S. 304-319 . - doi : 10.1007/3-540-45708-9_20 .
  12. ↑ "RC4-drop(nbytes)" . Databáze " Standardní pojmenování kryptografických algoritmů ".
  13. ↑ Souradyuti Paul, Bart Preneel. Nová slabina v generátoru RC4 Keystream a přístup ke zlepšení zabezpečení šifry  //  Poznámky k přednáškám z počítačové vědy: časopis. - 2004. - Sv. 3017 . - str. 245-259 . - doi : 10.1007/b98177 .
  14. ↑ RC4 NOMORE
  15. ↑ Hackeři ukázali praktickou metodu hackování RC4
  16. ↑ Ilya Mironov (2002-06-01), (Ne tak) Random shuffles of RC4 , Pokroky v kryptologii - CRYPTO 2002 , sv. 2442, Poznámky k přednáškám z informatiky, Springer-Verlag, s. 304–319, Archiv kryptologie ePrint: Zpráva 2002/067, ISBN 3-540-44050-X , doi : 10.1007/3-540-45708-9_20 
  17. ↑ Souradyuti Paul & Bart Preneel (2004), Nová slabina v generátoru RC4 Keystream a přístup ke zlepšení bezpečnosti šifry , Rychlé softwarové šifrování, FSE 2004 , sv. 3017, Poznámky k přednáškám z informatiky, Springer-Verlag, s. 245–259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), Analýza RC4 a návrh dalších vrstev pro lepší bezpečnostní marži , Pokrok v kryptologii - INDOCRYPT 2008 , sv. 5365, Poznámky k přednáškám z informatiky, Springer-Verlag, s. 27–39, Archiv kryptologie ePrint: Zpráva 2008/396, ISBN 3-540-89753-4 , doi : 10.1007/978-3-540-89754-5_3 
  19. ↑ RSA Laboratories - 3.6.3 Co je RC4?
  20. ↑ Odpovědi archivované 24. března 2010 na Wayback Machine na dotazy uživatelů mini prohlížeče Opera .
  21. ↑ RFC 4757 . Typy šifrování Kerberos RC4- HMAC používané systémem Microsoft Windows .
  22. ↑ Software PDF a PDF/A | PDF Tools AG | Prémiová technologie PDF Archivováno 3. listopadu 2005.
  23. ↑ Postup šifrování Skype je částečně odhalen . www.h-online.com. Získáno 8. července 2010. Archivováno z originálu dne 6. listopadu 2012.

Odkazy

 Symetrické kryptosystémy
Streamové šifry
Síť Feistel
Síť SP
jiný