XOR Keystream Reuse Attack: Many-Time Pad Cryptanalysis and Statistical Key Recovery

Why This Matters

XOR key reuse is one of the oldest exploitable failures in symmetric cryptography, and it continues to appear in CTF challenges, poorly written custom encryption libraries, and embedded firmware. The canonical historical example is the "two-time pad" attack on Lorenz cipher messages in World War II — multiple German messages were mistakenly sent with the same key settings, allowing Bill Tutte and colleagues at Bletchley Park to reconstruct the Lorenz cipher without ever capturing a physical device. In the modern era, CVE-2014-1266 (Apple SecureTransport) and several firmware encryption schemes have been shown to misapply stream ciphers with repeated keystreams. Any scheme that encrypts multiple plaintexts with the same XOR key — whether a short repeating key, a stream cipher nonce reuse, or a one-time pad reused — is vulnerable to the same family of attacks described here.

Core Concept

The XOR cipher with a repeating key of length n computes each ciphertext byte as c[i] = p[i] XOR k[i mod n], where p is plaintext and k is the key. This construction is mathematically equivalent to the Vigenère cipher operating in the binary (byte) domain rather than the alphabetic domain — the same algebraic structure that Kasiski and Friedman broke in the 19th century applies directly.

The one-time pad (OTP) is information-theoretically secure when the key is: (1) truly random, (2) at least as long as the message, and (3) never reused. The XOR cipher with a repeating key violates all three conditions for any message longer than the key.

Keystream recovery via known plaintext: the fundamental attack identity is k = c XOR p. If any single byte of plaintext p[i] is known, the corresponding key byte k[i mod n] is immediately recovered as c[i] XOR p[i]. Recovering the full key requires knowing one plaintext byte per key position, achievable by:

• Knowing the file format header (e.g., the first 4 bytes of a PNG are always x89PNG).
• Knowing the protocol framing (e.g., HTTP/1.1 responses begin with HTTP/).
• Guessing the most common byte (for English ASCII text, spaces 0x20 are most frequent).

Key length recovery via Hamming distance minimisation: if the key length is unknown, the normalised edit distance (Hamming distance divided by the slice length) between ciphertext slices is minimised when the slice length equals the key length. This works because XOR of two ciphertext slices at the correct key length spacing produces XOR of two plaintext bytes, which have a characteristic Hamming weight distribution for natural language or structured data.

Formally, for candidate key length L, compute: d(L) = hamming(c[0:L], c[L:2L]) / L

The L minimising d(L) is the most likely key length. This is the index of coincidence adapted to the byte domain — the original Friedman coincidence test from 1920, applied to bytes rather than alphabetic frequencies.

Crib-dragging exploits a statistical property: XOR of two English ASCII ciphertexts (c1 XOR c2 = p1 XOR p2) has the property that wherever one plaintext has a space (0x20), the other plaintext byte is revealed because 0x20 XOR letter = letter with bit 5 toggled (i.e., case-flipped). By sliding a known word (crib) across the XOR of two ciphertexts and checking whether the residual bytes form plausible ASCII at the complementary positions, the plaintext can be reconstructed interactively.

Technical Deep-Dive

# XOR key reuse cryptanalysis toolkit
# Prerequisites: standard library only

from itertools import combinations

def hamming_distance(b1: bytes, b2: bytes) -> int:
    """Count differing bits between two equal-length byte strings."""
    return sum(bin(x ^ y).count('1') for x, y in zip(b1, b2))

