Subject: [CFRG] Attack on a Real World SPAKE2 Implementation

From: Ruben Gonzalez <[email-masked]>
Date: Fri, 7 May 2021 09:24:20 +0200

Hello CFRGers,

this is my first time posting on the mailing list. In case this is the 
wrong place for such a message, I apologize.

Aaron Kaiser (in CC) and I wrote a detailed blog post about a 
vulnerability Aaron found in a real world SPAKE2 implementation.

The blog post "Croc Full Plaintext Recovery - CVE-2021-31603" can be 
found here: https://redrocket.club/posts/croc/.

We did not attack SPAKE2 directly, but a faulty implementation. The blog 
post might still be relevant for authors of the standard, since it shows 
how developers can easily misunderstand it.

For questions or additional information, just drop us an email.

Kind regards,

Ruben Gonzalez

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 7 May 2021 08:17:15 +0000

Ruben Gonzalez <[email-masked]> writes:

>We did not attack SPAKE2 directly, but a faulty implementation.

Nice work!  This is an example of what I once referred to as second-order
snake oil crypto, good crypto applied badly (first-order is bad crypto).  It's
also at least as deadly as first-order snake oil because now the attacker has
a beacon to guide them to where the insecurities are: Ignoring the great mass
of other code, look for where the crypto is done and then find the flaw in how
it's applied.

(This makes the job of doing crypto audits much, much easier, at least in the
sense that it makes it easy to demonstrate the value of performing the audit
to whoever commissioned it.  Seeing AES-GCM or some other RC4-equivalent and
ECDH practically guarantees a useful result).

Peter.

---

From: "Filippo Valsorda" <[email-masked]>
Date: Fri, 07 May 2021 19:51:47 -0400

2021-05-07 04:17 GMT-04:00 Peter Gutmann <[email-masked] <mailto:pgut001%40cs.auckland.ac.nz>>:
> Ruben Gonzalez <[email-masked] <mailto:in%2Blists%40ruben-gonzalez.de>> writes:
> 
> snake oil crypto, good crypto applied badly (first-order is bad crypto).

Snake oil is fraudulent. This is a broken implementation, for which specification authors should at least consider sharing the blame. How did the spec fail the implementers, who presumably were not trying to implement something in a broken way?

