RC4

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. július 17-én felülvizsgált verziótól ; az ellenőrzések 19 szerkesztést igényelnek .

Az RC4 (az angol  Rivest cipher 4 vagy Ron kódjából ), más néven ARC4 vagy ARCFOUR ( állítólagos RC4 ) egy adatfolyam-rejtjel , amelyet széles körben használnak a számítógépes hálózatok különféle információbiztonsági rendszereiben (például SSL és TLS protokollokban , vezeték nélküli biztonsági algoritmusokban). WPAésWEP ).

A titkosítást az RSA Security fejlesztette ki, és használatához licenc szükséges .

Az RC4 algoritmus, mint minden adatfolyam titkosítás , egy pszeudo -véletlen bitgenerátor köré épül . A kulcs a generátor bemenetére íródik, és a kimeneten pszeudo-véletlen bitek kerülnek beolvasásra. A kulcs hossza 40 és 2048 bit között lehet [1] . A generált bitek egyenletes eloszlásúak .

A titkosítás fő előnyei:

Az RC4 nagyon sebezhető, ha:

Ezek a tényezők, valamint a használat módja bizonytalanná tehetik a kriptorendszert (például a WEP ).

Történelem

Az RC4 adatfolyam titkosítót Ronald Rivest , az RSA Security készítette 1987 - ben . Az "RC4" rövidítés hivatalosan a "Rivest cipher 4" vagy a " Rivest cipher " rövidítése (a "4" a verziószám; lásd: RC2 , RC5 , RC6 ; Az RC1-et soha nem tették közzé; az RC3-at fejlesztették, de egy biztonsági rést találtak benne ), de gyakran a " Ron's code " (" Ron 's code ") rövidítésének tekintik [2] .

Hét évig a rejtjel üzleti titoknak számított, az algoritmus pontos leírását csak egy titoktartási megállapodás aláírása után közölték , de 1994 szeptemberében a leírását névtelenül elküldték a Cypherpunks levelezőlistájára [ 3] .  Hamarosan megjelent az RC4 leírása a usenet " sci.crypt " hírcsoportban. Innen a forráskód az internet számos webhelyére eljutott . A közzétett algoritmus olyan titkosított szövegeket állított elő a kimeneten , amelyek megegyeztek az eredeti RC4 által előállított rejtjelezett szövegekkel. Az RC4 forráskód legális másolatainak tulajdonosai megerősítették az algoritmusok azonosságát a jelölések és a programstruktúra eltéréseivel.

Mivel ez az algoritmus ismert, már nem üzleti titok . Az "RC4" név azonban az RSA Security védjegye . A védjegytulajdonos esetleges követeléseinek elkerülése érdekében a titkosítást néha „ARCFOUR” vagy „ARC4” néven említik, ami az angolra utal. egy állítólagos RC4  egy "állítólagos" RC4 (mert az RSA Security hivatalosan nem tette közzé az algoritmust).  

Az RC4 titkosítási algoritmust használják néhány széles körben használt titkosítási szabványban és protokollban (például WEP , WPA , SSL és TLS ).

Az RC4 a következőknek köszönhetően vált népszerűvé:

Az Egyesült Államokban az ajánlott kulcshossz háztartási használatra 128 bit. Az SPA ( s oftware publishers a ssociation )  és az Egyesült Államok kormánya között létrejött megállapodás lehetővé tette az RC4 titkosítók exportálását, legfeljebb 40 bites kulcshosszal. Az 56 bites kulcsokat amerikai cégek külföldi fióktelepei használhatják [4] .

Az algoritmus leírása

Az adatfolyam titkosítási algoritmus magja egy függvényből áll - egy pszeudo-véletlen bitgenerátorból ( gamma ), amely kulcsbitek folyamát állítja elő (kulcsfolyam, gamma, pszeudo-véletlen bitsorozat) .

titkosítási algoritmus.

  1. A függvény egy bitsorozatot generál ( ).
  2. A bitsorozat ezután összefűződik a nyílt szöveggel ( ) a modulo two összegzés (xor) művelet segítségével . Az eredmény egy titkosított szöveg ( ):

.

dekódoló algoritmus.

  1. A kulcs bitfolyam (kulcsfolyam) újra létrejön (újragenerálva) ( ).
  2. A kulcs bitfolyama hozzáadódik a titkosított szöveghez ( ) az " xor " művelettel . Az xor művelet tulajdonságai miatt a kimenet az eredeti (titkosítatlan) szöveg ( ):

