Re: [Cfrg] Using draft-irtf-cfrg-spake2-00 in Kerberos Preauth

[Nathaniel McCallum <[e-mail]>]

On Wed, 2015-01-28 at 08:06 -0800, Watson Ladd wrote:
> On Wed, Jan 28, 2015 at 7:53 AM, Nathaniel McCallum
> <[e-mail]> wrote:
> > I've only just now joined the mailing list, so I'm a bit late to the
> > party (though I see my name has been brought up in the previous
> > discussions).
> >
> > I am currently implementing a PAKE preauthentication mechanism for
> > Kerberos. https://github.com/npmccallum/krb5-pake
> >
> > One of the PAKEs we have chosen to use is SPAKE2. The aforementioned
> > program that I am using to generate M and N constants is here:
> > https://github.com/npmccallum/krb5-pake/blob/master/src/pake/spake_constants.c
> >
> > This program uses two seed strings:
> >  "OID point generation seed (M)"
> >  "OID point generation seed (N)"
> >
> > OID is replaced by the OID of the curve. Since some curves have multiple
> > aliases, the use of OIDs removes any ambiguity to the seed.
> >
> > The method use to generate the constants is fairly similar to that used
> > by Chromium, but differs in several ways:
> > http://src.chromium.org/viewvc/chrome/trunk/src/crypto/p224_spake.cc
> >
> > First, we calculate the length of the encoded value of a single point on
> > the curve. I'll call this $CURVE_SIZE.
> >
> > Second, we determine which is the smallest hash function (of SHA-1,
> > SHA-2-*) which outputs at least $CURVE_SIZE bytes. So, for instance,
> > given P256, SHA-2-256 will be used. If no hash function is larger than
> > $CURVE_SIZE, we use the largest hash. For example, P521 uses SHA-2-512.
> >
> > Third, we generate the seeds by filling in the OID value.
> >
> > Fourth, we begin a recursive process whereby we hash the seed (or the
> > previous hash of the seed) until the output of the hash yields an X
> > coordinate on the curve. The Y coordinate (+/-) is chosen using the
> > right-most bit of the hash.
> 
> I don't think this is what your C code is doing, or if it is, I can't
> figure it out because of the way it uses OpenSSL internals.
> I may try coding that up in SAGE and seeing if it agrees in the
> output. (In particular I think the first byte of the digest might get
> mangled to have the decode function work).

What internals?

EC_GROUP *g = EC_GROUP_new_by_curve_name(NID_secp521r1);
EC_POINT *p = EC_POINT_new();
BIGNUM *x = BN_new(hash(seed));
int y = seed[-1] & 0x1; // Last bit
EC_POINT_set_compressed_coordinates_GFp(g, p, x, y);

That seems straightforward to me.

> > This methodology differs from the Chromium methodology in three ways:
> > 1. The hash function is variable.
> > 2. OIDs are used instead of a friendly name (like P256).
> > 3. We generate M/N for all curves supported by OpenSSL at build time.
> >
> > In short, this is just a poorly devised method for hashing a constant
> > string onto the curve. I am definitely open to alternatives.
> 
> Do they matter? This only needs to happen once.

No, not really. By "poorly devised" I simply meant it is the
"hunt'n'peck" approach.

> > One other important difference of our implementation from
> > draft-irtf-cfrg-spake2-00 is that we do not use the SPAKE2 derivation
> > hash, but rather use a variant of it. The purpose of this is to have a
> > generic derivation which:
> > 1. Works for all PAKE types (notably, JPAKE).
> > 2. Includes all public negotiation data to provide protection from
> > downgrade attacks.
> >
> > Specifically, our derivation step includes:
> > * Client identity
> > * Server identity
> > * Recursive hash of all negotiation data (including SPAKE's public keys)
> > * The secret (w)
> > * The derived session key (K)
> >
> > So, all that to say this...
> >
> > As I see it, two improvements are needed to the draft.
> >
> > First, the method to calculate M/N needs to be clearly laid out. If an
> > existing method is chosen (Chromium's/krb5-pake's), I feel that using
> > curve names is not sufficiently unambiguous. Alternatively, a new method
> > of producing M/N constants could be devised. The latter may be necessary
> > since I'm not sure either of the existing methods will work for
> > Curve25519.
> 
> Why won't the same method work for the Edwards curve? I pick x by
> incrementing until there is a valid y value, then pick one of the two
> solutions of the quadratic.

Sure, it could work.

> Why do we need to be completely unambiguous? The only thing we need is
> that I don't know the discrete logarithms, which the method being used
> now already achieves.

Um. Because its a draft? As an implementer of several RFCs, ambiguity
always comes to bite me later.

In this case, the RFC will define a table of common constants. But as
soon as someone does another curve not in the table there will be two
different constants because the aliases are different. I'd rather see
the draft define a *method* for defining constants and then provide a
list of several common values. Curves that do not have constants defined
in the RFC can then follow the method to arrive at the same constants.

> > Second, the "real" SPAKE algorithm is the generation of K. The
> > derivation step is a common step that should be done for all PAKEs and
> > is not SPAKE specific. This derivation step is usually application
> > specific. While it may include other data, it must include at least the
> > following in some form:
> > * Client identity
> > * Server identity
> > * All publicly exchanged group members (in SPAKE: T and S)
> > * The secret (w)
> > * The derived session key (K)
> 
> I disagree with this change for the following reason: hashing the
> transcript needs to be done anyway. But some protocols don't do it
> correctly. In those protocols we derive additional protection from
> defining K to already include the data from SPAKE2.

Just because some people do derivation incorrectly is not a valid reason
to dictate where derivation must occur.

All other PAKEs provide a computed session key which is a group member
and derivation is left to the implementer. Making SPAKE2 different in
this regard is a burden on projects which intend to allow
interchangeable PAKE algorithms.

Additionally, there are caveats regarding state-tracking. When stateless
servers are doing a PAKE exchange, the private values of the PAKE
(regardless of the PAKE) are typically sent in an encrypted cookie along
with a rolling transcript hash. The rolling transcript hash already
contains the public key data; but not in a form which can be provided to
SPAKE2's derivation. This would mean that SPAKE2 would require the
encrypted cookie to contain the private key, the transcript hash (which
includes both public keys) AND one or two public keys (depending on who
starts the PAKE).

Let's look at one example of this. The use of SHA-2-256 with P521 will
be a common scenario. The transcript hash will be 32 bytes. Depending on
who initiates the conversation and the encoding of the points, retaining
the points for later derivation can cause the size of the cookie to grow
substantially (upwards of 8x against the transcript size). And if the
addition of the public key(s) causes the cookie data to be larger than
the block size of the encryption, now you get to send a whole new block
over the network filled with padding.