Cryptographic Implementation Security Questions

Direct answer

ROCA (an acronym for "Return of Coppersmith's Attack") targets RSA (Rivest-Shamir-Adleman) keys whose primes were generated by a flawed algorithm (found in a widely-deployed Infineon smart-card and TPM (Trusted Platform Module) library) that produces primes of the special form p = k*M + (65537^a mod M) for a "primorial" M (the product of the first several small primes). That structure is fast to test for at scale: for a basis of small primes, precompute the small cyclic subgroup that 65537 generates modulo each one (the set of values you get by repeatedly multiplying 65537 by itself modulo that prime: 65537, 65537^2, 65537^3, ..., which cycles back around to 1 after a fixed, often small, number of steps), then check whether the public modulus N reduces into that subgroup for every basis prime. A modulus that passes for a wide enough basis is flagged as ROCA-vulnerable and, if confirmed, is factorable via Coppersmith's method in practical time.

Structured elaboration

Why the test works on the PUBLIC modulus alone: if a prime p satisfies p mod p_i is in the subgroup generated by 65537 modulo each basis prime p_i (which the flawed generator guarantees), and q was generated the same way, then N mod p_i = (p mod p_i) * (q mod p_i) mod p_i is also in that subgroup, because a subgroup is closed under multiplication: multiplying any two elements that are already IN the subgroup always produces another element that is also in it, it can never land outside. Concretely, with basis prime 11 from the worked example below, 65537 mod 11 = 10, and the subgroup 10 generates is just {1, 10}; checking all four possible products confirms closure directly: 11=1, 110=10, 101=10, and 1010=100 mod 11=1, every one lands back inside {1, 10}. So you never need to see p or q, only N.

Detecting at scale in a large key repository:

1. Fast fingerprint pass (the ROCA discriminator). Precompute, for each basis prime, the set of values 65537 generates by repeated multiplication modulo that prime. For every key in the repository, check N mod p_i against that precomputed set for each basis prime. This is a handful of modular reductions and set lookups per key, so it scales to millions of keys in a batch job.
2. False-positive control. Each additional basis prime multiplies down the chance a NON-vulnerable, uniformly-random modulus passes by coincidence, because it must independently land in a small subgroup for every prime tested. Choose basis primes where 65537 has SMALL order (a small subgroup), since a prime where 65537 happens to be a primitive root (a generator whose subgroup is not some small piece of the group but the ENTIRE nonzero group) filters nothing at all (every residue is "in the subgroup" trivially).
3. Confirmation, not just flagging. A key that passes the fingerprint test is a CANDIDATE, not a proven break; confirm by actually running Coppersmith's lattice-based factoring method against it (a family of techniques that reformulate factoring as finding one specific short vector inside a carefully constructed multi-dimensional lattice, a grid-like algebraic structure of points, and then use lattice-basis-reduction algorithms to find that vector efficiently; in practice this means invoking a specialized, publicly available tool against a flagged candidate, not implementing the mathematics yourself) (this is the expensive step, so it should run only on the small candidate set the fast pass narrows down to, not the whole repository) or, if you control key generation metadata, by checking the library/firmware version against the known-vulnerable list.
4. Remediation. Any key that confirms as vulnerable must be treated as though the private key is already compromised (factoring times for the affected key sizes are within reach of a modest cloud budget for 1024-bit keys, and were shown practical up to 2048-bit for the weakest cases): revoke the certificate, reissue with a modulus generated by a non-vulnerable library, and audit anything the compromised key protected during its validity window.

Worked example

"""
ROCA-style weak-key fingerprint detector.

Real ROCA (Nemec et al., CCS 2017) keys are generated as p = k*M + (65537^a mod M)
for a "primorial" M (product of the first n small primes) and random k, a. That
construction forces p mod p_i to land inside the small cyclic subgroup of Z_p_i^*
generated by 65537, for every prime p_i dividing M. Because that subgroup property
is preserved under multiplication, N = p*q inherits it too, so the detector can
test the PUBLIC modulus N directly without ever seeing p or q.

This toy version reproduces that exact discriminator on a small basis of primes
and a modulus deliberately generated in ROCA form, then checks it does NOT
false-positive on an ordinary modulus.
"""
import random


def is_prime(n, rounds=40):
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31):
        if n == p:
            return True
        if n % p == 0:
            return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def next_prime(n):
    n += 1 if n % 2 == 0 else 2
    while not is_prime(n):
        n += 2
    return n


def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)


def modinv(a, m):
    g, x, _ = egcd(a % m, m)
    return x % m


GEN = 65537  # the real generator ROCA keys use

BASIS = [3, 5, 7, 11, 13, 17, 19, 23]
M = 1
for p_i in BASIS:
    M *= p_i

# Precompute, for each basis prime, the cyclic subgroup generated by GEN mod p_i.
subgroups = {}
for p_i in BASIS:
    g = GEN % p_i
    seen = set()
    x = 1
    while x not in seen:
        seen.add(x)
        x = (x * g) % p_i
    subgroups[p_i] = seen


def roca_flag(N, basis=BASIS):
    """Return True if N mod p_i lands in the GEN-subgroup for every basis prime."""
    for p_i in basis:
        if N % p_i not in subgroups[p_i]:
            return False
    return True


def false_positive_rate_estimate(basis=BASIS):
    """Chance a UNIFORM random N passes by coincidence: product of |subgroup|/p_i."""
    rate = 1.0
    for p_i in basis:
        rate *= len(subgroups[p_i]) / p_i
    return rate


def gen_roca_prime():
    """Build a prime p = k*M + (65537^a mod M) for random-ish small k, a."""
    a = random.randrange(1, 500)
    r = pow(GEN, a, M)
    k = random.randrange(10**5, 10**6)
    candidate = k * M + r
    if candidate % 2 == 0:
        candidate += M  # keep it odd; M is odd (product of odd primes) so this works
    while not is_prime(candidate):
        candidate += 2 * M  # stay in the same residue class mod each basis prime
    return candidate


print(f"basis primes: {BASIS}")
print(f"primorial M = {M}")
for p_i in BASIS:
    print(f"  subgroup size mod {p_i}: |<{GEN} mod {p_i}>| = {len(subgroups[p_i])} "
          f"(out of {p_i - 1} nonzero residues)")
fpr = false_positive_rate_estimate()
print(f"estimated false-positive rate for a random modulus passing all {len(BASIS)} checks: "
      f"{fpr:.2e}")

print()
print("=== Vulnerable modulus (both primes generated in ROCA form) ===")
random.seed(42)
p_vuln = gen_roca_prime()
q_vuln = gen_roca_prime()
N_vuln = p_vuln * q_vuln
print(f"p bit-length={p_vuln.bit_length()}, q bit-length={q_vuln.bit_length()}, "
      f"N bit-length={N_vuln.bit_length()}")
print(f"roca_flag(N_vuln) = {roca_flag(N_vuln)}")

print()
print("=== Control: ordinary modulus from two random primes (not ROCA form) ===")
random.seed(7)
p_ok = next_prime(random.randrange(2**100, 2**101))
q_ok = next_prime(random.randrange(2**100, 2**101))
N_ok = p_ok * q_ok
print(f"N_ok bit-length={N_ok.bit_length()}")
print(f"roca_flag(N_ok) = {roca_flag(N_ok)}")

failing = [p_i for p_i in BASIS if N_ok % p_i not in subgroups[p_i]]
print(f"basis primes that immediately reject N_ok: {failing}")

Output:

basis primes: [3, 5, 7, 11, 13, 17, 19, 23]
primorial M = 111546435
  subgroup size mod 3: |<65537 mod 3>| = 2 (out of 2 nonzero residues)
  subgroup size mod 5: |<65537 mod 5>| = 4 (out of 4 nonzero residues)
  subgroup size mod 7: |<65537 mod 7>| = 6 (out of 6 nonzero residues)
  subgroup size mod 11: |<65537 mod 11>| = 2 (out of 10 nonzero residues)
  subgroup size mod 13: |<65537 mod 13>| = 6 (out of 12 nonzero residues)
  subgroup size mod 17: |<65537 mod 17>| = 8 (out of 16 nonzero residues)
  subgroup size mod 19: |<65537 mod 19>| = 9 (out of 18 nonzero residues)
  subgroup size mod 23: |<65537 mod 23>| = 22 (out of 22 nonzero residues)
