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

[Nathaniel McCallum <[e-mail]>]

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.

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.

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.

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)

Nathaniel