4. diel - Pod pokrievkou šifrovacieho algoritmu RC4

V minulej lekcii, Ukážka jednoduchej šifrace textu Caesarovho šifra , sme si ukázali Caesarovu šifru.

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 roku 1994 došlo k vyzradeniu 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 pole, typicky s veľkosťou 256 bajtov. Tomuto poľu 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 sa rovná hodnote prvku).
2. KSA fáza: Toto pole (S-box) preženieme spomínaným KSáčkom, ktoré nám podľa užívateľom zadaného kľúča prevedie prehádzanie prvkov v poli a pridá bajty z kľúča. Ide vlastne o permutáciu, ktorá prebehne podľa bajtov kľúča 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) poľa. Kľúč máva väčšinou dĺžku v rozmedzí 40 a 128 bitov a pri permutácii 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ódovalo, 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ť mnoho 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 spomínanie 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ímacia strana správny kľúč, bude mať aj rovnaký keystream ako strana vysielacia).

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ľmi 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 je možné vykonať recovery kľúča. U wifi sa vykonáva zachytenie pakiet s tzv. inicializačnými vektormi. Samozrejme sa musí zachytiť pomerne veľké množstvo pakiet a teda musí byť pomerne veľká prevádzka na sieti, avšak nie je to nemožné.

Použitie

Jednoduchosť a rýchlosť operovania RC4 ho urobilo najpoužívanejšou 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 používajúci funkciu 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 š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 na tento účel nevhodný a tým vzniká priestor na diskusiu, ako by to šikovní kodéri v Jave riešili. Ď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áte a fci zvyknutý, tak ju pokojne používam ďalej. Dosť bolo rečou, ideme prelúsknuť kód:

Najskôr si premyslíme, čo budeme potrebovať. Bude tým trieda s jedným východiskovým konštruktorom, ktorá vždy inicializuje kľúč pre prípad, že by používateľ žiadny nezadal. Ďalej to budú 2 metódy, ktoré vychádzajú z podstaty RC4, teda ksa a prga. Ďalej potom jedna metóda, ktorá vymámi z uží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äčšou premennou je S-box s iba 256 bajtmi, preto 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 deklarované metódy triedy (vrátane konštruktora):

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ľúč o veľkosti 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 popí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 popísal, len tu doplním, že vypisujeme prehľadne pod seba zadaný text, keystream, šifrovaný text a dešifrovaný text po dvadsiatich znakoch. Musíme teda použiť ukladanie do medzipamäte, preto tie 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.

V ďalšej lekcii, Ukážka jednoduchej šifrace textu Vigenerova šifra , si ukážeme Vigenerovú šifru.

 

Mal si s čímkoľvek problém? Stiahni si vzorovú aplikáciu nižšie a porovnaj ju so svojím projektom, chybu tak ľahko nájdeš.