[Cfrg] Re-review of the four balanced PAKEs

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

I re-reviewed the four balanced PAKEs, looking at the more practical issues.



Summary: it comes down to the choice between CPace and SPAKE-2 (J-PAKE can be discounted because of the extra round trip needed, and the expense; SPEKE can be discounted because of the lack of a single proposal (and the single proven one is no better than CPace).



SPAKE-2 is better than CPACE in the sense that it is a single round protocol (and so can be used as a drop-in replacement for DH, assuming some hooks for exchanging identities), and so would be slightly easier to use in a protocol; CPACE requires a key confirmation to be sent after the exchange (possibly along with the first encrypted message).  On the other hand, I wouldn’t expect that a protocol would have a major issue with the extra message that CPACE requires.



SPAKE-2 is better in that it uses only standard (point multiplication) operations, which are more likely to be implemented in crypto libraries in constant time.  CPACE requires a hash-to-curve operation; it is less likely that a crypto library has a constant time implementation of that available.



SPAKE-2 is better in that it uses somewhat less message overhead (two hashes less).  However, even with this additional overhead, CPACE is still quite reasonable (perhaps 128 bytes total, not counting overhead).



SPAKE-2 (as specified in the RFC) is worse than CPACE in that it relies on global M and N parameters.  While the M and N values in the SPAKE-2 RFC are claimed to be generated in a NUMS manner, the issue still remains that if someone were to be able to solve a single ECDLog problem, they could then perform an on-line dictionary attack against anyone using that parameter set.



In terms of other practical issues (computation, message overhead), they are mostly identical.



My opinion is that CPACE is better, the single disadvantage that SPAKE-2 has (vulnerable if someone somewhere solves just one ECDLog problem) is worse than the three disadvantages of CPACE.





A more detailed listing of the comparison:





* Fragile is you give an attacker offline password guessing if there is a minor error in the implementation of ECC.

* Quantum annoying (“PQ-ish”) is the property that an attacker with a quantum computer needs to solve a DLP per password guess.



Balanced PAKE summary

Name              | PQ-ish   | Rounds*       | Fragile

------------------+----------+---------------+---------

CPace             | Good     | 1.5 (1/2)     | Moderate**

J-PAKE            | Bad      | 2   (2/2)***  | Good

SPAKE-2           | Bad      | 1   (1/1)     | Good

SPEKE (EC based)  | Good     | 1   (1/1)**** | Moderate**

SPEKE (ModP based)| Moderate | 1   (1/1)**** | Good



* "number of total trips" ("number of messages received before initiator can encrypt"/"number of messages received before responder can encrypt")

** CPace and SPEKE (EC) is listed as moderately fragile because they depend on a hash-to-curve operation based on the secret password; a timing variation there might leak the secret.  While constant-time hash-to-curve algorithms are known, they are less common than standard EC operations, and hence this needs to be considered.

*** This assumes that we use the three-pass variant, and we do use the recommended key confirmation.

**** Note that SPEKE claims to be secure without an explicit key confirmation pass; we assume the “Patched SPEKE” protocol found in the paper.  See my concerns about this below.



Balanced PAKE summary (continued)

Name              | Comp per side (*) | Total Message Size (**)

------------------+-------------------|------------------

CPace             | H+2x              | 2P+2H

J-PAKE            | 2g+3x+3pg+3pv     | 6P+4Z+2H

SPAKE-2           | d+x               | 2P

SPEKE (EC based)  | H+2x              | 2P

SPEKE (ModP based)| 2M                | 2M





* In all cases, the initiator and the responder perform the same overall amount of computation, hence we don’t break it down per side.  In addition, we omit the costs of hashes, point additions, modular multiplications, as they are expected to be insignificant compared to the point multiplications/modular exponentiations listed.

** Note that none of the protocols are defined in bits-on-the-wire format; there are likely to be some additional overhead (such as identities and nonces) exchanged, but those are not listed.  This additional overhead would appear to be likely to be similar for all the candidates.



Cost:

H: Hash to point

x: Point multiplication

g: Point multiplication of the generator (which is potentially cheaper than a point multiplication of an arbitrary point)

d: Double scalar point multiply and add, that is, aB + cD

pg: Zero knowledge proof generation (approximately the same as a field multiplication)

pv: Zero knowledge proof verification (approximately the same as a double scalar point multiply and add)

M: Modular exponentiation



Message Size:

P: An elliptic curve point

H: A hash

Z: A zero knowledge proof (an elliptic curve point plus an integer the size of the group)

M: An integer of the size of the DH group



Notes:



  *   In general, none of these proposals are defined at the level that I believe that the CFRG needs.  Most of them do not document bits-on-the-wire format, or call out required error checking.  I believe that we need to generate a sufficiently detailed protocol that could be inserted as a blackbox into real protocols; whichever we pick, there’s some work required before we get to that point.
  *   As a reminder, if we go with the SPAKE-2 option, someone would need to verify the generation of the M and N values specified in the RFC.  I was able to do a partial validation (which looked good); however, I was unable to accomplish a complete one.
  *   The more recent SPEKE paper (https://eprint.iacr.org/2014/585.pdf) claims that they don’t need an explicit key confirmation step, however I find their argument unsatisfying.  The claim appears in section 5.3 “Countermeasures and suggested changes to standards”; they give several suggestions in this section, and it is unclear which is being proposed.  They state that, in the case of multiple concurrent negotiations, the two sides should use distinct identifiers for each one (e.g. “Alice-1” for the first session, “Alice-2” for the second); that has obvious practical problems in the case that the two sides don’t agree on which session is the first.  In addition, the relevant text is:

As long the user identifiers are unique between concurrent sessions, the use of the extra session identifier does not seem needed. [emphasis added]

They give no proof as to the above statement.  This lack of rigor, and the lack of a single concrete proposal leads me to discount SPEKE as a desirable proposal



  *   Reasoning behind Quantum Annoying statements:
     *   J-PAKE is not Quantum Annoying, computing three discrete logs would allow an adversary to perform an off-line dictionary search for the password (that is, on a recorded session).  In addition, if the password is known, three discrete logs are sufficient to recover the shared secret on a recorded session.
     *   SPAKE-2, as proposed, is not Quantum Annoying, a single discrete log of the global M (or N) parameters would allow an adversary to perform an on-line dictionary attack.
     *   SPEKE (ModP based) is listed as moderate, as an attacker could attempt to compute a large number of discrete logs in an attempt to form a factor base (which would allow him to efficiently compute any discrete log).  However, the number of discrete logs required would be huge, and so this might not be a practical issue.