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

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 24 Oct 2019 15:23:09 +0000

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 identiﬁers are unique between concurrent sessions, the use of the extra session identiﬁer 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.

---

From: Paul Grubbs <[email-masked]>
Date: Thu, 24 Oct 2019 12:12:45 -0400

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) <
[email-masked]> wrote:

> 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.
>
>
>
> 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.
>
>
>
>
>
> * 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
>
> * "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.
>
> **** 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.
>
>
>
> * 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)
>
>    - 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 identiﬁers are unique between concurrent sessions, the
> use of the extra session identiﬁer *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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Scott Arciszewski <[email-masked]>
Date: Thu, 24 Oct 2019 12:21:09 -0400

"Quantum Annoying" was something Steve Thomas coined (IIRC).

It means you have to break an ECDLog problem per attempt. It's O(n) rather
than O(1).

It's not quite post-quantum resistance (where each attempt requires
breaking PQ crypto algorithms). But it does make attacks "annoying" if a
quantum computer is ever developed.

BSPAKE is argued to be quantum annoying. OPAQUE is not. I like both designs.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

On Thu, Oct 24, 2019 at 12:13 PM Paul Grubbs <[email-masked]> wrote:

> > 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
> 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)?
>
>> 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;
>> 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.
>>
>>
>>
>> ** 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
>> 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
>>
>>
>>

---

From: Björn Haase <[email-masked]>
Date: Thu, 24 Oct 2019 16:21:52 +0000

Hello Paul,

I am fairly convinced that Scott did mean to refer to an offline-attack.

>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.

It’s the same topic that has also be referred to as  “Trusted setup”  issue. Among the candidates, VTBPEKE and SPAKE-2 do have this issue J-PAKE and the protocols that use mappings don’t use special points and don’t have it.

Basically, when the discrete logarithm of the chosen points becomes known, the adversary is able to mount offline attacks for VTBPEKE and SPAKE-2.

Yours,

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 25 Oct 2019 09:18:43 +0000

Hi Sott,

When you consider the finite field setting (ModP), I think you need to count the cost of the hash-to-field-element operation, which is the equivalent of the hash-to-curve operation in the EC setting. To avoid the need for such an expensive mapping operation, SPEKE uses a safe prime for modulus. But then one exponentiation in SPEKE for 2048-bit modulus is about 7-8 times more expensive than that in J-PAKE. Overall, it can be even more expensive than J-PAKE! This is not reflected in your table. The same issue would apply to other PAKE candidates that rely on hash-to-curve functions.. One might avoid this issue by abandoning the finite field setting, but I think that’s inappropriate for the “completeness” of the protocol specification and the diversity of security choices. After all, the finite field and ECC are just two different ways to implement the same protocol. J-PAKE is specifically designed to eliminate a trusted setup and the need for any hash-to-curve (or the equivalent in the finite field), as neither was considered desirable. I hope this gives more context to understand the design rationale of this protocol.

Cheers,
Feng

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

SPAKE-2           | d+x               | 2P

Cost:

H: Hash to point

x: Point multiplication

---

From: Björn Haase <[email-masked]>
Date: Fri, 25 Oct 2019 12:36:46 +0000

Dear Scott,

>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.

Regarding the complexity of the session-ID establishment, Ran Canetti has recently provided a very helpful input on this list. As a result, I conclude that an additional round-trip for sid-establishment could be avoided.

I am working on a document that considers this aspect more in detail and also provides a suggestion regarding the API interface that has equally been suggested by Ran. I.e. in the case of CPace/AuCPace there might be an API that might provide the link between a possible TLS1.3 instantiation of CPace and a higher-level protocol, such as AuCPace where some protocol steps might be included in a operating-system component such as PAM on Linux.

Yours,

Björn.

Dr. Björn Haase 

Disclaimer:

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 24 Oct 2019 18:29:38 +0000

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

> 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) <[email-masked]<mailto:[email-masked]>> wrote:

Balanced PAKE summary

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

SPAKE-2           | d+x               | 2P

Cost:

H: Hash to point

x: Point multiplication

Message Size:

H: A hash

Notes:

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