Cryptographic Hashing and Digital Signatures Questions

Direct answer

I'd build a JWS (JSON Web Signature) verifier around three rules: never let the token's own header choose the verification algorithm, always check the signature against the exact bytes that were transmitted rather than a re-parsed version, and always check freshness separately from validity, since a signature only proves who signed something and that it wasn't altered, not that it's still supposed to be accepted right now. Production JWS bugs cluster around exactly the places where the verifier trusts something the ATTACKER controls: the algorithm name in the header, a stale but validly-signed token being replayed, or ambiguity about which bytes were actually hashed and signed.

Structured elaboration

Glossary. JWS (JSON Web Signature) is a standard for representing a signed JSON payload as a compact, base64url-encoded string in the form header.payload.signature. JWT (JSON Web Token) is the common special case where the payload holds a set of identity or authorization claims.

Algorithm confusion. The JWS header includes an "alg" field that the TOKEN ITSELF supplies. If a verifier is configured to accept multiple algorithms and blindly uses whichever one the token names, an attacker can often exploit the gap between an asymmetric and a symmetric algorithm specifically. For example, a server that verifies RS256 tokens (RSA signatures, asymmetric) using a public key, but is ALSO configured to accept HS256 (HMAC, Hash-based Message Authentication Code, a symmetric construction) using that SAME key value as the verification argument, lets an attacker who merely knows the public key, which is intentionally public, forge an HS256-"signed" token: HMAC only needs some shared secret bytes, and the public key's own PEM string works fine as one. The fix is to pin exactly one expected algorithm per verification context and never let the token select it.

Replay of an old but validly-signed request. A signature proves who signed something and that it wasn't altered; it says nothing about WHEN it's still valid to accept. The mitigation is to embed and check an expiry claim and an issued-at claim with a small allowed clock-skew window, plus a unique nonce or token identifier tracked server-side in a short-lived store, so a given token can't be replayed a second time within its own validity window.

Exactly what bytes get hashed and signed. JWS signs the base64url-encoded header and payload CONCATENATED WITH A LITERAL PERIOD CHARACTER, not the raw, re-parsed JSON object. If a verifier re-serializes the JSON, for instance re-encoding fields in a different key order or with different whitespace, before checking the signature, instead of checking it against the exact bytes that were transmitted, it can accept a token whose claims were subtly altered after signing, provided the alteration happens to normalize back to something matching after re-serialization.

Worked example

Here is the algorithm-confusion attack end to end, using a real RSA keypair and a real JWS library, showing a vulnerable verifier accept a forged token and a correctly pinned verifier reject it.

import json, hmac, hashlib, base64
import jwt
from cryptography.hazmat.primitives import serialization, hashes
from cryptography.hazmat.primitives.asymmetric import rsa, padding

def b64u(data: bytes) -> str:
    return base64.urlsafe_b64encode(data).rstrip(b'=').decode()

def b64u_decode(s: str) -> bytes:
    return base64.urlsafe_b64decode(s + '=' * (-len(s) % 4))

# server: RSA keypair, signs with RS256, publishes the PUBLIC key (e.g. via a JWKS endpoint)
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)

legit_token = jwt.encode({"sub": "alice", "role": "user"}, priv_pem, algorithm="RS256")

# VULNERABLE verifier: trusts the token's own "alg" header, reuses the SAME key bytes either way
def vulnerable_verify(token: str, verification_key: bytes):
    header_b64, payload_b64, sig_b64 = token.split('.')
    header = json.loads(b64u_decode(header_b64))
    signing_input = f"{header_b64}.{payload_b64}".encode()
    sig = b64u_decode(sig_b64)
    if header["alg"] == "HS256":
        expected = hmac.new(verification_key, signing_input, hashlib.sha256).digest()
        if not hmac.compare_digest(expected, sig):
            raise ValueError("bad HS256 signature")
    elif header["alg"] == "RS256":
        pub = serialization.load_pem_public_key(verification_key)
        pub.verify(sig, signing_input, padding.PKCS1v15(), hashes.SHA256())
    else:
        raise ValueError("unsupported alg")
    return json.loads(b64u_decode(payload_b64))

