[Cfrg] PAKE review

[Bjoern Tackmann <[e-mail]>]

Dear all,

please find my review of all candidates below.

Best,
Björn

============

Before providing my full report, I want to highlight that several parts of it depend heavily on the very insightfull reports that have been provided by independent reviewers. It was extremely valuable to me to have access to so many different perspectives.

tl;dr
As balanced scheme, CPACE seems best, with SPAKE2 coming in somewhat close second. As augmented scheme, I think that OPAQUE should be considered for its possible seamless integration with TLS. As a general aPAKE, I have a slight preference for the strong AUCPACE variant.

= Report

My report first deals with balanced schemes and then with augmented ones, each section is broadly structured in four areas: security, efficiency, implementation, protocol integration. Security is again subdivided into assumptions, properties, proof support.

== Balanced schemes

The following is under the assumption, which has been discussed on the CFRG list recently and seems plausible to me, that CPACE can be implemented without the additional session ID round.

Assumptions. SPAKE2 requires a group in which CDH holds as well as a hash function that is modeled as random oracle. It requires as a setup a pair of group elements M, N that are chosen at random with unknown dlog relationship. J-PAKE requires a group in which DDH holds, as well as a hash function, again modeled as random oracle. The proposed SPEKE variant does not seem to have a security proof, but its security would seem to be related to CDH and a hash function (most likely modeled again as random oracle) as well, in the elliptic curve case one also needs a good map_to_curve function. Finally, CPACE makes that same set of assumptions. The proof requires the random oracle to be programmable, which seems to be related to a stronger adaptive-security property proved for CPACE.

Properties. On a high level, the protocols (for SPEKE: are expected to) achieve largely similar security properties, although the security statement of especially SPAKE2 they are a bit harder to identify. (They include forward secrecy.) SPAKE2 is specific in that a single discrete log relationship is necessary for the security of all sessions, but then a good map_to_curve function as also required by SPEKE/CPACE can also be used to get a "good" pair.

Proof support. The security proofs are in different models, with important implications. CPACE uses the strictest model, in which the intuitive guarantee that weak passwords in one session do not affect the security of other session, as well as arbirtrary password distributions, are properly modeled. SPAKE2 uses an intermediate one, it formalizes multiple concurrent sessions but assumes uniformly distributed passwords (same distribution in all sessions) and the proved security bounds are trivial for realistic parameters. J-PAKE has the weakest model, in that it only considers an isolated user and again makes assumptions about password distribution. As noted before, the considered SPEKE variant does not have an accompanying proof.

Efficiency. CPACE and SPEKE are the most efficient proposals, followed by SPAKE2 which needs more exponentiations. J-PAKE is far less efficient than all other candidates, both in terms of computation and communication.

Implementation. SPAKE2 should be the most straightforward to inplement, J-PAKE has more protocol-inherent complexity but also depends purely on standard primitives. (Same for the Zp variant of SPEKE.) CPACE and the curve variant of SPEKE both depend on a map_to_curve implementation, which may not be as widely available at the moment.

Integration. The three more efficient protocols can likely be integrated nicely with TLS and IKEv2, whereas J-PAKE requires more rounds in IKEv2 and is not quite compatible with TLS.

Conclusion. While CPACE and SPEKE (over elliptic curves) are quite similar, it seems that SPEKE has almost no advantages over CPACE but CPACE has several advantages over SPEKE. (Such as a full security analysis.) Between SPAKE2 and J-PAKE, I see several advantages for SPAKE2 (efficiency, integration in protocols) and only one for J-PAKE (no setup); here I see SPAKE2 as preferable. The decision between CPACE and SPAKE2 is difficult: CPACE is more efficient in computation, does not need setup, and has better proof support, but in turn it requires map_to_curve which may not yet be as widely implemented. I personally would still opt for CPACE mainly for the setup of SPAKE2 and the better efficiency of CPACE, but one may weigh arguments differently.

Addendum. For CPACE, I suggest to include the entire transcript in the key derivation. For me to believe the (version of the) proof I read, this seemed necessary, although it is conceivable that one can argue that the malleability of Diffie-Hellman cannot be used by the attacker in non-trivial ways. This does require to keep some additional state in the computation, which is a burden on low-end embedded devices, so this is at least something for IETF to keep in mind and decide explicitly in the further process. I also found the observation (of Brian Warner) interesting that a slight variation of the CPACE protocol could make it fully symmetric, and thereby simplify integration in some use cases. I would also suggest to IETF to consider this in the following process.

== Augmented schemes

Assumptions. All augmented schemes depend on similar assumptions (CDH and hash function as random oracle). OPAQUE and AUCPACE require the random oracle to be programmable, but that seems to be related to the stronger security statements. VTBPEKE requires a pair U, V of points as setup, similarly to SPAKE2.

Properties. The major difference in properties seems to be whether schemes support security against precomputation, which is proved for OPAQUE and also claimed for BSPAKE. The "strong" variant of AUCPACE also achives this property, whereas standard AUCPACE and VTBPEKE do not. For OPAQUE and VTBPEKE, solving a single dlog attacks multiple sessions. It is important to differentiate here, though, between VTBPAKE where all protocol sessions globally are affected, whereas in the case of OPAQUE it only affects one subset of users at a time. Beyond that, OPAQUE has a very specific protocol structure in which the secret initial state of a standard AKE protocol is encrypted under a key oblivously derived from the password, and this state is sent to the client. This structure appears slightly detrimental to adaptive security (as the encryption is not deniable, which is also where the initial proof was problematic). This structure, on the other hand, makes the protocol flow nicely compatible with existing protocols.

Proof support. As in the case of the balanced schemes, the security analyses of the augmented schemes use different types of security models. OPAQUE and AUCPACE use the strong UC model. (The proof for AUCPACE has been updated and I am now reasonably convinced of its correctness. The authors of OPAQUE updated their paper as well after the first review round, I did not yet have time to fully check it but I will not hold this against the scheme.) VTBPEKE uses a game-based model. The numerical results are trivial for realistic parameters, and the definition assumes uniformly random passwords. (I have verified the VTBPEKE proof and it is correct.) There is no proof for BSPAKE.

Efficiency. OPAQUE and VTBPEKE require only three messages, whereas AUCPACE and BSPAKE require four. In terms of message sizes, OPAQUE is a bit less succinct than the other candidates, but the difference is not dramatic. (It still integrates well with protocols.)

Implementation. AUCPACE and BSPAKE need map_to_curve.

Integration. All candidates except for OPAQUE seem difficult to integrate with TLS, in particular the message pattern of AUCPACE and BSPAKE does not seem to fit well, and possibly require some out-of-band communication. For IKEv2, all candidates seem compatible, of course those with better round complexity seem preferable.

Conclusion. One main question for me related to augmented PAKEs is: which application scenarios does IETF aim for? If the goal is to retrofit existing protocols in the typical TLS scenario with improved security, then OPAQUE is the best option for its strong security and its compatible communication pattern. (In particular, TLS should use OPAQUE.) TLS and the likes aside, however, I see the "strong" version of AUCPACE as a strong contender: it is efficient in terms of computation and communication; the most significant drawback over OPAQUE appears to be the additional message. Also, as argued in the security section above, the protocol structure of strong AUCPACE seems better suited for adaptive security. Overall, ignoring application restrictions, my sympathies are just slightly tilted toward strong AUCPACE. In my view, VTBPEKE (requires setup, no precomputation security) and BSPAKE (lack of proper security analysis) should not be considered on the same level.

Addendum. The support for OPAQUE is under the condition that the recently submitted proof is correct, which I am willing to assume for now but it should be further validated in the standardization process.