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

[Nathaniel McCallum <[e-mail]>]

----- Original Message -----
> On Tue, Feb 10, 2015 at 4:57 AM, Nathaniel McCallum
> <[e-mail]> wrote:
> > On Wed, 2015-01-28 at 13:12 -0500, Nathaniel McCallum wrote:
> >> 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.
> >
> > Attached is a (slightly different) method implemented in Java using
> > Bouncy Castle. It depends on no system internals and only one hash. It
> > should be sufficiently simple to grok. A description is given in a
> > comment in the top of the file. This method is easily repeatable on
> > every crypto-system I have tried (including both OpenSSL and libnss).
> 
> I read that file and description of the method. It depends on details
> of SEC1 encoding, as it mungs the hash function value in strange ways.
> Stretching the hash function is ad hoc.

I'm not thrilled about the stretching of the hash function. However, without it we have a significant distribution problem. SHA512 into a curve >511bits has insufficient range.

An arbitrary sized Keccak may be a good fit here. It is implemented in Bouncy Castle, but only for the SHA3 sizes. Neither OpenSSL nor libnss support it yet.

> It's not as easy to describe as "generate a random x coordinate taking
> bytes from HKDF seeded with this particular string, then see if it is
> on the curve, and if so take the smaller y value". I'll implement that
> this weekend.

Except that this is (almost) precisely what the SEC1 encoding hack does. It takes the x coordinate from bytes from the hash. Your proposal (to take the smaller hash value) reduces distribution by one bit. My methodology has an advantage of range here.

The other problem is that standard libraries don't appear to expose similar methods for the type of mechanism you are proposing. This is precisely why I implemented the SEC1 hack: it can be easily implemented by all libraries.

The SEC1 hack isn't dirty because both the point encoding and the hash are octet strings. The only difference is that the SEC1 encoding has some magic bits. We just toggle those. This proposal isn't crazy.

> I've decided to modify the key generation procedure to make it
> integrate better into higher-level protocols,

What in the world does this mean? I'm an experienced protocol implementer and I seriously have no idea what you're talking about here. If you have a proposal, please state it explicitly so it can be properly reviewed.

> but will preserve the current method as an option,

There is no need to do this. Let's agree on a method and all use it. No backwards compatibility is a requirement at this point. I'm happy to update krb5-pake to whatever method we decide on. I just want it to happen soon so that we can start the Kerberos PAKE Preauth Mechanism draft.

> and try to come up with security
> considerations information that drives home how critical it is to pick
> the right one.

The most important consideration is range. All possible x/y values need to be possible outputs of the hash value.

Another idea I had was to have a "version" qualifier. Basically, it is just a counter value used in generating the seed. The purpose is that if a constant is successfully attacked, we can just increment the counter to the next number and get two new seeds.

> Does this seem good to everyone?

It does sound (mostly) good. I'd also like to see the draft include Boneh's (S)PAKE2+ augmented variant.

Nathaniel