Cryptographic Hashing and Digital Signatures Questions
Cryptographic hash functions (collision resistance, preimage resistance), message authentication codes, and digital-signature schemes. Covers HMAC, signature verification, and how hashing underpins integrity, commitments, and authentication. Distinct from non-cryptographic hashing used in data structures.
Your legacy API accepts certificate signatures using RSA PKCS#1 v1.5 and SHA-1. Outline concrete detection and mitigation actions to protect against Bleichenbacher-style oracle attacks and chosen-prefix collision threats. Include code-level changes, runtime mitigations, library updates, emergency policy changes, and a migration timeline prioritizing high-risk endpoints.
Sample Answer
Direct answer
This legacy setup bundles two SEPARATE, independent risks under one description. First, SHA-1's (part of the SHA, Secure Hash Algorithm, family) practical chosen-prefix collision weakness lets an attacker who can influence what gets certified forge a second document with an identical hash. Second, PKCS#1 v1.5's signature-verification FORMAT has a documented history, the Bleichenbacher forgery class from 2006, resurfacing as the "BERserk" bug in 2014, where verifiers that don't strictly check the padding structure can be tricked into accepting a forged value as a valid signature without the attacker ever touching the private key. Fixing this needs BOTH a hash migration AND a hardened, strictly-validating verifier, or a move to RSA-PSS (RSA using the PSS, Probabilistic Signature Scheme, padding) entirely, on an aggressive timeline for the highest-value endpoints first.
Structured elaboration
Glossary. PKCS#1 v1.5 (Public-Key Cryptography Standards #1, version 1.5) is a padding standard for RSA operations; the signature variant pads a block as 0x00, 0x01, a run of 0xFF bytes, 0x00, then an ASN.1-encoded hash-algorithm identifier followed by the actual digest. ASN.1 (Abstract Syntax Notation One) is a standard notation and binary encoding format for structured data: it is what lets a parser tell, unambiguously, exactly where the "this is a SHA-256 identifier" tag ends and the raw digest bytes begin inside that padded block, rather than the boundary being knowable only by convention. CA (certificate authority) is the entity whose signature on a certificate is what a client ultimately trusts.
Two distinct threats that need two distinct fixes.
- SHA-1 collision risk: fixed by migrating the HASH algorithm to SHA-256 or stronger. A strict, correctly-implemented PKCS#1 v1.5 verifier is not enough protection here, since the verifier is working exactly as designed; it's the hash underneath it that's weak.
- PKCS#1 v1.5 signature-forgery risk: fixed by tightening the VERIFIER's own padding and ASN.1 parsing, rejecting any trailing garbage bytes between the digest and the end of the padded block rather than only checking that the digest appears somewhere early in the block. Historically this bug was easiest to exploit when the RSA public exponent e was small, e=3 in particular, since a cube-root-style construction becomes computationally tractable at that exponent; auditing for any endpoint still using e=3 keys is a useful, cheap priority signal.
Detection. Audit every code path that calls an RSA PKCS#1 v1.5 signature-verification function, and specifically test the library's ACTUAL padding-validation logic, not merely whether verification succeeds on a valid signature, since a buggy verifier will also pass that test. Build a dedicated negative-test suite that submits deliberately malformed padded blocks, trailing garbage after the digest, wrong ASN.1 identifiers, short padding runs, and confirm EVERY one is rejected.
Immediate mitigation, day 0, highest-risk endpoints (authentication, payment, code-signing). Reject any certificate or signature using SHA-1 outright. Audit for, and immediately disable, any endpoint accepting e=3 RSA keys for signature verification pending a stricter parser rollout.
Code-level fix. Upgrade to a current, actively-maintained cryptography library, which will already implement strict PKCS#1 v1.5 parsing correctly, rather than hand-patching a parser. Migrate new signing to RSA-PSS, which has a modern security proof and isn't vulnerable to this specific parsing-ambiguity class at all.
Runtime mitigations, separate from the code fix itself, for the transition window before every client is migrated: rate-limit signature-verification attempts per calling principal, so an attacker probing for a forgeable padding pattern can't iterate quickly; unify every failure path to return the same generic error rather than distinguishing "bad padding" from "bad digest" from "bad signature" in a way a probing attacker could use as a signal; and log verification failures with enough detail for later forensic review without ever logging key material or full signature bytes.
Library and infrastructure updates. Pin and audit the exact TLS and crypto library versions in use across all affected services; enable any available strict-mode or hardened-parsing configuration flags those libraries expose.
Emergency policy. Temporarily REJECT, not merely warn on, SHA-1-signed or e=3-keyed certificates on the highest-risk endpoints while the fix rolls out, and communicate the deprecation timeline clearly to any legacy clients that still need to migrate.
Migration timeline, prioritized by risk. Day 0: reject outright on authentication, payment, and code-signing endpoints. Following days: roll out the strict parser and begin hash migration in staging for internal or lower-risk endpoints. Following weeks: full cutover and legacy-client migration across the remaining surface. Final phase: revoke and rotate any keys or certificates that were exposed to the weak configuration during the transition window.
Worked example
The concrete, checkable artifact here is the padded block's exact byte layout, since this is fundamentally a parsing question, not an arithmetic one: 0x00, 0x01, then a run of 0xFF bytes filling out the block, then 0x00, then the ASN.1-encoded DigestInfo structure, then the digest itself. A STRICT verifier must confirm there are ZERO extra bytes between the end of the digest and the end of the RSA-block-sized value; a loose verifier that only checks "does the digest appear somewhere early in the block" leaves exactly that trailing region open for an attacker to fill with a mathematically convenient value, which is the structural gap the 2006 and 2014 forgery bugs both exploited.
Trade-offs and pitfalls
- Rejecting SHA-1 or e=3 keys immediately breaks legitimate legacy clients that can't upgrade quickly. The trade-off is availability against security, and for authentication, payment, and code-signing endpoints the right call is almost always security-first, with a compatibility bridge, a separate, clearly-labeled legacy endpoint carrying extra monitoring, reserved only for genuinely low-risk, hard-to-migrate cases.
- Using e=65537 instead of e=3 reduces this specific forgery risk but is not a complete substitute for a strict, well-tested parser. Verifier bugs of this general shape have recurred across multiple libraries and years, so defense shouldn't rely on "we picked a safe exponent" alone.
- Don't conflate this signature-verification vulnerability with the different, older 1998 Bleichenbacher attack against RSA PKCS#1 v1.5 ENCRYPTION padding, the "million-message attack" against TLS key exchange. They share an author's name and a padding-oracle flavor, but target different operations, verify versus decrypt, and need unrelated fixes; naming the wrong one in an incident writeup sends a response team chasing the wrong root cause.
Design an API and versioning strategy for a cryptographic library that exposes hash and MAC primitives. Include how you will support algorithm agility, deprecation of broken hashes, runtime selection, safe defaults, and how you will prevent accidental misuse by application developers.
Sample Answer
Direct answer
The library's job is to make the SAFE choice the easy one and the unsafe choice require deliberate effort. That means: version every algorithm identifier explicitly rather than letting "the default" silently drift, expose a small set of named, curated presets (not raw parameter knobs) as the primary API, and make deprecating a broken hash a first-class, enforced state rather than a comment in a changelog. Everything else in a versioning strategy exists to support those three properties.
Structured elaboration
- Algorithm agility via explicit, versioned identifiers: every hash or MAC (message authentication code, a keyed tag proving integrity and possession of a shared secret) output that gets stored or transmitted should be tagged with an explicit algorithm identifier (
sha256,hmac-sha256-v1), not left implicit. This lets the library change its DEFAULT algorithm across versions without breaking the ability to verify data produced under an older default, because the identifier travels with the data rather than being inferred from "whatever version produced it." - Safe defaults, curated presets over raw parameters: expose
hash_password(...),mac_message(key, msg),hash_file(...)as the primary entry points, each backed by a currently-recommended algorithm choice the library picks FOR the caller. Reserve direct access to a specific primitive (sha256_raw(...)) for a clearly separate, more advanced part of the API surface, so a caller reaching for the "just hash this" function cannot accidentally select a broken or inappropriate primitive by typing the wrong string. - Deprecation as an enforced state, not documentation: give every supported algorithm a status (
current,deprecated,disabled) tracked in code, not prose. Adeprecatedalgorithm still verifies existing data (so old signatures/tags do not silently break) but a new call to CREATE adeprecatedhash/MAC either warns loudly or requires an explicit opt-in flag (allow_deprecated=True), so a caller cannot end up using MD5 or SHA-1 for a new artifact by accident, only by conscious override. - Runtime selection with a fail-safe default: when an algorithm identifier is unrecognized (e.g. read from data produced by a newer library version the current one doesn't know about), FAIL CLOSED (raise, refuse to verify) rather than silently falling back to a guessed algorithm; a fallback guess is exactly the kind of ambiguity that enables downgrade and algorithm-confusion attacks.
- Preventing accidental misuse: type-distinguish outputs that must not be interchanged (a
MacTagtype is not aDigesttype, even though both are byte strings under the hood) so a caller cannot pass a plain hash where a MAC verification is expected; this closes a whole class of "used the wrong primitive for the wrong purpose" bugs at the type-checker or code-review level rather than relying on every caller reading the docs correctly.
Worked example
Consider SHA-1 deprecation concretely, since it is the case every real crypto library has had to handle: version 1 of the library ships hash(data) defaulting to SHA-1 (the contemporary safe choice at the time). Version 2 needs to move the default to SHA-256 without breaking every caller who stored a SHA-1 digest and needs to keep VERIFYING against it. The versioned-identifier design handles this directly: every stored digest is ("sha1", <bytes>) or ("sha256", <bytes>), never a bare byte string. verify(data, tagged_digest) dispatches on the tag and still supports SHA-1 (marked deprecated, verify-only), while hash(data) (the "give me a new digest" entry point) now defaults to ("sha256", ...) and requires algorithm="sha1" explicitly, with a deprecation warning, if a caller insists on the old one. No caller's stored data breaks; every NEW call gets the safe default; and a caller who deliberately opts into SHA-1 for a new artifact has to type that choice out loud, which is exactly the friction that should exist for a known-broken primitive.
Trade-offs and pitfalls
- A "just pass any algorithm name as a string" API is more flexible but strictly worse for misuse-resistance than a small curated preset list; flexibility here is a cost, not a free feature, because it lets a caller type
"md5"as easily as"sha256". - Deprecation that silently disables verification (rather than keeping old data verifiable while blocking new use) breaks backward compatibility in a way that pushes teams to pin an old library version forever, which is worse for security than the deprecated algorithm being merely available in verify-only mode.
- Versioned identifiers add a small but permanent tagging overhead to every stored value; the alternative, inferring the algorithm from context or byte length, is fragile (some algorithms share output lengths) and reintroduces exactly the ambiguity the identifier was meant to remove.
You're building a cache-key generator for a CDN, and a teammate suggests reusing the same fast hash function for hashing user passwords too, to keep the codebase simple. How would you respond, and what's the real boundary between a general-purpose hash like MurmurHash and a cryptographic hash function? Give three situations where a non-cryptographic hash is perfectly fine and three where using one would be a serious mistake.
Sample Answer
Direct answer
I'd push back on reusing the same fast hash for both cache keys and passwords: speed is exactly the property you want for a cache key generator and exactly the property you must NOT want for password hashing, because speed is what lets an attacker try billions of password guesses per second against a stolen database. The real boundary isn't "cryptographic hashes are better," it's whether an adversary controls or benefits from the input or the output. A general-purpose hash like MurmurHash is optimized assuming no adversary is present; a cryptographic hash like SHA-256 (part of the SHA, Secure Hash Algorithm, family) is built assuming a motivated one is.
Structured elaboration
Definitions. MurmurHash is a family of non-cryptographic hash functions designed for speed and a good, even distribution of outputs, originally built for hash tables and checksums. A cryptographic hash function additionally has to survive an adversary who is actively trying to break it: preimage resistance (given a digest, you can't find an input that produces it), second-preimage resistance (given one input, you can't find a different input with the same digest), and collision resistance (you can't find any two distinct inputs, of your own choosing, that produce the same digest). MurmurHash provides none of these against a motivated attacker; SHA-256 is designed and studied specifically to provide all three.
Three situations where a non-cryptographic hash is perfectly fine (no adversary, or a collision only costs a little accuracy, not security):
- In-process hash tables or maps keyed by data the caller controls internally, not data supplied over a network by an untrusted party.
- Probabilistic data structures such as Bloom filters or HyperLogLog, used for approximate counting, where an occasional collision only slightly degrades accuracy rather than breaking a security property.
- Sharding or partitioning keys for a cache or a distributed system, where the goal is even distribution across nodes, not resistance to a deliberate adversary (with the caveat below about attacker-supplied keys).
Three situations where using one would be a serious mistake:
- Password storage. A fast hash lets an attacker who steals the password database try enormous numbers of candidate passwords per second offline; a password hash needs to be deliberately slow and memory-hard instead, using a KDF (key derivation function) such as bcrypt, scrypt, Argon2, or PBKDF2.
- Message authentication or integrity checks against an adversary, such as verifying a downloaded file or a signed API request. Collision and preimage resistance are exactly what stop forgery here, and MurmurHash offers neither.
- Any hash table exposed to attacker-controlled keys over a network, such as a web server hashing request parameters into an internal table. A known non-cryptographic hash lets an attacker craft many inputs that collide on purpose, degrading the table toward a linked list and causing an algorithmic-complexity denial-of-service, sometimes called hash flooding.
Worked example
The clearest way to see the password-hashing mistake in concrete numbers is to look at what a KDF's iteration count actually buys you, since that number multiplies attacker cost directly and doesn't depend on wall-clock benchmarking. Suppose a team configures PBKDF2, one of the KDFs named above, with, as one illustrative configuration, N = 100,000 iterations, versus hashing the password once with a fast hash like SHA-256:
- Fast hash (1 iteration): testing a 10,000,000-entry common-password wordlist against a stolen digest costs 10,000,000 hash evaluations.
- KDF at N = 100,000 iterations: the SAME wordlist costs 10,000,000 times 100,000 = 1,000,000,000,000 (one trillion) hash evaluations, because every single guess now has to pay the full iteration count, not just one hash call.
That multiplier applies uniformly whether the attacker has one laptop or a warehouse of GPUs; it's a property of the KDF's design, not of any particular attacker's hardware. A fast hash like MurmurHash has no equivalent knob at all: it was never designed to be slow, so there is no "iteration count" to raise.
Trade-offs and pitfalls
- "Non-cryptographic" doesn't mean "insecure everywhere," it means "not designed for an adversarial threat model." Using SHA-256 for a purely internal hash table works correctly but burns CPU cycles for no security benefit, which is a legitimate but different critique from the password-hashing mistake above.
- Watch for the middle ground: a hash-flood-resistant non-cryptographic hash, such as SipHash, exists specifically because "just use a full cryptographic hash for indexing" is often overkill. SipHash is fast AND keyed, which is the real fix for hash-flooding, not full collision resistance.
- Document the boundary explicitly in code and API naming, rather than relying on tribal knowledge. Naming functions distinctly, for example hash_for_indexing() versus hash_for_password_storage(), prevents exactly this kind of accidental reuse from recurring later.
A service signs messages built by concatenating fields without separators, say user || timestamp || amount. Demonstrate how two different sets of field values could produce the exact same concatenated string (and therefore the same signature), then propose a fix. What would you actually change about how these messages get serialized before signing, and what backward-compatibility issues would your fix create?
Sample Answer
Direct answer
Concatenating fields without separators throws away the boundary information between them, so the same byte string can come from more than one set of field values. Move a digit from the front of timestamp into the back of user and the concatenation is identical, which means the signature over it is identical too, even though the two field sets mean different things. The fix is to make the message a canonical, self-delimiting encoding before it is signed, most simply by length-prefixing every field, and the real cost of shipping that fix is a coordinated cutover with old signatures and old verifiers in the system at the same time.
Structured elaboration
Why the ambiguity exists. user || timestamp || amount with no separators is not really one message; it is three fields glued together with the split points thrown away. A verifier that reconstructs the signed bytes from parsed (user, timestamp, amount) values assumes there's exactly one way to split the string back into those three fields, but nothing in the byte string enforces that. Any two field sets that concatenate to the same string produce the same signature, because the signature was only ever over the concatenation, never over the field structure.
The fix. Replace the bare concatenation with a canonical, unambiguous serialization before signing. The standard tool is length-prefixing: encode each field as len(field) || field (for example a fixed-width 4-byte big-endian length followed by the field bytes) and concatenate those framed fields instead of the raw ones. Because the length is bound to the field, no rearrangement of byte boundaries can produce the same framed string from a different set of field values. Equivalent alternatives are a canonical structured encoding (protobuf, CBOR (Concise Binary Object Representation, a compact binary JSON-like encoding), or JSON with a fixed key order and no field values that can contain the delimiter) or a fixed-width encoding, if the field domains are bounded (a Unix timestamp always fits a fixed number of digits, for instance).
Backward compatibility. Changing the wire format breaks verification for anything already relying on the old bare concatenation. In practice this needs: an explicit scheme-version byte or field carried alongside the signature (so verifiers can tell old-format signatures from new-format ones and apply the matching canonicalization), a dual-verify window where the service accepts both formats while clients and stored signatures migrate, and an expiry date after which the old, ambiguous format is rejected outright. Anything that pre-signed messages under the old scheme (queued jobs, long-lived tokens, offline-signed batches) has to be re-signed or grandfathered explicitly rather than silently reinterpreted, because reinterpreting old bytes under the new canonicalization rules is exactly the kind of parsing ambiguity this fix is trying to eliminate.
Worked example
Two field sets that collide under the naive scheme:
Set A: user="bob", timestamp="1699999999", amount="50"
Set B: user="bob1", timestamp="699999999", amount="50"
import hmac, hashlib
KEY = b"pinned-demo-key"
def sign(user, timestamp, amount):
message = user + timestamp + amount
return message, hmac.new(KEY, message.encode(), hashlib.sha256).hexdigest()
concat_a, sig_a = sign("bob", "1699999999", "50")
concat_b, sig_b = sign("bob1", "699999999", "50")
print("concat_a == concat_b:", concat_a == concat_b, " sig_a == sig_b:", sig_a == sig_b)
print("sig_a:", sig_a)
def sign_fixed(user, timestamp, amount):
def framed(field):
b = field.encode()
return len(b).to_bytes(4, "big") + b
message = framed(user) + framed(timestamp) + framed(amount)
return message, hmac.new(KEY, message, hashlib.sha256).hexdigest()
fixed_a = sign_fixed("bob", "1699999999", "50")
fixed_b = sign_fixed("bob1", "699999999", "50")
print("framed_a == framed_b:", fixed_a[0] == fixed_b[0], " sig_a == sig_b (fixed):", fixed_a[1] == fixed_b[1])
print("sig_a (fixed):", fixed_a[1])
print("sig_b (fixed):", fixed_b[1])
Running this prints concat_a == concat_b: True sig_a == sig_b: True: concat_a and concat_b are both the literal string "bob169999999950", and the HMAC (Hash-based Message Authentication Code, a keyed construction that turns a hash function into a tag only someone holding the secret key can produce) over them is bit-for-bit identical, 7fdf7a5e9f5a0c17391868dc99f7d4e59733e01f508be32f9c136b9f62200475 in both cases. Applying the length-prefix fix flips both results to False: the framed messages differ (the length prefix on "bob" versus "bob1" diverges immediately), and the two signatures come out different, e6c2dcc3ce33b7eb3403189d7b8451905a8b53568145d06d2efa4e0494609c24 versus 2e4a6a43def8267dfb655fe02e3618d5a76d483773b7cb6f7b2c3eca923c229e.
Trade-offs and pitfalls
Length-prefixing is cheap and fully general but is not the only valid fix: a structured, canonical encoding buys the same guarantee and often better tooling support (schema validation, cross-language libraries), at the cost of a heavier format. A single separator character (like |) is a tempting shortcut but only works if the field values are guaranteed never to contain that character; if user can ever include a pipe, you have reinvented the same ambiguity one layer down. The migration is the part most teams underestimate: it is easy to fix the signer and forget that every downstream verifier, cached signature, or replayable message needs to agree on which format it is looking at, and a silent format-detection heuristic (guessing whether a message is old or new style) reintroduces exactly the kind of ambiguity you were trying to remove.
Discuss the security implications of truncating HMAC tags (for example, using a 64-bit tag instead of full output) in network protocols and APIs. How does truncation affect forgery probability, replay considerations, bandwidth, and latency? How would you select an appropriate truncation length for a given threat model?
Sample Answer
Direct answer
Truncating an HMAC tag (message authentication code, a keyed hash-based tag proving both integrity and possession of a shared secret) from its full output down to t bits raises the probability a blind forgery guess succeeds from roughly 2^-full_length to roughly 2^-t, in exchange for (full_length - t) / 8 fewer bytes on the wire per message. Whether that trade is acceptable depends entirely on how many forgery attempts an attacker can realistically make before the protocol notices and locks them out; t has to be chosen so that even an attacker allowed billions of attempts still faces a negligible cumulative success probability, not just an individually-small per-attempt one.
Structured elaboration
- Forgery probability, precisely: a single blind guess at a
t-bit tag succeeds with probability2^-tif the MAC is a good pseudorandom function (an attacker with no better strategy than guessing). This is NOT the birthday bound (the general fact, familiar from the "birthday paradox", that finding ANY two colliding items in a large set becomes likely after checking only around the square root of the set's size: in a room of just 23 people there is better-than-even odds two share a birthday, far fewer than the 365 you might expect, because every person is being compared against every OTHER person, not against one fixed target). Unlike collision-finding, forging one specific tag for one specific message does not benefit from that birthday-style square-root speedup, because there is no set of many items being compared against each other here, only many independent guesses against ONE fixed target tag; it only benefits from making more independent guesses, exactly the cumulative-probability calculation below. - Cumulative probability across many attempts: if an attacker is allowed
Nverification attempts before being rate-limited or the key rotates, the chance at least one succeeds is1 - (1 - 2^-t)^N, which for small2^-t * Nis well approximated byN * 2^-t. A truncation length is "safe" for a given deployment when this cumulative figure stays negligible across the LARGESTNa realistic attacker could reach, not just across one guess. - Bandwidth and latency: truncation is a pure win here, since a shorter tag means fewer bytes per authenticated message; this matters for high-frequency small-packet protocols (real-time telemetry, constrained IoT links) where tag overhead is a meaningful fraction of packet size.
- Replay considerations: truncation does not by itself weaken replay protection or strengthen it. Replay resistance comes from a nonce, counter, or timestamp bound into the MAC input, entirely independent of how many bits of the resulting tag get transmitted; a truncated tag over a well-formed, freshness-bound input is exactly as replay-resistant as a full-length one.
- Selecting a length for a threat model: fix an acceptable ceiling on cumulative forgery probability (a common engineering target is keeping it below roughly
2^-32to2^-40over the maximum attempts the deployment's rate-limiting genuinely bounds), then solve fortgiven the realistic maximumN:t >= log2(N) + target_security_margin. NIST SP 800-107 recommends never truncating below 32 bits and prefers at least 64 bits unless the protocol independently boundsNvery tightly (e.g. a hard rate limiter that locks out a key after a handful of failures).
Worked example
Take a 64-bit truncated tag (t = 64) in a protocol whose rate limiter permits at most N = 2^20 (about one million) verification failures before locking the key: cumulative forgery probability is approximately N * 2^-t = 2^20 * 2^-64 = 2^-44, comfortably negligible. Now suppose the SAME 64-bit tag protects an API endpoint with no meaningful rate limiting, where a botnet can realistically attempt N = 2^40 (about one trillion) forgeries: cumulative probability rises to 2^40 * 2^-64 = 2^-24, which is uncomfortably close to something a well-resourced or lucky attacker could hit, and no longer negligible by most engineering standards. The tag length that was "fine" in the first deployment is undersized for the second purely because of how weakly attempts are bounded, not because anything about the MAC itself changed.
Trade-offs and pitfalls
- The single biggest mistake is picking a truncation length in isolation from the deployment's actual rate-limiting story;
t = 64is safe behind a strict lockout and unsafe behind none. - Truncation interacts badly with a MAC verification bug: if tag comparison is not constant-time (does not take the same code path regardless of where two byte strings first differ), a SHORTER tag also means fewer bytes an attacker needs to brute-force byte-by-byte via a timing oracle, compounding two separate weaknesses.
- Never derive the truncation length from "what feels short enough to save bandwidth" without first fixing the target cumulative-forgery-probability ceiling and the realistic attempt bound; the length is a consequence of those two numbers, not an independent design choice.
Unlock Full Question Bank
Get access to all 19 Cryptographic Hashing and Digital Signatures interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.