RC4

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. heinäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 19 muokkausta .

RC4 ( englanninkielisestä  Rivest-salauksesta 4 tai Ronin koodista ), joka tunnetaan myös nimellä ARC4 tai ARCFOUR ( väitetty RC4 ) on tietovirtasalaus, jota käytetään laajalti erilaisissa tietoturvajärjestelmissä tietokoneverkoissa (esim. SSL- ja TLS-protokollat , langattomat suojausalgoritmit WPA-jaWEP- ).

Salauksen on kehittänyt RSA Security , ja sen käyttöön tarvitaan lisenssi .

RC4-algoritmi, kuten mikä tahansa virtasalaus , on rakennettu näennäissatunnaisen bittigeneraattorin ympärille . Avain kirjoitetaan generaattorin tuloon ja pseudosatunnaiset bitit luetaan lähdöstä. Avaimen pituus voi olla 40 - 2048 bittiä [1] . Luoduilla biteillä on tasainen jakautuminen .

Salauksen tärkeimmät edut:

RC4 on melko haavoittuvainen, jos:

Nämä tekijät sekä tapa, jolla sitä käytetään, voivat tehdä kryptojärjestelmästä epävarman (kuten WEP ).

Historia

RC4 - virtasalauksen loi vuonna 1987 Ronald Rivest RSA Securitysta . Lyhenne "RC4" tarkoittaa virallisesti "Rivest cipher 4" tai " Rivest cipher " ("4" on versionumero; katso RC2 , RC5 , RC6 ; RC1:tä ei koskaan julkaistu; RC3 kehitettiin, mutta siinä löydettiin haavoittuvuus ), mutta sitä pidetään usein lyhenteenä sanoista " Ron's code " (" Ron 's code ") [2] .

Seitsemän vuoden ajan salaus oli liikesalaisuus , ja tarkka kuvaus algoritmista toimitettiin vasta salassapitosopimuksen allekirjoittamisen jälkeen , mutta syyskuussa 1994 sen kuvaus lähetettiin nimettömänä Cypherpunks - postituslistalle [ 3] .  Pian RC4:n kuvaus julkaistiin usenet-uutisryhmässä " sci.crypt ". Sieltä lähdekoodi löysi tiensä monille Internetin sivustoille . Julkaistu algoritmi tuotti lähdössä salatekstejä , jotka vastasivat alkuperäisen RC4:n tuottamia salatekstejä. RC4- lähdekoodin laillisten kopioiden omistajat vahvistivat algoritmien identiteetin merkinnöissä ja ohjelmarakenteessa eroilla.

Koska tämä algoritmi tunnetaan, se ei ole enää liikesalaisuus . Nimi "RC4" on kuitenkin RSA Securityn tavaramerkki . Tavaramerkin omistajan mahdollisten vaatimusten välttämiseksi salausta kutsutaan joskus nimellä "ARCFOUR" tai "ARC4", viitaten englannin kieleen. väitetty RC4 on  "oletettu" RC4 (koska RSA Security ei ole virallisesti julkaissut algoritmia).  

RC4-salausalgoritmia käytetään joissakin yleisesti käytetyissä salausstandardeissa ja protokollissa (esimerkiksi WEP , WPA , SSL ja TLS ).

RC4:stä tuli suosittu seuraavien ansiosta:

Yhdysvalloissa suositeltu avaimen pituus kotikäyttöön on 128 bittiä. SPA:n ( s oftware publishers a ssociation )  ja Yhdysvaltain hallituksen välinen sopimus salli RC4-salausten viennin avaimenpituudeltaan jopa 40 bittiä. Amerikkalaisten yritysten ulkomaiset sivuliikkeet saavat käyttää 56-bittisiä avaimia [4] .

Algoritmin kuvaus

Virtasalausalgoritmin ydin koostuu funktiosta - näennäissatunnaisten bittien generaattorista ( gamma ), joka tuottaa avainbittien virran (avainvirta, gamma, näennäissatunnaisten bittien sarja).

