RSA LSB / Parity Oracle Attack — recover the plaintext one bit at a time from a decryption oracle

If a service decrypts attacker-chosen RSA ciphertexts and leaks nothing but the least-significant bit of the plaintext (odd/even, "parity", m mod 2), that single bit is enough to recover the *entire* plaintext via binary search — no factoring, no d, just repeated doubling and ~log2(n) queries.

The signal that gives it away

- A decryption or "check" oracle that takes a ciphertext you control and returns one bit, phrased as "even/odd", "the last bit", "parity", m & 1, or m mod 2 — never the plaintext itself. - You can submit modified ciphertexts freely (chosen-ciphertext access) and you know n and e. No padding scheme (OAEP, PKCS#1v1.5) sits between the oracle's modular exponentiation and the bit it returns — a correctly-checked padding scheme kills the malleability this attack needs, same precondition as RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism. - Query budget is generous: roughly n.bit_length() calls (~1024-2048 for typical CTF moduli). If the challenge caps queries far below that, this is the wrong tool. - This is not a heuristic guess: theory backs it up completely. The LSB of RSA plaintext is a proven hardcore predicate — recovering it with any non-negligible advantage over a coin flip is provably as hard as inverting RSA outright (Alexi-Chor-Goldreich-Schnorr, 1984). That's *why* leaking even one bit, adaptively, cracks the whole message: the oracle is quietly handing you a sequence of hardcore-bit predictions on ciphertexts of your own construction.

How it's exploited

The core trick is RSA's multiplicative homomorphism: (c * 2^e) mod n decrypts to 2m mod n. Since n is odd, whether 2m "wrapped around" n is exactly readable from the parity of the result: - if 2m < n, the reduction is a no-op and 2m mod n is even; - if 2m >= n, the reduction subtracts the odd n, flipping parity to odd.

So each oracle call on a re-doubled ciphertext tells you which half of the current interval m falls into — textbook binary search, ~1 bit of information per query, log2(n) queries to pin m down to an integer.

1. Maintain a bound [lo, hi] = [0, n] as exact rationals (Python fractions.Fraction), not floats — floating-point drift silently corrupts the low bits after a few hundred iterations. 2. Each round: c = (c * pow(2, e, n)) % n; query the oracle on c. 3. Interpret the bit against your oracle's actual convention (the two seed variants below differ only in which branch is "wrapped"): - LSB framed as "is the plaintext odd after doubling": bit 1 (odd) means 2m wrapped past n → raise lo; bit 0 → lower hi. - Parity framed as "even/odd of the decrypted value": same physics, just double-check which of 0/1 your specific oracle calls "even" before trusting the branch — this is the single most common source of a silently-wrong recovery, worth an explicit unit check against one known ciphertext before running the full loop.

```python from fractions import Fraction

lo, hi = Fraction(0), Fraction(n) c, mult = c0, pow(2, e, n) for _ in range(n.bit_length()): c = (c * mult) % n if oracle(c) == 1: # wrapped past n -> plaintext in upper half lo = (lo + hi) / 2 else: # no wrap -> plaintext in lower half hi = (lo + hi) / 2 m = int(hi) # take the ceiling; see precision note below ```

4. Precision at the tail is the recurring gotcha. The interval narrows to width 1 but rounding at the very last steps regularly produces an off-by-a-few-bytes result in the *last byte* of the recovered message — this shows up independently in more than one field report, so treat it as expected, not a bug in your code. Don't stop at int(hi): try int(hi), its ceiling, and a handful of neighboring integers, re-encrypt each candidate (pow(candidate, e, n) == c0), and keep the one that verifies. That final re-encryption check is mandatory, not optional — it's the only way to know you actually landed on m rather than m ± few. 5. If recovery diverges partway through (garbage bytes appear early rather than just at the tail), the most likely cause is the even/odd branch being inverted relative to what you coded — flip the two assignment lines and rerun; it is a one-line fix, not a sign the technique doesn't apply.

Related

RSA Fundamentals — the routing hub: which artifact points to which attack for recognizing raw/unpadded RSA in general; Error / Boolean Oracle Attack — turn any distinguishable valid/invalid response into a key or plaintext for the broader "any distinguishable oracle response is exploitable" family this belongs to; CBC Padding Oracle — leak the intermediate decryption value one byte at a time as the block-cipher-side sibling — same binary-search-via-oracle shape, different underlying math; RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism shares the same "no padding between input and modular exponentiation" precondition; Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright for a different way a decryption/signing implementation leaks its secret one query at a time.

What does NOT work

- Trusting floating-point bounds. hi = (lo + hi) / 2 on Python floats loses precision well before log2(n) iterations complete for a 1024+-bit modulus — you will get plausible-looking but wrong bytes with no error raised. Use Fraction (or pure-integer bound tracking) from the first line, not as an afterthought once floats "seem to be off." - Assuming the even/odd (or 0/1) convention matches your mental model. The two directions of this technique — "oracle returns the LSB directly" vs "oracle returns even/odd of the plaintext" — are functionally the same attack, but coding the wrong branch produces silent, confident-looking garbage rather than a crash. Verify the convention against one ciphertext with a known or at least self-consistent decryption before trusting the full run. - Running this against a padded oracle. If OAEP or checked PKCS#1v1.5 padding sits between your modified ciphertext and the bit the server returns, doubling the ciphertext does not cleanly double the plaintext anymore (the padding structure breaks under re-encryption), and the parity signal stops being informative. Confirm the oracle is operating on raw/textbook RSA before investing query budget here. - Skipping the final re-encryption check to save a query. The last byte or two of the recovered integer is exactly where this attack is least reliable; declaring victory at int(hi) without verifying pow(m, e, n) == c0 is the single most common way to submit a plaintext that's one byte short of correct. - Treating a large but finite query cap as "close enough." The attack is O(log2 n), not O(1) — if the challenge only allows, say, 50 queries against a 2048-bit modulus, this is not the intended path (look for a different leaked structure) rather than a technique to push through with fewer bits than the math requires.