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á recomendado su uso en los nuevos sistemas, 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 Ron 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 posteada anónimanente en una lista de correo de Cypherpunks. Enseguida pasó al grupo de correo sci.crypt y de ahí fue publicado en numerosos sitios de Internet. Debido al conocimiento del algoritmo, éste dejó de ser un secreto registrado. Sin embargo RC4 aún es una marca registrada. Actualmente la implementación no oficial de RC4 es legal, pero no puede ser utilizada con 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 como ARCFOUR, ARC4 o Alleged-RC4. RSA Security nunca ha liberado el algoritmo de su RC4.

RC4 es parte de los protocolos de cifrado más comunes como WEP, WPA para tarjetas wireless y TLS. Entre los factores principales que han ayudado a que RC4 esté en un rango tan amplio de aplicaciones son su increíble velocidad y simplicidad. La implementación tanto en software como en hardware es muy sencilla de desarrollar y son muy pocos los recursos necesarios para obtener un rendimiento eficiente de ARC4.

Descripción

RC4 es un un algoritmo sorprendentemente simple. Este consiste en 2 algoritmos: 1-Key Scheduling Algorithm (KSA) y 2- Pseudo-Random Generation Algorithm (PRGA). Ambos de estos algoritmos usan 8-by-8 S-box, el cual es solo un array de 256 números en el cual ambos son únicos en cuanto a rango y su valor va desde 0 hasta 255. Todos los números de 0 a 255 existen dentro del array, pero están solo mezclados de diferentes maneras, el KSA se encarga de realizar la primera mezcla en el S-Box, basado en el valor de la semilla dada dentro de él, y esta "semilla" puede ser de 256 bits de largo.

Primero, el S-box array es llenado con valores secuenciales desde 0-255. Este array será llamado simplemente S. Entonces, el otro array de 256-bits es llenado con el valor de la "semilla", repitiendo como sea necesario hasta que todo el array es llenado. Este array será llamado K, entonces el array S es mezclado usando el siguiente pseudocódigo.

j=0;
for i = 0 to 255
{
   j = (j+S[i] + K[i]) 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 el keystream data es necesitado, el Pseudo-Random Generation Algorithm (PRGA) es usado. 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 Pseudo-Code:

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. Este algoritmo es repetido para conseguir bytes adicionales de keystream. RC4 es simplemente suficiente, que puede ser fácilmente memorizado e implementado en el aire, y puede llegar a ser un poco "más" seguro si es usado apropiadamente, en fin, hay algunos problemas con la forma que RC4 es usado con el cifrado WEP en Wi-Fi.

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

Clave	Keystream	Mensaje	Texto cifrado
Key	eb9f7781b734ca72a719...	Plaintext	BBF316E8D940AF0AD3
Wiki	6044db6d41b7...	pedia	1021BF0420
Secret	04d46b053ca87b59...	Attack at dawn	45A01F645FC35B383552544B9BF5