skip to main content
10.1145/3052973.3053026acmconferencesArticle/Chapter ViewAbstractPublication Pagesasia-ccsConference Proceedingsconference-collections
research-article

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

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[26]
Y. Ding and P. Horster. Undetectable on-line password guessing attacks. SIGOPS Oper. Syst. Rev., 29:77--86, October 1995.
[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.
[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.
[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.
[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.
[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.
[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.
[33]
D. P. Jablon. Strong password-only authenticated key exchange. SIGCOMM Comput. Commun. Rev., 26(5):5--26, Oct. 1996.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[50]
T. D. Wu. The secure remote password protocol. In NDSS'98. The Internet Society, Mar. 1998.

Cited By

View all

Index Terms

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

    Recommendations

    Comments

    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
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 02 April 2017

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dictionary attacks
    2. password-authenticated key exchange
    3. server compromise

    Qualifiers

    • Research-article

    Conference

    ASIA CCS '17
    Sponsor:

    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

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)33
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 25 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media