Lekce 4 - Pod pokličkou šifrovacího algoritmu RC4

V minulé lekci, Ukázka jednoduché šifrace textu Caesarova šifra, jsme si ukázali Caesarovou šifru.

Proudovou šifru navrhl v roce 1987 Ron Rivest, zdrojový kód algoritmu byl zpočátku obchodním tajemstvím a RC4 podléhalo ochranné známce, avšak v září roku 1994 došlo k vyzrazení kódu. Ochranná známka se obešla vznikem alternativních názvů například ARC4 nebo ARCFOUR.

Princip RC4

Šifra má tři základní komponenty:

1. Tzv. S-box
2. Key scheduling algorithm - často se můžeme setkat se zkráceným označením KSA
3. Pseudo-random generation algorithm (PRGA).

Postup algoritmu

1. Nejprve vytvoříme pole, typicky o velikosti 256 bajtů. Tomuto poli se často říká S-box. Zpočátku ho inicializujeme smyčkou for tak, že se v něm budou nacházet vzestupně seřazená celá čísla v intervalu <0 ; 255> (hodnota indexu prvku pole bude rovna hodnotě prvku).
2. KSA fáze: Toto pole (S-box) proženeme zmíněným KSáčkem, které nám dle uživatelem zadaného klíče provede proházení prvků v poli a přidá bajty z klíče. Jde vlastně o permutaci, která proběhne dle bajtů klíče a jestli jsem správně vydedukoval a z pokusů vypozoroval, tak dle hodnot v klíči může dojít k přetečení hodnot prvku(ů) pole. Klíč mívá většinou délku v rozmezí 40 a 128 bitů a při permutaci je opakován stále dokola od začátku do konce S-boxu. Na konci kódu KSA najdeme ještě prohození (swap) hodnot prvků pole SBox[i] a SBox[j].
3. PRGA fáze: S-box, který nám KSA zakódovalo, předáme PRGA, které nám vygeneruje tzv. keystream. Úkolem PRGA je vytvořit takový keystream, který bude mít velkou periodu opakování a měl by mít mnoho kombinací jako skutečný náhodný číslicový generátor. Když srovnám KSA A PRGA, vidím, že jejich kódy jsou si velmi podobné s tím rozdílem, že PRGA „míchá“ bez klíče a „míchá“ neustále, protože musí neustále generovat keystream. Naproti tomu KSA zamíchá dle klíče pouze jednou. Na konci kódu PRGA opět najdeme zmínění swap.

No a potom už je to velice jednoduché. Zakódování dat (textu) se provede tak, že provedeme logickou funkci XOR keystreamu a dat (textu). A dekódování je též velice jednoduché. Opět provedeme funkci XOR na zakódovaná data (text) a keystream (když bude mít přijímací strana správný klíč, bude mít i stejný keystream jako strana vysílací).

Výhody RC4

Jednoduchá softwarová implementace, nenáročná na systémové prostředky. Šifra je také rychlá. Ve svých programech se chystám využít RC4 ke kódování hesel, kde nepotřebuji nutně hodně silnou šifru – např.: heslo pro přístup na FTP server, kde nejsou žádná citlivá data.

Nevýhody RC4

V dnešní době již není tak bezpečná, protože při zachycení většího množství keystreamu lze provést recovery klíče. U wifi se provádí zachycení paket s tzv. inicializačními vektory. Samozřejmě se musí zachytit poměrně velké množství paket a tudíž musí být poměrně velký provoz na síti, avšak není to nemožné.

Užití

Jednoduchost a rychlost operování RC4 ho udělalo nejpoužívanější proudovou šifrou. Nalezneme ho například v SSL a tím tedy například v zabezpečení mezi klientem a webovým serverem - naše známe HTTPS. Dříve se používalo hlavně v zabezpečení wifi sítí tzv. WEP (Wired equivalent privacy), jako že by mělo být stejné zabezpečení jako po drátě. a známé WPA.

Simulátor

Šifra mne velice zaujala a chtěl jsem ji pochopit a umožnit, abyste ji mohli dobře pochopit i vy. Proto jsem vytvořil simulátor. Je to hybrid užívající funkcí C a objektu C++, protože jsem se na itnetwork.cz naučil, že se mám snažit programovat objektově. Udělal jsem program do jedné třídy, i když si plně uvědomuji, že by šel vložit jen do fce main. Původně jsem chtěl program tvořit jako GUI v Javě, avšak nenašel jsem vhodný datový typ pro S-Box a postrádal jsem v Javě jedno-bajtový nezáporný datový typ. Nejblíže je typ byte, ale ten nabírá hodnot -128 až +128 a protože v S-boxu musí být hodnoty 0-255, je pro tento účel nevhodný a tím vzniká prostor pro diskusi, jak by to šikovní kodéři v Javě řešili. Dále vím, že bych měl užít cout a cin, ale protože fce printf se používá i v Javě, tak jsem na deskriptor formátu a fci zvyklý, tak jí klidně používám dál. Dost bylo řečí, jdeme přelousknout kód:

Nejdříve si promysleme, co budeme potřebovat. Bude tím třída s jedním výchozím konstruktorem, která vždy inicializuje klíč pro případ, že by uživatel žádný nezadal. Dále to budou 2 metody, které vychází z podstaty RC4, tedy ksa a prga. Dále pak jedna metoda, která vymámí z uživatele klíč. Privátní proměnné budou dvě políčka - jedno na klíč zadaný uživatelem a jedno na S-box. Dále jedna pomocná proměnná, která nám bude evidovat délku klíče. Největší proměnnou je S-box s pouhými 256 bajty, tudíž se domnívám, že bohatě vystačíme se zásobníkem a nic tedy v hromadě alokovat nebudu. Takže by to mohlo vypadat takhle:

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

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

Nyní implementujeme deklarované metody třídy (včetně 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");
        }
}

Metoda zadejKlic() by měla eliminovat neposlušného uživatele, který buď žádný klíč nezadá, nebo chce zadat příliš dlouhý klíč, v našem simulátoru je povolen klíč o velikosti 1-5 bajtů.

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];
        }
}

Metodu ksa jsem už v úvodu detailně popsal...

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");
   }
}

Metodu prga jsem již v úvodu také detailně popsal, jen zde doplním, že vypisujeme přehledně pod sebe zadaný text, keystream, šifrovaný text a dešifrovaný text po dvaceti znacích. Musíme tedy použít ukládání do mezipaměti, proto ta tři políčka buffer. Ještě zdůrazním, že keystream a šifrovaný text má být dle RC4 v šestnáctkové soustavě, jsou to samozřejmě hodnoty v intervalu 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 nakonec to všechno obsloužíme v hlavní funkci:

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

Přikládám celý zdrojový kód ke stažení a také zkompilovaný program.

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

V další lekci, Ukázka jednoduché šifrace textu Vigenerova šifra, si ukážeme Vigenerovou šifru.

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.