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

[Watson Ladd <[e-mail]>]

On Feb 13, 2015 7:30 AM, "Nathaniel McCallum" <[e-mail]> wrote:
>
> On Thu, 2015-02-12 at 07:44 -0800, Watson Ladd wrote:
> > On Thu, Feb 12, 2015 at 5:25 AM, Nathaniel McCallum <
> > [e-mail]> wrote:
> > >
> > >
> > > ----- 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 think how we generate the points doesn't matter, so I'll follow
> > your suggestion. Is this the list of generated points you sent me
> > earlier?
> >
> > Note that complaints about range etc. don't really matter. For
> > instance, over primes, we just take 2 and 3.
>
> No, it is not the same list. I don't really care about the method that
> is used (mine or another). I just want it to be:
> 1. secure
> 2. easy to implement on all major crypto libraries
> 3. establishing an unambiguous method for future curves

At this point you've sent me four files, one called
SPAKEConstants.java in an email saying it was slightly different from
the previous one, and one also called SPAKEConstants.java accompanied
with two CSV files, showing that both OpenSSL and Bouncycastle
produced the same results. Which one implements the method you
actually want?

What do you mean by secure?

As for point 3, it's worth noting that you haven't dealt with points
not of prime order or the possibility that the curve isn't specified
in Weierstrass form, or doesn't use SEC1 format.

>

> > > > 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.
> >
> > This is about a different issue, which you pointed out. In the
> > current version, K is a shared group element, and the generated K is
> > a hash of K and the values used to generate it. But in some cases we
> > can trust the higher level protocol to do that hashing, such as TLS
> > 1.3. In those cases having to retain the values sent adds complexity.
> >
> > I think it will be clearer when I upload the new version what I mean.
>
> Sure. But I don't see that having anything to do with how we generate
> the constants.

Notice how you started this thread with two comments on the draft? I'm
addressing both of them.

>
> > > > 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.
> >
> > So you would be happy if I mandated hashing the values used to
> > generate K into K?
>
> I'm not talking about hashing K. I'm talking about generating
> constants.
>
> > > > 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.
> >
> > Are you talking about the point generation? Because that isn't
> > actually a requirement.
>
> I'm talking about the M/N constants.

And it's not actually a requirement that we get all possible points.
We just need two points, and a method that isn't "here, take these".

>
> > > 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.
> >
> > If someone can compute a discrete logarithm, you probably shouldn't
> > use that group.
>
> Fair enough.
>
> > > > 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.
> >
> > Despite much work, I have not been able to find a reference. It does
> > appear in a draft book.
>
> I sent him an email asking for a reference. He has not (yet) responded.

Thanks for doing that. Maybe there is a paper that calls it something
different out there?

Bottom line: I'll upload a new version this weekend, and see if that
clears some of this up.

Sincerely,
Watson Ladd

>
> Nathaniel
>