Subject: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 14 Oct 2020 09:06:28 +0300

Dear CFRG participants,

This message is starting 2 weeks RGLC on
draft-irtf-cfrg-spake2-13 ("SPAKE2, a PAKE"), that will end on October 29th
2020. If you've read the document and think that it is ready (or not ready)
for publication as an RFC, please send a message in reply to this email or
directly to CFRG chairs ([email-masked]). If you have detailed
comments, these would also be very helpful at this point.

The document has undergone many reviewing during the PAKE selection process
(see https://github.com/cfrg/pake-selection/). Later there was another
review (of -12 version) by Scott Fluhrer (thanks, Scott!),
https://mailarchive.ietf.org/arch/msg/crypto-panel/ZYeiXy4J5whuW2Thvqx1jcxq8Xs/
.

SPAKE2 was not selected as a result of a selection process, but since it
predated the contest, the chairs decided not to stop it (and only it, not
any other PAKEs), asking the authors to add the corresponding disclaimer in
the draft: "This document predated the CFRG PAKE competition and it was not
selected.".

Thank you,

Stanislav, for CFRG chairs

---

From: "Hao, Feng" <[email-masked]>
Date: Wed, 14 Oct 2020 19:36:21 +0000

For “per-user M and N”, the authors need to be explicit how exactly will each party know the identity to be used by the other party even before any communication starts. Otherwise, you will end up with a “one-round PAKE” that can’t be implemented in one round.

Cheers,
Feng

From: Cfrg <[email-masked]> on behalf of "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wednesday, 14 October 2020 at 07:04
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: [Cfrg] RGLC on draft-irtf-cfrg-spake2-13

Dear CFRG participants,

This message is starting 2 weeks RGLC on draft-irtf-cfrg-spake2-13 ("SPAKE2, a PAKE"), that will end on October 29th 2020. If you've read the document and think that it is ready (or not ready) for publication as an RFC, please send a message in reply to this email or directly to CFRG chairs ([email-masked]<mailto:[email-masked]>). If you have detailed comments, these would also be very helpful at this point.

The document has undergone many reviewing during the PAKE selection process (see https://github.com/cfrg/pake-selection/). Later there was another review (of -12 version) by Scott Fluhrer (thanks, Scott!), https://mailarchive.ietf.org/arch/msg/crypto-panel/ZYeiXy4J5whuW2Thvqx1jcxq8Xs/.

SPAKE2 was not selected as a result of a selection process, but since it predated the contest, the chairs decided not to stop it (and only it, not any other PAKEs), asking the authors to add the corresponding disclaimer in the draft: "This document predated the CFRG PAKE competition and it was not selected.".

Thank you,

---

From: Watson Ladd <[email-masked]>
Date: Wed, 14 Oct 2020 14:37:13 -0700

On Wed, Oct 14, 2020, 12:36 PM Hao, Feng <[email-masked]> wrote:

> For “per-user M and N”, the authors need to be explicit how exactly will
> each party know the identity to be used by the other party even before any
> communication starts. Otherwise, you will end up with a “one-round PAKE”
> that can’t be implemented in one round.
>

This is a higher level protocol consideration, but I don't see how an extra
round would be needed since the server seems the client identity in the
first message. It has to look up the password after all.

If you have specific text that would be helpful I'm happy to add it post
collecting all the comments.

>
> Cheers,
>
> Feng
>
>
>
> *From: *Cfrg <[email-masked]> on behalf of "Stanislav V.
> Smyshlyaev" <[email-masked]>
> *Date: *Wednesday, 14 October 2020 at 07:04
> *To: *"[email-masked]" <[email-masked]>
> *Cc: *"[email-masked]" <[email-masked]>
> *Subject: *[Cfrg] RGLC on draft-irtf-cfrg-spake2-13
>
>
>
> Dear CFRG participants,
>
> The document has undergone many reviewing during the PAKE selection
> process (see https://github.com/cfrg/pake-selection/). Later there was
> another review (of -12 version) by Scott Fluhrer (thanks, Scott!),
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Hao, Feng" <[email-masked]>
Date: Wed, 14 Oct 2020 22:48:22 +0000

On Wed, Oct 14, 2020, 12:36 PM Hao, Feng <[email-masked]<mailto:[email-masked]>> wrote:
For “per-user M and N”, the authors need to be explicit how exactly will each party know the identity to be used by the other party even before any communication starts. Otherwise, you will end up with a “one-round PAKE” that can’t be implemented in one round.

This is a higher level protocol consideration, but I don't see how an extra round would be needed since the server seems the client identity in the first message. It has to look up the password after all.

How about the initiator? Besides client-server, you also need to consider peer-to-peer which is a typical setting for a balanced PAKE. How do peers know each other’s identity beforehand?

If you have specific text that would be helpful I'm happy to add it post collecting all the comments.

I’m afraid I don’t have any specific text to propose. It’s not about tweaking text. It’s a fundamental issue that needs to be considered carefully, especially that what you are doing here deviates from the established practice in the past many years research on PAKE where the user identities are established in-flow rather than being presumed or “remembered”. It’s OK that you do something different, but extra care is needed. I can only suggest you to flesh out full details on “per-user M and N” and how it is integrated within the SPAKE2 protocol as a complete specification before it’s possible for others to review and comment on your proposal; or alternatively revert to the original (published) SPAKE2 scheme and acknowledge the limitation of using a global trusted setup.

---

From: "Hao, Feng" <[email-masked]>
Date: Thu, 15 Oct 2020 23:01:58 +0000

In reply to Watson's offlist questions and with his permission I post my response on the CFRG list, as I feel the discussion may be of wider interest.

On 15/10/2020, 01:28, "Watson Ladd" <[email-masked]> wrote:

    Offlist:
    > How about the initiator? Besides client-server, you also need to consider peer-to-peer which is a typical setting for a balanced PAKE. How do peers know each other’s identity beforehand?

    I'm really struggling to understand what is meant here.  Do you have a
    concrete application that can't work because of this limitation? In
    what world do you open a connection with no idea of who you will find
    on the other end?

The identity used in PAKE must be "exact", as it will be used to look up the shared password from a local database. You of course know where to open a connection, say if you want to connect to a site, you may use "example.com", "www.example.com", "example.com:80", and etc. All these will lead you to the same site. However, these strings are too ambiguous to be used as an identity. You have to agree with the other party which "exact" string you two shall use. This can't happen out of thin air; it needs two parties to communicate and negotiate. Your draft mentions using internet addresses for identities - however, IP or MAC addresses are unsuitable to be used as identities as they may change at any time. When they change, the user will get authentication failure even after they have used the correct password. This is clearly unacceptable. To sum up, the identity in PAKE is defined at the application level. It must NOT be mixed up with "identities" used in the lower layers in the TCP/IP stack, which serve different purposes.

    > I’m afraid I don’t have any specific text to propose. It’s not about tweaking text. It’s a fundamental issue that needs to be considered carefully, especially that what you are doing here devia…

    The global setup is still an option in this version. I can also add a
    per-application variant.

It's good to see that you're taking steps to address the trusted setup issue. However, the pre-application solution, as you currently describe in the draft, cannot be realistically implemented in one round. You may want to revise your claims. Also, technically speaking, what you propose in Section 5 is not a "variant" of SPAKE2, but a new protocol (which hasn't gone through any formal peer-review process). You should at least call it a different name to avoid mixing up with the original (peer-reviewed) SPAKE2.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 15 Oct 2020 18:17:32 -0700

> The identity used in PAKE must be "exact", as it will be used to look up the shared password from a local database. You of course know where to open a connection, say if you want to connect to a si…

I think application developers can solve this, and the details are
very specific to the higher level protocol.

In the context of e.g. HTTP one could specify the origin (is a
precisely defined string) and the username suitably normalized.

In the context of magic wormhole one could set A=B=part of the shared string.

In network access controls MAC addresses make sense. These are
examples. They aren't meant to say that you use network addresses for
everything. I'm happy to revise this text to be more clear.

>     > I’m afraid I don’t have any specific text to propose. It’s not about tweaking text. It’s a fundamental issue that needs to be considered carefully, especially that what you are doing here dev…

The only reason this option exists is previous comments in the working
group that such a form would be desirable.

Would removing this/retaining this and adding a per-application
variant be a way forward? Part of the issue here is that people have
mostly been fine with per-application and global variants, so I can't
really point to a deployment that I know of that works.

> It's good to see that you're taking steps to address the trusted setup issue. However, the pre-application solution, as you currently describe in the draft, cannot be realistically implemented in o…

I strongly question "cannot be realistically implemented". It would
seem to me that no PAKE that uses user identities would meet the
requirement you outline.

As for variant per-user M and N are within the scope of the security
analysis in reference MNVAR, which was published in CRYPTO 2020 in
combined form. Thank you for reminding me to update this reference:
the publication history is not obvious.

Sincerely,
Watson Ladd

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 16 Oct 2020 08:22:40 +0000

I think the best way forward would be that you code it up and show a realistic implementation that works in the way you describe. Then you can verify your claim yourself. Don't leave difficult implementation questions to developers!

Have a look at the original (published) SPAKE2 which you should already be familiar with and see how the identities are established in-flow there. Also have a look at PAKEs that have been implemented and used in realistic applications (EKE, SPEKE, J-PAKE) and see how the identities are established in-flow. More broadly, have a look at the nearly 30 years literature on PAKE, and the field of authenticated key exchange in general, and see how identities are defined and established in-flow as part of the key exchange process. If you believe "identities" can be remembered by the communicating parties without needing any communication, you need to show working examples.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 16 Oct 2020 19:43:09 -0700

> I think the best way forward would be that you code it up and show a realistic implementation that works in the way you describe. Then you can verify your claim yourself. Don't leave difficult impl…

I can write an implementation but you would then say no, we cannot
know A and B ahead of time or no, this  not in the client server case.
Do you have a good example of an application where this is an issue so
that I can understand what the constraints are? For example would
making M depend only on A and N depend only on B (or maybe it is the
other way around) so each side can prepare the flow without the other
identity resolve your issue?

> Have a look at the original (published) SPAKE2 which you should already be familiar with and see how the identities are established in-flow there. Also have a look at PAKEs that have been implement…

I think you agree with me that this is only an issue when both sides
simultaneously prepare and exchange the first flow.  This is quite an
exotic application. Even peer-to-peer apps typically have initiators
and responders.  Again, do you have real world protocols with the
constraints you describe?

Sincerely,
Watson Ladd

---

From: "Hao, Feng" <[email-masked]>
Date: Sat, 17 Oct 2020 09:51:32 +0000

On 17/10/2020, 03:43, "Watson Ladd" <[email-masked]> wrote:

I think that'll be a step in the right direction - towards establishing the identities in-flow. However, you need to fully specify all details. Note that ambiguous definition of the identity/naming is one of the main causes for the public-key protocols failures; see Principle 8 [1].

[1] Anderson, Needham, "Robustness principles for public key protocols," Crypto'95. 

It's NOT just an issue for the simultaneous exchange case, but applicable to all cases. An initiator can't know the "exact" identity to be used by the other party before the communication starts. If you force a party to "remember" all other parties' "exact" identities to be used for PAKE beforehand, you need extra storage and more importantly - if a party mis-remembers the other party's "exact" identity, or if a party's identity is changed but without this change being known to other parties, you get instant authentication failures even if the passwords used by both parties are exactly the same. This is not how a PAKE system should work!

---

From: Björn Haase <[email-masked]>
Date: Sun, 18 Oct 2020 22:54:05 +0200

Hello CFRG and Watson,

I have reviewed the draft and think that is quite clear and readable.

In the course of the detailed specification for CPace, we have just
stumbled over a possible implementation pitfall, that might also apply
in the same form to implementations for SPAKE2. The topic is likely only
a theoretical problem and might likely be classified as "overly picky".
I'm not aware of any feasable attack, but still it might be worth adding
a hint in the text.

The problem that we found out when digging through the details for CPace
is, that it is not uncommon for Diffie-Hellman secret scalar sampling
algorithms out in the wild to have a slight bias.

If you generate the secret scalars just by using a standard RNG, you
likely will get a uniform distribution between [0,2^l - 1) for some l
but not something uniform modulo the group order.

Your current specification is explicit and completely secure with
requiring that the secret scalars have to be sampled randomly *and*
*uniformly*:

>   To begin, A picks x randomly and uniformly from the integers in
>   [0,p), and calculates X=x*P and T=w*M+X, then transmits pA=T to B.
>
>   B selects y randomly and uniformly from the integers in [0,p), and
>   calculates Y=y*P, S=w*N+Y, then transmits pB=S to A.

In fact, I believe that many implementations for Diffie-Hellman will just generate a random number
and won't care about uniform distribution in [0,p). When scanning briefly, I've even seen
implementations having some bits set to a fixed value for Diffie-Hellman (also for short Weierstrass
curves, not only the clamping for X25519 and X448).
Typically such a structure (unlike the case for ECDSA signatures) should not be so critical for
ephemeral Diffie-Hellman.

Still for the case of SPAKE2 and CPace such a
bias could in theory allow for some sort of offline password test, since if X and Y only come from a
fraction of the entire group. If one has a distinguisher for the structure in the secret scalar,
one would be able to rule out some values of W*m and thus some passwords. (I don't actually believe that
such a distinguisher exists (it might have to solve the DDH?) in practice.)

 From an implementation-security point of view, I think that for most curves, one should probably
drop the uniformity requirement, as any additional calculation involving the secret scalar that one
implements for getting uniform distribution might leak information on the secret scalar...
 From a theory point of view, the transmitted points on the wire only include zero information if pA
pB could be any arbitrary point on the curve...

The possible implementation attack might generate more risk than advantage in practice.? We might
actually be better of with leaking a small, but negligible and un-exploitable amount of information.?

So, summing up, it might be worth discussing this topic and adding a recommendation. At least it might
be worth adding a note, that some Diffie-Hellman code might not actually consider the
uniformity requirement and come up with a suggestion how to realize the uniformity.

For curves such as Curve25519 I'd clearly suggest to drop the uniformity requirement because the order
of the curve is extremely close to a power of two that any problem could be ruled out.
I'm not so decided regarding curves such as Brainpool or P256 where the order is further away from a
power of two.

There it might be possible to recommend to sample some more bits and reduce the result modulo the
group order. In the Hash2Curve draft they are doing something similar IIRC (however regarding the
field primes).

As stated before, I think that either option would have its advantages. My gut feeling would be that
one might be better of with skipping the uniformity requirement.?

I'd be happy to discuss this topic in some more depth, because the exact same consideration applies to
CPace if it's used on curves different from Curve25519 (i.e. with p significantly different from 2^l).

Yours,

Björn.

Am 14.10.2020 um 08:06 schrieb Stanislav V. Smyshlyaev:
> draft-irtf-cfrg-spake2-13 ("SPAKE2, a PAKE"), that will end on October
> 29th 2020. If you've read the document and think that it is ready (or
> not ready) for publication as an RFC, please send a message in reply
> to this email or directly to CFRG chairs ([email-masked]
> <mailto:[email-masked]>). If you have detailed comments, these
> would also be very helpful at this point.
>
> https://mailarchive.ietf.org/arch/msg/crypto-panel/ZYeiXy4J5whuW2Thvqx1jcxq8Xs/.
>
>
> SPAKE2 was not selected as a result of a selection process, but since
> it predated the contest, the chairs decided not to stop it (and only
> it, not any other PAKEs), asking the authors to add the corresponding
> disclaimer in the draft: "This document predated the CFRG PAKE
> competition and it was not selected.".
>
>
> Thank you,
>

---

From: Björn Haase <[email-masked]>
Date: Mon, 19 Oct 2020 11:26:09 +0200

Hi Watson,

 > On 19.10. 2020 Watson Ladd wrote:

>Thank you! I will add such a warning to the security section and
>advise the use of either reduction of a double length string or
>rejection sampling.

Indeed you are right. With my mind focused on "constant time" implementation all the time, I
did discard the cheap option of the rejection sampling too early. In fact, we won't
leak any useful information with rejection sampling even if it's not constant time.

On the other hand there is a non-negligible risk of leakage when reducing a double-length string (in addition to the code bloat).

Therefore I'd advocate to recommend rejection sampling only and not double-length-string reduction
(and this should also be the way to do for CPace on the short-Weierstrass curves).

Still there might worth pointing to the risk of a possible variable-time issue when re-using code from libraries that were written for conventional DH key exchange. I have seen implementations that just set the top-most bit of the secret scalar (loosing half a bit of security) during the sampling process in order to make sure that the windowed scalar multiplication algorithm runs in constant time.

If we have such a scalar multiplication algorithm with a uniformly sampled scalar, there is some risk
of getting a variable execution time behaviour...

Maybe some note in the security section in the form:

"Some scalar multiplication algorithms designed for conventional ECDH key exchange might not run in constant time when using uniformly sampled secret scalars. Implementations should verify this aspect."

could be worthwile.

Yours,

Björn

---

From: Annie Yousar <[email-masked]>
Date: Mon, 19 Oct 2020 12:20:18 +0200

Hi Björn, Watson,
there are *two* common solutions for "re-uniforming" from [0,2^N-1] to
[0,q-1], where the bitlength of q is n, and N>n (usually N=n+64 or
greater).

Pick r randomly and uniformly from [0,2^N-1] and
1. compute r mod q, or
2. compute r*q div 2^N

If you put all the 2^N values in to q boxes with one of these methods
you get all boxes filled with 2^64 or 2^64+1 values. Hardly you will see
here the differences.
The second method uses one multiplication (shift is not counted) instead
of modulo operation and may be a bit faster and easier to implement than
rejection sampling.

/Ann.

Am 2020-10-19 um 11:26 schrieb Björn Haase:
> On the other hand there is a non-negligible risk of leakage when
> reducing a double-length string (in addition to the code bloat).
> 
> Still there might worth pointing to the risk of a possible variable-time
> issue when re-using code from libraries that were written for
> conventional DH key exchange. I have seen implementations that just set
> the top-most bit of the secret scalar (loosing half a bit of security)
> during the sampling process in order to make sure that the windowed
> scalar multiplication algorithm runs in constant time.
> 
> "Some scalar multiplication algorithms designed for conventional ECDH
> key exchange might not run in constant time when using uniformly sampled
> secret scalars. Implementations should verify this aspect."
> 
> could be worthwile.
> 
> Yours,
> 
> Björn
>