AES-CTR Nonce Reuse Attack: XOR-Based Keystream Recovery and Plaintext Decryption

Why This Matters

In 2012, researchers discovered that Sony's PlayStation 3 firmware update encryption reused a CTR nonce across multiple messages, enabling full keystream recovery and allowing attackers to produce validly "encrypted" firmware containing arbitrary code. The same year, a large-scale analysis of real-world TLS sessions found evidence of nonce reuse in CTR-based cipher suites among embedded device implementations, exposing plaintext across thousands of connections. In CTF competitions, CTR nonce reuse is one of the most common symmetric crypto challenge archetypes, appearing in both the "many-time-pad" framing (multiple ciphertexts sharing a keystream) and the "recover one plaintext from two" framing. The attack requires only ciphertext and the ability to recognise English-language XOR patterns — no key and no complex mathematics.

Core Concept

CTR (Counter) mode transforms a block cipher into a stream cipher by encrypting successive counter values: KSᵢ = Eₖ(nonce || counter_i), where nonce is a unique value for each message and counter_i increments from 0. The ciphertext is Cᵢ = Pᵢ XOR KSᵢ. Because the keystream depends only on the key and nonce — not on the plaintext — CTR mode is malleable and provides no authentication.

The violated invariant is nonce uniqueness: if two messages P₁ and P₂ are encrypted with the same key and the same nonce, they produce ciphertexts C₁ = P₁ XOR KS and C₂ = P₂ XOR KS, where KS is identical. XORing the two ciphertexts cancels the keystream: C₁ XOR C₂ = P₁ XOR P₂ XOR KS XOR KS = P₁ XOR P₂. The attacker now has the XOR of two plaintexts with no key involvement. This is the many-time-pad (or two-time-pad) vulnerability — structurally identical to Vigenère but operating on bytes instead of letters.

Known-plaintext recovery of keystream: if the attacker knows (or guesses) any portion of one plaintext, the corresponding keystream bytes are immediately recovered: KS[i] = C₁[i] XOR P₁[i]. Once any keystream byte is known, the corresponding byte of every other message encrypted with the same nonce is also decrypted: P₂[i] = C₂[i] XOR KS[i].

Crib-dragging is the ciphertext-only variant: the attacker XORs the two ciphertexts to get P₁ XOR P₂, then slides a known English word ("the ", "is ", "and ", "password", etc.) — called a crib — across the XOR result. At positions where the crib coincides with plaintext from one message, the other message's bytes emerge as plausible English text. Both emerging texts are then used as cribs for each other, bootstrapping full plaintext recovery.

Nonce-misuse resistant modes such as AES-GCM-SIV and XChaCha20-Poly1305 are designed so that nonce reuse leaks only whether two plaintexts are identical, not the plaintexts themselves, and authentication tags remain unforgeable even under nonce reuse.

The cryptanalytic precondition is ciphertext-only (for crib-dragging on natural language) or known-plaintext (for direct keystream recovery when any plaintext byte is known).

Technical Deep-Dive

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

def crib_drag(c1: bytes, c2: bytes, crib: str) -> list[tuple[int, str, str]]:
    """
    Slide crib across C1 XOR C2 = P1 XOR P2.
    Returns positions where both emerging plaintexts look printable.
    """
    crib_bytes = crib.encode()
    xor_ct = xor_bytes(c1, c2)
    results = []
    for offset in range(len(xor_ct) - len(crib_bytes) + 1):
        # If crib matches P1 at offset, P2 bytes at offset emerge
        p2_candidate = xor_bytes(xor_ct[offset:offset+len(crib_bytes)], crib_bytes)
        # If crib matches P2 at offset, P1 bytes at offset emerge
        p1_candidate = xor_bytes(xor_ct[offset:offset+len(crib_bytes)], crib_bytes)
        # Check printability of the emerging candidate
        if all(32 <= b <= 126 for b in p2_candidate):
            results.append((offset, crib, p2_candidate.decode(errors="replace")))
    return results

def recover_keystream(ciphertexts: list[bytes], known_pt_idx: int,
                      known_pt: bytes) -> bytes:
    """
    Given one known plaintext, recover the keystream up to len(known_pt).
    Then decrypt all other ciphertexts at those positions.
    """
    ct_known = ciphertexts[known_pt_idx]
    keystream = xor_bytes(ct_known[:len(known_pt)], known_pt)
    decrypted = []
    for i, ct in enumerate(ciphertexts):
        if i == known_pt_idx:
            decrypted.append(known_pt)
        else:
            pt = xor_bytes(ct[:len(keystream)], keystream)
            decrypted.append(pt)
    return keystream, decrypted

# Many-time-pad: brute-force common English words as cribs
COMMON_CRIBS = [" the ", " and ", " of ", " to ", " in ", " is ",
                "password", "secret", "flag{", "http", "the "]

def many_time_pad_attack(ciphertexts: list[bytes]) -> dict:
    """
    Collect crib-drag hits across all pairs of ciphertexts.
    Returns mapping: offset -> list of candidate plaintext bytes.
    """
    results = {}
    for i in range(len(ciphertexts)):
        for j in range(i+1, len(ciphertexts)):
            for crib in COMMON_CRIBS:
                hits = crib_drag(ciphertexts[i], ciphertexts[j], crib)
                for offset, _, emerging in hits:
                    results.setdefault(offset, []).append(emerging)
    return results

Cryptanalysis Methodology

1. Confirm nonce reuse — Collect all available ciphertexts. If any two are the same length and XOR together to produce plausible-looking data (non-uniform, with high byte values near printable ASCII range), nonce reuse is likely. Identical leading bytes across ciphertexts also indicate a shared keystream prefix.
2. XOR all pairs — Compute C₁ XOR C₂ for every pair. For messages in English, XOR of two English plaintexts has a characteristic distribution: many bytes in the 0x00–0x3F range (XOR of two lowercase letters gives values in this range since lowercase ASCII starts at 0x61).
3. Apply crib-dragging — Slide common English words and phrases across each XOR pair using crib_drag(). Hits where both emerging values are printable ASCII are strong candidates for correct positions. Record confirmed positions.
4. Bootstrap from partial plaintext — Use confirmed portions as new, longer cribs to extend plaintext recovery across all ciphertexts simultaneously. Prioritise the longest confirmed crib at each position.
5. Recover the full keystream — Once enough plaintext positions are confirmed, reconstruct the keystream byte-by-byte. Apply the keystream to all ciphertexts to decrypt them completely.
6. Handle AES-CTR with known protocol headers — If the ciphertexts are from a known protocol (HTTP, JSON, XML), use the known header structure as the initial crib. For example, JSON always starts with '{', and HTTP responses start with 'HTTP'.

Secure Implementation Note — Never reuse a nonce in CTR mode or any nonce-based stream cipher. Generate nonces with a CSPRNG (os.urandom(12) for AES-GCM). If the risk of accidental nonce reuse is a concern (e.g., distributed systems, embedded devices), prefer nonce-misuse resistant AEAD schemes: AES-GCM-SIV (RFC 8452) or XChaCha20-Poly1305, which degrade gracefully under nonce reuse rather than catastrophically.

Common Cryptanalysis Errors

• XORing with the wrong alignment — Crib-dragging requires precise byte alignment. If the ciphertexts have variable-length headers or encoding prefixes (e.g., base64, hex), decode to raw bytes before XORing.
• Assuming all ciphertexts share the same nonce — In some systems, only a subset of ciphertexts share a nonce. Compute pairwise XOR and check each pair individually rather than assuming global nonce reuse.
• Ignoring ciphertexts of different lengths — XOR of unequal-length ciphertexts only recovers the keystream up to the length of the shorter ciphertext. Longer ciphertexts have additional bytes that can only be attacked via separate crib-dragging from the appropriate length.
• Not recognising the many-time-pad as a binary Vigenère — The attack is identical to Vigenère key recovery: the keystream is the "key" and byte XOR replaces modular addition. Apply Vigenère intuition (IoC, sliding window) to byte-level data when crib-dragging stalls.
• Stopping after recovering partial plaintext — Partial plaintext at 20 positions out of 100 may not include the flag. Continue extending the crib bootstrap until the full keystream is recovered.
• Confusing CTR with OTP — A one-time pad (OTP) is a CTR cipher where the keystream is truly random, used once, and never reused. An OTP with a reused "one-time" pad is no longer an OTP — it degrades to a many-time-pad with all the same weaknesses described here.

NICE Framework Alignment

Further Reading

• Attack on the RC4 Stream Cipher in WEP: The Many-Time Pad Problem — Scott Fluhrer et al., SAC 2001
• Nonce-Misuse Resistance — Phillip Rogaway, NIST workshop on authenticated encryption, 2014
• Practical Cryptography (Chapter 6: Stream Ciphers) — Niels Ferguson and Bruce Schneier, Wiley, 2003