Subject: [Cfrg] Review of the PAKE proposals

From: Yoav Nir <[email-masked]>
Date: Thu, 12 Sep 2019 00:05:02 +0300

Hi.

At Stanislav’s request, I have reviewed the PAKE proposals for suitability within the IKE protocol.  I have concentrated only on the requirements that are unique to IKE. There are, of course, other considerations that apply to IKE, such as code size, memory footprint, performance and such, but those apply to any protocol just as much. I have not included them in my review.

The tl;dr version is that IMO all the PAKEs can work with IKE, some with a little more “bending” of the IKE protocol than others.  So with that said, my review is below.

Yoav

Suitability of PAKE algorithms for IKE

IKEv2 (RFC7296) is a protocol for negotiating encryption keys and authenticating peers. The actual traffic goes over a different protocol called IPsec (RFC4301, RFC4302, RFC4303).

Most commonly, IKEv2 uses the UDP protocol, although variations exist that run over TCP (RFC8229) as well as support for running over UDP with IKE-level fragmentation to accommodate large payloads (RFC7383). Still, IKE has a hard limit of 64KB per message and to avoid the need for exotic transport extension it is preferred to keep the messages under 1500 bytes.

IKE is typically used in three scenarios:
site-to-site, where two gateway routers encrypt traffic between hosts that are behind them.
host-to-host, where two hosts encrypt traffic between them.
remote-access or "road warrior" where a host connects to a remote access gateway and encrypts traffic to hosts in the network behind the gateway. In this case the authenticated entity for the host in usually a user rather than a machine.
The first two scenarios are symmetrical. Either side may initiate the exchange. The third is inherently asymmetrical -- the host always connects to the gateway, never the other way around.  This means that an augmented PAKE is not suitable for the first two scenarios but may be suitable for remote-access, while a balanced PAKE may be suitable for all three.

Setting up an IPsec tunnel involves one IKE_SA_INIT exchange and one or more IKE_AUTH exchanges.

The IKE_SA_INIT exchange is used to negotiate encryption parameters, authentication methods, and to perform a Diffie-Hellman key exchange. The results are used to compute encryption keys for use in the IKE_AUTH exchanges. 

The identities of both the Initiator and the Responder are passed in the encrypted IKE_AUTH exchanges, so identities are protected against passive attackers. This property is considered important in IKE, so when considering how to integrate a PAKE into the IKEv2 protocol, I assume that we must retain this property. AFAICT this means that the PAKE cannot start until the first IKE_AUTH exchange, but parameter negotiation as well as negotiating the use of a PAKE can be done in the IKE_SA_INIT exchange.

IKE authentication with either certificates or with PSKs can be accomplished with a single IKE_AUTH exchange. The protocol diagram looks like the following:

   Initiator                         Responder
   -------------------------------------------------------------------
   HDR, SK {IDi, [CERT,] [CERTREQ,]
       [IDr,] AUTH, SAi2,
       TSi, TSr}  -->
                                <--  HDR, SK {IDr, [CERT,] AUTH,
                                         SAr2, TSi, TSr}
                                         
Every PAKE in this evaluation uses 4 messages, or two round-trips. This means that they can't be fitted into this single IKE_AUTH exchange. Fortunately, IKEv2 already has a provision for multiple IKE_AUTH exchanges, which is currently used for integrating IKE with EAP for user authentication.  The protocol diagram looks like this:

   Initiator                         Responder
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr, [CERTREQ]
   HDR, SK {IDi, [CERTREQ,]
       [IDr,] SAi2,
       TSi, TSr}  -->
                                <--  HDR, SK {IDr, [CERT,] AUTH,
                                         EAP}
   HDR, SK {EAP}  -->
                                <--  HDR, SK {EAP (success)}
   HDR, SK {AUTH}  -->
                                <--  HDR, SK {AUTH, SAr2, TSi, TSr}
                                
The SA*2, TSi and TSr payloads are related to the traffic keys that the IKE protocol is generating for IPsec. The Responder returns them only after the authentication is complete. The AUTH payloads are a digital signature when authenticating with a certificate or a PRF when authenticating with a shared secret. The later AUTH payloads when using EAP are authenticated with the MSK for key-generating EAP methods, and derivatives of the IKE SA key material for non-key-generating methods.

