Minx: a simple and efficient anonymous packet format

ABSTRACT

<i>Minx</i> is a cryptographic message format for encoding anonymous messages, relayed through a network of Chaumian mixes. It provides security against a passive adversary by completely hiding correspondences between input and output messages. Possibly corrupt mixes on the message path gain no information about the route length or the position of the mix on the route. Most importantly Minx resists active attackers that are prepared to modify messages in order to embed tags which they will try to detect elsewhere in the network. The proposed scheme imposes a low communication and computational overhead, and only combines well understood cryptographic primitives.

REFERENCES

• 1: Advanced Encryption Standard, FIPS-197. National Institute of Standards and Technology, November 2001.
• 2: Ross J. Anderson , Eli Biham, Two Practical and Provably Secure Block Ciphers: BEARS and LION, Proceedings of the Third International Workshop on Fast Software Encryption, p.113-120, February 21-23, 1996
• 3: Mihir Bellare , Alexandra Boldyreva , Anand Desai , David Pointcheval, Key-Privacy in Public-Key Encryption, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.566-582, December 09-13, 2001
• 4: M. Bellare, R. Canetti, and H. Krawczyk. Message authentication using hash functions: The HMAC construction. RSA Laboratories' CryptoBytes, 2(1), Spring 1996.
• 5: O. Berthold and H. Langos. Dummy traffic against long term intersection attacks. In R. Dingledine and P. Syverson, editors, Proceedings of Privacy Enhancing Technologies workshop (PET 2002). Springer-Verlag, LNCS 2482, April 2002.
• 6: Oliver Berthold , Andreas Pfitzmann , Ronny Standtke, The disadvantages of free MIX routes and how to overcome them, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.30-45, January 2001, Berkeley, California, United States
• 7: 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]
• 8: G. Danezis. Mix-networks with restricted routes. In R. Dingledine, editor, Privacy Enhancing Technologies workshop (PET 2003), volume 2760 of LNCS, pages 1--17, Dresden, Germany, March 2003. Springer-Verlag.
• 9: G. Danezis. Better Anonymous Communications. PhD thesis, University of Cambridge, Computer Laboratory, 2004.
• 10: 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
• 11: R. Dingledine, V. Shmatikov, and P. Syverson. Synchronous batching: From cascades to free routes. PET 2004, 2004.
• 12: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 13: David M. Goldschlag , Michael G. Reed , Paul F. Syverson, Hiding Routing Information, Proceedings of the First International Workshop on Information Hiding, p.137-150, May 30-June 01, 1996
• 14: Ceki Gulcu , Gene Tsudik, Mixing Email with Babel, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.2, February 22-23, 1996
• 15: N. Mathewson, R. Dingledine, and G. Danezis. Type iii (mixminion) mix directory specification. Technical report, The Mixminion Project, 2004.
• 16: B. Möller. Provably secure public-key encryption for length-preserving chaumian mixes. In M. Joye, editor, Topics in Cryptology CT-RSA 2003, volume 2612 of LNCS, pages 244--262, San Francisco, CA, USA, 13--17 April 2003. Springer-Verlag.
• 17: U. Möller, L. Cottrell, P. Palfrader, and L. Sassaman. Mixmaster Protocol --- Version 2. Draft, July 2003.
• 18: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 19: Choonsik Park , Kazutomo Itoh , Kaoru Kurosawa, Efficient anonymous channel and all/nothing election scheme, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.248-259, January 1994, Lofthus, Norway
• 20: Andreas Pfitzmann , Birgit Pfitzmann , Michael Waidner, ISDN-MIXes: Untraceable Communication with Small Bandwidth Overhead, Kommunikation in Verteilten Systemen, Grundlagen, Anwendungen, Betrieb, GI/ITG-Fachtagung, p.451-463, February 20-22, 1991
• 21: B. Pfitzmann. Breaking efficient anonymous channel. In A. D. Santis, editor, Advances in Cryptology (Eurocrypt '94), volume 950 of LNCS, pages 332--340, Perugia, Italy, 9-12 May 1994. Springer-Verlag.
• 22: Birgit Pfitzmann , Andreas Pfizmann, How to break the direct RSA-implementation of mixes, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.373-381, November 1990, Houthalen, Belgium
• 23: J. B. Postel. Simple mail transfer protocol. Technical report, Request for comments number 821, August 1982.
• 24: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 25: Andrei Serjantov , Roger Dingledine , Paul F. Syverson, From a Trickle to a Flood: Active Attacks on Several Mix Types, Revised Papers from the 5th International Workshop on Information Hiding, p.36-52, October 07-09, 2002
• 26: P. D. V. Gligor. Infinite garble extension. Technical report, NIST, 10 November 2000.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Security

Keywords:
anonymity, mix networks, tagging attacks