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

[Björn Haase <[e-mail]>]

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:
>
> 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 ([e-mail]
> <mailto:[e-mail]>). 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
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg