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

[Paul Grubbs <[e-mail]>]

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?

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)?

On Thu, Oct 24, 2019 at 11:23 AM Scott Fluhrer (sfluhrer) <
[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]
> https://www.irtf.org/mailman/listinfo/cfrg
>