Secure off-the-record messaging

ABSTRACT

At the 2004 Workshop on Privacy in the Electronic Society (WPES), Borisov, Goldberg and Brewer, presented "Off the Record Messaging" (OTR), a protocol designed to add end-to-end security and privacy to Instant Messaging protocols. An open-source implementation of OTR is available and has achieved considerable success.In this paper we present a security analysis of OTR showing that, while the overall concept of the system is valid and attractive, the protocol suffers from security shortcomings due to the use of an insecure key-exchange protocol and other problematic design choices.On the basis of these findings, we propose alternative designs and improvements that strengthen the security of the system and provide the originally intended features of the protocol, including deniability, in a sound and well-defined sense.

REFERENCES

• 1: M. Abadi, Private Authentication, Proc. of the 2002 Workshop on Privacy Enhancing Technologies (PET 2002), Springer-Verlag, pp. 27--40, 2003.
• 2: Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276854]
• 3: Nikita Borisov , Ian Goldberg , Eric Brewer, Off-the-record communication, or, why not to use PGP, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029200]
• 4: J. Callas, L. Donnerhacke, H. Finney and R. Thayer, OpenPGP message format, RFC2440, November 1998.
• 5: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 6: Ran Canetti , Hugo Krawczyk, Security Analysis of IKE's Signature-Based Key-Exchange Protocol, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.143-161, August 18-22, 2002
• 7: W. Diffie and M.E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, vol. 22, n. 6, pp. 644--654, 1976.
• 8: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 9: M. Di Raimondo, R. Gennaro and H. Krawczyk, Deniable authentication and Plaintext Awareness, Manuscript, August 2005.
• 10: Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk and T. Rabin, Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes, Advances in Cryptology -- Proc. of CRYPTO '04, LNCS 3152, Springer-Verlag, pp. 399--424, 2004.
• 11: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.409-418, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276853]
• 12: Christoph G. Günther, An identity-based key-exchange protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.29-37, November 1990, Houthalen, Belgium
• 13: D. Harkins and D. Carrel, ed., The Internet Key Exchange (IKE), RFC 2409, Nov. 1998.
• 14: J. Katz, Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications, Advances in Cryptology -- Proc. of EUROCRYPT '03, LNCS 2656, Springer-Verlag, pp. 211--228, 2003.
• 15: C. Kaufman, ed., Internet Key Exchange (IKEv2) Protocol, draft-ietf-ipsec-ikev2-17.txt, September 2004 (pending RFC).
• 16: H. Krawczyk, M. Bellare and R. Canetti, HMAC: Keyed-hashing for message authentication, RFC2104, February 1997.
• 17: H. Krawczyk, SKEME: a versatile secure key exchange mechanism for Internet, Proceedings of the 1996 Symposium on Network and Distributed System Security (SNDSS '96), p.114, February 22-23, 1996
• 18: H. Krawczyk, SIGMA: The 'SiGn-and-MAc' Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols, Advances in Cryptology -- Proc. of CRYPTO '03, LNCS 2729, Springer-Verlag, pp. 400--425, 2003. Available at http://www.ee.technion.ac.il/hdir hugo/sigma.html
• 19: H. Krawczyk, HMQV: A High-Performance Secure Diffie-Hellman Protocol, Advances in Cryptology -- Proc. of CRYPTO '05, LNCS, Springer-Verlag, 2005. Available at http://eprint.iacr.org/2005/176.
• 20: Laurie Law , Alfred Menezes , Minghua Qu , Jerry Solinas , Scott Vanstone, An Efficient Protocol for Authenticated Key Agreement, Designs, Codes and Cryptography, v.28 n.2, p.119-134, March 2003 [doi>10.1023/A:1022595222606]
• 21: W. Mao and K.G. Paterson, On the plausible deniability feature of Internet protocols, Manuscript.
• 22: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 23: R. Pass, On Deniability in the Common Reference String and Random Oracle Model, Advances in Cryptology -- Proc. of CRYPTO '03, LNCS 2729, Springer-Verlag, pp. 316--337, 2003.
• 24: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 25: Editor B. Ramsdell, S/MIME version 3 message specification, RFC2633, June 1999.
• 26: T. Ylonen, SSH secure login connections over the Internet, 6th USENIX Security Symposium, pp. 37--42, San Jose, CA, July 1996.
• 27: Philip R. Zimmermann, The official PGP user's guide, MIT Press, Cambridge, MA, 1995

INDEX TERMS

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

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

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

General Terms:
Security

Keywords:
authentication, deniability, instant messaging, perfect forward secrecy