estimated false-positive rate for a random modulus passing all 8 checks: 8.18e-03

=== Vulnerable modulus (both primes generated in ROCA form) ===
p bit-length=45, q bit-length=46, N bit-length=90
roca_flag(N_vuln) = True

=== Control: ordinary modulus from two random primes (not ROCA form) ===
N_ok bit-length=202
roca_flag(N_ok) = False
basis primes that immediately reject N_ok: [11, 13]

Note the real finding from running this: the basis prime 23 filtered NOTHING here, because 65537 happens to be a primitive root modulo 23 (as defined above, its subgroup is the entire nonzero group, not just a small piece of it). A real ROCA detector deliberately selects basis primes where 65537 has small order, and uses far more of them (dozens to low hundreds) than this eight-prime toy basis, which is why the published detector's false-positive rate is negligible rather than the roughly 1-in-100 shown above.

Trade-offs and pitfalls

• The fingerprint test is a NECESSARY but not SUFFICIENT condition; treat a match as "queue for confirmation," never as "confirmed broken," especially with a small basis where coincidental matches are not vanishingly rare.
• Basis-prime SELECTION matters more than basis-prime COUNT: a prime where 65537 is close to a primitive root contributes almost nothing (as seen with 23 above), so a naive "just add more small primes" approach wastes computation without meaningfully improving the false-positive rate.
• Running Coppersmith confirmation against every candidate at repository scale is expensive; the two-stage design (cheap fingerprint filter, then expensive confirmation only on survivors) is what makes this tractable against millions of keys.
• This detects ONE specific flawed generation pattern. A repository-wide key-health sweep should also separately check for classic weaknesses (shared/duplicate primes across keys via batch-GCD, small key sizes, common default keys) that ROCA fingerprinting will not catch.

Direct answer

Build this as a two-tier telemetry system: an EXACT, bounded-memory check for cryptographic misuse patterns that can be verified deterministically (nonce and IV (initialization vector) reuse under a known key, deprecated algorithm usage, certificate mis-issuance against a known-good policy), plus a PROBABILISTIC layer (a Bloom filter or similar sketch) for anything that needs to scale past what exact tracking can hold in memory, with every alert's confidence and cost characterized analytically, not asserted. Route telemetry through sampling and aggregation tuned per misuse class (some classes need every event, others tolerate sampling), and treat automated mitigation as tiered by severity, never a blanket auto-block on a probabilistic signal alone.

Structured elaboration

Telemetry sources: instrument the cryptographic LIBRARY CALL SITES themselves (a thin wrapper or an eBPF (extended Berkeley Packet Filter)/agent-based hook around the actual encrypt/decrypt/sign calls, not just application-level logs, since misuse can happen below what application code even sees), TLS (Transport Layer Security) termination points for certificate and cipher-suite telemetry, and configuration/inventory scanners that periodically audit which algorithms and key sizes are actually deployed across the fleet (catching deprecated-algorithm drift that no single request-level event would surface).

Sampling strategy, matched to what each misuse CLASS actually needs:

• Nonce/IV reuse detection needs EVERY event, not a sample, because the whole point is catching the specific pair of reused values, and a sampled-away instance is a silently missed detection, not a smaller but still valid signal.
• Deprecated-algorithm-in-use and certificate-mis-issuance detection tolerate aggregation (periodic inventory sweeps, or counting occurrences per time window) rather than per-event capture, since the question is "is this happening at all and how often," not "catch this exact instance."

Anomaly-detection heuristics and false-positive reduction, worked through for the flagship example (nonce/IV reuse), since it generalizes to the others:

• Maintain an EXACT recent-window set per (key_id, algorithm) pair for nonce/IV values seen, with FIFO (first-in, first-out) eviction once a size cap is hit, giving zero false positives within the tracked window at a bounded, predictable memory cost.
• For the long-tail archive beyond what an exact set can hold in memory, a Bloom filter trades a SMALL, ANALYTICALLY COMPUTED false-positive rate for bounded memory at much larger scale, and critically never produces a false NEGATIVE, a real reuse is never silently missed, only occasionally a non-reuse gets an extra (cheap, verifiable) confirmation check.
• Reduce false positives by requiring corroboration before auto-mitigating: a Bloom-filter hit alone triggers a cheap exact re-check (a targeted database/log lookup) before any automated action, keeping the probabilistic layer's occasional false alarm from ever reaching an automated response on its own.

Worked example

"""
a minimal streaming nonce/IV-reuse detector, the kind of anomaly heuristic
a production telemetry pipeline would run per (key_id, algorithm).

Real deployments cannot hold every historical nonce in memory forever at scale,
so this shows the two honest tiers: an exact in-memory set for a bounded
recent window (zero false positives, bounded memory), and a probabilistic
Bloom filter for the long-tail archive (bounded memory, a tunable and
CALCULATED false-positive rate, never a false negative).
"""
import hashlib


class ExactWindowDetector:
    """Exact recent-window check: a set per key_id, capped and evicted FIFO."""
    def __init__(self, capacity=100_000):
        self.capacity = capacity
        self.seen = {}          # key_id -> set of nonces
        self.order = {}         # key_id -> list preserving insertion order for eviction

    def check_and_record(self, key_id, nonce):
        s = self.seen.setdefault(key_id, set())
        o = self.order.setdefault(key_id, [])
        if nonce in s:
            return True         # REUSE DETECTED
        s.add(nonce)
        o.append(nonce)
        if len(o) > self.capacity:
            oldest = o.pop(0)
            s.discard(oldest)
        return False


class BloomFilter:
    """Simple Bloom filter for the long-tail archive: bounded memory, tunable
    false-positive rate, computed analytically from (bits, num_hashes, n_items)."""
    def __init__(self, size_bits, num_hashes):
        self.size_bits = size_bits
        self.num_hashes = num_hashes
        self.bits = bytearray(size_bits)

    def _hashes(self, item):
        for i in range(self.num_hashes):
            h = hashlib.sha256(f"{i}:{item}".encode()).digest()
            yield int.from_bytes(h, "big") % self.size_bits

    def add(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = 1

    def might_contain(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))


def expected_false_positive_rate(size_bits, num_hashes, n_items):
    return (1 - (1 - 1 / size_bits) ** (num_hashes * n_items)) ** num_hashes


exact = ExactWindowDetector(capacity=1000)
events = [
    ("keyA", "nonce_0001"),
    ("keyA", "nonce_0002"),
    ("keyB", "nonce_0001"),   # different key_id, same nonce string: NOT a reuse
    ("keyA", "nonce_0002"),   # same key_id, repeated nonce: REUSE
]
print("=== exact recent-window detector ===")
for key_id, nonce in events:
    reused = exact.check_and_record(key_id, nonce)
    flag = "ALERT: nonce reuse under this key" if reused else "ok, first time under this key"
    print(f"  {key_id} / {nonce}: {flag}")

n_items = 10_000_000
size_bits = 100_000_000       # ~12.5 MB
num_hashes = 5
fpr = expected_false_positive_rate(size_bits, num_hashes, n_items)
print(f"\n=== archive Bloom filter sizing ===")
print(f"bits={size_bits:,}, hash functions={num_hashes}, items={n_items:,}")
print(f"computed false-positive rate: {fpr:.6f} ({fpr*100:.4f}%)")
print("false-NEGATIVE rate is always exactly 0 for a Bloom filter: a real reuse is never missed,")
print("only an occasional false alarm on a nonce that was never actually reused.")

bloom = BloomFilter(size_bits=10_000, num_hashes=3)
bloom.add("nonce_abc")
print(f"\nsmall bloom demo: 'nonce_abc' in filter -> {bloom.might_contain('nonce_abc')}")
print(f"                  'nonce_xyz' in filter -> {bloom.might_contain('nonce_xyz')}")

