Subject: [kitten] SPAKE edwards25519 M/N values and test vectors

From: Greg Hudson <[email-masked]>
Date: Sat, 28 Oct 2017 12:25:57 -0400

I noticed two problems with the current edwards25519 group definition in
the SPAKE preauth draft which I would like to correct:

1. When I created the test vectors, I generated x/y values incorrectly.
The IRTF SPAKE draft says "A picks x randomly and uniformly from the
integers in [0,ph) divisible by h", but I instead just picked from
[0,p], so most of the x and y values aren't divisible by the cofactor.
Depending on how an implementation works, this could make testing
awkward.

2. The M and N constants aren't in the prime-order subgroup, as is
required by the IRTF SPAKE draft.  This causes a few low-order bits of w
to be leaked, which could be used as a pre-filter before an online
password attack.  This could be papered over by forcing w to be
divisible by the cofactor, but I think providing M/N values in
conformance with the IRTF draft is much more elegant.  I generated new
values with point order checking:

   M: d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf
   N: d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab

The appendix describing M/N generation needs to be adjusted to match, as
it currently says that the M/N values are just hashes of the seed
strings.  I propose the wording:

   The M and N constants for the NIST groups are from
   [I-D.irtf-cfrg-spake2] section 3.

   The M and N constants for the edwards25519 group were generated using
   the algorithm from [I-D.irtf-cfrg-spake2] section 3 and the seed
   strings "edwards25519 point generation seed (M)" and "edwards25519
   point generation seed (N)".

(I plan to see about adding edwards25519 to the IRTF SPAKE draft, in
which case this appendix can be simplified or eliminated.  But first I
want to fix the kitten draft.)

The full document update is at https://github.com/greghudson/ietf/pull/3
but is mostly changes to hex strings.

---

From: Benjamin Kaduk <[email-masked]>
Date: Sat, 28 Oct 2017 13:53:03 -0500

> but is mostly changes to hex strings.

Thanks for spotting the inconsistency, and preparing the update!
It looks good to me.

-Ben