Pod pokrievkou šifrovacieho algoritmu RC4

Prúdovú šifru navrhol v roku 1987 Ron Rivest, zdrojový kód algoritmu bol spočiatku obchodným tajomstvom a RC4 podliehalo ochrannej známke, avšak v septembri 1994 viedli k porušeniu kódu. Ochranná známka sa obišla vznikom alternatívnych názvov napríklad ARC4 alebo ARCFOUR.

Princíp RC4

Šifra má tri základné komponenty:

1. Tzv. S-box
2. Key scheduling algorithm - často sa môžeme stretnúť so skráteným označením KSA
3. Pseudo-random generation algorithm (PRGA).

Postup algoritmu

1. Najprv vytvoríme polia, typicky s veľkosťou 256 bajtov. Tomuto poli sa často hovorí S-box. Spočiatku ho inicializujeme slučkou for tak, že sa v ňom budú nachádzať vzostupne zoradená celé čísla v intervale <0; 255> (hodnota indexu prvku poľa bude rovnať hodnote prvku).
2. KSA fáza: Toto pole (S-box) preženie spomenutým KSáčkem, ktoré nám podľa užívateľom zadaného kľúča vykoná proházení prvkov v poli a pridá bajty z kľúča. Ide vlastne o permutáciu, ktorá prebehne podľa bajtov kľúče a či som správne vydedukoval az pokusov vypozoroval, tak podľa hodnôt v kľúči môže dôjsť k pretečeniu hodnôt prvku (ov) pole. Kľúč máva väčšinou dĺžku v rozmedzí 40 a 128 bitov a pri permutáciu je opakovaný stále dookola od začiatku do konca S-boxu. Na konci kódu KSA nájdeme ešte prehodenie (swap) hodnôt prvkov poľa SBOX [i] a SBOX [j].
3. PRGA fáza: S-box, ktorý nám KSA zakódoval, odovzdáme PRGA, ktoré nám vygeneruje tzv. Keystream. Úlohou PRGA je vytvoriť taký keystream, ktorý bude mať veľkú periódu opakovania a mal by mať veľa kombinácií ako skutočný náhodný číslicový generátor. Keď porovnám KSA A PRGA, vidím, že ich kódy sú si veľmi podobné s tým rozdielom, že PRGA "mieša" bez kľúča a "mieša" neustále, pretože musí neustále generovať keystream. Naproti tomu KSA zamieša podľa kľúča iba raz. Na konci kódu PRGA opäť nájdeme spomenutí swap.

No a potom už je to veľmi jednoduché. Zakódovanie dát (textu) sa vykoná tak, že vykonáme logickú funkciu XOR keystreamu a dát (textu). A dekódovanie je tiež veľmi jednoduché. Opäť vykonáme funkciu XOR na zakódované dáta (text) a keystream (keď bude mať prijímacie strana správny kľúč, bude mať aj rovnaký keystream ako strana vysielacej).

Výhody RC4

Jednoduchá softvérová implementácia, nenáročná na systémové prostriedky. Šifra je tiež rýchla. Vo svojich programoch sa chystám využiť RC4 na kódovanie hesiel, kde nepotrebujem nutne veľa silnú šifru - napr .: heslo pre prístup na FTP server, kde nie sú žiadne citlivé dáta.

Nevýhody RC4

V dnešnej dobe už nie je tak bezpečná, pretože pri zachytení väčšieho množstva keystreamu možno vykonať recovery kľúča. U wifi sa vykonáva zachytenie paket s tzv. Inicializácie vektory. Samozrejme sa musí zachytiť pomerne veľké množstvo paket a teda musí byť pomerne veľký prevádzku na sieti, avšak nie je to nemožné.

Použitia

Jednoduchosť a rýchlosť operovania RC4 ho urobilo najpoužívanejšie prúdovou šifrou. Nájdeme ho napríklad v SSL a tým teda napríklad v zabezpečení medzi klientom a webovým serverom - naše poznáme HTTPS. Predtým sa používalo hlavne v zabezpečení wifi sietí tzv. WEP (Wired equivalent privacy), ako že by malo byť rovnaké zabezpečenie ako po drôte. a známe WPA.

Simulátor

Šifra ma veľmi zaujala a chcel som ju pochopiť a umožniť, aby ste ju mohli dobre pochopiť aj vy. Preto som vytvoril simulátor. Je to hybrid užívajúci funkcií C a objektu C ++, pretože som sa na itnetwork.cz naučil, že sa mám snažiť programovať objektovo. Urobil som program do jednej triedy, aj keď si plne uvedomujem, že by išiel vložiť len do fce main. Pôvodne som chcel program tvoriť ako GUI v Jave, avšak nenašiel som vhodný dátový typ pre S-Box a postrádal som v Jave jedno-bajtové nezáporný dátový typ. Najbližšie je typ byte, ale ten naberá hodnôt -128 až +128 a pretože v S-boxe musia byť hodnoty 0-255, je pre tento účel nevhodný a tým vzniká priestor pre diskusiu, ako by to šikovní kodér v Jave riešenia. Ďalej viem, že by som mal užiť cout a cin, ale pretože fce printf sa používa aj v Jave, tak som na deskriptor formátu a FCI zvyknutý, tak jej pokojne používam ďalej. Dosť bolo rečí, ideme přelousknout kód:

