Cryptographic Hashing and Digital Signatures Questions

Direct answer

A signature library's real bugs are almost never "the math is wrong on the happy path." They are in the seams: malformed or non-canonical encodings, edge-case scalar values, and cross-implementation disagreement about what counts as a valid signature. A strategy that actually catches production bugs combines known-answer test vectors (to prove the core algorithm is right), a differential test harness against at least one independent, mature implementation (to catch encoding and edge-case divergence), and property-based fuzzing over both malformed inputs and the algorithms' own known failure classes (malleability, non-canonical encodings, degenerate scalars), rather than only fuzzing "random bytes at the verifier."

Structured elaboration

• Known-answer tests (KATs): run the official test vectors for each scheme (RSA-PSS and ECDSA have NIST CAVP vectors; EdDSA, the Edwards-curve Digital Signature Algorithm, has the RFC 8032 test vectors). This proves the core sign/verify math matches the standard, and it is the cheapest test to write, but it only ever exercises the inputs someone thought to publish.
• Differential testing: sign and verify the same messages and keys against a second, independent implementation (e.g. a Python binding for one library, a Rust or Go library for another) and assert both agree on every accept/reject decision, not just on successful signatures. Disagreement on a REJECT is often the more interesting bug: it means one implementation accepts something the other correctly refuses.
• Malformed-encoding fuzzing: mutate the byte encoding of signatures, public keys, and DER/ASN.1 structures (truncate, pad, flip bits, insert extra elements) and assert the verifier only rejects, never crashes or leaks information through an exception type or timing difference. ECDSA/RSA-PSS use ASN.1 DER encodings that historically have had parser bugs (extra/duplicate elements accepted, negative integers mis-parsed).
• Known failure-class targeted tests, not generic fuzzing:
  • ECDSA/RSA-PSS: does (r, s) and its algebraic sibling (r, n-s) (or the RSA-PSS equivalent, an alternate valid encoding of the same signature) both verify, when the scheme's spec says only one should be accepted as canonical? This is signature malleability, and it has broken real systems (see the worked example).
  • EdDSA/Ed25519: is the scalar S in a signature checked to be strictly less than the group order, or does the verifier silently reduce it, accepting a second, non-canonical 64-byte encoding of the same signature? RFC 8032 requires strict rejection.
  • All schemes: degenerate values (r = 0, s = 0, the identity point as a public key, an all-zero signature) must be rejected, not accidentally accepted through an unchecked division or comparison.
• Cross-algorithm confusion tests: if the library exposes a generic "verify(pubkey, msg, sig)" entry point, assert it never accepts a signature produced under one scheme when verified as though it were another (algorithm confusion is a real bug class in libraries that dispatch on a caller-supplied type tag rather than a value derived from the key material itself).

Worked example

The malleability check above is not hypothetical: it is the exact bug class behind the 2014 Bitcoin transaction-malleability incident, where systems that used a signature's raw byte encoding as part of a transaction identifier could be handed a second, still cryptographically valid signature for the same transaction and computed a different ID for what was semantically identical content. Here it is demonstrated end to end on a tiny, hand-checkable elliptic curve (illustration only, not a secure curve size): a signature (r, s) is generated and verified, then its algebraic twin (r, n-s) is checked, and a naive verifier that only checks the ECDSA equation is shown accepting BOTH:

"""
Toy demonstration of ECDSA signature malleability: for a valid signature (r, s),
(r, n - s) is ALSO valid, because the verification equation only uses s through
s^{-1} and w = s^{-1}*z, u2 = s^{-1}*r, and (n - s)^{-1} == -(s^{-1}) mod n.

This is the exact bug class behind Bitcoin's historic transaction-malleability
incident (the 2014 Mt. Gox-era issue, closed at the protocol level via BIP62/
BIP66/SegWit rather than by a single tracked CVE, not CVE-2014-8275, which is an
unrelated OpenSSL certificate-fingerprint bypass): a system that used the
signature's byte encoding as a transaction identifier could be fed a second,
still-valid signature for the same message and get a different ID for what was
semantically the same transaction.
A fuzz/property test that checks "is (r, n-s) also accepted" catches this in any
new signature library before it ships.

ec_add / ec_mul / inv are defined below so the script runs standalone.
"""

