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

From: Nathaniel McCallum <[email-masked]>
Date: Tue, 10 Feb 2015 13:57:42 +0100

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 <
> > [email-masked]> 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).

Nathaniel

---

From: Watson Ladd <[email-masked]>
Date: Wed, 11 Feb 2015 08:21:36 -0800

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

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.

I've decided to modify the key generation procedure to make it
integrate better into higher-level protocols,  but will preserve the
current method as an option, and try to come up with security
considerations information that drives home how critical it is to pick
the right one.

Does this seem good to everyone?

Sincerely,
Watson

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

---

From: Watson Ladd <[email-masked]>
Date: Thu, 12 Feb 2015 07:44:14 -0800

On Thu, Feb 12, 2015 at 5:25 AM, Nathaniel McCallum
<[email-masked]> wrote:
>
>
> ----- Original Message -----
> 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.
>
> 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.

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

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

>
>> and try to come up with security
> 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.

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

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

---

From: Nathaniel McCallum <[email-masked]>
Date: Thu, 12 Feb 2015 08:25:04 -0500 (EST)

----- Original Message -----

Nathaniel

---

From: Nathaniel McCallum <[email-masked]>
Date: Fri, 13 Feb 2015 10:30:41 -0500

On Thu, 2015-02-12 at 07:44 -0800, Watson Ladd wrote:
> On Thu, Feb 12, 2015 at 5:25 AM, Nathaniel McCallum <
> > > On Tue, Feb 10, 2015 at 4:57 AM, Nathaniel McCallum <
> > > > > > > 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
> > > > > > > 
> > > > > > > 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.
> > > > > > > 
> > > > > > > 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
> > > > > > > (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?
> > > > > 
> > > > 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?
> 

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

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

Sure. But I don't see that having anything to do with how we generate 
the constants.

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

I'm not talking about hashing K. I'm talking about generating 
constants.

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

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

Fair enough.

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

I sent him an email asking for a reference. He has not (yet) responded.

Nathaniel

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Feb 2015 08:04:42 -0800

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

> Sure. But I don't see that having anything to do with how we generate

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

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

> 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

---

From: Nathaniel McCallum <[email-masked]>
Date: Fri, 13 Feb 2015 11:29:13 -0500

On Fri, 2015-02-13 at 08:04 -0800, Watson Ladd wrote:
> On Feb 13, 2015 7:30 AM, "Nathaniel McCallum" <[email-masked]
> > wrote:
> > 
> > > > > > > > > aforementioned program that I am using to generate M 
> > > > > > > > > and
> > > > > > > > > N
> > > > > > > > > constants is here:
> > > > > > > > > function is larger than $CURVE_SIZE, we use the 
> > > > > > > > > largest
> > > > > > > > > hash.
> > > > > > > > > Fourth, we begin a recursive process whereby we hash 
> > > > > > > > > the
> > > > > > > > > seed
> > > > > > description is given in a comment in the top of the file. 
> > > > > > This method is easily repeatable on every crypto-system I 
> > > > > > have
> > > > > details of SEC1 encoding, as it mungs the hash function 
> > > > > value in strange ways. Stretching the hash function is ad 
> > > > > hoc.
> > > > 
> > > > However, without it we have a significant distribution 
> > > > problem. SHA512 into a curve >511bits has insufficient range.
> > > > 
> > > > 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.
> > > > 
> > > > 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?
> > > 
> > 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
> 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.

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

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

Agreed.

> > > > Another idea I had was to have a "version" qualifier. 
> > > > Basically, it is just a counter value used in generating the 
> > > > seed. The
> > > If someone can compute a discrete logarithm, you probably 
> > > shouldn't use that group.
> > 
> > Fair enough.
> > 
> > > Despite much work, I have not been able to find a reference. It 
> > > does appear in a draft book.
> > 
> Thanks for doing that. Maybe there is a paper that calls it 
> something different out there?
> 

Sounds great!

---

From: Nathaniel McCallum <[email-masked]>
Date: Tue, 17 Feb 2015 12:04:03 -0500

> Bottom line: I'll upload a new version this weekend, and see if that 

The new draft looks good. If you would like to use the Java program 
(or some version of it) from my previous email in an appendix, feel 
free.

Nathaniel