[Cfrg] Review of the Balanced PAKE proposals

[Karthik Bhargavan <[e-mail]>]

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