Cryptanalysis and Security Evaluation Questions

Comprehensive expertise in analyzing and evaluating the security of cryptographic primitives and protocols. Candidates should understand a broad set of cryptanalytic methods including differential cryptanalysis, linear cryptanalysis, algebraic attacks, index calculus methods, Pollard rho algorithms, meet in the middle attacks, birthday paradox and collision finding for hash functions, brute force and key space reasoning, and related statistical and algebraic techniques. Knowledge of practical exploit classes such as side channel attacks including timing analysis, power analysis and cache attacks, fault injection, and protocol level attack vectors is required. Candidates must be able to estimate attack complexity in time and memory, reason about time and memory trade offs, convert theoretical attacks into practical threat models, and assess attack cost and feasibility. They should understand how security parameters such as key length, round count and security margin affect resistance, be able to identify relevant attacks for a given construction, and propose mitigations and design choices to harden primitives and protocols. Foundational mathematical skills such as modular arithmetic, prime factorization and discrete logarithm reasoning, along with randomness and entropy assessment, are expected. Interviewers may probe applied problem solving with puzzles, worked examples and complexity estimates to evaluate analytical and mathematical thinking in cryptography.

HardTechnical

48 practiced

Analyze how Grover's algorithm impacts symmetric-key search and how meet-in-the-middle (MITM) style attacks interact with quantum speedups. For single-key size k describe classical and quantum brute-force costs, for double-encryption with two k-bit keys compare classical MITM cost to naive quantum search and discuss recommended key sizes to achieve an equivalent 128-bit security margin against quantum adversaries.

Sample Answer

**Summary of effects**

- Grover gives a quadratic speedup for unstructured search: a classical 2^{n} search becomes ≈2^{n/2} quantum.- Meet-in-the-middle (MITM) is a structural (time–memory) trade that classically reduces double-key search from 2^{2k} to about 2^{k+1} time with ≈2^{k} memory. Quantum Grover and quantum MITM interact: naive Grover over the 2^{2k} space costs 2^{k} (square root), so asymptotically similar to classical MITM time; specialized quantum algorithms for composition can change constants but do not restore full classical security.

Single-key (k bits)- Classical brute force: time ≈ 2^{k}.- Quantum (Grover): time ≈ 2^{k/2}, memory small.Formula:

text

Classical time  = 2^{k}
Quantum time     ≈ 2^{k/2}

Double-encryption (two independent k-bit keys, total 2k bits)- Classical naive: time 2^{2k}.- Classical MITM: time ≈ 2^{k+1}, memory ≈ 2^{k} (store all E_k1(P) and lookup).- Quantum naive (Grover over 2^{2k}): time ≈ 2^{k}, memory small.- Comparison: classical MITM (≈2^{k+1}) and quantum Grover (≈2^{k}) are the same order; thus double-encryption does not regain full 2k-bit security against quantum attackers. Quantum-aware MITM/quantum-walk techniques can shift constants but do not achieve exponential restoration.

Security-sizing for 128-bit quantum security- Single-key: require 2^{k/2} ≥ 2^{128} ⇒ k ≥ 256.- Double-encryption: choose k so that the best quantum attack cost ≥ 2^{128}. Naive Grover gives cost ≈ 2^{k} so require k ≥ 128. Classical MITM would need k ≥ 127 to give ~2^{128} cost classically, but quantum adversary can use Grover to reach 2^{k} so k ≥ 128 is necessary.Recommendation:- For single-key primitives: use k = 256 bits to retain 128-bit security against quantum search.- For double-encryption: use k ≥ 128 to ensure naive quantum Grover cost ≥2^{128}; for conservative margin (future quantum-MITM improvements and side-channel realism), prefer k = 256.

Practical note: prefer single-key ciphers with 256-bit keys (e.g., AES-256) rather than relying on composition to regain quantum security; composition can help classically but gives limited benefit against quantum adversaries.

HardTechnical

69 practiced

Given a small SPN cipher specified algebraically over GF(2) with small S-boxes, explain the steps to mount a Groebner-basis attack: generation of polynomial system, choice of variable ordering and monomial order, expected degree of regularity, and heuristics to reduce run-time. Provide a qualitative complexity estimate for toy parameters and discuss when Groebner attacks are impractical.

Sample Answer

**Overview / Goal**Describe how to mount a Gröbner-basis algebraic attack on a small SPN over GF(2): build the polynomial system modelling rounds and S‑boxes, choose orders to help elimination of key vars, estimate degree of regularity (dreg) and attack cost, and apply heuristics to reduce runtime.

**1) Generate polynomial system**- Model each AND/XOR as polynomials in GF(2). Represent XOR as linear equations x + y + z = 0 and S-box as a small multivariate polynomial ideal: either explicit ANF relations or a compact algebraic basis (e.g., algebraic normal form with multiplication relations).- Add key schedule constraints and known plaintext/ciphertext as equations.

