Cryptography Fundamentals Questions
Core concepts and vocabulary of cryptography: confidentiality, integrity, authentication, and non-repudiation; the difference between symmetric and asymmetric primitives; and how standard algorithms, libraries, and protocols fit together. Covers threat models, common standards, and applying primitives and cryptographic libraries correctly to real-world security problems. The entry point for the cryptography track.
Write a function that compares two byte strings for equality in constant time, suitable for verifying a MAC (e.g. an HMAC tag) without using a language's built-in constant-time-compare helper. Explain specifically why your implementation doesn't leak timing information, and how you'd test that claim.
Sample Answer
Approach
A naive byte-string comparison (a == b, or a loop that returns on the first mismatch) short-circuits: it stops as soon as it finds a differing byte. That means comparing a correct tag's first byte takes measurably less time than comparing a tag that's correct for the first 30 bytes and wrong on byte 31. An attacker who can measure that timing difference, even over a network with noise, can recover a valid message authentication code (MAC) one byte at a time by trying all 256 values for each position and keeping whichever one takes longest. This is exactly the kind of attack a constant-time compare exists to prevent.
The fix has two ingredients: never stop early, and never let the result of one byte's comparison affect how much work is done for the next one. Instead of comparing and branching, XOR every corresponding byte pair and OR the results together, then check that final accumulator once at the end.
def constant_time_compare(a: bytes, b: bytes) -> bool:
"""Compare two byte strings without leaking a length-prefix match via timing."""
if len(a) != len(b):
# Do a dummy pass over `a` so this branch isn't a distinguishably fast return.
# MAC length is public protocol information, not a secret, so this is defense
# in depth rather than the core of the fix.
result = 0
for byte in a:
result |= byte
return False
result = 0
for x, y in zip(a, b):
result |= x ^ y
return result == 0
Key points
x ^ yis zero only when the two bytes are equal, so OR-ing every position's XOR into one accumulator means the finalresultis zero only if every byte matched. There is no branch inside the loop whose outcome depends on secret data, so the number of operations performed is identical (a function only oflen(a)) regardless of where, or whether,aandbdiffer.- To confirm this is actually equivalent to the trusted built-in (
hmac.compare_digestin Python, or the language's equivalent), verify it agrees on both a correct tag and tags tampered at the first and last byte:
import hmac, hashlib
key, message = b"super-secret-mac-key", b"account=1042&amount=500.00"
real_tag = hmac.new(key, message, hashlib.sha256).digest()
tampered_first = bytes([real_tag[0] ^ 0xFF]) + real_tag[1:]
tampered_last = real_tag[:-1] + bytes([real_tag[-1] ^ 0xFF])
print(constant_time_compare(real_tag, real_tag)) # True
print(constant_time_compare(real_tag, tampered_first)) # False
print(constant_time_compare(real_tag, tampered_last)) # False
Running this prints True, False, False, matching a normal equality check's correctness while removing its timing signal.
Testing the timing claim
You cannot prove "no timing leak" from reading code alone; the honest way to test it is to compare relative timing behavior across many repetitions with the mismatch position deliberately varied, and confirm the naive version gets faster as the mismatch moves earlier while the constant-time version does not:
import time
def naive_compare(a, b):
if len(a) != len(b): return False
for x, y in zip(a, b):
if x != y: return False
return True
long_a = bytes([0] * 10000)
mismatch_early = bytes([1]) + bytes([0] * 9999)
mismatch_late = bytes([0] * 9999) + bytes([1])
def time_it(fn, a, b, n=2000):
start = time.perf_counter()
for _ in range(n): fn(a, b)
return time.perf_counter() - start
print("naive early/late:", time_it(naive_compare, long_a, mismatch_early), time_it(naive_compare, long_a, mismatch_late))
print("const-time early/late:", time_it(constant_time_compare, long_a, mismatch_early), time_it(constant_time_compare, long_a, mismatch_late))
On a real run this printed the naive version taking roughly three orders of magnitude longer when the mismatch was near the end than near the start, while the constant-time version's two timings were within measurement noise of each other. Exact numbers are hardware- and load-dependent, so a real audit runs many trials and looks at the statistical distribution, not a single measurement, but the qualitative signature (does timing correlate with mismatch position) is what you're checking for.
Complexity
Both the comparison and the dummy fallback pass are O(n) in the length of the inputs, with no early exit, so the constant-time version does strictly more work than a best-case naive comparison and exactly the same work as a worst-case one. Space is O(1) beyond the inputs themselves.
Edge cases
- Different-length inputs must not be rejected via an instant
return False, that branch is itself timeable; either pad to a fixed comparison length or, as shown, burn equivalent work before returning. - Compiler and interpreter optimizations can sometimes reintroduce short-circuiting (e.g. an optimizer proving a branch is dead); production code should use the language's own vetted constant-time primitive (
hmac.compare_digest,crypto/subtle.ConstantTimeComparein Go,CRYPTO_memcmpin OpenSSL) once you understand why it exists, this exercise is about understanding the mechanism, not replacing the standard tool.
Your organization still relies on SHA-1 in legacy components including certificate signatures and internal git repositories. Create a phased migration plan to stronger hashes (SHA-256 or better) that minimizes downtime, covers certificate replacement and repository migration, addresses interoperability with older clients, and verifies successful migration.
Sample Answer
Framing
SHA-1 (Secure Hash Algorithm 1) has a practically demonstrated collision break: attackers have published real pairs of distinct inputs producing the same hash, which matters enormously for certificate signatures (a certificate authority's signature over a certificate is only trustworthy if nobody could have engineered a colliding, malicious certificate with the same signature) and matters somewhat differently for a version-control system, where hashes are primarily content-addressing identifiers, not signatures over untrusted third-party input, but a maliciously crafted collision could still let an attacker substitute code silently. The migration has to run on two independent tracks with different urgency, plus a compatibility bridge for anything that can't move immediately.
Phased plan
- Inventory and freeze new usage. Find every place SHA-1 is used: certificate signing requests still being issued with SHA-1, internal certificate authorities configured to sign with it, git repositories, and any code computing SHA-1 for reasons other than pure legacy compatibility. Immediately stop issuing anything new with SHA-1, every new certificate gets a SHA-256 signature, this alone is low-risk and shrinks the problem going forward.
- Certificate replacement, done by criticality. Re-issue certificates in order of exposure: externally-facing services first (least time for an attacker to have obtained a colliding forgery in the wild, since publicly trusted certificate authorities stopped issuing SHA-1 certificates industry-wide years ago), then internal services with their own private certificate authority. For each certificate, reissue with a SHA-256 (or stronger) signature, deploy to the service, and confirm it serves the new chain before revoking the old one, not the other way around, to avoid an outage window with no valid certificate at all.
- Interoperability with older clients. Some very old clients may not support SHA-256-signed certificate chains. Handle this the same way any protocol version deprecation is handled: identify which specific clients are actually still connecting (from real traffic logs, not assumption), give them a defined, communicated end-of-support date, and only keep a SHA-1 fallback path alive for that dwindling population, with monitoring on its usage so you know when it's safe to remove.
- Repository migration. For internal git repositories still keyed by SHA-1 object identifiers, the practical mitigation already in wide use is a hardened SHA-1 implementation that detects known collision-attack patterns (this is what major hosting platforms adopted after the first public collision was demonstrated) rather than an immediate wholesale rehash, since git's own transition to a stronger hash is a larger, longer-running effort tracked by the git project itself; the near-term action for an internal deployment is ensuring the collision-detecting variant is actually in use, and tracking the upstream migration path for the longer term.
- Verification. Confirm success with evidence, not assumption: scan all active certificates for signature algorithm, monitor certificate authority issuance logs to confirm zero new SHA-1 signatures, and run a hash-algorithm audit against the code and configuration inventory from step 1 to catch anything missed.
Trade-offs and pitfalls
The riskiest failure mode in this kind of migration isn't SHA-1 itself, it's a broken rollout: revoking an old certificate before confirming the new one is deployed and trusted causes a real outage, and rushing repository rehashing without coordinating with every consumer of those commit hashes (build systems, deployment pipelines, external mirrors) can silently break more than it fixes. Sequence certificate work by exposure and treat the legacy-client interoperability period as a tracked, time-boxed exception with an actual removal date, not a permanent fallback that quietly never gets revisited.
Compare block cipher modes of operation such as CBC and GCM. In a system that requires encryption for disks (at-rest logs) and for transport (TLS-like traffic), which mode(s) would you choose for each use case and why? Discuss IV/nonce requirements and integrity guarantees.
Sample Answer
Direct answer
For transport-like traffic (a live connection between two parties), use Galois/Counter Mode (GCM): it is authenticated, single-pass, and parallelizable, which matches a stream of packets where you want low latency and can generate a fresh nonce per message easily. For data at rest (logs sitting on disk with no live connection to negotiate per-message nonces), Cipher Block Chaining (CBC) is the classic textbook answer but is the wrong choice today for the same reason it always was: it provides no built-in integrity check. The honest, current recommendation for both cases is an authenticated mode, GCM (or an alternative authenticated construction) for both, with the at-rest case leaning on deliberate nonce management rather than live negotiation.
Comparing the modes
- CBC encrypts each plaintext block XORed with the previous ciphertext block, using an initialization vector (IV) to seed the first block. It needs the IV to be unpredictable (not necessarily secret, but not attacker-guessable in advance) and requires padding, which historically enabled padding-oracle attacks when an application leaked whether decryption padding was valid. Critically, CBC on its own gives you confidentiality but no integrity: an attacker can flip bits in ciphertext and produce predictable, attacker-influenced changes in the decrypted plaintext with no error raised.
- GCM combines counter-mode encryption with a polynomial-based authentication tag (GHASH) in one pass, so it gives you both confidentiality and integrity, and it detects any tampering by failing to verify rather than silently decrypting corrupted data. Its hard requirement is a nonce (a 96-bit value in the standard construction) that must never repeat under the same key, reuse breaks both the confidentiality guarantee (via keystream reuse) and the authentication guarantee (via leaking GCM's internal authentication key), so nonce uniqueness is non-negotiable.
Worked recommendation
- At-rest logs: use GCM, with nonces generated from a per-file or per-segment counter that is durably persisted alongside the encrypted data (so a process restart cannot repeat a value), or a per-record random 96-bit nonce if record volume per key stays well under the birthday-bound guidance for random nonces. Store the nonce and authentication tag next to the ciphertext; verification on read means corrupted or tampered log segments are detected immediately instead of silently trusted.
- Transport-like traffic: use GCM (or ChaCha20-Poly1305 where hardware AES acceleration isn't available) with a fresh, connection-scoped nonce per record, which is exactly the pattern Transport Layer Security (TLS) 1.2 and 1.3 use internally, a per-record explicit or implicit nonce derived from a sequence number.
Trade-offs and pitfalls
The single hardest constraint in both cases is the same one: nonce uniqueness under a fixed key. Choosing GCM for both use cases only pays off if the nonce-generation strategy for each is actually enforced (durable counters for files that survive restarts, connection state for transport), because a mode swap from a broken CBC deployment to a broken GCM deployment (repeating nonces) is not actually a fix, it trades one class of catastrophic failure for another.
Compare PBKDF2, bcrypt, scrypt, and Argon2 at a high level. For each describe its primary design goals, whether it is CPU-bound or memory-hard, how resistant it is to GPU/ASIC acceleration, and any known side-channel concerns. For a greenfield web service today, state which you would choose by default and justify that choice in terms of security and deployability.
Sample Answer
Direct answer
All four are key derivation functions (KDFs) built specifically to make password guessing slow, unlike a plain fast hash like SHA-256, which an attacker with commodity graphics-processing-unit (GPU) hardware can evaluate billions of times a second. They differ in what resource they force an attacker to spend: pure computation time (PBKDF2), or computation time plus memory (bcrypt, scrypt, Argon2). For a new, general-purpose web service today, Argon2id is the right default.
Comparing the four
| Function | Primary resource cost | Memory-hard? | GPU/ASIC resistance | Notable side-channel concern |
|---|---|---|---|---|
| PBKDF2 (Password-Based Key Derivation Function 2) | CPU time only (many rounds of an underlying hash-based message authentication code) | No | Weak: its small, fixed memory footprint makes it comparatively cheap to parallelize on GPUs and custom application-specific integrated circuit (ASIC) hardware | None specific to the algorithm itself |
| bcrypt | CPU time, with a small, fixed memory requirement from its Blowfish-based design | Modest, not true memory-hardness by modern standards | Better than PBKDF2, still meaningfully weaker against GPU/ASIC attackers than scrypt or Argon2 | Its internal state fits comfortably in a GPU's cache, reducing the memory-bandwidth advantage a defender would want |
| scrypt | CPU time and a large, tunable memory requirement | Yes, this was its original selling point | Strong, since large memory requirements are expensive to replicate at scale on GPUs and especially on ASICs | Its data-dependent memory access pattern can leak information via cache-timing side channels |
| Argon2 (Argon2id variant) | CPU time and tunable memory, explicitly designed as the winner of the 2015 Password Hashing Competition | Yes, and tunable independently of CPU cost | Strong, comparable to or better than scrypt, with more flexible tuning of the memory/time/parallelism trade-off | Argon2id specifically mitigates the side-channel weakness of Argon2d by using a data-independent memory access pattern for its first pass |
Worked recommendation
For a greenfield web service today, default to Argon2id with parameters sized to your actual server hardware (a common practical target is tuning memory and iteration count so a single hash takes somewhere in the range of a few hundred milliseconds on your production hardware, adjusted for how much concurrent login load you need to serve). Argon2id is chosen specifically because it is both memory-hard (expensive to parallelize on GPUs and application-specific hardware) and resistant to the cache-timing side-channel weakness of the purely data-dependent Argon2d variant, while remaining widely supported in current cryptography libraries and formalized in a published standard (RFC 9106). Where a platform or compliance requirement mandates a National Institute of Standards and Technology (NIST) approved algorithm and Argon2 isn't an option, PBKDF2 with a high iteration count is the fallback, but it should not be the first choice when Argon2id is available, since it offers no meaningful memory-hardness at all.
Trade-offs and pitfalls
Picking a KDF is necessary but not sufficient: tuning it too weakly (low iteration count, low memory) to keep login latency low defeats the purpose, while tuning it too aggressively can create a denial-of-service risk on a login endpoint under load. Every one of these functions must also be used with a unique, randomly generated salt per user, reusing a salt (or omitting one) lets an attacker precompute or share cracking work across every account that used the same value, regardless of which of these four algorithms is chosen.
Provide a detailed analysis comparing RSA and elliptic curve cryptography (ECC) for large-scale TLS termination where millions of handshakes occur daily. Address CPU and memory cost per handshake, signature verification versus generation costs, key and certificate sizes, hardware acceleration impact, caching strategies, and long-term maintainability.
Sample Answer
Direct answer
Default to elliptic curve cryptography (ECC), specifically X25519 for key exchange and Ed25519 or
ECDSA over P-256 for signatures, for large-scale Transport Layer Security (TLS) termination. At
equivalent security strength ECC needs far smaller keys and signatures and a cheaper signing
operation than RSA, which is the operation that scales with handshake volume; keep RSA (2048 or
3072-bit) only as a compatibility fallback for legacy clients.
Structured elaboration
- Why signing cost dominates, not verification. In TLS 1.3 the server signs the handshake
transcript once per new connection (or resumes without a fresh signature at all), so signature
generation cost sits on the server's critical path at scale, while signature verification
happens on the client, one per connection, off the server's aggregate budget. - Key and signature sizes are exact, not estimated. An RSA-2048 modulus is 2048 bits, that is,
256 bytes, and an RSA signature is exactly that size. An ECDSA P-256 signature is two 256-bit
integers, 64 bytes raw (roughly 70 to 72 bytes once Distinguished Encoding Rules, DER, ASN.1
framing is added). An Ed25519 signature is a fixed 64 bytes. Every certificate in a chain carries
its issuer's signature, so this size difference compounds down the whole chain, which is why
ECDSA/Ed25519 certificate chains are noticeably smaller on the wire than RSA-2048 ones. - Hardware acceleration. AES-NI accelerates the symmetric bulk-data phase of TLS (the actual
application traffic), not the asymmetric handshake math, so it helps both algorithm choices
equally. Dedicated accelerators for modular exponentiation, such as Intel QuickAssist Technology
(QAT, a chipset feature that offloads public-key math to dedicated silicon), give RSA a much
bigger relative boost than ECC, precisely because RSA's operation is the more expensive one to
begin with; an EC-heavy fleet has less headroom left to reclaim from hardware. - Caching and session reuse. Use TLS 1.3 by default (it drops RSA key exchange entirely in
favor of ephemeral Diffie-Hellman), enable session resumption via session tickets or a
pre-shared key (PSK) to skip the full handshake on repeat connections, and use Online
Certificate Status Protocol (OCSP) stapling so clients do not each make a separate revocation
check.
Worked example
A rough, complexity-based estimate of why ECC signing is cheaper (not a timed benchmark, since
wall-clock numbers depend on hardware and library and are not reproducible from an answer): if you skip the arithmetic that follows, the single point is that RSA does its math on 2048-bit numbers while ECC does it on 256-bit ones, and because the cost of each multiplication grows with the square of that width, the far narrower ECC numbers are what make it cheaper. For the details: RSA-2048
with the Chinese Remainder Theorem (CRT) optimization (a standard speed-up that splits the RSA private-key computation into two half-size pieces, one per prime factor of the modulus, then recombines them) does its private-key operation as two
roughly 1024-bit modular exponentiations. A square-and-multiply exponentiation (the standard way to raise a number to a large power: read the exponent one bit at a time, squaring at every step and multiplying in the base only on the 1-bits) over a k-bit
exponent needs on the order of k modular squarings plus, on average, k/2 modular
multiplications, so per 1024-bit exponentiation that is roughly 1024+512=1536
multiplications of 1024-bit numbers, doubled for the two primes: about 3072 multiplications at
1024-bit width. An ECDSA P-256 signature needs one scalar multiplication of a 256-bit scalar (the elliptic-curve counterpart of exponentiation: repeatedly combining a fixed curve point with itself, once per bit of the scalar);
double-and-add (the point-by-point analogue of square-and-multiply) costs roughly 256 doublings plus, on average, 128 additions, about 384 point
operations, and each point operation (one add or double of curve points) costs on the order of 10 field multiplications (multiplications of the fixed-width numbers the curve is built over; one point add or double works out to roughly a dozen of them in the usual coordinate systems, so 10 is a round figure) at 256-bit
width, roughly 3840 multiplications at 256-bit width. Since schoolbook modular multiplication of a
k-bit number costs on the order of k2 bit operations (the grade-school method of multiplying every digit by every digit does about k×k single-bit steps for k-bit numbers), the total bit-operation counts come out
to roughly 3072×10242≈3.2×109 for RSA versus roughly
3840×2562≈2.5×108 for ECC, a difference of about an order of magnitude
(roughly 13x under these assumptions). Real libraries use faster multiplication and windowing
techniques that change the constants, not the qualitative conclusion: the much narrower modulus is
what makes elliptic-curve signing cheaper, and that gap only widens at higher RSA key sizes.
Trade-offs & pitfalls
- RSA public-key verification is actually cheap (the public exponent is conventionally 65537, a
17-bit value with few 1-bits), often cheaper than an EC verification, which needs a
double-scalar multiplication; this is why RSA can still look attractive for verify-heavy,
sign-light workloads, which server-side TLS termination is not. - Do not trust a generic multiplier like "ECC is N times faster" as a measured fact for your stack;
the real number depends on your library, curve, and hardware, and should be benchmarked on your
own production-shaped load rather than assumed. - Maintain algorithm agility (support more than one signature scheme in your TLS stack and be able
to swap without a client-facing break), since both RSA and ECC are broken by a sufficiently large
quantum computer; treat post-quantum migration as an awareness item to plan for, not a mechanism
to implement here. - Common wrong turn: benchmarking handshake cost while ignoring session resumption; a design that
looks expensive per-handshake can be cheap in aggregate if most connections resume instead of
performing a full handshake.
Unlock Full Question Bank
Get access to all 44 Cryptography Fundamentals interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.