salausalgoritmi.

  1. Funktio luo bittisekvenssin ( ).
  2. Bittijono ketjutetaan sitten selkeän tekstin ( ) kanssa modulo two -summausoperaation (xor) avulla . Tuloksena on salateksti ( ):

.

salauksen purkualgoritmi.

  1. Avaimen bittivirta (avainvirta) luodaan uudelleen (generoidaan uudelleen) ( ).
  2. Avaimen bittivirta lisätään salatekstiin ( ) " xor " -operaatiolla . Xor - toiminnon ominaisuuksista johtuen tulosteena on alkuperäinen (salaamaton) teksti ( ):

RC4 on itse asiassa algoritmien luokka, jonka määrittelee lohkokoko (jäljempänä S-laatikko ). Parametri n on algoritmin sanan pituus ja määrittää S-laatikon pituuden . Yleensä n = 8, mutta analyysitarkoituksiin voit pienentää sitä. Turvallisuuden parantamiseksi sinun on kuitenkin lisättävä tätä arvoa. S-laatikon koon kasvattamisen algoritmissa ei ole ristiriitaa . Kun n kasvaa , oletetaan 16 bittiin asti, S-laatikon elementeistä tulee 65 536 ja vastaavasti alkuperäistä iteraatioaikaa pidennetään. Salausnopeus kuitenkin kasvaa [5] .

RC4:n sisäinen tila on esitetty matriisina, jonka koko on 2 n ja kaksi laskuria. Taulukko tunnetaan nimellä S-box , ja siihen viitataan nimellä S. Se sisältää aina sanan 2n mahdollisen merkityksen permutaation. Kaksi laskuria on merkitty ija j.

RC4-alustus koostuu kahdesta osasta:

  1. S-boxin alustus ;
  2. näennäissatunnainen sanan sukupolvi K.

S-boxin alustus

Algoritmi tunnetaan myös nimellä "avaimen ajoitusalgoritmi" tai "KSA". Tämä algoritmi käyttää käyttäjän toimittamaa avainta, joka on tallennettu hakemistoon Keyja jonka pituus on Ltavua. Alustus alkaa taulukon täyttämisellä S, minkä jälkeen tämä taulukko sekoitetaan avaimen määrittämillä permutaatioilla. Koska kohdalle suoritetaan vain yksi toiminto S, väitteen on oltava, että se Ssisältää aina samat arvot, jotka annettiin alkuperäisessä alustuksessa ( S[i] := i ).

minulle 0-255 _ _ _ _ S[i] := i endfor j := 0 minulle 0-255 _ _ _ _ j := ( j + S[i] + näppäin[ i mod L ] ) mod 256 // n = 8 ; 28 = 256 vaihtaa S[i] ja S[j] endfor

Pseudosatunnainen sanasukupolvi K

Tätä algoritmin osaa kutsutaan pseudosatunnaissekvenssigeneraattoriksi ( p seudor  andom generation a lgorithm , PRGA ) . RC4-avainvirran generaattori muuttaa tiedostoon tallennetut arvot . Yhdessä RC4-syklissä määritetään yksi n - bittinen sana avainvirrasta. Jatkossa avainsanaan lisätään modulo kaksi selkeää tekstiä, jonka käyttäjä haluaa salata, ja salateksti saadaan. SK

minä := 0 j := 0 sukupolven silmukan aikana : i := ( i + 1 ) mod 256 j := ( j + S[i] ) mod 256 vaihtaa S[i] ja S[j] t := ( S[i] + S[j] ) mod 256 K := S[t] luotu näennäissatunnainen sana K (jos n = 8 luodaan yksi tavu) endwhile

Turvallisuus

