Noisy Padding Oracle Attack (Statistical Amplification)

Updated 19 Sep 2026

• •

  What it is

  • •

    A variant of the padding-oracle attack where the oracle's Boolean answer isn't reliable — it's randomly corrupted some fraction of the time. As long as the corruption isn't a perfect 50/50 coin flip (the reported answer still carries some correlation, positive or negative, with the truth), repeating each query many times and aggregating results statistically — elimination, majority vote, or a running score — lets the true signal be recovered, exactly as repeated measurements beat noise in any statistical setting.

• •

  When to apply

  • •

    A padding oracle (or any binary oracle) is deliberately noisy — check the exact corruption model, since it changes the right strategy:

    • •

      "OR" noise (result = good | (rng.random() > p)): a true padding is always reported truthfully (no false negatives), but a false padding is falsely reported "true" some of the time. A single False response is always trustworthy — the challenge is confirming a True candidate isn't just noise.

    • •

      "XOR" noise (result = good ^ (rng.random() > p)): the answer is flipped outright with some probability. If that flip probability exceeds 50%, the reported answer is actually anti-correlated with the truth (lies more than it tells the truth) — a naive majority vote gets the sign backwards, so you have to explicitly determine which direction the correlation points before aggregating.

• •

  Math

  • •

    Score each candidate by accumulating $+1$/$-1$ per query outcome (e.g. $\text{score} \mathrel{+}= (-1)^{\text{oracle result}}$), and keep sampling only the current leading candidate (a sequential test) rather than sampling every candidate equally — concentrating the limited query budget on resolving the close call rather than wasting queries confirming already-clear answers. Pick a score threshold empirically: too low risks false positives, too high wastes queries.

• •

  Worked example

  • •

    Suppose a Boolean oracle is correct with probability $0.60$. One positive reply gives likelihood ratio $0.60/0.40=1.5$. Five more positive than negative replies give odds $1.5^5\approx7.59$, or posterior probability about $88\%$ from equal priors. Query counts depend on the measured noise model; a fixed threshold does not imply a universal success rate.

• •

  Python

  • •

    def recover_byte_scored(oracle, make_query, n_candidates=16, threshold=23):
        score = [0] * n_candidates
        while max(score) < threshold:
            i = score.index(max(score))
            score[i] += -1 if oracle(make_query(i)) else 1   # sign depends on the noise model — verify empirically
        return score.index(max(score))
    

• •

  Related

  • •

    CBC Padding Oracle Attack (Vaudenay)

• •

  Cards

  • •

    What property must a noisy oracle retain for statistical amplification to work at all?

    • •

      Some correlation (positive or negative) with the truth — a perfectly 50/50 random oracle carries zero information no matter how many times you query it.

  • •

    Why query only the current leading candidate instead of sampling every candidate equally?

    • •

      It's a sequential test: concentrating queries on the close call resolves ambiguous bytes faster and wastes fewer queries on already-clear ones — important under a hard total query budget.

◌ Explore connections in Graph view