Nonesuch: a mix network with sender unobservability

ABSTRACT

Oblivious submission to anonymity systems is a process by which a message may be submitted in such a way that neither the anonymity network nor a global passive adversary may determine that a valid message has been sent. We present Nonesuch: a mix network with steganographic submission and probabilistic identification and attenuation of cover traffic. In our system messages are submitted as stegotext hidden inside Usenet postings. The steganographic extraction mechanism is such that the the vast majority of the Usenet postings which do not contain keyed stegotext will produce meaningless output which serves as cover traffic, thus increasing the anonymity of the real messages. This cover traffic is subject to probabilistic attenuation in which nodes have only a small probability of distinguishing cover messages from "real" messages. This attenuation prevents cover traffic from travelling through the network in an infinite loop, while making it infeasible for an entrance node to distinguish senders.

REFERENCES

• 1: Matthias Bauer, New covert channels in HTTP: adding unwitting Web browsers to anonymity sets, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC [doi>10.1145/1005140.1005152]
• 2: Berman, R., Fiat, A., and Ta-Shma, A. Provable unlinkability against traffic analysis. In Proceedings of Financial Cryptography (FC '04) (February 2004), A. Juels, Ed., Springer-Verlag, LNCS 3110.
• 3: D. Chaum, The dining cryptographers problem: unconditional sender and recipient untraceability, Journal of Cryptology, v.1 n.1, p.65-75, 1988
• 4: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 5: George Danezis , Roger Dingledine , Nick Mathewson, Mixminion: Design of a Type III Anonymous Remailer Protocol, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.2, May 11-14, 2003
• 6: George Danezis , Ben Laurie, Minx: a simple and efficient anonymous packet format, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029198]
• 7: Díaz, C. Anonymity and Privacy in Electronic Services. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium, December 2005.
• 8: Dingledine, R., Mathewson, N., and Syverson, P. Tor: The second-generation onion router. In Proceedings of the 13th USENIX Security Symposium (August 2004).
• 9: Nicholas J. Hopper , John Langford , Luis von Ahn, Provably Secure Steganography, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.77-92, August 18-22, 2002
• 10: M. R. Horton , R. Adams, Standard for interchange of USENET messages, RFC Editor, 1987
• 11: B. Kantor , P. Lapsley, Network News Transfer Protocol, RFC Editor, 1986
• 12: Dogan Kesdogan , Jan Egner , Roland Büschkes, Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System, Proceedings of the Second International Workshop on Information Hiding, p.83-98, April 14-17, 1998
• 13: Levine, B. N., Reiter, M. K., Wang, C., and Wright, M. K. Timing attacks in low-latency mix-based systems. In Proceedings of Financial Cryptography (FC '04) (February 2004), A. Juels, Ed., Springer-Verlag, LNCS 3110.
• 14: Mixminion Stats V1.0. Statistics generated by the remailer grove. WWW, June 2006. http://privacy.outel.org/minion/nlist.html.
• 15: Serjantov, A. On the Anonymity of Anonymity Systems. PhD thesis, University of Cambridge, June 2004.
• 16: Serjantov, A., and Danezis, G. Towards an information theoretic metric for anonymity. In Proceedings of Privacy Enhancing Technologies Workshop (PET 2002) (April 2002), R. Dingledine and P. Syverson, Eds., Springer-Verlag, LNCS 2482.
• 17: Paul Syverson , Gene Tsudik , Michael Reed , Carl Landwehr, Towards an analysis of onion routing security, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.96-114, January 2001, Berkeley, California, United States
• 18: von Ahn, L., and Hopper, N. J. Public-key steganography. In EUROCRYPT (2004), C. Cachin and J. Camenisch, Eds., vol. 3027 of Lecture Notes in Computer Science, Springer, pp. 323--341.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Information hiding

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Security

Keywords:
minx packet format, mix networks, oblivious channels, public key, sender unobservability, steganography