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

[Nathaniel McCallum <[e-mail]>]

On Fri, 2015-02-13 at 08:04 -0800, Watson Ladd wrote:
> 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?

The email with CSVs never made it to the list because they were too 
large. The last email which contains only SPAKEConstants.java is, I 
think, the best method so far. It is on the list and is publicly 
reviewable.

> What do you mean by secure?

A prescriptive method with adequate public review.

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

Agreed. I don't plan to address this. Feel free to.

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

Mea culpa. I misunderstood you from the beginning.

Yes, the transition from the calculated shared elliptic curve point to 
a shared key should be generic enough to incorporate other protocol 
concerns. Agreed.

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

Agreed.

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

Sounds great!