Subject: [TLS] Updated EdDSA in TLS drafts

From: Simon Josefsson <[email-masked]>
Date: Mon, 08 Jun 2015 11:52:23 +0200

Hello.

I've updated my EdDSA-in-TLS draft to clarify the choice of
HashAlgorithm that goes together with the EdDSA SignatureAlgorithm,
please see:

https://tools.ietf.org/html/draft-josefsson-tls-eddsa-01

The other feedback I have received is to reuse the existing ECDSA
ciphersuites.  I think this is a good idea, and believe it would likely
work, but it is a fundamentally different approach.  I created another
draft to describe that approach, now published as:

https://tools.ietf.org/html/draft-josefsson-tls-eddsa2-00

Having these two approaches described separately allows us to review
both and decide which is the better approach.

More feedback is appreciated!  Some issues that is not clear to me
includes:

* Is it a good idea to reuse the NamedCurve value for Curve25519 for
  Ed25519 too?

* Similar question for ECPointFormat.  Maybe EdDSA should use a
  different definition here.

For more context, related to the above is a draft describing OIDs for
EdDSA for use in PKIX certificates as public keys and a signature
algorithm:

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

Cheers,
/Simon

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 08 Jun 2015 11:16:22 +0100

Hiya,

On 08/06/15 10:52, Simon Josefsson wrote:
> More feedback is appreciated!

My v. high level feedback is that we really don't want
to get too far ahead of cfrg here. They've not yet got
all details of their preferred signature scheme using
that curve defined and it'd be really dumb for any IETF
WG to get ahead of that by accident.

So while working on this draft is a fine thing, I don't
think we want to get to IETF LC for things like this until
after cfrg have figured out their preferred signature
scheme. (And the cfrg chairs tell me that ought be done
soon - in a few months.)

Note that waiting until the cfrg position is clear
does not mean that the IETF has to mindlessly adopt what
cfrg have done, but we won't want to ignore their work
either. And fwiw, I guess I'd take the same position for
any work item for almost any new ECC work for the moment.
Since cfrg are nearly done and seem to be making progress
now, pre-empting their decisions wouldn't be a good plan.

Cheers,
S.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 8 Jun 2015 13:39:40 +0300

> https://tools.ietf.org/html/draft-josefsson-tls-eddsa-01

What hash algorithm is internally used? EdDSA does not fix that
(Ed25519 does fix it to SHA-512).

Does more need to be said about how R and S are packed into single
blob for signature (concatenate)?

More ciphersuites. Eew.

Also, in TLS 1.2 Client CertificateVerify (does not apply to server
certificate, nor either certificate in TLS 1.3) signs the entiere
handshake so far. That could be many kilobytes in size, spread over
multiple message.

> https://tools.ietf.org/html/draft-josefsson-tls-eddsa2-00

TLS 1.0 and 1.1 lack algorithm specification for signature, which is
very useful for merging ciphersuites like this. In theory, one could
infer the algorithm from certificate, but I don't think that kind
of tricks are very often pulled off.

I don't know if mixing curves used for key exchange and curves used
for signing is a good idea. Signing is much more complicated than
ECDH.

The point format used by EdDSA has very little to do with montgomery X
(it does not have the same number of bits). The point format is little-
endian encoding of 2^(b-1)*lsb(x)+y, b is 256 for Curve25519, and lsb(x)
is x mod p mod 2. X and Y are edwards coordinates.

Also, notes about not seemingly fixing the hash, encoding of signature
and TLS 1.2 client certs apply.
 
> https://tools.ietf.org/html/draft-josefsson-pkix-eddsa-00

Repeating the definitions sounds bit odd, one could presumably just
state what to put in each field.

Public key encoding? Edwards points have two coordinates. The usual
EdDSA encoding (32 octets for Curve25519)?

Hash algorithm? Note that public keys are not compatible across hash
algoritmhs. Fixed to SHA-512?

Signature encoding? Presumably the same as on TLS side.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Mon, 8 Jun 2015 10:38:47 -0700

> * Is it a good idea to reuse the NamedCurve value for Curve25519 for

I don't think so.  I understand that there might be some shared code,
but we are likely to see implementation of DH on 25519 long before
signatures.

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 9 Jun 2015 00:42:19 +0000

> I don't think so.  I understand that there might be some shared code, but we
> are likely to see implementation of DH on 25519 long before signatures.

Agree, use distinct identifiers; djb thinks they are fundamentally different, and calls them X25519 and Ed25519.  (And of course the point format is different :)

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 09 Jun 2015 10:07:17 +0200

