XOR, crib dragging, and the two-time pad

XOR is the most common primitive in CTF crypto because it is the cheapest thing an author can build a challenge around, and because it fails in instructive ways. Three properties do all the damage: XOR is its own inverse (a ^ b ^ b = a), it is commutative and associative, and a ^ a = 0. Every attack below is a consequence of one of those.

Single-byte XOR: 256 guesses and a scoring function

If a message is XORed with one repeated byte, there are only 256 possible keys. Try them all and score each candidate for English-likeness - chi-squared, printable-character ratio, or a simple frequency heuristic. This is not a clever attack, it is an exhaustive one, and it always works.

def score(b: bytes) -> float:
    # Cheap English score: reward letters and spaces, punish control bytes.
    good = sum(1 for c in b if c in b’ETAOIN SHRDLUetaoin shrdlu')
    bad  = sum(1 for c in b if c < 9 or (13 < c < 32) or c > 126)
    return good - 5 * bad

def break_single_byte(ct: bytes):
    return max(
        ((k, bytes(c ^ k for c in ct)) for k in range(256)),
        key=lambda kv: score(kv[1]),
    )

One property worth internalising: XOR with a byte below 0x20 preserves the case pattern of the text, and XOR with 0x20 flips case exactly. If a decode comes out as recognisable words in inverted case, your key is off by 0x20 and you are one step from done.

Repeating-key XOR: find the length, then split

Repeating-key XOR is the Vigenère cipher over bytes, and it breaks the same way: recover the key length *k*, split the ciphertext into *k* columns, and break each column as a single-byte XOR. Only the first step needs a new idea.

The idea is the normalised Hamming distance. English text has low entropy, so two chunks of English XORed together differ in relatively few bits - roughly 2 to 3 bits per byte. Two chunks of unrelated ciphertext differ in about 4 bits per byte, the random baseline. When you guess the key length correctly, corresponding chunks line up with the same key bytes, the key cancels, and you are measuring plaintext against plaintext.

def hamming(a: bytes, b: bytes) -> int:
    return sum(bin(x ^ y).count('1') for x, y in zip(a, b))

def guess_keysize(ct: bytes, lo=2, hi=40, blocks=4):
    results = []
    for k in range(lo, hi + 1):
        if len(ct) < k * (blocks + 1):
            break
        chunks = [ct[i * k:(i + 1) * k] for i in range(blocks + 1)]
        pairs = [(chunks[i], chunks[i + 1]) for i in range(blocks)]
        avg = sum(hamming(a, b) for a, b in pairs) / (blocks * k)
        results.append((round(avg, 3), k))
    return sorted(results)[:5]   # lower distance = better guess

def break_repeating(ct: bytes, k: int) -> bytes:
    key = bytes(break_single_byte(ct[i::k])[0] for i in range(k))
    return key

Known plaintext: the key falls straight out

Because XOR is its own inverse, key = ciphertext ^ plaintext. If you know *any* stretch of the plaintext, you get the corresponding stretch of key for free. In CTFs you almost always know some plaintext:

• The flag format. If the plaintext starts with flag{, XOR those five ciphertext bytes against flag{ and you have five key bytes.
• File headers. A XORed PNG still begins with the 8-byte PNG signature, a XORed ZIP with PK\x03\x04, a XORed PDF with %PDF-.
• Structural text. JSON starts with {", HTTP with GET or HTTP/1.1, PEM with -----BEGIN.

Recovering a few key bytes is often enough to see the rest. If the key turns out to be a repeating ASCII word, the recovered fragment tells you what the word is, and the whole message unlocks.

PNG_SIG = bytes([0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A])
key_prefix = bytes(c ^ p for c, p in zip(ciphertext, PNG_SIG))
print(key_prefix)   # b’sup3rs3' -> the key is probably 'sup3rs3cr3t'

The two-time pad

A one-time pad is information-theoretically secure, on one condition: the pad is used once. Reuse it and the security evaporates, because for two ciphertexts under the same key

C1 = P1 ^ K
C2 = P2 ^ K
C1 ^ C2 = P1 ^ P2      # the key is gone entirely

You are now looking at the XOR of two English plaintexts, with no key involved. That object is very far from random, and crib dragging is how you unpick it.

How crib dragging works

Take a likely fragment of plaintext - a *crib* - such as " the ". Slide it along C1 ^ C2, XORing at each offset. Wherever the crib happens to align with that exact text in P1, the result at that position is the corresponding piece of P2, and vice versa. Almost every offset yields noise; the correct offsets yield readable English.

def crib_drag(xored: bytes, crib: bytes):
    for off in range(len(xored) - len(crib) + 1):
        window = xored[off:off + len(crib)]
        out = bytes(a ^ b for a, b in zip(window, crib))
        if all(32 <= c < 127 for c in out):
            yield off, out.decode()

for off, text in crib_drag(c1_xor_c2, b' the '):
    print(off, repr(text))

The technique bootstraps. A hit gives you a fragment of the other plaintext; that fragment extends into a longer word; the longer word becomes your next crib at that offset; and you ratchet outward in both directions. Good starting cribs are " the ", " and ", "flag{", the event name, and any word from the challenge description.

Many-time pad: solve it column-wise instead

With more than a handful of ciphertexts under the same key, you do not need cribs at all. Column *i* of every ciphertext was XORed with key byte *i*, so each column is a single-byte XOR problem across many samples. Guess the byte that makes the whole column printable and English-shaped, and repeat for every column. Roughly seven ciphertexts is usually enough for this to converge on its own.

Recognising XOR in the wild

• Byte values clustered in an unusual band (say 0x40-0x7f shifted oddly) rather than spread over the full range - single-byte XOR of ASCII does this.
• Repeating patterns at a fixed stride: identical plaintext runs XOR to identical ciphertext runs when they align with the key period. Long runs of the same byte in the plaintext (padding, spaces) leak the key directly.
• A file that is *almost* a known format: right length, right structure, wrong magic. XOR the observed first bytes against the expected magic and see if you get something that repeats.
• Entropy around 4-5 bits per byte rather than the ~7.9 you would see from real encryption. XOR does not compress or randomise; it just relabels.

That last point is the summary of the whole post. XOR is a relabelling, not a randomisation, and every statistical structure in the plaintext survives it intact. Your job is only ever to find the structure that survived.