Abstract
In the past three decades, an impressive body of knowledge has been built around secure and private password authentication. In particular, secure password-authenticated key exchange (PAKE) protocols require only minimal overhead over a classical Diffie-Hellman key exchange. PAKEs are also known to fulfill strong composable security guarantees that capture many password-specific concerns such as password correlations or password mistyping, to name only a few. However, to enjoy both round-optimality and strong security, applications of PAKE protocols must provide unique session and participant identifiers. If such identifiers are not readily available, they must be agreed upon at the cost of additional communication flows, a fact which has been met with incomprehension among practitioners, and which hindered the adoption of provably secure password authentication in practice.
In this work, we resolve this issue by proposing a new paradigm for truly password-only yet securely composable PAKE, called bare PAKE. We formally prove that two prominent PAKE protocols, namely CPace and EKE, can be cast as bare PAKEs and hence do not require pre-agreement of anything else than a password. Our bare PAKE modeling further allows to investigate a novel “reusability” property of PAKEs, i.e., whether \(n^2\) pairwise keys can be exchanged from only n messages, just as the Diffie-Hellman non-interactive key exchange can do in a public-key setting. As a side contribution, this add-on property of bare PAKEs leads us to observe that some previous PAKE constructions relied on unnecessarily strong, “reusable” building blocks. By showing that “non-reusable” tools suffice for standard PAKE, we open a new path towards round-optimal post-quantum secure password-authenticated key exchange.
J. Hesse—The author was supported by the Swiss National Science Foundation (SNSF) under the AMBIZIONE grant “Cryptographic Protocols for Human Authentication and the IoT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
The same problem appears in the BPR model for party identifiers, but not for session identifiers, which are protocol outputs rather than inputs.
- 3.
For a protocol realizing an ideal functionality that runs an independent session, with a globally unique session identifier, for a small set of parties, this means only that each of these participants must have a different party identifier. However, when analyzing protocols that realize multi-instance versions of ideal functionalities that may interact with an arbitrary number of honest participants, the uniqueness of party identifiers becomes a global requirement.
- 4.
This application appeared in [36], which give a BPR-model analysis of a solution assuming pseudorandomness of PAKE protocol messages. Note that S can limit guessing attempts by upper-bounding the number n of C’s instances it processes.
- 5.
In contrast to the standard notion of NIKE, where party identities are an input to the protocol, simplified NIKE has only public keys [24].
- 6.
Field \(\textsf{role}\) can be set to \(\bot \) if the protocol is symmetric.
- 7.
In [17] the PAKE functionality leaks if this case occures to the adversary, but our default notion omits that leakage since it is not present in the protocols we analyze.
- 8.
Either mark prevents \(\mathcal {A}\) from issuing another \(\textsf{TestPwd}\) query for the same session.
- 9.
\(\mathcal {F}_{\textsf{bPAKE}}\) rules allow the ideal-world adversary to set \( ssid \)’s at will when a session terminates, but each of our protocols implements \( ssid \) as a protocol transcript, and the global \( ssid \) uniqueness is assured by the entropy of protocol messages.
- 10.
See step (2) in \(\textsf{Passive}\textsf{NewKey}\) in Fig. 2, although it can be difficult to pattern-match the above with Fig. 2 because in this second \(\textsf{Passive}\textsf{NewKey}\) instances \(\mathcal {P}'_{ i '}\) and \(\mathcal {P}_{ i }\) play the opposite roles compared to the notation in that step in the figure.
- 11.
- 12.
If party \(\mathcal {P}_ i \) wants to use state \(st_i\) to process only n sessions then it can process only the first n session triples output by \(\mathcal {P}_ i \). This is equivalent to terminating a bPAKE instance, and one can extend \(\mathcal {F}_{\textsf{bPAKE}}\) to explicitly support such feature.
- 13.
This limits our analysis to two-pass protocols, which we do in this paper for the sake of simplicity. Our approach can be extended to protocols with additional rounds.
- 14.
We do not carry out a security analysis against quantum adversaries because it is not well understood, to the best of our knowledge, on how to deal with quantum adversaries in the ideal cipher model. Nevertheless, we note that the ideal cipher is only relevant when protecting against active attacks, which means that passive security (even with a posteriori password compromise) follows directly from the security of the underlying NIKE. This means that our protocol is suitable for applications that are concerned with preserving the confidentiality of data exchanged in the presence of passive attackers today, which may log the data and have access to a quantum computer in the future.
- 15.
In practice, \(\mathcal {S}\mathcal {K}\) will be the set of bit strings of fixed length \(\ell \) for some \(\ell \ge \kappa \). We consider the more general case to cover core protocols such as Diffie-Hellman, where keys are elements of a group with order at least \(2^\kappa \).
- 16.
The \(\mathcal {F}_ crs \)-hybrid model assumes that all parties have access to a functionality that publishes a common reference string (CRS) sampled from some distribution. In our work this CRS does not need to be programmed by the simulator, and hence this functionality can be global.
References
Abdalla, M., Barbosa, M., Bradley, T., Jarecki, S., Katz, J., Jiayu, X.: Universally composable relaxed password authenticated key exchange. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part I. LNCS, vol. 12170, pp. 278–307. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-56784-2_10
Abdalla, M., Haase, B., Hesse, J.: CPace, a balanced composable PAKE. IRTF CFRG draft (2020)
Abdalla, M., Haase, B., Hesse, J.: Security analysis of CPace. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part IV. LNCS, vol. 13093, pp. 711–741. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-92068-5_24
Abdalla, M., Pointcheval, D.: Simple password-based encrypted key exchange protocols. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 191–208. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30574-3_14
Barbosa, M., Boldyreva, A., Chen, S., Warinschi, B.: Provable security analysis of FIDO2. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part III. LNCS, vol. 12827, pp. 125–156. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-84252-9_5
Barbosa, M., Gellert, K., Hesse, J., Jarecki, S.: Bare Pake: universally composable key exchange from just passwords. Cryptology ePrint Archive, Paper 2024/234 (2024). https://eprint.iacr.org/2024/234
Beguinet, H., Chevalier, C., Pointcheval, D., Ricosset, T., Rossi, M.: Get a CAKE: generic transformations from key encaspulation mechanisms to password authenticated key exchanges. In: Tibouchi, M., Wang, X. (eds.) ACNS 2023, Part II. LNCS, vol. 13906, pp. 516–538. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33491-7_19
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_11
Bellovin, S.M., Merritt, M.: Encrypted key exchange: password-based protocols secure against dictionary attacks. In: 1992 IEEE Symposium on Security and Privacy, pp. 72–84. IEEE Computer Society Press (1992)
Bender, J., Fischlin, M., Kügler, D.: Security analysis of the PACE key-agreement protocol. In: Samarati, P., Yung, M., Martinelli, F., Ardagna, C.A. (eds.) ISC 2009. LNCS, vol. 5735, pp. 33–48. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04474-8_3
Bindel, N., Cremers, C., Zhao, M.: FIDO2, CTAP 2.1, and WebAuthn 2: Provable security and post-quantum instantiation. Cryptology ePrint Archive, Report 2022/1029 (2022). https://eprint.iacr.org/2022/1029
Bonneau, J., Herley, C., van Oorschot, P.C., Stajano, F.: The quest to replace passwords: a framework for comparative evaluation of web authentication schemes. In: 2012 IEEE Symposium on Security and Privacy, pp. 553–567. IEEE Computer Society Press, May 2012
Bradley, T., Jarecki, S., Xu, J.: Strong asymmetric PAKE based on trapdoor CKEM. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 798–825. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_26
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press (2001)
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: IEEE Symposium on Foundations of Computer Science – FOCS 2001, pp. 136–145. IEEE (2001)
Canetti, R.: SIDS in UC-secure PAKE and KE. IRTF CFRG mail archive (2019)
Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.: Universally composable password-based key exchange. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 404–421. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_24
Canetti, R., Rabin, T.: Universal composition with joint state. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_16
Cash, D., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 127–145. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_8
CFRG. CFRG PAKE selection. IRTF website (2020)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)
Dupont, P.-A., Hesse, J., Pointcheval, D., Reyzin, L., Yakoubov, S.: Fuzzy password-authenticated key exchange. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 393–424. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_13
Freire, E.S.V., Hofheinz, D., Kiltz, E., Paterson, K.G.: Non-interactive key exchange. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 254–271. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_17
Freire, E.S.V., Hofheinz, D., Kiltz, E., Paterson, K.G.: Non-interactive key exchange. Cryptology ePrint Archive, Report 2012/732 (2012). https://eprint.iacr.org/2012/732
Gajland, P., de Kock, B., Quaresma, M., Malavolta, G., Schwabe, P.: Swoosh: practical lattice-based non-interactive key exchange. Cryptology ePrint Archive, Report 2023/271 (2023). https://eprint.iacr.org/2023/271
Gentry, C., MacKenzie, P., Ramzan, Z.: A method for making password-based key exchange resilient to server compromise. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 142–159. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_9
Gu, Y., Jarecki, S., Krawczyk, H.: KHAPE: asymmetric PAKE from key-hiding key exchange. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part IV. LNCS, vol. 12828, pp. 701–730. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_24
Haase, B., Labrique, B.: Making password authenticated key exchange suitable for resource-constrained industrial control devices. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 346–364. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_17
Hao, F., Shahandashti, S.F.: The SPEKE protocol revisited. Cryptology ePrint Archive, Report 2014/585 (2014). https://eprint.iacr.org/2014/585
He, W., et al.: Rethinking access control and authentication for the home internet of things (IoT). In: 27th USENIX Security Symposium (USENIX Security 18), Baltimore, MD, August 2018, pp. 255–272. USENIX Association (2018)
Hesse, J.: Separating symmetric and asymmetric password-authenticated key exchange. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 579–599. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_29
Hesse, J., Jarecki, S., Krawczyk, H., Wood, C.: Password-authenticated TLS via OPAQUE and post-handshake authentication. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 98–127. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_4
Hwang, J.Y., Jarecki, S., Kwon, T., Lee, J., Shin, J.S., Xu, J.: Round-reduced modular construction of asymmetric password-authenticated key exchange. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 485–504. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_26
Jablon, D.P.: Extended password key exchange protocols immune to dictionary attacks. In: 6th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 1997), Cambridge, MA, USA, June 18–20, 1997, pp. 248–255. IEEE Computer Society (1997)
Jarecki, S., Krawczyk, H., Xu, J.: OPAQUE: an asymmetric PAKE protocol secure against pre-computation attacks. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 456–486. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_15
Kiefer, F., Manulis, M.: Oblivious PAKE: efficient handling of password trials. In: Lopez, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 191–208. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23318-5_11
Krawczyk, H.: SIGMA: the ‘SIGn-and-MAc’ approach to authenticated Diffie-Hellman and its use in the IKE protocols. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 400–425. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_24
Küsters, R., Tuengerthal, M.: Composition theorems without pre-established session identifiers. In: Chen, Y., Danezis, G., Shmatikov, V., (eds.) ACM CCS 2011, pp. 41–50. ACM Press (2011)
MacKenzie, P.: On the security of the SPEKE password-authenticated key exchange protocol. Cryptology ePrint Archive, Report 2001/057 (2001). https://eprint.iacr.org/2001/057
Pointcheval, D., Wang, G.: VTBPEKE: verifier-based two-basis password exponential key exchange. In: Karri, R., Sinanoglu, O., Sadeghi, A.-R., Yi, X. (eds.), ASIACCS 17, pp. 301–312. ACM Press (2017)
Santos, B.F.D., Yanqi, G., Jarecki, S.: Randomized half-ideal cipher on groups with applications to UC (a)PAKE. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 128–156. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30589-4_5
Santos, B.F.D., Gu, Y., Jarecki, S., Krawczyk, H.: Asymmetric PAKE with low computation and communication. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 127–156. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-07085-3_5
Shoup, V.: Security analysis of spake2+. Cryptology ePrint Archive, Paper 2020/313 (2020)
W3C. Web authentication working group (2017). https://www.w3.org/groups/wg/webauthn/
Wikpedia. Internet of things (2023). https://en.wikipedia.org/wiki/Internet_of_things/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Barbosa, M., Gellert, K., Hesse, J., Jarecki, S. (2024). Bare PAKE: Universally Composable Key Exchange from Just Passwords. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14921. Springer, Cham. https://doi.org/10.1007/978-3-031-68379-4_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-68379-4_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68378-7
Online ISBN: 978-3-031-68379-4
eBook Packages: Computer ScienceComputer Science (R0)
