research-article

Examining indistinguishability-based security models for key exchange protocols: the case of CK, CK-HMQV, and eCK

Author:

Cas CremersAuthors Info & Claims

ASIACCS '11: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security

Pages 80 - 91

https://doi.org/10.1145/1966913.1966925

Published: 22 March 2011 Publication History

Abstract

Many recent key exchange (KE) protocols have been proven secure in the CK, CK-HMQV, or eCK security models. The exact relation between these security models, and hence the relation between the security guarantees provided by the protocols, is unclear. We show first that the CK, CK-HMQV, and eCK security models are formally incomparable. Second, we show that these models are also practically incomparable, by providing for each model attacks on protocols from the literature that are not considered by the other models. Third, our analysis enables us to find previously unreported flaws in protocol security proofs from the literature. We identify the causes of these flaws and show how they can be avoided.

References

[1]

E. Barker, D. Johnson, and M. Smid. NIST special publication 800--56A: Recommendation for pair-wise key establishment schemes using discrete logarithm cryptography (revised). Technical report, NIST, March 2007.

Digital Library

[2]

M. Bellare, R. Canetti, and H. Krawczyk. A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract). In STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 419--428, New York, NY, USA, 1998. ACM.

Digital Library

[3]

M. Bellare and P. Rogaway. Provably secure session key distribution: the three party case. In STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 57--66, New York, NY, USA, 1995. ACM.

Digital Library

[4]

C. Boyd, Y. Cliff, J. M. G. Nieto, and K. G. Paterson. One-round key exchange in the standard model. IJACT, 1(3):181--199, 2009.

Digital Library

[5]

R. Canetti and H. Krawczyk. Analysis of key-exchange protocols and their use for building secure channels. Cryptology ePrint Archive, Report 2001/040, 2001. http://eprint.iacr.org/.

[6]

R. Canetti and H. Krawczyk. Analysis of key-exchange protocols and their use for building secure channels. In EUROCRYPT'01, volume 2045 of LNCS, pages 453--474. Springer, 2001.

Digital Library

[7]

R. Canetti and H. Krawczyk. Universally composable notions of key exchange and secure channels. In EUROCRYPT'02, Lecture Notes in Computer Science, pages 337--351. Springer-Verlag, 2002.

Digital Library

[8]

Q. Cheng, G. Han, and C. Ma. A new efficient and strongly secure authenticated key exchange protocol. Information Assurance and Security, International Symposium on, 1:499--502, 2009.

Digital Library

[9]

K.-K. Choo, C. Boyd, and Y. Hitchcock. Examining indistinguishability-based proof models for key establishment proofs. In ASIACRYPT, volume 3788 of Lecture Notes in Computer Science, pages 624--643. Springer, 2005.

Digital Library

[10]

K.-K. Choo, C. Boyd, Y. Hitchcock, and G. Maitland. On session identifiers in provably secure protocols. In SCN, volume 3352 of Lecture Notes in Computer Science, pages 351--366. Springer-Verlag, 2004.

Digital Library

[11]

C. Cremers. Session-state Reveal is stronger than Ephemeral Key Reveal: Attacking the NAXOS key exchange protocol. In ACNS'09, Lecture Notes in Computer Science, 2009.

Digital Library

[12]

H. Huang and Z. Cao. Strongly secure authenticated key exchange protocol based on computational Diffie-Hellman problem. Cryptology ePrint Archive, Report 2008/500, 2008. http://eprint.iacr.org/.

[13]

M. Just and S. Vaudenay. Authenticated multi-party key agreement. In Advances in Cryptology-ASIACRYPT 1996, volume 1163 of Lecture Notes in Computer Science, pages 36--49, 1996.

Digital Library

[14]

M. Kim, A. Fujioka, and B. Ustaoǧlu. Strongly secure authenticated key exchange without NAXOS' approach. In IWSec, volume 5824/2009 of Lecture Notes in Computer Science, pages 174--191. Springer-Verlag, 2009.