Toisin kuin nykyaikaiset salaukset (kuten eSTREAM ), RC4 ei käytä noncea ( englannin sanasta nonce - "luku, jota voidaan käyttää vain kerran" - numero, jota voidaan käyttää vain kerran) avaimen kanssa. Tämä tarkoittaa, että jos yhtä avainta käytetään ajan mittaan useiden virtojen salaamiseen, itse RC4:ää käyttävän salausjärjestelmän on yhdistettävä tilaisuus ja pitkän aikavälin avain tuottaakseen virtaavaimen RC4:lle. Yksi mahdollinen ratkaisu on luoda uusi avain RC4:lle käyttämällä pitkän aikavälin avaimen hash -funktiota ja nonce . Kuitenkin monet RC4:ää käyttävät sovellukset yksinkertaisesti yhdistävät avaimen ja nonce : n . Tämän ja RC4:ssä käytetyn heikon näppäinajoituksen vuoksi sovelluksesta voi tulla haavoittuva [6] [7] [8] . Siksi monet ohjelmistoyritykset, kuten Microsoft , ovat poistaneet sen käytöstä . Esimerkiksi Microsoftin .NET Frameworkista puuttuu RC4 :n toteutus .

Tässä tarkastellaan joitakin salaukseen kohdistuvia hyökkäyksiä ja suojautumismenetelmiä niitä vastaan.

Roosen tutkimus ja avaimen palautus permutaatiosta

Vuonna 1995 Andrew Roos havaitsi kokeellisesti, että avainvirran ensimmäinen tavu korreloi avaimen kolmen ensimmäisen tavun kanssa ja avaimen ajoitusalgoritmin jälkeiset muutamat ensimmäiset tavut ( eng  . KSA ) korreloivat jonkin lineaarisen yhdistelmän kanssa . avaintavuista [9] . Nämä harhat todistettiin vasta 2007, jolloin Paul, Rafi ja Maitrae osoittivat, että avain ja avainvirta korreloivat. Myös Paul ja Maitre osoittivat permutaation ja avaimen korrelaation. Jälkimmäisessä työssä käytetään myös avainpermutaatiokorrelaatiota ensimmäisen täydellisen avaimen palautusalgoritmin luomiseksi viimeisestä KSA:n jälkeisestä permutaatiosta ilman, että tehdään oletuksia avaimesta ja alustusvektorista ( IV , i nitial v ector ) . Tällä algoritmilla on jatkuva onnistumisen todennäköisyys ajan mittaan, mikä on raa'an voiman monimutkaisuuden neliöjuuri. Viime aikoina on tehty paljon työtä avaimen palauttamiseksi RC4:n sisäisestä tilasta.   

Fluhrerin, Mantinin ja Shamirin hyökkäys (FMS)

Vuonna 2001 Fluhrer, Mantin ja Shamir julkaisivat paperin RC4-avainaikataulun haavoittuvuudesta. He osoittivat, että avainvirran ensimmäiset tavut kaikkien mahdollisten avainten joukossa eivät ole satunnaisia. Näistä tavuista on mahdollista saada suurella todennäköisyydellä tietoa käytetystä salausavaimesta. Ja jos pitkäaikainen avain ja nonce yksinkertaisesti liimataan yhteen RC4-salausavaimen luomiseksi, niin tämä pitkäaikainen avain voidaan saada analysoimalla riittävän suuri määrä tällä avaimella salattuja viestejä [10] . Tätä haavoittuvuutta ja joitain siihen liittyviä vaikutuksia käytettiin WEP -salauksen katkaisemiseen langattomissa IEEE 802.11 -verkoissa . Tämä osoitti tarpeen vaihtaa WEP mahdollisimman pian , mikä johti uuden langattoman tietoturvastandardin, WPA :n, kehittämiseen .

Salausjärjestelmä voidaan tehdä immuuniksi tälle hyökkäykselle hylkäämällä avainvirran alku. Siten modifioitua algoritmia kutsutaan nimellä "RC4-drop[n]", jossa n on hylättävien tavujen määrä avainvirran alusta. On suositeltavaa käyttää n = 768, varovainen arvio on n = 3072[11] [12] .

