RC4

Archiu:RC4.svg

RC4

Archiu:RC4.svg

Diagrama de l'algoritme RC4.

Dins de la criptografia RC4 o ARC4 és el sistema de sifrat de fluix Stream cipher més utilisat i s'usa en alguns dels protocols més populars com Transport Layer Security (TLS/SSL) (per a protegir el tràfic d'Internet) i Wired Equivalent Privacy (WEP) (per a afegir seguritat en les rets inalàmbriques). RC4 va ser exclós en seguida dels estàndarts d'alta seguritat pels criptógrafos i alguns modos d'usar l'algoritme de criptografia RC4 ho han dut a ser un sistema de criptografia molt insegur, incloent el seu us WEP. No està recomanada la seua aplicació en proyectes nous; no obstant, alguns sistemes basats en RC4 són lo suficientment segurs per a un us comú.

Història

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

Inicialment l'algoritme era un secret registrat, pero en setembre de 1994 una descripció de l'algoritme va ser distribuïda anónimamente en una llista de correu de Cypherpunks. En seguida va passar al grup de notícies sci.crypt i d'allí a numerosos llocs d'Internet, deixant aixina de ser secret; no obstant RC4 encara és una marca registrada. Actualment l'implementació no oficial de RC4 és llegal, pero no pot utilisar-se baix el nom de RC4. Per este motiu, i en la finalitat d'evitar problemes llegals a raïl de la marca registrada, a sovint podem vore-ho nomenat ARCFOUR, ARC4 (Alleged-RC4). RSA Security mai ha lliberat de manera oficial l'algoritme del seu RC4.

RC4 és part dels protocols de sifrat més comuns com WEP, TLS i WPA per a targetes inalàmbriques. Els factors principals per a l'èxit de RC4 i la seua aplicació en tan ampli ranc d'aplicacions han segut la seua increible velocitat i la seua simplicitat. L'implementació eficient en software i en hardware varen ser molt simples de desenrollar.

Descripció

RC4 és un protocol sorprenentment simple que ampra 2 algoritmes: 1-Key Scheduling Algorithm (KSA) i 2- Pseudo-Random Generation Algorithm (PRGA), cada u dels quals usa un estat intern secret: 8-per-8 S-box, que és un apany en els 256 possibles bytes permutats i dos índexs de 8 bits ("i" i "j" en el còdic següent). El KSA genera la permutació en el S-Box basant-se en una clau de llongitut variable ("keylength", entre 40 i 2048 bits).

Primer s'ompli el S-box (cridat "S" a continuació) en els valors de 0 a 255 en seqüència (permutació identitat); despuix li'l processa 256 voltes tal com ho fa el PRGA principal, excepto que, ademés, es mesclen bytes presos de la clau ("K"), usant el següent pseudocódigo.

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

Una volta que això és fet, la S-box és intercanviada basant-se en el valor de la "llavor". Eixa és la "Key" programada per a l'algoritme, alguna cosa senzill.

Ara quan es necessita el keystream data, s'usa el Pseudo-Random Generation Algorithm (PRGA). Este algoritme té 2 contadors, l'i i la j, en el qual abdós són inicializados en 0 per a començar. Despuix d'això, cada bit de keystream data és usat en el següent pseudocódigo:

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

El valor expost del byte de S[t] és el primer byte del keystream, repetint-se l'algoritme descrit per a conseguir bytes adicionals de keystream.

RC4 és lo suficientment senzill com per a ser almagasenat i implementat al vol, encara que la robustea de dit algoritme depén, en gran mida, de l'implementació i utilisació realisada, existint greus problemes coneguts en l'implementació del sistema de sifrat WEP, dissenyat per a oferir confidencialitat en rets Wireless.

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>

#definix 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("
");
    }
    getch(); 
    return 0;
}

Test vectors

Esta prova no és oficial, pero resulta adequada per a algú provant el seu propi programa RC4. Les claus i el text en clar estan en ASCII, el text sifrat està en hexadecimal. El Keystream és el valor obtingut consecutivament per la funció RC4Output (passat a hexadecimal, per a ser llegible).

Clau	Keystream	Mensage	Text sifrat
Key	eb9f7781b734ca72a7	Plaintext	BBF316E8D940AF0AD3
Wiki	6044db6d41	pedia	1021BF0420
Secret	04d46b053ca87b594172302aec9b	Attack at dawn	45A01F645FC35B383552544B9BF5
Cervantes	287fdbeef86ccd89b1i1d7acd118i2664927f97d6f9aafc2	En un lloc de la taca	6D11FB9B964CA1FCD680A58CB57DC20A2807941C01F9C7A3

Referències

• Applied Cryptography, segona edició, Bruce Schneier, pàgina 397 i següents.