Re: [Cfrg] Re-review of the four balanced PAKEs

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

From: Paul Grubbs <[e-mail]>
Sent: Thursday, October 24, 2019 12:13 PM
To: Scott Fluhrer (sfluhrer) <[e-mail]>
Cc: [e-mail]
Subject: Re: [Cfrg] Re-review of the four balanced PAKEs

Hey Scott, thanks for your comments. I have a couple questions:

1. Regarding SPAKE-2, you said this
> 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.
I don't quite understand what you mean - can you explain this on-line dictionary attack? In general, aren't all PAKEs vulnerable to online dictionary attacks?

I’m sorry, I should have been more explicit.

What I meant is that there is an on-line dictionary attack, where the adversary could participate in one exchange, and as a result of that one exchange, is able to check every entry in his dictionary.

Here is how it would work: in SPAKE-2, the honest initiator transmits the value X = xG + pwM (x is a random value, pw is a value based on the password); the adversary responder transmits the value Y=yG (for an arbitrary value y that the adversary knows), and then the honest initiator computes x(Y – pwN), and generates an encrypted message based on that value (and the password, and some other things that the adversary knows).

Now, suppose the adversary knows the value n s.t. N = nG.  Then, for a password guess pw’, he can compute x’G = X -pw’M,  and then compute the expected shared secret (y – pw’ n) x’G, if his guess of pw’ is correct (that is, pw’ = pw), then (y – pw’ n)x’G = x(Y – pwN), and so that shared secret (along with pw’) would allow him to decrypt the initial message (and thus signal that his password guess was correct.

Because the interaction with the honest initiator did not depend on the password guess, the adversary can perform this computation for every password in his dictionary as a result of a single exchange.

And, because the RFC makes N global, he can perform this on-line attack against everyone using the same parameter set (and, if he can perform the computations fast enough, he might be able to compute the shared secret before the initiator times out (which means that the initiator would not know that he’s been attacked).



2. This 'quantum annoying' property is the subject of much CFRG discussion, but it seems ill-specified. Can you explain it in a bit more detail, maybe by example (e.g., why does CPace have 'good' quantum annoyance)?

Well, as far as I know, it hasn’t been given a formal definition.  The best informal one I can think of is “as a result of X online exchanges (and unlimited number of off-line exchanges, that is, the recording of negotiations between two honest parties), the ability to compute Y Discrete Logs would allow the adversary to check at most X+Y dictionary entries”

The impetus for this concept is that it is reasonable to expect that initial Real Quantum Computers (that is, Quantum Computers sophisticated enough to solve DLog problems at all) are likely to be both expensive and slow.  Hence, even if a large scale adversary gets some, they’re not going to be able to afford that many, and hence the number of discrete log problems they can solve will be limited.  Hence, if it takes a million discrete logs to do a full dictionary search, that’s likely to be beyond their budget.

This is obviously a rather weaker goal than full Quantum-Safe cryptography, but would appear (at least, IMHO) a reasonable compromise (given that no Quantum-Safe PAKEs have been submitted.

Now, as for CPace, I do not have any proof that it is “Quantum Annoying”; the best I can say is “I don’t see any way that you could use a limited ‘Discrete Log’ finder to search for multiple passwords, or otherwise recover the shared secret’.  You can take that for what it is worth.

On Thu, Oct 24, 2019 at 11:23 AM Scott Fluhrer (sfluhrer) <[e-mail]<mailto:[e-mail]>> wrote:

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.


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