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

From: Greg Hudson <[email-masked]>
Date: Tue, 12 May 2015 14:51:02 -0400

SPAKE preauth[1] will use the client long-term key as input to the
SPAKE2 algorithm[2] as the shared secret w value.  The current draft
doesn't say how to derive the w value, and the SPAKE2 draft doesn't say
much either (just "Typically w will be the hash of a user-supplied
password, truncated and taken mod p").  The proof of concept just
converts the bits of the key into a bignum, which doesn't match our
usual cryptographic practices.

I expect we will want to start by generating some uniformly distributed
bytes using PRF+(k, "someconstant") with an output length dependent on
the curve.  Beyond that point, I think it will depend on the curve type.

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.

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.

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

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.

[1] https://tools.ietf.org/html/draft-mccallum-kitten-krb-spake-preauth-00
[2] https://tools.ietf.org/html/draft-irtf-cfrg-spake2-01

---

From: Nico Williams <[email-masked]>
Date: Tue, 12 May 2015 16:47:41 -0500

> the input are forced to specific values.

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

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

> need to make sure the scalar value is divisible by the cofactor?  This

Yes.

> preauth work with arbitrary non-CFRG curves without additional per-curve

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

> since it operates on a secret input.

Yes.

Nico
--

---

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 13 May 2015 09:51:31 -0400

> Yes, this is really a question for Watson Ladd in particular and 

I have CC'd Watson Ladd.

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

> > need to make sure the scalar value is divisible by the cofactor? 

The SPAKE draft covers this scenario.

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

>  - make_point(x, y)             -> point

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

> perhaps for signatures too, though that's a debate that hasn't 

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.

> > since it operates on a secret input.

+1

---

From: Watson Ladd <[email-masked]>
Date: Wed, 13 May 2015 07:17:59 -0700

>> Yes, this is really a question for Watson Ladd in particular and

The question of whether or not a protocol requires a uniformly
determined scalar is not a function of the curve, but the protocol.
EdDSA is much more stringent than key agreement, for instance: the
same scalar conversion code is dangerous to use with it.  Of course,
the curve doesn't tell you how to sample values: that's an
implementation detail and the there is nothing about P256 or P521 that
stops you from doing it by modular reduction of values only slightly
larger than the curvesize.

>> mapping from the long-term key to w, provided there's a way to

w is not distributed uniformly: far from it. The question of how far
from uniform x may be distributed is a subtle one, but my guess is
that even gross deviations from uniformity are fine, so taking a bunch
of bytes mod the curve order is ok. But rejection sampling or modular
reduction of longer strings are both easy to implement to sidestep
this issue.

>> perhaps for signatures too, though that's a debate that hasn't

SPAKE2 requires addition be supported. That rules out Kummer lines.
The CFRG has not specified a model and how to encode points on that
for addition to work. When they do I will modify the draft
accordingly.

However, I don't understand why the above abstraction isn't an
implementation detail only. All one has to provide to use this draft
are two generators and how to encode group elements. The algorithms
for addition, multiplication etc. will be documented in the CFRG
eventually. It's true that many groups only come with one canonical
generator, but any sort of hashing method will give you two
generators.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Nico Williams <[email-masked]>
Date: Wed, 13 May 2015 11:05:51 -0500

> w is not distributed uniformly: far from it. The question of how far

That depends on how its salted.  For our purposes, in practice it's not.

> reduction of longer strings are both easy to implement to sidestep

That's what I thought.

> generator, but any sort of hashing method will give you two

It absolutely could be an implementation-only abstraction.  If it will
be useful for many implementations though, it'd be useful to write that
up.  In particular, adding curves to an implementation will be easy if
there is such an abstraction internally.

(This was in response to an off-list question by an implementor about
how to make it easy to add curves to their implementation given that
they are using OpenSSL, without first having to add them to OpenSSL.
Two simple answers are: don't, or add such an abstraction.)

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Wed, 13 May 2015 21:15:19 -0700

> That depends on how its salted.  For our purposes, in practice it's not.

Not true: w comes from a much smaller list of values. If it was
uniformly distributed over a wide range, we could use it as a key
directly.

> there is such an abstraction internally.

Many implementations already have such a layer. I don't see how it's
useful to write up: it's obvious, and doesn't affect interop.

> Two simple answers are: don't, or add such an abstraction.)

I believe OpenSSL does permit specifying parameters of arbitrary
Weierstrass curves. In practice I don't know how useful that is. Or am
I misunderstanding the question?

Sincerely,
Watson Ladd

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 14 May 2015 00:19:40 -0400 (EDT)

> uniformly distributed over a wide range, we could use it as a key

In the scheme kitten is considering, w is an existing kerberos long-term
(password-derived) key, so at least 128 bits and with no clear structure.

-Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 14 May 2015 10:39:31 -0400 (EDT)

> (password-derived) key, so at least 128 bits and with no clear structure.

Now that I am awake (i.e., not falling asleep), I should clarify that w is
planned to be the output of a KDF or PRF construction keyed on the
kerberos long-term key I mentioned, not the key itself.  (I don't think
this was very clear in the -00, though, and we discussed it on the list a
fair amount.)

To give something of a summary of the propsal with background from
kerberos:

In kerberos, we have password-derived keys that are used for initial user
authentication; the KDC ends up sending a response with session key,
encrypted in the long-term password-derived key.  (Sometimes the user
sends a timestamp encrypted in that key as "pre-authentication".)
Regardless, an attacker can easily get a ciphertext in this
password-derived key, and since some users will always pick weak
passwords, some of this traffic will succumb to a brute-force guessing
attack.

The proposal in draft-mccallum-kitten-krb-spake-preauth is to use SPAKE(2)
as a zero-knowledge proof, not of the password itself, but rather of the
password-derived kerberos key, so that existing kerberos deployments can
seamlessly be upgraded to use this new preauthentication scheme which does
not expose ciphertexts in the password-derived key to an attacker.  As an
additional feature, it allows for a second factor to be included in the
key exchange in a fashion such that an attacker trying online guessing
cannot tell which of the password or second factor was incorrect.  So, the
"password" input to spake is not the user's actual password, but rather
this kerberos long-term password-derived key, which has already been
through a salted PBKDF2 (or similar, for older enctypes).  As is normal
for use of long-term kerberos keys, it will go through a key-derivation
step before being used.

Hopefully that gives some background to the questions we were asking for
input on.

-Ben

---

From: Nico Williams <[email-masked]>
Date: Thu, 14 May 2015 10:47:22 -0500

> uniformly distributed over a wide range, we could use it as a key

For Kerberos (the context in which we're discussing SPAKE2) w would be
derived from user principal long-term keys, which are basically a
PBKDF2() application to the password and salt.  The salt can in
principle be uniformly distributed and randomly chosen, but it is
public, so w has no more entropy than the password, but w can be as
uniformly distributed as the salt.

In practice the salt is not chosen randomly but derived from the user's
principal name.  So w does not (will not) be uniformly distributed.

In any case, there's a big difference between "uniformly distributed"
and "difficult to guess".  We want a PAKE precisely because user
principal long-term keys are derived from simple passwords and used to
encrypt messages which are then subject to off-line dictionary attacks.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Thu, 14 May 2015 10:52:39 -0500

> useful to write up: it's obvious, and doesn't affect interop.

True.  (But we must have a point representation, which per-CFRG is now
part of each curve's specification.  We have a point representation for
Curve25519 for DH, but not yet for point addition.)

> I misunderstanding the question?

The context is an implementation of Kerberos that would like such an
abstraction so it can use curves not yet supported by OpenSSL, in
particular Curve/Ed25519.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 14 May 2015 08:54:39 -0700

> passwords, some of this traffic will succumb to a brute-force guessing

Yes, which implies that it is not uniformly distributed over the whole
domain of strings of the length of w. Uniform distribution means
uniform: if it only ever takes on values in some subset, it isn't
uniform. The fact that guessing attacks are possible demonstrates,
that after conditioning on public values, it isn't uniform over the
entire range.

---

From: Nico Williams <[email-masked]>
Date: Thu, 14 May 2015 11:10:56 -0500

> that after conditioning on public values, it isn't uniform over the

OK, fair enough, but what about x.  How critical is it that it be
uniformly distributed?  You answered "The question of how far
from uniform x may be distributed is a subtle one, but my guess is
that even gross deviations from uniformity are fine, so taking a bunch
of bytes mod the curve order is ok."  Can you refine this answer?

My guess is that indeed, x's uniformity is not that important, because
if it were a well-known constant then this protocol devolves into one
where the attacker still has to mount an off-line dictionary attack in
order to recover w and session keys, so as the range of x choices
improves, the attacker's position worsens.  But if we add in timing side
channels then x's "gross deviation" from unifomity might yield more
information, no?

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Thu, 14 May 2015 11:26:11 -0500

OTOH, I think we need timing side-channel-free curve implementations
anyways, which means that as long as x is chosen randomly and somewhat
uniformly, it will do.

---

From: Simo Sorce <[email-masked]>
Date: Mon, 18 May 2015 06:17:26 -0400 (EDT)

----- Original Message -----
> From: "Nico Williams" <[email-masked]>
> To: "Watson Ladd" <[email-masked]>
> Cc: [email-masked]
> Sent: Thursday, May 14, 2015 5:47:22 PM
> Subject: Re: [kitten] SPAKE preauth: generation of SPAKE2 secret input
> 

This is not so clear cut, and depend on deployments.
A truly random "special" salt can be used (and in fact we use it in FreeIPA),
and there is also the sad situation with the RC4-HMAC key that is not salted
at all ...

This is just nitpicking, but hows that we have a wide range of different keys
we may end up using in deployments and we cannot assume uniformity even if in
some cases we may get quite close.

Simo.

> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten
> 

--

-- 
Simo Sorce * Red Hat, Inc. * New York

---

From: Greg Hudson <[email-masked]>
Date: Tue, 19 May 2015 12:14:46 -0400

Based on the results of this discussion, here is the wording I came up
with for my pull request.  In the prerequisites section:

   Both KDCs and clients MUST implement one or more groups for which the
   discrete logarithm problem is hard, each with an corresponding object
   identifer.  Group object identifiers MUST refer to one of the
   following:

   o  One of the eight elliptic curves specified in [SEC2] section 2,
      using the corresponding object identifier from appendix A.2.1.

   o  A group with an unambiguous specification for representing group
      elements as octet strings, and an unambiguous specification for
      converting an octet string of a specific length into an integer
      for use as a scalar multiplier.

and then in a new section titled "SPAKE Parameters and Conversions":

   The SPAKE algorithm requires a shared secret input w to be used as a
   scalar multiplier (see [I-D.irtf-cfrg-spake2] section 2).  This value
   MUST be produced from the client principal's long-term key as
   follows:

   1.  Determine a scalar octet string input length for the chosen
       group.  For SEC 2 curves over a prime field F(p), this is
       ceil(log2(p)/8).  For other groups, this length is specified by
       the group.

   2.  Produce an octet string of the above length with PRF+(K,
       "SPAKEsecret"), where K is the long-term key and PRF+ is defined
       in [RFC6113] section 5.1.

   3.  If the chosen group is secp521r1, set the high seven bits of the
       first byte to 0 so that there are at most 521 significant bits in
       the octet string.

   4.  For SEC 2 curves, decode the octet string as a big-endian
       positive integer as specified in [SEC1] section 2.3.8.  For other
       groups, decode the octet string as specified by the group.

Salient points:

* SEC 2 curves over Fp (which include NIST P-256/P-384/P-521) get to use
existing OIDs with conversions specified in this draft, using SEC 1
encoding primitives.  Other groups need to use an OID which
unambiguously specifies the needed conversions.  I expect the
forthcoming CFRG curves to slot in here, although I'm not sure if they
plan to designate OIDs for their curves.

* Because the eight SEC 2 curves all have cofactor 1, we don't have to
worry about cofactors in the conversions we specify.  Except for
secp521r1, they all use primes close to a power of 2^8.

* The w values won't be uniformly distributed even if the long-term key
is.  But as Watson noted, SPAKE doesn't assume that w is uniformly
distributed.

* A small proportion of w values will be larger than the group order.
Implementations need to be able to handle these values correctly and
without side channels.  I will try to make a note of this in the
security considerations, and will try to make sure that there are test
vectors exercising this possibility.  OpenSSL contains P-256 and P-521
implementations which are supposed to be constant-time if the input
bignum doesn't contain more than 256 or 521 significant bits respectively.

* It's possible, though vanishingly unlikely, for w to be equal to 0 or
to the group order.  I believe all of the computations should work in
this case, so there is no need to reject those values.

---

From: Nico Williams <[email-masked]>
Date: Tue, 19 May 2015 14:01:09 -0500

> plan to designate OIDs for their curves.

Notionally each curve should have its own conversions.

> secp521r1, they all use primes close to a power of 2^8.

Sure.

> bignum doesn't contain more than 256 or 521 significant bits respectively.

We do have to specify what this conversion is.  We can't merely refer to
OpenSSL.

If need be use w' = truncate(H(w), floor(log2(group_order / cofactor))).
We don't need w or w' to be particularly strong (that's the point of
using a PAKE), so this should be just fine.

> this case, so there is no need to reject those values.

Agreed.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Tue, 19 May 2015 12:09:20 -0700

>       for use as a scalar multiplier.

My draft does not have M and N for binary curves. There are only three
curves in my draft IIRC. My draft completely describes each parameter,
and gives it a name.

>        groups, decode the octet string as specified by the group.

I feel as though I should rework the draft to specify the length of an
octet string and how to treat it, but I think this was already done
elsewhere. (I.e. step 2 would need to be done, but all others in my
draft)

> plan to designate OIDs for their curves.

OIDs are not unique per object.

> bignum doesn't contain more than 256 or 521 significant bits respectively.

The easy fix here is to truncate.

---

From: Greg Hudson <[email-masked]>
Date: Tue, 19 May 2015 19:51:07 -0400

> curves in my draft IIRC. My draft completely describes each parameter,

I've been operating under the assumption that M and N can be computed
for other curves as long as they have assigned OIDs.  The risk of
interoperability failures from people getting it subtly wrong might be
kind of high, though.

I don't have an objection if we want to limit ourselves to curves
explicitly listed in the spake2 document (or follow-on SPAKE2
documents), but it's a greater departure from Nathaniel's intent.

F2m curves (I assume that's what you mean by "binary curves") are
documented in SEC 2 section 3, not in section 2.  I don't think we need
to support those.

>>    1.  Determine a scalar octet string input length [...]
>>    2.  Produce an octet string of the above length with PRF+ [...]
>>    3.  If the chosen group is secp521r1, set the high seven bits [...]
>>    4.  For SEC 2 curves, decode the octet string as a big-endian [...]

> elsewhere. (I.e. step 2 would need to be done, but all others in my

There's RFC 6979 section 3.2, but it would introduce a significant side
channel if applied here.

I would be happy to delegate steps 3 and 4 to another document if there
is a suitable reference.

>> [...] I expect the

Can you elaborate on this?

>> Implementations need to be able to handle these values [...]

> The easy fix here is to truncate.

You mean lop off the high bit?  We could do that, but I'm not sure if
it's needed.  I think 25519's scalar preprocessing generates scalar
values up to eight times the subgroup order, for comparison.
(2^254+(2^251-1)*8 / 2^252+27742317777372353535851937790883648493 ~= 8.)

> We do have to specify what this conversion is.  We can't merely refer to

I'm not referring to OpenSSL for semantics.  Mathematically, scalar
multiplication within a group is defined for any non-negative value of
the scalar.  If an implementation can't handle values above a certain
size, or has side channels for values above a certain size, that is an
implementation limit.  I just brought up OpenSSL as an example of
implementation limits compatible with my proposed method.

> using a PAKE), so this should be just fine.

I'm not sure why we would want to introduce another hash invocation.  w
is already the output of a PRF; we can truncate it to any desired size.