def normalised_edit_distance(ciphertext: bytes, keylen: int) -> float:
    """Average normalised Hamming distance across multiple slice pairs."""
    slices = [ciphertext[i*keylen:(i+1)*keylen]
              for i in range(min(4, len(ciphertext) // keylen))]
    pairs  = list(combinations(slices, 2))
    if not pairs:
        return float('inf')
    return sum(hamming_distance(a, b) / keylen for a, b in pairs) / len(pairs)

def find_key_length(ciphertext: bytes, max_keylen: int = 40) -> list:
    """Return candidate key lengths sorted by normalised Hamming distance."""
    scores = [(kl, normalised_edit_distance(ciphertext, kl))
              for kl in range(2, max_keylen + 1)]
    return sorted(scores, key=lambda x: x[1])

def xor_bytes(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))

def break_single_byte_xor(stream: bytes) -> tuple:
    """
    Recover a single key byte by frequency analysis.
    Returns (key_byte, score, decrypted_stream).
    Score = count of printable ASCII bytes — higher is better.
    """
    best = (0, -1, b"")
    for k in range(256):
        candidate = bytes(b ^ k for b in stream)
        score = sum(1 for c in candidate if 32 <= c <= 126)
        if score > best[1]:
            best = (k, score, candidate)
    return best

def recover_repeating_key(ciphertext: bytes, keylen: int) -> bytes:
    """
    For each key position, collect every keylen-th ciphertext byte
    and run single-byte XOR frequency attack.
    """
    key = bytearray()
    for pos in range(keylen):
        stream = bytes(ciphertext[i] for i in range(pos, len(ciphertext), keylen))
        k, _, _ = break_single_byte_xor(stream)
        key.append(k)
    return bytes(key)

# --- Known-plaintext recovery: k = c XOR p ---
def recover_key_from_known_plaintext(ciphertext: bytes,
                                     known_plain: bytes,
                                     offset: int = 0) -> bytes:
    """Recover key bytes at positions offset..offset+len(known_plain)."""
    return xor_bytes(ciphertext[offset:offset + len(known_plain)], known_plain)

# --- Crib-drag: slide a known word across (c1 XOR c2) ---
def crib_drag(ct1: bytes, ct2: bytes, crib: bytes) -> list:
    """
    XOR the two ciphertexts and slide the crib across.
    Where the result is printable ASCII at all crib positions,
    report the offset and the revealed plaintext bytes.
    """
    xored   = xor_bytes(ct1, ct2)
    results = []
    for offset in range(len(xored) - len(crib) + 1):
        candidate = xor_bytes(xored[offset:offset + len(crib)], crib)
        if all(32 <= c <= 126 for c in candidate):
            results.append((offset, candidate))
    return results

# CyberChef workflow (online tool, no install required):
# 1. Paste hex ciphertext → "From Hex" → "XOR Brute Force" (key length 1–40)
# 2. Visually inspect outputs for readable text patterns

# xortool for automated key length and key recovery:
# pip install xortool
xortool -x ciphertext.hex          # auto-detect key length
xortool -l 13 -c 20 ciphertext.bin # specify key length 13, most common byte = 0x20 (space)
# Output: key bytes and decrypted plaintext in xortool_out/

Cryptanalysis Methodology

1. Collect all ciphertexts — Confirm that multiple messages are encrypted with the same key (identical key length, or a stream cipher with nonce reuse). If only one ciphertext is provided, look for known-plaintext opportunities (file headers, protocol framing).
2. Estimate key length — Call find_key_length(ciphertext) for key lengths 2–40. The top candidates with the lowest normalised Hamming distance are the most probable key lengths. Verify the top two or three candidates.
3. Recover key bytes via frequency attack — For each candidate key length L, split the ciphertext into L interleaved streams (each stream consists of every L-th byte starting at offset 0, 1, ..., L-1). Run break_single_byte_xor on each stream.
4. Apply known-plaintext shortcuts — If any plaintext byte at position i is known (file header, protocol keyword), recover k[i mod L] directly with k = c XOR p, then verify the key hypothesis against the full ciphertext.
5. Use crib-dragging for multi-message XOR — XOR two ciphertexts to eliminate the key. Slide known words ('the', 'and', ' a ', 'is ', 'http', common CTF flag prefixes) across the result. Accept positions where all XOR-ed bytes are printable ASCII.
6. Reconstruct and verify — XOR the full ciphertext with the recovered key. Confirm the output is valid plaintext (readable text, correct file magic bytes, or flag format).

Secure Implementation Note — The XOR cipher with a repeating key provides no cryptographic security. Use an authenticated stream cipher such as ChaCha20-Poly1305 (RFC 8439) or AES-GCM (NIST SP 800-38D). Both require a unique nonce per message — never reuse a (key, nonce) pair. For a true one-time pad, the key must be generated from a CSPRNG (os.urandom), be at least as long as the message, and never reused. In Python: from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305.

Common Cryptanalysis Errors

• Applying frequency analysis directly to ciphertext bytes — Frequency analysis works on each interleaved key-position stream, not the ciphertext as a single stream. Treating the full ciphertext as one stream gives incorrect key byte guesses.
• Using floating-point Hamming distance without normalising — Longer candidate key lengths span more ciphertext bytes; without dividing by the key length, longer candidates always score lower. Always normalise by dividing the Hamming distance by the slice length.
• Stopping at key length without recovering individual bytes — The Hamming distance test gives key length, not the key itself. Each byte of the key must be recovered separately via single-byte frequency attack or known plaintext.
• Forgetting that crib-dragging requires at least two ciphertexts — Crib-dragging works on (c1 XOR c2), which equals (p1 XOR p2). With only one ciphertext, this technique is not applicable.
• Missing OTP vs repeating key distinction — If the key is exactly as long as the ciphertext and appears uniformly random, it may be a genuine OTP. Verify key reuse before applying the frequency attack (two messages of the same length with the same key are the tell).
• Assuming space is always the most frequent byte — For non-English or non-ASCII plaintexts (binary data, compressed content), 0x20 is not the dominant byte. Examine the challenge plaintext type before applying the space-dominant heuristic.

NICE Framework Alignment

Further Reading

• Friedman, W.F. (1920). The Index of Coincidence and Its Applications in Cryptanalysis — Riverbank Publication No. 22
• Ferguson, N., Schneier, B., and Kohno, T. (2010). Cryptography Engineering — Chapter 3: Stream Ciphers — Wiley
• RFC 8439: ChaCha20 and Poly1305 for IETF Protocols — IETF (Nir and Langley)