Hyökkäys perustuu alustusvektorin heikkouteen . Kun tiedät ensimmäiset näennäissatunnaiset sanat ja syöttöavaimen tavut , käyttämällä näennäissatunnaisen sanan generointialgoritmin heikkoutta , voidaan saada syöttöavaimen tavu. Toistamalla vaiheet saadaan koko avain. Kun hyökkäät WEP :tä kohtaan, for on muoto (B; 255; N), jossa  - 3 - 8 ja mikä tahansa numero . Noin 60 N:n muunnelman määrittäminen vaatisi noin 4 miljoonan paketin sieppaamisen. [kymmenen]KmKeyKm + 1n = 8 IVBN

Klein Attack

Vuonna 2005 Andreas Klein esitteli RC4-salauksen analyysin, jossa hän huomautti vahvan korrelaation avaimen ja RC4-avainvirran välillä. Klein analysoi hyökkäykset ensimmäisellä kierroksella (samanlainen kuin PMS-hyökkäys), toisella kierroksella ja niiden mahdollisia parannuksia. Hän ehdotti myös joitain muutoksia algoritmiin salauksen vahvuuden parantamiseksi. Erityisesti hän väittää, että jos käännät syklin suunnan avainaikataulun algoritmissa, voit tehdä salauksesta kestävämmän FMS:n kaltaisia ​​hyökkäyksiä vastaan ​​[1] .

Kombinatorinen ongelma

Vuonna 2001 Adi Shamir ja Itzhak Mantin esittivät ensimmäisenä kombinatorisen ongelman, joka liittyy RC4-salauksen mahdollisten tulojen ja lähtöjen määrään. Jos kaikista mahdollisista salauksen sisäisen tilan 256 elementistä tunnetaan xelementtejä tilasta ( x ≤ 256), niin jos oletetaan, että loput alkiot ovat nollia, maksimimäärä elementtejä, jotka voidaan saada deterministisellä algoritmilla seuraavat 256 kierrosta on myös yhtä suuri kuin x. Vuonna 2004 Souradyuti Paul ja Bart Preneel vahvistivat  tämän oletuksen [ 13 ] . 

Attack of Vanhof and Pissens (2015)

Kesällä 2015 Mathy Vanhoef ja Frank Piessens Leuvenin yliopistosta Belgiasta osoittivat todellisen hyökkäyksen TLS-protokollaa vastaan , joka käyttää RC4:ää lähetettyjen tietojen salaamiseen [14] . Hakkeroinnin idea perustuu MITM -periaatteeseen . Upottamalla tiedonsiirtokanavaan hyökkääjä tuottaa suuren määrän pyyntöjä palvelimelle, pakottaen sen palauttamaan vastauksena evästeitä , jotka on salattu samalla avaimella. Noin 9x2 27 ~ 2 30 {plaintext, ciphertext} -parin ollessa käsillä hyökkääjä pystyi palauttamaan avaimen ja siten myös salatut evästeet Fluhrer- McGrewn ja ABSAB :n tilastollisten menetelmien perusteella 94 %:n todennäköisyydellä. Käytännössä käytetty aika oli noin 52 tuntia, kun ylempi arvio tarvittavasta ajasta esittelyhetkellä oli noin 72 tuntia [15] .

RC4 modit

Aikaisemmin harkittiin salatekstin ja avaimen ensimmäisten tavujen korrelaatioon perustuvia hyökkäyksiä. Tällaiset algoritmin heikkoudet voidaan ratkaista hylkäämällä salatekstin alkuosa [16] . On turvallista hylätä ensimmäiset 256, 512, 768 ja 1024 tavua. Salatekstin alun tutkimukset suoritettiin osoittamaan tiettyjen ensimmäisten tavujen epäluotettavuus, mikä voi johtaa siihen, että hyökkääjä saa salausavaimen. RC4:lle on ehdotettu useita muunnelmia, jotka suorittavat turvallisuuden parantamisen algoritmia käytettäessä: RC4A, VMPC , RC4+.

RC4A

Vuonna 2004 Souradyuti Paulin ja Bart Preneelin työ näki valon, joka ehdotti RC4A:n muutosta [17] .

