Deniable authentication and key exchange

ABSTRACT

We extend the definitional work of Dwork,Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE)protocol.SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first "natural" application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security).SIGMA, on the other hand,uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, "partial deniability" property: a party may not be able to deny that it was "alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors.We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

References

1. M. Bellare, R. Canetti and H. Krawczyk. A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols.STOC '98, 419--428, ACM 1998.]]
2. M. Bellare, A. Desai, D. Pointcheval and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. CRYPTO '98, LNCS 1462, 26--45, Springer 1998.]]
3. M. Bellare and A. Palacio. The Knowledge of Exponent Assumptions and 3-Round Zero-Knowledge Protocols. CRYPTO '04, LNCS 3152, 273--289, Springer 2004.]]
4. M. Bellare and A. Palacio. Towards Plaintext-Aware Public-Key Encryption without Random Oracles. ASIACRYPT '04,LNCS 3329,48--62, Springer 2004.]]
5. M. Bellare and P. Rogaway. Entity authentication and key distribution. CRYPTO '93, LNCS 773, 232--249, Springer 1994.]]
6. M.Bellare and P.Rogaway.Optimal Asymmetric Encryption. EUROCRYPT '94,LNCS 950, 92--111,Springer 1994.]]
7. N. Borisov, I. Goldberg and E. Brewer. Off-the-Record Communication, or, Why Not To Use PGP. ACM WPES '04, 77--84, ACM 2004.]]
8. C. Boyd, W. Mao and K. Paterson. Key Agreement using Statically Keyed Authenticators. ACNS 2004, LNCS 3089, 248--262, Springer 2004.]]
9. R. Canetti and H. Krawczyk. Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels. EUROCRYPT '01, LNCS 2045, 453--474, Springer 2001.]]
10. R.Canetti and H. Krawczyk. Universally Composable Notions of Key Exchange and Secure Channels.EUROCRYPT '02, LNCS 2332, 337--351, Springer 2002. Full version at eprint.iacr.org/2002/059.]]
11. R. Canetti and H. Krawczyk. Security Analysis of IKE 's Signature-based Key-Exchange Protocol.CRYPTO '02, LNCS 2442, 143--161, Springer 2002.]]
12. D. Chaum. Untraceable Electronic Mail,Return Addresses, and Digital Pseudonyms.Communications of the ACM, 24(2), February 1981.]]
13. D. Chaum. Blind Signatures for Untraceable Payments. CRYPTO '82, 199--203,Plenum 1982.]]
14. D. Chaum. Security Without Identification: Transaction Systems to Make Big Brother Obsolete. Communications of the ACM, 28(10):1030--1044, October 1985.]]
15. D. Chaum and H. van Antwerpen. Undeniable Signatures. CRYPTO '89,LNCS 435, 212--226, Springer 1990.]]
16. S. Chawla, C. Dwork, F. McSherry, A. Smith and H. Wee. Toward Privacy in Public Databases.TCC '05,LNCS 3378, 363--385, Springer 2005.]]
17. B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan. Private Information Retrieval. FOCS '95, 41--50, IEEE 1995.]]
18. R. Cramer and V. Shoup. A Practical Public-Key Cryptosystem Secure Against Adaptive Chosen Ciphertexts Attacks. CRYPTO '98, LNCS 1462, 13--25, Springer 1998.]]
19. I. Damgard. Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks.CRYPTO '91,LNCS 576, 445--456, Springer 1992.]]
20. A. Dent. Cramer-Shoup is Plaintext-Aware in the Standard Model. EUROCRYPT '06,LNCS 4004, 289--307, Springer 2006.]]
21. M. Di Raimondo and R. Gennaro. New Approaches for Deniable Authentication. ACM CCS '05, 112--121, ACM 2005.]]
22. M. Di Raimondo, R. Gennaro and H. Krawczyk. Secure Off-the-Record Messaging. ACM WPES '05,81--89, ACM Press, 2005.]]
23. D. Dolev, C. Dwork and M. Naor. Non-Malleable Cryptography, SIAM J. Comp., 30(2): 391--437, April 2000.]]
24. C. Dwork and K. Nissim. Privacy-Preserving Datamining on Vertically Partitioned Databases. CRYPTO '04, LNCS 3152, 528--544, Springer 2004.]]
25. C. Dwork, M. Naor and A. Sahai. Concurrent Zero-Knowledge. J. ACM 51(6): 851--898 (2004).]]
26. W. Diffie, P. Van Oorschot and M. Wiener. Authentication and Authenticate Key Exchange.Designs,Codes and Cryptography, no.2, 107--125, 1992.]]
27. S. Goldwasser, S. Micali,and C. Rackoff. The Knowledge Complexity of Interactive Proof-systems.SIAM J.Comp., 18(1): 186--208, February 1989.]]
28. S. Hada and T. Tanaka. On the Existence of 3-Round Zero-Knowledge Protocols.CRYPTO '98, LNCS 1462, 408--423, Springer 1998.]]
29. D. Harkins and D. Carrel, eds. The Internet Key Exchange (IKE). RFC 2409 November 1998.]]
30. ISO/IEC IS 9798-3,"Entity authentication mechanisms ¿ Part 3: Entity authentication using asymmetric techniques ", 1993.]]
31. M. Jakobsson, K. Sako and R. Impagliazzo. Designated Verifier Proofs and Their Applications.EUROCRYPT '96, LNCS 1070, 143--154, Springer 1996.]]
32. J. Katz, Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications. EUROCRYPT '03, LNCS 2656, 211--228, Springer 2003.]]
33. C. Kaufman, ed., Internet Key Exchange (IKEv2) Protocol, draft-ietf-ipsec-ikev2-17. txt, September 2004 (pending RFC).]]
34. H. Krawczyk. SKEME: a versatile secure key exchange mechanism for Internet. IEEE SNDSS '96, 114--127, IEEE Press 1996.]]
35. H. Krawczyk. SIGMA: The 'SiGn-and-MAc 'Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols. CRYPTO '03,LNCS 2729, 400--425, Springer 2003. Available at www.research.ibm.com/security/sigma.p]]
36. Y. Lindell and B. Pinkas. Privacy Preserving Data Mining. J. of Cryptology, 15(3): 177--206, Springer 2002.]]
37. C. H. Lim and P. J. Lee. A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. CRYPTO '97, LNCS 1294, 249--263, Springer 1997.]]
38. W. Mao and K. G. Paterson. On the Plausible Deniability Feature of Internet Protocols. Manuscript.]]
39. R. Pass. On Deniability in the Common Reference String and Random Oracle Model. CRYPTO '03, LNCS 2729, 316--337, Springer 2003.]]
40. R. Rivest, A. Shamir and Y. Tauman. How to Leak a Secret. ASIACRYPT '01, LNCS 2248, 552--565, Springer 2001]]
41. V. Shoup. On Formal Models for Secure Key Exchange. IBM Research Report RZ 3120, April 1999.]]

Index Terms

• Networks

  • Network protocols

    • Application layer protocols

• Security and privacy

  • Security services

    • Authentication

  • Systems security

    • Operating systems security