RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism

RSA's multiplicative homomorphism lets you obtain a signature (or decryption) on a message an oracle refuses to touch by disguising it as a uniformly random value, having the oracle process *that*, then dividing the disguise back out — the oracle never "sees" the forbidden value.

The signal that gives it away

- A signing or decryption oracle checks the input against a blocklist of exact values (a specific message, an admin token, one specific ciphertext) but will happily process anything else. Framing like "I'll sign anything except X" or "decrypt anything except this ciphertext" is the tell. - The oracle operates on raw/textbook RSA — s = m^d mod N or p = c^d mod N with no hashing and no structured padding (OAEP/PSS) between the value you control and the modular exponentiation. This is load-bearing: hashing or randomized padding destroys the algebraic relation the attack depends on, so if the oracle hashes first, this technique does not apply (see below). - The check is a value/string equality test, not a semantic one — the server compares your submitted integer (or its decoded plaintext) against the forbidden value directly, not a hash or a property of it. A blinded value is numerically unrelated to the original, so an exact-match filter cannot catch it. - The same RSA keypair (same N, e) is reachable for both encryption/decryption and signing — this is itself a design smell independent of any blocklist: Wikipedia's treatment of blind signatures flags that reusing one key for both roles is exactly what makes decryption-oracle blinding possible, since a "sign this" request and a "decrypt this" request are the same modular exponentiation.

How it's exploited

The core fact: r ↦ r^e mod N is a permutation of Z_N^*, so multiplying m by r^e mod N for a uniformly random r produces a uniformly random-looking m' that carries no visible relationship to m. Signing/decrypting is a homomorphism ((m·r^e)^d = m^d·r^{ed} = m^d·r mod N), so the disguise factor r survives linearly through the oracle and can be divided back out.

1. Pick random `r` coprime to `N`. Compute gcd(r, N) yourself and retry on failure — don't assume the oracle will catch a bad r for you. 2. Blind. m' = m * pow(r, e, N) mod N for a signing oracle, or c' = c * pow(r, e, N) mod N for a decryption oracle. 3. Query the oracle on the blinded value. It signs/decrypts it because m'/c' doesn't match anything on the blocklist. 4. Unblind. For signing: s = s' * pow(r, -1, N) mod N is a valid signature on the *original* m. For decryption: p = p' * pow(r, -1, N) mod N is the plaintext of the original c.

``python def rsa_blind_forge(m, e, N, sign_oracle): while True: r = random.randrange(2, N) if gcd(r, N) == 1: break blinded = (m * pow(r, e, N)) % N s_blinded = sign_oracle(blinded) # oracle signs the blinded msg s = (s_blinded * pow(r, -1, N)) % N # unblind return s # valid signature on m # decryption oracle: same idea, send c*r^e mod N, then multiply the # oracle's answer by r^{-1} mod N to recover the original plaintext ``

A free bonus leak. If the oracle *itself* validates gcd(m', N) == 1 and rejects values that fail — i.e. it tries to be "safer" by refusing non-invertible inputs — that rejection is a signal in its own right: a non-trivial gcd(m', N) means m' shares a factor with N, so a rejection on a value you chose tells you it shares a factor with the modulus, handing you a path to factor N directly. A defensive check meant to harden the oracle becomes an oracle for factoring it.

Related

RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key exploits the exact same multiplicative-homomorphism property but in a different role — forgery *combines* signatures you already hold (sig(m1)*sig(m2) = sig(m1*m2)) to build a signature on a target you never queried directly, while blinding *disguises* a single target so the oracle signs it without recognizing it. They're the same algebraic fact used two different ways, and the same raw-RSA-no-padding precondition gates both. See also RSA Fundamentals — the routing hub: which artifact points to which attack for how to recognize raw/textbook RSA in the first place, and Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key for the broader family of "the signature scheme leaks structure the verifier didn't account for" bugs.

What does NOT work

- Reusing the same small, fixed `r` across queries (e.g. always r=2). Even though each individual blinded value looks random, a defender who logs submitted values can brute-force small, plausible r against every blocklist entry for each logged query — a small fixed r has few candidates to check, so the disguise is trivially reversible after the fact. Draw a fresh, uniformly random r from the full range on every query; don't economize by reusing or incrementing it. - Trying this against a hashed-then-signed or padded scheme (PKCS#1v1.5 with correct padding checks, RSASSA-PSS, OAEP decryption). Hashing or randomized structured padding sits between the value you control and the modular exponentiation, so H(m) ≠ H(m)*r^e mod N in any usable sense — blinding only survives through the exponentiation itself, so the oracle must be operating on the raw integer for this to work at all. If the oracle hashes or pads first, this is the wrong technique; look for a padding-oracle or forgery angle on RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key instead. - Forgetting the blinded value still has to survive the transport. A field-tested gotcha from a real writeup: a uniformly random blinded integer, once decoded back to bytes/text for a command-style oracle, can accidentally contain characters that break the surrounding parser (e.g. a stray quote confusing a shlex-style split). If your blinded query gets rejected or mis-parsed for reasons unrelated to the blocklist, don't assume the attack failed — redraw r and try again; a different random draw sidesteps the parsing collision. - Expecting this to recover the private key `d`. Blinding forges a signature (or recovers one plaintext) for a chosen value — it is not key recovery. If the goal is the private key itself rather than one forged signature/decryption, this technique is a dead end; that requires factoring N or a fault-injection leak instead. - Assuming the oracle's own `gcd` sanity-check protects it. If you skip verifying gcd(r, N) == 1 on your own side and the oracle also does no such check, an unlucky r that shares a factor with N produces a non-invertible blinding you can't undo — always verify invertibility client-side before querying, rather than relying on the oracle to reject a bad r for you.