The PAKEs in this evaluation typically have one round trip for the key exchange, and then another for key confirmation.  The key confirmation serves the same purpose as the AUTH payload in IKEv2. It therefore makes sense that the key confirmation would be embedded as a new format of AUTH payload, while the key exchange will be embedded as an entirely new payloads, which I will mark as PAKE:

   Initiator                         Responder
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr,
   HDR, SK {IDi, PAKE
       [IDr,] SAi2,
       TSi, TSr}  -->
                                <--  HDR, SK {IDr, [CERT,] AUTH, PAKE}
   HDR, SK {AUTH}  -->
                                <--  HDR, SK {AUTH, SAr2, TSi, TSr}
                        
So what could make any PAKE candidate unsuitable for IKE?
It could require messages that are too long. Looking at the various PAKE candidates, all seem to have a compact enough encoding that message size does not matter. They are actually quite small when compared to common certificates, so that part is not something we should be concerned about
It could require significant computation power. All the methods require asymmetric operations, but these are no more onerous than certificate verification. The performance consideration is also not in any way unique to IKE, so it does not make much of a difference for this review.
It could require a particular order of initiation. This disqualifies the augmented PAKEs for the site-to-site and the host-to-host scenarios. For the remote-access scenario I would prefer to have an augmented PAKE, because users tend to reuse passwords and all servers should be protected from password database leaks.
  
So I believe an augmented PAKE is suitable for the remote-access scenario, and a balanced PAKE is suitable for the others. Negotiating the use of the PAKE and any parameters within is pretty straightforward in IKE and can be done within the IKE_SA_INIT exchange in the usual manner (initiator proposes >=1 options; responder picks 1)

So now to consider the specific proposed balanced PAKEs.

SPAKE2 / SPAKE2+
The PAKE payloads would transmit T and S. Their size are those of a group element.
The latter AUTH payload should, according to RFC7296, be a PRF using the shared key of an IKE transcript. We could use either KcA/KcB as the shared keys to calculate AUTH, or use the two F function results. To avoid modifying the PAKE, I believe it would be better to use the F values as the shared keys used in AUTH. Since the F values can be computed independently by the two parties, it is enough to use a derivative value, no need to send them explicitly.
This proposal fits well within IKEv2 and finishes tunnel setup in 3 round-trips.

J-Pake (I considered the two-round variant)
This too is two-round. However, the PAKE payloads would be significantly larger, including two group elements in the PAKE payloads plus the knowledge proofs. 
The second round also includes an element and knowledge proofs. You can't calculate the shared key K until after you see the messages of the second round. This means that the AUTH payloads (using K as shared key) are delayed until a third IKE_AUTh exchange.
This proposal is suitable for IKEv2, but takes 4 round-trips to set up a tunnel.

SPEKE
This, much like SPAKE2, sends a single group element in the PAKE payloads. A single K value is then used to MAC the AUTH payloads.
This proposal fits well within IKEv2 and finishes tunnel setup in 3 round-trips.

CPace
As far as I understand, this is a variation of SPEKE, and although it's much more complicated, using extra functions such as TBPEKE or Map2Curve, the number and size of messages is unchanged.

Some of the augmented PAKEs have a password registration step. This step does not fit well in IKEv2, in that IKE_SA_INIT is used only to generate keys for IKE, and IKE_AUTH is used to authenticate. Nothing else is ever done without authentication. A setup phase would be required to be done before authentication.

It makes sense for a real authentication to follow the registration, just to prove that it is possible. We can have registration use the same payload type as the other PAKE payloads, but for the sake of clarity, I will use the notation REG for the payloads containing the registration payload. 

So assuming that registration takes two round-trips (as it does in OPAQUE), and actual authentication takes 3 round trips (again, as it does in OPAQUE), a tunnel setup with registration would look like this:

   User                              Server
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr,
   HDR, SK {IDi, REG
       [IDr,] SAi2,
       TSi, TSr}  -->
                                <--  HDR, SK {IDr, [CERT,] AUTH, REG}
   HDR, SK {REG}  -->
                                <--  HDR, SK {REG, PAKE}
   HDR, SK {PAKE}  -->
                                <--  HDR, SK {PAKE}
   HDR, SK {PAKE}  -->
                                <--  HDR, SK {PAKE}
   HDR, SK {AUTH}  -->
                                <--  HDR, SK {AUTH, SAr2, TSi, TSr}

