THE GARDEN

Plaintext Recovery via Rejection-Sampling Oracle (Process of Elimination)

Updated 19 Sep 2026

• •

  What it is

  • •

    A subtle failure mode where a server's own "safety check" — refusing to return an output that would obviously leak information (e.g. a ciphertext byte that happens to equal the corresponding plaintext byte) — becomes an information leak in its own right. If a fresh random key/pad is generated on every request, and the server rejects the entire response whenever any byte would trivially leak (ciphertext byte == plaintext byte at that position), then every response you do receive carries a guarantee: at every position, the pad byte used there was never the one specific value that would have caused a leak. Across many successful (non-rejected) responses, the ciphertext byte at a given position will — in the long run — take on every possible byte value except the plaintext byte itself (since that's the one value structurally excluded by the leak check). Tracking, per position, which byte values have been observed and which haven't, the last remaining unobserved value at each position is exactly that position's plaintext byte.

• •

  When to apply

  • •

    A server generates fresh randomness per request, encrypts with a simple XOR/pad-style scheme, and explicitly checks for and rejects "leaky" outputs (ciphertext byte equal to plaintext byte) rather than just always returning the result — the rejection logic itself is the exploitable signal, not any weakness in the pad's randomness.

• •

  Math

  • •

    For a byte position with a uniformly random pad byte conditioned only on "not producing a leak at this position" (equivalent to the pad byte $\ne 0$), the ciphertext byte $c=p\oplus k$ (with $k\ne0$) ranges uniformly over all 255 values except $p$ itself; the coupon-collector-style expected number of successful samples needed to observe all 255 possible values at a single position is $\approx 255\ln(255)\approx1413$, similar for every position simultaneously since all positions are checked (and thus sampled) together on every successful response.

• •

  Worked example

  • •

    At one position, successful samples can show any ciphertext byte except the true plaintext byte. After enough independent accepted samples, the one never observed value is a candidate plaintext byte. The expected coupon-collector scale is about $255H_{255}\approx1561$ accepted samples, but completion has a tail and is never guaranteed at a fixed count.

• •

  Python

  • •

    possible = [set(range(256)) for _ in range(flag_len)]
    while any(len(s) > 1 for s in possible):
            ct = try_request()          # None if the server rejected this trial as "leaky"
            if ct is None:
                continue
            for i, b in enumerate(ct):
                possible[i].discard(b)
    flag = bytes(next(iter(s)) for s in possible)
    

• •

  Cards

  • •

    Why does the server's "leak check" itself become the vulnerability here?

    • •

      Rejecting outputs where ciphertext equals plaintext at any position structurally guarantees that value can never appear in a successful response — turning "never observed" into a direct identification of the plaintext byte.

  • •

    What does a single successful (non-rejected) response actually prove about the pad used, at every position?

    • •

      That the pad byte at every position was nonzero — i.e. the ciphertext byte at every position is guaranteed to differ from the true plaintext byte there.

◌ Explore connections in Graph view