2008-sovran-pass
findings extracted from this paper
-
Centralized proxy-discovery services are reliably disabled by censors: both Anonymizer and SafeWeb were blocked in China by targeting their central discovery sites, and Wikipedia identified and blocked all 700+ Tor anonymizing relay servers to prevent anonymous edits. Any single publicly-known host that handles proxy distribution becomes the censor's primary and sufficient target.
-
Kaleidoscope uses at most one intermediate relay hop so proxies can serve users beyond their immediate trust neighborhood without directly learning user addresses. If a system allowed each proxy to directly advertise to N users, a censor posing as a proxy would learn N user identities; the one-hop relay design caps per-proxy exposure to r=5 relay addresses and keeps end-user identities hidden from proxies.
-
On a crawled Orkut subgraph of 42,474 users (≈90% Brazilian nodes treated as the censored domain, 15% of external nodes as proxies = 1.5% overall), the median node reaches 7 proxies — higher than the synthetic graph due to greater average degree (5.59 vs. 4.65) and lower clustering. Even when subverted trust links reach half the total proxy count, more than 94% of users can still access at least one proxy unknown to the censor.
-
Kaleidoscope bounds censor knowledge by routing proxy advertisements over symmetric random routes of length r=5 on a social trust graph: if the censor controls f subverted trust links, they can learn of at most r×f = 5f users or proxies regardless of how many Sybil identities they generate. Symmetric routing ensures the set a node learns of and the set that learns of a node are identical, closing the asymmetric information-leakage channel.
-
Simulation on a synthetic social graph of one million nodes (average degree 4.65, maximum 13) shows that when 1.5% of nodes act as proxies and random routes of length r=5 are used, the median node can reach 3 proxies and more than 90% of nodes can access at least one proxy.