Lox: Protecting the Social Graph in Bridge Distribution

Relying on third-party email providers to verify users was demonstrated by Ling et al. to leave Tor's BridgeDB vulnerable to censors capable of creating multiple accounts, enabling bridge enumeration via sock-puppet attacks at scale. Active and passive detection techniques — including traffic flow analysis, DPI, website fingerprinting, and active probing — have been demonstrated in prior work to reveal Tor bridges, making Tor inaccessible for the majority of users in some regions.

§2.2.1 detection active-probingdpitraffic-shapewebsite-fingerprintip-blocking generic

The Lox check-blockage protocol response size and time grow linearly with the number of blocked bridges — 6 kB / 11 ms at 5% blocked, 63 kB / 64 ms at 50%, and 126 kB / 122.5 ms at 100% — creating a bandwidth bottleneck a strategic and patient censor can exploit by triggering mass bridge blockages during a critical event (election, coup) to deny successful blockage migrations at the moment users most need them.

Figure 1, §5.2 detection ip-blockingthrottling generic

In a Rust implementation evaluated over 10,000 runs with 3,600 bridges (1,800 open-entry single-bridge buckets and 600 hot-spare three-bridge buckets), Lox's trust promotion protocol incurs the highest latency at 364.2 ms response time and 378 kB response size due to the encrypted migration hashtable, but this operation occurs only once per user. All other protocols complete in under 16 ms with request sizes under 3.4 kB.

Table 4, §5.2 evaluation generic

Lox's trust level scheme (L=0 through L=4, requiring 30, 14, 28, 56, and 84 days respectively per level before upgrading, per Table 2) with blockage inheritance — invited users inherit their inviter's blockage count d — prevents a censor from resetting their reputation through self-invitation after causing blocking events, while users with d ≥ 4 become ineligible to migrate, capping the damage a persistent infiltrator can do.

§4.2.1, §2.4.2, Table 2 defense ip-blockingactive-probing generic

Lox uses Chase et al.'s keyed-verification algebraic MAC anonymous credentials in a single-issuer/verifier setting with jointly-chosen credential IDs (neither party can unilaterally select them), so a fully compromised Lox Authority cannot link credential showings to specific users or reconstruct the social graph — the LA learns only that a shown credential was authentically issued.

§3.1, §4.2 defense active-probing generic