Related-Key Attack — exploiting encryptions under keys with a known relationship

You observe encryptions under two or more keys whose *relationship* you know (K and K⊕Δ, or K and K+1) even though K itself stays secret; weaknesses in the key schedule let that known difference propagate predictably, enabling differential-style key recovery across keys instead of across plaintexts.

The signal that gives it away

- The oracle or protocol lets you request ciphertext under several keys derived from one secret master key by a known transform — XOR with a chosen delta, an incrementing counter, a per-session "rekey" step. This is the whole precondition: no relationship, no attack. - "Rekeying" schemes and nonce-as-key designs smell of this immediately. The textbook real case is WEP: the RC4 key for every packet is IV || WEPkey, so every packet is encrypted under a *related* key (same secret suffix, known-relationship prefix), which is exactly what broke it in practice. - The key schedule looks linear, or has thin diffusion relative to the number of cipher rounds — e.g. a 256-bit key schedule that only runs a handful of expansion rounds to feed a much longer cipher. Strength of the round function does not imply strength of the key schedule; check them separately.

How to exploit

1. Cheap diagnostic first, before modeling anything. Fix a plaintext, flip one key bit at a time, and look for structure in how the ciphertext changes across the two keys:

``python # probe: does flipping key bits move ciphertext predictably? def related_probe(enc, key, P): base = enc(P, key) for i in range(len(key) * 8): k2 = bytearray(key); k2[i // 8] ^= 1 << (i % 8) yield i, base, enc(P, bytes(k2)) # look for structure `` If a single key-bit flip produces a very localized or deterministic ciphertext delta, the schedule has weak diffusion and it's worth investing in the full attack. If flips scatter unpredictably across the whole ciphertext, stop here — the schedule is doing its job.

2. Model the key-schedule difference. Compute, symbolically or by hand for a few rounds, how a chosen Δ in the master key maps to per-round subkey differences. You are looking for a Δ that *cancels* diffusion in later rounds rather than spreading it — i.e. a low-weight difference path through the schedule. This is a search problem in its own right: for AES-256, the best known related-key differential path holds the schedule to only 9 active bytes over the first four expansion rounds, achieved by starting from a single-byte difference in one specific key byte — that's the scale of "good" you're hunting for in a real cipher.

3. Run the related-key differential. With a good Δ in hand, collect (P, C) pairs across the two keys and filter on the *predicted* output difference, exactly like ordinary differential cryptanalysis but with the extra lever of a known key difference instead of (or in addition to) a chosen plaintext difference. Surviving pairs leak master-key bits. See Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes for the filtering/counting machinery — it's the same machinery, applied to a key-difference path instead of a plaintext-difference path.

4. If the schedule is linear over GF(2) — common in home-rolled or "simplified for the CTF" ciphers — skip the differential search entirely: write the subkey relations induced by Δ as a linear system and solve directly with Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2. This is strictly cheaper than differential path-search when it's available; check for it before reaching for step 2.

5. If the relationship instead repeats every round (not a one-off Δ between two keys, but a periodic structure in how subkeys are generated), or the round function itself repeats identically across rounds, pivot to Slide Attack — breaking a cipher's key schedule, not its rounds — it doesn't need Δ to be small or the diffusion analysis of step 2 at all, only that the round function repeats.

What does NOT work

- Confusing this with plain differential cryptanalysis under one fixed key. Varying the plaintext under the same key tells you about the *round function's* diffusion, not the *key schedule's*. A related-key attack specifically needs the difference to enter through the key. If the oracle only gives you related messages under one key, that's Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes, not this — don't burn queries testing the wrong mechanism. - Assuming a strong round function implies a strong key schedule. It doesn't. Full AES-256's round function is unbroken, but its key schedule is thin enough (only 7 expansion rounds carrying a 256-bit key across 14 cipher rounds) that a good differential path exists with as few as 9 active bytes over the first 4 rounds. The lesson generalizes: audit the schedule on its own, independent of how good the cipher "feels." - Expecting a fast key from this against a real, unmodified strong cipher in a CTF. Even the best full-AES-256 related-key results remain of theoretical interest only — the query/time cost is far beyond practical exploitation, and they do not threaten real deployments. In a CTF, this technique pays off against *home-rolled or weakened* key schedules, or against *protocol-level* related-key exposure (WEP-style key derivation from a known/attacker-influenced value) — not against a textbook-strength primitive used correctly. - Blind delta search. Don't scan candidate Δ values without first checking, even roughly, where the schedule's diffusion can be made to cancel. Undirected search over deltas on a real cipher is expensive and usually the wrong first move; the bit-flip probe above exists precisely to tell you fast whether a good Δ is even plausible before you invest in path modeling.

Related

Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes Slide Attack — breaking a cipher's key schedule, not its rounds Weak Key Classes — when a cipher's own key schedule betrays it