RC4A:ssa käytetään kahta S-laatikkoa yhden sijasta, kuten RC4:ssä, merkitty S₁ja S₂. Niille käytetään j₁vastaavasti kahta laskuria j₂. Laskuria iRC4:n tapaan käytetään yksikkömuodossa koko algoritmille. Algoritmin suoritusperiaate pysyy samana, mutta siinä on useita eroja:

  1. S₁on parametri S₂.
  2. Yhdelle iteraatiolle, eli yhdelle indeksin lisäykselle i, luodaan kaksi tavua salatekstiä.

Algoritmi:

minä := 0 j₁ := 0 j₂ := 0 sukupolven silmukan aikana : minä := i + 1 j1 := ( jl + S1[i] ) mod 256 vaihda S₁[i] ja S1[j₁] I2 := ( S1[i] + S1[j1] ) mod 256 lähtö  := S₂[I₂] j2 = (j2 + S2[i]) mod 256 vaihda S₂[i] ja S₂[j2] I1 = (S2[i] + S2[j2]) mod 256 lähtö  := S₁[I1] endwhile

Tämän algoritmin salausnopeutta voidaan lisätä rinnakkaisuudella .

RC4+

Vuonna 2008 kehitettiin ja ehdotettiin RC4+ -muutosta. Kirjoittajat Subhamoy Maitra ja Goutam Paul muuttivat S-boxin (KSA+) alustusta käyttämällä 3-tason sekoitusta. Myös näennäissatunnainen sanagenerointialgoritmi (PRGA+) [18] muutettiin .

Algoritmi:

Kaikki aritmeettiset operaatiot suoritetaan modissa 256. Symbolit "<<" ja ">>" tarkoittavat bittisiirtymiä vasemmalle ja oikealle, vastaavasti. Symboli "⊕" tarkoittaa toimintoa " yksinomainen TAI " , kun generointisilmukka: minä := i + 1 a := S[i] j := j + a b := S[j] S[i] := b (vaihdettu S[i] ja S[j]) S[j] := a c := S[ i<<5 ⊕ j>>3 ] + S[ j<<5 ⊕ i>>3 ] lähtö ( S[a+b] + S[c⊕0xAA] ) ⊕ S[ j+b ] endwhile

Toteutus

Monet virtasalaukset perustuvat lineaarisiin palautesiirtorekistereihin ( LFSR ) .  Tämä mahdollistaa tehokkaan salauksen toteutuksen integroidun piirin muodossa (laitteistototeutus), mutta vaikeuttaa tällaisten salausten ohjelmistototeutusta. Koska RC4-salaus ei käytä LFSR:ää ja perustuu tavutoimintoihin, se on kätevää toteuttaa ohjelmistossa. Tyypillinen toteutus suorittaa 8-16 konekäskyä tekstitavua kohden , joten salauksen ohjelmistototeutuksen tulisi olla nopea [19] .

RC4:ää käyttävät kryptojärjestelmät ja protokollat

Sana "(muuttuja)" tarkoittaa, että RC4 on yksi useista salausalgoritmeista, joita järjestelmä voi käyttää.

Katso myös

