Cryptanalysis and Security Proofs Questions

Definition — Shannon entropy

H(X) = - sum_x P(X=x) * log2 P(X=x)

Plain English: average unpredictability per sample; measures mean information content.

Definition — Min-entropy

H_min(X) = - log2( max_x P(X=x) )

Plain English: measures the worst-case predictability (the highest single-symbol probability).

Which is most relevant for cryptographic keys and why

• Min-entropy is the critical metric for key material because it bounds the adversary’s success guessing the most likely value. Cryptographic security reductions (e.g., extractor/PRF analyses) use min-entropy to guarantee unpredictability even in worst-case distributions. Shannon entropy can be high while one value is very likely, so it’s insufficient alone.

Practical tests/checks for hardware RNGs

• Formal min-entropy estimation per NIST SP 800-90B (IID and non-IID estimators).
• Statistical suites: NIST STS, Dieharder, TestU01 (for gross failures, not a substitute for entropy estimates).
• Bias and frequency tests, autocorrelation, run-length, serial correlation.
• Health/online tests: repetition count test, adaptive proportion, continuous RNG health checks.
• Environmental checks: sensor plausibility, supply-voltage & temperature monitoring.
• Entropy source modeling and threat analysis; use conditioning (CSPRNG) and conservative entropy accounting; periodic re-seeding and fail-stop on anomaly.

Brief overview

Game-hopping (hybrid argument) proves security by defining a sequence of games G0,...,Gk from the real to ideal. If each adjacent pair is indistinguishable, the endpoints are indistinguishable.

Constructing the sequence

• Start with G0 = real protocol, Gk = ideal/desired simplified game.
• Change one small, analyzable component per hop (e.g., replace PRF with random function, change plaintext to zero, abort condition).
• Keep changes localized so you can bound advantage differences.

Valid hop

A hop Gi -> Gi+1 is valid if you can give a reduction or coupling showing any adversary A distinguishing them implies solving a hard problem or breaking a primitive. Typically you build a simulator B that uses A to break the primitive; advantage transfers.

Bounding advantage change

Use triangle inequality over advantages:

Adv_A(G0,Gk) <= sum_{i=0}^{k-1} Adv_A(Gi,Gi+1)

Intuition: total distinguishing advantage is at most sum of per-hop gaps. For each hop, show

Adv_A(Gi,Gi+1) <= Adv_B(primitive) + eps

where eps is a negligible collision or abort probability.

Short example

G0: Encryption uses PRF F_k to derive nonce r = F_k(s).
G1: Replace F_k with truly random function R. Reduction: any A distinguishing gives PRF distinguisher B, so

Adv_A(G0,G1) <= Adv_B(PRF)

G2: Further replace r with uniform random independent of s (removing dependence); bound difference by collision prob eps. Then

Adv_A(G0,G2) <= Adv_B(PRF) + eps

This is a standard hybrid: make atomic, provable changes and sum per-hop bounds.

High-level goal
Show IND-CCA under concurrent composition by giving a reduction R that, given any adaptive adversary A that interleaves many sessions, uses A to break a single-session IND-CCA challenger while simulating all other functionality consistently.

Modeling choices for concurrency

• Model sessions as labeled by unique session IDs and ordered message transcripts; allow adversary to schedule message delivery and oracle queries adaptively.
• Specify ideal oracles: encryption, decryption (CCA), key-generation, and any subprotocols (e.g., proofs). Distinguish global or per-session state (e.g., keys).
• Work in either the random-oracle model (where programmability helps) or the standard model (need stronger building blocks: non-malleable, extractable components).

Simulation / embedding strategy

• Use hybrid/partitioning: pick at most one target session where R forwards the IND-CCA challenge to the external challenger; all other sessions are simulated internally.
• Ensure non-conflicting embeddings by:
  • Tagging ciphertexts with session IDs or ciphertext formats so R can recognize which ciphertexts belong to the real-challenge session.
  • If scheme uses randomness that can be programmed (RO), program the oracle so challenge ciphertexts are consistent across interleavings.
  • For decryption queries, forward those that reference the real-challenge ciphertext to the external decryption oracle; answer others using R's secret key(s) or simulation trapdoors.
• If simulation requires rewinding (e.g., to extract secrets in zero-knowledge), use extractable or straight-line simulation primitives; otherwise rewinding may fail under concurrency.

Bounding advantage across interleavings

• Use a hybrid argument over sessions and events: progressively replace simulated sessions with real ones; each hybrid change increases adversary advantage by at most the reduction loss.
• If there are N sessions and Q oracle queries, show advantage(A) ≤ N * adv_single + negligible(λ), where adv_single is the reduction's success bound. Improve constants by grouping sessions or using session tags to make embeddings orthogonal.
• When using programmability (RO), loss often scales with number of programmed points (poly Q), so account for that in the bound.

When concurrency breaks security (risks & required protocol features)

• Malleable ciphertext formats: an adversary can transform a ciphertext from one session to another, violating indistinguishability across interleavings.
• Lack of session binding (no session IDs/tags): simulations collide, making challenge recognition impossible.
• Decryption oracles that leak partial plaintexts or accept malformed ciphertexts allow cross-session attacks.
• Proofs that are not concurrently zero-knowledge or extractable force rewinding-based simulations to fail.
• Reuse of randomness or keys across sessions enables linking and distinguishing.

Takeaway / design prescriptions

• Use session tags and authenticated ciphertext formats (plaintext-awareness or strong non-malleability).
• Employ concurrent zero-knowledge/extractable proofs when simulator needs extraction.
• Prefer schemes with straight-line simulators or work in the RO model with careful programming to handle many sessions.
• In the reduction, carefully count sessions and oracle queries to bound advantage multiplicatively; explicit session isolation and non-malleability avoid blow-up.

