Re: [kitten] SPAKE edwards25519 group

[Benjamin Kaduk <[e-mail]>]

On Thu, Sep 07, 2017 at 01:16:58PM -0400, Greg Hudson wrote:
> 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.)

In general I support this proposal.

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

Seems reasonable.

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

Sure.

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

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.

> * 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:

Sure.

>     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

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