(I know, I know, SPAKE2 is a draft, not an RFC! But it's been a draft for almost 7 years, and at some point people need to implement stuff.)

---

From: Watson Ladd <[email-masked]>
Date: Sat, 8 May 2021 15:25:15 -0400

On Fri, May 7, 2021, 7:52 PM Filippo Valsorda <[email-masked]> wrote:

> 2021-05-07 04:17 GMT-04:00 Peter Gutmann <[email-masked]>:
>
> Snake oil is fraudulent. This is a broken implementation, for which
> specification authors should at least consider sharing the blame. How did
> the spec fail the implementers, who presumably were not trying to implement
> something in a broken way?
>

The SPAKE2 draft postdates many if the deployed implementations. There is
no evidence the authors consulted the draft which counting specified M and
N to avoid exactly this failure.

>
> (I know, I know, SPAKE2 is a draft, not an RFC! But it's been a draft for
> almost 7 years, and at some point people need to implement stuff.)
>

I think the failure to publish a secure protocol that is actually deployed
and used in a timely manner is a problem. Thankfully it has at last gotten
out of the CFRG.

Part of the issue is that I had a dissertation to write and was not the
most motivated all of the time. But the bigger issue imho is that very few
implementors gave feedback or provided the prodding to advance it. Until
Ben came along no one cared and kitten ended up doing its own thing because
we were too slow.

What happened to rough consensus and running code?

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

---

From: Björn Haase <[email-masked]>
Date: Sun, 9 May 2021 18:05:47 +0200

Hello All,

I think we should be be careful with biased wordings such as "sharing
the blame" and assumptions such as "snake oil" which implies fraudulent
intentions.

IMO, we just don't know all of the details and it might be more
constructive not to speculate too much.

(When writing this: Even though my professional experience taught me to
never under-estimate the power of foolishness, I think that it should be
considered to be truly remarkable how many things have gone wrong here
simultaneously. )

For the same reason, I don't think that one should be careful of
"blaming" the authors of the SPAKE2 for anything that has gone wrong here.

Regarding possible improvements of the draft I still would like to come
up with a suggestion:

What about adding a clear and *mandatory* specification for conforming
implementations of SPAKE2 on any curve on how to generate the "nothing
upon my sleeve" inputs M,N?

I would recommend mandating a procedure that refers to the current draft
version of the h2c draft as it is today.

Alternatively, if one would like to avoid references to the h2c draft
(in order to make M,N independent of possible future changes in the h2c
draft), one could consider using a specification in the style of
appendix A in https://eprint.iacr.org/2018/286.pdf, where similar 
"nothing upon my sleeve" points "A, C" were needed.

At any rate, I believe that there seems to be need for a mandatory
trustworthy way for generating M, N for *any* curve.

Yours,

Björn

P.S.:

Actually, I just noticed that its not really explicit how the points M,
N in the current SPAKE2 draft 18 are calculated for the curves where
test vectors are provided. I presume that the uniform h2c map was used
for the given seed inputs?

Am 08.05.2021 um 01:51 schrieb Filippo Valsorda:
>> Ruben Gonzalez <[email-masked]
>> <mailto:in%2Blists%40ruben-gonzalez.de>> writes:
>>
> specification authors should at least consider sharing the blame. How
> did the spec fail the implementers, who presumably were not trying to
> implement something in a broken way?
>
> (I know, I know, SPAKE2 is a draft, not an RFC! But it's been a draft
> for almost 7 years, and at some point people need to implement stuff.)
>

---

From: [email-masked]
Date: Sun, 9 May 2021 14:02:58 -0500 (CDT)

By the way, they state where the algorithm details came from "This protocol is derived from Dan Boneh and Victor Shoup's cryptography book [https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_4.pdf] (pg 789, 'PAKE2 protocol')." So we should look at that to see how to improve descriptions. I think it's really people not knowing that "hash to curve" or "a random point on the curve" are not normal things and very important. I know of someone who read about "hash to curve" in I think OPAQUE and thought that it was "H(value)*G". So we need to make special notes on these things.

> On 05/09/2021 11:05 AM Björn Haase <[email-masked]> wrote:
> 
> 
> Hello All,
> 
> 
> 
> I think we should be be careful with biased wordings such as "sharing the blame" and assumptions such as "snake oil" which implies fraudulent intentions.
> IMO, we just don't know all of the details and it might be more constructive not to speculate too much.
> 
> (When writing this: Even though my professional experience taught me to never under-estimate the power of foolishness, I think that it should be considered to be truly remarkable how many things have gone wrong here simultaneously. )
> 
> For the same reason, I don't think that one should be careful of "blaming" the authors of the SPAKE2 for anything that has gone wrong here.
> Regarding possible improvements of the draft I still would like to come up with a suggestion:
> 
> What about adding a clear and *mandatory* specification for conforming implementations of SPAKE2 on any curve on how to generate the "nothing upon my sleeve" inputs M,N? 
> 
> I would recommend mandating a procedure that refers to the current draft version of the h2c draft as it is today. 
> 
> Alternatively, if one would like to avoid references to the h2c draft (in order to make M,N independent of possible future changes in the h2c draft), one could consider using a specification in the style of appendix A in https://eprint.iacr.org/2018/286.pdf, where similar "nothing upon my sleeve" points "A, C" were needed.
> At any rate, I believe that there seems to be need for a mandatory trustworthy way for generating M, N for *any* curve.
> 
> Yours,
> Björn
> P.S.:
> Actually, I just noticed that its not really explicit how the points M, N in the current SPAKE2 draft 18 are calculated for the curves where test vectors are provided. I presume that the uniform h2c map was used for the given seed inputs?
> 
> 
> _______________________________________________ CFRG mailing list [email-masked] https://www.irtf.org/mailman/listinfo/cfrg

---

From: Loup Vaillant-David <[email-masked]>
Date: Sun, 09 May 2021 23:56:10 +0200

Hi,

> I know of someone who read about "hash to curve" in I think OPAQUE
> and thought that it was "H(value)*G". So we need to make special
> notes on these things.

I made the same mistake the first time I've heard about PAKE. I was
like, "that can't possibly work", because I noticed that if I
implemented hash to curve this way, that would utterly break the
protocol I was looking at.

And I consider myself reasonably knowledgeable about these things, I
just didn't know about this new thing we called "hash to curve". I
expect many people stumbling upon the concept might not do the sanity
check I did, and happily something broken instead of reaching for the
real thing.

Loup.

---

From: "Filippo Valsorda" <[email-masked]>
Date: Mon, 10 May 2021 01:26:07 +0200

2021-05-08 21:25 GMT+02:00 Watson Ladd <[email-masked] <mailto:watsonbladd%40gmail.com>>:
> On Fri, May 7, 2021, 7:52 PM Filippo Valsorda <[email-masked]> wrote:__
> The SPAKE2 draft postdates many if the deployed implementations. There is no evidence the authors consulted the draft which counting specified M and N to avoid exactly this failure.
>> 
>> 
> I think the failure to publish a secure protocol that is actually deployed and used in a timely manner is a problem. Thankfully it has at last gotten out of the CFRG.
> 
> Part of the issue is that I had a dissertation to write and was not the most motivated all of the time. But the bigger issue imho is that very few implementors gave feedback or provided the prodding to advance it. Until Ben came along no one cared and kitten ended up doing its own thing because we were too slow.
> 

That was bad phrasing on my side, sorry Watson.

It was "specification authors" at large, not "this specification's Authors". It looks like the way it failed this implementation might be by not finalizing soon enough, which is definitely not your individual responsibility (as that would be of course an unsustainable model).

In other words, agreed on where the problem lies.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 9 May 2021 22:48:12 -0400

On Sun, May 9, 2021 at 12:06 PM Björn Haase <[email-masked]> wrote:
<snip>
> Regarding possible improvements of the draft I still would like to come up with a suggestion:

Thank you for the suggestion. Alas there are several procedural and
substantive reasons I don't think I'll be following it.

> I would recommend mandating a procedure that refers to the current draft version of the h2c draft as it is today.

Remember the M and N are computed offline, once. So hunt and peck
works, and is what we did for the M and N in the draft for the most
common curves of interest. Really there is just P256 and Ed25519 in
use.

Now, as for the h2c draft, the problem is that draft is far behind in
the process, and indeed didn't even exist when we began this work. I'd
prefer to not introduce an unnecessary dependency.  The other problem
is that then changes to the h2c draft would force changes, sometimes
big ones to this draft.

> Alternatively, if one would like to avoid references to the h2c draft (in order to make M,N independent of possible future changes in the h2c draft), one could consider using a specification in the…

This draft has already passed through extensive review, including two
distinct examinations by the Experts Panel, a rather prolonged
post-last call process that discovered several unfortunate mistakes
(now corrected!) in test vector generation.

At this stage, with the draft in the IRTF chair queue, I am very
reluctant to make a change solely because it might be a good idea for
a small handful of people doing things on other curves. If there is a
genuine implementor need, a separate document can be advanced.

Sincerely,
Watson Ladd

-- 
Astra mortemque praestare gradatim

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 10 May 2021 11:24:57 +0000

Hi Watson,

I had some comments on the SPAKE2 draft, but I didn’t know how they were addressed. Maybe there is an implicit feedback loop that I’ve missed. Anyway, I had another look at the latest version (v18). I think the draft can be improved in a few places. The following comments are for your consideration.

  1.  Section 3.1, “Let G be a group in which the gap Diffie-Hellman (CDH) problem is hard.”

Do you mean GCDH instead of CDH? It looks a typo. It’s worth noting that CDH is assumed in the original SPAKE2 paper [1], but in the updated version [2] that includes the consideration of forward secrecy, the assumption has been changed to GCDH.

  1.  Section 3.1, “In the case of a composite order group we will work in the quotient group.”

How exactly does the protocol work in a composite order group? This is not consistent with the statement that the proposed protocol operates in a prime-order group, which is also stated in the original SPAKE2 paper.

  1.  Section 3.2, “SPAKE2 is a one round protocol to establish a shared secret with an additional round for key confirmation.”

This is not precise for two reasons. First, “round” has an established definition in a two/multi-party secure computation setting which refers to a step that parties can do without depending on each other. The order of the items in the KDF defined in SPAKE2 implies a sequence of actions which cannot be done in one round. Therefore, strictly speaking, it’s 2-round. But you can also say it’s 2-flow, which can be completed in one round trip. I think the one-round trip is what you wanted to emphasize here. Second, the one-round trip, as stated in the original SPAKE2 paper, is based on treating the explicit key confirmation as an optional step. But in your draft, you have made it mandatory (see my comment later). When a mandatory explicit key confirmation process is considered, the SPAKE2 protocol should be 3-flows (or 1.5 round trips). I suggest the technical claims be made more precise.

  1.  Section 3.2., “Both parties MUST NOT consider the protocol complete prior to receipt and validation of these key confirmation messages.”

This makes the explicit key confirmation mandatory, which is different from the specification in the original SPAKE2 paper. It’s fine that you change it to “mandatory”, but you need to consider the implication on your claim on round-efficiency. These need to be consistent.

  1.  Section 3.3, “To begin, A picks x randomly and uniformly from the integers in [0,p)”

I take it that you mean [1, p] instead of [0, p]? I don’t know what 0 means here. The spec for B on choosing y will need to be changed accordingly.

  1.  Section 3.3, “Both A and B calculate a group element K.  A calculates it as h*x*(T-w*N), while B calculates it as h*y*(S-w*M).  A knows S because it has received it, and likewise B knows T.  The multiplication by h prevents small subgroup confinement attacks by computing a unique value in the quotient group.  This is a common mitigation against this kind of attack.”

This is confusing. Why do you multiply the value by h? Given that the public key validation is done properly on the received item, the multiplication by h appears not necessary at all. The statement that “The multiplication by h prevents small subgroup confinement attacks by computing a unique value in the quotient group.” Is potentially misleading and should be removed (more comment on public key validation later).

  1.  Section 3.3., “If an identity is absent, it is encoded as a zero-length string. This MUST only be done for applications in which identities are implicit.  Otherwise, the protocol risks Unknown Key Share attacks (discussion of Unknown Key Share attacks in a specific protocol is given in [I-D.ietf-mmusic-sdp-uks]).”

When the identities are implicitly known, is there any reason why they cannot be stated explicitly? Allowing an empty identity introduces unnecessary risks and only invites implementation errors and attacks.

  1.  Section 5, “In addition M and N may be equal to have a symmetric variant.”

It’s very vague. First of all, you didn’t define how M and N can be equal. Second, if M and N are allowed to be equal, why you still have the M!=N variant? The more variants of a protocol that you introduce, the more likely the protocol and the implementation may be attacked.

  1.  Section 5, “The security of these variants is examined in [MNVAR].”

This is potentially misleading. This gives the reader the impression that the variants that you describe in Section 5 have been examined in [MNVAR], but I don’t think that’s the case. The option of M = N is discussed in [2], but not for the per-user M and N setting as far as I can tell. You need to give an appropriate reference for the security analysis of the variants that you describe (to my knowledge, there is no such reference, but I may have missed something). If you refer to the M=N variant for the main protocol in Section 3.2, then there is a question, why you can’t just use M=N for the main protocol as it’s simpler? In general, having lots of variants is not a good idea, and should be avoided as much as possible.

  1.  Section 5, “This variant may not be suitable for protocols that require the messages to be exchanged symmetrically and do not know the exact identity of the parties before the flow begins.”

The SPAKE2 protocol is not symmetrical. So “exchanging symmetrically” is not applicable here. The variant can be of course be used in the scenario you describe. It just needs an additional flow to send the user identity. This implies that this variant can’t be completed in 1 round trip. It’s best to be explicit on these to give the reader a full pictures.

  1.  Section 7, “A security proof of SPAKE2 for prime order groups is found in [REF], reducing the security of SPAKE2 to the gap Diffie-Hellman assumption.”

As said above, the proof based on gap DH is in a different paper; see [2] below. The reference should be updated.

  1.  Section 7, “The generation methods specified in this document are designed to eliminate concerns related to knowing discrete logs of M and N.”

I suggest to use “mitigating concerns” rather than “eliminating concerns”. Given that M and N are static value in a global setup, once the relation of the two static values becomes somehow known later, the system will be compromised without the users being aware. To address this threat, you might need to update the M and N values regularly, say every few years. A procedure that describes the regular update of the values would be useful (which may include some time information in the hash).

  1.  Section 7, “Elements received from a peer MUST be checked for group membership: failure to properly validate group elements can lead to attacks.  It is essential that endpoints verify received points are members of G.”

It’s good that you explicitly mandate the group membership. Given that it’s a crucial step, I suggest you give more details on how the validation is done. You can refer to Algorithm 6, in p. 25 of [3] for the steps to validate a received item. The Algorithm 6 is described for ECDSA, but the same applies to SPAKE2.

  1.  Section 7, “Some implementations of elliptic curve multiplication may leak information about the length of the scalar: these MUST NOT be used.”

A bit vague. I would suggest you give more details on which exact implementations must not be used.

  1.  Test vectors

For cases where the user identity is an empty string, these should be removed. The user identities should be explicitly defined. An empty user identity string will only lead to confusion and potential attacks.

[1] https://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
[2] https://eprint.iacr.org/2019/1194.pdf
[3] https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 10 May 2021 12:02:35 +0000

*   I take it that you mean [1, p] instead of [0, p]? I don’t know what 0 means here. The spec for B on choosing y will need to be changed accordingly.

Just to clarify, the data range I meant is from 1 to p-1.

(I typed a round bracket after p, but somehow it looks like a square bracket)