Stadium: A Distributed Metadata-Private Messaging System

ABSTRACT

Private communication over the Internet remains a challenging problem. Even if messages are encrypted, it is hard to deliver them without revealing metadata about which pairs of users are communicating. Scalable anonymity systems, such as Tor, are susceptible to traffic analysis attacks that leak metadata. In contrast, the largest-scale systems with metadata privacy require passing all messages through a small number of providers, requiring a high operational cost for each provider and limiting their deployability in practice.

This paper presents Stadium, a point-to-point messaging system that provides metadata and data privacy while scaling its work efficiently across hundreds of low-cost providers operated by different organizations. Much like Vuvuzela, the current largest-scale metadata-private system, Stadium achieves its provable guarantees through differential privacy and the addition of noisy cover traffic. The key challenge in Stadium is limiting the information revealed from the many observable traffic links of a highly distributed system, without requiring an overwhelming amount of noise. To solve this challenge, Stadium introduces techniques for distributed noise generation and differentially private routing as well as a verifiable parallel mixnet design where the servers collaboratively check that others follow the protocol. We show that Stadium can scale to support 4x more users than Vuvuzela using servers that cost an order of magnitude less to operate than Vuvuzela nodes.

References

1. Sebastian Angel and Srinath T. V. Setty. 2016. Unobservable Communication over Fully Untrusted Infrastructure. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016. 551--569. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/angel
2. Kevin S. Bauer, Damon McCoy, Dirk Grunwald, Tadayoshi Kohno, and Douglas C. Sicker. 2007. Low-resource routing attacks against Tor. In Proceedings of the 2007 ACM Workshop on Privacy in the Electronic Society, WPES 2007, Alexandria, VA, USA, October 29, 2007. 11--20.
3. Stephanie Bayer and Jens Groth. 2012. Efficient Zero-Knowledge Argument for Correctness of a Shuffle. In EUROCRYPT (Lecture Notes in Computer Science), Vol. 7237. Springer, 263--280.
4. Mihir Bellare and Phillip Rogaway. 1993. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In ACM Conference on Computer and Communications Security, Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby (Eds.). ACM, 62--73. http://dl.acm.org/citation.cfm?id=168588
5. Daniel J. Bernstein. 2006. Curve25519: New Diffie-Hellman Speed Records. Springer Berlin Heidelberg, Berlin, Heidelberg, 207--228.
6. Nikita Borisov. 2005. An Analysis of Parallel Mixing with Attacker-Controlled Inputs. In Privacy Enhancing Technologies (Lecture Notes in Computer Science), George Danezis and David M. Martin Jr (Eds.), Vol. 3856. Springer, 12--25.
7. Xiang Cai, Xin Cheng Zhang, Brijesh Joshi, and Rob Johnson. 2012. Touching from a distance: website fingerprinting attacks and defenses. In the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16-18, 2012. 605--616.
8. David Chaum. 1981. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. Commun. ACM 24, 2 (1981), 84--88.
9. David Chaum. 1988. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability. J. Cryptology 1, 1 (1988), 65--75.
10. David Chaum, Farid Javani, Aniket Kate, Anna Krasnova, Joeri de Ruiter, and Alan T. Sherman. 2016. cMix: Anonymization by High-Performance Scalable Mixing. IACR Cryptology ePrint Archive 2016 (2016), 8. http://eprint.iacr.org/2016/008
11. David Chaum and Torben Pryds Pedersen. 1992. Wallet Databases with Observers (Extended Abstract). In Advances in Cryptology---CRYPTO '92 (Lecture Notes in Computer Science), Ernest F. Brickell (Ed.), Vol. 740. Springer-Verlag, 1993, 89--105.
12. Raymond Cheng, William Scott, Bryan Parno, Arvind Krishnamurthy, and Thomas Anderson. 2016. Talek: a Private Publish-Subscribe Protocol. Technical Report. University of Washington.
13. Michael E. Clarkson, Stephen Chong, and Andrew C. Myers. 2007. Civitas: A Secure Remote Voting System. In Frontiers of Electronic Voting, 29.07.-03.08.2007. http://drops.dagstuhl.de/opus/volltexte/2008/1296
14. Henry Corrigan-Gibbs, Dan Boneh, and David Mazières. 2015. Riposte: An Anonymous Messaging System Handling Millions of Users. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015. 321--338.
15. Henry Corrigan-Gibbs and Bryan Ford. 2010. Dissent: accountable anonymous group messaging. In Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, October 4-8, 2010. 340--350.
16. Artur Czumaj and Berthold Vöcking. 2014. Thorp Shuffling, Butterflies, and Non-Markovian Couplings. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 344--355.
17. George Danezis, Roger Dingledine, and Nick Mathewson. 2003. Mixminion: Design of a Type III Anonymous Remailer Protocol. In 2003 IEEE Symposium on Security and Privacy (S&P 2003), 11-14 May 2003, Berkeley, CA, USA. 2--15.
18. Roger Dingledine, Nick Mathewson, and Paul F. Syverson. 2004. Tor: The Second-Generation Onion Router. In Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA. 303--320. http//:www.usenix.org/publications/library/proceedings/sec04/tech/dingledine.html
19. Roger Dingledine, Vitaly Shmatikov, and Paul F. Syverson. 2004. Synchronous Batching: From Cascades to Free Routes. In Privacy Enhancing Technologies, 4th International Workshop, PET 2004, Toronto, Canada, May 26-28, 2004, Revised Selected Papers. 186--206.
20. Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science 9, 3-4 (2014), 211--407.
21. Kevin P. Dyer, Scott E. Coull, Thomas Ristenpart, and Thomas Shrimp-ton. 2012. Peek-a-Boo, I Still See You: Why Efficient Traffic Analysis Countermeasures Fail. In IEEE Symposium on Security and Privacy, SP 2012, 21-23 May 2012, San Francisco, California, USA. 332--346.
22. Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO (Lecture Notes in Computer Science), Andrew M. Odlyzko (Ed.), Vol. 263. Springer, 186--194.
23. Jun Furukawa and Kazue Sako. 2001. An Efficient Scheme for Proving a Shuffle. In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings. 368--387.
24. Nethanel Gelernter, Amir Herzberg, and Hemi Leibowitz. 2016. Two Cents for Strong Anonymity: The Anonymous Post-office Protocol. IACR Cryptology ePrint Archive 2016 (2016), 489. http://eprint.iacr.org/2016/489
25. Sharad Goel, Mark Robson, Milo Polte, and Emin Sirer. 2003. Herbivore: A Scalable and Efficient Protocol for Anonymous Communication. Technical Report. Cornell University.
26. Philippe Golle and Ari Juels. 2004. Parallel mixing. In Proceedings of the 11th ACM Conference on Computer and Communications Security, CCS 2004, Washington, DC, USA, October 25-29, 2004. 220--226.
27. Ceki Gülcü and Gene Tsudik. 1996. Mixing Email with Babel. In 1996 Symposium on Network and Distributed System Security, (S)NDSS '96, San Diego, CA, February 22-23, 1996. 2--16.
28. Johan Håstad. 2006. The square lattice shuffle. Random Struct. Algorithms 29, 4 (2006), 466--474.
29. Markus Jakobsson, Ari Juels, and Ronald L. Rivest. 2002. Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking. In Proceedings of the 11th USENIX Security Symposium, San Francisco, CA, USA, August 5-9, 2002. 339--353. http//:www.usenix.org/publications/library/proceedings/sec02/jakobsson.html
30. Aaron Johnson, Chris Wacek, Rob Jansen, Micah Sherr, and Paul F. Syverson. 2013. Users get routed: traffic correlation on Tor by realistic adversaries. In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013. 337--348.
31. Dogan Kesdogan, Jan Egner, and Roland Büschkes. 1998. Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System. In Information Hiding, Second International Workshop, Portland, Oregon, USA, April 14-17, 1998, Proceedings. 83--98.
32. Albert Kwon, Henry Corrigan-Gibbs, Srinivas Devadas, and Bryan Ford. 2017. Atom: Horizontally scaling strong anonymity. In Symposium on Operating Systems Principles.
33. Albert Kwon, David Lazar, Srinivas Devadas, and Bryan Ford. 2016. Riffle: An Efficient Communication System With Strong Anonymity. PoPETs 2016, 2 (2016), 115--134. http//:www.degruyter.com/view/j/popets.2015.2016.issue-2/popets-2016-0008/popets-2016-0008.xml
34. David Lazar and Nickolai Zeldovich. 2016. Alpenhorn: Bootstrapping Secure Communication without Leaking Metadata. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016. 571--586. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/lazar
35. C. Andrew Neff. 2001. A verifiable secret shuffle and its application to e-voting. In CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6-8, 2001. 116--125.
36. W. Norton. 2010. Internet Transit Prices - Historical and Projected. Technical Report. http://drpeering.net/white-papers/Internet-Transit-Pricing-Historical-And-Projected.php
37. Ania M. Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser, and George Danezis. 2017. The Loopix Anonymity System. In 26th USENIX Security Symposium, USENIX Security 2017, Vancouver, BC, Canada, August 16-18, 2017. 1199--1216. https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/piotrowska
38. Charles Rackoff and Daniel R. Simon. 1993. Cryptographic Defense Against Traffic Analysis. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing (STOC '93). ACM, New York, NY, USA, 672--681.
39. Alan Rusbridger. 2013. The Snowden Leaks and the Public. The New-York Review of Book. (Nov. 2013).
40. Claus-Peter Schnorr. 1989. Efficient Identification and Signatures for Smart Cards. In Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. 239--252.
41. Victor Shoup. 2016. NTL: A Library for doing Number Theory. http//:www.shoup.net/ntl/. (2016).
42. Paul F. Syverson, David M. Goldschlag, and Michael G. Reed. 1997. Anonymous Connections and Onion Routing. In 1997 IEEE Symposium on Security and Privacy, May 4-7, 1997, Oakland, CA, USA. 44--54.
43. The Tor Project. 2016. Tor Metrics: Advertised Relay Bandwidth. https://metrics.torproject.org/advbwdist-perc.html?start=2016-03-15&end=2016-09-15&p=97. (May 2016).
44. Nirvan Tyagi, Yossi Gilad, Matei Zaharia, and Nickolai Zeldovich. 2016. Stadium: A Distributed Metadata-Private Messaging System. IACR Cryptology ePrint Archive 2016 (2016), 943. http://eprint.iacr.org/2016/943
45. Jelle van denHooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. 2015. Vuvuzela: scalable private messaging resistant to traffic analysis. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP 2015, Monterey, CA, USA, October 4-7, 2015. 137--152.
46. Tao Wang and Ian Goldberg. 2013. Improved website fingerprinting on Tor. In Proceedings of the 12th annual ACM Workshop on Privacy in the Electronic Society, WPES 2013, Berlin, Germany, November 4, 2013. 201--212.
47. David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, and Aaron Johnson. 2012. Dissent in Numbers: Making Strong Anonymity Scale. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012. 179--182. https://www.usenix.org/conference/osdi12/technical-sessions/presentation/wolinsky

Index Terms

• Security and privacy

  • Security services

    • Privacy-preserving protocols

    • Pseudonymity, anonymity and untraceability

  • Systems security

    • Distributed systems security