**2) Variable / monomial ordering**- Use elimination-friendly orders: place key and internal state variables as elimination targets. A common choice: lex or block‑lex where public/input vars are higher than key vars so elimination yields key‑only relations.- For practical Gröbner computations pick graded reverse lex (grevlex) for F4/F5 engines to keep intermediate polynomials smaller, then convert (FGLM) to lex if elimination is required.

**3) Expected degree of regularity**- dreg often equals the first degree where number of linearly independent monomials ≥ number of equations; for random systems approximate by Macaulay bound. For SPN with t-bit S-boxes and nonlinear degree Δ (max monomial degree in S-box ANF), expect dreg ≈ O(#rounds * Δ) for small instances. In toy examples (4-bit S-box, 4 rounds) dreg typically 3–6.- Higher dreg implies combinatorial blowup in Macaulay matrices.

**4) Heuristics to reduce run-time**- Use S-box equation reduction: replace full ANF by small generating set of low-degree relations (e.g., linear plus a few quadratics) to reduce degree.- Introduce auxiliary variables to split high-degree monomials (Rewriting) to lower dreg at cost of more variables.- Add linear relations from known differential/linear properties to cut search space.- Solve subsystems (meet‑in‑the‑middle) and stitch with Gröbner only on remaining ambiguity.- Use symmetry breaking: fix some key bits and run multiple smaller Gröbner solves in parallel.- Preprocess with XL-like linearization to detect low-degree consequences before full Gröbner run.

**5) Complexity estimate (toy parameters)**- Cost dominated by Gaussian elimination on Macaulay matrix at degree dreg: roughly O( binom(n + dreg, dreg)^ω ) with ω≈2.7; n = #variables.- Example: n=80 vars, dreg=5 → monomials ≈ binom(85,5) ≈ 3.2×10^7; matrix operations are infeasible. For toy SPN: n=30, dreg=4 → binom(34,4)=46,376, matrix elimination feasible in minutes–hours depending on sparsity.

**6) When Gröbner attacks are impractical**- Large n and moderate-to-high dreg (≥6) produce astronomic Macaulay sizes; structured key schedules and high nonlinear degree S‑boxes raise dreg.- When S‑box algebraic immunity is high or when degree grows with rounds, attack becomes infeasible.- Also impractical if conversion to lex (for key extraction) is too costly; then hybrid or SAT/guess-and-determine approaches may be better.

**Takeaway**Gröbner attacks are powerful on small, low‑degree, poorly mixed SPNs; success depends on keeping dreg small via modeling choices and heuristics. For real-world ciphers with many variables or high dreg, cost explodes and alternative attacks are preferable.

EasyTechnical

47 practiced

Explain the birthday paradox and why generic collision search against an n-bit hash function requires about 2^{n/2} evaluations. Compute approximate expected work to find a collision for n=128 and n=256, and discuss practical implications for choosing hash output size in modern systems.

Sample Answer

**Brief explanation (birthday paradox applied to hashes)** The birthday paradox says collisions in a domain of size N become likely after about sqrt(N) random samples. For an n-bit hash, N = 2^n, so a generic collision search requires on the order of 2^{n/2} hash evaluations.

**Key formula (collision probability ≈ 1/2 at threshold k)**

text

p(coll) ≈ 1 - exp( - k*(k-1) / (2 * 2^n) )

Solving p ≈ 1/2 gives the rule-of-thumb

text

k ≈ 1.1774 * 2^{n/2}

Plain English: you need roughly 1.18×2^{n/2} hashes to get a 50% chance of any two outputs colliding.

**Numeric estimates**

- n = 128: - 2^{n/2} = 2^{64} ≈ 1.84 × 10^19 - k ≈ 1.1774 × 2^{64} ≈ 2.17 × 10^19 hash evaluations

- n = 256: - 2^{n/2} = 2^{128} ≈ 3.40 × 10^38 - k ≈ 1.1774 × 2^{128} ≈ 4.01 × 10^38 hash evaluations

**Practical implications for hash output size (cryptographer view)**

- Collision resistance goal: to achieve s-bit security against generic collision attacks, choose n ≈ 2s. For classical attackers, n=256 provides ~128-bit collision security; n=128 provides ~64-bit collision security (already borderline for high-value systems).- Long-term and high-value use: prefer 256-bit outputs (SHA-256/512/Keccak variants) to resist massive parallel/cloud attacks and future increases in attacker capability.- Quantum note: generic quantum algorithms (Grover) primarily weaken preimage to about 2^{n/2}; collision resistance against quantum adversaries is more nuanced but still motivates larger n for long-term security.- Engineering: larger digests increase bandwidth/storage; you can safely truncate only if analysis ensures remaining bits meet required security level and prevents domain separation errors.

Recommendation: for modern systems targeting 128-bit security, use 256-bit hash output (or larger) and avoid relying on 128-bit hashes for high-value long-term integrity guarantees.

