Understanding RC4 byte by byte

Introduction

A buffer is filled with 00 01 02 ... ff. One loop swaps entries according to a key. Another keeps swapping entries and XORs each input byte with a value read from that same buffer. That sequence of operations is RC4.

The output depends on the exact order of reads and writes. With key 01 02 03 04 05, the first keystream byte is b2. To see where it comes from, follow the 256-byte state, indices i and j, and the swap that happens before each keystream read.

The state: a permutation of 256 bytes

RC4 keeps an array S[0..255] containing every byte value exactly once. Initially, S[i] = i. The key is not XORed directly with each message byte. It first rearranges S in the Key Scheduling Algorithm (KSA). Then the Pseudo-Random Generation Algorithm (PRGA) keeps changing that same array while obtaining one keystream byte for each input byte.

The indices i and j are byte values too. Their sums, and the index t used to read the keystream, are reduced modulo 256. Python expresses this with & 0xff; an 8-bit register naturally discards the overflow.

key ──> KSA ──> permuted S ──> PRGA ──> K[0], K[1], K[2], ...
                                      data[n] XOR K[n] = output[n]

XOR is reversible: (P XOR K) XOR K = P. Encryption and decryption run the same operation, provided both start with the same key and the same position in the keystream.

KSA: mixing the array with the key

KSA traverses S once. i runs from 0 to 255; j accumulates the current S[i] and one key byte. When the key is shorter than 256 bytes, the key index wraps around.

S[i] = i                                  for i = 0..255
j = 0
for i = 0..255:
    j = (j + S[i] + key[i % len(key)]) mod 256
    swap S[i], S[j]

Order matters: j uses S[i] before the swap. The next iteration sees the modified array. With the hexadecimal key 01 02 03 04 05, the first three iterations are:

On the second iteration, S[1] is 0 because the first swap moved 0 there. Computing all 256 j values against an unchanged identity array would therefore give the wrong state.

With rdi = &S[0], rsi = &key[0], ecx = i, r9d = key index, and r10d = j, the update to j and the swap can be written like this in x86-64 Intel syntax:

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

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

movzx loads a byte without sign extension. The and 0xff keeps j within the array. A compiler may instead keep j in an 8-bit register and omit the explicit mask.

PRGA: one keystream byte per iteration

After KSA, i and j are reset to zero. S is not reset: PRGA starts with the permuted array. Each iteration advances i, updates j, swaps two entries, and reads a third position to obtain K.

i = 0; j = 0
for each input byte:
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap S[i], S[j]
    t = (S[i] + S[j]) mod 256         # after the swap
    K = S[t]
    output = input XOR K

The sum producing t has the same value before and after the swap: only the order of its two terms changes. Reading S[t] must happen after the swap, though, because that position may have changed.

For key 01 02 03 04 05, the first PRGA iteration finds S[1] = 3 after KSA. Thus i = 1 and j = 3. Before the swap, S[3] = 201; afterward, S[1] = 201 and S[3] = 3. This gives t = (201 + 3) & 0xff = 204, and S[204] = 0xb2. That is the first byte in the RFC 6229 test vector.

In PRGA, r8b and r9b can hold i and j; overflow in these byte registers already implements modulo 256. With rdi = &S[0], rsi at the current input byte, and rdx at the current output byte, one iteration looks like this:

inc   r8b                            ; i = (i + 1) & 0xff
movzx eax, r8b
mov   cl, byte ptr [rdi + rax]       ; cl = old S[i]
add   r9b, cl                       ; j = (j + S[i]) & 0xff
movzx eax, r9b
mov   r10b, byte ptr [rdi + rax]     ; r10b = old S[j]
mov   byte ptr [rdi + rax], cl       ; S[j] = old S[i]
movzx eax, r8b
mov   byte ptr [rdi + rax], r10b     ; S[i] = old 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]             ; output byte = input XOR K
mov   byte ptr [rdx], al

RC4 has no special instruction. The pattern is an indexed read, an accumulating j, two writes that exchange bytes, another indexed read, and an XOR with the data. Implementations may combine steps or store S elsewhere, but the data dependencies remain.

In a complete routine, the input and output pointers advance to the next byte before the loop repeats. A compiler may choose other registers or reorder independent instructions; the values feeding each read and write still determine the output.

Manual Python implementation

In Python, & 0xff makes the byte boundary explicit, and s[i], s[j] = s[j], s[i] performs the two writes of the swap. The two loops correspond to KSA and PRGA without a cryptography library:

def rc4(key: bytes, data: bytes) -> bytes:
    if not key:
        raise ValueError("RC4 requires a nonempty key")

    # KSA: initialize and permute 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: generate a byte and consume an input byte each time.
    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

Feeding 16 zero bytes exposes the keystream because 0 XOR K = K. The result matches the first 16 bytes in RFC 6229. The assertion decrypts from a fresh state: a second call to rc4 repeats KSA and resets PRGA. Processing a message in chunks requires retaining S, i, and j between chunks; resetting them would move back to the start of the stream.

Reusing that starting stream for two different messages also exposes a relationship between their plaintexts: C1 XOR C2 = P1 XOR P2, because the keystream cancels out. This follows directly from the same XOR operation used to encrypt each message.

What to follow in a disassembly

In a binary, the 256-byte table may live on the stack or heap. S[i] = i may appear as a loop or a copy of a constant table. Next, follow the writes: KSA performs 256 swaps and accesses the key cyclically; PRGA keeps two byte-sized indices and performs an XOR for every processed byte.

The key may be embedded, constructed at runtime, or supplied by another routine. Variants may also discard initial keystream bytes, alter initialization, or transform the input further. Finding a 256-byte array alone does not prove RC4. Check the read and write order, the initial i and j, and the data that actually reaches the XOR.

KSA permutes S, and PRGA keeps changing it. Each K byte comes from the state left by all earlier swaps. Reconstructing S, i, and j explains the value that reaches the XOR at any position in the message.