Subject: [Cfrg] Point format for Edwards curves

From: Watson Ladd <[email-masked]>
Date: Sat, 16 May 2015 15:02:14 -0700

Dear all,

I hope to upload version 02 of my SPAKE2 draft soon, however, I was
hoping to have points on Ed448Goldilocks and Ed25519 in it. This can't
currently happen because we've not decided on a point format for
Edwards curves. The existing point formats in the CFRG draft will not
work because I need addition. I'm aware this has taken quite a bit of
conversation spread out, but something like a little endian y
coordinate and sign bit of x doesn't seem to be wrong enough to not
put forward.

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 17 May 2015 20:56:20 -0700

> coordinate and sign bit of x doesn't seem to be wrong enough to not

The sign bit of T can also be implicit when T=wM+xG in your draft is 
required to have the positive 't_x' for T={t_x, t_y}  (or "compliant" 
T). The "encoding" of T can be done very efficiently because the sender 
chooses a random x.

https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.3 
describes the algorithm for the sum of points.

---

From: Nico Williams <[email-masked]>
Date: Mon, 18 May 2015 10:49:41 -0500

> >coordinate and sign bit of x doesn't seem to be wrong enough to not

Sure.

> required to have the positive 't_x' for T={t_x, t_y}  (or
> "compliant" T). The "encoding" of T can be done very efficiently
> because the sender chooses a random x.

Even better.

> describes the algorithm for the sum of points.

There's a timing variation, but it's entirely to do with the sums of
randomly selected points, not the fixed point derived from the password,
which means there's no side channel.  Very nice.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Mon, 18 May 2015 09:57:31 -0700

> which means there's no side channel.  Very nice.

And this proposal will not work with batchable signature schemes. It also
never gets to the byte level.

>
> Nico
> --
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Nico Williams <[email-masked]>
Date: Mon, 18 May 2015 12:39:36 -0500

> never gets to the byte level.

I didn't take Andrey's proposal as a generic point encoding for a
signature scheme, just for the SPAKE2.  That's convenient mainly because
there are implementors who might ship SPAKE2 with Curve255129 and
Goldilocks, but they can't do it without a point encoding for addition
-- Andrey's proposal saves them having to wait for CFRG to specify it.

For the signature scheme I agree we need a generic point encoding that
permits addition, and for that I support your proposal (y plus sign of x).

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Mon, 18 May 2015 10:48:42 -0700

> -- Andrey's proposal saves them having to wait for CFRG to specify it.

But I'm proposing we solve that right now, rather then adopt a workaround.
There is no reason not to decide now.

> permits addition, and for that I support your proposal (y plus sign of x).

That is extra byte for sign bit, little endian?

---

From: Nico Williams <[email-masked]>
Date: Mon, 18 May 2015 12:58:58 -0500

> There is no reason not to decide now.

Sure.  I was worried that CFRG might take a long time to reach consensus
on this.

> That is extra byte for sign bit, little endian?

Yes, little-endian y, sign bit of x as an extra byte.

Nico
--

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 18 May 2015 11:39:13 -0700

Resending with more information because it didn’t seem to go through last time?

I agree that CFRG really ought to choose a point format sometime soon, and (x,sign y) is as good as any.

If you want to spend complexity to get a point format compatible with the curves draft, please consider the "half-caf” solution, which is related to Jivsov’s trick: Montgomery x such that Montgomery y/x is positive, or 0 for the cases Curve25519 would say 0 (i.e. the identity and 2tor points).  Positive means even, or in [0,(p-1)/2], or similar.  The point encoding can be found by replacing (x,y) with (1/x, -y/x^2) if x/y is odd, since this changes the sign of y/x.  No adjustment to the secret scalar is required.

This method quotients out the 2-torsion of the group (or to be precise, one of the 2-torsion points if in case there’s more than 1).  This causes no problems with the final output if you clear the cofactor, or use the same encoding for the output, or both.  This means that it can interoperate with the systems in the curves draft, which clear the cofactor (but of course do not use the same encoding for output).

Using this change does mean that if you need to compare two points internally for some reason, and you haven’t cleared the cofactor yet, then you need to compare (in Edwards coordinates) both X:Y:Z and -X:-Y:Z.  (In the decaf version of this you only need to compare X:Y, so it actually makes your equality checker simpler, but I haven’t checked whether that works for half-caf.)  For SPAKE you don’t ever compare points, so this doesn’t matter.

