Cryptanalysis and Security Proofs Questions
Evaluating the strength of cryptographic constructions: attack techniques, cryptanalysis of ciphers and protocols, reduction-based security proofs, and formal analysis. Covers reasoning about what an adversary can and cannot do and how security guarantees are argued rigorously. The offensive-and-verification counterpart to scheme design.
Estimate the time required to brute-force symmetric keys of length 56, 80, 112, and 128 bits on a machine that can test 1e9 keys per second. Provide results in seconds, days, and years, and briefly discuss how parallelization or specialized hardware changes these estimates.
Sample Answer
Direct answer
Exhaustive key search over an n-bit keyspace costs up to 2^n trial operations (2^(n-1) on average before success), so dividing the keyspace size by the attacker's throughput gives wall-clock time directly. At 1e9 keys per second, a 56-bit key falls in about a day, an 80-bit key takes tens of millions of years, and 112- or 128-bit keys push into numbers vastly beyond the age of the universe for a single machine at this rate. Every extra key bit doubles the required work, which is why these numbers grow so explosively.
Structured elaboration
The governing relationship, worst case (exhaustive search of the full space):
Tseconds=R2nwhere R is keys tested per second. The average case (expected time to find the one correct key, searching in a random order) is half that. All results below use one consistent basis: seconds, converted to days by dividing by 86,400, then to years by dividing by 365.25.
Brute force is embarrassingly parallel: each machine searches a disjoint slice of the keyspace, so P independent machines at the same per-machine rate divide the total time by P almost exactly. Specialized hardware (ASICs, FPGAs) also matters far more than raw machine count: the EFF's 1998 Deep Crack machine, a purpose-built ASIC design, broke a 56-bit DES key in under three days using hardware that would look unremarkable a decade later, demonstrating that "impractical for a lone attacker on commodity CPUs" is very different from "impractical for an adversary willing to invest in custom silicon."
Worked example
At R = 1e9 keys/second, worst-case (full exhaustive search) times:
| Key size | Keyspace (2^n) | Seconds | Days | Years |
|---|---|---|---|---|
| 56 bits | 7.21 x 10^16 | 7.21 x 10^7 | ~834 | ~2.28 |
| 80 bits | 1.21 x 10^24 | 1.21 x 10^15 | ~1.40 x 10^10 | ~3.83 x 10^7 |
| 112 bits | 5.19 x 10^33 | 5.19 x 10^24 | ~6.01 x 10^19 | ~1.65 x 10^17 |
| 128 bits | 3.40 x 10^38 | 3.40 x 10^29 | ~3.94 x 10^24 | ~1.08 x 10^22 |
(Average-case time, if you only need to search until the actual key is found rather than the whole space, is exactly half of every figure above, on the same basis.)
Trade-offs and pitfalls
Notice the scale jump between 80 and 112 bits: 80-bit keys are firmly within reach of a sufficiently resourced attacker over realistic timeframes, while 112 bits (2-key 3DES territory) sits at the edge of adequate margin and 128 bits (AES-128) remains solid. A common mistake is assuming more hardware erodes security proportionally; it does not, because keyspace grows exponentially while hardware only scales resources linearly (or with parallel machine count). A million-fold increase in an attacker's compute buys only about 20 bits of effective security reduction (log2(1,000,000) ≈ 19.9), which is why 128-bit keys stay comfortably out of reach even against enormous, well-funded compute budgets, while 56- and 80-bit keys do not.
Describe how you would convert a theoretical attack cost (for example 2^{60} operations and 128 GB memory) into a real-world feasibility assessment. Include considerations such as attacker parallelism, memory distribution, hardware & electricity cost, logistics of acquiring hardware, time-to-completion, and how to present risk to non-technical stakeholders.
Sample Answer
Direct answer
A raw complexity figure like "2^60 operations, 128 GB memory" tells you almost nothing about real-world risk on its own. Converting it into an actionable assessment means pinning down a realistic hardware throughput assumption, computing wall-clock time and dollar cost from that assumption, checking whether the memory requirement is a genuine bottleneck or something that parallelizes cleanly, and then translating the result into terms a non-technical stakeholder can weigh against a business decision, a specific dollar figure and timeframe under stated assumptions, never a bare exponent.
Structured elaboration
- Attacker parallelism: is the workload embarrassingly parallel, like brute force, where each unit works an independent slice, or does it need shared, growing state, like one giant sorted table, that resists easy distribution? Parallel work divides wall-clock time roughly linearly with machine count; non-parallel work does not.
- Memory distribution: 128 GB might comfortably fit on one server today, but if the real attack needs 128 GB PER PARALLEL WORKER rather than shared, the total footprint multiplies by worker count and can become the actual bottleneck instead of the operation count.
- Hardware and electricity cost: pick a concrete throughput-per-dollar and power-draw assumption for the hardware class actually suited to the workload (general CPU vs GPU vs custom ASIC, since purpose-built silicon is often 100 to 1,000 times cheaper per operation), then multiply by the operation count and a stated electricity rate to get a total dollar figure.
- Hardware acquisition logistics: can an attacker actually buy or rent this much compute quickly (cloud spot capacity, ASIC lead times, export controls), or does it require years of custom fabrication and warehouse space? This changes whether the threat is "a well-funded criminal group next month" or "a nation-state over several years."
- Time-to-completion: state the wall-clock duration explicitly under the chosen hardware assumption, and how it scales down with more budget.
- Presenting risk to non-technical stakeholders: translate the final numbers into business-relevant framing, for example "under these stated assumptions this would cost roughly $X and Y months for an attacker with Z resources," always naming the assumptions rather than presenting one deceptively precise figure, and being explicit that estimates should be treated as an upper bound on required attacker sophistication, since cheaper attacks tend to be discovered later, not more expensive ones.
Worked example
Take the example given, 2^60 operations and 128 GB memory, with an explicitly stated hardware assumption: a cluster delivering a combined 10^11 (100 billion) operations per second.
Tseconds=1011260≈10111.153×1018≈1.153×107 seconds≈133.5 days≈0.37 yearsThis number is only as good as the stated 10^11 operations/second assumption, a plausible mid-size GPU-cluster figure for many cryptographic operations; the SAME 2^60-operation attack could complete in hours on a large dedicated ASIC farm, or take years on a single laptop. A real feasibility assessment shows the number under a couple of clearly different, explicitly stated hardware assumptions, rather than one unexplained figure presented as fact.
Trade-offs and pitfalls
A common wrong turn is presenting the raw exponent to a non-technical stakeholder ("2^60 operations") without translation; it either sounds meaninglessly abstract or gets anchored to whatever the listener's gut feeling about "a big number" happens to be. Another common wrong turn is picking an unrealistically weak, or unrealistically strong, hardware assumption to make the risk look however the presenter wants; always state the assumption explicitly and, where possible, anchor it to a real public benchmark or a documented prior attack's resources rather than inventing one.
Explain the meet-in-the-middle attack on double-DES (ciphertext C = E_{k2}(E_{k1}(P))). Derive the time and memory complexity in terms of single-DES key size k=56 and show the numeric work factor and memory requirement. Explain why double-DES was not considered secure and how 3DES addresses the issue.
Sample Answer
Direct answer
Stacking two independent 56-bit DES keys as C = E_k2(E_k1(P)) looks like it should give 112 bits of security, but a meet-in-the-middle (MITM) attack, one that attacks from both ends of the computation at once instead of guessing the whole key pair, breaks it in only about 2^57 time and 2^56 memory. That is barely more work than breaking single DES, which is exactly why double-DES was never adopted and why triple-DES (3DES, using a third independent key) became the real fix.
Structured elaboration
Given one known plaintext/ciphertext pair (P, C):
- Forward pass: for every candidate k1 (all 2^56 values), compute X = E_k1(P) and store the pair (X, k1) in a lookup table, sorted or hashed by X.
- Backward pass: for every candidate k2 (all 2^56 values), compute Y = D_k2(C) and check whether Y appears in the table. Any match (X == Y) gives a candidate key pair (k1, k2) satisfying E_k2(E_k1(P)) = C for this one plaintext/ciphertext pair.
- Because a single pair produces many false-positive matches by chance, confirm each candidate against a second known plaintext/ciphertext pair, which quickly eliminates all but the true key pair.
Total time: roughly 2 x 2^56 = 2^57 operations (one pass to build the table, one to probe it), instead of the naive 2^112 needed to brute-force every key pair directly. Total memory: about 2^56 stored table entries, which turns out to be the real bottleneck.
Worked example
Time: 2 x 2^56 = 2^57 ≈ 1.44 x 10^17 single-DES operations, versus a naive brute force of 2^112 ≈ 5.19 x 10^33 key-pair trials, a reduction of about 17 orders of magnitude in time.
Memory: 2^56 ≈ 7.21 x 10^16 entries; at roughly 16 bytes per entry (a 64-bit ciphertext block plus a 56-bit key, with indexing overhead), that is about 1.15 x 10^18 bytes, on the order of an exabyte. This is genuinely large, but well within reach of a well-funded adversary as storage costs fall, and it does not require anywhere near 2^112 time, which is the entire point: MITM shows double-DES's real security sits close to single DES's 2^56, not the naively expected 2^112.
Trade-offs and pitfalls
A common wrong turn is looking at 2^57 in isolation and concluding "that's still huge, so double-DES is fine." The relevant comparison is not to zero, it is to the intended 112-bit target: MITM shows the actual margin is barely one bit better than single DES. Triple-DES fixes this by adding a genuinely independent third key (encrypt-decrypt-encrypt with three keys); the same MITM trick against 3DES would need to search a much larger combined space, restoring most of the intended margin (2-key 3DES is generally estimated at only about 80 bits of practical security against known attacks, still well short of the naive 112, which is one reason NIST now treats 3DES itself as deprecated legacy technology, recommending AES for any new system rather than any variant of DES.
Analyze small-subgroup and invalid-curve attacks against Diffie-Hellman and elliptic-curve schemes. Show mathematically how a malicious peer can exploit lack of subgroup checks to recover private key material, provide a concrete attack example with group orders and cofactors, and list efficient defenses to implement on both client and server sides.
Sample Answer
Direct answer
If a Diffie-Hellman or elliptic-curve implementation does not validate that a received public value actually lies in the expected large prime-order subgroup, an attacker can send a value from a small-order subgroup instead. The victim's computed "shared secret" then only takes as many possible values as that small subgroup's order, so the attacker can determine the victim's private key modulo that small order just by observing which of the few possible outcomes resulted. Repeating this with several different small-order subgroups, or several maliciously crafted invalid curves, lets the attacker accumulate enough congruences to reconstruct the full private key via the Chinese Remainder Theorem (CRT).
Structured elaboration
Setup: a Diffie-Hellman group of prime order q sits inside a larger group of order N = q * h, where h is the "cofactor," a small leftover factor. A well-formed public key lies in the order-q subgroup, but if the implementation skips subgroup checks, any element of the full order-N group is accepted, including elements from small-order subgroups whose order divides h.
The attack: the attacker sends (or an invalid curve provides) an element y of known small order h_i, a divisor of h. The victim, using their real private exponent b, computes a shared secret S = y^b mod p (or the elliptic-curve equivalent, a scalar multiplication). Since y has order h_i, S can only take h_i distinct possible values, S = y^(b mod h_i). If the attacker can distinguish which of those few outcomes occurred, for instance through a MAC accept/reject oracle or a distinguishable error message, they learn b mod h_i exactly.
Repeating with several different small-order elements, or several different maliciously crafted invalid curves (curves that do NOT match the real curve equation but happen to have points of small known order, the classic elliptic-curve "invalid-curve attack"), gives b mod h_1, b mod h_2, and so on for several pairwise-coprime small factors; CRT combines these into b mod (h_1 * h_2 * ...). With enough distinct small factors this recovers the full private key, or at minimum leaks many bits of it. On elliptic curves this is especially dangerous because the curve's b coefficient in the short Weierstrass equation y^2 = x^3 + ax + b typically does not enter the point-addition and doubling formulas at all, so an implementation that never checks the received point actually satisfies the real curve equation happily computes on whatever invalid curve the attacker chose, including one deliberately picked for its small-order subgroups.
Worked example
Let p = 23, so the full multiplicative group has order p - 1 = 22 = 2 x 11. A small subgroup of order h = 2 exists, generated by -1 mod 23 = 22, since 22^2 mod 23 = 484 mod 23 = 1. The attacker sends y = 22 as their "public key." For a victim with real private exponent b:
S=ybmod23=22bmod23=(−1)bmod23which equals 1 if b is even and 22 if b is odd, only two possible outcomes (verified directly: b = 0..5 gives shared values 1, 22, 1, 22, 1, 22, alternating exactly with b mod 2). If the victim then, say, derives a MAC key from S and the attacker can tell success from failure on a forged message, the attacker learns b mod 2, one bit of the private key, from a single exchange. Real invalid-curve attacks on standard curves generalize this with several different invalid curves, each contributing a different small-order factor, until enough congruences accumulate via CRT to pin down an entire roughly 256-bit private scalar; this is the mechanism behind several real, publicly disclosed vulnerabilities in TLS and elliptic-curve libraries around 2015 to 2017 that omitted point-on-curve validation.
Trade-offs and pitfalls
A common wrong turn is assuming "the attacker cannot possibly recover a large key this way," but CRT combination across enough small factors scales to arbitrarily large keys, it is a matter of how many distinct small-order queries the attacker can make, not a hard ceiling. Another wrong turn is validating "the point lies on some curve" generically without checking it lies on the specific expected curve with the expected order.
Defenses, both client and server side, since either party can be the attack's target:
- Full public-key validation on receipt, every exchange: for finite-field Diffie-Hellman, check 1 < y < p - 1 and y^q mod p == 1 (confirms y lies in the intended order-q subgroup); for elliptic curves, check the point satisfies the actual curve equation, is not the point at infinity, and (when the cofactor h > 1) that its order is not a small cofactor-only factor.
- Prefer curves with cofactor h = 1 where available, removing this class of residue entirely.
- Cofactor clearing before use (standard practice in modern X25519 implementations), so an unchecked small-order input gets multiplied into the identity element before it can leak anything.
- Never let timing, error messages, or downstream MAC accept/reject behavior distinguish based on the raw shared-secret value in an externally observable way; run everything through a KDF and handle validation failures uniformly, as defense in depth alongside point validation, not a replacement for it.
- On the responder side specifically, reject an invalid public key BEFORE performing any Diffie-Hellman computation with it.
Describe the Bellcore (CRT-RSA) fault attack in full mathematical detail: show how a single faulty exponentiation modulo p or q yields a pair of values whose difference reveals a nontrivial gcd with N, and thus factors N. Then design a complete set of mathematical countermeasures (including verification steps and blinding techniques), and prove that your defense prevents key leakage under a single-fault model.
Sample Answer
Direct answer
CRT-RSA (a standard speedup that computes an RSA signature or decryption separately modulo each secret prime factor p and q, then recombines the results) is catastrophically fragile against a single injected computational fault. If an attacker causes even one error during EITHER the mod-p or the mod-q half of the computation, but not both, the resulting faulty signature and a genuine correct signature for the same message agree modulo one prime but disagree modulo the other, so their difference is a multiple of exactly one secret prime; a single GCD (greatest common divisor) computation against N then reveals that prime directly and fully breaks the key. The standard, provably sufficient countermeasure is to verify the output against the public key before ever releasing it, so a faulty result is caught and discarded internally instead of ever leaving the device.
Structured elaboration, full mathematics
CRT-RSA signing: for modulus N = p x q, private exponent d, message m, compute:
sp=mdmod(p−1)modp,sq=mdmod(q−1)modqthen recombine (Garner's formula) into s, satisfying:
s≡sp(modp),s≡sq(modq)which equals the ordinary RSA signature m^d mod N.
Fault model: a transient hardware fault, a voltage glitch, laser pulse, or clock glitch, the classic physical fault-injection vectors, corrupts only the mod-q branch, so the device recombines the CORRECT s_p with a WRONG s_q', producing a faulty output s' with:
s′≡sp(modp)(still correct mod p),s′≡sq(modq)(wrong mod q)Attack: an attacker who has both the correct s and the faulty s' for the same message computes:
s−s′≡0(modp),s−s′≡0(modq)⟹gcd(s−s′,N)=pa nontrivial factor of N, recoverable with a single, cheap Euclidean-algorithm GCD, no exponentiation or search at all; q = N / p follows immediately, giving the full private key via d = e^(-1) mod (p-1)(q-1). A fault landing in the mod-p branch instead yields gcd(s - s', N) = q by the identical argument.
Worked example, fully verified
p = 61, q = 53, N = 3233, phi = 3120, e = 17, d = 2753. Message m = 65. Correct signature s = 588 (checked: 588^17 mod 3233 = 65). Inject a fault only in the mod-q branch (a +7 perturbation to s_q before recombination): faulty signature s' = 2662.
gcd(588−2662, 3233)=gcd(−2074, 3233)=61=precovering the true prime factor from nothing but two signatures and one GCD computation, exactly the claimed mechanism, verified with genuinely executed modular arithmetic.
Complete countermeasure set, with a soundness argument under a single-fault model
- Signature verification before release, the standard, provably sufficient fix: after computing s, independently check s^e mod N == m using the small public exponent e (cheap compared to the two large private-exponent CRT computations already performed); if the check fails, discard the result rather than releasing anything. Soundness sketch: a fault corrupting exactly one CRT branch produces an s' that, per the derivation above, is wrong modulo N as a whole, so s'^e mod N differs from m with overwhelming probability (this check only fails to catch the fault if s'^e happens to equal m mod N by pure coincidence, roughly a 1-in-N chance for a fault of any real magnitude, negligible). Under a model where at most one fault occurs per signing operation, corrupting at most one CRT branch, verification catches it before release with overwhelming probability, and the attacker never obtains a usable correct-and-faulty pair.
- Message and exponent blinding: randomize the input before each CRT exponentiation (for example multiply m by a fresh random r^e mod N before signing and divide the result by r afterward) so that even if a fault somehow slipped past verification, defense in depth rather than sole reliance, the attacker cannot correlate a faulty signature with a specific known-correct one for the SAME effective input, breaking the attack's requirement of a matched pair.
- Redundant internal computation or consistency checks between the two CRT branches, catching a fault before final recombination even happens, useful when a device cannot afford the extra public-exponentiation cost of step 1.
- Physical and environmental fault-injection hardening (voltage and clock glitch detectors, light sensors against laser injection, duplicated execution paths with a hardware comparator), addressing the attack vector itself as defense in depth alongside the mathematical countermeasures above.
Trade-offs and pitfalls
A common wrong turn is abandoning CRT-RSA entirely for plain, non-CRT exponentiation, which sidesteps this specific attack but costs a real, significant performance penalty (CRT-RSA is roughly four times faster, the entire reason it is used); the correct fix is verification and blinding, not abandoning CRT. Another pitfall is verifying the signature AFTER logging or transmitting it rather than strictly before release; the check must gate the actual output path. A third pitfall is implementing the verification itself with a single, un-hardened comparison instruction that a second, well-timed fault could also flip; robust implementations duplicate or otherwise harden the check itself, not just add it naively.
Unlock Full Question Bank
Get access to all 13 Cryptanalysis and Security Proofs interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.