Najskôr si premyslite, čo budeme potrebovať. Bude tým trieda s jedným predvoleným konstruktoru, ktorá vždy inicializuje kľúč pre prípad, že by užívateľ žiadny nezadal. Ďalej to budú 2 metódy, ktoré vychádza z podstaty RC4, teda ksa a prga. Ďalej potom jedna metóda, ktorá vymeÀte z používateľa kľúč. Privátne premenné budú dve políčka - jedno na kľúč zadaný užívateľom a jedno na S-box. Ďalej jedna pomocná premenná, ktorá nám bude evidovať dĺžku kľúča. Najväčší premennou je S-box s iba 256 bajty, teda sa domnievam, že bohato vystačíme so zásobníkom a nič teda v hromade alokovať nebudem. Takže by to mohlo vyzerať takto:

class RC4Simulator
{
public:
RC4Simulator();
void ksa();
void prga();
void zadejKlic();

private:
uchar key[5];
uchar SBox[256];  //index 0-255
ushort delka_klice;
};

Teraz implementujeme deklarovanej metódy triedy (vrátane konstruktoru):

RC4Simulator::RC4Simulator()
{
key[0]='K';
key[1]='e';
key[2]='y';
key[3]='\n';
key[4]='\n';
delka_klice=3;

        for (int i = 0; i < 256 ; i++)  //inicializace S-boxu
        {
        SBox[i]=i;
        if (i==0)printf("\nKonstruktor inicializuje SBox");
        if ((i%16)==0) printf(".");
        if (i==255) printf("OK\n");
        }
}

Metóda zadejKlic () by mala eliminovať neposlušného používateľa, ktorý buď žiadny kľúč nezadá, alebo chce zadať príliš dlhý kľúč, v našom simulátore je povolený kľúč s veľkosťou 1-5 bajtov.

void RC4Simulator::zadejKlic()  /*pozada uzivatele o zadani klice*/
{
ushort pocet = 0;
uchar input_key[] = {'a','b','c','d','e'};

printf("\nZadej klic a stiskni klavesu Enter, povoleno je 1-5 znaku: ");

while( ((input_key[pocet] = getchar()) != '\n') ) /*rutinka pro osefovani vstupu*/
{

pocet++;

        if (pocet > 5)
        {
        printf("\nZadal jsi moc dlouhou hodnotu, opakuj zadani.\n");
        while ( getchar()!= '\n' ) ;//printf("Vyprazdnuji buffer.\n");
        pocet = 0;
        }
}

        if (input_key[0]=='\n')
        {
        printf("\nNezadal jsi nic, bude pouzit vychozi klic: %s" ,key);
        }
        else
        {
        delka_klice = pocet;
        for(int a=0 ; a<=pocet ; a++)
        key[a]=input_key[a];
        }
}

Metódu ksa som už v úvode detailne opísal ...

void RC4Simulator::ksa()         /*fce ksa inicializuje S-box dle klice*/
{
   int i,j=0,temp;

   for (i=0; i < 256; ++i) {
      j = (j + SBox[i] + key[i % delka_klice]) % 256;
      temp = SBox[i];
      SBox[i] = SBox[j];
      SBox[j] = temp;
      if (i==0)printf("\nKsa is mixing SBox");
      if ((i%16)==0) printf(".");
      if (i==255) printf("OK\n");
   }
}

Metódu prga som už v úvode tiež detailne opísal, len tu doplním, že vypisujeme prehľadne pod seba zadaný text, keystream, šifrovaný text a dešifrovanom text po dvadsiatich znakoch. Musíme teda použiť caching, preto tá tri políčka buffer. Ešte zdôrazním, že keystream a šifrovaný text má byť podľa RC4 v šestnástkovej sústave, sú to samozrejme hodnoty v intervale 0-255.

void RC4Simulator::prga()        /*generovani keystreamu, buffering a vypis*/
{
   ushort i=0,j=0,x=0,temp;
   uchar znak;
   uchar buffer_znaky[20],buffer_keystream[20],buffer_encrypted[20];

   printf("\nFce PRGA nyni generuje keystream, zadavej text pro zakodovani, "
   "\npo 20-ti zadanych znacich se ti zobrazi keystream, zasifrovany text "
   "\na desifrovany text. Program ukoncis stiskem klavesy Enter nebo nuly.\n\n");

   while( (znak!='\r')&&( znak!='0'))
   {
        i = (i + 1) % 256;
        j = (j + SBox[i]) % 256;
        temp = SBox[i];
        SBox[i] = SBox[j];
        SBox[j] = temp;

        znak = getch();
        buffer_znaky[x]=znak;
        buffer_keystream[x]=SBox[(SBox[i] + SBox[j])%256];
        buffer_encrypted[x]= (buffer_keystream[x]^buffer_znaky[x]);
        x++;
        printf("%c  " , znak);

        if(x>=20)
        {
        printf("\n");
        for(int a=0 ; a<20 ; a++)
        printf("%02x " , buffer_keystream[a]);  /*keystream*/

        printf("\n");
        for(int a=0 ; a<20 ; a++)
        printf("%02X ",(buffer_keystream[a]^buffer_znaky[a]) );/*xor zakodovano*/

        printf("\n");
        for(int a=0 ; a<20 ; a++)
        printf("%c  ",( buffer_keystream[a]^buffer_encrypted[a]) );/*xor dekodovano*/

        printf("\n\n");
        x=0;
        }
   }

}

No a nakoniec to všetko obslúžime v hlavnej funkcii:

int main(int argc, char* argv[])
{
printf("*********************\n");
printf("****RC4 Simulator****\n");
printf("*********************\n");
RC4Simulator rc4simulator;
rc4simulator.zadejKlic();
rc4simulator.ksa();
rc4simulator.prga();
return 0;
}

Prikladám celý zdrojový kód na stiahnutie a tiež skompilovaný program.

Zdroje: vlastné empirické pokusy, wikipedia, informit.com, bradconte.com, Jadavpur univerzity (Kolkata-India) - department of computer science and enginnering.