Anyway, I think that this trick is simpler, faster and less stateful than Jivsov’s trick, and it generalizes better to other protocols.

— Mike

> On May 17, 2015, at 8:56 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> The sign bit of T can also be implicit when T=wM+xG in your draft is required to have the positive 't_x' for T={t_x, t_y}  (or "compliant" T). The "encoding" of T can be done very efficiently because the sender chooses a random x.
> 
> https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.3 describes the algorithm for the sum of points.
>

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 18 May 2015 15:15:37 -0700

On 05/18/2015 09:57 AM, Watson Ladd wrote:
>
>
> On May 18, 2015 8:49 AM, "Nico Williams" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> And this proposal will not work with batchable signature schemes. It 
> also never gets to the byte level.
>

Can you please elaborate?

I assume that:
* these schemes include a (long-term) public key and thus 
https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.2 works.
* If you are talking about r in {r,s}, this method actually helps 
because r=(kG)_x can be made equivalent to R=kG using the same method 
(making ECDSA==ECDSA*==ECDSA#).

I also think that the "black box" method 
https://tools.ietf.org/html/draft-jivsov-ecc-compact-05#section-4.2.1 
should always work, even with already deployed/written software and HSMs.

Here is the rationale for my proposal againl, at the high level:

* the value of "one bit", e.g. "sign", is determined somehow (a 
particular method to define it is not important, and sometimes it's not 
even relevant as for ECDH)
* this bit is implicitly encoded at key generation time, removing the 
need to explicitly encode it downstream
* the act of export in compressed/uncompressed forms is a non-crypto 
operation (a memcpy of x||y, x, or y); import knows what to do based on 
the size of payload (crypto APIs don't need to change to handle 
compression or sign bit -- all the work can be done internally to the API)
* other benefits are privacy, lack of covert channels, unified point 
format, compatibility with any explicit encoding, possibility to encode 
public keys as short(er) integers

> > [email-masked] <mailto:[email-masked]>

---

From: Nico Williams <[email-masked]>
Date: Tue, 19 May 2015 18:24:17 -0500

On Mon, May 18, 2015 at 03:15:37PM -0700, Andrey Jivsov wrote:
> >And this proposal will not work with batchable signature schemes.
> >It also never gets to the byte level.
> 
> because r=(kG)_x can be made equivalent to R=kG using the same
> method (making ECDSA==ECDSA*==ECDSA#).

If the signature scheme is deterministic and we're using something like
r = H(key1, M) then this doesn't work.  We could add a small delta input
to the derivation of r, but this then makes the system have a timing
leak.  The iterations needed to find a suitable delta could be quite a
few as first we need to derive a suitable R, then a suitable S.

Where timing leaks are unimportant (e.g., an off-line CA) this makes a
nice compression scheme, compressing public keys and signatures.  But as
a part of a general purpose deterministic signature scheme this won't
do.  It would work for a randomized signature scheme, but it would trade
off signature size for other things (e.g., signing gets slower).

Watson's proposal for point encoding for addition works for me.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 19 May 2015 23:20:15 -0700

> few as first we need to derive a suitable R, then a suitable S.

S is an integer in ECDSA.

The number of trails until the first success of generating a "compliant" 
R is 2 with a "black box" or with additions, but this is the worst case. 
Algorithms like ECDSA would only need a simple and deterministic r := 
order-r, on average for every other R=rG. This saves the check later 
regarding whether the second coordinate is to be encoded with 0 or 1 
(but order-r or order<r are tiny steps).

> off signature size for other things (e.g., signing gets slower).

I don't think there is a concern about leakage of 0.5 bit because we 
base the decision on public information, e.g. the sign of y. r and 
order-r have the same amount of entropy, or, equivalently, (x,y) is as 
strong as (x,-y).

If I only generate a key in a deterministic way (a very uncommon 
operation), the implicit encoding of y cannot work. The only case where 
this may be needed, as noted by Watson, is for batchable ECDSA# with 
deterministic r in R=rG of {R, s}. Long-term ECDSA# public keys, just as 
ECDSA keys, are not affected. (The same applies to EdDSA). The other 
example I knew about but thought it was not worth mentioning even though 
there is a software product that does this, is generation of public key 
pairs from unsalted passwords.