Include request timing in threat model? Add timeout noise between polled requests?

[DanGould]

Adding noise may make for better privacy against metadata timing attacks in some circumstances

For a given subdirectory ID, the amount of time in between requests that the directory sees before this change was 5 seconds + R_i, where R is the round trip latency to the relay and i indexes { Alice, Bob or Carol }.

The directory will is able to measure R_i indirectly before this change, and almost directly after it, thereby potentially identifying who is the receiver and who is the sender, since those roles are distinguishable based on the latency patterns of a pair of potentially related (i.e. temporally close but satisfying the ordering constraints of the BIP 77 messaging patterns). In other words R_i is potentially identifying metadata that leaks for each subdirectory, and by correlating different subdirectories (for which differences in this noisy measurement are helpful), the directory could still heuristically identify the parties involved, or at least learn some information or constraints about them with the same difficulty both before and after this change.

If on the other hand the spec encouraged clients to first sample some additional noise to artificially add to the latency, I believe that would address the conern desscribed in the PR more comprehensively than simply divergence in fixed values chosen by different implementations.

Note that this noise could in principle be negative too, by sending the next request slightly before an in flight one is expected to time out and return, at the cost of a low probability of small waste in bandwidth.

...
I'm not convinced such metadata leaks are justifiably in the threat model. Thoughts?

Originally posted by @nothingmuch in #436 (review)

• Calculate under which traffic conditions timing analysis exposes an attack to which adversaries with vs without noise between requests
• Decide if this can be rolled out optionally or gradually in only a few implementations, or if it must be enforced in all implementations given that live implementations make OHTTP requests without any noise
• Decide yea or nay to include timing attacks in the threat model
• If yea, Document the decision in BIP 77
• If yea, Implement in payjoin-cli reference and other implementations under our maintainership

[benalleng]

Does this metadata timing attack still remain meaningful with the more modern addition of random relay selection

[nothingmuch]

Does this metadata timing attack still remain meaningful with the more modern addition of random relay selection

yes, c.f. literature on statistical disclosure attacks. timing metadata is an inherent risk for any such protocol and can't really be solved within the model of a particular protocol without making very strong assumptions. but it can be mitigated.

random relay selection makes the threat model a lot less sensitive to do this, i.e. an adversary would have to corrupt the user's ISP to account for the split. the relay selection procedure i described in #919 does make it harder for an individual corrupt relay to gain useful information, so it hardens against this, but doesn't eliminate this issue.

