Cryptographic Hashing and Digital Signatures Questions

Direct answer

A length-extension attack exploits the fact that a Merkle-Damgard hash's final digest IS its complete internal state at the moment hashing stopped. Anyone holding that digest can resume hashing from that exact state and process more data, computing a valid hash for a longer message whose prefix they never actually saw. Against a naive MAC (Message Authentication Code) built as MAC = H(key || message), this means an attacker who knows only the digest and the plaintext message, never the key, can still produce a valid tag for (message plus padding plus an attacker-chosen suffix).

Structured elaboration

Merkle-Damgard recap. A message is split into fixed-size blocks after standardized padding: a delimiter bit, zero padding, and an encoded bit-length field. A fixed starting value is compressed together with each block in turn, and the digest is simply whatever the running state equals after the last block. MD5, SHA-1, and SHA-256 (part of the SHA, Secure Hash Algorithm, family) are all built this way.

Why internal state enables forgery. The compression function only needs the CURRENT state plus the next block; it has no memory of how that state was reached. Resuming from a leaked digest is therefore mechanically identical to resuming from any legitimate intermediate state partway through hashing; the hash function itself cannot tell the difference.

Step-by-step forgery against MAC = H(key || message):

1. The attacker observes tag = H(key || message) and the plaintext message. They don't know key, but guess or brute-force its LENGTH, often a narrow search since key sizes are frequently fixed, such as a standard API-key length.
2. They compute glue, the exact padding bytes H would have appended after (key || message) at that guessed total length. This depends only on the length, never on the key's actual content.
3. They set the hash's internal state to tag, the resume step, and continue compressing an attacker-chosen suffix, applying the standard padding rules again but now accounting for the new, longer total length.
4. The result is a valid H(key || message || glue || suffix), computed with zero knowledge of key.
5. The attacker sends (message || glue || suffix) along with the forged tag. A server that naively recomputes H(key || received_bytes) accepts it, because the values genuinely match.

Tooling. Publicly available tools such as hashpump automate steps 1 through 4 against MD5, SHA-1, and SHA-256, searching candidate key lengths and computing the extension automatically, without the attacker writing any hash-internals code themselves.

Worked example

Real MD5 or SHA-256 implementations don't expose a "resume from this state" API directly, so here is a small, from-scratch hash built specifically to demonstrate the exact structural mechanism, the same padding rules and the same digest-equals-final-state property that MD5, SHA-1, and SHA-256 all share in production, without needing to reimplement a full production hash function.

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')

secret = b'k3y-unknown-to-attacker'
message = b'user=alice&amount=10'
suffix = b'&admin=true'

real_mac = H(secret + message)
guessed_secret_len = len(secret)
original_total_len = guessed_secret_len + len(message)
glue = md_pad(original_total_len, original_total_len)
forged_digest = H_resume(real_mac, original_total_len + len(glue), suffix)
forged_message = message + glue + suffix

server_side = H(secret + forged_message)

print('MAC(secret||message)    =', real_mac.hex())
print('forged digest           =', forged_digest.hex())
print('server-recomputed digest=', server_side.hex())
print('forgery accepted?       =', forged_digest == server_side)

Output:

MAC(secret||message)    = 30d840639d174d72
forged digest            = f3e85087bb9b1a3c
server-recomputed digest = f3e85087bb9b1a3c
forgery accepted?        = True

The forged digest, computed with no knowledge of secret at all, matches exactly what the server independently recomputes with the real secret. This is the same mechanism a real attack against MD5, SHA-1, or SHA-256 would use.

Trade-offs and pitfalls

• This answer is deliberately about the ATTACK MECHANICS only. It does not by itself tell you how to fix a naive MAC, since that requires understanding what's structurally different about a properly nested construction, not just concluding "switch to something else."
• Guessing the key length is usually easy in practice, given fixed key sizes or a small brute-forceable range, so "the attacker doesn't know the key" is a much weaker protection than it sounds.
• SHA-3, built on a sponge construction rather than Merkle-Damgard, does not expose its full internal state through its digest the same way, so this specific attack doesn't apply to it. That's a property of the construction, not a blanket guarantee that every SHA-3-based scheme is automatically safe against every other kind of attack.

Direct answer

What broke is collision resistance, not preimage resistance. Given a digest, nobody can efficiently find an input that produces it, and preimage resistance still roughly holds for both MD5 and SHA-1 (part of the SHA, Secure Hash Algorithm, family). But an attacker who gets to choose BOTH inputs in advance can now find two different messages that hash to the same digest, cheaply. That distinction matters because most real attacks, forged certificates and swapped signed files, rely on the attacker preparing both an innocuous version and a malicious version ahead of time and getting only the innocuous one reviewed and signed. That's a collision attack, and collision resistance is exactly the property that broke.

