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

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 28 Jan 2015 10:53:08 -0500

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 28 Jan 2015 08:06:36 -0800

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

> string onto the curve. I am definitely open to alternatives.

Do they matter? This only needs to happen once.

> since I'm not sure either of the existing methods will work for

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.

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.

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

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 28 Jan 2015 13:12:17 -0500

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

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

> solutions of the quadratic.

Sure, it could work.

> that I don't know the discrete logarithms, which the method being used

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.

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

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 28 Jan 2015 11:23:21 -0800 (PST)

On Wed, January 28, 2015 7:53 am, Nathaniel McCallum wrote:
[snip]
> string onto the curve. I am definitely open to alternatives.

  Have you considered the technique from "An Indifferentiable Hash
Function into Elliptic Curves" by Coron and Icart?

  regards,

  Dan.

---

From: Nathaniel McCallum <[email-masked]>
Date: Wed, 28 Jan 2015 14:34:15 -0500

> Function into Elliptic Curves" by Coron and Icart?

I have a copy of the paper and have glanced at it briefly. I have not
had time to implement it. Nor am I sure how difficult this would be to
do with OpenSSL.

Nathaniel