Re: [Cfrg] PAKE review

[Hugo Krawczyk <[e-mail]>]

Björn, thanks for your truly amazing work here.
I added some notes below regarding the aPAKE protocols and the comparison
between OPAQUE and Strong AuCPace.

Hugo

On Tue, Oct 29, 2019 at 5:14 PM Bjoern Tackmann <[e-mail]>
wrote:

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


DH-OPRF requires the Gap-One-More-DH assumption so both OPAQUE and Strong
AuCPace need that too.

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.


Why a subset of users and a single user? Note that he OPRF key k is unique
per user. The setting where this may be relevant is with quantum computers
that can break dlog efficiently, and as I commented in another email,
OPAQUE seems better positioned in the sense of preparedness for the PQ (and
transition) era.

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


Deniability depends on the encryption function and the underlying
theoretical modeling. If you are willing to accept programmable RO (which
both OPAQUE and AUCPace need) then you get deniable encryption. Just derive
a random pad R and a HMAC key Km from rwd (using HKDF-Expand for example),
and define Env_u as the pair (e=p_u xor R, HMAC_Km(c)). This is deniable
assuming the underlying H is a programmable RO (e.g., using same H as  in
DH-OPRF) and is a perfectly practical implementation for OPAQUE. You can
also have an instantiation of OPAQUE with an envelope that does not use
encryption at all (it is described in the OPAQUE internet draft - version
03). Yet another way to bypass the deniability issue is to use
"non-information oracles" as in the treatment of adaptive UC-secure
channels in https://eprint.iacr.org/2002/059.

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


Note that AuCPace with Strong aPAKE security (i.e. security against
pre-computation attacks) incurs in additional computation due to the added
OPRF stage. Also, message size and server storage for OPAQUE can be made
much shorter with the non-encryption version of the envelope.


> Implementation. AUCPACE and BSPAKE need map_to_curve.
>

OPAQUE too.


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

I expect most applications to integrate the aPAKE with some existing
mechanism, at the very least, a mechanism that uses the key derived from
the aPAKE to protect communication (a standalone key exchange without an
application that uses the key is not too useful in general). Today TLS
would be the natural choice for such integration but there are other cases
(e.g. IKEv2/IPsec). The modular design of OPAQUE eases integration in these
cases too, in particular allowing to reuse the existing AKE mechanism (if
so desired). Yet another reason to integrate aPAKE with existing
(non-password-based) AKE protocols is the need to protect user account
information.


> 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 (though possibly less significant) Strong AuCPace requires an
additional (variable-base) exponentiation per party to achieve security
against pre-computation attacks.

Also, as argued in the security section above, the protocol structure of
> strong AUCPACE seems better suited for adaptive security.


The issue of adaptivity in the analysis of OPAQUE arises in two cases: (1)
equivocable encryption as mentioned above which is resolved under the same
programmable RO model assumed in OPAQUE (and AuCPace) and (2) the use of
DH-OPRF whose proof of security (emulating the UC-OPRF functionality) is
non-adaptive. The latter makes the analysis of Strong AuCPace   (that also
uses this DH-OPRF) non-adaptive too.

> Overall, ignoring application restrictions, my sympathies are just
> slightly tilted toward strong AUCPACE.


I like AuCPace too. But given the above remarks I fail to see its
advantages over OPAQUE (well, one is that the proof of AuCPace appears to
be simpler but once you move to the strong model for security against
pre-computation ayyacks things become more complicated).

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


> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>