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.

Solutions

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

PriFi

• 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

DC-Nets

• 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

PriFi

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

Conclusions

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