Repeating-Key XOR — recovering key length and key from a Vigenère-style stream

Plaintext XORed byte-by-byte with a short key repeated cyclically (c_i = p_i ⊕ k_{i mod L}): structurally a Vigenère cipher over bytes instead of letters, and it breaks the same way — recover the key length, then crack the key one byte at a time.

The signal that betrays it

- Ciphertext is raw binary or hex/base64-encoded, with no block structure (no 16-byte alignment, no IV field) — this is what separates it from a block-cipher mode at a glance. - The challenge or its metadata hints at "XOR" or "vigenere" directly, or the ciphertext is just too random-looking for a classical letter-substitution cipher but too short-period for a real stream cipher. - The expected plaintext is ASCII text (English prose is the classic case — Cryptopals set 1, challenge 6 uses exactly this setup). - Each key byte, applied to its column of the transposed ciphertext, is a self-contained single-byte-XOR problem — i.e. a Substitution & Shift Cipher — recovered by letter-frequency, not by algebra instance repeated L times in parallel. Recognizing that decomposition is the whole trick.

How it's exploited

Three-stage break, no factoring or lattice work needed — pure statistics:

1. Find the key length L via normalized Hamming distance. For each candidate L in a range (2–40 covers virtually all CTF cases), take several L-byte chunks of ciphertext, compute the pairwise Hamming distance (bit-differences) between them, and normalize by L. The candidate with the smallest average normalized distance is very likely the true key length — because at the correct period, c_i ⊕ c_j = (p_i⊕k) ⊕ (p_j⊕k) = p_i ⊕ p_j, the key cancels out and you're left with the low bit-density of XOR-ed English text; at the wrong period the key doesn't cancel and the distance looks close to random (~4 bits/byte average). - Operational detail that matters: don't just compare the first two chunks — pull 4 (or more) chunks and average *all* pairwise distances. Two chunks alone are noisy enough to misrank close candidates; four stabilizes the ranking substantially. - Don't commit to the single best-scoring L blindly — keep the top 2–3 candidates and let stage 3 confirm which one actually decrypts to readable text. A near-tied second place is common on short ciphertexts. 2. Transpose the ciphertext into L columns: column i is every byte at position ≡ i (mod L). Every byte in a given column was XORed with the *same* key byte. 3. Solve each column independently as single-byte XOR: try all 256 candidate bytes, XOR them against the whole column, and score the result by printable-ASCII / English-letter-frequency fitness (chi-squared against expected English frequencies works better than a bare "is it printable" filter, which lets through false positives on short columns). The best-scoring byte per column, concatenated, is the key.

```python def hamming(a, b): return sum(bin(x ^ y).count('1') for x, y in zip(a, b))

def keysize(ct, lo=2, hi=40, n_chunks=4): def score(L): chunks = [ct[i*L:(i+1)*L] for i in range(n_chunks)] d = [hamming(chunks[i], chunks[j]) for i in range(n_chunks) for j in range(i+1, n_chunks)] return sum(d) / len(d) / L return sorted(range(lo, hi + 1), key=score)[:3] # top-3, not just the best

def single_byte(col, fit): return max(range(256), key=lambda k: fit(bytes(b ^ k for b in col)))

def crack(ct, fit, L): cols = [ct[i::L] for i in range(L)] return bytes(single_byte(c, fit) for c in cols) # the recovered key ```

Related techniques this composes with or sits next to: Substitution & Shift Cipher — recovered by letter-frequency, not by algebra (each column is exactly this problem), Vigenere Cipher — Kasiski / Index-of-Coincidence Key-Length Recovery (same construction, letters instead of bytes), Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge (the general umbrella of additive-cipher breaks), One-Time-Pad / Many-Time-Pad Reuse — the crib-drag break when a pad is used twice (a *different* attack — see below).

What does NOT work

- Confusing this with many-time-pad / keystream reuse. One-Time-Pad / Many-Time-Pad Reuse — the crib-drag break when a pad is used twice and Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge look superficially similar ("a key/keystream got reused") but are a different scenario: the *same* keystream reused across *multiple independent ciphertexts*, broken by XORing ciphertexts together and crib-dragging. Repeating-key XOR is a *single* ciphertext where a *short* key repeats *within itself*. Applying crib-dragging techniques here, or Hamming-distance keysize detection there, is a category error — check which shape you actually have before picking a method. - Trusting a single best-scoring key length blindly. On short or unlucky ciphertexts the true L sometimes isn't the outright minimum — it's in the top few candidates. If stage 3 produces gibberish, don't restart from scratch: retry with the second- and third-best L from stage 1 before suspecting a different cipher entirely. - Using only a "is it printable" filter to score single-byte-XOR candidates. It underdetermines short columns — several key-byte guesses can produce all-printable garbage. A frequency-based score (English letter/space frequency, chi-squared) is far more discriminating and is worth the extra few lines of code. - Assuming the plaintext is English ASCII when it isn't. The whole column-scoring step depends on a fitness function tuned to the expected plaintext's statistics. Binary, compressed, or non-English plaintext defeats an English-frequency scorer outright — you need either a different language model or a known-plaintext crib to anchor stage 3. - Ignoring the case where key length ≈ ciphertext length. If the "repeating" key is as long as (or longer than) the message, there's no repetition to exploit and the Hamming-distance method degenerates into noise — this is no longer repeating-key XOR, it's effectively a one-time pad and unbreakable by this method (though if the *same* long key is reused across other messages, that reopens One-Time-Pad / Many-Time-Pad Reuse — the crib-drag break when a pad is used twice).