Subject: [TLS] PKIX drafts on EdDSA/Ed25519 and Curve25519/Curve448

From: Simon Josefsson <[email-masked]>
Date: Tue, 30 Jun 2015 00:02:39 +0200

Hi all,

(I'm cross-posting pkix@ and tls@ because there is cross-WG coordination
involved here -- please redirect followups appropriately.)

Symantec kindly donated two OIDs for Ed25519 keys/signatures.  I have
updated the EdDSA/Ed25519 draft to use them, together with some other
minor tweaks.  Please find the updated document here:

https://tools.ietf.org/html/draft-josefsson-pkix-eddsa-02

Symantec also offered 1.3.101.102...1.3.101.127 for other curves or
signature schemes, as they are defined, which will shave off a couple of
bytes for us.  Coordination of allocation is handled by Rick Andrews.

A couple of people suggested to define encodings for Curve25519/Curve448
(the CFRG curves) public keys.  I didn't see that this necessarily had
to be in the above document, so I put it in a separate document.  I'm
not entirely sure how useful this is, or if I may have completely
misunderstood what people had in mind.  Please find a new document here:

https://tools.ietf.org/html/draft-josefsson-pkix-newcurves-00

The document is short and a bit rough at the moment; all feedback is
welcome.

Cheers,
/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 30 Jun 2015 11:20:22 +0300

On Tue, Jun 30, 2015 at 12:02:39AM +0200, Simon Josefsson wrote:
> misunderstood what people had in mind. 

Well, EdDSA-like scheme (obtained by dropping constraints on curve
and hash[1] and generation of a and seed[2])  would be:

(a and seed generated from secret)
r = h(seed || M)
R = rB
A = aB
s = (r + h(encode_p(R) || encode_p(A) || M) * a) mod l
signature = encode_p(R) || encode_s(s)
public key = encode_p(A)

(Multiply equation for s to get verification equation:
sB = R + h(encode_p(R) || encode_p(A) || M) * A )

(One can obtain Ed25519 from this by substituting suitable a / seed
generation, B and functions h, encode_p and encode_a.)

And since encode_p(X) is inside hash, one must pin it down for the
scheme to work (interoperate between signers and verifiers), along
with the hash function h to use.

Edwards curves are always constant or quadric in x for in every
term of curve equation. Which means that x can be compressed to
a single LSB bit (Ed25519 paper is somewhat unclearly worded IMO,
but this is what it does for prime curves[3][4]).

There's also encode_s(x), but it is straightforward (can just use
little-endian base-256 integer encoding.

[1] Enabling it to work on curves other than very few ones, especially
with standard-issue hashes.

[2] Since hash function length is insufficient for the method used in
Ed25519 without using exotic hashes.

[3] There are other possibilities, but LSB bit (even/odd) seems to be
the easiest to extract and to compare.

[4] For Ed448 there is also encoding from Ed448-Goldilocks, which is
56 bytes (448 bits) instead of 57 bytes (449 bits). But it is fair
bit more complicated (slow) than straightforward point compression.

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 30 Jun 2015 12:00:44 -0700

> On Jun 30, 2015, at 1:20 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

To clarify, the encoding in Ed448-Goldilocks, and its successor “decaf”,
are more complicated than straightforward point compression but not
significantly slower.

There is also the alternative of (low bit of x is 0) ? y : -y, with the identity
(0,1) mapped arbitrarily to 1.

As for hash functions, the hash function used to produce the challenge
doesn’t have to be uniform.  It doesn’t even have to output a number as
big as the curve — half as big is good enough — but most schemes use
the full length for extra conservatism.  Also, if the curve order is close to
a power of 2 (i.e. 2^bleh +- O(2^(bleh/2))), then a hash the same length
as the order is good enough for choosing the seed.  You only need a
longer seed if the curve is not close enough to a power of 2, eg P256 or
Brainpool.  But it is nice to be able to choose the same hash function for
every curve of the same size.

Cheers,
— Mike

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 30 Jun 2015 23:07:21 +0300

> (0,1) mapped arbitrarily to 1.

As for some explanation how to decode that... Use the y as y coordinate of
the point and then force LSB(x) to 0. The resulting point is either (x,y)
or (-x,-y)=(x,y)+(0,-1)  (it has to be -x because curve is symmetric w.r.t.
axes and the LSB(x) flipped).

The (0,-1) term can be canceled out by multiplying both sides of the
check equation by some even number coprime to basepoint order (8 works,
and Ed25519 already recommends multiplication by that). 

That would certainly enable encoding Ed448 points to 56 bytes instead of
57. Also, it looks simple, fast to encode and reasonably fast to decode.

> every curve of the same size.

Yeah, I have noticed that when calculating what would be enough for
various curves. If you are wondering where that 5/4 rule in signature
proposal comes from, it is from those calculations.

The formulas I use yield acceptable values already for 256-bit hash with
Curve25519 (Delta=0.015 bits) and 448-bit hash with Curve448 (Delta=0.171
bits). The formulas are pretty conservative (e.g. assuming that 100% of
entropy loss is converted to information about private key, and assume
ridiculous amount of signatures), but maybe not conservative enough.

-Ilari

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 30 Jun 2015 13:30:37 -0700

> On Jun 30, 2015, at 1:07 PM, Ilari Liusvaara <[email-masked]> wrote:
> 

Thanks for adding that missing explanation.  I’m not pushing this as necessarily a good idea; I just wanted it to be out there.

> ridiculous amount of signatures), but maybe not conservative enough.

Ah, nice.  What’s delta?  Is that (work to break signatures with uniform hash)
- (work to break with biased hash)?  In that case it’s conservative enough.

— Mike

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 30 Jun 2015 23:37:55 +0300

> - (work to break with biased hash)?  In that case it’s conservative enough.

sqrt(l) times difference of entropies between uniform distribution and modulo
distribution.

-Ilari