RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key

Textbook RSA signing (s = m^d mod N) is multiplicatively homomorphic, and a PKCS#1 v1.5 verifier that under-checks its padding can be tricked into accepting a crafted integer as a valid signature — both routes forge a signature without ever touching d.

The signal that gives it away

- Raw/textbook RSA signing is visible — source shows s = pow(m, d, N) with no hash-then-pad step in between, or a signing oracle that exposes sig(x) for chosen x. Multiplicative homomorphism only survives when nothing structured (a hash, randomized padding) sits between the message and the exponentiation — see RSA Fundamentals — the routing hub: which artifact points to which attack for spotting textbook RSA in the first place. - A signing oracle that will sign chosen values but refuses the exact target message — "I'll sign anything except the admin token" framing. This is the tell for *combination* forgery: you never ask the oracle to sign the forbidden value directly, you ask it to sign values whose product (mod N) equals it. - Small public exponent (`e = 3` is the classic case, small odd `e` in general) paired with a PKCS#1 v1.5 signature verifier, especially a homegrown or older one. This is the tell for the Bleichenbacher '06 low-exponent forgery: suspect it whenever the challenge hands you a verifier to fool rather than an oracle to query, e is tiny, and the padding-check code looks like it stops as soon as it finds 00 01 FF...FF 00 <ASN.1><hash> without confirming the rest of the block is fully consumed. Public writeups link this exact laxness to a real 2006-era break of PKCS#1 v1.5 signature validation in Firefox/NSS (CVE-2006-5462), and to a later NSS variant nicknamed "BERserk" (ASN.1 BER-parsing laxness instead of raw padding laxness, same root cause: the verifier stops looking too early). - **Don't confuse this with RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism.** Both exploit the same multiplicative-homomorphism fact, but in opposite roles: blinding *disguises* one target value so an oracle unwittingly signs it, then you unblind; forgery here *combines* signatures you already hold (or can legitimately obtain) into a signature on a target you never asked the oracle to sign at all. Same algebraic fact, two different plans.

How it's exploited

Homomorphic/combination forgery. The core identity: sig(m1) * sig(m2) mod N = sig(m1*m2 mod N), because m1^d * m2^d = (m1*m2)^d mod N. To forge a signature on a target m, express it as a product of values you can get signed — factor m = m1 * m2 directly, or use the blinding-style form m * r^e if you'd rather disguise m than factor it — get signatures on the factors from the oracle (or from signatures you legitimately hold), and multiply the signatures mod N:

``python def forge_product(s1, s2, N): # sig(m1*m2) = sig(m1)*sig(m2) return (s1 * s2) % N ``

The oracle is never queried on the actual target message, only on the factors, so an exact-match blocklist on the target never fires.

Low-e cube-root forgery for lax PKCS#1 v1.5 parsers (Bleichenbacher '06). Craft an integer whose *leading* bytes match the required padding-and-digest prefix 00 01 FF..FF 00 <ASN.1> <HASH> and whose trailing bytes are arbitrary garbage, then take an integer e-th root (cube root when e = 3) and round up. If the verifier's padding check stops as soon as it has located and confirmed the hash, and never checks that the padded block is fully and exactly consumed to its declared length, the forged value passes:

```python from gmpy2 import iroot

def cube_root_forge(prefix_int, e=3): s, exact = iroot(prefix_int, e) # round up so the high bytes line up correctly return s + 1 ```

- This is specifically a small-`e` technique: the trick needs enough "slack" bits below the fixed prefix that an integer e-th root still lands close enough to it, and that slack shrinks fast as e grows. Public sources tie the practical range to e = 3 (and note the attack was a direct reason CAs moved away from e = 3 toward e = 65537 for signing keys) — don't expect this route against a standard e = 65537 verifier. - Full private-key recovery is a different problem entirely: neither route here recovers d. If the goal is the key itself, this technique is a dead end — that needs factoring N (see Integer Factorization Methodology — which factoring attack to try, in what order) or a fault-injection leak (see Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright).

What does NOT work

- Homomorphic combination against a hashed-then-signed scheme. As soon as the signing operation is sig(H(m)) rather than sig(m) directly — which is standard practice, and mandatory for any *correctly implemented* padding scheme — the multiplicative relation breaks: H is not homomorphic, so sig(H(m1)) * sig(H(m2)) mod N is not sig(H(m1*m2)) for any message you'd recognize. This technique only bites textbook/unpadded RSA signing, or an oracle you can feed a raw integer directly. - Low-e cube-root forgery against a verifier that fully validates the padded block. The fix for Bleichenbacher '06 is exactly the check this attack skips: confirm the 00 01 FF...FF 00 prefix, the ASN.1 DigestInfo, the hash, *and* that the whole structure exactly fills the modulus-sized block with no trailing garbage. A patched or spec-correct PKCS#1 v1.5 verifier (or RSASSA-PSS, which is randomized and structurally different) rejects the forged value outright — if the target library is current, this is the wrong technique. - Reaching for the low-e trick at standard exponents. At e = 65537 there isn't enough numerical slack for an integer root near a fixed high-order prefix to work; this is a small-e technique specifically, not a general PKCS#1 v1.5 weakness. Don't burn time on it once you've confirmed e is large. - Assuming a cryptographically valid forged signature is automatically a useful one. Combination forgery gives you a valid (m, sig(m)) pair for whatever m = m1*m2 mod N happens to be — that product is not something you chose freely, and it may not be a well-formed message for the application on top (a valid-looking blob of bytes that isn't valid JSON/protobuf/whatever the app expects next). Check that the algebraically-reachable target is also an application-meaningful one before assuming the forgery is useful, not just mathematically valid. - Treating this as key recovery. Neither the combination trick nor the low-e cube-root trick yields d. If the challenge wants the private key rather than one forged signature, this is the wrong page — go to factoring (Integer Factorization Methodology — which factoring attack to try, in what order) or fault injection (Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright) instead.

Related

RSA Fundamentals — the routing hub: which artifact points to which attack RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright Integer Factorization Methodology — which factoring attack to try, in what order