p, a, b = 23, 5, 3
n = 23
G = (11, 3)


def inv(x: int, m: int) -> int:
    """Modular inverse of x mod m (m prime here)."""
    return pow(x, -1, m)


def ec_add(P, Q, a, p):
    """Short-Weierstrass point addition on y^2 = x^3 + a*x + b over F_p.
    None represents the point at infinity (the group's identity element)."""
    if P is None:
        return Q
    if Q is None:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None  # P + (-P) = identity
    if P == Q:
        if y1 == 0:
            return None
        lam = (3 * x1 * x1 + a) * inv(2 * y1, p) % p
    else:
        lam = (y2 - y1) * inv((x2 - x1) % p, p) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)


def ec_mul(k, P, a, p):
    """Scalar multiplication via double-and-add."""
    result = None
    addend = P
    while k > 0:
        if k & 1:
            result = ec_add(result, addend, a, p)
        addend = ec_add(addend, addend, a, p)
        k >>= 1
    return result


def sign(d, k, z):
    R = ec_mul(k, G, a, p)
    r = R[0] % n
    s = (inv(k, n) * (z + r * d)) % n
    return r, s


def verify(Q, z, r, s):
    w = inv(s, n)
    u1 = (z * w) % n
    u2 = (r * w) % n
    X = ec_add(ec_mul(u1, G, a, p), ec_mul(u2, Q, a, p), a, p)
    return X is not None and X[0] % n == r


def is_low_s(s, n):
    return s <= n // 2


if __name__ == "__main__":
    d, k, z = 7, 4, 15
    Q = ec_mul(d, G, a, p)
    r, s = sign(d, k, z)
    s_flipped = (n - s) % n

    print("original signature (r, s) =", (r, s), " verifies:", verify(Q, z, r, s))
    print("malleated signature (r, n-s) =", (r, s_flipped), " verifies:", verify(Q, z, r, s_flipped))
    print("both encode the SAME message + key, but are byte-different signatures")

    print("\nnaive verifier (accepts both) is vulnerable to malleability-based bugs.")
    print("fix: reject any signature that is not the canonical low-S form.")
    print(f"  original s={s} is low-S: {is_low_s(s, n)}  (n//2={n // 2})")
    print(f"  flipped  s={s_flipped} is low-S: {is_low_s(s_flipped, n)}")

    def verify_canonical(Q, z, r, s):
        if not is_low_s(s, n):
            return False
        return verify(Q, z, r, s)

    print("\nwith canonical-S enforcement:")
    print("  original accepted:", verify_canonical(Q, z, r, s))
    print("  malleated accepted:", verify_canonical(Q, z, r, s_flipped))

original signature (r, s) = (10, 4)  verifies: True
malleated signature (r, n-s) = (10, 19)  verifies: True
both encode the SAME message + key, but are byte-different signatures

naive verifier (accepts both) is vulnerable to malleability-based bugs.
fix: reject any signature that is not the canonical low-S form.
  original s=4 is low-S: True  (n//2=11)
  flipped  s=19 is low-S: False

with canonical-S enforcement:
  original accepted: True
  malleated accepted: False

A single test asserting "for every valid (r, s) this library produces, (r, n-s) must be REJECTED, not just non-canonical" would have caught this class before shipping. That is the shape every entry in the "known failure-class" list above should take: a concrete, executable assertion derived from a documented historical bug, not a vague "test edge cases" note.

Trade-offs and pitfalls

• KATs alone give false confidence: a library can pass every published test vector and still accept malleated or non-canonical signatures, because the vectors were never designed to probe encoding ambiguity.
• Differential testing is only as strong as the reference implementation; if both libraries share the same upstream bug (a shared underlying big-integer library, for instance), agreement between them proves nothing about that bug.
• Verification is typically far cheaper than signing (RSA verification uses a small public exponent, commonly e = 65537, while signing needs a full-size modular exponentiation with the private exponent or an equivalent CRT computation (CRT here meaning the Chinese Remainder Theorem trick of splitting that single full-size exponentiation into two smaller ones, one modulo each of RSA's two secret prime factors, then recombining them, several times faster than doing the full-size exponentiation directly)), which matters for fuzz-loop throughput: run the cheap verify-side fuzzing first and reserve the expensive sign-side property tests for a smaller, targeted set.
• Do not stop at accept/reject correctness: also assert exception TYPE and rough control flow are the same across malformed inputs that differ only in where the malformation occurs, since a verifier that fails fast on an early field and slowly on a late one is leaking structure through timing, which is a distinct bug class from wrong accept/reject decisions.

Direct answer

HKDF (HMAC-based key derivation function, defined in RFC 5869, where HMAC itself is a keyed hash-based message authentication code) splits key derivation into two separate steps, extract then expand, because the input it starts from (a Diffie-Hellman shared secret, for example) is usually NOT uniformly random, it just has enough hidden randomness (entropy) that an attacker cannot guess it, while the keys a protocol actually needs must be close to uniformly random bytes. Extract concentrates whatever entropy the input has into one short, uniform-looking value; expand then stretches that value into as many independent-looking derived keys as needed. Hashing the shared secret directly, in one step, conflates these two different jobs and does neither one on purpose.

Structured elaboration

• Extract: PRK = HMAC(salt, input_keying_material). Inputs are a (recommended, but not required) random salt and the raw secret material IKM. Its job is purely to CONCENTRATE entropy: turn a secret that might be, say, an elliptic-curve point's x-coordinate (structured, not uniformly random bits) into a fixed-length pseudorandom key PRK that looks uniform.
• Expand: OKM = HKDF-Expand(PRK, info, length), computed via repeated HMAC calls keyed by PRK. Its job is to STRETCH that concentrated entropy into as much output as needed, with info (a context string, e.g. "session-key" vs "encryption-key") providing domain separation so different derived keys for the same PRK are independent of each other.
• Why not just hash the secret directly: a single H(shared_secret) call does not have a clean way to (a) account for non-uniform input entropy the way a salted extract does, and (b) safely produce MULTIPLE independent derived keys from one secret without either reusing the same output for two purposes or re-deriving from scratch each time; a plain hash also has no principled way to bound how much output it can safely stretch to, which HKDF's expand step defines explicitly (bounded by the underlying HMAC's output size times 255).

Worked example

Concretely: a key exchange yields a shared secret that is NOT uniformly random bit-for-bit (its high bits, for instance, may be biased by the specific elliptic curve's structure). Extract absorbs that non-uniformity: PRK = HMAC(salt, shared_secret) produces a value that looks uniform regardless of the input's structure, because HMAC behaves like a pseudorandom function (its output is unpredictable and uncorrelated across different inputs, given a secret key) rather than merely mixing bits, and that property does not preserve input-level bias into its output. Expand then derives, from that ONE PRK, both K_enc = HKDF-Expand(PRK, "encryption", 32) and K_mac = HKDF-Expand(PRK, "authentication", 32), two independent-looking keys from one exchange, which a single direct hash call has no clean mechanism to produce.

Trade-offs and pitfalls

• Skipping extract (feeding raw, structured secret material straight into expand) is a common shortcut when the input already looks "random enough"; it is not categorically broken, but it discards the one step designed specifically to handle non-uniform input, which is exactly the wrong place to cut a corner when you cannot fully characterize your input's entropy.
• salt is optional in the RFC but should not be treated as unimportant: a fixed, well-known, or absent salt still lets extract work, but a distinct salt per use context adds an extra layer of domain separation between otherwise-identical secrets used in different protocols.

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.

Direct answer

Use a Merkle Mountain Range (MMR): an append-only forest of perfect binary subtrees ("peaks"), one per set bit in the current leaf count's binary representation, whose peaks get combined ("bagged") into a single root. Appending a leaf only touches $O(\log n)$ nodes (merging adjacent equal-height peaks as needed), light-client proofs stay $O(\log n)$ in size like an ordinary Merkle tree, and because the structure is purely append-only, an earlier MMR state is provably a strict prefix of a later one without recomputing anything, which is exactly what makes handling reorgs cheap: you roll back to a prior peak list instead of rebuilding a tree from scratch.

Structured elaboration

Node layout. Leaves and internal nodes are stored in a single flat, insertion-ordered array (this is the standard MMR indexing scheme): appending leaf $k+1$ may also trigger merging the two most recent peaks of equal height into a new parent node, cascading upward exactly as far as needed, the same carry-propagation pattern as incrementing a binary counter. After $n$ leaves, the number of peaks equals the number of set bits in $n$'s binary representation, since each peak corresponds to a maximal perfect subtree that hasn't yet been merged into a larger one.

Proof compression. A light-client inclusion proof for one leaf is the sibling path up to its containing peak (identical in structure to an ordinary Merkle proof, $O(\log(\text{peak height}))$ hashes), plus a short "bagging" path combining that peak with the other peaks into the overall root, itself $O(\log(\text{number of peaks}))$. Total proof size stays logarithmic in the total leaf count, the same asymptotic guarantee as a balanced Merkle tree, without needing the whole tree rebuilt on every append the way a naive binary Merkle tree (with duplicate-last-node padding) effectively requires, since a naive tree's shape and root change unpredictably as leaves are added.

Handling large forks without re-hashing entire histories. Because appends are strictly additive (never rewriting already-finalized peaks), a node can keep the peak list (and, for reorg support, a small history of PRIOR peak lists at recent checkpoints, not the full tree) and roll back a reorg by restoring an earlier peak list rather than reconstructing the tree from the new canonical chain's genesis. The cost of rolling back $d$ blocks is proportional to $d$ (undoing $d$ appends), not to the full chain length, which is the property that makes MMRs suitable for high-throughput chains where reorgs of a handful of recent blocks are routine and reprocessing the entire history on every reorg would be prohibitively expensive.

Worked example

flowchart LR
    subgraph MMR["Merkle Mountain Range after 7 leaves"]
        direction LR
        P1["Peak A (height 2, leaves 1-4)"]
        P2["Peak B (height 1, leaves 5-6)"]
        P3["Peak C (height 0, leaf 7)"]
    end
    P1 --> Bag["bag peaks: H(H(P1,P2), P3)"]
    P2 --> Bag
    P3 --> Bag
    Bag --> Root["MMR root"]
    NewLeaf["append leaf 8"] -.merges with P3, then P2.-> P2b["new Peak (height 2)"]

After 7 leaves, 7 in binary is 111, three set bits, matching the three peaks shown (heights 2, 1, 0 covering 4, 2, and 1 leaves respectively). Appending an 8th leaf triggers a full cascade: the new leaf (height 0) merges with peak C (also height 0) into a height-1 peak, that result merges with peak B (height 1) into a height-2 peak, and that in turn merges with peak A (height 2) into a single height-3 peak covering all 8 leaves. The cascade stops there because no height-3 peak previously existed to merge with. The result is exactly ONE peak, matching 8 = 1000 in binary having a single set bit: the peak count after n leaves always equals the number of set bits in n's binary representation, and this three-step carry-propagation cascade is the same pattern as incrementing a binary counter from 0111 to 1000.

Trade-offs and pitfalls

MMRs give up the ability to trivially locate "the $i$-th leaf" by a single array index the way a naive complete binary tree can, since leaf position now depends on the historical sequence of merges, so an implementation needs explicit index-mapping bookkeeping, a real but manageable complexity cost. Bitcoin's own historical CVE-2012-2459 (a Common Vulnerabilities and Exposures identifier for a duplicate-transaction second-preimage issue in its Merkle tree's odd-node handling) is a cautionary example of why domain-separating leaf hashes from internal-node hashes, and being precise about how odd counts and the peak-merge cascade are handled, matters just as much in an MMR as in a plain Merkle tree; getting the bagging order or leaf/node domain separation wrong reopens the same class of ambiguity bug. Finally, an MMR's rollback-by-restoring-a-prior-peak-list approach assumes those prior peak lists were actually retained; a node that only ever keeps the LATEST peak list has traded reorg cost for storage in a way that only pays off if it also budgets for keeping enough recent history to cover the deepest reorg it expects to see.

Direct answer

A cryptographic hash function (a deterministic function mapping arbitrary-length input to a fixed-length output, chosen so it is hard to invert or to find two inputs with the same output) carries no built-in notion of "what it was called for." If the same hash function, on the same or overlapping input material, is used for a key derivation, a MAC (message authentication code, a keyed tag proving both integrity and that the sender held a shared secret), and a commitment (a value that binds you to a choice now without revealing it, verified later), then a value computed for one purpose can be replayed, confused with, or engineered to collide with a value expected for another purpose. The fix is domain separation: tag every hash invocation with an explicit, purpose-specific label (a prefix byte, an HKDF info string, or a distinct derived key) so outputs from different roles are provably independent of each other.

Structured elaboration

• Why it breaks: a hash output by itself is just bytes. If role A's computation and role B's computation can ever be fed the same input, they produce the same output, and anything that treats "the output" as proof of role B now also accepts a value that was really produced for role A.
• Domain-separation mechanisms, roughly in order of how directly they fix the problem:
  • A fixed domain-tag byte or string prepended to every hash input, unique per role (H(0x01 || x) for key derivation vs H(0x02 || x) for a MAC).
  • A real key-derivation function (KDF, a function that turns one keying secret into one or more independent-looking derived keys) such as HKDF, where each derived key/value uses a distinct info label instead of ad hoc concatenation.
  • Distinct keys per purpose (an HMAC key used only for authentication, never reused as input keying material for a KDF).
• A second, easy-to-miss requirement: domain separation only closes the "which role" ambiguity. It does not by itself close a "where do the fields end" ambiguity when you concatenate several variable-length fields before hashing; that needs length-prefixing or fixed-width encoding, and both problems tend to appear together in the same ad hoc protocol.

Worked example

Mistake 1, reusing one computation for two roles: a protocol computes tag = H(secret || message) as a MAC, authenticating that the holder of secret approved message. The same team later needs a commitment scheme and, to save code, publishes commitment = H(secret || message) as "proof the message was fixed in advance." Because tag and commitment are literally the same computation, publishing the commitment leaks a valid MAC tag for message: anyone who now sees commitment and message can replay commitment as the MAC, since it is bit-for-bit the value the MAC check expects. Fix: derive two independent values, e.g. tag = HMAC(K_mac, message) and commitment = HMAC(K_commit, message), where K_mac and K_commit come from a KDF fed distinct info labels ("mac" vs "commit"), so knowing one output tells you nothing about the other.

Mistake 2, concatenation ambiguity masquerading as a hash-role confusion: a system derives a session subkey as K' = H(K || "session-key") and separately computes a per-request MAC over structured fields as MAC = H(K || field1 || field2), with no length-prefixing and no domain tag distinguishing the two computations. An attacker who controls field1 in the MAC path can set field1 = "session-key" and force field2 to be empty (many APIs happily accept an empty trailing field), so the MAC computation becomes H(K || "session-key"), i.e. exactly the subkey-derivation computation. The attacker never learns K, but they now hold K' (the session subkey), obtained purely by requesting a MAC over attacker-chosen fields. Fix: length-prefix every field so "session-key" as literal field content can never line up with a concatenation boundary, and put a fixed domain-tag byte first in every hash call in the protocol (0x01 for key derivation, 0x02 for MAC), defined centrally in the spec so a future feature cannot silently reuse an existing tag.

Trade-offs and pitfalls

• Domain separation only helps if applied everywhere, consistently, including features added later; leaving it as convention rather than a spec-level, centrally enforced rule is how it gets skipped once.
• A domain tag placed at the very start of the input matters for Merkle-Damgard-style hashes (SHA-256, SHA-1, a family of hash constructions that process input in fixed-size blocks through a repeated compression step): tying the tag to the first hashed block, rather than appending it at the end, keeps the tag inseparable from everything that follows, which matters once you also consider length-extension-style manipulation of hash inputs.
• Do not treat "add a prefix" and "length-prefix the fields" as the same fix: the first stops cross-role confusion, the second stops within-role field-boundary confusion, and a protocol missing either one is still exploitable.