Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input

[Nico Williams <[e-mail]>]

On Tue, May 12, 2015 at 02:51:02PM -0400, Greg Hudson wrote:
> For CFRG curves (when they exist), we'll be done; CFRG curves accept
> uniformly distributed bytes as input and force them into appropriate
> form for a scalar.  For instance, for curve25519/ed25519, five bits of
> the input are forced to specific values.

Will that be true for other CFRG curves?  I hope so, that'd be nice.

> For P-256, P-384, and P-521, we need a large integer in the range of the
> group order, which is not bit-aligned.  The simplest option is to just
> decode the bytes as a bignum and let the resulting distribution of
> scalar values be somewhat non-uniform (a small fraction of scalar values
> are effectively twice as likely as the other ones).  I don't think this
> slight non-uniformity is a problem, and so far the people I have talked
> to have agreed.  But I'd like to check here, and will probably also need
> to solicit opinions from Walter Ladd and maybe others.

Yes, this is really a question for Watson Ladd in particular and CFRG in
general.

My take is that the public values being of the for xG + wM, where x
should be a randomly and uniformly chosen scalar, the xG term will cause
the public value to be as uniformly distributed as x regardless of how
non-uniform w might be.  So I think there's no harm in picking a simple
mapping from the long-term key to w, provided there's a way to abstract
this (see below).

However, don't you run into the same problem when generating the
ephemeral scalars?  Or does OpenSSL provide a function for that?  If
distributions of both w and x are uniform, then I don't know if x's mere
randomness is enough (again, a question for Watson L.).

> I don't know if there are likely to be additional considerations for
> other old curves.  For example, if the curve cofactor is not 1, do we
> need to make sure the scalar value is divisible by the cofactor?  This

Yes.

> ties into the larger question of whether we can really make SPAKE
> preauth work with arbitrary non-CFRG curves without additional per-curve
> specification.

Can we define a curve abstraction that provides what we need?

 - random2scalar(r)             -> scalar
 - randomscalar()               -> scalar
 - dh(s)                        -> public   # for Curve25519-like curves
 - dh_sharedsecret(s, public)   -> secret   # for Curve25519-like curves
 - scalarmult(s, point)         -> point    # generic; points are opaque
 - add(point1, point2)          -> point
 - sub(point1, point2)          -> point
 - encode_point(point)          -> octet string
 - decode_point(octet string)   -> point
 - point_x(point)               -> x scalar
 - point_y(point)               -> y scalar
 - make_point(x, y)             -> point
 ...

Ideally CFRG should be providing this for its curves.  It should be
pssible to implement such things for other curves too.

Some of the above abstractions are a consequence of CFRG electing to
leave point encoding to each curve for DH (and, if it were useful,
perhaps for signatures too, though that's a debate that hasn't happened
yet).

> Whatever we do needs to be well-specified (or we will have
> interoperability issues), and cannot contain inherent timing channels
> since it operates on a secret input.

Yes.

Nico
--