Wiki / Concepts

Keystream Reuse

What happens when a stream cipher encrypts two different messages under the same key and nonce: the key cancels out and the two plaintexts are left XORed with each other.

keystream reuse key reuse nonce reuse iv reuse two-time pad many-time pad crib dragging known plaintext stream cipher ctr mode aes-ctr aes-ccm gcm rc4 xor counter reset
Two messages, one keystream
C1 = P1 XOR KS message 1
C2 = P2 XOR KS message 2
C1 XOR C2 = P1 XOR P2 no key left
XOR the two ciphertexts and the keystream cancels, whatever it was and however strong the cipher underneath. What remains is one plaintext masked by the other, which is not encryption at all: it is a puzzle that the redundancy of real data solves.

Keystream reuse is the failure where a stream cipher, or a block cipher in a streaming mode, produces the same pseudorandom bytes twice and encrypts two different messages with them. It is not a weakness of the cipher. AES is not broken when this happens; the construction around it is misused, and the result is that the cipher stops doing anything at all for those two messages.

What it is

A stream cipher encrypts by generating a keystream from the key and a nonce, and XORing it with the plaintext:

C1 = P1 XOR KS
C2 = P2 XOR KS

An attacker who has both ciphertexts computes:

C1 XOR C2 = (P1 XOR KS) XOR (P2 XOR KS) = P1 XOR P2

The keystream is gone. No key was needed to remove it, and no amount of key length would have helped. What is left is the XOR of two plaintexts, historically called a two-time pad, and it is a solvable puzzle whenever the plaintexts have any structure at all.

The two ways in are:

  • Known plaintext. If you know or can predict any part of one message, XOR it into the combined stream and the other message falls out at those positions, for free and with no guessing.
  • Crib dragging. If you know nothing, guess a likely fragment of one message, slide it along P1 XOR P2, and read what comes out on the other side. At the wrong offset you get noise; at the right one you get language. Then extend from both ends. English text, protocol headers, file magic and fixed field layouts are all far more predictable than they feel.
def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

combined = xor(c1, c2)                 # keystream already gone
print(xor(combined, b"ESPILON{"))      # a known crib gives the other side directly

for off in range(len(combined) - 8):   # crib dragging when you know nothing
    guess = xor(combined[off:off + 8], b" the ")
    if all(32 <= b < 127 for b in guess):
        print(off, guess)

Why it matters

Every modern AEAD construction, AES-CTR, AES-CCM, AES-GCM and ChaCha20-Poly1305 among them, is a stream cipher with a nonce, and every one of them fails this way. The nonce is what keeps two encryptions apart, and it is usually a counter that lives in RAM. That makes reuse an availability of state problem rather than a cryptography problem, which is why it survives code review: the crypto call is textbook correct and the bug is three layers away in a reset path.

The reliable sources of reuse in embedded work are all mundane: - A counter kept in RAM and zeroed by a wake path, a watchdog reset or a firmware update, while the key is kept in flash and survives. - A random IV drawn from an unseeded or badly seeded PRNG, so a device produces the same value on every boot. - A protocol that re-keys the session without changing the nonce, or changes the nonce without re-keying. - A counter that is simply too small and wraps.

GCM deserves a specific warning: nonce reuse there does not only expose plaintext, it leaks the authentication subkey and lets an attacker forge messages. CCM and CTR lose confidentiality only, which is bad enough.

How to work with it

Detecting reuse in a capture needs no key:

  1. Group ciphertexts that plausibly share a key and a nonce, for example the same direction of the same session.
  2. XOR every pair over their overlapping length.
  3. Score the result. Random against random is uniform; two plaintexts XORed together is not. Count bytes below 0x80, count zero bytes (they mark positions where the two plaintexts agree) or compute an index of coincidence. Real pairs stand out immediately.
  4. On a hit, drag cribs, or apply any known plaintext you already have.

A structural shortcut worth remembering: protocol headers are free known plaintext. A length field you can compute from the frame size, a fixed channel identifier, a constant opcode, all of them give you keystream bytes without a single guess, and those bytes decrypt the other message at the same offsets.

Pitfalls

  • The MIC will not tell you. An authentication tag is computed per message under that message's nonce. Two messages under one nonce both authenticate perfectly. Nothing in the protocol notices, and nothing logs it.
  • Reuse is per nonce, not per key. Encrypting a thousand messages under one key is fine, as long as every nonce differs. The key is not the thing you must vary.
  • Partial overlap still leaks. If the two messages have different lengths, the shorter one is fully exposed and the tail of the longer one is not. That is a partial break, not a failure.
  • The plaintexts do not need to be text. Two binary structures XORed together are just as breakable, because the fixed fields agree and XOR to zero, marking themselves.
  • Do not fix it by hashing the counter. The fix is to guarantee the nonce never repeats: persist it, or derive it from something monotonic that survives a reset, or re-key whenever you cannot.

Further reading

Used in these courses

BLE Exploitation