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

[Nathaniel McCallum <[e-mail]>]

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

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

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

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

Nathaniel