RC4

De Viquipèdia
Dreceres ràpides: navegació, cerca
Diagrama de l'algorisme RC4.

Entre la criptografia RC4 o ARC4 és el sistema de xifratge de flux Stream cipher més utilitzat i s'usa en alguns dels protocols més populars com Transport Layer Security (TLS/SSL) (per protegir el tràfic d'Internet) i Wired Equivalent Privacy (WEP) (per afegir seguretat a les xarxes sense fils). RC4 va ser exclòs de seguida dels estàndards d'alta seguretat pels criptògrafs i algunes maneres d'utilitzar l'algorisme de criptografia RC4 l'han portat a ser un sistema de criptografia molt insegur, incloent el seu ús WEP. No està recomanat el seu ús en els nous sistemes, però, alguns sistemes basats en RC4 són prou segurs per a un ús comú.

Història[modifica | modifica el codi]

L'algorisme de criptografia RC4 va ser dissenyat per Ron Rivest de la RSA Security l'any 1987; el seu nom complet és Rivest Cipher 4, tenint l'acrònim RC un significat alternatiu al de Ron s Code utilitzat per als algoritmes de xifrat RC2, RC5 i RC6.

Inicialment l'algorisme era un secret registrat, però al setembre de 1994 una descripció de l'algorisme va ser postejada anònimament en una llista de correu de cypherpunks. De seguida va passar al grup de correu sci.crypt i d'aquí va ser publicat en nombrosos llocs d'Internet. A causa del coneixement de l'algorisme, aquest va deixar de ser un secret registrat. No obstant això RC4 encara és una marca registrada. Actualment la implementació no oficial de RC4 és legal, però no pot ser utilitzada amb el nom de RC4. Per aquest motiu, i a fi d'evitar problemes legals arran de la marca registrada, sovint podem veure-ho nomenat com ARCFOUR, ARC4 o Alleged-RC4. RSA Security mai ha alliberat l'algoritme de la seva RC4.

RC4 és part dels protocols de xifrat més comuns com WEP, WPA per a targetes wireless i TLS. Entre els factors principals que han ajudat a que RC4 estigui en un rang tan ampli d'aplicacions són la seva increïble velocitat i simplicitat. La implementació tant en programari com en maquinari és molt senzilla de desenvolupar i són molt pocs els recursos necessaris per obtenir un rendiment eficient de ARC4.

Descripció[modifica | modifica el codi]

RC4 és un un algorisme sorprenentment simple. Aquest consisteix en 2 algorismes: 1-Key Scheduling Algorithm (KSA) i 2 - Pseudo-Random Generation Algorithm (PRGA). Tots dos d'aquests algorismes usen 8-by-8 S-box, el qual és només un array de 256 nombres en el qual ambdós són únics quant a rang i el seu valor va des de 0 fins 255. Tots els nombres de 0 a 255 existeixen en cas de fallida, però estan només barrejats de diferents maneres, el KSA s'encarrega de realitzar la primera barreja en el S-Box, basat en el valor de la llavor donada dins d'ell, i aquesta "llavor" pot ser de 256 bits de llarg.

Primer, el S-box array és omplert amb valors seqüencials des 0-255. Aquest array serà cridat simplement S. Llavors, l'altre array de 256-bits és omplert amb el valor de la "llavor", repetint com sigui necessari fins que tot l'array és omplert. Aquest array serà cridat K, llavors la matriu S és barrejat usant el següent pseudocodi.

 j = 0;
 for i = 0 to 255
{
    j = (j+S [i]+K [i]) mod 256;
    intercanvia S [i] and S [j];
}


Quan això és fet, la S-box és intercanviada basant-se en el valor de la "llavor". Aquesta és la "Key" programada per al algorisme, alguna cosa senzilla.

Ara quan el keystream data és necessitat, el Pseudo-Random Generation Algorithm (PRGA) és usat. Aquest algorisme té 2 comptadors, l'i i la j, en el qual ambdós són inicialitzats a 0 per començar. Després d'això, cada bit de keystream data és usat en el següent Pseudo-Code:

i = (i+1) mod 256;
j = (j+S [i]) mod 256;
intercanvia S [i] and S [j];
t = (S [i]+S [j] mod 256;
Exposar valor de S [t];

El valor exposat del byte de S [t] és el primer byte del keystream. Aquest algorisme és repetit per aconseguir bytes addicionals de keystream. RC4 és simplement suficient, que pot ser fàcilment memoritzat i implementat en l'aire, i pot arribar a ser una mica "més" segur si és usat apropiadament, en fi, hi ha alguns problemes amb la forma que RC4 és usat amb el xifrat WEP en Wi-Fi.

Una possible implementació en C:

unsigned char S [256];
unsigned int i, j;
 
void swap (unsigned char * s, unsigned int i, unsigned int j){
    unsigned char temp = s [i];
    s [i] = s [j];
    s [j] = temp;
}
 
/* KSA */
void rc4_init (unsigned char * key, unsigned int key_length){
    for (i = 0; i <256; i++)
        S [i] = i;
 
    for (i = j = 0; i <256; i++){
        j = (j+key [i% key_length]+S [i]) & 255;
        swap (S, i, j);
   }
 
    i = j = 0;
}
 
/* PRGA */
unsigned char rc4_output (){
    i = (i+1) & 255;
    j = (j+S [i]) & 255;
 
    swap (S, i, j);
 
    return S [(S [i]+S [j]) & 255];
}
 
#Include <stdio.h>
#Include <string.h>
#Include <stdlib.h>
 
#Define ARRAY_SIZE (a) (sizeof (a)/sizeof (a [0]))
 
int main (){
    unsigned char * test_vectors [] [2] =
   {
       {"Key", "Plaintext"},
       {"Wiki", "pedia"},
       {"Secret", "Attack at dawn"}
   };
 
    int x;
    for (x = 0; x <ARRAY_SIZE (test_vectors); x++){
        int i;
        rc4_init (test_vectors [x] [0], strlen ((char *) test_vectors [x] [0]));
 
        for (i = 0; i <strlen ((char *) test_vectors [x] [1]), i++)
            printf ("% 02X", test_vectors [x] [1] [i]^rc4_output ());
        printf ("\n");
   }
    getch ();
    return 0;
}

Test vectors[modifica | modifica el codi]

Aquesta prova no és oficial, però resulta adequada per a algú provant el seu propi programa RC4. Les claus i el text en clar estan en ASCII, el text xifrat està en hexadecimal


Clau Keystream Missatge Text xifrat
 Key 
 eb9f7781b734ca72a719 ... 
 Plaintext 
 BBF316E8D940AF0AD3 
 Wiki 
 6044db6d41b7 ... 
 pedia 
 1021BF0420 
 Secret 
 04d46b053ca87b59 ... 
 Attack at dawn 
 45A01F645FC35B383552544B9BF5 

Nota[modifica | modifica el codi]