ultimately if an ISP sees a pattern of activity that relates to relays known to be used with payjoins, all of the potential payjoin looking transaction broadcast shortly after the communication pattern of the session ceases are more likely. if the clusters associated with that transaction also have metadata associated with the traffic information (for instance suppose one of two candidate transactions a cluster associated with an exchange that only operates in some markets but those markets are in agreement with the IP level metadata recovered from traffic analysis, that isn't conclusive but definitely suggests that one transaction is more likely than another to be the payjoin whose traffic patterns were observed).

the only way to categorically eliminate this is to have every payjoin user generate traffic continuously (strictly speaking, in perpetuity) which is just in no way practical or realistic on any level.

however, with random relay selection and some cover traffic (see various discussions i posted in particular on #582), then i would say the problem is probably mitigated to the extent that it's reasonable to try and mitigate that.

[nothingmuch]

@Mshehu5 @bc1cindy do you remember where we discussed specifically the timing issues WRT the stateless algorithm? specifically i'm referring to the nuance of sampling relays with vs. without replacement

at any rate, to reiterate: if you take the list of relays and shuffle it, then go through the list one by one (sampling without replacement) then that leaks slightly more information to relays through timing patterns about how many relays you are using.

if instead you picked a random relay statelessly every time (which is what the latest iteration of #919's proposed approach is), then in the limit this is the same (the rate of requests per relay is inversely proportional to the number of relays being used by the client) but the sampling without replacement approach converges on this limit faster than simply picking randomly.

i think a good way to think about #919 is as 3 populations: the GET request population, the buffer population (unused), and the POST request population. relays move from GET to buffer to POST and from POST to buffer to GET pools as a function of time, where the buffer relays are not used at all (to account for clock skews), and GET/polling requests use the GET pool and message requests use the POST pool.

because the sampling is done from disjoint populations, the random choice of relay itself can reduce the leaks from the choice of relay itself.

the main practical implication of that for timing is that with this stateless approach that permits sampling with replacement, the communication pattern observed by each relay is closer to a Poisson process as opposed to a periodic process with variance.

however, it's still a stationary Poisson process, and as stated above over time its rate or density is still leaked. a good way to confound such analysis is through varying the timing of requests.

tl;dr - the details of how relay selection is done also informs the analysis of how much timing information is leaked, and stateless (but time dependent) relay selection makes it easier to analyze the temporal leak mitigations (cover traffic & random jitter in request timing, both of which make the observed timeline of observations of a single relay or a single client's traffic patterns closer to an inhomogenous Poisson process, which is a a pretty uncontroversial notion of an uninformative prior)

[bc1cindy]

@nothingmuch the with/without-replacement nuance is written up in #919 comment

"tradeoffs of randomizing per request vs. per session, and randomizing statelessly or statefully"

it's tracked cross-integration under #1586, which in practice shows integrations polling at 2s/5s/~30s, distinguishable today.

@benalleng yes, #919 proposal is AS-aware relay/AS selection (the spatial axis); by design it doesn't add jitter or cover traffic to request timing, so the 5s + R_i cadence is untouched, it hardens the spatial axis but the rate still leaks, timing stays a distinct layer on top

[bc1cindy]

analysis (calibrated, full mitigation stack) Simulated the directory's per-short-ID poll timing, calibrated with real data:

cadences from #1586 (BBM on a fixed 5s timer; everything else cli/ldk/boltz/liana/cake on the ~30s long-poll, cake being long-poll + a 2s sleep) and R_i anchored to measured TCP-handshake RTTs to the live relays (payjoin.lab.vinteum.org 70ms · ohttp.cakewallet.com 104ms · payjoin.achow101.com 143ms · payjo.in 149ms · mailroom.luisschwab.net 151ms · pj.bobspacebkk.com 307ms). The signal that distinguishes the two parties is the difference in round-trip time between sender and receiver (same relay, different locations), so I swept that gap from 20ms (similar-region users) to 250ms (cross-continent), a range consistent with the ~240ms spread those single-client measurements show network distance alone can produce. 20ms is conservative: even there the role is already distinguishable (0.62), and the fix (B2) cancels the latency at any gap.

• A - response-gated (today): the client re-polls only after the previous response returns, so each cycle = cadence + R_i. This is the long-poll path (payjoin-cli / ldk-node / Boltz / Liana) and the issue's original 5s + R_i framing; Cake's sleep loop is the same regime, a response-gated await on the long-poll, then a 2s sleep. (note: BBM's Timer.periodic is the one schedule-driven outlier, so R_i largely cancels for it, but it still leaks its fixed 5s cadence. That's exactly the point below: being scheduled is not enough on its own.)
• B1 - gated + jitter (naive): add random jitter on top of that same gated loop.
• B2 - schedule-driven Poisson (the fix): poll on an independent clock (random/Poisson gaps), decoupled from the response, with a uniform average rate (Loopix-style). This fixes both axes at once: R_i becomes a constant offset that cancels in the gaps between requests, AND the fixed cadence is replaced by a uniform rate.
• +cover - Loopix loop traffic: poll even when idle, to address the residual (whether a session is active at all).

how well the directory can attack (0.5 = coin flip, 1.0 = certain; adversary = directory, a relay sees only a subset, an ISP sees per-client):

Directory attack	A (today)	B1 (gated+jitter)	B2 (the fix)
Identify BBM vs the long-poll group (chance 0.50)	1.00	1.00	0.49
Sender vs receiver - 20 ms gap	0.62	0.60	0.50
Sender vs receiver - 100 ms gap	0.92	0.91	0.51
Sender vs receiver - 250 ms gap	1.00	1.00	0.51

role rows: directory correlating N=500 polls × K=20 subdirectories (strong-correlation case).

the naive jitter (B1) isn't enough because the role leak accumulates as the directory correlates more requests/subdirectories:

Role AUC (100 ms gap)	few obs (N=100, K=1)	many (N=500, K=20)
A	0.92	0.92
B1	0.63	0.90
B2	0.49	0.50

B1 climbs (statistical disclosure); B2 stays at coin-flip, no latency signal left to accumulate.

residual + cover traffic. after B2, the directory can still tell when a session is active (the short ID is being polled at all).

cover/loop traffic: polling even when idle, The Loopix Anonymity System, hides this in the short term, but over long observation the rate still gives it away; fully hiding it would need heavy, perpetual cover, which is impractical (worse on mobile, #1586). So cover mitigates the residual, it doesn't eliminate it.

a wallet polling on a Poisson schedule looks obviously different from one that isn't, so this only helps if adopted uniformly / at the spec level, not one wallet at a time.

the data says yes: the leak is real and mitigable, with the caveat that mitigation means switching to schedule-driven polling, not bolting jitter onto the current loop.

Decide yea or nay to include timing attacks in the threat model

enough to say yea or nay?

if we include it in the threat model, should I follow documenting in BIP 77 wording in the network privacy, alongside the existing Uniform Payloads, poll timing as an independent Poisson schedule (random gaps, uniform average rate), with optional cover traffic for the residual, then implement in payjoin-cli and the bindings?

simulation code

#!/usr/bin/env python3
"""
Timing-leak simulation for payjoin #440 (step-1 analysis), calibrated with real
data:
  - cadences from #1586: BBM on a fixed 5s timer; everything else
    (cli/ldk/boltz/liana/cake) on the ~30s long-poll (cake = long-poll + 2s sleep);
  - R_i (round-trip latency) range anchored to MEASURED RTTs to the real relays
    (payjoin.lab.vinteum.org 70ms ... pj.bobspacebkk.com 307ms), so the
    sender/receiver gap is swept over an empirically justified 20-250ms.

Adversary = directory (per short ID point process of polls).

Three client designs (the key distinction):
  A  -- response-gated polling (TODAY): re-poll waits for the response, so each
        cycle = cadence + R_i  ->  R_i is in every inter-arrival.
  B1 -- gated + Poisson jitter (NAIVE noise): cadence + R_i + Exp(J). R_i is
        STILL in every cycle (jitter only adds variance) and the cadence is
        still in the mean.
  B2 -- schedule-driven Poisson (LOOPIX-faithful): poll on an independent
        Poisson clock, NOT gated on the response. Then R_i is a constant offset
        on every arrival time and CANCELS in the inter-arrivals; the cadence is
        replaced by a uniform rate.  -> only the rate leaks; R_i is gone.

Pure stdlib, deterministic (seed). Cover traffic = a separate (activity/session)
layer, noted but not the R_i mechanism (see notes at bottom).
"""

import math
import random
import statistics

SEED = 440
random.seed(SEED)

# ----- calibration -----------------------------------------------------------
CADENCES = {"bbm": 5.0, "longpoll": 30.0}   # bbm schedule-driven 5s; cli/ldk/boltz/liana/cake all ~30s long-poll
RBAR_SENDER = 0.10          # base per-party RTT (s); ~median of measured 70-307ms
SIGMA_POP = 0.05            # population spread of per-party RTT (s)
SIGMA_NET = 0.02            # per-request network jitter (s); from relay samples
J_B1 = 2.0                  # B1 added Poisson jitter mean (s)
MU_B2 = 5.0                 # B2 schedule-driven Poisson mean inter-arrival (s)
N_SESSIONS = 1500

# gap = sender/receiver RTT gap to the same relay (empirically: 20-250 ms)
DELTA_SWEEP = [0.02, 0.05, 0.10, 0.25]
N_SWEEP = [100, 500]
K_SWEEP = [1, 20]


# ----- model -----------------------------------------------------------------
def gen_intervals(variant, cadence, rbar, n):
    out = []
    for _ in range(n): 
        if variant == "A":                       # gated: R_i in each cycle
            x = cadence + rbar + random.gauss(0, SIGMA_NET)
        elif variant == "B1":                    # gated + jitter: R_i still there
            x = cadence + rbar + random.expovariate(1.0 / J_B1)
        else:                                    # B2: schedule-driven -> R_i cancels
            x = random.expovariate(1.0 / MU_B2) + random.gauss(0, SIGMA_NET * 1.414)
        out.append(max(x, 1e-6))
    return out


def estimate_rbar(intervals, variant, cadence):
    m = statistics.fmean(intervals)
    if variant == "A": 
        return m - cadence
    if variant == "B1":
        return m - cadence - J_B1
    return m - MU_B2                             # B2: no R_i in the signal


def predict_integration(intervals, variant):
    """Strongest adversary: knows the variant's non-cadence offset, subtracts it,
    then nearest cadence."""  
    m = statistics.fmean(intervals)
    off = {"A": 0.0, "B1": J_B1, "B2": MU_B2}[variant]
    feat = m - off
    return min(CADENCES.values(), key=lambda c: abs(c - feat))


def auc(pos, neg):
    lab = sorted([(s, 1) for s in pos] + [(s, 0) for s in neg], key=lambda t: t[0])
    ranks = [0.0] * len(lab)
    i = 0 
    while i < len(lab):
        j = i
        while j + 1 < len(lab) and lab[j + 1][0] == lab[i][0]:
            j += 1
        for k in range(i, j + 1):
            ranks[k] = (i + j) / 2.0 + 1.0
        i = j + 1
    sp = sum(ranks[idx] for idx, (_, l) in enumerate(lab) if l == 1)
    return (sp - len(pos) * (len(pos) + 1) / 2.0) / (len(pos) * len(neg))


# ----- experiments -----------------------------------------------------------
def role_and_ri(variant, delta, n, k):
    es, er = [], [] 
    sq = 0.0
    cnt = 0
    names = list(CADENCES)
    for _ in range(N_SESSIONS):
        cad = CADENCES[random.choice(names)]
        for role, mu in (("s", RBAR_SENDER), ("r", RBAR_SENDER + delta)):
            true_r = random.gauss(mu, SIGMA_POP)
            est = statistics.fmean(
                estimate_rbar(gen_intervals(variant, cad, true_r, n), variant, cad)
                for _ in range(k))
            (es if role == "s" else er).append(est)
            sq += (est - true_r) ** 2
            cnt += 1
    return auc(er, es), math.sqrt(sq / cnt)


def poisson(lam):
    """Poisson sample (Knuth for small lam, normal approx for large)."""
    if lam < 30:
        L = math.exp(-lam)
        k, p = 0, 1.0
        while True:
            k += 1
            p *= random.random()
            if p <= L:
                return k - 1
    return max(0, round(random.gauss(lam, math.sqrt(lam))))


def cover_activity_auc(rho, n_real, windows=4000):
    """Residual leak AFTER B2: can the directory detect WHEN a real session is
    active?  Cover/loop traffic (Loopix) keeps the client polling when idle.
      idle window   ~ Poisson(rho * n_real)            (cover only)
      active window ~ Poisson((1 + rho) * n_real)      (cover + real)
    rho = cover_rate / real_rate ; n_real = expected real polls in the window.
    AUC = separability of active vs idle by the observed poll count."""
    active = [poisson((1.0 + rho) * n_real) for _ in range(windows)]
    idle = [poisson(rho * n_real) for _ in range(windows)]
    return auc(active, idle)


def integration_acc(variant, n):
    names = list(CADENCES)
    correct = 0
    for _ in range(N_SESSIONS):
        nm = random.choice(names)
        cad = CADENCES[nm]
        rbar = random.gauss(RBAR_SENDER, SIGMA_POP)
        if predict_integration(gen_intervals(variant, cad, rbar, n), variant) == cad:
            correct += 1
    return correct / N_SESSIONS


# ----- main ------------------------------------------------------------------
def main():
    print(f"#440 timing-leak sim (seed={SEED}, {N_SESSIONS} sessions/config)")
    print("calibration: cadences {5,30}s (#1586); R_i anchored to measured "
          "relay RTTs 70-307ms")
    print("adversary=directory.  A=gated(today)  B1=gated+jitter(naive)  "
          "B2=schedule-driven Poisson(loopix)\n")

    print("=" * 70)
    print("INTEGRATION ID  (BBM 5s vs long-poll ~30s; chance = 0.5)")
    print(f"{'N':>5} | {'A':>6} {'B1':>6} {'B2':>6}")
    print("-" * 70)
    for n in N_SWEEP:
        print(f"{n:>5} | {integration_acc('A', n):>6.3f} "
              f"{integration_acc('B1', n):>6.3f} {integration_acc('B2', n):>6.3f}")
    print("  A & B1: cadence still recovered (acc~1)  ->  naive jitter does NOT "
          "hide integration")
    print("  B2: acc ~ chance  ->  uniform Poisson rate hides it")

    print("\n" + "=" * 70)
    print("ROLE AUC (sender vs receiver)   [chance = 0.5]   at N=500, K=20")
    print(f"{'gap(ms)':>7} | {'A':>6} {'B1':>6} {'B2':>6}")
    print("-" * 70)
    for d in DELTA_SWEEP:
        a, _ = role_and_ri("A", d, 500, 20)
        b1, _ = role_and_ri("B1", d, 500, 20)
        b2, _ = role_and_ri("B2", d, 500, 20)
        print(f"{int(d*1000):>7} | {a:>6.3f} {b1:>6.3f} {b2:>6.3f}")
    print("  A: leaks at every realistic gap.  B1: leaks too (accumulates).")
    print("  B2: ~0.5 at ALL gaps -> R_i cancels, role unrecoverable")

    print("\n" + "=" * 70)
    print("ROLE AUC vs accumulation (N requests x K subdirs), gap=100ms")
    print(f"{'N':>5} {'K':>4} | {'A':>6} {'B1':>6} {'B2':>6}")
    print("-" * 70)
    for n in N_SWEEP:
        for k in K_SWEEP:
            a, _ = role_and_ri("A", 0.10, n, k)
            b1, _ = role_and_ri("B1", 0.10, n, k)
            b2, _ = role_and_ri("B2", 0.10, n, k)
            print(f"{n:>5} {k:>4} | {a:>6.3f} {b1:>6.3f} {b2:>6.3f}")
    print("  A: high always.  B1: climbs with N*K (statistical disclosure).")
    print("  B2: stays ~0.5 (no R_i signal to accumulate)")

    print("\n" + "=" * 70)
    print("COVER TRAFFIC -- residual after B2: SESSION-ACTIVITY detection AUC")
    print("(can the directory tell when a real session is active?)  rho = "
          "cover/real rate")
    print(f"{'rho':>5} | " + " ".join(f"{'N='+str(nr):>8}" for nr in (5, 20, 100)))
    print("-" * 70)
    for rho in (0.0, 0.5, 1.0, 2.0, 5.0):
        row = " ".join(f"{cover_activity_auc(rho, nr):>8.3f}" for nr in (5, 20, 100))
        print(f"{rho:>5.1f} | {row}")
    print("  rho=0 (no cover): AUC~1 -> session activity trivially detected")
    print("  rho up: AUC -> 0.5 (activity hidden), BUT long observation (N up)")
    print("  recovers it -> the rate still leaks over time; full hiding needs")
    print("  heavy perpetual cover (impractical, esp. mobile).")


if __name__ == "__main__":
    main()

[DanGould]

@bc1cindy thanks for this push. You're closing a real gap in the model. Based on the legwork here, I do think we want to include timing in the threat model, but I'd flip the sequence by attempting the implementation in payjoin-cli first and then making a PR for BIP 77.

It doesn't hurt to draft the text you'd want to see in BIP 77 (very helpful in fact), perhaps in the a rust-payjoin PR body for the implementation, but I suggest holding off on posting the PR on bitcoin/bips until we've workshopped it to save the BIPs reviewers a few cycles. The last few updates I've initiated there would have saved them some cycles if I had held off and workshopped first.

[bc1cindy]

thanks @DanGould,

it's not only a client change. BIP 77 currently puts the gating on the directory

"GET requests on an empty mailbox should block until a message is posted or a timeout occurs. The timeout should be 30 seconds because that will not exceed the default timeout for most HTTP clients."

while the directory holds the GET, the server owns the cadence, so the client can't move to an independent schedule without the directory also offering a non-blocking / immediate-return GET. So the PR will touch payjoin-mailroom too

plan:

• (1) payjoin non-blocking poll variant
• (2) payjoin-mailroom non-blocking GET
• (3) payjoin-cli Poisson scheduler on the poll loops
• (4) payjoin-ffi to expose it

then, as follow-ups:

• (5) re-clock the POST emission (closes the message-channel residual)
• (6) directory-side mixing delay + constant-padded responses
• (7) self cover traffic for the activity residual

(5)-(7) carry costs beyond the client (latency, a shared-directory change, uniform adoption), so I'll bring designs to discuss

BIP 77 wording drafted alongside.

is this scope ok?

[DanGould]

I think 2-3 effectively demonstrate the concept and could be the minimal path forward. I don't think payjoin defines any blocking/non-blocking poll variant. It only gives network messages, that's up to the HTTP client's interaction with the mailroom. I'm guessing FFI does not need to change

• Cover traffic / "re-clock POST emission" seems like their own further improvements for follow up.
• Do we not already have constant padded responses?

Seems like spec updates can also be workshopped incrementally with the PRs that prove them out

[bc1cindy]

I think 2-3 effectively demonstrate the concept and could be the minimal path forward.

makes sense, payjoin/FFI don't need changes (core just builds/parses, 202 already handled), and padding already exists, so the directory item is just the mixing delay.

updated scope:

• payjoin-mailroom: non-blocking / immediate-return GET
• payjoin-cli: Poisson scheduler on the directory poll loops
• BIP 77 wording drafted

follow-ups:

• re-clock POST emission (closes message-channel residual)
• directory-side mixing delay
• self cover traffic for the activity residual

working on it