Note that OPQAUE starts with the user only transmitting the user/account name, which is contained in IDi. I piggybacked the server's first PAKE message on the message with the final REG message. A tunnel setup without registration would look like this:

   User                              Server
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr,
   HDR, SK {IDi,
       [IDr,] SAi2,
       TSi, TSr}  -->
                                <--  HDR, SK {IDr, [CERT,] AUTH, PAKE}
   HDR, SK {PAKE}  -->
                                <--  HDR, SK {PAKE}
   HDR, SK {PAKE}  -->
                                <--  HDR, SK {PAKE}
   HDR, SK {AUTH}  -->
                                <--  HDR, SK {AUTH, SAr2, TSi, TSr}
                                
So now a comparison of the proposed augmented PAKEs:

OPAQUE
OPAQUE spends one round-trip on sending IDi and receiving EnvU and vU.
OPAQUE spends another round-trip on the OPRF protocol.
OPAQUE spends yet another round-trip for a KE exchange.
The final IKE_AUTH message uses the generated key for the AUTH payloads.
Altogether 5 round-trips (or IKE_AUTH exchanges) are needed for user authentication.

VTBPEKE
VTBPEKE utilizes a balanced variant of SPEKE called TBPEKE. TBPEKE is a 1 round-trip protocol, just like SPEKE.
Before that round-trip, the client needs the salt for password hashing, so that's another round-trip. The proposal allows using a common salt for all users, so we could slightly abuse the protocol by sending this salt in the IKE_SA_INIT response. 
A final round is required for the AUTH payloads and the server response to SAr2, TSi, and TSr.
All told, 4 or 3 round-trips for the tunnel setup. VTBPEKE does not include a registration step.

BSPAKE
BSPAKE is a variation of SPAKE that includes hashing and salt for the user password.
It requires two round-trips for the protocol.
We can save a round-trip by considering VerifierC and VerifierS as the keys for the AUTH payloads rather than sending them within the protocol. This allows us to use the same round-trip for the second round of BSPAKE and the AUTH payloads.
This means that BSPAKE can set up a tunnel in 3 round-trips.

AuCPace
AuCPace as depicted in figure 4 of the paper requires 4 round-trips. It fits well with the framework (and it does have a registration phase). Adding the IKE_SA_INIT and the final IKE_AUTH AuCPace requires 6 round-trips. We can save one by piggy-backing the ssid agreement in the IKE_SA_INIT, which brings us down to 5 round-trips.

In summary, for the purposes of IKEv2 the different proposals all fit the mold, some with a minor abuse of the IKEv2 protocol. They are different in the number of round trips, which leads me to prefer SPAKE and BSPAKE, but none of the others is disqualified.

The proposals differ, of course, in performance and in complexity of implementation, but none of that is different for IKEv2 as compared with other protocols.

If we are to use PAKEs for IKEv2, we definitely need a balanced PAKE. In my opinion it is better to also have an augmented PAKE for the remote access scenario.

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 11 Sep 2019 21:30:42 -0400

Hi Yoav and Valery,

thanks for your extensive analysis of the different PAKE candidates.
I would like to clarify some issues regarding the way you
envision the integration of OPAQUE in the context of IKEv2.

Let me first refer to Yoav's analysis
https://mailarchive.ietf.org/arch/msg/cfrg/PWhIOQKBHapZ1Rpbd7Brr_JFIg8
where he says:

> The final IKE_AUTH flow uses the generated key for the AUTH payloads.

This mimics the modular description in the OPAQUE draft that shows the
different
logical components. However, these components need not be run sequentially
but
rather in parallel, namely, piggybacking the OPRF to any existing AKE
protocol.
This is exemplified in the OPAQUE draft for any AKE with 3 flows as follows:

   Generic OPAQUE with 3-message KE:

   o  C to S: Uid, alpha=H'(PwdU)*g^r, KE1

   o  S to C: beta=alpha^kU, vU, EnvU, KE2

   o  C to S: KE3

Thus, one can integrate OPAQUE with IKEv2 at the cost of a single additional
message from C to S, and no change to the AUTH mechanics.

Here is how it would look (I keep Yoav's notation and add the OPAQUE
elements in
< ... >). The only changes to regular IKEv2 are piggybacking the elements
alpha, beta, vU, EnvU to the existing IKEv2 flows and adding the last
client-to-server flow with the AUTH value.

   User                              Server
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr,
   HDR, SK {IDi,
       [IDr,] SAi2,
       TSi, TSr
       <alpha>}     -->
                                <--  HDR, SK {IDr, AUTH, <beta, vU, EnvU>}
   HDR, AUTH       -->

Server's AUTH needs no change, except that the signature is computed with
the server's key authenticated under EnvU, and client's AUTH in the added
flow is computed under the user's key under EnvU.

The first two flows don't change (except maybe for a HDR type indicating
password authentication). The value IDi is used to transfer user's account
information (whose privacy is protected against passive adversaries by
virtue of
the DH exchange (KEi, KEr)).

As you can see, my depiction above is quite similar to the way Valery
Smyslov
https://datatracker.ietf.org/doc/html/draft-smyslov-ikev2-pake
integrates OPAQUE with IKEv2, with two notable differences.
Valery's version (top of page 10 in the draft) takes three round trips
(instead
of 2.5) as he delays the server's AUTH to an additional sixth flow. In
contrast, I include this information in the fourth flow.
More significantly, Valery re-defines the AUTH values as
               AUTHi = sig(PrivU, <InitiatorSignedOctets>)
               AUTHr = sig(PrivS, <ResponderSignedOctets>)
This is not necessary. One can keep IKEv2's AUTH unchanged (as I said, only
the
public keys change from certificate-based to EnvU-based). Actually, defining
AUTH i/r as above would not be secure (it departs from the necessary logic
of
SIGMA-R underlying IKEv2).

Finally, responding to one of the points of Yoav, the password registration
procedure only takes 3 flows (C to S, S to C, C to S).

The common point to the above comments is that integrating OPAQUE into an
existing protocol should be quite painless. You just need to piggyback the
two
OPRF messages and EnvU to the existing key exchange flows. Assuming
extensibility of the protocol to accommodate the above elements, the cost
would
be at most one additional flow for user's explicit authentication.
Computation-wise it's just one exponentiation for the server and two for the
client (with one or both of these exponentiations using a fixed base), plus
a
hash into the curve by the client.

Let me know if the above makes sense to you and whether I missed something
significant about the way IKEv2 works.

Thanks again!

Hugo

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 12 Sep 2019 09:56:58 +0300

HI Hugo,

Hi Yoav and Valery, 

> Altogether 5 round-trips (or IKE_AUTH exchanges) are needed for user

This mimics the modular description in the OPAQUE draft that shows the different
logical components. However, these components need not be run sequentially but
rather in parallel, namely, piggybacking the OPRF to any existing AKE protocol.
This is exemplified in the OPAQUE draft for any AKE with 3 flows as follows:

   o  C to S: KE3

Here is how it would look (I keep Yoav's notation and add the OPAQUE elements in
< ... >). The only changes to regular IKEv2 are piggybacking the elements
alpha, beta, vU, EnvU to the existing IKEv2 flows and adding the last
client-to-server flow with the AUTH value.

   User                              Server

The first two flows don't change (except maybe for a HDR type indicating
password authentication). The value IDi is used to transfer user's account
information (whose privacy is protected against passive adversaries by virtue of
the DH exchange (KEi, KEr)).

As you can see, my depiction above is quite similar to the way Valery Smyslov
https://datatracker.ietf.org/doc/html/draft-smyslov-ikev2-pake
integrates OPAQUE with IKEv2, with two notable differences. 
Valery's version (top of page 10 in the draft) takes three round trips (instead
of 2.5) as he delays the server's AUTH to an additional sixth flow. 

          I did this for the purpose. IKEv2 is a strict request-response protocol,

          so that initiator sends a request message and responder

          sends a response. It is the initiator who is responsible for 

          any retransmission in case request or response get lost.

         This is a core principle of IKEv2 and for this reason non-integer

         RTTs are non-applicable for IKEv2. In your example the proper sequence 

         would be:

   User                              Server

                                <--  HDR, SK{}

      which, in my opinion, is no better than my proposal,

       because it also changes the order AUTH payloads are

       computed by initiator and responder (I prefer the 

       initiator authenticates itself first to decrease possible DoS attacks surface).

In contrast, I include this information in the fourth flow.
More significantly, Valery re-defines the AUTH values as 
               AUTHi = sig(PrivU, <InitiatorSignedOctets>)
               AUTHr = sig(PrivS, <ResponderSignedOctets>)
This is not necessary. One can keep IKEv2's AUTH unchanged (as I said, only the
public keys change from certificate-based to EnvU-based). Actually, defining
AUTH i/r as above would not be secure (it departs from the necessary logic of
SIGMA-R underlying IKEv2).

          Here I’m confused. Actually, the above AUTH payload calculation

          is exactly as it is done in IKEv2 (or in SIGMA) with the assumption

          that once the OPAQUE is complete each peer can use its private

          key Priv[U|S] for signing. I believed I didn’t change AUTH calculation 

          in case of OPAQUE at all. From RFC7296, Section 2.15:

2.15.  Authentication of the IKE SA

   When not using extensible authentication (see Section 2.16), the

   peers are authenticated by having each sign (or MAC using a padded

   shared secret as the key, as described later in this section) a block

   of data.

     Later in this section this block of data is depicted as InitiatorSignedOctets

          for initiator and as ResponderSignedOctets for responder.

          So, I failed to understand where I changed the way AUTH payload

          is calculated for the OPAQUE. Am I missing something?

          Thank you,

          Valery.

The common point to the above comments is that integrating OPAQUE into an
existing protocol should be quite painless. You just need to piggyback the two
OPRF messages and EnvU to the existing key exchange flows. Assuming
extensibility of the protocol to accommodate the above elements, the cost would
be at most one additional flow for user's explicit authentication.
Computation-wise it's just one exponentiation for the server and two for the
client (with one or both of these exponentiations using a fixed base), plus a
hash into the curve by the client.

Thanks again!

Hugo

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 12 Sep 2019 10:56:29 -0400

Hi Valery,

Thanks for the clarifications.

If IKEv2 requires full rounds Initiator-Responder then one needs to add one
round trip to the original IKEv2 as you propose. I am ok with AUTH in the
last flow.
Finally, regarding the definition of AUTH, I now see that the signed
stream <InitiatorSignedOctets>
is defined to include the nonce and prf(SK_pi, IDi') - and similarly for
the responder, so this is indeed *exactly* how IKEv2 works. This shows the
advantage of the modular composition: you get security directly by the
(already analyzed) security of the underlying AKE protocol, in this case
IKEv2 (no need to re-analyze). In case of OPAQUE you also get security
against pre-computation attacks.

The added cost in the case of IKEv2 (due to the OPRF computation)  is one
additional round, a single exponentiation for the server  and two for the
client (with one or both of these exponentiations using a fixed base), plus
a hash into the curve for the client.  There is also the hardening on the
client side (iterated hashing, Argon2, scrypt, etc.) against offline
attacks at the server and online attacks at the client (hardening should be
mandatory for all proposals).

 Thanks again Valery.

Hugo

---

From: Yoav Nir <[email-masked]>
Date: Sun, 15 Sep 2019 22:55:02 +0300

> On 12 Sep 2019, at 4:30, Hugo Krawczyk <[email-masked]> wrote:
> 
> Hi Yoav and Valery, 
> 
> https://mailarchive.ietf.org/arch/msg/cfrg/PWhIOQKBHapZ1Rpbd7Brr_JFIg8 <https://mailarchive.ietf.org/arch/msg/cfrg/PWhIOQKBHapZ1Rpbd7Brr_JFIg8>
> where he says:
> 

Thanks, Hugo.  That makes sense.

It also strengthens the conclusion from both Valery and myself that all the proposed PAKEs will work well enough with IKEv2, so that compatibility with IKEv2 should not be a consideration when picking 1 or 2 PAKEs.

Yoav

---

From: Karthik Bhargavan <[email-masked]>
Date: Mon, 16 Sep 2019 11:30:37 +0200

Hello All,

Bruno Blanchet and I did a quick (and admittedly incomplete) review of the Balanced PAKE proposals, primarily from the angle of whether they could be easily incorporated into 
the design (and proofs) of TLS 1.3. Some of our observations may carry over to the Augmented PAKEs, but we did not look at those too deeply.

SPEKE
======

The proposed variant of SPEKE belongs to a long line of well-studied protocols.
The specific protocol proposed here is the one by Hao and Shahandashti [1]
This version does not appear to have a proof. In fact, there appears to be an attack on the design as proposed (more below).

We note that in the questionnaire, the authors refer to the proof of SPEKE in [2] but that is for a different protocol.
Moreover, the authors of [1] criticize the proof of [2] as inadequate, so it is unclear why the proof of [2] should apply to [1] in the first place.

The proposed protocol in [1] is written as follows:

A -> B:  A, M = g^x
B -> A:  B, N = g^y

A computes: H (min(A, B), max(A, B), min(M, N), max(M, N), N^x)
B computes: H (min(A, B), max(A, B), min(M, N), max(M, N), M^y)

This can be followed by an optional key confirmation phase but the security of the protocol
is claimed not to depend upon it (“key confirmation can remain as “optional” as it is in the current standards.” [1, Section 5.3])

Bruno observes that the above protocol has a reflection-style attack where A can be fooled into thinking
it has a session with B although it only has a session with itself.
Suppose A is willing to act as Initiator and Recipient in different sessions.
Now consider a network (man-in-the-middle) attacker I between A and B.

Session 1:			Session 2:
A -> I:  A, M = g^x   		I -> A: B, M = g^x
					A -> I: A, N = g^y
I -> A: B, N = g^y

A computes  H (min(A, B), max(A, B), min(M, N), max(M, N), N^x)
A thinks it has completed session 1 with an authenticated B, but
in fact it has only completed a session with itself.
In fact, since the two sessions will end up with the same key, although I does not know this key.
messages encrypted under the shared key can be forwarded from one session to another.

The main flaw here appears to be the independent use of min/max(A,B) and min/max(M,N)
A fix would be to do the min/max computation once:
e.g. let ab = min(A,B)
       let AB = max(A,B)
       if ab = A then 
	  let mn = M
	  let MN = N
       else
	  let mn = N
	  let MN = M
       A computes H(ab,AB,mn,MN,N^x)
       B computed H(ab,AB,mn,MN,M^y)

Still, we have not proved the security of the protocol after this fix, but it prevents the reflection attack described above.

[1] https://eprint.iacr.org/2014/585.pdf <https://eprint.iacr.org/2014/585.pdf>
[2] https://eprint.iacr.org/2001/057.pdf <https://eprint.iacr.org/2001/057.pdf>

CPace
======

CPace can be considered a variant of SPEKE and the proposal includes a full security proof in the Universal Composability (UC) framework [3].
We did not check the proof in detail but have no reason to believe it is flawed. 

Unfortunately, features of the proof appear to leak into the protocol design which make it difficult to understand how the concrete protocol will be deployed.
The protocol in Figure 4 includes a first round to establish a session identifier, making CPace into a 2 round protocol.
If this first round is included, then CPace would not be suitable for TLS 1.3, so understanding its need is essential.

The assumptions on this identifier are unclear to us: is it just a proof artefact? does removing it introduce a concrete attack?
The authors say "Hashing CI into G allows us to fend off certain types of relay attacks”. What are these attacks? Are they practical? 
The authors also say that "In the context of TCP/IP, the CI might be constructed by concatenating unique representations of the server’s and client’s IP address and TCP port numbers.”

This seems to indicate that uniqueness across CPace sessions is the only property desired for the CI. Is this the case?
The proof appears to rely on the ssid being derived from fresh random values “s” and “t” generated by both parties, and TCP/IP addresses are definitely not fresh random values in practice.
Would the proof still work if you used local counters for s and t? 
Also, how would the authors envision this would work with other transport protocols like Quic or raw UDP?

Also: CPace does not specify key confirmation and it would be an important aspect to flesh out if the protocol were to be integrated into TLS.

[3] https://eprint.iacr.org/2018/286 <https://eprint.iacr.org/2018/286>

J-PAKE
======

J-PAKE as standardized in RFC8236 describes a 3-message protocol that requires 6 exponentiations (scalar multiplications) and 6 zero-knowledge proofs.
Consequently, this protocol is significantly heavier in computational and implementation complexity than the other proposals. 
We wonder whether it would not be better to consider more efficient variants of J-PAKE, as proposed in [7], for example.

The submission cites proofs in 3 papers [4,5,6]. Of these, the first 2 contain proofs in a non-standard model of key exchange and are not easy to compare with proofs for other PAKE protocols.
[6] presents a proof of J-PAKE in a standard AKE setting but observes that the use of Schnorr proofs in J-PAKE requires the use of a stronger algebraic adversary model.
The use of stronger SE-NIZK proofs would have avoided the algebraic assumption and allowed J-PAKE to be proved secure under the weaker Decision Square Diffie-Hellman (DSDH) assumption.

The J-PAKE RFC suggests two key confirmation methods. The second of these is quite compatible with the TLS Finished messages.

[4] https://www.dcs.warwick.ac.uk/~fenghao/files/pw.pdf <https://www.dcs.warwick.ac.uk/~fenghao/files/pw.pdf>
[5] https://eprint.iacr.org/2010/190.pdf <https://eprint.iacr.org/2010/190.pdf>
[6] https://www.normalesup.org/~fbenhamo/files/publications/SP_AbdBenMac15.pdf <https://www.normalesup.org/~fbenhamo/files/publications/SP_AbdBenMac15.pdf>
[7] https://eprint.iacr.org/2016/379.pdf <https://eprint.iacr.org/2016/379.pdf>

SPAKE2
======

SPAKE2 belongs to a third class of protocols based on Encrypted Key Exchange (EKE).
The current proposal is based on the SPAKE2 internet draft and cites a proof from CT-RSA 05 [9].
We note that [9] does not prove forward secrecy for the scheme, but the property is believed to hold.
(A new more complete proof would be needed.)

There are three main issues with the SPAKE2 design.

1) Choosing M and N
    The security of the protocol relies on M and N being group elements, chosen in a way that their discrete logarithms are unknown to the adversary.
    The SPAKE2 draft [8] describes an algorithm for generating M and N but it is difficult to prove that this algorithm generates appropriate values.
    
    A more convincing algorithm would be to choose some secure hash-to-group algorithm H and calculate M = H(0) and N = H(1)
    Perhaps the SPAKE2 authors did not want to add a dependency to the hash-to-curve draft and this is why they did not do this?
    It is also worth noting that the design of SPAKE2 in [9] was primarily inspired by not wanting to rely on a hash-to-group primitive.
    If we start relying on a hash-to-group function, then simpler and more efficient protocols become available

    In particular, a precursor of SPAKE2 (by the same authors) called One-Mask Diffie-Hellman Key Exchange (OMDHKE) is described in [10].
    It does not use M or N at all and instead uses a mask generation function implemented by multiplying g^x with H(pwd) for some hash-to-group function H.
    Furthermore, it only requires one endpoint (say the client) to perform this masking, the other endpoint (say the server) only has to send the usual DH share g^y.
    The resulting 3-message protocol (with key confirmation) is ideal for integration into TLS 1.3 and has a security proof.
    Furthermore, a follow-up paper [11] proves forward secrecy for this variant of the protocol.

    In summary, we recommend that SPAKE2 should reduce trust in the M/N generation function by using some proved hash-to-group function.
    Alternatively, it may even be better to move to a more efficient hash-based EKE construction like OMDHKE.

2) Computing in the prime-order subgroup
    The security proof of SPAKE2 in [9] relies on all computations being done in the prime-order subgroup.
    Section 3.2 of [1] tries to ensure that the received DH values are in this subgroup:

    "Upon receipt of T, B computes T*h and aborts if the result is equal to I. (This ensures T is in the prime order subgroup of G.)”
   
    The last statement is incorrect. 
    Checking that T*h is not equal to I guarantees that T is not in one of the small subgroups. 
    It does not guarantee that T is in the prime-order subgroup. 
    Instead of this check, we recommend the more expensive check that T*p = I.
    Alternatively, we may decide to “clamp” the received X* and Y* by multiplying them with h (although we need to check that this works for all the groups we care about.)
    For elliptic curves where the full point is being sent, an easier check may be to make sure that the point lies on the curve.

3) Combining Key Confirmation with TLS Finished
    It would be attractive to combine the SPAKE2 key confirmation message with the TLS Finished message.
    However, the transcript used for SPAKE2 key confirmation includes the password. 
    Adding this password to the transcript in the current TLS standards does not appear to be easy.
    This may mean that the SPAKE2 confirmation MAC should be separate from the TLS Finished message.

[8] https://tools.ietf.org/html/draft-irtf-cfrg-spake2-08 <https://tools.ietf.org/html/draft-irtf-cfrg-spake2-08>
[9] https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf <https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf>
[10] https://www.di.ens.fr/david.pointcheval/Documents/Papers/2004_pkc.pdf <https://www.di.ens.fr/david.pointcheval/Documents/Papers/2004_pkc.pdf>
[11] https://www.di.ens.fr/~mabdalla/papers/ACP05-letter.pdf <https://www.di.ens.fr/~mabdalla/papers/ACP05-letter.pdf>

Summary
=======

From the viewpoint of proofs:
- SPEKE does not have a proof in its current submitted form
- CPace has a proof that relies on an assumption about session identifiers that is not fully clear to us
- J-PAKE has a proof that requires an algebraic adversary model
- SPAKE2 has a proof in [9] but this needs to be extended for forward secrecy
(This over-simplified summary ignores many important details of the underlying models,
 including differences between proofs that rely on random oracles and those that do not.)

From the viewpoint of TLS integration:
- SPEKE can be implemented in 3 flows.
  It requires a standard DH key exchange (2 key gens, 1 shared secret.)
  Key confirmation for SPEKE uses a mechanism that is quite different from TLS finished messages.
- CPace can be implemented in 3 flows under some assumptions about the underlying transport protocol; otherwise it may require 5 flows. 
  It requires a standard DH key exchange. 
  Key confirmation is not specified.
- J-PAKE can be implemented in 3 flows. 
  It requires a special DH key exchange (4 key gens, 6 exponentiations and 6 ZK proofs)
  One of the key confirmation mechanisms suggested in the RFC is compatible with TLS.
- SPAKE2 can be implemented in 3 flows. 
  It requires a standard DH key exchange. 
  Key confirmation requires including the password into the transcript, and hence is incompatible with TLS.

Overall, we liked best the structure of SPAKE2, but prefer the variant called OMDHKE from [10].

Open Questions
=============

1) Are there more efficient or more secure variants of these protocols that would be more suitable than the ones submitted to the competition?
    We don’t have a definite answer; we found literature on more efficient versions of SPAKE2 and J-PAKE, with which the submitted versions should be compared.

2) How will the proposed protocol compose with existing modes of (protocols like) TLS?
    We investigated whether the key confirmation messages of these PAKEs could be integrated with TLS Finished messages.
    However, many open questions remain: How do passwords interact with PSKs? What will mixed PAKE+Certificate flows look like?
    It also remains to be seen whether the proofs of TLS 1.3 and the proposed PAKEs will compose easily.

Acknowledgments
=============
The analysis above was undertaken by the INRIA Prosecco team, with the kind help of Michel Abdella and David Pointcheval.
We look forward to hearing about any mistakes or misunderstandings in our analysis.

Best regards,
Karthik Bhargavan and Bruno Blanchet

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 16 Sep 2019 13:54:29 +0000

Hi Karthink,

Many thanks for your constructive feedback (and the analysis by Bruno). Please refer to my comments below.

“The proposed variant of SPEKE belongs to a long line of well-studied protocols. The specific protocol proposed here is the one by Hao and Shahandashti [1] “

As you rightly point out, there are many variants of SPEKE. Actually I don’t know which exact SPEKE variant was proposed for this selection. In Dan’s submission, he cites [2] IACR 2001/057 for the security proof of SPEKE, but also states the submitted SPEKE is symmetric and allows the parties to initiate the key exchange simultaneously. However, from [2] it should be clear that what was analysed there is essentially a “modified” SPEKE with mandatory key confirmation. The version described in [2] is certainly not symmetric, and the two parties can’t initiate the process simultaneously. It also requires more rounds. What we report in [1] is a limitation in the SPEKE protocol (as specified in Jablon’s original papers and in the IEEE P1363.2 and ISO/IEC 11770-4 standards), namely: the user identity is not cryptographically bound with the key exchange flows,  which gives rises to some authentication issues (unknown key sharing attack). The attacks don’t apply to the variant in [2] as the key confirmation is defined mandatory, but everywhere else (IEEE and ISO/IEC standards) it’s defined as optional. To avoid any confusion, I think it’s best to leave it to Dan Harkins to clarify which exact SPEKE specification he was referring to in the submission.

“This version does not appear to have a proof.”

I would like to refer you to the updated paper that is recently published at IEEE TIFS 2018.

https://arxiv.org/pdf/1802.04900.pdf

As acknowledged in the paper (last paragraph in Section VI), although we analyzed the effectiveness of the proposed countermeasure, we don’t have any reductionist proof. In my personal opinion, it’s impossible to have any reductionist proof based on common assumptions (CDH, DDH etc). There are an unbounded number of ways for the attacker to fabricate data of any format. It seems inevitable that we are stuck with the heuristic security as it is.

“Bruno observes that the above protocol has a reflection-style attack where A can be fooled into thinking it has a session with B although it only has a session with itself.
Suppose A is willing to act as Initiator and Recipient in different sessions …”

I’m not sure if the attack would work though. Please see [1] and the published version above. Kindly note that in concurrent sessions, the party should add an extension to the identity to make it unique. This is explained in both papers. We can take this discussion offline or wait for Dan to clarify which version was submitted so to keep the discussions relevant to this PAKE selection process.

“We wonder whether it would not be better to consider more efficient variants of J-PAKE, as proposed in [7], for example.”

The two variants of J-PAKE in [7] rely on a trusted setup and a hash-to-curve function respectively. The original idea in the J-PAKE construction is exactly to remove these. Indeed, if we reply on either of these, other PAKE protocols would be more desirable.

[4] https://www.dcs.warwick.ac.uk/~fenghao/files/pw.pdf
[5] https://eprint.iacr.org/2010/190.pdf
[6] https://www.normalesup.org/~fbenhamo/files/publications/SP_AbdBenMac15.pdf
[7] https://eprint.iacr.org/2016/379.pdf