Entendiendo RC4 byte a byte

Introducción

Un buffer se llena con los bytes 00 01 02 ... ff. Luego, un bucle intercambia posiciones según una clave. Un segundo bucle continúa los intercambios y combina cada byte de entrada con un valor leído del mismo buffer mediante XOR. Esa secuencia de operaciones es RC4.

El resultado depende del orden exacto de las lecturas y las escrituras. Con la clave 01 02 03 04 05, el primer byte de flujo es b2. Para entender de dónde sale hay que seguir el estado de 256 bytes, los índices i y j y el intercambio que ocurre antes de cada lectura.

El estado: una permutación de 256 bytes

RC4 mantiene S[0..255], un array que contiene cada valor de byte exactamente una vez. Al empezar, S[i] = i. La clave no se combina directamente con cada byte del mensaje: primero reordena S mediante el Key Scheduling Algorithm (KSA). Después, el Pseudo-Random Generation Algorithm (PRGA) modifica ese mismo array mientras obtiene un byte de flujo por cada byte de entrada.

Los índices i y j también son bytes. Todas sus sumas, y el índice t usado para extraer el flujo, se reducen módulo 256. En Python aparece & 0xff; en un registro de 8 bits el desbordamiento ya descarta los bits superiores.

clave ──> KSA ──> S permutado ──> PRGA ──> K[0], K[1], K[2], ...
                                          datos[n] XOR K[n] = salida[n]

El XOR es reversible: (P XOR K) XOR K = P. Cifrar y descifrar ejecutan la misma operación, siempre que ambos lados partan de la misma clave y de la misma posición del flujo.

KSA: mezclar el array con la clave

KSA recorre S una sola vez. i avanza de 0 a 255; j acumula el valor actual de S[i] y un byte de la clave. Si la clave es más corta que 256 bytes, su índice vuelve al principio.

S[i] = i                                  para i = 0..255
j = 0
para i = 0..255:
    j = (j + S[i] + clave[i % len(clave)]) mod 256
    intercambiar S[i], S[j]

El orden importa: j se calcula con el S[i] anterior al intercambio. La siguiente iteración ve el array ya modificado. Con la clave hexadecimal 01 02 03 04 05, las tres primeras vueltas quedan así:

En la segunda vuelta S[1] vale 0 porque el primer intercambio llevó el 0 a esa posición. Este detalle explica por qué no sirve calcular los 256 valores de j a partir de un array de identidad inmutable.

Con rdi = &S[0], rsi = &clave[0], ecx = i, r9d = índice de clave y r10d = j, la actualización de j y el intercambio se pueden expresar así en x86-64, con sintaxis Intel:

movzx eax, byte ptr [rdi + rcx]      ; eax = S[i], antes del swap
movzx edx, byte ptr [rsi + r9]       ; edx = clave[k]
add   r10d, eax
add   r10d, edx
and   r10d, 0xff                     ; j = (j + S[i] + clave[k]) % 256

mov   dl, byte ptr [rdi + r10]       ; temporal = S[j]
mov   byte ptr [rdi + rcx], dl       ; S[i] = antiguo S[j]
mov   byte ptr [rdi + r10], al       ; S[j] = antiguo S[i]

movzx carga un byte sin propagar signo. El and 0xff mantiene j en el rango de índices del array. Un compilador también puede usar un registro de 8 bits para j, evitando esa máscara explícita.

PRGA: un byte de flujo por vuelta

Terminado KSA, i y j se reinician a cero. Esto no restaura S: PRGA parte del array ya mezclado. Cada vuelta incrementa i, actualiza j, intercambia dos entradas y lee una tercera posición para obtener K.

i = 0; j = 0
para cada byte de entrada:
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    intercambiar S[i], S[j]
    t = (S[i] + S[j]) mod 256         # después del intercambio
    K = S[t]
    salida = entrada XOR K

La suma que forma t da el mismo valor si se hace antes o después del intercambio, porque solo cambia el orden de los dos sumandos. La lectura S[t], en cambio, debe hacerse después: el intercambio puede haber cambiado esa posición.

Para la clave 01 02 03 04 05, tras KSA, la primera vuelta de PRGA encuentra S[1] = 3. Por tanto i = 1 y j = 3. Antes del intercambio, S[3] = 201; después, S[1] = 201 y S[3] = 3. Sale t = (201 + 3) & 0xff = 204, y S[204] = 0xb2. Es el primer byte del vector de prueba de RFC 6229.

En PRGA, r8b y r9b pueden guardar los índices i y j; el desbordamiento de sus sumas ya implementa el módulo 256. Con rdi = &S[0], rsi en el byte de entrada y rdx en el de salida, una vuelta queda así:

inc   r8b                            ; i = (i + 1) & 0xff
movzx eax, r8b
mov   cl, byte ptr [rdi + rax]       ; cl = antiguo S[i]
add   r9b, cl                       ; j = (j + S[i]) & 0xff
movzx eax, r9b
mov   r10b, byte ptr [rdi + rax]     ; r10b = antiguo S[j]
mov   byte ptr [rdi + rax], cl       ; S[j] = antiguo S[i]
movzx eax, r8b
mov   byte ptr [rdi + rax], r10b     ; S[i] = antiguo S[j]

add   cl, r10b                      ; t = (S[i] + S[j]) & 0xff
movzx eax, cl
mov   al, byte ptr [rdi + rax]       ; al = K = S[t]
xor   al, byte ptr [rsi]             ; byte de salida = entrada XOR K
mov   byte ptr [rdx], al

No hay una instrucción especial de RC4. El patrón es una lectura indexada, un j acumulativo, dos escrituras que intercambian bytes, otra lectura indexada y un XOR con los datos. Algunas implementaciones fusionan pasos o guardan S en una zona distinta de memoria; el flujo de dependencias sigue siendo el mismo.

En una rutina completa, los punteros de entrada y salida avanzan al siguiente byte y el bucle repite esa secuencia. El compilador puede elegir otros registros o reorganizar instrucciones independientes; los valores que alimentan cada lectura y escritura siguen determinando el resultado.

Implementación manual en Python

En Python, & 0xff hace explícito el límite de un byte y la asignación s[i], s[j] = s[j], s[i] realiza las dos escrituras del intercambio. Los dos bucles corresponden a KSA y PRGA, sin bibliotecas criptográficas:

def rc4(key: bytes, data: bytes) -> bytes:
    if not key:
        raise ValueError("RC4 necesita una clave no vacía")

    # KSA: inicializar y permutar S.
    s = list(range(256))
    j = 0
    for i in range(256):
        j = (j + s[i] + key[i % len(key)]) & 0xff
        s[i], s[j] = s[j], s[i]

    # PRGA: generar un byte y consumir un byte de datos por vuelta.
    i = 0
    j = 0
    output = bytearray()
    for value in data:
        i = (i + 1) & 0xff
        j = (j + s[i]) & 0xff
        s[i], s[j] = s[j], s[i]
        t = (s[i] + s[j]) & 0xff
        output.append(value ^ s[t])

    return bytes(output)


key = bytes.fromhex("0102030405")
stream = rc4(key, bytes(16))
print(stream.hex(" "))
# b2 39 63 05 f0 3d c0 27 cc c3 52 4a 0a 11 18 a8

message = b"RC4"
ciphertext = rc4(key, message)
assert rc4(key, ciphertext) == message

Pasar 16 bytes nulos deja visible el flujo, porque 0 XOR K = K. El resultado coincide con los primeros 16 bytes publicados en RFC 6229. La aserción descifra desde un estado nuevo: llamar otra vez a rc4 repite KSA y reinicia PRGA. Si se procesa un mensaje en fragmentos, hay que conservar S, i y j entre fragmentos; reiniciarlos cambiaría la posición del flujo.

Reutilizar ese flujo inicial para dos mensajes distintos también revela una relación entre sus textos originales: C1 XOR C2 = P1 XOR P2, porque el flujo se cancela. Es una consecuencia directa del mismo XOR usado para cifrar cada mensaje.

Qué mirar al desensamblar

En un binario, la tabla de 256 bytes puede estar en la pila o en el heap. La inicialización S[i] = i puede ser un bucle o una copia de una tabla constante. Después conviene seguir las escrituras: KSA hace 256 intercambios y consulta la clave de forma cíclica; PRGA mantiene dos índices que se desbordan a 8 bits y realiza un XOR por byte procesado.

La clave puede estar embebida, construirse en tiempo de ejecución o venir de otra rutina. También puede haber variantes que descartan bytes iniciales del flujo, cambian la inicialización o aplican otra transformación a la entrada. Por eso, reconocer un array de 256 bytes no basta: hay que verificar el orden de las lecturas y escrituras, la posición inicial de i y j, y qué datos llegan realmente al XOR.

S se permuta durante KSA y sigue cambiando durante PRGA. Cada byte K sale del estado dejado por los intercambios anteriores. Reconstruir S, i y j basta para explicar el valor que llega al XOR en cualquier posición del mensaje.