print("legit RS256 token verifies:", vulnerable_verify(legit_token, pub_pem)["role"] == "user")

# attacker: no private key, but the public key IS public by design; forge an HS256 token
# using the public-key PEM bytes as the HMAC secret
header = {"alg": "HS256", "typ": "JWT"}
payload = {"sub": "alice", "role": "admin"}
signing_input = f"{b64u(json.dumps(header, separators=(',', ':')).encode())}.{b64u(json.dumps(payload, separators=(',', ':')).encode())}"
forged_sig = hmac.new(pub_pem, signing_input.encode(), hashlib.sha256).digest()
forged_token = f"{signing_input}.{b64u(forged_sig)}"

try:
    result = vulnerable_verify(forged_token, pub_pem)
    print("FORGED token accepted by vulnerable verifier! role =", result["role"])
except Exception as e:
    print("forged token rejected:", e)

# FIXED verifier: pins ONE expected algorithm; PyJWT also independently refuses to use a
# PEM-shaped key for HS256, a defense added specifically against this bug class
def fixed_verify(token):
    return jwt.decode(token, pub_pem, algorithms=["RS256"])

try:
    fixed_verify(forged_token)
    print("FIXED verifier: forgery accepted (BUG)")
except jwt.InvalidTokenError as e:
    print("FIXED verifier correctly rejects the forged token:", type(e).__name__)

Output:

legit RS256 token verifies: True
FORGED token accepted by vulnerable verifier! role = admin
FIXED verifier correctly rejects the forged token: InvalidAlgorithmError

The vulnerable verifier escalates the attacker from "user" to "admin" using only the public key, which was never secret in the first place. Pinning the algorithm closes the hole entirely. Worth noting: PyJWT itself independently refuses to use a PEM-shaped key as an HMAC secret, a guard added specifically because this exact bug class was common enough in real deployments to justify hardening the library itself.

Trade-offs and pitfalls

• "Accept multiple algorithms for flexibility" is almost always the wrong trade. Pin one algorithm per key or context; if you genuinely need to rotate algorithms, select a specific known key-and-algorithm pair via a key identifier looked up from a server-side allowlist, never from attacker-supplied header content alone.
• A replay window sized to be "generous for clock skew" is a real, live trade-off: too tight and legitimate clients with slightly-off clocks get rejected, too loose and a captured token stays exploitable for longer. There's no universally correct number; size it to your actually observed clock drift plus a safety margin, and prefer short-lived tokens over a large skew window.
• Signing the raw transmitted bytes exactly, rather than a re-serialized or re-parsed version, avoids a whole class of canonicalization-mismatch bugs, but requires the client, server, and any intermediary to agree on byte-for-byte fidelity in transit; don't let a proxy "prettify" JSON along the way.

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

Concatenating fields without separators throws away the boundary information between them, so the same byte string can come from more than one set of field values. Move a digit from the front of timestamp into the back of user and the concatenation is identical, which means the signature over it is identical too, even though the two field sets mean different things. The fix is to make the message a canonical, self-delimiting encoding before it is signed, most simply by length-prefixing every field, and the real cost of shipping that fix is a coordinated cutover with old signatures and old verifiers in the system at the same time.

Structured elaboration

Why the ambiguity exists. user || timestamp || amount with no separators is not really one message; it is three fields glued together with the split points thrown away. A verifier that reconstructs the signed bytes from parsed (user, timestamp, amount) values assumes there's exactly one way to split the string back into those three fields, but nothing in the byte string enforces that. Any two field sets that concatenate to the same string produce the same signature, because the signature was only ever over the concatenation, never over the field structure.

The fix. Replace the bare concatenation with a canonical, unambiguous serialization before signing. The standard tool is length-prefixing: encode each field as len(field) || field (for example a fixed-width 4-byte big-endian length followed by the field bytes) and concatenate those framed fields instead of the raw ones. Because the length is bound to the field, no rearrangement of byte boundaries can produce the same framed string from a different set of field values. Equivalent alternatives are a canonical structured encoding (protobuf, CBOR (Concise Binary Object Representation, a compact binary JSON-like encoding), or JSON with a fixed key order and no field values that can contain the delimiter) or a fixed-width encoding, if the field domains are bounded (a Unix timestamp always fits a fixed number of digits, for instance).

Backward compatibility. Changing the wire format breaks verification for anything already relying on the old bare concatenation. In practice this needs: an explicit scheme-version byte or field carried alongside the signature (so verifiers can tell old-format signatures from new-format ones and apply the matching canonicalization), a dual-verify window where the service accepts both formats while clients and stored signatures migrate, and an expiry date after which the old, ambiguous format is rejected outright. Anything that pre-signed messages under the old scheme (queued jobs, long-lived tokens, offline-signed batches) has to be re-signed or grandfathered explicitly rather than silently reinterpreted, because reinterpreting old bytes under the new canonicalization rules is exactly the kind of parsing ambiguity this fix is trying to eliminate.

Worked example

Two field sets that collide under the naive scheme:

Set A: user="bob",  timestamp="1699999999", amount="50"
Set B: user="bob1", timestamp="699999999",  amount="50"

import hmac, hashlib

KEY = b"pinned-demo-key"

def sign(user, timestamp, amount):
    message = user + timestamp + amount
    return message, hmac.new(KEY, message.encode(), hashlib.sha256).hexdigest()

concat_a, sig_a = sign("bob", "1699999999", "50")
concat_b, sig_b = sign("bob1", "699999999", "50")
print("concat_a == concat_b:", concat_a == concat_b, " sig_a == sig_b:", sig_a == sig_b)
print("sig_a:", sig_a)

def sign_fixed(user, timestamp, amount):
    def framed(field):
        b = field.encode()
        return len(b).to_bytes(4, "big") + b
    message = framed(user) + framed(timestamp) + framed(amount)
    return message, hmac.new(KEY, message, hashlib.sha256).hexdigest()

fixed_a = sign_fixed("bob", "1699999999", "50")
fixed_b = sign_fixed("bob1", "699999999", "50")
print("framed_a == framed_b:", fixed_a[0] == fixed_b[0], " sig_a == sig_b (fixed):", fixed_a[1] == fixed_b[1])
print("sig_a (fixed):", fixed_a[1])
print("sig_b (fixed):", fixed_b[1])

Running this prints concat_a == concat_b: True sig_a == sig_b: True: concat_a and concat_b are both the literal string "bob169999999950", and the HMAC (Hash-based Message Authentication Code, a keyed construction that turns a hash function into a tag only someone holding the secret key can produce) over them is bit-for-bit identical, 7fdf7a5e9f5a0c17391868dc99f7d4e59733e01f508be32f9c136b9f62200475 in both cases. Applying the length-prefix fix flips both results to False: the framed messages differ (the length prefix on "bob" versus "bob1" diverges immediately), and the two signatures come out different, e6c2dcc3ce33b7eb3403189d7b8451905a8b53568145d06d2efa4e0494609c24 versus 2e4a6a43def8267dfb655fe02e3618d5a76d483773b7cb6f7b2c3eca923c229e.

Trade-offs and pitfalls

Length-prefixing is cheap and fully general but is not the only valid fix: a structured, canonical encoding buys the same guarantee and often better tooling support (schema validation, cross-language libraries), at the cost of a heavier format. A single separator character (like |) is a tempting shortcut but only works if the field values are guaranteed never to contain that character; if user can ever include a pipe, you have reinvented the same ambiguity one layer down. The migration is the part most teams underestimate: it is easy to fix the signer and forget that every downstream verifier, cached signature, or replayable message needs to agree on which format it is looking at, and a silent format-detection heuristic (guessing whether a message is old or new style) reintroduces exactly the kind of ambiguity you were trying to remove.

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

The birthday paradox says you need far fewer draws than the output space size to find some collision, because you're comparing every pair of draws against each other, not searching for one fixed target. For an n-bit hash, that means an attacker needs on the order of $2^{n/2}$ hash computations to find a collision, not $2^n$. At 2^30 hash computations per second, a 128-bit hash falls to a collision search in a practically alarming timeframe (hundreds of years, not the age of the universe); a 256-bit hash does not, by a margin of roughly twelve orders of magnitude.

Structured elaboration

Why the birthday bound is $2^{n/2}$, not $2^n$. With $N = 2^n$ possible outputs, the classic result is that after about $1.25\sqrt{N}$ random draws, the probability that at least two of them collide passes 50%. Intuitively: with $q$ draws there are $\binom{q}{2} \approx q^2/2$ pairs, and each pair has roughly a $1/N$ chance of colliding, so the expected number of colliding pairs is around $q^2/(2N)$; that crosses 1 once $q$ is on the order of $\sqrt{N} = 2^{n/2}$. This is fundamentally different from a preimage search, which fixes one target output first and needs about $N = 2^n$ tries to hit it, because there you are matching against a single fixed value, not against every other draw you've already made.

Applying it to 128-bit and 256-bit hashes. For a 128-bit hash, the birthday-bound work is about $2^{64}$ hash calls. For a 256-bit hash, it's about $2^{128}$ hash calls, the square of the 128-bit figure, not merely double it: doubling the output size squares the birthday-bound work, because the exponent itself doubles.

Worked example

Pinned inputs: attacker rate $= 2^{30}$ hashes/second, one calendar year $= 365.25 \times 24 \times 3600 \approx 3.156\times10^7$ seconds.

SECONDS_PER_YEAR = 365.25 * 24 * 3600
RATE = 2 ** 30

def estimate(n_bits):
    ops_needed = 2 ** (n_bits // 2)
    seconds = ops_needed / RATE
    return ops_needed, seconds, seconds / SECONDS_PER_YEAR

for n in (128, 256):
    ops, secs, yrs = estimate(n)
    print(n, ops, secs, yrs)

Running this gives:

• 128-bit: work $\approx 2^{64} = 1.845\times10^{19}$ hash calls, time $= 1.718\times10^{10}$ seconds $\approx 5.44\times10^{2}$ years.
• 256-bit: work $\approx 2^{128} = 3.403\times10^{38}$ hash calls, time $= 3.169\times10^{29}$ seconds $\approx 1.00\times10^{22}$ years.

For scale, the age of the universe is about $1.38\times10^{10}$ years. The 128-bit estimate (about 544 years) is uncomfortably close to a human timescale if the attacker's rate climbs with cheaper hardware or a distributed botnet; the 256-bit estimate exceeds the age of the universe by about twelve orders of magnitude and is not a practically meaningful risk from raw compute at any foreseeable rate.

Trade-offs and pitfalls

Practical feasibility is not just about raw operation count: real attacks also need memory to detect the collision (a naive hash table over $2^{64}$ entries is itself infeasible; real large-scale birthday attacks use van Oorschot-Wiener style parallel collision search with "distinguished points" to avoid storing every draw), and the estimate above assumes the attacker can reach $2^{30}$ hashes/second sustained, which is itself a strong assumption unless the attack is massively parallelized across dedicated hardware (ASICs, application-specific integrated circuits built for one job, or a large GPU/FPGA farm, FPGA meaning field-programmable gate array, a chip that can be reconfigured for a specific computation). A common mistake is quoting $2^{n/2}$ as if it were the probability of a collision rather than the work to reach roughly even odds of one; another is mixing bases mid-calculation, such as multiplying a per-second rate by a bit-count without first converting both work and rate to the same unit (hash operations), which is exactly the kind of unit-mismatch that produces a wrong-by-many-orders-of-magnitude answer.