Az RC4 valójában a blokkméret által meghatározott algoritmusok osztálya (a továbbiakban S-box ). Az n paraméter az algoritmus szóhossza, és az S-box hosszát adja meg . Általában n = 8, de elemzési célból csökkentheti. A biztonság növelése érdekében azonban növelni kell ezt az értéket. Nincs ellentmondás az S-box méretének növelésére szolgáló algoritmusban . Az n növekedésével , mondjuk 16 bitig, az S-box elemei 65 536-ra válnak, és ennek megfelelően a kezdeti iterációs idő megnő. A titkosítási sebesség azonban megnő [5] .

Az RC4 belső állapotát egy 2 n méretű tömb és két számláló ábrázolja. A tömb S-box néven ismert , és a továbbiakban: S. Mindig tartalmazza a szó 2n lehetséges jelentésének permutációját. iA két számlálót és jelöli j.

Az RC4 inicializálása két részből áll:

  1. S-box inicializálás ;
  2. álvéletlen szógenerálás K.

S-box inicializálás

Az algoritmus „kulcsütemező algoritmus” vagy „KSA” néven is ismert. Ez az algoritmus egy, a felhasználó által biztosított kulcsot használ, amely ben tárolódik és bájt Keyhosszúságú . LAz inicializálás a tömb kitöltésével kezdődik S, majd ezt a tömböt a kulcs által meghatározott permutációk keverik. Mivel csak egy műveletet hajtanak végre Sa -n, az állításnak meg kell állnia, hogy az Smindig ugyanazt az értékkészletet tartalmazza, amelyet a kezdeti inicializáláskor adtak meg ( S[i] := i ).

