Abstract
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. has briefly noticed this issue, we present the first comprehensive study of correctness in UC PAKE:
-
1.
We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE;
-
2.
We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable;
-
3.
We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible;
-
4.
Finally, we show how to naturally incorporate correctness by changing the model—we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party.
In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The cases of [17, 25] are especially problematic, since their (asymmetric) PAKE protocols use a UC-secure authenticated key exchange (AKE) protocol as a building block, and their modelings of UC AKE also do not guarantee correctness. Therefore, a proof of PAKE correctness would need a separate correctness notion for AKE: roughly, that there exists an efficient algorithm \(\textsf{Gen}\) such that if we run it twice and obtain two key pairs (pk, sk) and \((pk',sk')\), then two AKE parties with inputs \((pk,pk',sk)\) and \((pk',pk,sk')\) should output the same key (assuming there is no adversarial interference). Such structural requirement is not mentioned in any of the aforementioned works (and in particular, the \(\mathsf {Key.Gen}\) algorithm in [25, Fig. 6] is undefined; a similar problem appears in [20]). The exact requirement of AKE correctness used in [17, 20, 25] is out of the scope of this work.
- 2.
The \(\textsf{role}\) field might be necessary for the description of the protocol when the algorithms of the two parties are not identical (especially when one party must wait for the other party’s message before starting its own session; see [10, Figure 5] for an example), but it has nothing to do with the security of the protocol.
- 3.
The functionality in Fig. 2 lets the ideal adversary \(\mathcal {S}\) learn whether its password guess is correct or not. This is necessary for the simulation of some PAKE protocols but not for others. The variant where \(\mathcal {S}\) does not learn this information is called implicitly-only PAKE; see [14] for further discussion. We follow the standard PAKE functionality, but note that all theorems below apply to implicitly-only PAKE as well.
- 4.
We can assume w.l.o.g. that \(\mathcal {Z}\) never reuses a session id, i.e., it never sends \((\textsf{NewSession}, sid, \textsf{P}, \cdot , \cdot , \cdot )\) to \(\textsf{P}\) twice (otherwise the second message will be ignored in both the real world and the ideal world).
- 5.
The purpose of considering \(\textsf{NoOutput}\) is to rule out the “empty” protocol mentioned in Sect. 1, where \(\textsf{P}\) and \(\textsf{P}'\) simply don’t do anything (and \(\mathcal {S}\) also doesn’t do anything). Although our primary focus is to rule out protocols like TrivialPAKE, with the requirement on \(\textsf{NoOutput}\) in place and with how we define correctness (Definition 4), we can formally rule out the “empty” protocol as well.
- 6.
More precisely, assume w.l.o.g. that \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\) first and \((\textsf{NewKey}, sid, \textsf{P}', \cdot )\) next. Then when \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\), \(\mathcal {F}_{\text {PAKE}}\) enters the third case, so \(\textsf{P}\) receives and outputs (sid, K) for \(K \leftarrow \{0,1\}^\lambda \); when \(\mathcal {S}\) sends \((\textsf{NewKey}, sid, \textsf{P}, \cdot )\), \(\mathcal {F}_{\text {PAKE}}\) enters the second case, so \(\textsf{P}\) receives and outputs \((sid, K')\) for \(K':=K\).
- 7.
This is w.l.o.g. because any environment \(\mathcal {Z}\) can be converted into another environment \(\mathcal {Z}'\) that behaves exactly like \(\mathcal {Z}\), except that \(\mathcal {Z}'\) additionally sends \((\textsf{Modify}, sid)\) when \(\mathcal {Z}\) instructs the adversary to modify a protocol message for the first time in session sid. Obviously the distinguishing advantages of \(\mathcal {Z}\) and \(\mathcal {Z}'\) are equal.
- 8.
In fact \(\mathcal {Z}'\) does not need to output anything, since we rely on the fact that \(\Pr [\textsf{SpuriousGuess}(\mathcal {S},\mathcal {Z}')]\) is negligible, rather than the distinguishing advantage of \(\mathcal {Z}'\) is negligible; whether \(\textsf{SpuriousGuess}(\mathcal {S},\mathcal {Z}')\) happens or not is already determined before \(\mathcal {Z}'\) finally outputs a bit.
- 9.
Formally, r is a random variable depending on the random tape of \(\mathcal {Z}\), and all probabilities below are also taken over the random tape of \(\mathcal {Z}\).
- 10.
\(0^\lambda \) can be replaced by any string in \(\{0,1\}^\lambda \).
- 11.
This can be viewed as a priority system. In programs of this form, we assign the action y a lower priority than sending m to \(\textsf{X}\), all processing done by \(\textsf{X}\), all messages sent by \(\textsf{X}\) as a result, and so on.
- 12.
Technically, \(\textsf{Output}\) must be sent by every honest party. Additionally, it must be sent some polynomial number of times, not just once, to allow protocols with multiple rounds. See [21] for details.
References
Abdalla, M., Barbosa, M., Bradley, T., Jarecki, S., Katz, J., Xu, J.: Universally composable relaxed password authenticated key exchange. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12170, pp. 278–307. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_10
Abdalla, M., Haase, B., Hesse, J.: Security analysis of CPace. In: ASIACRYPT 2021, Part IV, Dec. (2021)
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
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, May (1992)
Bellovin, S.M., Merritt, M.: Augmented encrypted key exchange: a password-based protocol secure against dictionary attacks and password file compromise. In: ACM CCS 93, Nov. (1993)
Boyko, V., MacKenzie, P., Patel, S.: Provably secure password-authenticated key exchange using diffie-hellman. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 156–171. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_12
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, Oct. (2001)
Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_2
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., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-party computation without set-up assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_5
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, May (2002)
Crypto Forum Research Group. PAKE selection (2020). https://github.com/cfrg/pake-selection
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. LNCS, vol. 10822, pp. 393–424. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78372-7_13
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
Groce, A., Katz, J.: A new framework for efficient password-based authenticated key exchange. In: ACM CCS 2010, Oct. (2010)
Gu, Y., Jarecki, S., Krawczyk, H.: KHAPE: asymmetric PAKE from key-hiding key exchange. In: CRYPTO 2021, Part IV, Aug. (2021)
Haase, B., Labrique, B.: AuCPace: efficient verifier-based PAKE protocol tailored for the IIoT. Cryptology ePrint Archive, Report 2018/286, (2018). https://eprint.iacr.org/2018/286
Hesse, J.: Separating symmetric and asymmetric password-authenticated key exchange. In: SCN 20, Sept. (2020)
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
Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_27
Katz, J., Ostrovsky, R., Yung, M.: Efficient password-authenticated key exchange using human-memorable passwords. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 475–494. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_29
Katz, J., Vaikuntanathan, V.: Smooth projective hashing and password-based authenticated key exchange from lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 636–652. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_37
McQuoid, I., Rosulek, M., Roy, L.: Minimal symmetric PAKE and 1-out-of-N OT from programmable-once public functions. In: ACM CCS 2020, Nov. (2020)
Santos, B.F.D., Gu, Y., Jarecki, S., Krawczyk, H.: Asymmetric PAKE with low computation and communication. In: EUROCRYPT 2022, Part II, May/June (2022)
Smyshlyaev, S.V.: Results of the PAKE selection process (2020). https://mailarchive.ietf.org/arch/msg/cfrg/LKbwodpa5yXo6VuNDU66vt_Aca8
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Roy, L., Xu, J. (2023). A Universally Composable PAKE with Zero Communication Cost. In: Boldyreva, A., Kolesnikov, V. (eds) Public-Key Cryptography – PKC 2023. PKC 2023. Lecture Notes in Computer Science, vol 13940. Springer, Cham. https://doi.org/10.1007/978-3-031-31368-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-031-31368-4_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-31367-7
Online ISBN: 978-3-031-31368-4
eBook Packages: Computer ScienceComputer Science (R0)