Overview / goal
I would mount a chosen-plaintext differential attack to recover bits of the round keys by (1) selecting high-probability input differences, (2) composing a 3-round differential characteristic, (3) collecting chosen plaintext pairs, and (4) using partial decryption to filter and rank subkey candidates.

1) Select input differences

• Use the S-box differential table to pick small-weight differences that activate few S-boxes in the round function (e.g., single 4-bit S-box differences if the 32-bit round function is 8×4-bit).
• Choose ΔP = (ΔL0, ΔR0) so the first-round input to S-boxes yields t1 active S-boxes with high per-S-box DP. This maximizes characteristic probability.

2) Build characteristics across 3 rounds

• For Feistel: after round i, L_{i} = R_{i-1}, R_{i} = L_{i-1} ⊕ F(R_{i-1}, K_i).
• Compose a specific characteristic Δ through rounds 1→3 using the S-box DPs: for each round j count active S-boxes t_j and per-round probability P_j = (p_s)^{t_j} (use exact per-differential probabilities if available).
• Overall characteristic probability:

P_char = P_1 * P_2 * P_3

(put exact per-S-box probabilities from table into each P_j).

3) Estimate number of chosen plaintext pairs

• Expected surviving pairs ~ N * P_char. To get M useful survivors (e.g., M≈50–200 for reliable statistics) choose

N ≈ M / P_char

• Use a safety margin (×5–10) because of approximations and wrong-key noise.

4) Data collection

• Generate N plaintext pairs (P, P ⊕ ΔP) under chosen-plaintext model, encrypt, and store ciphertext pairs.

5) Partial decryption / key guessing and ranking

• Focus on recovering bits of K3 (and optionally K2) because last round partial decryption is cheap:

  • For each ciphertext pair (C, C'), compute the difference at the inputs of the last round F by reversing permutation of Feistel (partial decrypt one round): derive candidate differences for F-inputs.
  • For each small-group subkey (e.g., per affected S-box or small subkey nibble), iterate over all 2^k possibilities (k typically 4 or 8). For a guessed subkey, partially decrypt the corresponding S-box inputs for both ciphertexts and check whether the resulting input difference to the S-box matches the expected Δ_in from the characteristic.
  • Increment a counter for that subkey guess when it matches. Repeat over all pairs.

• Ranking: sort subkey guesses by counts; correct key(s) should produce significantly higher counts.

• Use log-likelihood or chi-square to combine evidence across S-boxes if guessing multi-nibble subkeys.

6) Complexity and practical notes

• Data complexity: N ≈ M / P_char (plug numeric P_char).
• Time complexity: roughly N * sum(2^{k_i}) where k_i are sizes of independent subkey groups guessed; can be parallelized and done per S-box nibble to reduce cost.
• Verify top candidates by full-key test (decrypt some new pairs).

Edge cases and tradeoffs

• If P_char extremely small, use higher-round truncated differentials or attack K2 via meet-in-the-middle combining guesses for K3 and K2.
• If S-boxes are large or highly nonlinear, group-bit guessing may need to expand (higher per-guess cost).

This strategy balances data vs. computation: choose characteristics with highest P_char (few active S-boxes) to minimize chosen-plaintext pairs, then exploit partial decryption per S-box to keep key-guess complexity manageable.

Answer (DFA on AES with single‑bit fault before last round)

Situation and approach

• Injecting a single‑bit flip into the 16‑byte state just before AES’s final round yields one correct ciphertext c and one faulty ciphertext c'. The attacker knows c,c' and wants each last‑round key byte k_i.
• For a given byte i, let y = InvSubByte(c_i ⊕ k_i) and y' = InvSubByte(c'_i ⊕ k_i). A single‑bit fault in the state before the last SubBytes + ShiftRows produces a sparse, low‑weight Δy = y ⊕ y' whose pattern depends on k_i. Brute‑force all 256 k_i and keep those producing a single‑bit (or expected low‑weight) Δy; the correct k_i typically survives while most wrong keys are eliminated.

Derivation of expected encryptions

• Let p be probability a given encryption suffers a useful single‑bit fault at (or mapped to) the target byte. For each encryption attempt we get a usable pair with prob p.
• Let s be the expected number of key candidates that survive checking one usable pair (empirically s is a small constant ≈1–4 depending on exact test). To uniquely identify k_i we need on average about s survivors reduced to 1, so roughly O(s) independent usable pairs.
• Expected number of encryptions E[N] = (expected usable pairs required) / p ≈ C / p, where C ≈ s (commonly near 1–4). So E[N] = Θ(1/p). More explicitly, if r usable pairs are required to reduce to single candidate, E[N] = r / p.

Practical constraints

• Fault locality: real hardware may not let you target a single byte; faults may affect multiple bytes or rounds, reducing elimination power.
• Fault reproducibility & timing: you need precise timing to flip the bit immediately before last round; jitter reduces p.
• Detection & classification: differentiating single‑bit faults from multi‑bit noise requires filtering; misclassified pairs increase s.
• Countermeasures: masking, redundancy, and fault detection (e.g., error flags) can invalidate or detect injected faults.
• Implementation variance: S‑box properties and ShiftRows diffusion mean some bit flips in state before last round don’t map to single‑byte low‑weight Δy at ciphertext — reduces effective p.

Takeaway

• DFA with single‑bit pre‑last‑round faults recovers last‑round key bytes with expected encryptions proportional to 1/p (constant factor small). Real attacks hinge on raising p, isolating single‑byte faults, and reliably classifying useful faulty outputs.