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

[Nathaniel McCallum <[e-mail]>]

On Tue, 2015-05-12 at 16:47 -0500, Nico Williams wrote:
> 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.

I have CC'd Watson Ladd.

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

OpenSSL provides a function for generating a random scalar uniformly
distributed within a given range. It works by generating n bytes of
random data, where n is the smallest number of bytes that can
represent the range. Then it checks to see if the generated random
data is within the range. If it is, the value is returned. If it is
not, it repeats the process until an appropriate random value is found.

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

The SPAKE draft covers this scenario.

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

Specifying an abstraction this tightly removes the possibility for at
least one optimization. I'm not sure I want to get into the
abstraction business.

>  - point_x(point)               -> x scalar
>  - point_y(point)               -> y scalar
>  - make_point(x, y)             -> point
>  ...

I'm not sure what these are even used for.

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

I'm not sure this is necessary. I think it is sufficient to specify
that the group OIDs MUST define things like point encoding and M/N
values or MUST implicitly use SEC1 compressed and the M/N values
generated using the technique in the SPAKE draft.

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

+1