Output:

=== exact recent-window detector ===
  keyA / nonce_0001: ok, first time under this key
  keyA / nonce_0002: ok, first time under this key
  keyB / nonce_0001: ok, first time under this key
  keyA / nonce_0002: ALERT: nonce reuse under this key

=== archive Bloom filter sizing ===
bits=100,000,000, hash functions=5, items=10,000,000
computed false-positive rate: 0.009431 (0.9431%)
false-NEGATIVE rate is always exactly 0 for a Bloom filter: a real reuse is never missed,
only an occasional false alarm on a nonce that was never actually reused.

small bloom demo: 'nonce_abc' in filter -> True
                  'nonce_xyz' in filter -> False

Automated mitigation actions, tiered by confidence and severity: an EXACT nonce-reuse detection (zero false-positive risk within the tracked window) can justify an automated response proportionate to blast radius, meaning how much of the system or how many users a mistaken automated action could affect: rotate the implicated key, and alert on-call immediately for anything touching production traffic; a Bloom-filter-only hit, before exact corroboration, should trigger investigation and the confirmation check described above, never a direct automated block, since acting on an analytically-nonzero false-positive rate without confirmation risks disrupting legitimate traffic on a signal that is, by design, sometimes wrong.

Privacy and data-retention considerations: nonce and IV values themselves are not secret, but the METADATA around them (which key, which service, which caller, at what volume) can reveal sensitive information about system architecture and usage patterns; apply the same retention discipline as any other security telemetry (a bounded retention window, access controls on the raw event stream, aggregation before long-term storage) rather than treating cryptographic misuse telemetry as exempt from the organization's general data-handling policy just because it is security-motivated.

Trade-offs and pitfalls

• The most consequential design mistake is applying UNIFORM sampling across all misuse classes; nonce/IV reuse detection silently degrades to "sometimes catches reuse" under sampling, which defeats its entire purpose, while other classes waste storage and processing capturing every event when aggregation would serve just as well.
• Automating mitigation directly off a probabilistic (Bloom-filter) signal, without the cheap exact-confirmation step, trades a security win for an availability risk (legitimate traffic disrupted on a false positive); the corroboration step is not optional overhead, it is what makes automated response on the probabilistic layer SAFE to enable at all.
• Instrumenting at the library call site (rather than only at the application log level) is more invasive to deploy but catches misuse that application-level logging structurally cannot see; the deployment cost is real and the coverage gap from skipping it is easy to underestimate until an incident reveals it.

Direct answer

As the on-call cryptographer, the priority order is: bound the scope of the reuse from logs and ciphertexts, stop further reuse immediately (rotate the key and fix the nonce-generation bug, in that order of urgency), then run the forensics and rotation plan needed to actually recover trust, in parallel with the parts of this that are not purely technical: customer communication, legal and PR involvement, and a long-term root-cause verification that proves the same bug class cannot silently recur. Treat AES-GCM (Galois/Counter Mode, an authenticated encryption mode) nonce reuse as a confidentiality AND integrity incident, not just a confidentiality one, since a reused nonce can also expose the authentication subkey and enable forged messages, not only leak plaintext.

Structured elaboration

Detecting the scope from logs and ciphertexts

• Correlate every logged (key identifier, nonce) pair across all systems and services that could have used the affected key; a repeated pair is direct proof of reuse, and the surrounding log entries bound exactly which messages are affected.
• If nonces are not directly logged, look for the usual root causes of accidental reuse and search for their fingerprints: a counter-based nonce scheme that reset to zero on a service restart or failover (correlate reuse timestamps against deployment and restart events), a nonce derived from a source with insufficient entropy, or a copy-pasted encryption call that accidentally shares a nonce source across two different features.
• Cross-reference every system that shares the affected key, not just the one where the bug was found; a symmetric key reused across services multiplies the population of potentially-colliding nonces well beyond the single buggy code path.

Immediate mitigation

• Rotate the affected key immediately, this is the single action that stops further reuse from happening, regardless of whether the root cause is understood yet.
• Take the vulnerable encryption path out of service or hotfix the nonce generation (restore correct counter semantics, or move to a construction where accidental collision is effectively impossible, such as a random 192-bit nonce scheme like XChaCha20-Poly1305 instead of GCM's standard 96-bit nonce).
• Because nonce reuse in GCM can expose the authentication subkey, not just the keystream, treat every message ever authenticated under the compromised key as potentially forgeable until forensics proves otherwise, not just the messages with confirmed plaintext exposure.

Remediation plan

• Forensics: for every confirmed reused-nonce pair, determine whether the associated plaintexts are actually recoverable (does the attacker have or can they guess enough of one message to recover the other via the keystream-reuse mechanism), so the eventual customer and legal communication can be precise about impact rather than maximally alarming or falsely reassuring.
• Key rotation: rotate the compromised key everywhere it is used, and audit for any other key shared across the same set of services, since key sharing across features is frequently the actual root enabler of a nonce-space collision.
• Recovering trust: re-issue or re-encrypt any data or tokens whose integrity depended on the compromised key, and add an automated nonce-uniqueness or monotonicity check to the release pipeline so this failure mode is caught before deployment, not after.

The broader incident-response arc

• Customer communication: a factual, appropriately scoped disclosure, naming what data category was plausibly exposed and, just as importantly, what was NOT, coordinated with legal so the technical claims in the notice are accurate and do not overcommit on language the forensics cannot yet support.
• Legal and PR considerations: breach-notification obligations vary by jurisdiction and by the category of data in the affected messages, so legal needs the bounded forensic scope BEFORE any external statement goes out; PR needs a contingency plan for the case where details leak or a proof-of-concept becomes public before the fix is fully deployed everywhere.
• Long-term root-cause verification: do not close the incident once the immediate leak is plugged. Confirm precisely why the nonce generator produced a duplicate, and add regression coverage that would fail the build if the same class of bug reappeared, since "we rotated the key" fixes the symptom, not the generator that will collide again on the new key if the underlying logic is unfixed.

Worked example

Illustrative runbook ordering, not a timed schedule (concrete hour-by-hour timing is environment- and incident-specific and would be fabricated precision to state here): detect the reuse pattern from log correlation, capture a full snapshot of the affected traffic and key-usage logs BEFORE or DURING rotation so the forensic evidence is not lost to the fix itself, rotate the key and patch the nonce generator, run the recoverability analysis on the captured snapshot to bound actual plaintext exposure, hand the bounded scope to legal and customer-communications teams for a disclosure decision, and only then close the incident once a regression test proving nonce uniqueness is merged and passing in CI (continuous integration).

Trade-offs and pitfalls

The sharpest trade-off is speed versus evidence: rotating the key immediately stops further damage but can destroy the only evidence available to bound the incident's actual scope if it is not paired with capturing a full snapshot of the affected logs and ciphertexts first (or, if that is not feasible fast enough, simultaneously with rotation rather than after it). A common pitfall is treating key rotation alone as remediation and closing the incident before the nonce-generation root cause is actually fixed, the new key is exposed to the exact same bug and will eventually collide again. Another pitfall is letting legal and customer-communication timelines drive the technical investigation instead of the other way around: an incident notice sent before forensics has bounded the actual exposure risks both under-disclosing (a compliance and trust problem) and over-disclosing (unnecessary alarm, and a claim that may later have to be walked back).

Direct answer

Detecting a padding-oracle attack in server-side logs and traces means looking for the ATTACK'S SHAPE, not any single request: a burst of many structurally similar ciphertexts against the same endpoint, differing only in a few bytes at a time, with response CHARACTERISTICS (error codes, response sizes, or timing) that cluster into two statistically distinguishable groups. Extract those features per request, score requests in rolling windows with a statistical test comparing the observed response-type distribution against what benign traffic looks like, and alert when a client's traffic crosses a confidence threshold for that pattern, while keeping the detector robust to normal traffic noise (retries, load balancers, legitimate malformed requests from buggy clients).

Structured elaboration

Features to extract per request/response pair:

• Ciphertext similarity to prior requests from the same client. A real Bleichenbacher-style or CBC (cipher block chaining) padding-oracle attack sends THOUSANDS of ciphertexts that are bit-flips or block-manipulations of a small number of base ciphertexts, not independent random traffic; a rolling similarity or edit-distance measure against recent requests from the same source is a strong structural signal.
• Response timing, bucketed. Even where the response CODE is identical (a "fixed" implementation), a residual timing difference between padding-valid and padding-invalid paths sometimes survives; bucket timing into fine intervals and track whether they cluster bimodally rather than following the expected single distribution of normal traffic.
• Response/error-code distribution. Any two-valued (or more) DISTINGUISHABLE outcome (distinct error codes, distinct response body lengths, distinct headers) associated with decryption/padding failure is the classic signal; track the RATE at which each response type occurs per client, per time window.
• Repeated ciphertexts, or near-repeats differing by one block/byte. Legitimate traffic essentially never resends the exact same ciphertext, or a version differing by exactly one manipulated byte, hundreds of times in a short window; this is one of the highest-precision features because benign explanations for it are rare.

Statistical detection method:

• Maintain a per-client (or per-source-IP) rolling window and compute the response-type distribution within it; compare it against a BASELINE distribution built from historical benign traffic using a chi-square or two-proportion test (the same statistical machinery used to test a suspected padding oracle directly against a target, applied here to CLASSIFY incoming traffic instead).
• Combine that with the similarity/repeat-ciphertext feature as a STRONG PRIOR: traffic that is both statistically anomalous in response-type distribution AND structurally similar in ciphertext content is a much higher-confidence signal than either feature alone, which is how you push false positives down without needing an implausibly extreme statistical threshold on either feature individually.

Reducing false positives:

• Whitelist known-benign sources of malformed traffic (health checks, vulnerability scanners with an authorized allowlist, retry logic in known client libraries that legitimately resends similar payloads).
• Require the ANOMALY to persist across a minimum request count and time window before alerting, since a handful of malformed requests from a normal client (a buggy integration, a flaky network causing retries) should not trigger the same response as a sustained few-thousand-request campaign.
• Weight the SIMILARITY feature heavily; independent, unrelated malformed requests from different legitimate sources will rarely resemble each other, whereas a real attack's requests are systematically related to each other by construction.

Remediation actions on detection:

• Rate-limit or temporarily block the offending source while the alert is triaged, since a real attack needs a very large query volume and slowing it down materially raises the attacker's cost.
• Escalate to a code review of the flagged endpoint's error handling specifically, since a detected campaign is strong evidence the oracle actually exists and needs the protocol/implementation-level fix (unify all decryption-failure responses), not just traffic-level mitigation.

Worked example

Walk one campaign through the pipeline: a source IP begins sending thousands of requests over a short window to a decryption endpoint, each ciphertext differing from the last by exactly one manipulated byte in the final block, a textbook CBC (cipher block chaining)-mode bit-flipping pattern. The similarity feature flags this immediately (near-identical ciphertexts, high correlation across the window). The response-type feature shows two error codes appearing at a heavily skewed ratio across the window, correlated with which byte value was tried, rather than the single dominant error code normal traffic would show. Combined, the two features push the anomaly score for this source well past the alerting threshold long before the attack would have gathered enough queries to complete a real recovery, and the system rate-limits the source while flagging the endpoint's error-handling code for review.

Trade-offs and pitfalls

• A detector tuned only on response-CODE distribution will miss a TIMING-only oracle entirely (the response bodies look identical); the timing feature is more expensive to compute reliably (needs careful baseline calibration per endpoint) but closes that gap.
• Over-aggressive similarity thresholds will false-positive on legitimate retry storms (a flaky client resending the same request many times); tuning the similarity feature against real production retry patterns before deployment is necessary, not optional.
• Detection is a MITIGATION, not a fix: it buys time and evidence, but the actual defect (a distinguishable padding-failure signal) still needs to be removed from the implementation regardless of how well the detector performs.