Tracking Resistance in PriFi

David Wolinsky, Bryan Ford, Daniel Jackowitz, and Ewa Syta

Yale University

Tracking Is Pervasive

  • Facebook / Google / Advertisers follow you
  • Governments monitor flow across the Internet
  • Verizon -- Universal Identifier Header (UIDH)
  • Turn uses UIDH to make cookies

Is Encryption Enough?

Google's Eric Schmidt recently stated, "We can end government censorship in a decade. The solution to government surveillance is to encrypt everything."

Encryption doesn't protect "metadata:" who you are and who you are talking with. That requires anonymity.


  • VPNs / Single-hop proxies: TorGuard, IPVanish, Cloak
  • Anonymizing networks: Tor / I2P


  • Very fast
  • Delegating responsibility of Web traffic to VPN
  • VPN must be trusted
  • Vulnerable to ISP level adversary


  • Very fast
  • Delegating responsibility of Web traffic to VPN
  • VPN must be trusted
  • Vulnerable to ISP level adversary


  • Performance improving every day
  • Offers more security than VPNs
  • Still vulnerable


  • Performance improving every day
  • Offers more security than VPNs
  • Still vulnerable


  • Organization/metro network
  • Users transmit equal length streams synchronously producing untraceable anonymized traffic
  • External adversaries learn only output
  • Internal adversaries know online client set
  • Builds on Dissent and hence DC-nets to offer strong anonymity


  • Each pair have a shared secret (random bit)
  • Xor shared secrets and optional cleartext, publish
  • Xor published content, reveal anonymous cleartext

Practical Challenges

  • Scheduling -- cannot trivial handle simultaneous cleartext
  • Churn -- must restart transmission upon any disconnection
  • Integrity -- consensus on output
  • Disruption -- malicious participant can anonymously jam channel

Dissent (OSDI'12)

  • Delegate workload to highly-reliable servers
  • Clients online status not critical for protocol completion
  • Trust that at least one server is honest without knowing which
  • Every exchange requires 4 server-to-server exchanges

Dissent Overheads

  • Clients have 50 ms delay / 100 Mbps shared uplink to servers
  • Servers 10 ms LAN w/ 100 Mbps links
  • Want servers distributed, more server overhead, but harder for attackers to compromise servers
  • Want clients close together, less client costs, harder to distinguish unique individuals
  • Must remove servers from critical path


  • Removes trust from critical performance loop
  • Clients and trustees perform DC-nets with untrusted middleman handling ciphertext aggregation and Internet routing
  • Retains Dissents features without per-exchange communication between trustees and clients

Moments of Stability

  • Server's exchange client set to determine what to generate
  • Insight -- Keep static client set for a period of time -- interval
  • Result -- Trustees can produce ciphertext independent of clients
  • New clients must wait until next interval
  • Departing clients pause exchanges until following interval

Client Enforced Integrity

  • Must ensure all clients obtain same output
  • Clients can perform internal integrity check
    • Receive exchange output, sign it, transmit to relay
    • Relay receives signatures and broadcasts
    • Clients verify, process output
  • Optimization 1: Composite signatures
  • Optimization 2: Use previous exchanges output to encrypt next exchanges ciphertext

Resistance to Disruption

Resistance to Disruption

  • Introduce random trap bits
  • Anonymous sender never touches trap bits
  • Trap bits -- shared secrets between sender and trustees
  • Sender can embed message around trap bits
  • Trustees learn trap bits at end of interval and verify output
  • If a trap bit is flipped, perform Dissent accountability

Assigning Windows

  • Assign windows and trap bits
  • Runs outside of critical loop
  • Clients need not participate -- Shared secret can be produced via trustees

Preliminary Results

  • 3 Trustees, 32 client machines
  • Measured delay for performing 128KB HTTP GET
  • Take-away: Trustee delay irrelevant
  • Written in Python, in midst of rewriting in Go

More and More Challenges

  • Scale beyond a single relay?
    • Broadcast trees
  • Support VPN clients (remote parties)?
    • Multiple DC-net channels, different rates
  • Handle intersection attacks?
    • Buddies CCS'12
  • Selecting trustees
    • Trusted providers, e.g., social networks (CryptoBook -- Hotnets '13)
    • Randomly from a clouds of trustee providers (Secure random selection of relay selection in Tor)


Performance gains by using trustees outside the critical performance loop:
  • Trustees produce ciphertext independently and parallely of clients
  • Trustees can create schedules without client interaction
  • Trustees can detect disruption outside of interval
  • Don't be afraid to give the clients some work (integrity)
More information: