[Cfrg] Review of the PAKE proposals

[Yoav Nir <[e-mail]>]

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.