Error / Boolean Oracle Attack — turn any distinguishable valid/invalid response into a key or plaintext

Any endpoint whose response partitions attacker-controlled input into exactly two distinguishable classes — "valid"/"invalid", 200/500, True/False, even a measurable timing gap — is a *boolean oracle*, and crypto attacks against it are all the same shape: reduce a secret to a sequence of yes/no questions the oracle answers, chosen so each answer removes about half the remaining search space.

The signal that gives it away

- A decrypt/verify/login/check endpoint that returns distinguishable outcomes for attacker-modified input, and that outcome correlates with a hidden property of the underlying plaintext or key. Concretely: a try/except that leaks a different error class or message depending on *why* decryption failed; an HTTP status code that differs (200 vs 500, or a custom error body vs a generic one); a JSON field that's literally true/false; a "does this look like a valid X" check exposed as its own boolean; a numeric comparison whose sign or parity you can read off. - You have repeated, chosen-input access to the oracle — not a one-shot leak. The attack needs adaptive queries: submit input, read the bit, submit different input informed by what you just learned. This is the same access pattern the public literature calls an *adaptive chosen-ciphertext attack*: query a decryption oracle with attacker-chosen ciphertexts and use the valid/invalid answers to peel back the secret, without ever querying the oracle on the actual target ciphertext. - The oracle's *predicate* is the thing to identify precisely before writing any exploit code — not just "it leaks something" but exactly what boolean it's answering: parity of a decrypted integer, structural validity of padding, whether a value is a quadratic residue, whether a MAC/signature check passed. Two different oracles that both "return a bool" can require completely different exploitation math depending on what that bool actually means. - A timing gap counts as a boolean oracle too, but it's the weakest, noisiest form — see Timing Attack — recovering a secret from how long a secret-dependent operation takes for why a single sample never suffices there.

How it's exploited

The methodology is always: define `oracle(input) -> bool`, pin down exactly what property it tests, then encode secret recovery as adaptive queries against that predicate. Two families of predicate cover almost everything seen in practice, and they lead to genuinely different exploit shapes — identifying which one you're facing is the actual triage step:

1. Ordering/threshold oracles — the bit tells you which side of a numeric boundary the hidden value falls on (e.g. "is the decrypted plaintext even or odd", which — via RSA's multiplicative homomorphism — tells you whether doubling the plaintext wrapped past the modulus). This shape reduces to binary search over the secret's domain: maintain an interval, use a mathematical operation on the ciphertext that maps to a known operation on the plaintext (doubling being the classic one for RSA), and halve the interval on every query. log2(domain size) queries recover the exact value. This is the pattern behind RSA LSB / Parity Oracle Attack — recover the plaintext one bit at a time from a decryption oracle — see that page for the full binary-search implementation, precision pitfalls (float vs exact-rational bounds), and the mandatory final re-encryption check. 2. Structural/positional oracles — the bit tells you whether a specific byte or field satisfies a structural constraint (correct PKCS#7 padding, a magic header, a length field), not where a number sits on a number line. This shape reduces to a byte-at-a-time recovery/forgery loop: fix everything except one target byte, brute-force that byte's 256 possibilities against the oracle, lock it in, move to the next. This is the pattern behind CBC Padding Oracle — leak the intermediate decryption value one byte at a time — see that page for the block-by-block loop, the pad=1 false-positive guard, and the "forge, don't just decrypt" extension once you have the intermediate value.

Generic abstract loop shape shared by both families (before you specialize to which one you're in):

```python def oracle(candidate_input) -> bool: # submit candidate_input to the service, interpret its response # as exactly ONE boolean — no other information should leak. ...

# ordering oracle: binary search lo, hi = 0, N for _ in range(N.bit_length()): probe = transform(lo, hi) # e.g. re-double the ciphertext if oracle(probe): lo = midpoint(lo, hi) else: hi = midpoint(lo, hi)

# structural oracle: per-position brute force for position in target_positions: for guess in range(256): if oracle(forge(position, guess)): recovered[position] = guess break ```

Before investing in either loop: confirm the oracle is real. Test it against a deliberately valid input and a deliberately invalid one first. If both come back the same, or the "two classes" turn out to collapse into one under a closer look (a generic catch-all exception, a constant-time comparison, an integrity/MAC check that rejects *before* the structural check you wanted to probe ever runs), there is no exploitable boundary and no amount of query volume fixes that — go back to identifying what the predicate actually is.

Related

RSA LSB / Parity Oracle Attack — recover the plaintext one bit at a time from a decryption oracle for the concrete ordering-oracle implementation against RSA; CBC Padding Oracle — leak the intermediate decryption value one byte at a time for the concrete structural-oracle implementation against CBC; Timing Attack — recovering a secret from how long a secret-dependent operation takes when the only distinguishable signal is latency rather than an explicit error/status/body difference; Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright for a different way a decrypt/sign implementation leaks its secret one query at a time, without needing a boolean response at all; RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism for bypassing a *different* kind of oracle (a blocklist, not a validity check) with the same "chosen-input access" precondition.

What does NOT work

- Treating "the endpoint sometimes errors" as automatically exploitable. The error has to correlate with the *specific* property you want to learn, not with generic malformed input. A catch-all except Exception: return "error" that fires identically whether padding is wrong, the ciphertext is too short, or the server hit an unrelated bug gives you nothing — the classes aren't separated by the property you care about. Confirm separability with deliberately-valid vs deliberately-invalid probes before assuming the oracle is real. - Assuming the query budget is unlimited. Both exploit families are O(log n) or O(bytes × 256), never O(1) — if a challenge caps queries far below what the math requires (e.g. 50 queries against a 2048-bit oracle that needs ~2048), the intended path is a different leak entirely, not this technique squeezed into fewer queries than it needs. - Skipping the "which family is this" step and copy-pasting the wrong loop. An ordering oracle fed into a byte-forgery loop (or vice versa) does not degrade gracefully — it just produces confidently wrong output with no crash, because both loops always terminate with *some* answer. Identify the predicate's actual shape (threshold-on-a-number vs validity-of-a-structural-field) before writing the recovery code, not after it produces garbage. - Trusting a single oracle answer as noiseless ground truth, especially near edge cases. Structural oracles can have positions where a wrong guess accidentally satisfies the check for the *wrong* reason (a coincidental short-padding match, for instance) — treating every "valid" response as unconditionally correct lets one false positive corrupt every byte recovered downstream, since each step typically depends on the previous one being right. Where the concrete attack page documents a specific guard against this, use it; where it doesn't, add a confirmation query before trusting an ambiguous hit. - Building this on a timing signal without statistical treatment. A timing "oracle" is the same methodology in principle but a much noisier oracle() in practice — one measurement is not a boolean, it's a noisy real number, and network/server jitter alone can flip which side of the threshold a single sample lands on. This is a big enough difference in practice that it's its own page: see Timing Attack — recovering a secret from how long a secret-dependent operation takes before wiring latency straight into either loop above.