Muistiinpanot

  1. ↑ 1 2 Klein A. Hyökkäykset RC4-virtasalaukseen  (määrittämätön)  // Suunnitelmat, koodit ja salaus. - 2008. - T. 48 , nro 3 . - S. 269-286 . - doi : 10.1007/s10623-008-9206-6 .
  2. ↑ Rivest UKK (downlink) . Haettu 15. lokakuuta 2009. Arkistoitu alkuperäisestä 15. heinäkuuta 2017. 
  3. ↑ Kiitos Bob Anderson . Cypherpunks- postituslista (9. syyskuuta 1994). Haettu 28. toukokuuta 2007.
  4. ↑ RSA Laboratories - 3.6.2 Mikä on RC2?
  5. ↑ Bruce Schneier. Sovellettu kryptografia. toinen painos. John Wiley & Sons. 1996
  6. ↑ http://www.networklife.net/images/wep-rc4/RC4.pdf
  7. ↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 16. lokakuuta 2013. Arkistoitu alkuperäisestä 16. marraskuuta 2012. 
  8. ↑ https://uwspace.uwaterloo.ca/bitstream/10012/1141/1/memckagu2005.pdf
  9. ↑ Heikot näppäimet RC4:ssä (downlink) . Haettu 7. marraskuuta 2012. Arkistoitu alkuperäisestä 18. kesäkuuta 2012. 
  10. ↑ 1 2 Scott R. Fluhrer, Itsik Mantin, Adi Shamir. RC4:n  (neopr.) avainaikataulutusalgoritmin heikkouksia  // Tietojenkäsittelytieteen luentomuistiinpanot. - 2001. - T. 2259 . - S. 1-24 . - doi : 10.1007/3-540-45537-X_1 . Arkistoitu alkuperäisestä 7. syyskuuta 2008.
  11. ↑ I. Mironov. (Ei niin) RC4:n satunnaiset sekoitukset  (neopr.)  // Tietojenkäsittelytieteen luentomuistiinpanot. - 2002. - T. 2442 . - S. 304-319 . - doi : 10.1007/3-540-45708-9_20 .
  12. ↑ "RC4-drop(nbytes)" . " Vakio kryptografisten algoritmien nimeämis " -tietokanta.
  13. ↑ Souradyuti Paul, Bart Preneel. Uusi heikkous RC4 Keystream -generaattorissa ja lähestymistapa salauksen turvallisuuden parantamiseen  // Tietojenkäsittelytieteen luentomuistiinpanot  : lehti. - 2004. - Voi. 3017 . - s. 245-259 . - doi : 10.1007/b98177 .
  14. ↑ RC4 NOMOORE
  15. ↑ Hakkerit esittelivät käytännöllisen menetelmän RC4:n hakkerointiin
  16. ↑ Ilja Mironov (2002-06-01), (Ei niin) RC4:n satunnaiset sekoitukset , Salaustekniikan edistysaskel - CRYPTO 2002 , voi. 2442, Tietojenkäsittelytieteen luentomuistiinpanot, Springer-Verlag, s. 304–319, Cryptology ePrint -arkisto: Raportti 2002/067, ISBN 3-540-44050-X , doi : 10.1007/3-540-45708-9_20 
  17. ↑ Souradyuti Paul & Bart Preneel (2004), Uusi heikkous RC4-avainvirtageneraattorissa ja lähestymistapa salauksen turvallisuuden parantamiseen , Fast Software Encryption, FSE 2004 , voi. 3017, Lecture Notes in Computer Science, Springer-Verlag, s. 245–259 , ISBN 3-540-22171-9 _ _ 
  18. ↑ Subhamoy Maitra & Goutam Paul (2008-09-19), RC4:n analyysi ja ehdotus lisätasoiksi paremman suojausmarginaalin parantamiseksi , Progress in Cryptology - INDOCRYPT 2008 , voi. 5365, Lecture Notes in Computer Science, Springer-Verlag, s. 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 Mikä on RC4?
  20. ↑ Vastaukset arkistoitu 24. maaliskuuta 2010 Wayback Machinessa Opera mini -selaimen käyttäjien kysymyksiin .
  21. ↑ RFC 4757 . Microsoft Windowsin käyttämät RC4- HMAC kerberos -salaustyypit .
  22. ↑ PDF- ja PDF/A-ohjelmisto | PDF Tools AG | Premium PDF -tekniikka Arkistoitu 3. marraskuuta 2005.
  23. ↑ Skypen salausmenettely osittain paljastettu . www.h-online.com. Haettu 8. heinäkuuta 2010. Arkistoitu alkuperäisestä 6. marraskuuta 2012.

Linkit

 Symmetriset salausjärjestelmät
Suoratoista salauksia
Feistelin verkko
SP verkko
muu