> scheme. (And the cfrg chairs tell me that ought be done

Thanks for feedback.  I believe these documents are quite far away from
LC-ready so that this aspect shouldn't be a problem.

I view the EdDSA/Ed25519 effort similar to the Brainpool/GOST efforts.
If CFRG happens to pick EdDSA, then fine, but that isn't the
motivational factor here.

/Simon

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 09 Jun 2015 10:33:33 +0200

Again, many thanks for feedback Ilari!

> (Ed25519 does fix it to SHA-512).

Yeah.  I think this is actually a larger question: will EdDSA be defined
with other curves than Ed25519?  If no, the only interesting algorithm
to specify is Ed25519.  If yes, the parameter choices needs to be
encoded somehow.  The hash isn't the only parameter to EdDSA.

> blob for signature (concatenate)?

I'm hoping draft-josefsson-eddsa-ed25519 already covers that.

> More ciphersuites. Eew.

Yeah.  I offer this approach in the rare case that it might actually
prove less complex to implement, and that some might find it useful.  I
suspect it might get shot down during further discussions.

> handshake so far. That could be many kilobytes in size, spread over

Some implementations buffer the entire handshake to deal with this
problem.  I'm not sure what to recommend generally, or if this document
has to care about this.

> of tricks are very often pulled off.

RFC 4492 defines SignatureAlgorithm for TLS 1.0 and 1.1, or am I
misunderstanding what you are saying?

> for signing is a good idea. Signing is much more complicated than

Agreed.  I've changed to use a separated NamedCurve registration.

> is x mod p mod 2. X and Y are edwards coordinates.

Right, this was just broken.  I've changed it to use a separate
ECPointFormat registration for EdDSA public keys.

> and TLS 1.2 client certs apply.

I've changed to use "sha512" instead of "none" in the latest update.

> state what to put in each field.

I find repeating this establish the terminology a bit better.  There are
so many structures in RFC 5280 that it is hard to find the right one.
Also, I mostly stole this text from some other RFC.

> EdDSA encoding (32 octets for Curve25519)?

I was hoping draft-josefsson-eddsa-ed25519 takes care of define a
canonical public key encoding.

> algoritmhs. Fixed to SHA-512?

Yes, I've changed my opinion and think that the HashAlgorithm should
probably be sha512 to indicate Ed25519-SHA-512.

> Signature encoding? Presumably the same as on TLS side.

Again, hoping to shift this burden on draft-josefsson-eddsa-ed25519.  I
agree there could be clearer text on this.

Cheers,
/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 09 Jun 2015 10:36:53 +0200

I made the NamedCurve/ECPointFormat registrations stand on their own,
please see updated draft here:

https://tools.ietf.org/html/draft-josefsson-tls-eddsa2-01

I'm hoping this version is a bit easier to read since everything it uses
is defined in the document.

/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 9 Jun 2015 12:43:41 +0300

> encoded somehow.  The hash isn't the only parameter to EdDSA.

The requirements of EdDSA are so bizarre that I don't think there are
realistic curves to use with that besides Edwards form of Curve25519.

(Edwards form of M-379 might come the closest, but the needed 760-bit(!)
hash function is pretty much unobtabnium).

> I'm hoping draft-josefsson-eddsa-ed25519 already covers that.

Oh yeah.

> suspect it might get shot down during further discussions.

I checked the TLS 1.2 spec:
- If advertised ciphersuites and signature_algorithms conflict, latter
  takes precedence.
- If selected ciphersuite and signature algorithm in struct
  DigitallySigned conflict, latter takes percedence.

This means TLS_DHE_RSA_* key exchange can end up being signed with ECDSA,
if client told it supports ECDSA.

> problem.  I'm not sure what to recommend generally, or if this document

I was thinking maybe PRF-hash, since one has that running anyway (for
session_hash and finished) and it better be secure enough.

Or maybe buffering doesn't really matter.

> misunderstanding what you are saying?

I mean the explicit signature algorithm in struct DigitallySigned. That
was new in TLS 1.2.

Without that, one is left guessing the algorithm from the certificate,
which is quite unclean.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 9 Jun 2015 12:59:09 +0300

> is defined in the document.

Eeh...

"enum { ed25519(5) } NamedCurve;"

NamedCurve 5 is already assigned to some (too weak) elliptic curve.

The currently free named groups are 0x1D-0xFF and 0x0200-FDFF (don't
use other ones, those have special meaning, and 0xFExx is private use).

"When included in a ServerKeyExchange or ClientKeyExchange message,"

AFAIK, SKE or CKE never carry signature keys. The signature keys are
sent inside Certificate messages (usually as PKIX SubjectPublicKeyInfo,
but also OpenPGP format is defined).

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 09 Jun 2015 11:14:10 +0100

Hi Simon,

> LC-ready so that this aspect shouldn't be a problem.

Yep, I think that's correct. But I'd be somewhat wary of
making design decisions in the meantime - we really don't
want to end up with a cfrg-annointed signature scheme that
ends up being hard to integrate because of decisions made
now. (And folks who care about what cfrg are doing on that
should get involved on the cfrg list.)

> motivational factor here.

Well, maybe. With no hats, I personally don't think we want
more unused ciphersuites, and especially not ones that are
almost-but-not-quite the same as one that uses the eventual
cfrg-annointed signature scheme. (Unless there's a good
reason to not use the cfrg stuff of course, in which case
we're in a different situation.)

But so long as the TLS WG don't bake in too much stuff and
so long as cfrg continue to make progress in a timely fashion
it should all work out.

Cheers,
S.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 9 Jun 2015 12:42:54 +0200

> > Thanks for feedback.  I believe these documents are quite far away
> > from LC-ready so that this aspect shouldn't be a problem.
> 

Hi Stephen.  Sure.  I don't think any decisions are or will be made
here now.  This is brainstorming about how to approach adding a new
signature algorithm to TLS.  There are no changes to any TLS version
proposed that could cause integration problems for a future CFRG-blessed
signature scheme.

> > I view the EdDSA/Ed25519 effort similar to the Brainpool/GOST
> > efforts. If CFRG happens to pick EdDSA, then fine, but that isn't
> > the motivational factor here.
> 

Agreed.  Btw, it seems that no new ciphersuites will have to be
allocated anyway, and that the existing ECDSA ciphersuites can be
reused.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 9 Jun 2015 12:47:04 +0200

Den Tue, 9 Jun 2015 12:59:09 +0300
skrev Re: [TLS] Updated EdDSA in TLS drafts:

> > I made the NamedCurve/ECPointFormat registrations stand on their
> > own, please see updated draft here:
> > 
> > I'm hoping this version is a bit easier to read since everything it
> > uses is defined in the document.
> > 
> > /Simon
> 
> Eeh...
> 
> sent inside Certificate messages (usually as PKIX
> SubjectPublicKeyInfo, but also OpenPGP format is defined).

Should be fixed in working copy, thank you!

https://gitlab.com/jas/ietf-tls-eddsa/blob/master/draft-josefsson-tls-eddsa2.txt

/Simon

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 09 Jun 2015 11:48:18 +0100

> proposed that could cause integration problems for a future CFRG-blessed

Cool, thanks,
S.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 09 Jun 2015 13:09:55 +0200

> realistic curves to use with that besides Edwards form of Curve25519.

Okay.  If that is really the case, we should specify Ed25519 directly
and don't bother with EdDSA.  But if there is a chance that we'll see
other curves used with EdDSA, then it would be better to specify EdDSA
and instantiate it for Ed25519 with some parameter choice.

I believe this is an important question, but I lack knowledge to make a
decision.

> hash function is pretty much unobtabnium).

Can't you build one with a keyed PRF?

> if client told it supports ECDSA.

While a bit ugly, language could be added to the TLS-Ed25519 document
saying what to do in each case.  I don't propose to do this, though,
just saying that the problem above could be solved if it was really
important.

> session_hash and finished) and it better be secure enough.