Digital Library

[15]

K. Kobara, S. Shin, and M. Strefler. Partnership in key exchange protocols. In ASIACCS '09: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, pages 161--170, New York, NY, USA, 2009. ACM.

Digital Library

[16]

H. Krawczyk. HMQV: A high-performance secure Diffie-Hellman protocol. In CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 546--566. Springer-Verlag, 2005.

Digital Library

[17]

B. LaMacchia, K. Lauter, and A. Mityagin. Stronger security of authenticated key exchange. Cryptology ePrint Archive, Report 2006/073, 2006. http://eprint.iacr.org/.

[18]

B. LaMacchia, K. Lauter, and A. Mityagin. Stronger security of authenticated key exchange. In ProvSec, volume 4784 of Lecture Notes in Computer Science, pages 1--16. Springer, 2007.

Digital Library

[19]

L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone. An efficient protocol for authenticated key agreement. Designs, Codes and Cryptography, 28:119--134, 2003.

Digital Library

[20]

J. Lee and C. S. Park. An efficient authenticated key exchange protocol with a tight security reduction. Cryptology ePrint Archive, Report 2008/345, 2008. http://eprint.iacr.org/.

[21]

J. Lee and J. H. Park. Authenticated key exchange secure under the computational Diffie-Hellman assumption. Cryptology ePrint Archive, Report 2008/344, 2008. http://eprint.iacr.org/.

[22]

A. Menezes and B. Ustaoǧlu. Comparing the pre- and post-specified peer models for key agreement. In Proceedings of ACISP 2008, volume 5107 of Lecture Notes in Computer Science, pages 53--68, 2008.

Digital Library

[23]

D. Moriyama and T. Okamoto. An eCK-secure authenticated key exchange protocol without random oracles. In ProvSec, volume 5848 of Lecture Notes in Computer Science, pages 154--167. Springer-Verlag, 2009.

Digital Library

[24]

T. Okamoto. Authenticated key exchange and key encapsulation in the standard model. In ASIACRYPT, volume 4833 of Lecture Notes in Computer Science, pages 474--484, 2007.

Digital Library

[25]

M. D. Raimondo, R. Gennaro, and H. Krawczyk. Deniable authentication and key exchange. Cryptology ePrint Archive, Report 2006/280, 2006. http://eprint.iacr.org/.

[26]

B. Ustaoǧlu. Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS. Des. Codes Cryptography, 46(3):329--342, 2008.

Digital Library

[27]

J. Xia, J. Wang, L. Fang, Y. Ren, and S. Bian. Formal proof of relative strengths of security between ECK2007 model and other proof models for key agreement protocols. Cryptology ePrint Archive, Report 2008/479, 2008. http://eprint.iacr.org/, retrieved on April 1st, 2009.

Cited By

Katz JRosenberg M(2024)LATKE: A Framework for Constructing Identity-Binding PAKEsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_7(218-250)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68379-4_7
Boyd Cde Kock BMillerjord L(2023)Modular Design of KEM-Based Authenticated Key ExchangeInformation Security and Privacy10.1007/978-3-031-35486-1_24(553-579)Online publication date: 15-Jun-2023
https://doi.org/10.1007/978-3-031-35486-1_24
Hashimoto KKatsumata SKwiatkowski KPrest T(2022)An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-quantum, State Leakage Secure, and DeniableJournal of Cryptology10.1007/s00145-022-09427-135:3Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00145-022-09427-1
Show More Cited By

Index Terms

Examining indistinguishability-based security models for key exchange protocols: the case of CK, CK-HMQV, and eCK
1. Networks
  1. Network protocols
    1. Protocol correctness
      1. Protocol testing and verification
2. Security and privacy

Recommendations

An Efficient and Leakage-Resilient RSA-Based Authenticated Key Exchange Protocol with Tight Security Reduction*A preliminary version appeared in [33]. Some mistakes about security proof are corrected in this paper.

Both mutual authentication and generation of session keys can be accomplished by an authenticated key exchange (AKE) protocol. Let us consider the following situation: (1) a client, who communicates with many different servers, remembers only one ...
Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security

This paper discusses how to realize practical post-quantum authenticated key exchange (AKE) with strong security, i.e., CK⁺ security (Krawczyk, CRYPTO 2005). It is known that strongly secure post-quantum AKE protocols exist on a generic construction ...
Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal

We show that it is possible to achieve perfect forward secrecy (PFS) in two-message or one-round key exchange (KE) protocols even in the presence of very strong active adversaries that can reveal random values of sessions and compromise long-term secret ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIACCS '11: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security

March 2011

527 pages

ISBN:9781450305648

DOI:10.1145/1966913

General Chairs:
Bruce Cheung
The University of Hong Kong, China
,
Lucas Chi Kwong Hui
The University of Hong Kong, China
,
Program Chairs:
Ravi Sandhu
University of Texas, San Antonio
,
Duncan S. Wong
City University of Hong Kong, China

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Eidgenössische Technische Hochschule Zürich

Conference

ASIA CCS '11

Sponsor:

SIGSAC

ASIA CCS '11: 6th ACM Symposium on Information, Compuer and Communications Security

March 22 - 24, 2011

Hong Kong, China

Acceptance Rates

ASIACCS '11 Paper Acceptance Rate 35 of 217 submissions, 16%;

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
343
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Katz JRosenberg M(2024)LATKE: A Framework for Constructing Identity-Binding PAKEsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_7(218-250)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68379-4_7
Boyd Cde Kock BMillerjord L(2023)Modular Design of KEM-Based Authenticated Key ExchangeInformation Security and Privacy10.1007/978-3-031-35486-1_24(553-579)Online publication date: 15-Jun-2023
https://doi.org/10.1007/978-3-031-35486-1_24
Hashimoto KKatsumata SKwiatkowski KPrest T(2022)An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-quantum, State Leakage Secure, and DeniableJournal of Cryptology10.1007/s00145-022-09427-135:3Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00145-022-09427-1
BOYD CPointcheval D(2022)Key ExchangeAsymmetric Cryptography10.1002/9781394188369.ch9(187-211)Online publication date: 30-Nov-2022
https://doi.org/10.1002/9781394188369.ch9
TOMIDA JFUJIOKA ANAGAI ASUZUKI K(2021)Strongly Secure Identity-Based Key Exchange with Single Pairing OperationIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2020CIP0010E104.A:1(58-68)Online publication date: 1-Jan-2021
https://doi.org/10.1587/transfun.2020CIP0010
Xiao YZhang RMa H(2021)Modular Design of Role-Symmetric Authenticated Key Exchange ProtocolsAdvances in Cryptology – ASIACRYPT 202110.1007/978-3-030-92068-5_25(742-772)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92068-5_25
Jager TKiltz ERiepel DSchäge S(2021)Tightly-Secure Authenticated Key Exchange, RevisitedAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77870-5_5(117-146)Online publication date: 16-Jun-2021
https://doi.org/10.1007/978-3-030-77870-5_5
de Saint Guilhem CFischlin MWarinschi B(2020)Authentication in Key-Exchange: Definitions, Relations and Composition2020 IEEE 33rd Computer Security Foundations Symposium (CSF)10.1109/CSF49147.2020.00028(288-303)Online publication date: Jun-2020
https://doi.org/10.1109/CSF49147.2020.00028
Boyd CGellert K(2020)A Modern View on Forward SecurityThe Computer Journal10.1093/comjnl/bxaa104Online publication date: 24-Aug-2020
https://doi.org/10.1093/comjnl/bxaa104
Xiao YZhang RMa H(2020)Tightly Secure Two-Pass Authenticated Key Exchange Protocol in the CK ModelTopics in Cryptology – CT-RSA 202010.1007/978-3-030-40186-3_9(171-198)Online publication date: 24-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-40186-3_9
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents