Subject: [kitten] SPAKE edwards25519 group

From: Greg Hudson <[email-masked]>
Date: Thu, 07 Sep 2017 13:16:58 -0400

I would like to add a SPAKE group specification using the Edwards
2^255-19 curve used by the ed25519 signature algorithm.  I was recently
able to implement this group by adapating the SPAKE2 code from
BoringSSL.

I would like to specify that the new group is the only
mandatory-to-implement group, as I believe that it is the easiest to
implement in constant time and has the potential to be the most
performant choice.  (P-256 may be more performant in practice in some
situation, as OpenSSL normally uses an optimized assembly implementation
of P-256, while the BoringSSL Edwards 25519 SPAKE code is in C.  But in
my tests they're pretty close even so.)

I would like to renumber the groups so that the new group is 1 and the
three NIST groups are 2, 3, and 4.  As we have not assigned pa-data or
key usage code points yet, there should be no interoperability issues
with renumbering the groups.

I suggest the group name "edwards25519", which is used in RFC 7748.  The
shorter name "ed25519" could create confusion with the ed25519 signature
algorithm.

Here is the registry entry (please verify that my RFC 7748 and RFC 8032
references seem correct):

* ID Number: 1
* Name: edwards25519
* Specification: [RFC7748] section 4.1 (edwards25519)
* Serialization: [RFC8032] section 3.1
* Multiplier Length: 32
* Multiplier Conversion: RFC 8032 section 3.1
* SPAKE M Constant: 5ada7e4bf6ddd9adb6626d32131c6b5c51a1e347a3478f53cfcf441b88eed12e
* SPAKE N Constant: 10e3df0ae37d8e7a99b5fe74b44672103dbddcbd06af680d71329a11693bc778

To justify the M and N values (which are the same ones used by
BoringSSL), I would like to add an appendix B titled "SPAKE M and N
Value Selection" with the text:

    The M and N constants for the edwards25519 group are the SHA-256
    hashes [RFC6234] of "edwards25519 point generation seed (M)" and
    "edwards25519 point generation seed (N)" respectively.  Both hashes
    decode to valid curve points.

(The BoringSSL SPAKE2 code includes a whole bit of Python code in a
comment which would iterate the SHA-256 hash until a valid curve point
is found.  But it turns out both seeds hash to a valid curve point
immediately.)

Convenience links:

https://tools.ietf.org/html/rfc7748
https://tools.ietf.org/html/rfc8032
https://tools.ietf.org/html/draft-ietf-kitten-krb-spake-preauth-00

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 11 Sep 2017 10:25:26 -0500

> my tests they're pretty close even so.)

In general I support this proposal.

> with renumbering the groups.

Seems reasonable.

> shorter name "ed25519" could create confusion with the ed25519 signature

Sure.

> * Specification: [RFC7748] section 4.1 (edwards25519)

Yes, that's the right section for edwards25519, even though the section
title is Curve25519.  RFC 7748 does have an external reference for ed25519
(and the edwards25519 curve), which is a Springer publication, so the
RFC is probably better.

> * Serialization: [RFC8032] section 3.1

RFC 8032 seems to refer to bit-string serializations, whereas our group
elements are represented as octet strings.  RFC 8032 does describe packing
bit strings into octet strings in section 2, so perhaps the given reference
suffices.

> Value Selection" with the text:

Sure.

> https://tools.ietf.org/html/draft-ietf-kitten-krb-spake-preauth-00

It would be good to hear some additional feedback before pushing an
updated version of the document.  Does anyone want to speak for
or against adding the edwards25519 curve and making it MTI?

-Ben

---

From: Simo Sorce <[email-masked]>
Date: Mon, 11 Sep 2017 11:34:08 -0400

On Mon, 2017-09-11 at 10:25 -0500, Benjamin Kaduk wrote:
> > * SPAKE M Constant:
> > 5ada7e4bf6ddd9adb6626d32131c6b5c51a1e347a3478f53cfcf441b88eed12e
> > * SPAKE N Constant:
> > 10e3df0ae37d8e7a99b5fe74b44672103dbddcbd06af680d71329a11693bc778
> > 

In favor.

Simo.

-- 
Simo Sorce
Sr. Principal Software Engineer
Red Hat, Inc

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Thu, 14 Sep 2017 21:39:48 -0700

> On Sep 11, 2017, at 8:25 AM, Benjamin Kaduk <[email-masked]> wrote:
> 

I remember thinking we would be adding 25519 real soon when I reviewed it. Sure go ahead.

Personal email.  [email-masked]