EasyTechnical

69 practiced

List and explain major classes of side-channel attacks (timing, simple and differential power analysis, electromagnetic, cache-based, acoustic). For each class give a concrete example of an implementation-level leak and a practical mitigation that engineers can deploy.

Sample Answer

**Overview — major classes**Below are common side-channel classes, an implementation-level leak example for each, and practical engineering mitigations.

**1) Timing attacks**- Leak: Branch-dependent or table-index-dependent code (e.g., AES T‑table lookups causing variable execution time correlated with key bytes).- Mitigation: Constant-time implementations (avoid data-dependent branches/memory accesses), use bit-sliced algorithms or masked table lookups, and enforce compiler flags that prevent optimization-induced branches.

**2) Simple & Differential Power Analysis (SPA/DPA)**- Leak: Power waveform peaks during key-dependent operations (SPA) and statistical correlation across many traces (DPA) leaking AES round keys on smartcards.- Mitigation: Current and voltage noise injection, algorithmic masking (randomize intermediate values per operation), and dual-rail logic or power balancing at hardware level.

**3) Electromagnetic (EM)**- Leak: EM emanations from CPU during modular exponentiation reveal windowed exponentiation pattern, exposing private key bits.- Mitigation: Shielding, PCB layout minimization, algorithmic blinding (e.g., exponent blinding), and randomized instruction scheduling.

**4) Cache-based attacks**- Leak: Flush+Reload or Prime+Probe revealing which cache lines (S-boxes, table lookups, or branch targets) were accessed during AES or RSA, exposing key-dependent memory access patterns.- Mitigation: Avoid secret-dependent memory access (use constant-time/memory access), isolate caches (process/core pinning, flush on context switch), and use hardware features like Intel CAT or page coloring.

**5) Acoustic**- Leak: High-frequency acoustic signatures during cryptographic operations (RSA key-dependent multiplication sequences) correlated to key bits.- Mitigation: Algorithmic randomization (blinding), add acoustic noise or jitter, and isolate sensitive hardware in soundproof enclosures.

Practical notes: combine mitigations (software + hardware), perform leakage assessment (TVLA, CPA), and prioritize fixes based on attack surface and threat model.

HardTechnical

55 practiced

Given a lattice-based KEM using a cyclotomic polynomial modulus with n=1024, q=2^{14}, and Gaussian error sigma=3.2, describe how you would estimate classical and quantum security levels using BKZ blocksize beta heuristics. Explain how to map beta to bit-security, how parameter changes affect security, and discuss typical implementation side-channel concerns for these schemes.

Sample Answer

**Approach overview**- Reduce security estimation to: for the given RLWE parameters (n=1024, q=2^14, sigma=3.2) find the BKZ blocksize β an attacker needs to solve the underlying lattice instance, then map β to a concrete cost (classical and quantum) using SVP cost heuristics and report bit-security = -log2(cost).

**Steps to estimate**1. Compute target lattice root-Hermite factor δ required for an attack to succeed (use standard reductions from RLWE/LWE to approximate shortest vector length vs. lattice determinant; many tools do this automatically).2. Use δ → β mapping via BKZ δ(β) heuristics (e.g., ε-BKZ models / blockwise GSA fits or the empirical relation used in the Lattice Estimator/LWE estimator).3. Convert β to cost: - Classical SVP (sieving) cost ~ 2^{c_classical * β} (use c_classical from current literature / estimator — typical used constants from Albrecht et al./Chen-Nguyen). - Quantum SVP speedup uses quantum sieving/shrinking constants giving smaller exponent c_quantum.4. Bit-security = -log2(cost). Report both classical and quantum bits.

**How parameters affect security**- Increasing n increases hardness roughly exponentially (needs larger β). - Increasing q can lower or raise hardness depending on noise ratio; for fixed σ, larger q generally makes the lattice determinant larger and can make finding secret somewhat easier—security is governed by q/σ (noise-to-modulus). - Increasing σ (more noise) increases security but can raise correctness/DFR concerns.

**Typical side-channel concerns**- Constant-time polynomial arithmetic (NTT) to avoid timing/leakage.- Gaussian sampler leakage (timing or power) — use discrete constant-time samplers or masked sampling.- Rejection sampling branches and short secret/key-dependent branching -> use fixed-time or dummy operations.- Decryption failure side channels: DFR-induced oracle attacks (measure error/noise patterns) — minimize DFR and avoid observable differences.- Memory/stack traces from large lattice operations (key-dependent access patterns) — constant-memory access patterns or masking.

Implement using the LWE/Lattice Estimator tools (Albrecht’s estimator) and cite up-to-date SVP cost constants; validate with both classical and quantum models and include side-channel mitigations in the implementation plan.

Unlock Full Question Bank

Get access to hundreds of Cryptanalysis and Security Evaluation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.