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 team is evaluating a new, non-standard hash function proposed for internal use instead of a NIST-standardized algorithm. What would you want to see before signing off on it, and what is the bar for approving it internally versus waiting for it to go through external standardization?
Sample Answer
Direct answer
Before signing off on a non-standard hash function for internal use, I want to see published, peer-reviewed cryptanalysis with no known practical attack, a formal security argument or proof sketch relating it to a well-studied hard problem, published test vectors and a reference implementation independent of the proposer, and years, not months, of public scrutiny from people actively trying to break it. The internal-approval bar should be much narrower than "we reviewed it and it looks fine": approve it only for a tightly scoped, explicitly non-security-critical use case, with a mandatory re-evaluation date, and never as a substitute for an algorithm standardized by NIST (the National Institute of Standards and Technology, the US body that ran the SHA-3 competition below) or ISO (the International Organization for Standardization) anywhere the failure mode is exploitable by an external adversary.
Structured elaboration
What to look for before any sign-off. A candidate hash function needs, at minimum: a public specification detailed enough for independent implementation; published cryptanalysis attempts (ideally from more than one independent research group) with no known collision, preimage, or distinguishing attack better than generic (birthday-bound) attacks; a security argument connecting its design to established primitives or hard problems, even if not a full formal proof; independently-produced test vectors that a from-scratch implementation can be checked against; and, ideally, participation in or comparison against a public competition process (the NIST SHA-3 competition is the reference model: five years of public, adversarial cryptanalysis across dozens of competing submissions, from the 2007 call for submissions to the Keccak selection in 2012, before the standard was finalized as FIPS 202 in 2015).
The internal-versus-external bar, and why they should differ. External standardization (NIST, ISO) exists precisely because no single team, however competent, can replicate years of adversarial, multi-team cryptanalysis internally. An internal review board can meaningfully assess implementation quality, side-channel behavior in your specific deployment, and whether the DESIGN RATIONALE is sound, but it cannot substitute for the thing external standardization actually buys: time and adversarial diversity. So the correct internal bar is not "is this as good as SHA-256," it's "is the SCOPE of harm from being wrong here small enough to accept the residual risk of unproven cryptanalysis." Concretely: approving a non-standard hash for an internal deduplication index, where a future collision would cause an incorrect dedup decision but nothing security-critical, is a defensible narrow approval; approving the same hash for anything touching authentication, integrity of externally-facing data, or code signing is not, regardless of how good the internal review looked, because the blast radius of being wrong is unbounded in exactly the cases external standardization is designed to guard against.
What a defensible internal approval requires. Explicit written scope limits (which systems, which data, which failure consequence is accepted); a named re-evaluation cadence (say, annually, or immediately upon any new published cryptanalysis against the algorithm); a migration plan ready to execute if a weakness is found, not one to be improvised after the fact; and sign-off from whoever owns cryptographic risk for the organization, not just the team that wants to use it.
Worked example
The concrete reference case for "how long is long enough" is the SHA-3 (Keccak) selection process: NIST opened the competition to public cryptanalysis in 2007, spent five years of adversarial attacks against dozens of competing submissions before selecting Keccak as the winner in 2012, and then took three more years of further scrutiny before finalizing the standard as FIPS 202 in 2015, specifically to let the field of cryptanalysts attack every candidate for years before any of them were trusted for general use, even though Keccak's sponge construction was, from early on, considered a strong design by its authors and many reviewers. If a five-year public competition among dozens of expert teams was the bar the industry set just to pick a winner, with years of further standardization scrutiny still to come after that, an internal review by one team, however skilled, is not a substitute for that process; it's a different, narrower kind of assurance, appropriate only for a narrower kind of risk.
Trade-offs and pitfalls
The most common failure mode here is treating "our internal review didn't find anything wrong" as equivalent to "this has been shown safe," when the honest position is "we did not find a weakness in the time we had, which is much weaker evidence than years of adversarial public attention." A second pitfall is scope creep: an algorithm approved narrowly for internal deduplication quietly ends up used for something security-adjacent a year later because no one revisited the original scope limits; the mandatory re-evaluation cadence and written scope are what prevent that, not goodwill. Performance or licensing advantages are legitimate reasons to WANT a non-standard hash, but they are never a substitute for the cryptanalytic evidence itself, and a review process that lets performance urgency compress the evaluation timeline is exactly how weak algorithms end up load-bearing.
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.
Your team is migrating a legacy signing library from RSA PKCS#1 v1.5 to RSA-PSS. Why is this considered a security improvement, what specifically was wrong with the old scheme's determinism, and what verification checks does your new implementation need to get right to avoid introducing a vulnerability during the migration?
Sample Answer
Direct answer
RSA-PSS (Probabilistic Signature Scheme) is a security improvement over PKCS#1 v1.5 (the older RSA signature padding standard, part of the Public-Key Cryptography Standards series) primarily because it has a tight, formal security proof (Bellare and Rogaway, 1996) reducing forgery to the RSA problem itself, while PKCS#1 v1.5's padding is ad hoc, standard practice without an equivalent proof. The old scheme's determinism isn't itself the core vulnerability the way a reused per-signature random value is for Elliptic Curve DSA (ECDSA, a different signature algorithm where nonce reuse directly leaks the private key); the real problem is that its rigid, fixed padding structure created real, exploitable forgery surface in verifiers that checked the padding loosely, most famously Bleichenbacher's 2006 low-exponent forgery. Migrating safely means the new verifier has to check the ENTIRE encoded block PSS produces, not just a recognizable prefix, or you've reintroduced the same class of bug in a new format.
Structured elaboration
Why PSS is the improvement. PSS embeds a random salt into the padded block for every signature, via a Mask Generation Function (MGF1, a hash-based function that expands a short input into an arbitrary-length pseudorandom mask), so the exact padded bytes differ signature to signature even for the identical message, and the whole padded block is what verification reconstructs and checks, leaving no room for "recognize the prefix and ignore the rest" shortcuts. Its provable-security reduction is not a formality: it says that ANY successful forgery against PSS (in the random-oracle model, an idealized proof setting where the hash function is treated as a perfect black box that returns a fresh, unpredictable output for every distinct input, so the proof can reason about the scheme's security without depending on any specific hash's actual internal design) can be converted into an algorithm that breaks the underlying RSA problem itself, which PKCS#1 v1.5's construction never had.
What was actually wrong with the old scheme. PKCS#1 v1.5 signature padding is 0x00 0x01 [0xFF padding] 0x00 [ASN.1 (Abstract Syntax Notation One, a standard format for describing structured data) DigestInfo encoding the hash algorithm OID, or Object Identifier] [hash]. Determinism per se (same message, same key, always the same signature) is not dangerous for a SIGNATURE the way it is for encryption or an ECDSA nonce; the actual defect was that many real implementations verified this structure loosely, checking that the padded block STARTED with the right prefix and hash, without confirming the 0xFF padding filled the ENTIRE remaining space up to the modulus boundary with no trailing garbage. Bleichenbacher's 2006 attack exploited exactly this: for a small public exponent like e=3, an attacker can construct a value whose approximate cube root has the correct PKCS#1 v1.5 prefix and a large, uncontrolled suffix, forging a valid-looking signature without ever touching the private key, purely because the verifier's parser was too permissive. Multiple real libraries (including implementations affecting Java, stacks built on NSS, Mozilla's Network Security Services cryptography library, and others reported over the following years) had exactly this parsing bug.
Verification checks the migration has to get right. Per RFC 8017's EMSA-PSS-VERIFY procedure: (1) confirm the salt length matches the expected, fixed convention for the deployment (commonly equal to the hash's output length) rather than accepting any salt length the signature happens to carry; (2) confirm the hash used for the message digest and the hash used inside MGF1 are the SAME algorithm the verifier expects, an algorithm-confusion mismatch between the two would silently weaken the security argument; (3) check the trailer byte (0xBC) and the top bits of the masked data block exactly as specified, not approximately; (4) reject anything where the encoded message length doesn't precisely match the expected bit length for the modulus, no "close enough" tolerance; (5) during the migration window, support BOTH schemes with an explicit algorithm identifier carried alongside each signature, since a verifier cannot safely infer which padding scheme was used from the signature bytes alone.
Worked example
The concrete shape of the bug PSS closes: a PKCS#1 v1.5 verifier that only checks the DECODED value STARTS WITH 0x00 0x01 0xFF...0xFF 0x00 <DigestInfo> <hash> and never confirms there's nothing else after the hash up to the full modulus width will accept a forged value whose low-order bits (which a small-exponent cube root leaves attacker-controllable) are garbage the checker never looked at. PSS's verification instead reconstructs the ENTIRE mask from the recovered salt and re-derives the full expected block; there is no "prefix-only" shortcut available to a lazy or buggy implementation, because the salt makes every byte of the padded block depend on the signature itself, not on a fixed, guessable structure.
Traced with real bytes: a small (illustrative-only, not a secure key size) 2047-bit RSA key with public exponent e=3, the exact setting that makes Bleichenbacher's forgery cheap, since it turns into one integer cube root instead of a search:
import hashlib, random
random.seed(42) # fixes the Miller-Rabin witness draws too, for a fully reproducible run
# ---------- small (illustrative-only) ~2048-bit RSA key with e=3 ----------
def is_probable_prime(n, rounds=20):
if n < 2:
return False
for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31):
if n % p == 0:
return n == p
d, r = n - 1, 0
while d % 2 == 0:
d //= 2
r += 1
for _ in range(rounds):
a = random.randrange(2, n - 1)
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
def gen_prime(bits, seed):
rng = random.Random(seed)
while True:
cand = rng.getrandbits(bits) | (1 << (bits - 1)) | 1
if cand % 3 == 2 and is_probable_prime(cand): # p % 3 == 2 guarantees gcd(3, p-1) == 1
return cand
p = gen_prime(1024, seed=1001)
q = gen_prime(1024, seed=2002)
n = p * q
phi = (p - 1) * (q - 1)
e = 3
d = pow(e, -1, phi)
MOD_BYTES = (n.bit_length() + 7) // 8
print("modulus bit length:", n.bit_length(), "-> MOD_BYTES:", MOD_BYTES)
# DigestInfo prefix for SHA-256 per RFC 8017 / PKCS#1
DIGESTINFO_SHA256 = bytes.fromhex("3031300d060960864801650304020105000420")
def pkcs1v15_encode(message: bytes) -> bytes:
digest = hashlib.sha256(message).digest()
T = DIGESTINFO_SHA256 + digest
ps_len = MOD_BYTES - 3 - len(T)
assert ps_len >= 8
return b"\x00\x01" + b"\xff" * ps_len + b"\x00" + T
def pkcs1v15_sign(message: bytes) -> int:
em = pkcs1v15_encode(message)
return pow(int.from_bytes(em, "big"), d, n)
def strict_verify(message: bytes, sig: int) -> bool:
em_check = pow(sig, e, n).to_bytes(MOD_BYTES, "big")
return em_check == pkcs1v15_encode(message)
def loose_verify(message: bytes, sig: int) -> bool:
# VULNERABLE parser: walks 0x00 0x01, THEN however many 0xFF bytes are
# actually present (accepting >= 8, the spec minimum), THEN 0x00, THEN
# the expected DigestInfo+hash -- but never checks that the buffer ENDS
# there. Real Bleichenbacher-class bugs looked exactly like this.
em_check = pow(sig, e, n).to_bytes(MOD_BYTES, "big")
if em_check[0:2] != b"\x00\x01":
return False
idx, ff_count = 2, 0
while idx < len(em_check) and em_check[idx] == 0xFF:
idx += 1
ff_count += 1
if ff_count < 8 or idx >= len(em_check) or em_check[idx] != 0x00:
return False
idx += 1
target = DIGESTINFO_SHA256 + hashlib.sha256(message).digest()
return em_check[idx:idx + len(target)] == target # <-- never checks idx+len(target) == len(em_check)
msg = b"transfer $10 to alice"
sig = pkcs1v15_sign(msg)
em_genuine = pkcs1v15_encode(msg)
print("\ngenuine EM (hex, first 40 bytes):", em_genuine[:40].hex())
print("genuine EM length:", len(em_genuine), "bytes")
print("strict_verify(genuine sig):", strict_verify(msg, sig))
print("loose_verify(genuine sig):", loose_verify(msg, sig))
# ---------- Bleichenbacher-style forgery: NO private key used ----------
def iroot(x: int, k: int) -> int:
if x == 0:
return 0
lo, hi = 0, 1
while hi ** k <= x:
hi <<= 1
while lo < hi:
mid = (lo + hi + 1) // 2
if mid ** k <= x:
lo = mid
else:
hi = mid - 1
return lo
digest = hashlib.sha256(msg).digest()
prefix = b"\x00\x01" + b"\xff" * 8 + b"\x00" + DIGESTINFO_SHA256 + digest # 2+8+1+51 = 62 bytes
garbage_bytes = MOD_BYTES - len(prefix)
print("\nprefix length:", len(prefix), "bytes; attacker-controlled garbage suffix:", garbage_bytes, "bytes")
prefix_int = int.from_bytes(prefix, "big")
target_lo = prefix_int << (garbage_bytes * 8)
target_hi = (prefix_int + 1) << (garbage_bytes * 8)
s_forged = iroot(target_hi - 1, 3)
while s_forged ** 3 < target_lo:
s_forged += 1
assert target_lo <= s_forged ** 3 < target_hi, "no cube landed in the target window (need a larger modulus/more garbage room)"
assert s_forged ** 3 < n # pure integer cube root, no modexp: nothing here ever used d
em_forged = (s_forged ** 3).to_bytes(MOD_BYTES, "big")
print("forged EM (hex, first 40 bytes): ", em_forged[:40].hex())
print("forged EM (hex, last 20 bytes, attacker garbage):", em_forged[-20:].hex())
print("forged EM's first 62 bytes hit the exact target prefix:", em_forged[:62] == prefix)
print("target prefix ends with the real DigestInfo+hash of msg:", prefix.endswith(DIGESTINFO_SHA256 + digest))
print("strict_verify(forged sig, no private key, no d used anywhere):", strict_verify(msg, s_forged))
print("loose_verify(forged sig, no private key, no d used anywhere):", loose_verify(msg, s_forged))
Output:
modulus bit length: 2047 -> MOD_BYTES: 256
genuine EM (hex, first 40 bytes): 0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
genuine EM length: 256 bytes
strict_verify(genuine sig): True
loose_verify(genuine sig): True
prefix length: 62 bytes; attacker-controlled garbage suffix: 194 bytes
forged EM (hex, first 40 bytes): 0001ffffffffffffffff003031300d06096086480165030402010500042045438557ecd09550923d
forged EM (hex, last 20 bytes, attacker garbage): 01f2dcec1b19f06d48f492c8ddd72962eb992405
forged EM's first 62 bytes hit the exact target prefix: True
target prefix ends with the real DigestInfo+hash of msg: True
strict_verify(forged sig, no private key, no d used anywhere): False
loose_verify(forged sig, no private key, no d used anywhere): True
The genuine signature's decoded block passes both the strict, spec-correct check and the loose, prefix-only check, as expected. The forged block is built with NO private key anywhere (s_forged is a pure integer cube root of a crafted target; d is never referenced), and it passes ONLY the loose check: its first 62 bytes land exactly on the required 0x00 0x01, eight 0xFF bytes, the 0x00 separator, and the real DigestInfo-plus-hash for the message, while its last 194 bytes are attacker-chosen garbage that a spec-correct verifier rejects on sight but a loose 'starts with the right prefix' verifier never inspects. PSS closes exactly this gap: there is no fixed prefix to imitate this way, because the salt makes the ENTIRE recovered block, not just its opening bytes, depend on the real signature.
Trade-offs and pitfalls
A common wrong turn is explaining this migration purely in terms of "determinism is bad, randomness is good," which is the right intuition for ECDSA nonces but the wrong causal story here; PSS's randomization does add a defense-in-depth benefit (a deterministic scheme gives an attacker a single fixed target to attack across many observed signatures, per-signature randomization removes that), but the PRIMARY improvement is the formal security proof and the elimination of the loose-parsing forgery surface, not randomness for its own sake. A second pitfall during migration: reusing the same RSA keypair across both schemes is generally considered acceptable for signing, but the migration still needs an explicit algorithm tag on every signature, silently trying "verify as PSS, fall back to verify as PKCS#1 v1.5" without an explicit tag reopens exactly the kind of format-confusion ambiguity this whole migration is meant to close.
Explain why using H(secret || message) as a MAC is insecure when the hash is a Merkle–Damgård construction (e.g., MD5/SHA-1) and describe the length-extension attack. Show the attack idea and then explain how HMAC fixes it, including why HMAC resists length-extension and what properties of the underlying hash it relies on.
Sample Answer
Direct answer
H(secret || message) is insecure as a MAC (Message Authentication Code) when H is a Merkle-Damgard hash, because a Merkle-Damgard digest literally IS the hash's complete internal state at the moment processing stopped. Anyone who sees that digest can resume hashing from that exact state and feed in more data, computing a valid hash for a longer message whose secret prefix they never saw. This is the length-extension attack. HMAC (Hash-based Message Authentication Code) fixes it by nesting two keyed hash computations, so the value an attacker could mechanically "extend" is never the value the verifier actually recomputes.
Structured elaboration
Merkle-Damgard construction. MD5, SHA-1, and SHA-256 (part of the SHA, Secure Hash Algorithm, family) all build a hash over arbitrary-length input the same way: split the padded message into fixed-size blocks, run each block through a compression function that mixes it into a running state, and output whatever that state equals after the last block. Padding is standardized (a delimiter bit, zero bytes, and an encoded bit-length field) so the final block is unambiguous.
The attack idea. Suppose MAC = H(secret || message). An attacker who knows message and the tag also effectively knows the hash's internal state right after processing (secret || message), because that state IS the tag. They can:
- Guess or brute-force the length of secret (often narrow, since key sizes are frequently fixed).
- Compute glue, the exact padding H would have appended after (secret || message) at that guessed length. This only depends on the length, never on the secret's actual bytes.
- Resume hashing from the leaked state (the tag) and continue compressing an attacker-chosen suffix, applying the standard padding rules again for the new, longer total length.
- The result is a valid H(secret || message || glue || suffix), computed without ever knowing secret.
- The attacker sends (message || glue || suffix) with the forged tag; a server that naively recomputes H(secret || received_bytes) accepts it, because the values genuinely match.
Why HMAC resists it.
HMAC(K,m)=H((K⊕opad)∥H((K⊕ipad)∥m))The tag the attacker sees is the output of the OUTER hash call. It's true that the attacker can mechanically continue that outer computation, since the length of its input (a block-size padded key plus one inner digest) is fixed and publicly known, so the padding is computable without secret knowledge. But doing so computes H((K xor opad) || inner || glue || suffix), a hash of a specific, longer byte string. That is simply not the string the verifier ever hashes. Verification always recomputes HMAC(K, candidate_message) from scratch: a brand-new inner hash over (K xor ipad || candidate_message), then a brand-new outer hash over (K xor opad || that fresh inner digest). Those two computations diverge from the attacker's extension as soon as the candidate message differs at all, so the extended value never equals what verification checks, regardless of whether the attacker can mechanically compute it.
Properties HMAC relies on. The proof needs the compression function to behave unpredictably once keyed, formally requiring H (when used the way HMAC uses it) to act like a PRF (pseudorandom function), plus the structural fact that the inner hash's output is a short, fixed-length value with no byte-for-byte relationship to any message an attacker would need to forge.
Worked example
A real MD5/SHA-256 implementation doesn't expose a "resume from this state" API, so here is a small, from-scratch Merkle-Damgard hash built specifically to demonstrate the exact structural mechanism (padding, state-as-digest, resumability) that also applies to MD5, SHA-1, and SHA-256 in production.
MASK64 = (1 << 64) - 1
IV = 0xCBF29CE484222325
BLOCK = 16
ODD_CONST = 0xBF58476D1CE4E5B9
def rotl64(x, r):
return ((x << r) | (x >> (64 - r))) & MASK64
def compress(state, block):
w0 = int.from_bytes(block[:8], 'big')
w1 = int.from_bytes(block[8:], 'big')
x = state ^ w0
x = rotl64(x, 17)
x = (x + w1) & MASK64
x ^= rotl64(x, 31)
x = (x * ODD_CONST) & MASK64
x ^= (state >> 7)
return x & MASK64
def md_pad(local_len, total_len_bytes):
pad = b'\x80'
while (local_len + len(pad)) % BLOCK != BLOCK - 8:
pad += b'\x00'
pad += (total_len_bytes * 8).to_bytes(8, 'big')
return pad
def H(message):
padded = message + md_pad(len(message), len(message))
state = IV
for i in range(0, len(padded), BLOCK):
state = compress(state, padded[i:i+BLOCK])
return state.to_bytes(8, 'big')
def H_resume(state_bytes, processed_len, tail):
state = int.from_bytes(state_bytes, 'big')
total_len = processed_len + len(tail)
padded_tail = tail + md_pad(len(tail), total_len)
for i in range(0, len(padded_tail), BLOCK):
state = compress(state, padded_tail[i:i+BLOCK])
return state.to_bytes(8, 'big')
def hmac_toy(key, message):
if len(key) > BLOCK:
key = H(key)
key = key.ljust(BLOCK, b'\x00')
ipad = bytes(b ^ 0x36 for b in key)
opad = bytes(b ^ 0x5c for b in key)
inner = H(ipad + message)
return H(opad + inner)
secret = b'k3y-unknown-to-attacker'
message = b'user=alice&amount=10'
suffix = b'&admin=true'
# 1. naive MAC = H(secret || message): forgeable
naive_mac = H(secret + message)
guessed_len = len(secret) + len(message)
glue = md_pad(guessed_len, guessed_len)
forged = H_resume(naive_mac, guessed_len + len(glue), suffix)
server_side_naive = H(secret + message + glue + suffix)
print('naive MAC =', naive_mac.hex())
print('forged (length-extended) MAC =', forged.hex())
print('server recomputes to =', server_side_naive.hex())
print('naive MAC forgery accepted? =', forged == server_side_naive)
# 2. same trick against HMAC-style construction: fails
tag = hmac_toy(secret, message)
outer_input_len = BLOCK + 8 # fixed: padded key + one digest, regardless of message length
naive_ext_of_tag = H_resume(tag, outer_input_len, suffix)
real_hmac_of_extended_message = hmac_toy(secret, message + suffix)
print('HMAC(K, message) =', tag.hex())
print('naive extension of the HMAC tag =', naive_ext_of_tag.hex())
print('real HMAC(K, message+suffix) =', real_hmac_of_extended_message.hex())
print('HMAC forgery accepted? =', naive_ext_of_tag == real_hmac_of_extended_message)
Output:
naive MAC = 30d840639d174d72
forged (length-extended) MAC = f3e85087bb9b1a3c
server recomputes to = f3e85087bb9b1a3c
naive MAC forgery accepted? = True
HMAC(K, message) = 6c71eb8f8d2ae6ea
naive extension of the HMAC tag = 1ca1d95df1f503e9
real HMAC(K, message+suffix) = 860b4a1b8ed8024b
HMAC forgery accepted? = False
The naive construction accepts the forgery outright. The HMAC-style construction lets the attacker mechanically compute an extension of the tag, but that value simply doesn't match what real verification checks, exactly as the reasoning above predicts.
Trade-offs and pitfalls
- SHA-3, built on a sponge construction rather than Merkle-Damgard, does not expose its full internal state through its digest, so plain H(secret || message) with SHA-3 is not vulnerable to this specific attack. That is not a reason to skip a dedicated MAC construction: use HMAC, or a sponge-native keyed mode, since ad hoc MAC constructions have a long history of other subtle breaks even when length-extension isn't one of them.
- A common near-miss: H(message || secret), with the secret at the end instead of the start, is not vulnerable to this specific length-extension attack, but it inherits other weaknesses (for instance, if H has any known collision between message1 and message2, then H(message1 || secret) equals H(message2 || secret) for any secret). "Not vulnerable to length-extension" is not the same claim as "secure"; use HMAC either way.
- Don't try to patch this by hiding the secret's length. Attackers can often infer or brute-force it from context, such as a fixed-size API key, so security must never depend on length secrecy.
Compare SHA-256, SHA-3, and BLAKE2 for a new cloud service that needs fast content hashing and occasional authenticated signing. Walk through the internal design differences that matter for your choice, how they affect performance in software and hardware, and which one you'd pick and why.
Sample Answer
Direct answer
For a cloud service that needs fast content hashing with occasional authenticated signing, I'd pick BLAKE2 as the primary workhorse: it's designed specifically for high software throughput and offers a native keyed mode that covers the occasional-signing need without a separate wrapper construction. SHA-256 (part of the SHA, Secure Hash Algorithm, family) stays valuable where hardware acceleration or broad interoperability matters more than raw software speed, and SHA-3 is worth reaching for specifically when structural diversity from SHA-2 is itself a requirement, not just a nice-to-have.
Structured elaboration
Internal design. SHA-256 is a Merkle-Damgard construction using Davies-Meyer compression (each step runs the running state through a block-cipher-like function keyed by that message block, then XORs, or "feeds forward," the original input state back into the result; that feed-forward is specifically what turns an otherwise-invertible cipher-like step into a one-way compression function): a sequential running state, processed block by block, with the final state as the output. This is exactly the structure that makes plain H(secret || message) vulnerable to length-extension unless wrapped in HMAC (Hash-based Message Authentication Code). SHA-3 (Keccak) is a completely different family, built on a sponge construction: input is absorbed into a large internal state, then output is squeezed back out; because the digest doesn't reveal the FULL internal state, SHA-3 doesn't have the length-extension weakness by construction, independent of any external MAC wrapper. BLAKE2 descends from BLAKE, a SHA-3 competition finalist, and uses an ARX (add-rotate-xor) permutation in the spirit of ChaCha, layered with an explicit block counter and optional salt and personalization inputs that also close the length-extension weakness structurally, by a different route than SHA-3's.
Performance in software versus hardware. SHA-256 benefits enormously from dedicated hardware acceleration available on many modern CPUs, and is extremely fast when that hardware path exists, but is comparatively slower in pure software on hardware lacking it. SHA-3's sponge permutation suits hardware implementations well (compact circuits, flexible security and speed trade-offs via its rate and capacity split, where "rate" is the portion of the sponge's fixed-width internal state that gets absorbed from input and squeezed out as output each round, controlling speed, and "capacity" is the remaining portion that input and output never touch and that holds the security margin, so widening the rate speeds things up while widening the capacity strengthens security, each at the other's expense), but tends to be the slowest of the three in general-purpose software absent dedicated hardware. BLAKE2 was explicitly designed to outperform SHA-256 in pure software on ordinary CPUs, using fewer, SIMD-friendly operations per byte, without requiring any special hardware support.
Security posture. All three currently have no practically exploitable collision or preimage attacks; their cryptanalytic status is "actively studied and currently unbroken," not "mathematically proven safe forever." SHA-3's structural break from Merkle-Damgard is often cited as valuable algorithmic diversity: SHA-2 and SHA-3 don't share the same internal design, so a future attack targeting one family's specific weaknesses wouldn't automatically threaten the other, a real operational hedge for infrastructure that wants to survive a hypothetical break in one family without a full re-architecture.
Signature-relevance for this scenario. Since the scenario needs occasional authenticated signing too, BLAKE2's native keyed mode gives a fast, standardized way to do keyed hashing directly, without strictly requiring a separate HMAC wrapper (an HMAC-BLAKE2 construction also exists and works fine if a standard MAC construction is specifically required by policy). Both SHA-256 and SHA-3 rely on HMAC, or for SHA-3 the standardized KMAC construction, for keyed use; BLAKE2's built-in support is a genuine, primitive-level convenience the other two don't offer natively.
Worked example
import hashlib
msg = b'content-hash-me-2026'
print('SHA-256 :', hashlib.sha256(msg).hexdigest())
print('SHA3-256 :', hashlib.sha3_256(msg).hexdigest())
print('BLAKE2b :', hashlib.blake2b(msg, digest_size=32).hexdigest())
print('BLAKE2b keyed (native MAC mode):', hashlib.blake2b(msg, digest_size=32, key=b'shared-key').hexdigest())
Output:
SHA-256 : f270702f24908a9f078e6c6c57d5813acb794f78f960718848c1902aca9b32ff
SHA3-256 : 0c931d3ab755f76c1b435f6a3c004e567f353cf7f8b704862cfef485e5a3ab6e
BLAKE2b : ce9e18779d6cd1178190f63152108419941372837aaadc67c65d8197897ebe43
BLAKE2b keyed (native MAC mode): 6b59f08957a0f0be63eeb6c16e5ed20c8295ca7aa3b9bba5f688880d6a73968a
All three algorithms are available directly from the same standard library, each producing a distinct 256-bit (32-byte, 64 hex character) digest for the identical input, and BLAKE2's keyed call above demonstrates its native MAC-like mode with no separate construction layered on top. Digest-size comparison across common variants: SHA-256 and SHA3-256 both fix their output at 256 bits; BLAKE2b supports up to 512 bits (optimized for 64-bit platforms) and BLAKE2s supports up to 256 bits (optimized for 8- to 32-bit platforms), so BLAKE2 also offers size flexibility the other two don't.
Trade-offs and pitfalls
- Migrating everything to BLAKE2 purely for speed can hurt interoperability: many external systems, compliance regimes, and existing certificate or signature ecosystems specifically expect SHA-256, so "fastest in software" isn't the only axis that matters once other parties must independently verify your hashes.
- SHA-3's extra safety margin from being structurally different from SHA-2 is a hedge against a specific, so-far-hypothetical risk. Don't pay a real performance cost today for a purely hypothetical future benefit unless your risk tolerance specifically calls for that diversification, such as a long-lived archival signing scheme.
- Keyed BLAKE2 is convenient, but many auditors or compliance frameworks specifically expect a named, standardized MAC construction, HMAC or KMAC, with its own established security proof pedigree. Native keying is a real engineering convenience, not automatically a drop-in replacement for a specifically-mandated construction in a regulated context.
Unlock Full Question Bank
Get access to all 25 Cryptographic Hashing and Digital Signatures interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.