Ah.  Would you then sign the PRF-hash with SHA-512 for Ed25519?

> Or maybe buffering doesn't really matter.

I think not.  Let's see.

> Without that, one is left guessing the algorithm from the certificate,

Ah, right.  Maybe there should be words to that effect: If TLS 1.0 or
1.1 then look at the certificate to find out the algorithm to use.

Thanks again,
/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 9 Jun 2015 14:38:56 +0300

> I believe this is an important question, but I lack knowledge to make a

Also, since this is also brainstorming about adding a new signature primitive
(post-RFC5246).

The CFRG signature primitive probably will be parameterized by curve and hash
function (maybe with restrictions on minimum hash length for each curve).
 
> Can't you build one with a keyed PRF?

Maybe. But that's something I'd rather not mess with.

> just saying that the problem above could be solved if it was really

Why not just follow standard TLS 1.2 rules (which are a bit odd as noted
above, but look to be workable)?

> Ah.  Would you then sign the PRF-hash with SHA-512 for Ed25519?

Yup (if avoiding buffering is important).

-Ilari

---

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

Hi.  The discussion about Curve25519 and ECPointFormat made me realize
that the same appears to apply to Ed25519.  So I have removed the
ECPointFormat registration and let the document say "use uncompressed".
Here is an updated document:

https://tools.ietf.org/html/draft-josefsson-tls-eddsa2-02

Anyone disagreeing with this, and would like to see an EdDSA
ECPointFormat for some reason?  Why?

Come to think of it, maybe the SignatureAlgorithm registration for eddsa
is unnecessary too, and we can overload the ecdsa value.  The NamedCurve
value "ed25519" should signal support for EdDSA anyway.

More review whether the draft would actually work for different TLS
versions (1.3 included) is appreciated.

/Simon