i - nél 0 -tól 255 -ig S[i] := i endfor j := 0 i - nél 0 -tól 255 -ig j := ( j + S[i] + Kulcs[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 S[i] és S[j] felcserélése endfor

Álvéletlen szógeneráció K

Az algoritmusnak ezt a részét pszeudo-véletlen sorrendgenerátornak nevezik ( p seudor  andom generation a lgorithm , PRGA ) . Az RC4 kulcsfolyam-generátor módosítja a -ban tárolt értékeket . Egy RC4 ciklusban a kulcsfolyamból egy n bites szó kerül meghatározásra. A jövőben a kulcsszót modulo two-val egészítik ki azzal a nyílt szöveggel, amelyet a felhasználó titkosítani szeretne, és megkapja a titkosított szöveget. SK

én := 0 j := 0 míg generációs hurok: i := ( i + 1 ) mod 256 j := ( j + S[i] ) mod 256 S[i] és S[j] felcserélése t := ( S[i] + S[j] ) mod 256 K := S[t] generált pszeudo-véletlen szó K ( n = 8 esetén egy bájt generálódik) endwhile

Biztonság

Ellentétben a modern titkosításokkal (például az eSTREAM ), az RC4 nem használ nonce -t (az angol nonce - "szám, amelyet csak egyszer lehet használni" - egy szám, amelyet csak egyszer lehet használni) a kulcs mellett. Ez azt jelenti, hogy ha egy kulcsot kell használni több adatfolyam titkosításához, akkor magának az RC4-et használó titkosítási rendszernek kombinálnia kell az alkalmat és a hosszú távú kulcsot, hogy létrehozza az RC4 adatfolyam-kulcsát. Az egyik lehetséges megoldás egy új kulcs létrehozása az RC4 számára a hosszú távú kulcs és a nonce hash függvényével . Azonban sok RC4-et használó alkalmazás egyszerűen összefűzi a kulcsot és a nonce -t . Emiatt és az RC4-ben használt gyenge kulcsütemezés miatt az alkalmazás sebezhetővé válhat [6] [7] [8] . Ezért sok szoftvercég, például a Microsoft , elavulttá vált . Például a Microsoft .NET-keretrendszeréből hiányzik az RC4 megvalósítása.

Itt megvizsgáljuk a titkosítás elleni támadásokat és az ellenük való védekezés módszereit.

Roose kutatása és a kulcs helyreállítása a permutációból

1995-ben Andrew Roos kísérletileg megfigyelte, hogy a kulcsfolyam első bájtja korrelál a kulcs első három bájtjával, és a permutáció első néhány bájtja a kulcsütemezési algoritmus ( eng  . KSA ) után valamilyen lineáris kombinációval korrelál. kulcsbájtokból [9] . Ezeket a torzításokat 2007-ig nem sikerült bebizonyítani, amikor Paul, Rafi és Maitrae bebizonyította, hogy a kulcs és a kulcsfolyam összefügg. Ezenkívül Paul és Maitre bebizonyította a permutáció és a kulcs összefüggését. Az utóbbi munka kulcspermutáció korrelációt is használ az első teljes kulcs-helyreállítási algoritmus létrehozásához a KSA utáni utolsó permutációból, anélkül, hogy feltételezéseket tenne a kulcsról és az inicializálási vektorról ( IV , i nitial v ector ) . Ennek az algoritmusnak állandó a sikerének valószínűsége az idő múlásával, ami a nyers erő összetettségének négyzetgyöke. Az utóbbi időben sok munka történt a kulcs helyreállításán az RC4 belső állapotából.   

Fluhrer, Mantin és Shamir támadása (FMS)

2001-ben Fluhrer, Mantin és Shamir publikált egy tanulmányt az RC4 kulcsütemezésének sebezhetőségéről. Megmutatták, hogy a kulcsfolyam első bájtjai az összes lehetséges kulcs közül nem véletlenszerűek. Ezekből a bájtokból nagy valószínűséggel lehet információt szerezni a használt rejtjelkulcsról. És ha egy hosszú távú kulcsot és egy nonce - t egyszerűen összeragasztanak egy RC4 rejtjelkulcs létrehozásához, akkor ezt a hosszú távú kulcsot úgy kaphatjuk meg, ha kellően nagy számú, ezzel a kulccsal titkosított üzenetet elemezünk [10] . Ezt a sérülékenységet és néhány kapcsolódó hatást a WEP titkosítás megszakítására használták ki az IEEE 802.11 vezeték nélküli hálózatokon . Ez megmutatta a WEP mielőbbi lecserélésének szükségességét, ami egy új vezeték nélküli biztonsági szabvány, a WPA kifejlesztéséhez vezetett .

A kriptorendszer immunissá tehető ezzel a támadással szemben, ha eldobjuk a kulcsfolyam elejét. Így a módosított algoritmust "RC4-drop[n]"-nak hívják, ahol n a kulcsfolyam elejétől számított bájtok száma, amelyet el kell dobni. Használata javasolt n = 768, óvatos becslés: n = 3072[11] [12] .

A támadás az inicializálási vektor gyengeségén alapul . Az első pszeudo-véletlen szó és beviteli kulcs bájtjainak ismeretében , az álvéletlen szógeneráló algoritmus egy gyenge pontját felhasználva megkaphatjuk a beviteli kulcs bájtját. A lépések megismétlésével a teljes kulcsot megkapjuk. A WEP támadásakor a for alakja (B; 255; N), ahol  - 3-tól 8-ig, és tetszőleges szám . Az N körülbelül 60 változatának meghatározásához körülbelül 4 millió csomagot kellene elfogni. [tíz]KmKeyKm + 1n = 8 IVBN

Klein Attack

2005-ben Andreas Klein bemutatta az RC4 titkosítás elemzését, amelyben rámutatott a kulcs és az RC4 kulcsfolyam közötti szoros összefüggésre. Klein elemezte a támadásokat az első körben (hasonlóan a PMS-támadáshoz), a második körben és azok lehetséges fejlesztéseit. Néhány változtatást javasolt az algoritmusban is, hogy javítsa a titkosítás erősségét. Különösen azzal érvel, hogy ha megfordítja a ciklus irányát a kulcsütemezési algoritmusban, akkor a titkosítást ellenállóbbá teheti az olyan támadásokkal szemben, mint az FMS [1] .

Kombinatorikus probléma

2001-ben Adi Shamir és Itzhak Mantin voltak az elsők, akik kombinatorikus problémát vetettek fel az RC4 titkosítás lehetséges be- és kimeneteinek számával kapcsolatban. Ha a rejtjel belső állapotának összes lehetséges 256 eleméből ismertek xa ( x ≤ 256) állapotból származó elemek, akkor, ha feltételezzük, hogy a fennmaradó elemek nullák, akkor a determinisztikus algoritmussal maximálisan megkapható elemek száma a következő 256 kör is egyenlő x. 2004-ben ezt a feltevést Souradyuti Paul és  Bart Preneel is bebizonyította [ 13 ] . 

Vanhof és Pissens támadása (2015)

2015 nyarán Mathy Vanhoef és Frank Piessens a belgiumi Leuveni Egyetemről valódi támadást mutattak be a TLS protokoll ellen , amely az RC4-et használja a továbbított adatok titkosítására [14] . A hackelés ötlete a MITM elvén alapul . Az adatátviteli csatornába való beágyazással a támadó nagyszámú kérést generál a szerver felé, és válaszul arra kényszeríti, hogy cookie -kat küldjön vissza , ugyanazzal a kulccsal titkosítva. Körülbelül 9x2 27 ~ 230 { plaintext , ciphertext } párral a támadó 94%-os valószínűséggel tudta visszaállítani a kulcsot, és így a titkosított cookie -kat a Fluhrer-McGrew és az ABSAB statisztikai módszerei alapján. A gyakorlati idő kb. 52 óra volt, míg a demonstráció idején szükséges idő felső becslése kb. 72 óra [15] .

RC4 modok

Korábban a rejtjelezett szöveg és a kulcs első bájtjainak korrelációján alapuló támadásokat vették számításba. Az algoritmus ilyen gyengeségei a rejtjelezett szöveg kezdeti részének elvetésével oldhatók meg [16] . Az első 256, 512, 768 és 1024 bájt biztonságos eldobása. A rejtjelezett szöveg kezdetére vonatkozó tanulmányokat végeztek annak kimutatására, hogy bizonyos számú első bájt megbízhatatlan, ami oda vezethet, hogy a támadó titkosítási kulcsot kap. Az RC4 számos olyan módosítását javasolták, amelyek az algoritmus használatakor a biztonság fokozását látják el: RC4A, VMPC , RC4+.

RC4A

2004-ben Souradyuti Paul és Bart Preneel munkája látott napvilágot, amely az RC4A [17] módosítását javasolta .

Az RC4A esetében két S-boxot használunk egy helyett, mint az RC4-ben, S₁és jelöléssel S₂. Számukra két számlálót használnak, j₁ill j₂. Az RC4-hez hasonlóan a számlálót iegyes számban használjuk a teljes algoritmushoz. Az algoritmus végrehajtási elve változatlan marad, de számos különbség van:

  1. S₁paramétere a S₂.
  2. Egy iterációhoz, azaz egy iindexnöveléshez két bájt titkosított szöveg jön létre.

Algoritmus:

én := 0 j₁ := 0 j₂ := 0 míg generációs hurok: i := i + 1 j₁ := ( j₁ + S₁[i] ) mod 256 S₂[i] és S₁[j₁] felcserélése I₂ := ( S1[i] + S1[jl] ) mod 256 kimenet  := S₂[I₂] j₂ = ( j₂ + S₂[i] ) mod 256 S₂[i] és S₂[j₂] felcserélése I₁ = ( S2[i] + S₂[j2] ) mod 256 kimenet  := S₁[I₁] endwhile

Ennek az algoritmusnak a titkosítási sebessége párhuzamosítással növelhető .

RC4+

2008-ban kidolgozták és javasolták az RC4+ módosítást. Subhamoy Maitra és Goutam Paul szerzők 3-szintű kódolással módosították az S-box (KSA+) inicializálását. Az álvéletlen szógeneráló algoritmus (PRGA+) [18] is módosult .

Algoritmus:

Minden aritmetikai műveletet a 256-os módban hajtunk végre. A "<<" és ">>" szimbólumok balra, illetve jobbra történő biteltolódást jelölnek . A "⊕" szimbólum az " exkluzív VAGY " műveletet jelöli , miközben a Generációs ciklus: i := i + 1 a := S[i] j := j + a b := S[j] S[i] := b (S[i] és S[j] felcserélve) S[j] := a c := S[i<<5⊕j>>3] + S[j<<5⊕i>>3] kimenet ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ] endwhile

Megvalósítás

Sok adatfolyam titkosítás lineáris visszacsatolásos eltolási regisztereken ( LFSR ) alapul .  Ez lehetővé teszi a titkosítás nagy hatékonyságú megvalósítását integrált áramkör formájában (hardveres megvalósítás), de megnehezíti az ilyen rejtjelek szoftveres megvalósítását. Mivel az RC4 titkosítás nem használja az LFSR-t, és bájtműveleteken alapul, célszerű szoftverben implementálni. Egy tipikus megvalósítás 8-16 gépi utasítást hajt végre szövegbájtonként , ezért a titkosítás szoftveres megvalósításának gyorsnak kell lennie [19] .

RC4-et használó kriptorendszerek és protokollok

A "(változó)" szó azt jelenti, hogy az RC4 a rendszer által használható számos titkosítási algoritmus egyike.

Lásd még

Jegyzetek

  1. ↑ 1 2 Klein A. Támadások az RC4 adatfolyam titkosítására  (undefined)  // Tervek, kódok és kriptográfia. - 2008. - T. 48 , 3. sz . - S. 269-286 . - doi : 10.1007/s10623-008-9206-6 .
  2. ↑ Rivest GYIK (downlink) . Letöltve: 2009. október 15. Az eredetiből archiválva : 2017. július 15. 
  3. ↑ Köszönöm Bob Anderson . Cypherpunks levelezőlista (1994. szeptember 9.). Letöltve: 2007. május 28.
  4. ↑ RSA Laboratories – 3.6.2 Mi az RC2?
  5. ↑ Bruce Schneier. Alkalmazott kriptográfia. második kiadás. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Archivált másolat (a hivatkozás nem elérhető) . Letöltve: 2013. október 16. Az eredetiből archiválva : 2012. november 16.. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Gyenge kulcsok az RC4-ben (downlink) . Letöltve: 2012. november 7. Az eredetiből archiválva : 2012. június 18.. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Az RC4 (neopr.) kulcsfontosságú ütemezési algoritmusának gyengeségei   // Számítástechnikai előadásjegyzetek. - 2001. - T. 2259 . - S. 1-24 . - doi : 10.1007/3-540-45537-X_1 . Archiválva az eredetiből 2008. szeptember 7-én.
  11. ↑ I. Mironov. (Nem úgy) véletlenszerű keveredés az RC4  -ből (neopr.)  // Lecture Notes in Computer Science. - 2002. - T. 2442 . - S. 304-319 . - doi : 10.1007/3-540-45708-9_20 .
  12. ↑ "RC4-drop(nbytes)" . " Szabványos kriptográfiai algoritmusok elnevezése " adatbázis.
  13. ↑ Souradyuti Paul, Bart Preneel. Új gyengeség az RC4 Keystream generátorban és megközelítés a titkosítás biztonságának javítására  //  Lecture notes in Computer science : Journal. - 2004. - 20. évf. 3017 . - 245-259 . o . - doi : 10.1007/b98177 .
  14. ↑ RC4 NEM
  15. ↑ A hackerek egy praktikus módszert mutattak be az RC4 feltörésére
  16. ↑ Ilja Mironov (2002-06-01), (Nem úgy) Az RC4 véletlenszerű keverései , A kriptológia fejlődése - CRYPTO 2002 , vol. 2442, Előadásjegyzet a számítástechnikából, Springer-Verlag, p. 304–319, Cryptology ePrint archívum: Jelentés 2002/067, ISBN 3-540-44050-X , doi : 10.1007/3-540-45708-9_20 
  17. ↑ Souradyuti Paul és Bart Preneel (2004), Új gyengeség az RC4 kulcsfolyam-generátorban és megközelítés a titkosítás biztonságának javítására , Fast Software Encryption, FSE 2004 , vol. 3017, Lecture Notes in Computer Science, Springer-Verlag, p. 245–259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra és Goutam Paul (2008-09-19), Az RC4 elemzése és javaslat további rétegekre a jobb biztonsági rés érdekében , Progress in Cryptology - INDOCRYPT 2008 , vol. 5365, Lecture Notes in Computer Science, Springer-Verlag, p. 27–39., Cryptology ePrint Archívum: Jelentés 2008/396, ISBN 3-540-89753-4 , doi : 10.1007/978-3-540-89754-5_3 
  19. ↑ RSA Laboratories – 3.6.3 Mi az RC4?
  20. ↑ A válaszok archiválva 2010. március 24-én a Wayback Machine -nél az Opera mini böngésző felhasználóinak kérdéseire .
  21. ↑ RFC 4757 . A Microsoft Windows által használt RC4- HMAC kerberos titkosítási típusok .
  22. ↑ PDF és PDF/A szoftver | PDF Tools AG | Prémium PDF technológia Archiválva : 2005. november 3.
  23. ↑ A Skype titkosítási eljárása részben nyilvánosságra került . www.h-online.com. Letöltve: 2010. július 8. Az eredetiből archiválva : 2012. november 6..

Linkek

 Szimmetrikus titkosítási rendszerek
Rejtjelfolyam adatfolyam
Feistel hálózat
SP hálózat
Egyéb