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

@nothingmuch

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

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

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.

@Mshehu5

@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)

@nothingmuch

@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

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()

@bc1cindy

@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.

@DanGould

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?

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

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

@DanGould

Based on the importance of trying to reduce fingerprints across clients we did end up with a PollSchedule in 44e9bca. @DanGould I know this a bit at odds with #440 (comment) but given the nature of this mechanism we really have 2 options again like all fingerprints, completely uniform or completely random. I felt leaving this timing up to implementers would likely result in some but not all wallets modifying this schedule to better fit their time preference and creating fingerprints.

@nothingmuch

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

I tend to agree with this, though I am not sure where @nothingmuch stands on whether/how much further mitigation is required.

For me it seems a bit futile to worry about timing attacks from the directory since the directory can already see whether the request is a POST or GET request and just that alone should easily allow identification of the receiver vs sender. I do think timing attacks make sense to worry about from the relay, though whether I feel strongly enough about it to say it should "included in our threat model" is hard to say. I do strongly feel that payjoin should include infrastructure that supports responsible usage of relays (like #1696).

Overall, my position is:

we should eliminate the 30s blocking for GET requests as suggested, to make GET and POST requests have similar timing from relay perspective
would probably be good to mention timing attacks from relay perspective in BIP 77, so that implementers are aware they should rotate relays for each request and also not poll too often (but I'm not convinced it matters from directory perspective)
I don't think we need to support mitigation of directory timing attacks in the payjoin crate

That said, my position rests entirely on the premise that the directory can already see the order in which GET and POST requests come in for each mailbox which will already identify the sender vs receiver, and that adjusting timing of requests cannot mitigate this heuristic. Let me know if my premise is flawed in some way.

@xstoicunicornx

@xstoicunicornx premise doesn't hold, because both parties GET and POST, so method alone doesn't split roles. the real distinguisher is R_i cadence, which #1658 removes, and per #919 even that collapses to one indistinguishable GET once the mailbox has contents. mailroom-nonblocking + cli-Poisson is the minimal path (the 30s-blocking removal you want is in #1658)

But order matters.

Sender always POSTs first (and receiver always GETs first)
Receiver always POSTs second (and sender always GETs second)

This seems easily identifiable to me?

agreed, the polling-phase ordering identifies role structurally, and this work doesn't touch it. where the poll-schedule earns its place is a different directory-observable axis: client-cadence uniformity, today the directory separates BBM's 5s from the ~30s long-poll group, and one shared Poisson rate drops that. the ordering leak is separate and worth its own issue.

today the directory separates BBM's 5s from the ~30s long-poll group, and one shared Poisson rate drops that

Wouldn't changing the 30s long poll to a regular GET request (with the recommendation of only polling every 5s) also mitigate this?

the ordering leak is separate and worth its own issue

I don't actually see it as an issue, just an inherent limitation of this protocol. Though I'm not super familiar with OHTTP so maybe there is a better way for us to be using it?

Overall, I guess I am not against adding the minimal scheduler in #1658. However, I do worry that it just turns into another fingerprint since we have no real way to enforce its usage. Today we already explicitly define the behavior all clients should exhibit, which is supported by the mailroom, and yet we still have variance. It is not clear to me that making request timing more complicated will clearly reduce variance between implementations.

Also, if the heuristic we are trying to mitigate is wallet detection (and not sender vs receiver detection as was initially stated) then I actually would probably change my mind about eliminating the 30s blocking GET, as the current spec is the most we will ever be able to enforce consistency in timing between wallets.

Wouldn't changing the 30s long poll to a regular GET request (with the recommendation of only polling every 5s) also mitigate this?

no, that's regime A/B1 of the #440 (comment): response-gated, interval = 5s + R_i, role AUC 0.92–1.00 at ≥100ms gaps (0.62 even at 20ms), and jitter doesn't fix it. a fixed independent timer cancels R_i but leaks phase and clock skew; poisson leaks only the rate. and a recommendation has the same enforcement problem you raise against the scheduler.

I don't actually see it as an issue, just an inherent limitation

its levers (re-clock POST, mixing delay) are already follow-ups in the agreed scope. #440 (comment)

we already explicitly define the behavior all clients should exhibit... and yet we still have variance

that variance happened under the most enforceable spec we've had, the server-held 30s GET: bbm ran its own 5s timer, cake added a 2s sleep (#1586). server blocking doesn't enforce client loops, a shared lib default does.

if the heuristic we are trying to mitigate is wallet detection (and not sender vs receiver detection as was initially stated)

it's both, and the sim measures both: "BBM vs long-poll" is the wallet heuristic (1.00 under A/B1, 0.49 under B2); the role rows are the R_i heuristic #440 opened on. long-poll fails both axes, and non-blocking GET is your own earlier point (GET ≈ POST from the relay), plus the minimal path agreed above, which #1658 implements.

@bc1cindy

I realize that work has already begun to address timing fingerprints, however I am not sure the first two items on this issue have been adequately addressed:

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

Calculating the traffic conditions under which timing analysis exposes an attack is a tricky problem, and capturing accurate metrics is essential to appropriately evaluate and address the fingerprinting attack vector.

I also think the rollout needs to be carefully considered, as well as implementation realities. Just because there is a shared lib that exists does not guarantee that it will be used by an implementer, nor does it guarantee that it will be used correctly. Additionally, with added complexity in the spec those using independent libraries outside PDK will have more opportunity to create fingerprints that don't perfectly align in behavior.

From what I have gathered there are two types of fingerprinting that are being reviewed here.

1. Wallet fingerprinting

This was the data given for evidence of being able to fingerprint a wallet:

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

I have a number of issues with this calculation.

Conceptual Issue

When determining whether a wallet can be fingerprinted, it seems fairly straightforward that a wallet that doesn't match the specified poll cadence is easily fingerprint-able. However, wallets that do not follow the specification is not something that is under our control and it will always be fingerprint-able. The B2 fix scenario assumes an environment in which all wallets are appropriately complying with the specification measured against an environment in which there is a wallet not complying with the specification. This is a huge discrepancy. When considering whether or not the specification needs to be updated we should only evaluate fingerprinting for wallets who are conforming to the spec.

Technical Issue

The identification chance for the B2 fix is stated at 0.49, which is what you ideally want. However, what this number is actually measuring is when creating a distribution of poll intervals with either a mean of 5s (BBM's cadence) or 30s (the standard cadence), how often does the average of those intervals match 5s vs 30s. It makes sense that A and B1 all have identification of 100%. However, what does not make sense is to compare this to B2 which is only constructed with a 5s mean interval time in all simulated polling sessions. The B2 fix is close to 0.5 chance simply because the there is a 0.5 chance of the scenario randomly selecting 30s intervals (and since B2 mean interval time is always 5s it will only match against 5s interval cases), not because B2 actually obfuscated the polling average cadence.

General

This calculation should be trying to understand for a specific specification how much timing data is leaked when using the different scenarios. If you want to simulate in this in an ideal scenario where all wallets conform to spec, like for B2 scenario, then that should be the same environment that A and B1 are also evaluated in.

To be clear, I am not stating that B2 fix doesn't help wallet fingerprinting, I am just stating that the evidence we have thus far isn't appropriate for evaluating how effective the B2 fix is at obfuscating fingerprinting.

2. Sender vs Receiver fingerprinting

As I have state previously, I don't find obfuscating this type of fingerprinting worthwhile simply because the directory will already easily be able to determine who is sender vs receiver. @bc1cindy you mentioned "re-clock POST, mixing delay" as potential ways to obfuscate this. Can you expand on what these are?

In regards to the way this fingerprinting was calculated there were a couple things that seemed off. First is using K = 20 makes the assumption that the attacker already knows the exact 20 subdirectories being used by each individual party, rather than having to discern for themselves which 20 subdirectories (out of the all the subdirectories it has) should be sampled together to strengthen the signal. Second is that an artificial tunable gap is being added to the receiver round trip times to differentiate it from the sender. While this does accomplish the goal of modeling how much each gap value changes the ability to identify sender vs receiver, it doesn't really model what that gap will realistically be on average.

I attempted to address these couple things myself by adding some modifications to @bc1cindy 's simulation above:

introducing rtt variance that reflects using a discrete relay set (rather than having it be a static value, effectively representing a single relay being, for all polls within a polling set)
setting K = 1
removed the tunable gap and instead allowed a natural gap to emerge from the randomly constructed set of relay rtts
replaced the tunable gap with a tunable relay set count

Here are the results I got:

======================================================================
DISTINGUISH THE TWO ENDS (emergent gap)  [chance = 0.5]   at N=500, K=1
gap is emergent: 2 draws from one population, lower mean = sender
relays |      A     B1     B2     B3
----------------------------------------------------------------------
     1 |  0.824  0.647  0.490  0.518
     2 |  0.842  0.614  0.503  0.516
     6 |  0.832  0.566  0.493  0.511
    20 |  0.824  0.541  0.503  0.502
   100 |  0.793  0.525  0.496  0.505
  fewer relays -> bigger emergent gap -> the two ends split more easily.
  A/B1/B3: separable whenever the emergent gap beats estimator noise;
  the signal fades as relays grow and the two set means converge.
  B2: ~0.5 at EVERY relay count -> R_i cancels, the ends stay unlinkable.

(The B3 scenario is B2 but without an independent scheduler, ie requests are still gated by previous response and R_i is included in round trip time)

Wrapping up

Introducing complexity to the specification should be backed by data. In this instance I am not convinced that the data shows that the added complexity is worth it. When requiring something like a scheduler you are either asking the implementer to roll one from scratch without mistakes or add one as a dependency. This is burden that should be considered carefully.

Additionally, there are other mitigation strategies that are less complex and have not yet been discussed. For example double nested OHTTP requests would help with obfuscating round trip time as well. And a variant of B2 fix, which I have dubbed B3, which keeps the poisson distribution for poll intervals but doesn't so far as to require a scheduler to obfuscate R_i.

At this point I am not even sure I agree with my previous position here #440 (comment), as it seems like the less poll requests that are made the less accurately an attacker can discern fingerprints (30s poll time requires less requests than 5s poll time).

You can find my modified version of @bc1cindy 's simulation work (#440 (comment)) at https://github.com/xstoicunicornx/pj-directory-timing-analysis/tree/relay-var.

For the sake of simplicity we should probably go with a simple jitter addition, option B1, as this is the least complex with demonstrated results on even a single relay.

To keep this out of implementer's hands I do think that this should still go in the payjoin crate as it is unreasonable to put a relatively important privacy preserving code in something as innocuous as a random sleep. It just seems like a prime area for implementers to get it wrong or ommit it.

since rn i have a different focus, feel free to continue with this work

thank you

The question I wanted to really have discussion around first is - what do we gain but trying to obfuscate request round trip times?

This simulation has demonstrated that it is relatively easy to differentiate between 2 parties based on their poll round trip time. However, it seems to me that the larger factor that will differentiate between 2 parties using a single mailbox will be the fact that only party polls GET requests on schedule and the other party makes a one-off POST request. Is this a valid heuristic? If so, it doesn't seem like we gain much by trying to obfuscating the poll round trip timing without obfuscating the pattern of GET vs POST requests.

Navigation Menu

Repository navigation

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

1. Wallet fingerprinting

Conceptual Issue

Technical Issue

General

2. Sender vs Receiver fingerprinting

Wrapping up

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

benalleng commented on Jun 11, 2026

nothingmuch commented on Jun 11, 2026

nothingmuch commented on Jun 11, 2026

bc1cindy commented on Jun 11, 2026

bc1cindy commented on Jun 15, 2026

DanGould commented on Jun 16, 2026

bc1cindy commented on Jun 16, 2026

DanGould commented on Jun 17, 2026

bc1cindy commented on Jun 17, 2026

benalleng commented on Jun 22, 2026

xstoicunicornx commented on Jul 21, 2026

bc1cindy commented on Jul 21, 2026

xstoicunicornx commented on Jul 21, 2026

bc1cindy commented on Jul 21, 2026

xstoicunicornx commented on Jul 21, 2026

bc1cindy commented on Jul 21, 2026

xstoicunicornx commented on Jul 23, 2026

1. Wallet fingerprinting

Conceptual Issue

Technical Issue

General

2. Sender vs Receiver fingerprinting

Wrapping up

benalleng commented on Aug 25, 2026

bc1cindy commented on Aug 25, 2026

xstoicunicornx commented on Aug 29, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions