research-article

VTBPEKE: Verifier-based Two-Basis Password Exponential Key Exchange

Authors:

David Pointcheval,

Guilin WangAuthors Info & Claims

ASIA CCS '17: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security

Pages 301 - 312

https://doi.org/10.1145/3052973.3053026

Published: 02 April 2017 Publication History

Abstract

PAKE protocols, for Password-Authenticated Key Exchange, enable two parties to establish a shared cryptographically strong key over an insecure network using a short common secret as authentication means. After the seminal work by Bellovin and Merritt, with the famous EKE, for Encrypted Key Exchange, various settings and security notions have been defined, and many protocols have been proposed.

In this paper, we revisit the promising SPEKE, for Simple Password Exponential Key Exchange, proposed by Jablon. The only known security analysis works in the random oracle model under the CDH assumption, but in the multiplicative groups of finite fields only (subgroups of Zp*), which means the use of large elements and so huge communications and computations. Our new instantiation (TBPEKE, for Two-Basis Password Exponential Key Exchange) applies to any group, and our security analysis requires a DLIN-like assumption to hold. In particular, one can use elliptic curves, which leads to a better efficiency, at both the communication and computation levels. We additionally consider server corruptions, which immediately leak all the passwords to the adversary with symmetric PAKE. We thus study an asymmetric variant, also known as VPAKE, for Verifier-based Password Authenticated Key Exchange. We then propose a verifier-based variant of TBPEKE, the so-called VTBPEKE, which is also quite efficient, and resistant to server-compromise.

References

[1]

M. Abdalla, F. Benhamouda, and D. Pointcheval. Public-key encryption indistinguishable under plaintext-checkable attacks. Cryptology ePrint Archive, Report 2014/609, 2014. http://eprint.iacr.org/2014/609.

[2]

M. Abdalla, F. Benhamouda, and D. Pointcheval. Public-key encryption indistinguishable under plaintext-checkable attacks. In J. Katz, editor, PKC 2015, volume 9020 of LNCS, pages 332--352. Springer, Heidelberg, Mar. / Apr. 2015.

[3]

M. Abdalla, D. Catalano, C. Chevalier, and D. Pointcheval. Efficient two-party password-based key exchange protocols in the UC framework. In T. Malkin, editor, CT-RSA 2008, volume 4964 of LNCS, pages 335--351. Springer, Heidelberg, Apr. 2008.

Digital Library

[4]

M. Abdalla, C. Chevalier, and D. Pointcheval. Smooth projective hashing for conditionally extractable commitments. In S. Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 671--689. Springer, Heidelberg, Aug. 2009.

Digital Library

[5]

M. Abdalla, P.-A. Fouque, and D. Pointcheval. Password-based authenticated key exchange in the three-party setting. In S. Vaudenay, editor, PKC 2005, volume 3386 of LNCS, pages 65--84. Springer, Heidelberg, Jan. 2005.

Digital Library

[6]

M. Abdalla and D. Pointcheval. Simple password-based encrypted key exchange protocols. In A. Menezes, editor, CT-RSA 2005, volume 3376 of LNCS, pages 191--208. Springer, Heidelberg, Feb. 2005.

Digital Library

[7]

M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption. In 38th FOCS, pages 394--403. IEEE Computer Society Press, Oct. 1997.

Digital Library

[8]

M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated key exchange secure against dictionary attacks. In B. Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 139--155. Springer, Heidelberg, May 2000.

Digital Library

[9]

M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In V. Ashby, editor, ACM CCS 93, pages 62--73. ACM Press, Nov. 1993.

Digital Library

[10]

M. Bellare and P. Rogaway. Entity authentication and key distribution. In D. R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 232--249. Springer, Heidelberg, Aug. 1994.

Digital Library

[11]

M. Bellare and P. Rogaway. Provably secure session key distribution: The three party case. In 27th ACM STOC, pages 57--66. ACM Press, May / June 1995.

Digital Library

[12]

S. M. Bellovin and M. Merritt. Encrypted key exchange: Password-based protocols secure against dictionary attacks. In 1992 IEEE Symposium on Security and Privacy, pages 72--84. IEEE Computer Society Press, May 1992.

Digital Library

[13]

S. M. Bellovin and M. Merritt. Augmented encrypted key exchange: A password-based protocol secure against dictionary attacks and password file compromise. In V. Ashby, editor, ACM CCS 93, pages 244--250. ACM Press, Nov. 1993.

Digital Library

[14]

F. Benhamouda and D. Pointcheval. Verifier-based password-authenticated key exchange: New models and constructions. Cryptology ePrint Archive, Report 2013/833, 2013. http://eprint.iacr.org/2013/833.

[15]

D. Boneh and X. Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology, 21(2):149--177, Apr. 2008.

Digital Library

[16]

D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41--55. Springer, Heidelberg, Aug. 2004.

[17]

V. Boyko, P. D. MacKenzie, and S. Patel. Provably secure password-authenticated key exchange using Diffie-Hellman. In B. Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 156--171. Springer, Heidelberg, May 2000.

Digital Library

[18]

E. Bresson, O. Chevassut, and D. Pointcheval. Security proofs for an efficient password-based key exchange. In S. Jajodia, V. Atluri, and T. Jaeger, editors, ACM CCS 03, pages 241--250. ACM Press, Oct. 2003.

Digital Library

[19]

E. Bresson, O. Chevassut, and D. Pointcheval. New security results on encrypted key exchange. In F. Bao, R. Deng, and J. Zhou, editors, PKC 2004, volume 2947 of LNCS, pages 145--158. Springer, Heidelberg, Mar. 2004.

[20]

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067, 2000. http://eprint.iacr.org/2000/067.

[21]

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136--145. IEEE Computer Society Press, Oct. 2001.

Digital Library

[22]

R. Canetti, S. Halevi, J. Katz, Y. Lindell, and P. D. MacKenzie. Universally composable password-based key exchange. In R. Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 404--421. Springer, Heidelberg, May 2005.

Digital Library

[23]

D. Cash, E. Kiltz, and V. Shoup. The twin Diffie-Hellman problem and applications. In N. P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 127--145. Springer, Heidelberg, Apr. 2008.

Digital Library

[24]

D. Catalano, D. Pointcheval, and T. Pornin. IPAKE: Isomorphisms for password-based authenticated key exchange. In M. Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 477--493. Springer, Heidelberg, Aug. 2004.

[25]

R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In L. R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 45--64. Springer, Heidelberg, Apr. / May 2002.

Digital Library

[26]

Y. Ding and P. Horster. Undetectable on-line password guessing attacks. SIGOPS Oper. Syst. Rev., 29:77--86, October 1995.

Digital Library

[27]

R. Gennaro. Faster and shorter password-authenticated key exchange. In R. Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 589--606. Springer, Heidelberg, Mar. 2008.

Digital Library

[28]

R. Gennaro and Y. Lindell. A framework for password-based authenticated key exchange. In E. Biham, editor, EUROCRYPT 2003, volume 2656 of LNCS, pages 524--543. Springer, Heidelberg, May 2003. http://eprint.iacr.org/2003/032.ps.gz.

Digital Library

[29]

C. Gentry, P. MacKenzie, and Z. Ramzan. A method for making password-based key exchange resilient to server compromise. In C. Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 142--159. Springer, Heidelberg, Aug. 2006.

Digital Library

[30]

C. Gentry, P. D. Mackenzie, and Z. Ramzan. Password authenticated key exchange using hidden smooth subgroups. In V. Atluri, C. Meadows, and A. Juels, editors, ACM CCS 05, pages 299--309. ACM Press, Nov. 2005.

Digital Library

[31]

A. Groce and J. Katz. A new framework for efficient password-based authenticated key exchange. In E. Al-Shaer, A. D. Keromytis, and V. Shmatikov, editors, ACM CCS 10, pages 516--525. ACM Press, Oct. 2010.

Digital Library

[32]

D. Harkins. Simultaneous authentication of equals: A secure, password-based key exchange for mesh networks. In Proceedings of the 2008 Second International Conference on Sensor Technologies and Applications, SENSORCOMM '08, pages 839--844, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[33]

D. P. Jablon. Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. Rev., 26(5):5--26, Oct. 1996.

Digital Library

[34]

J. Katz, R. Ostrovsky, and M. Yung. Efficient password-authenticated key exchange using human-memorable passwords. In B. Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 475--494. Springer, Heidelberg, May 2001.

Digital Library

[35]

J. Katz, R. Ostrovsky, and M. Yung. Forward secrecy in password-only key exchange protocols. In S. Cimato, C. Galdi, and G. Persiano, editors, SCN 02, volume 2576 of LNCS, pages 29--44. Springer, Heidelberg, Sept. 2003.

Digital Library

[36]

J. Katz, R. Ostrovsky, and M. Yung. Efficient and secure authenticated key exchange using weak passwords. Journal of the ACM, 57(1):78--116, 2009.

Digital Library

[37]

J. Katz and V. Vaikuntanathan. Smooth projective hashing and password-based authenticated key exchange from lattices. In M. Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 636--652. Springer, Heidelberg, Dec. 2009.

Digital Library

[38]

J. Katz and V. Vaikuntanathan. Round-optimal password-based authenticated key exchange. In Y. Ishai, editor, TCC 2011, volume 6597 of LNCS, pages 293--310. Springer, Heidelberg, Mar. 2011.

Digital Library

[39]

F. Kiefer and M. Manulis. Zero-knowledge password policy checks and verifier-based PAKE. In M. Kutylowski and J. Vaidya, editors, ESORICS 2014, Part II, volume 8713 of LNCS, pages 295--312. Springer, Heidelberg, Sept. 2014.

[40]

W. Ladd. SPAKE2, a PAKE, 2015. https://tools.ietf.org/html/draft-irtf-cfrg-spake2-02.

[41]

S. Lucks. Open key exchange: How to defeat dictionary attacks without encrypting public keys. In Workshop on Security Protocols, École Normale Supérieure, 1997.

Digital Library

[42]

P. MacKenzie. On the security of the SPEKE password-authenticated key exchange protocol. Cryptology ePrint Archive, Report 2001/057, 2001. http://eprint.iacr.org/2001/057.

[43]

P. D. MacKenzie, S. Patel, and R. Swaminathan. Password-authenticated key exchange based on RSA. In T. Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 599--613. Springer, Heidelberg, Dec. 2000.

Digital Library

[44]

C.-P. Schnorr. Efficient identification and signatures for smart cards (abstract) (rump session). In J.-J. Quisquater and J. Vandewalle, editors, EUROCRYPT'89, volume 434 of LNCS, pages 688--689. Springer, Heidelberg, Apr. 1990.

Digital Library

[45]

S. Shin and K. Kobara. RFC 6628: Efficient Augmented Password-Only Authentication and Key Exchange for IKEv2, 2012. https://tools.ietf.org/pdf/rfc6628.pdf.

[46]

S. Shin and K. Kobara. Augmented Password-Authenticated Key Exchange (AugPAKE), 2016. https://tools.ietf.org/html/draft-irtf-cfrg-augpake-06.

[47]

S. Shin and K. Kobara. Augmented Password-Authenticated Key Exchange for Transport Layer Security (TLS), 2016. http://www.ietf.org/id/draft-shin-tls-augpake-07.txt.

[48]

S. Shin, K. Kobara, and H. Imai. Security proof of AugPAKE. Cryptology ePrint Archive, Report 2010/334, 2010. http://eprint.iacr.org/2010/334.

[49]

V. Shoup. Lower bounds for discrete logarithms and related problems. In W. Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 256--266. Springer, Heidelberg, May 1997.

Digital Library

[50]

T. D. Wu. The secure remote password protocol. In NDSS'98. The Internet Society, Mar. 1998.

Cited By

Qi MHu WTai Y(2024)SAE+: One-Round Provably Secure Asymmetric SAE Protocol for Client-Server ModelIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337279919(3906-3913)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3372799
Qi MHu W(2024)Provably Secure Asymmetric PAKE Protocol for Protecting IoT AccessIEEE Internet of Things Journal10.1109/JIOT.2023.331420911:4(7071-7078)Online publication date: 15-Feb-2024
https://doi.org/10.1109/JIOT.2023.3314209
Hanai STanaka KTezuka MYoshida Y(2024)Universally Composable Relaxed Asymmetric Password-Authenticated Key ExchangeSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_13(272-293)Online publication date: 10-Sep-2024
https://doi.org/10.1007/978-3-031-71073-5_13
Show More Cited By

Index Terms

VTBPEKE: Verifier-based Two-Basis Password Exponential Key Exchange
1. Security and privacy
  1. Security services
    1. Authentication

Recommendations

Efficient password-authenticated key exchange for three-party secure against undetectable on-line dictionary attacks
ICCS'06: Proceedings of the 6th international conference on Computational Science - Volume Part I

A password-authenticated key exchange (PAKE) protocol in the three-party setting allows two users communicating over a public network to agree on a common session key by the help of a server. In the setting the users do not share a password between ...
ID-Based Two-Server Password-Authenticated Key Exchange
Computer Security - ESORICS 2014
Abstract
In two-server password-authenticated key exchange (PAKE) protocol, a client splits its password and stores two shares of its password in the two servers, respectively, and the two servers then cooperate to authenticate the client without knowing ...
Cryptanalysis of simple three-party key exchange protocol (S-3PAKE)

Password-authenticated key exchange (PAKE) protocols allow parties to share secret keys in an authentic manner based on an easily memorizable password. Recently, Lu and Cao proposed a three-party password-authenticated key exchange protocol, so called S-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIA CCS '17: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security

April 2017

952 pages

ISBN:9781450349444

DOI:10.1145/3052973

General Chairs:
Ramesh Karri
New York University, New York, USA
,
Ozgur Sinanoglu
New York University Abu Dhabi, UAE
,
Program Chairs:
Ahmad-Reza Sadeghi
Technische Universität Darmstadt, Germany
,
Xun Yi
RMIT University, Australia

Copyright © 2017 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 the author(s) 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: 02 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASIA CCS '17

Sponsor:

SIGSAC

ASIA CCS '17: ACM Asia Conference on Computer and Communications Security

April 2 - 6, 2017

Abu Dhabi, United Arab Emirates

Acceptance Rates

ASIA CCS '17 Paper Acceptance Rate 67 of 359 submissions, 19%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
288
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)7

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qi MHu WTai Y(2024)SAE+: One-Round Provably Secure Asymmetric SAE Protocol for Client-Server ModelIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337279919(3906-3913)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3372799
Qi MHu W(2024)Provably Secure Asymmetric PAKE Protocol for Protecting IoT AccessIEEE Internet of Things Journal10.1109/JIOT.2023.331420911:4(7071-7078)Online publication date: 15-Feb-2024
https://doi.org/10.1109/JIOT.2023.3314209
Hanai STanaka KTezuka MYoshida Y(2024)Universally Composable Relaxed Asymmetric Password-Authenticated Key ExchangeSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_13(272-293)Online publication date: 10-Sep-2024
https://doi.org/10.1007/978-3-031-71073-5_13
Barbosa MGellert KHesse JJarecki S(2024)Bare PAKE: Universally Composable Key Exchange from Just PasswordsAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68379-4_6(183-217)Online publication date: 16-Aug-2024
https://doi.org/10.1007/978-3-031-68379-4_6
Lian HYang YZhao Y(2023)Efficient and Strong Symmetric Password Authenticated Key Exchange With Identity Privacy for IoTIEEE Internet of Things Journal10.1109/JIOT.2022.321952410:6(4725-4734)Online publication date: 15-Mar-2023
https://doi.org/10.1109/JIOT.2022.3219524
Han YXu CLi SJiang CChen K(2023)ttPAKE: Typo tolerance password-authenticated key exchangeJournal of Information Security and Applications10.1016/j.jisa.2023.10365879(103658)Online publication date: Dec-2023
https://doi.org/10.1016/j.jisa.2023.103658
Liu XLiu SHan SGu D(2023)EKE Meets Tight Security in the Universally Composable FrameworkPublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_24(685-713)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31368-4_24
Duman JHartmann DKiltz EKunzweiler SLehmann JRiepel D(2023)Generic Models for Group ActionsPublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_15(406-435)Online publication date: 2-May-2023
https://doi.org/10.1007/978-3-031-31368-4_15
Hao Fvan Oorschot PSuga YSakurai KDing XSako K(2022)SoKProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security10.1145/3488932.3523256(697-711)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1145/3488932.3523256
Li ZWang DMorais E(2022)Quantum-Safe Round-Optimal Password Authentication for Mobile DevicesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2020.304077619:3(1885-1899)Online publication date: 1-May-2022
https://doi.org/10.1109/TDSC.2020.3040776
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