OAKE: a new family of implicitly authenticated diffie-hellman protocols

ABSTRACT

Cryptographic algorithm standards play an important role both to the practice of information security and to cryptography theory research. Among them, the KEA and OPACITY (KEA/OPACITY, in short) protocols, and the MQV and HMQV ((H)MQV, in short) protocols, are a family of implicitly authenticated Diffie-Hellman key-exchange (IA-DHKE) protocols that are among the most efficient authenticated key-exchange protocols known and are widely standardized. In this work, from some new design insights, we develop a new family of practical IA-DHKE protocols, referred to as OAKE (standing for "optimal authenticated key-exchange" in brief). We show that the OAKE protocol family combines, in essence, the advantages of both (H)MQV and KEA/OPACITY, while saving from or alleviating the disadvantages of them both.

References

1. M. Abdalla, J. H. An, M. Bellare, and C. Namprempre. From identification to signatures via Fiat-Shamir transform: Necessary and sufficient conditions for security and forward-security. IEEE Transactions on Information Theory, 54(8):3631--3646, 2008.
2. M. Abe and S. Fehr. PerfectuppercaseNIZK with adaptive soundness. In TCC, pages 118--136, 2007.
3. W. Aiello, S. M. Bellovin, M. Blaze, R. Canetti, J. Ioannidis, A. D. Keromytis, and O. Reingold. Just fast keying: Key agreement in a hostile internet. ACM Trans. Inf. Syst. Secur., 7(2):242--273, 2004.
4. ANSI. 504--1: Information technology-generic identity command set, part 1: Card application command set.
5. ANSI. AmericanuppercaseNationaluppercaseStandard,uppercaseX9.42--2001.
6. B. Barak. How to go beyond the black-box simulation barrier. In FOCS, pages 106--115, 2001.
7. E. Barker, D. Johnson, and M. Smid.uppercaseNIST special publication 800--56\uppercaseA: Recommendation for pair-wise key establishment schemes using discrete logarithm cryptography (revised).uppercaseTechnical report, 2007.
8. M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. In CRYPTO, pages 1--15, 1996.
9. M. Bellare and A. Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In CRYPTO, pages 273--289, 2004.
10. M. Bellare and A. Palacio. Towards plaintext-aware public-key encryption without random oracles. In ASIACRYPT, pages 48--62, 2004.
11. M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM Conference on Computer and Communications Security, pages 62--73, 1993.
12. E. Biham and A. Shamir. Differential fault analysis of secret key cryptosystems. In CRYPTO, pages 513--525, 1997.
13. N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In ITCS, pages 326--349, 2012.
14. S. Blake-Wilson, D. Johnson, and A. Menezes. Key agreement protocols and their security analysis. In IMA Int. Conf., pages 30--45, 1997.
15. C. Boyd, Y. Cliff, J. M. G. Nieto, and K. G. Paterson. Efficient one-round key exchange in the standard model. In ACISP, pages 69--83, 2008.
16. C. Boyd, W. Mao, and K. G. Paterson. Deniable authenticated key establishment for internet protocols. In Security Protocols Workshop, pages 255--271, 2003.
17. C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. ISBN 3--540--43107--1, Springer-Verlag.
18. Z. Brakerski, Y. T. Kalai, J. Katz, and V. Vaikuntanathan. Overcoming the hole in the bucket: Public-key cryptography resilient to continual memory leakage. In FOCS, pages 501--510, 2010.
19. R. Canetti. Security and composition of cryptographic protocols: a tutorial (part i). SIGACT News, 37(3):67--92, 2006.
20. R. Canetti and R. R. Dakdouk. Extractable perfectly one-way functions. In ICALP (2), pages 449--460, 2008.
21. R. Canetti and R. R. Dakdouk. Towards a theory of extractable functions. In TCC, pages 595--613, 2009.
22. R. Canetti and H. Krawczyk. Analysis of key-exchange protocols and their use for building secure channels. In EUROCRYPT, pages 453--474, 2001.
23. L. Chen and Y. Chen. The n-\uppercaseDiffie-\uppercaseHellman problem and its applications. In ISC, pages 119--134, 2011.
24. L. Chen and C. Kudla. Identity based authenticated key agreement protocols from pairings. In CSFW, pages 219--233, 2003.
25. C. Cremers. Examining indistinguishability-based security models for key exchange protocols: the case ofuppercaseCK,uppercaseCK-HMQV, and e\uppercaseCK. In ASIACCS, pages 80--91, 2011.
26. C. J. F. Cremers. Session-state reveal is stronger than ephemeral key reveal: Attacking theuppercaseNAXOS authenticated key exchange protocol. In ACNS, pages 20--33, 2009.
27. I. Damgård. Towards practical public key systems secure against chosen ciphertext attacks. In CRYPTO, pages 445--456, 1991.
28. I. Damgård, S. Faust, and C. Hazay. Secure two-party computation with low communication. In TCC, pages 54--74, 2012.
29. A. W. Dent. TheuppercaseCramer-\uppercaseShoup encryption scheme is plaintext aware in the standard model. In EUROCRYPT, pages 289--307, 2006.
30. T. Dierks and C. Allen. The TLS Protocol, Version 1.0. Request for Comments: 2246, January 1999.
31. W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644--654, 1976.
32. W. Diffie, P. C. van Oorschot, and M. J. Wiener. Authentication and authenticated key exchanges. Des. Codes Cryptography, 2(2):107--125, 1992.
33. V. S. Dimitrov, G. A. Jullien, and W. C. Miller. Complexity and fast algorithms for multiexponentiations. IEEE Trans. Computers, 49(2):141--147, 2000.
34. Y. Dodis, J. Katz, A. Smith, and S. Walfish. Composability and on-line deniability of authentication. In TCC, pages 146--162, 2009.
35. A. Freier, P. Karlton, and P. Kocher. The SSL Protocol, Version 3.0. INTERNET-DRAFT: draft-freier-ssl-version3-02.txt, November 1996.
36. R. Gennaro, H. Krawczyk, and T. Rabin. Okamoto-\uppercaseTanaka revisited: Fully authenticateduppercaseDiffie-\uppercaseHellman with minimal overhead. In ACNS, pages 309--328, 2010.
37. S. Goldwasser, H. Lin, and A. Rubinstein. Delegation of computation without rejection problem from designated verifieruppercaseCS-proofs. IACR Cryptology ePrint Archive, 2011:456, 2011.
38. D. M. Gordon. A survey of fast exponentiation methods. J. Algorithms, 27(1):129--146, 1998.
39. J. Groth. Short pairing-based non-interactive zero-knowledge arguments. In ASIACRYPT, pages 321--340, 2010.
40. S. Hada and T. Tanaka. On the existence of 3-round zero-knowledge protocols. In CRYPTO, pages 408--423, 1998.
41. J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: cold-boot attacks on encryption keys. Commun. ACM, 52(5):91--98, 2009.
42. S. Halevi and H. Krawczyk. One-passuppercaseHMQV and asymmetric key-wrapping. In Public Key Cryptography, pages 317--334, 2011.
43. D. Harkins and D. Carreal. Internet Key Exchange (IKE). RFC 2049, The Internet Engineering Task Force, November 1998.
44. K. Hickman. The SSL Protocol. Online document: www.netscape.com/eng/security/SSL-2.html, Feburary 1995.
45. IEEE. 1363--2000: Standard specifications for public key cryptography.
46. ISO/IEC. 11770--3:2008 information technology - security techniques - key management - part 3: Mechanisms using asymmetric techniques.
47. ISO/IEC. 24727--6:2010 identification cards - integrated circuit card programming interfaces - part 6: Registration authority procedures for the authentication protocols for interoperability.
48. B. S. Kaliski. An unknown key-share attack on theuppercaseMQV key agreement protocol. ACM Trans. Inf. Syst. Secur., 4(3):275--288, 2001.
49. C. Kaufman. Internet Key Exchange (IKEv2) Protocol. The Internet Engineering Task Force: INTERNET-DRAFT, October 2002.
50. H. Krawczyk.uppercaseSIGMA: The 'sign-and-mac' approach to authenticateduppercaseDiffie-\uppercaseHellman and its use in theuppercaseIKE-protocols. In CRYPTO, pages 400--425, 2003.
51. H. Krawczyk.uppercaseHMQV: A high-performance secureuppercaseDiffie-\uppercaseHellman protocol. In CRYPTO, pages 546--566, 2005.
52. H. Krawczyk, K. G. Paterson, and H. Wee. On the security of theuppercaseTLS protocol: A systematic analysis. IACR Cryptology ePrint Archive, 2013:339, 2013.
53. C. Kudla and K. G. Paterson. Modular security proofs for key agreement protocols. In ASIACRYPT, pages 549--565, 2005.
54. S. Kunz-Jacques and D. Pointcheval. A new key exchange protocol based onuppercaseMQV assuming public computations. In SCN, pages 186--200, 2006.
55. B. A. LaMacchia, K. Lauter, and A. Mityagin. Stronger security of authenticated key exchange. In ProvSec, pages 1--16, 2007.
56. K. Lauter and A. Mityagin. Security analysis ofuppercaseKEA authenticated key exchange protocol. In Public Key Cryptography, pages 378--394, 2006.
57. A. B. Lewko, Y. Rouselakis, and B. Waters. Achieving leakage resilience through dual system encryption. In TCC, pages 70--88, 2011.
58. T. Matsumoto, Y. Takashima, and H. Imai. On seeking smart public-key distribution systems. Trans. IECE of Japan, E69(2):99--106, 1986.
59. A. Menezes, M. Qu, and S. Vanstone. Some new key agreement protocols providing mutual implicit authentication. In SAC, pages 70--88, 1995.
60. A. Menezes and B. Ustaoglu. On the importance of public-key validation in theuppercaseMQV anduppercaseHMQV key agreement protocols. In INDOCRYPT, pages 133--147, 2006.
61. A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
62. T. Mie. Polylogarithmic two-round argument systems. J. Mathematical Cryptology, 2(4):343--363, 2008.
63. NIST. Special publication 800--56 (\uppercaseDRAFT): Recommendation on key establishment schemes,uppercaseDraft 2,uppercaseJanuary 2003.
64. NIST. S\uppercaseP 800--56 (\uppercaseDRAFT): Special publication 800--56, recommendation for pair-wise key establishment schemes using discrete logarithm cryptography,uppercaseJuly 2005.
65. NIST.uppercaseSKIPJACK anduppercaseKEA algorithm specifications. http://csrc.nist.org/encryption/skipjack/skipjack.pdf, 1998.
66. T. Okamoto and D. Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In Public Key Cryptography, pages 104--118, 2001.
67. D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361--396, 2000.
68. M. D. Raimondo and R. Gennaro. New approaches for deniable authentication. In ACM Conference on Computer and Communications Security, pages 112--121, 2005.
69. M. D. Raimondo, R. Gennaro, and H. Krawczyk. Deniable authentication and key exchange. In ACM Conference on Computer and Communications Security, pages 400--409, 2006.
70. E. Saint, D. Fedronic, and S. Liu. Open Protocol for Access Control Identification and Ticketing with Privacy. Smart Card Alliance, July 2011. http://www.smartcardalliance.org/resources/pdf/\\ OPACITY\_Protocol\_3.7.pdf.
71. J. Stasak. NSAs Elliptic Curve Licensing Agreement. The IETF's Security Area Advisory Group, 2004.
72. A. C.-C. Yao and Y. Zhao. Deniable internet key exchange. In ACNS, pages 329--348, 2010.
73. A. C.-C. Yao and Y. Zhao. A new family of practical non-malleable protocols. IACR Cryptology ePrint Archive, 2011:35, 2011.

Index Terms

• General and reference

  • Document types

    • Computing standards, RFCs and guidelines

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques