Cryptanalysis and Security Proofs Questions

Direct answer

Recover the last round's subkey bits by building a differential characteristic (a predicted sequence of XOR differences between two plaintexts as they propagate round by round) over the first rounds of the cipher using the S-box's (substitution box, the nonlinear lookup table each round applies) difference distribution table, encrypting many chosen plaintext pairs that start at the fixed input difference, guessing the final round's subkey, partially decrypting, and keeping only the subkey guesses whose partial decryption reproduces the predicted difference far more often than chance.

Structured elaboration

1. Build the difference distribution table (DDT). For an $n$-bit S-box, the DDT entry $\mathrm{DDT}[\Delta_{in}][\Delta_{out}]$ counts, over all $2^n$ inputs $x$, how many satisfy $S(x) \oplus S(x \oplus \Delta_{in}) = \Delta_{out}$. Dividing by $2^n$ gives the probability that input difference $\Delta_{in}$ produces output difference $\Delta_{out}$. Pick the $(\Delta_{in}, \Delta_{out})$ pair with the highest nonzero probability; that is your one-round differential.
2. Chain a characteristic across rounds. In a Feistel network the round update is $(L,R) \to (R,\, L \oplus F(R,K))$, so a difference $(\Delta L, \Delta R)$ becomes $(\Delta R,\, \Delta L \oplus \delta)$ where $\delta$ is drawn from the DDT row indexed by $\Delta R$ (the difference entering $F$). Choosing the plaintext difference so that early rounds have a zero (or otherwise free, probability-1) input difference into $F$ lets you skip paying for those rounds, saving data.
3. Estimate chosen-plaintext pairs needed. If the multi-round characteristic you chained has probability $p$, you need on the order of $c/p$ chosen-plaintext pairs (for some small constant $c$ depending on the target confidence) so that "right pairs" (pairs that actually followed the characteristic) outnumber the statistical noise from wrong-key guesses by a visible margin.
4. Rank key candidates on the un-attacked round(s). Leave the last round's key-dependent step unresolved by the characteristic. For every candidate value of the last-round subkey, partially decrypt each ciphertext pair by that one round and check whether the resulting difference matches the characteristic's predicted intermediate difference. The correct subkey should show a count well above the random-guess baseline (expected count $\approx N/2^{\text{key bits}}$ for a wrong guess, versus $\approx N \cdot p$ for the right one); rank guesses by count and keep the top candidates.

Worked example

Executed on a scaled-down toy instantiation (8-bit block, two 4-bit halves, 4-bit round keys, a real 4-bit S-box) so the DDT and the full attack can be built and run directly; the strategy is identical at the 32-bit scale the question asks about, only the pair counts and key-guess space grow.

SBOX = [0xC,0x5,0x6,0xB,0x9,0x0,0xA,0xD,0x3,0xE,0xF,0x8,0x4,0x7,0x1,0x2]
def F(R, K): return SBOX[(R ^ K) & 0xF]
def encrypt(L, R, keys):
    for K in keys:
        L, R = R, L ^ F(R, K)
    return L, R
def build_ddt():
    ddt = [[0]*16 for _ in range(16)]
    for x in range(16):
        for dx in range(16):
            ddt[dx][SBOX[x] ^ SBOX[x ^ dx]] += 1
    return ddt

ddt = build_ddt()
dx, dy, cnt = max(((a,b,ddt[a][b]) for a in range(1,16) for b in range(16)), key=lambda t: t[2])
p = cnt / 16
DL0, DR0 = dx, 0                 # round 1 input diff to F is 0 -> free, prob 1
DL2, DR2 = DL0, dy               # 2-round characteristic, prob p

import random
random.seed(1234)
K1, K2, K3 = random.randrange(16), random.randrange(16), random.randrange(16)
true_keys = (K1, K2, K3)

def one_round_dec(L, R, K):
    Rprev = L
    Lprev = R ^ F(Rprev, K)
    return Lprev, Rprev

N_PAIRS = 4000
counts = [0]*16
for _ in range(N_PAIRS):
    L, R = random.randrange(16), random.randrange(16)
    C1 = encrypt(L, R, true_keys)
    C2 = encrypt(L ^ DL0, R ^ DR0, true_keys)
    for guess in range(16):
        A = one_round_dec(*C1, guess)
        B = one_round_dec(*C2, guess)
        if (A[0]^B[0], A[1]^B[1]) == (DL2, DR2):
            counts[guess] += 1

ranked = sorted(range(16), key=lambda k: -counts[k])
print("best diff dx=%X->dy=%X p=%.3f" % (dx, dy, p))
print("true K3 =", hex(K3), "top guesses:", [(hex(k), counts[k]) for k in ranked[:3]])

Output:

best diff dx=1->dy=3 p=0.250
true K3 = 0x0 top guesses: [('0x0', 994), ('0x3', 994), ('0x1', 248)]

With 4000 chosen-plaintext pairs and a 2-round characteristic of probability $p=0.25$, the correct subkey candidate's vote count (994) is roughly $4000 \times 0.25$, far above the wrong-guess baseline of $4000/16 = 250$, exactly as the estimate in step 3 predicts.

Trade-offs and pitfalls

The top-scoring candidate above is actually tied between two subkey values (0x0 and 0x3), not unique. This is a genuine and common phenomenon: a single characteristic often leaves a residual ambiguity from symmetries in how the S-box's difference structure interacts with the last-round guess, so it narrows the key space without fully determining it. Rerunning the attack with a second, independent input difference and intersecting the two candidate sets resolves it to the unique correct key here. More generally: the estimate in step 3 assumes rounds behave independently (the "Markov cipher" assumption), which real ciphers only approximate; a characteristic with too low a probability (below roughly $2^{-n}$ for an $n$-bit block) needs more data than a full codebook, making brute force cheaper; and picking the single best characteristic ignores that many characteristics sharing the same input/output difference (a "differential" rather than one "characteristic") can sum to a higher effective probability than any one of them, which is why serious differential cryptanalysis tracks clusters of characteristics, not just the top one.

Direct answer

IND-CPA (indistinguishability under chosen-plaintext attack, the standard security notion meaning an adversary who can request encryptions of chosen messages still cannot tell which of two messages a target ciphertext encrypts) composes well under both sequential and parallel use, PROVIDED each instance uses an independent key and independent randomness. A hybrid-argument reduction shows that breaking the composed system implies breaking at least one individual instance, with the composed scheme's advantage (a numeric measure of how much better than random guessing an attacker does) bounded by roughly the SUM of the individual instances' advantages, not their product, so composing n instances costs at most an n-fold loosening of the bound, not a broken guarantee. That guarantee silently disappears, however, the moment the components share key material, share a randomness source, or leak information about each other through a side channel.

Structured elaboration

Sequential composition: chaining one primitive's output into another generally preserves security if each stage is independently secure and independently keyed, proven by a hybrid argument: swap one stage at a time from real to simulated, and bound the total distinguishing advantage as the sum of per-stage swap advantages.

Parallel composition, the concrete example: take two IND-CPA schemes (Enc1, Key1) and (Enc2, Key2), used in parallel to encrypt a two-part message (m1, m2) as (c1, c2) = (Enc1_Key1(m1), Enc2_Key2(m2)). The proof uses a hybrid reduction with three worlds: (real c1, real c2), (real c1, random-looking c2), (random-looking c1, random-looking c2). An adversary distinguishing the combined system from fully random ciphertexts must distinguish at least one adjacent pair of hybrids, and distinguishing that pair reduces directly to breaking IND-CPA of whichever ONE scheme changed between those two hybrids (the reduction forwards the adversary's queries for the unchanged component using its own oracle access, and answers the changed component's queries using its own IND-CPA challenge). This gives:

a standard hybrid-argument bound: total advantage is bounded by the sum of the per-component advantages, each hop in the hybrid chain contributing at most that component's own best possible distinguishing advantage. Composing n independently keyed components costs at most an n-fold loosening of the advantage bound, typically translating to losing about log2(n) bits of security margin, a modest, well-quantified cost, not an open-ended risk.

Subtle issues the theorem does NOT cover, exactly what the question asks to identify:

1. Shared randomness: if both encryption calls internally derive their randomness from a single shared source, for example one PRNG stream reused or insufficiently re-seeded between the two calls, the reduction's step of answering the unchanged component using independent oracle access breaks, because the components are no longer actually independent. This is the same failure mode behind real nonce or IV reuse bugs when two logically separate encryption operations accidentally draw from the same underlying randomness pool.
2. Correlated keys: if Key2 is derived FROM Key1, or both derive from a common master secret without proper independent key derivation (a KDF, key derivation function, with distinct, domain-separated labels per component), the reduction can no longer treat "swap component 2 to random" as independent of component 1's behavior. An adversary who learns something about Key1, through a side channel, partial compromise, or the ciphertext itself, may learn something about Key2 too, breaking the sum bound's underlying independence assumption entirely; the theorem simply does not apply once keys are correlated, and no generic bound is provided.
3. Cross-component information leakage: even with independent keys and randomness, if the two plaintexts m1 and m2 are not actually independent (for example m2 is computable from m1, or a secret is split unsafely across both), an adversary attacking the composed system may combine partial information leaked from each ciphertext in a way neither component's individual IND-CPA guarantee anticipated. IND-CPA only promises indistinguishability of each ciphertext given the ADVERSARY'S CHOSEN messages; it says nothing about what happens when the plaintexts are correlated by the system's own design.

Worked example

If Adv1 <= 2^(-40) and Adv2 <= 2^(-40) individually, two well-designed, properly and independently keyed IND-CPA schemes each with a comfortable margin:

exactly one bit of security margin lost from correctly parallel-composing two such schemes, a small, well-quantified, fully expected cost. Contrast this with what an UNQUANTIFIED shared-randomness or correlated-key bug could cause: a potentially total, catastrophic loss of security with no bound at all, since the composition theorem simply does not cover that case.

Trade-offs and pitfalls

The most common wrong turn is treating "each component is individually provably IND-CPA-secure" as automatically meaning the composed system is exactly as secure; the sum-bound theorem gives a quantified, generally small extra cost, not a free guarantee, and it comes with load-bearing independence assumptions (separate keys, separate randomness, no cross-plaintext correlation) that real systems violate more often than engineers expect, especially the shared-randomness case, reusing a PRNG stream or an IV/nonce generator across logically separate crypto operations remains one of the most common real-world implementation bugs. The fix is always the same: enforce genuinely independent key derivation, with a KDF using distinct labels per component, and genuinely independent randomness per component; only then is the clean sum-bound theorem the guarantee you actually get.

Direct answer

Using EasyCrypt: model the hybrid scheme (a key encapsulation mechanism, KEM, that establishes a shared key, composed with a symmetric data-encapsulation mechanism, DEM, that uses it) as separate probabilistic modules with an encryption oracle answering a left-right challenge and a decryption oracle that refuses the challenge ciphertext, then prove IND-CCA (indistinguishability under chosen-ciphertext attack) via a chain of game-hop equivalences that reduce the real game to one where the derived symmetric key is statistically independent of everything the adversary sees, bottoming out in the KEM's own hardness assumption and the DEM's authenticated-encryption security.

Structured elaboration

• Modeling choices. The two oracles the adversary gets are an encryption oracle (returns a hybrid ciphertext for one of two adversary-chosen messages depending on a hidden bit $b$) and a decryption oracle (answers any ciphertext except the literal challenge). If the KEM derives its key via a hash, that hash is modeled as a programmable random oracle (RO, an idealised public function the reduction controls) module; each of these pieces is a separate EasyCrypt module so a game hop can swap out one module's behavior (say, replacing "real KEM key" with "uniformly random key") while leaving the rest of the game's code untouched.
• Lemmas needing manual proof. The step that swaps the derived symmetric key for a uniformly random one is where the actual KEM hardness assumption gets invoked, and that step is not auto-discharged: it requires an explicit reduction lemma constructing a KEM-breaking adversary from any distinguisher between the two games, proved by hand. Bounding the probability that the decryption oracle ever needs to answer a query touching an unprogrammed (not-yet-fixed) random-oracle point in a way that would reveal the switch also needs a manual "bad event" bound, the same abort-probability bookkeeping that shows up in any random-oracle-model (ROM) proof with an adaptive decryption oracle. The DEM's own authenticated-encryption unforgeability (bounding the probability a forged ciphertext is accepted) is likewise proved as its own reduction, not derived automatically from the game syntax.
• Representing probabilistic advantage bounds. Each game hop contributes an explicit term (a KEM-breaking advantage, a DEM-forgery probability, a random-oracle collision probability), and the final theorem states the overall IND-CCA advantage as the sum of those terms, mirroring exactly the "telescoping sum of adjacent-game distances" structure a hand-written concrete-security proof uses on paper.
• Common obstacles. Keeping the programmed random oracle consistent with "lazy sampling" (only fixing an output the first time it's actually queried, in any order the adversary chooses) while the decryption oracle might implicitly probe the same input is the single trickiest recurring issue, because an adaptive decryption query can indirectly ask "was this random-oracle point already fixed?" without the adversary ever querying it directly, and the game hops have to account for that indirect leakage explicitly.

Worked example

Concretely, the telescoping bound looks like

where each term on the right is exactly the probability bound proved by one of the manual lemmas above, and the left side is what the final EasyCrypt theorem statement exports. Nothing here is a single automated tactic call end to end; each summand is its own lemma, connected by the game-hop chain.

Trade-offs and pitfalls

The dominant practical cost is proof-engineering effort, not any single hard step: each additional game hop in the hybrid argument is its own block of manual EasyCrypt tactics, and a moderately involved hybrid encryption scheme can require hundreds to low thousands of lines of proof script even though the paper proof it mirrors might be a page of prose. The place this gets genuinely hard, beyond routine bookkeeping, is exactly where the reduction stops being "swap a distribution" and starts needing non-black-box algebraic reasoning about the KEM's underlying group structure; EasyCrypt reasons well about probabilistic program equivalence, but an algebraic argument (for instance, one requiring the algebraic group model) has to be encoded by hand as an additional hypothesis, not discovered by the tool.

Direct answer

Deterministic signature schemes (where signing the same message twice always produces the exact same signature) need extra care in an unforgeability proof because the reduction cannot embed independent fresh randomness into each simulated signature the way it might for a randomized scheme; a simulated signing oracle for a deterministic scheme has to behave exactly like a random oracle: an idealized hash function that a security proof is allowed to treat as returning an independent, uniformly random output for every new input, but always returning that same output again if the exact same input is queried a second time, so its answers must be consistent and fixed once queried. Determinism also raises a distinct concern, strong unforgeability, since even a scheme with a single canonical signature per message can still have a verification equation that accepts more than one valid signature string for that same message, which existential unforgeability under chosen-message attack (EUF-CMA) does not rule out.

Structured elaboration

Why the proof needs care. Many textbook unforgeability proofs for randomized schemes lean on being able to program a fresh, independent random value into each signing-oracle response. A deterministic scheme forbids that outright: the same queried message must always receive the same simulated signature, exactly the consistency requirement a random oracle itself has to satisfy. In practice this pushes deterministic-signature proofs toward random-oracle-style bookkeeping, deriving the "randomness" a construction needs deterministically from the message (and the secret key) via a pseudorandom function or the random oracle itself, so the simulator can still program a consistent answer without introducing genuine fresh randomness anywhere the reduction cannot control.

Existential versus strong unforgeability. Ordinary EUF-CMA only requires that the adversary cannot produce a valid signature on a message it never asked the signing oracle to sign; strong unforgeability (sUF-CMA) additionally requires that the adversary cannot produce a new, different valid signature for a message it already saw signed. For a genuinely deterministic scheme, where signing is a fixed function with exactly one output per message, a second valid signature on an already-signed message would seem impossible by construction, but this is only true if the verification algorithm is also injective in the signature for a fixed message; if verification instead accepts more than one distinct signature string as valid for the same message, strong unforgeability fails even though the signing algorithm itself never produces more than one of them.

A concrete replay concern: ECDSA-style malleability. The elliptic-curve digital signature algorithm (ECDSA) has exactly this shape: its verification equation is symmetric under negating the signature's second component modulo the group order, so both $(r, s)$ and $(r, n - s)$ verify as valid for the same message under the same public key, even though the deterministic signing procedure only ever outputs one of the two. This is a pure public malleability of the verification equation, requiring no secret key material to exploit, and it does nothing to break ordinary EUF-CMA (no new message gets forged) while completely breaking strong unforgeability. Systems that treat the signature bytes themselves as a unique identifier (blockchain transaction identifiers computed by hashing the signed transaction, including its signature, are the best-known real example) are directly vulnerable to this gap, which is why some deployed systems added an explicit canonical-form rule (accepting only the numerically smaller of $s$ and $n - s$) specifically to close it.

A reduction from forgery to collision-resistance or one-wayness. For a deterministic hash-then-invert scheme built on a trapdoor one-way permutation (the full-domain-hash construction, proven in the random oracle model by Bellare and Rogaway), the reduction programs the random oracle so that each legitimate signing query on message $m_i$ is answered by first choosing a value $y_i$ the reduction can invert (because it chose it), setting the oracle's output for $m_i$ to be $y_i$ run forward through the public trapdoor permutation, and returning $y_i$ itself as the signature; for one designated message the reduction instead plants its own one-wayness challenge as the oracle's output. A forgery on that designated message directly inverts the challenge, breaking one-wayness; determinism is not an obstacle to this technique, it is the native case the technique was designed for. If instead the scheme first hashes the message with an ordinary, non-random-oracle collision-resistant hash before a deterministic core signing step, then a forgery on two distinct messages that happen to hash to the same digest trivially reuses the same signature for both, so proving unforgeability for that construction requires the outer hash to be collision-resistant as a genuinely necessary assumption, not merely a convenient one.

Worked example

The $(r,s)$ versus $(r, n-s)$ malleability can be traced with small toy numbers reflecting the same algebraic symmetry: take a toy modulus $n = 17$ and a toy signature value $s_0 = 5$; $s_0^2 \bmod 17 = 8$. Its symmetric partner is $s_1 = n - s_0 = 12$, and indeed $s_1^2 \bmod 17 = 144 \bmod 17 = 8$, the same value: both $s_0 = 5$ and $s_1 = 12$ satisfy the same verification relation modulo 17, exactly the small-scale version of the $(r,s)$ and $(r, n-s)$ symmetry that makes ECDSA malleable, on numbers small enough to verify by hand.

Trade-offs and pitfalls

Treating strong unforgeability as an academic nicety once ordinary EUF-CMA is proven is a real, consequential mistake whenever anything downstream depends on the signature bytes being unique per message, not merely on the message itself being unforgeable; transaction-malleability incidents in deployed systems are the direct, practical consequence of exactly this gap. Deterministic construction and strong unforgeability are also easy to conflate in the wrong direction: determinism of the signing algorithm does not automatically grant strong unforgeability, since the verification algorithm, not the signing algorithm, is what ultimately decides whether a second valid signature string exists for an already-signed message.

Direct answer

Algebraic cryptanalysis models a cipher's components (substitution boxes, linear mixing layers, and linear feedback shift registers, or LFSRs) as a system of polynomial equations over the binary field GF(2), then tries to solve that system for the secret key or state using SAT solvers, Groebner-basis algorithms, or the XL (extended linearization) technique. A primitive is vulnerable to this style of attack to the extent its nonlinear components can be described by relatively few, relatively low-degree equations relative to its state size.

Structured elaboration

Modeling each component. A linear mixing layer or a bit permutation is trivially linear over GF(2) and contributes only degree-one equations. An LFSR's state evolves by a fixed linear recurrence, so every state bit at any later time step is itself a linear function of the initial state bits. The nonlinear component (an S-box, or a nonlinear Boolean function combining several LFSR outputs) is where the interesting modeling work happens: some S-boxes admit a surprisingly compact algebraic description, the most famous example being the AES S-box, which satisfies 39 independent quadratic equations relating its 8 input bits and 8 output bits, despite being constructed from an inversion operation over a larger field composed with an affine map.

Solving techniques. Plain linearization treats every distinct monomial appearing in the system as an independent new unknown and solves the resulting linear system directly. XL systematically multiplies the original equations by extra monomials before linearizing, trying to generate enough genuinely new linear relations without needing as many original equations. Groebner-basis algorithms (in practice, F4 and F5) compute a canonical generating set for the polynomial system adaptively, generally outperforming XL on many real systems, though with a worst-case cost governed by the system's degree of regularity (informally, the highest total degree the elimination process actually has to reach before the equations collapse into a directly solvable linear system: a low degree of regularity keeps Groebner-basis elimination cheap, and a high one means it must climb close to the same combinatorial blow-up that plain linearization hits at that degree). SAT solvers convert the whole system into Boolean satisfiability and hand it to a modern solver, which is often effective for cipher structures with a lot of exploitable internal regularity even when the raw monomial count would make algebraic linearization infeasible.

What makes a primitive vulnerable. Low algebraic degree in the nonlinear component, or more precisely low algebraic immunity (the smallest degree at which the function, or any function closely related to it by a simple algebraic relation, becomes low-degree); a small total state size, which directly caps how large the monomial count can possibly get; an over-determined system, meaning there are substantially more low-degree equations available than there are unknowns, which happens when a component (like the AES S-box) satisfies unusually many independent low-degree relations for its size; and a linear or near-linear internal state structure, such as an LFSR, which lets an attacker convert what would otherwise be a large exhaustive-search problem into a large but highly structured linear-algebra problem instead.

Worked example

The AES S-box's 39 quadratic equations are the standard illustration of "unusually compact algebraic structure" in a widely deployed primitive: despite that compactness, no practical full-AES algebraic break exists, because the attack's real bottleneck is not the individual S-box's equation count but how those equations chain together across the cipher's many rounds, which is governed by the degree of regularity of the full multi-round system, not by any single component's own description.

Trade-offs and pitfalls

The most common conceptual error is treating "this component has a compact algebraic description" as equivalent to "the cipher is broken by algebraic attack"; a compact single-component description is necessary groundwork, not sufficient, and the full-system degree of regularity across all rounds is what actually determines feasibility. Algebraic attacks are also a known-keystream or known-plaintext class of attack, requiring the attacker to actually observe enough cipher output to build the equation system in the first place, and they are best understood as a design-time evaluation tool (choose components with high algebraic immunity, avoid unnecessarily compact algebraic structure where a different construction is available) rather than as a practical break against any well-vetted, full-round modern cipher.