Structured elaboration

Definitions. Preimage resistance: given a digest y, it's hard to find ANY input x with H(x) = y. Second-preimage resistance: given one input x1, it's hard to find a DIFFERENT input x2 with H(x2) = H(x1). Collision resistance: it's hard to find any two distinct inputs x1 and x2, both of the attacker's own choosing, with H(x1) = H(x2). These are three separate guarantees, and a hash function can lose one while keeping the others largely intact.

What actually broke. MD5 fell to practical collision attacks starting in 2004 (Wang et al.). SHA-1 fell to a fully practical, demonstrated collision in 2017 (SHAttered, a joint Google and CWI Amsterdam project). Preimage attacks against both remain computationally infeasible; only collision resistance dropped from its theoretically ideal cost down to something practically achievable using each algorithm's specific internal structural weaknesses, not brute force.

Concrete real-world demonstrations. SHAttered (2017) produced two visually different PDF files with an identical SHA-1 hash, proving SHA-1 collisions were a practical reality rather than a theoretical bound. Nearly a decade earlier, researchers demonstrated a rogue MD5-signed certificate authority certificate (2008): by engineering a collision between a routine, innocuous certificate request and a malicious CA (certificate authority) certificate, they got a real certificate authority to sign the malicious one, since its MD5 digest matched exactly what was actually reviewed and approved.

What it means for a system that still signs with MD5 or SHA-1. Signature schemes typically sign H(m) rather than m directly, precisely for efficiency reasons. A collision attack lets an adversary prepare two messages ahead of time, one innocuous that gets legitimately reviewed and signed, and one malicious that nobody ever sees, and the resulting signature is valid for both, because the signature only ever certified the shared digest, not either specific message. This directly threatens certificate issuance and code-signing, the two contexts where an attacker most benefits from smuggling a different payload past a human or automated review step.

Advice for a team still relying on them.

1. Inventory every place MD5 or SHA-1 is used for anything security-relevant: TLS certificates, code-signing, integrity checks on anything downloaded or executed. Deprioritize purely non-adversarial uses, like a local deduplication cache, relative to these.
2. Migrate every security-relevant use to SHA-256 or stronger immediately, and reissue any certificates or signed artifacts still using MD5 or SHA-1.
3. Treat git's continued internal use of SHA-1 for object naming as a special case, not a template: git added collision detection (a hardened SHA-1 implementation) as a stopgap and has an ongoing SHA-256 migration path, since a full ecosystem-wide hash change is a large undertaking. That git hasn't fully migrated yet doesn't mean git is broadly unsafe today, but it's also not a reason to leave OTHER, unrelated systems unmigrated.

Worked example

The exact computational cost of the SHAttered SHA-1 collision isn't something to state precisely here without a citation-grade source, but the qualitative shape is well established and worth being precise about: a generic collision search against an n-bit hash costs on the order of 2 to the power of n over 2 operations (the birthday bound). SHA-1 produces a 160-bit digest, so a fully generic collision search would cost roughly 2 to the power of 80 operations, computationally far out of reach for essentially any attacker. SHAttered did not do a generic search; it exploited specific differential weaknesses in SHA-1's internal compression function to find a collision at a cost dramatically below that generic bound, which is exactly why "the output is 160 bits, so it should take 2 to the power of 80 to break" turned out to be false in practice: the generic birthday bound is only an upper bound on how hard collision-finding SHOULD be for an ideal random function, and a real algorithm can fall well short of that ideal.

Trade-offs and pitfalls

• "Collision-resistant broke, preimage resistance didn't" is a nuanced state, not a simple binary. A system that only needs preimage resistance, such as one checking a password against a stored hash where the attacker doesn't control both sides, is less urgently exposed than one relying on collision resistance, such as certificates or signatures. "Less urgent" is not "fine": preimage attacks against these constructions have also crept forward over the decades, and 128-bit or 160-bit margins are thin by modern standards regardless.
• A common excuse-shaped mistake: "we truncate, salt, or combine MD5 with something else, so it's fine." Ad hoc combinations of a broken primitive rarely restore the original guarantee cleanly and are hard to reason about formally. The correct fix is migrating to a modern hash function, not patching around the old one.
• Chosen-prefix collisions, a stronger 2020-era refinement of the SHA-1 attack, let an attacker start from TWO ARBITRARY, attacker-chosen prefixes, not just any two random-looking blobs, and still find a collision. That's what makes attacks against a specific, real target practical rather than two arbitrary files simply happening to collide.

Direct answer

Treat a practical hash collision the way you'd treat any critical, cross-product vulnerability: assume it's already being exploited the moment it's confirmed, move fast on detection and downstream notification before public announcement, have a pre-agreed revocation and re-signing path ready rather than improvised, and close the loop with a long-term mitigation that stops this from being a single-point-of-failure again. The plan has five parts: detection, announcement policy, revocation and migration, downstream coordination, and long-term mitigation, in that rough order of urgency.

Structured elaboration

Detection. Before anything else, confirm the collision is practically exploitable, not merely of academic interest (a theoretical attack requiring more compute than exists is a different response than a demonstrated, reproducible break). Check internal systems for artifacts signed or fingerprinted with the affected algorithm: certificate chains, code-signing records, deduplication indices, any place the hash's collision resistance, not just its preimage resistance, was load-bearing. Stand up monitoring for anomalies consistent with exploitation, such as unexpected certificate issuance, signature verification passing for unexpected content, or duplicate-hash entries in integrity-checked stores that shouldn't exist.

Announcement policy. Coordinated disclosure, not silence and not immediate public broadcast. Downstream-affected parties (anyone relying on your signed artifacts, certificates, or integrity checks) need advance notice before the vulnerability becomes public knowledge, on a timeline that gives them a real chance to patch or mitigate, industry norms for this kind of disclosure typically run from a few weeks to a small number of months depending on exploitability and how many parties are affected, coordinated through the same channels used for any critical vulnerability disclosure. Internally, a clear owner (security incident commander) and a single source of truth for status, so engineering, legal, and communications aren't independently improvising what to say.

Revocation and migration of affected artifacts. Every artifact whose integrity depended on the broken hash needs a path to re-establish trust under a stronger algorithm: certificates get revoked (Certificate Revocation List or Online Certificate Status Protocol, whichever the relying parties actually check) and reissued signed with a stronger hash; code-signing artifacts get re-signed; any content-addressed storage keyed by the broken hash needs either a migration to a stronger hash's identifiers (the same object-identifier-versioning problem any Git-style content-addressable store runs into when its hash algorithm changes) or, at minimum, a documented acceptance of residual risk for anything too costly to migrate immediately, with a hard deadline attached, not an open-ended exception.

