RC4

Diagrama del algoritmo RC4.

Dentro de la criptografía RC4 o ARC4 es el sistema de cifrado de flujo Stream cipher más utilizado y se usa en algunos de los protocolos más populares como Transport Layer Security (TLS/SSL) (para proteger el tráfico de Internet) y Wired Equivalent Privacy (WEP) (para añadir seguridad en las redes inalámbricas). RC4 fue excluido enseguida de los estándares de alta seguridad por los criptógrafos y algunos modos de usar el algoritmo de criptografía RC4 lo han llevado a ser un sistema de criptografía muy inseguro, incluyendo su uso WEP. No está recomendada su aplicación en proyectos nuevos; sin embargo, algunos sistemas basados en RC4 son lo suficientemente seguros para un uso común.

Historia

El algoritmo de criptografía RC4 fue diseñado por Ronald Rivest de la RSA Security en el año 1987; su nombre completo es Rivest Cipher 4, teniendo el acrónimo RC un significado alternativo al de Ron's Code utilizado para los algoritmos de cifrado RC2, RC5 y RC6.

Inicialmente el algoritmo era un secreto registrado, pero en septiembre de 1994 una descripción del algoritmo fue distribuida anónimamente en una lista de correo de Cypherpunks.​ Enseguida pasó al grupo de noticias sci.crypt y de allí a numerosos sitios de Internet, dejando así de ser secreto; sin embargo RC4 aún es una marca registrada.​ Actualmente la implementación no oficial de RC4 es legal, pero no puede utilizarse bajo el nombre de RC4. Por este motivo, y con el fin de evitar problemas legales a raíz de la marca registrada, a menudo podemos verlo nombrado ARCFOUR, ARC4 (Alleged-RC4). RSA Security nunca ha liberado de manera oficial el algoritmo de su RC4.

RC4 es parte de los protocolos de cifrado más comunes como WEP, TLS y WPA para tarjetas inalámbricas. Los factores principales para el éxito de RC4 y su aplicación en tan amplio rango de aplicaciones han sido su increíble velocidad y su simplicidad. La implementación eficiente en software y en hardware fueron muy simples de desarrollar.

Descripción

RC4 es un protocolo sorprendentemente simple que emplea 2 algoritmos: 1-Key Scheduling Algorithm (KSA) y 2- Pseudo-Random Generation Algorithm (PRGA), cada uno de los cuales usa un estado interno secreto: 8-por-8 S-box, que es un arreglo con los 256 posibles bytes permutados y dos índices de 8 bits ("i" y "j" en el código siguiente). El KSA genera la permutación en el S-Box basándose en una clave de longitud variable ("keylength", entre 40 y 2048 bits).

Primero se llena el S-box (llamado "S" a continuación) con los valores de 0 a 255 en secuencia (permutación identidad); después se lo procesa 256 veces tal como lo hace el PRGA principal, excepto que, además, se mezclan bytes tomados de la clave ("K"), usando el siguiente 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;
    intercambia S[i] and S[j];
}

Una vez que eso es hecho, la S-box es intercambiada basándose en el valor de la "semilla". Esa es la "Key" programada para el algoritmo, algo sencillo.

Ahora cuando se necesita el keystream data, se usa el Pseudo-Random Generation Algorithm (PRGA). Este algoritmo tiene 2 contadores, el i y la j, en el cual ambos son inicializados en 0 para comenzar. Después de eso, cada bit de keystream data es usado en el siguiente pseudocódigo:

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

El valor expuesto del byte de S[t] es el primer byte del keystream, repitiéndose el algoritmo descrito para conseguir bytes adicionales de keystream.

RC4 es lo suficientemente sencillo como para ser almacenado e implementado al vuelo, aunque la robustez de dicho algoritmo depende, en gran medida, de la implementación y utilización realizada, existiendo graves problemas conocidos en la implementación del sistema de cifrado WEP, diseñado para ofrecer confidencialidad en redes Wireless.

Una posible implementación 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 y;
        rc4_init(test_vectors[x][0], strlen((char*)test_vectors[x][0]));

        for (y = 0; y < strlen((char*)test_vectors[x][1]); y++)
            printf("%02X", test_vectors[x][1][y] ^ rc4_output());
        printf("\n");
    }
    getch(); 
    return 0;
}

Test vectors

Esta prueba no es oficial, pero resulta adecuada para alguien probando su propio programa RC4. Las llaves y el texto en claro están en ASCII, el texto cifrado está en hexadecimal. El Keystream es el valor obtenido consecutivamente por la función RC4Output (pasado a hexadecimal, para ser legible).

Clave	Keystream	Mensaje	Texto cifrado
Key	eb9f7781b734ca72a7	Plaintext	BBF316E8D940AF0AD3
Wiki	6044db6d41	pedia	1021BF0420
Secret	04d46b053ca87b594172302aec9b	Attack at dawn	45A01F645FC35B383552544B9BF5
Cervantes	287fdbeef86ccd89b1e1d7acd118e2664927f97d6f9aafc2	En un lugar de la mancha	6D11FB9B964CA1FCD680A58CB57DC20A2807941C01F9C7A3

Referencias

• Applied Cryptography, segunda edición, Bruce Schneier, página 397 y siguientes.

• Datos: Q846955