Vuvuzela: scalable private messaging resistant to traffic analysis

ABSTRACT

Private messaging over the Internet has proven challenging to implement, because even if message data is encrypted, it is difficult to hide metadata about who is communicating in the face of traffic analysis. Systems that offer strong privacy guarantees, such as Dissent [36], scale to only several thousand clients, because they use techniques with superlinear cost in the number of clients (e.g., each client broadcasts their message to all other clients). On the other hand, scalable systems, such as Tor, do not protect against traffic analysis, making them ineffective in an era of pervasive network monitoring.

Vuvuzela is a new scalable messaging system that offers strong privacy guarantees, hiding both message data and metadata. Vuvuzela is secure against adversaries that observe and tamper with all network traffic, and that control all nodes except for one server. Vuvuzela's key insight is to minimize the number of variables observable by an attacker, and to use differential privacy techniques to add noise to all observable variables in a way that provably hides information about which users are communicating. Vuvuzela has a linear cost in the number of clients, and experiments show that it can achieve a throughput of 68,000 messages per second for 1 million users with a 37-second end-to-end latency on commodity servers.

References

1. A. Back, U. Möller, and A. Stiglic. Traffic analysis attacks and trade-offs in anonymity providing systems. In Proceedings of the Workshop on Information Hiding, pages 245--257, Pittsburgh, PA, Apr. 2001.
2. M. Backes, A. Kate, P. Manoharan, S. Meiser, and E. Mohammadi. AnoA: A framework for analyzing anonymous communication protocols. In Proceedings of the 26th IEEE Computer Security Foundations Symposium, pages 163--178, New Orleans, LA, June 2013.
3. R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, Oct. 2013.
4. O. Berthold and H. Langos. Dummy traffic against long term intersection attacks. In Proceedings of the Workshop on Privacy Enhancing Technologies, pages 110--128, Dresden, Germany, Mar. 2003.
5. R. Bhaskar, A. Bhowmick, V. Goyal, S. Laxman, and A. Thakurta. Noiseless database privacy. In Proceedings of the 17th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pages 215--232, Seoul, South Korea, Dec. 2011.
6. N. Borisov, I. Goldberg, and E. Brewer. Off-the-record communication, or, why not to use PGP. In Proceedings of the 2004 Workshop on Privacy in the Electronic Society, Washington, DC, Oct. 2004.
7. R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. Journal of Cryptology, 20(3):265--294, July 2007.
8. D. Chaum. The dining cryptographers problem: unconditional sender and recipient untraceability. Journal of Cryptology, 1 (1):65--75, 1988.
9. D. L. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2), Feb. 1981.
10. B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Journal of the ACM, 45(6):965--981, Nov. 1998.
11. I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In Proceedings of the Workshop on Design Issues in Anonymity and Unobservability, pages 46--66, Berkeley, CA, July 2000.
12. H. Corrigan-Gibbs, D. Boneh, and D. Mazières. Riposte: An anonymous messaging system handling millions of users. In Proceedings of the 36th IEEE Symposium on Security and Privacy, San Jose, CA, May 2015.
13. G. Danezis. Statistical disclosure attacks: Traffic confirmation in open environments. In Proceedings of the 18th International Conference on Information Security, pages 421--426, Athens, Greece, May 2003.
14. G. Danezis. Measuring anonymity: a few thoughts and a differentially private bound. In Proceedings of the DIMACS Workshop on Measuring Anonymity, May 2013.
15. G. Danezis, R. Dingledine, and N. Mathewson. Mixminion: Design of a type III anonymous remailer protocol. In Proceedings of the 24th IEEE Symposium on Security and Privacy, pages 2--15, Oakland, CA, May 2003.
16. R. Dingledine, N. Mathewson, and P. Syverson. Tor: The second-generation onion router. In Proceedings of the 13th Usenix Security Symposium, pages 303--320, San Diego, CA, Aug. 2004.
17. C. Dwork. Differential privacy: a survey of results. In Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, Xi'an, China, Apr. 2008.
18. C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211--407, 2014.
19. D. Fitzgerald. Bulk bandwidth prices get steadier after long swoon. Wall Street Journal, Sept. 2014. http://www.wsj.com/articles/bulk-bandwidth-prices-get-steadier-after-long-plunge-1411602100.
20. M. J. Freedman and R. Morris. Tarzan: A peer-to-peer anonymizing network layer. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS), pages 193--206, Washington, DC, Nov. 2002.
21. S. Goel, M. Robson, M. Polte, and E. G. Sirer. Herbivore: A scalable and efficient protocol for anonymous communication. Technical Report 2003-1890, Cornell University, Computing and Information Science, Ithaca, NY, 2003.
22. I. Goldberg and The OTR Development Team. Off-the-record messaging, 2015. https://otr.cypherpunks.ca/.
23. M. Hayden. The price of privacy: Re-evaluating the NSA. Johns Hopkins Foreign Affairs Symposium, Apr. 2014. https://www.youtube.com/watch?v=kV2HDM86XgI&t=17m50s.
24. D. Kesdogan, J. Egner, and R. Büschkes. Stop-and-go-MIXes providing probabilistic anonymity in an open system. In Proceedings of the Workshop on Information Hiding, pages 83--98, Portland, OR, Apr. 1998.
25. A. Langley. Pond, 2015. https://pond.imperialviolet.org/.
26. N. Mathewson and R. Dingledine. Practical traffic analysis: Extending and resisting statistical disclosure. In Proceedings of the Privacy Enhancing Technologies Workshop, pages 17--34, May 2004.
27. I. Mironov, O. Pandey, O. Reingold, and S. Vadhan. Computational differential privacy. In Proceedings of the 29th Annual International Cryptology Conference (CRYPTO), pages 126--142, Santa Barbara, CA, Aug. 2009.
28. S. J. Murdoch and G. Danezis. Low-cost traffic analysis of Tor. In Proceedings of the 26th IEEE Symposium on Security and Privacy, pages 183--195, Oakland, CA, May 2005.
29. Open Whisper Systems. Open Whisper Systems partners with WhatsApp to provide end-to-end encryption, Nov. 2014. https://whispersystems.org/blog/whatsapp/.
30. Open Whisper Systems. TextSecure protocol v2, 2015. https://github.com/WhisperSystems/TextSecure/wiki/ProtocolV2.
31. T. Perrin and M. Marlinspike. Axolotl ratchet, 2014. https://github.com/trevp/axolotl/wiki.
32. M. K. Reiter and A. D. Rubin. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security, 1(1):66--92, Nov. 1998.
33. A. Rusbridger. The Snowden leaks and the public. The New York Review of Books, Nov. 2013.
34. L. Sassaman, B. Cohen, and N. Mathewson. The Pynchon gate: A secure method of pseudonymous mail retrieval. In Proceedings of the Workshop on Privacy in the Electronic Society, Arlington, VA, Nov. 2005.
35. P. F. Syverson, D. M. Goldschlag, and M. G. Reed. Anonymous connections and onion routing. In Proceedings of the 18th IEEE Symposium on Security and Privacy, pages 44--54, Oakland, CA, May 1997.
36. D. I. Wolinsky, H. Corrigan-Gibbs, B. Ford, and A. Johnson. Dissent in numbers: Making strong anonymity scale. In Proceedings of the 10th Symposium on Operating Systems Design and Implementation (OSDI), Hollywood, CA, Oct. 2012.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Hardware

  • Communication hardware, interfaces and storage

• Networks

  • Network performance evaluation

  • Network services

    • Network monitoring