Coordinating with downstream users. Anyone consuming your signed or hash-verified artifacts, software-development-kit users, partner integrations, customers with pinned certificates, needs an advisory (what's affected, what action is required, by when), a patched client or library if the fix requires client-side changes (accepting new algorithm identifiers, trusting reissued certificates), and a realistic deprecation timeline for the old artifacts rather than an immediate hard cutover that breaks integrations with no warning.

Long-term mitigations. The single most valuable long-term investment is crypto-agility: algorithm identifiers baked into every signed or hashed format from the start, so a future migration is "issue new artifacts under the new identifier and phase out the old one" rather than a flag-day rewrite. Alongside that: active monitoring for weak-algorithm usage across the whole artifact estate (so the NEXT deprecated algorithm doesn't require an inventory exercise from scratch), and a standing deprecation policy with SLAs (service-level agreements, meaning explicit target timeframes) for retiring cryptographic algorithms proactively, ahead of a forced break, rather than only reactively.

Worked example

The concrete reference incident for this exact plan is the 2008 to 2017 industry response to MD5 and then SHA-1 certificate-signing weaknesses: detection came from published cryptanalysis (not an internal discovery, which changes the announcement calculus, since the vulnerability was already public and the clock was already running); the CA/Browser Forum (the industry body that sets the rules Certificate Authorities, or CAs, the trusted parties that sign certificates, must follow) drove the coordinated migration policy across every root program simultaneously, rather than each CA improvising separately; revocation and reissuance happened certificate by certificate over a multi-year deprecation window with hard sunset dates; and Certificate Transparency was stood up partly AS a long-term mitigation, so that a similar future incident (any CA issuing a bad certificate, for any reason) becomes detectable by third parties rather than depending on the CA's own honesty.

Trade-offs and pitfalls

The biggest real-world failure mode in incidents like this is announcing before downstream parties can act, which effectively hands attackers a countdown timer against every organization that hasn't patched yet; the opposite failure, sitting on a confirmed practical collision too long "to avoid panic," is worse, because the vulnerability doesn't stop being exploitable while you deliberate. A second common mistake is treating "revoke and reissue" as the whole plan and skipping the long-term mitigation step; without crypto-agility built in afterward, the next algorithm break repeats the same fire drill from scratch. A third: coordinating with downstream users as an afterthought instead of a parallel workstream from day one, since the technical fix (reissuing certificates) is often the FAST part, and the slow part is getting every downstream consumer to actually adopt the reissued artifacts before the old ones are cut off.

Approach

Use the cryptography library's high-level sign and verify methods with RSA-PSS (Probabilistic Signature Scheme) padding and SHA-256 (part of the SHA, Secure Hash Algorithm, family), letting the library handle the actual RSA and hash math internally. The three parameters that must match exactly between signer and verifier are the message-hash algorithm (SHA-256), the mask-generation function's hash (MGF1 using SHA-256, matching the message hash is the standard convention), and the salt length (here, set equal to the hash's own digest size, 32 bytes, a common recommended default).

from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import padding, rsa

def sign_message_rsa_pss(private_pem: bytes, message: bytes) -> bytes:
    private_key = serialization.load_pem_private_key(private_pem, password=None)
    return private_key.sign(
        message,
        padding.PSS(
            mgf=padding.MGF1(hashes.SHA256()),
            salt_length=hashes.SHA256().digest_size,   # 32 bytes
        ),
        hashes.SHA256(),
    )

def verify_message_rsa_pss(public_pem: bytes, message: bytes, signature: bytes) -> bool:
    public_key = serialization.load_pem_public_key(public_pem)
    try:
        public_key.verify(
            signature, message,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()),
                salt_length=hashes.SHA256().digest_size,
            ),
            hashes.SHA256(),
        )
        return True
    except Exception:
        return False

if __name__ == '__main__':
    key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
    priv_pem = key.private_bytes(serialization.Encoding.PEM, serialization.PrivateFormat.PKCS8, serialization.NoEncryption())
    pub_pem = key.public_key().public_bytes(serialization.Encoding.PEM, serialization.PublicFormat.SubjectPublicKeyInfo)

    message = b"transfer 100 credits to account 42"
    sig = sign_message_rsa_pss(priv_pem, message)
    print("signature length (bytes):", len(sig))
    print("verify(correct message)  :", verify_message_rsa_pss(pub_pem, message, sig))
    print("verify(tampered message) :", verify_message_rsa_pss(pub_pem, message + b"!", sig))

Output:

signature length (bytes): 256
verify(correct message)  : True
verify(tampered message) : False

Key points

• RSA-PSS is a RANDOMIZED padding scheme (a random salt is mixed in through the mask-generation function), unlike the older, deterministic PKCS#1 v1.5 padding; randomization gives PSS a stronger, more modern security proof, and it's the currently recommended RSA signature padding for new systems.
• The private key is loaded once from PEM bytes, and .sign() returns raw signature bytes directly. Verification loads the PUBLIC key and calls .verify(), which RAISES an exception on failure rather than returning a boolean; swallowing that exception incorrectly, or treating "no exception" as the only success signal without confirming verify was actually called, is a common integration mistake.
• Constant-time verification is handled internally by the library, not something the caller needs to implement, unlike a hand-rolled MAC (Message Authentication Code) comparison; never hand-implement RSA padding.

Complexity

RSA sign and verify cost is dominated by modular exponentiation over the key's modulus. For a fixed key size this cost doesn't depend on message length beyond the initial hashing pass, since the message is compressed to a fixed-size digest before any RSA math happens; signing (the private-key operation, using the full-size exponent) is meaningfully more expensive than verifying (the public-key operation, which typically uses a small exponent such as 65537).

Edge cases

• A message longer than the modulus is a non-issue here, unlike raw RSA encryption of long data, precisely because the message is hashed to a fixed size before being signed.
• A passphrase-protected private key needs that passphrase passed to password= instead of None; the shown code assumes an unencrypted key.
• Verifying with the WRONG public key fails closed, by raising, not by returning False silently; calling code must catch that exception path explicitly rather than assuming a boolean return.
• PSS's randomized salt means signing the SAME message twice with the SAME key produces two DIFFERENT valid signature byte strings. This is expected and correct, not a bug; don't assume signature reproducibility for any purpose that needs it, such as content-addressing.

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):

1. In-process hash tables or maps keyed by data the caller controls internally, not data supplied over a network by an untrusted party.
2. 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.
3. 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:

1. 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.
2. 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.
3. 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.