Subject: [Cfrg] Unwarrented change to point formats

From: Watson Ladd <[email-masked]>
Date: Sat, 26 Jul 2014 10:58:09 -0700

Dear all,
Curve25519 was a draft. Curve25519 came back with good reviews from
the CFRG. End of story? No: the TLS WG leadership has decided to ask
for the choice of curves, on nebulous criteria, ignoring existing
drafts, on the basis that the curves must be applicable "IETF wide".

I don't see the reason for this, especially given that OpenSSH has
implemented and deployed Curve25519 and Ed25519, complete with
Montgomery form on the wire.  Arguing that we need twisted Edwards
point formats everywhere for consistency with existing libraries
ignores what has already been deployed and widely adopted.

Sincerely,
Watson Ladd

---

From: "Paterson, Kenny" <[email-masked]>
Date: Sun, 27 Jul 2014 18:25:54 +0000

Watson,

There was certainly support for Curve25519 at the CFRG interim phone conference, from my reading of the transcript. 

I don't think the reasons for the TLS WG to ask for our input are nebulous, as you put it. I'd say they were taking a responsible approach, charging us as experts to explore the alternatives carefully and make recommendations. This choice will affect the future security of TLS for years - or decades - to come. So we have to get it right. 

That request to us does not mean anyone is ignoring existing drafts, as you write. I am also not aware of this IETF-wide requirement that you mention. I believe it's a "nice to have", but not a hard requirement. Can you point to something more solid that is demonstrably a consensus view?

You will note from my previous emails summarising the meeting in Toronto that backwards compatibility with the existing wire format is regarded as being desirable but not essential by the TLS WG leadership. If it can be done, it will make adoption easier; if not, we can change it, but it will need some careful drafting to make sure it's crystal clear. 

The fact that the small group who run OpenSSH has adopted a couple of schemes based on a particular curve does not necessarily make that curve the right choice for TLS. I also don't regard that as wide adoption, as you put it. I'm not aware of a public, requirements-driven process behind their choice. That's what we are attempting here.  

Your continued inputs to the process are most welcome. 

Regards

Kenny 

> On 26 Jul 2014, at 18:59, "Watson Ladd" <[email-masked]> wrote:
> 
> Dear all,
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 27 Jul 2014 19:45:39 +0100

To clarify this bit...

On 27/07/14 19:25, Paterson, Kenny wrote:
> The fact that the small group who run OpenSSH has adopted a couple of
> schemes based on a particular curve does not necessarily make that
> curve the right choice for TLS.

We provisionally allocated a code point for SSH use of Ed25519
to help with interop for their current running code.

I'm AD sponsoring the draft for that [1] and awaiting a few
changes from the author as a result of the IETF LC. A few of
those comments made the point that the hash input format was
not defined in the draft. I'm not sure if SM (the author) will
be able to fix all that now, which could raise the possibility
that we'll need another code-point when we have a standard
format for representing Ed25519 public keys as input to the
hash function here. But that's ok and none of IMO it impinges
on the ask from TLS, nor on how CFRG should process that,
except that if Ed25519 is one of the things CFRG do recommend,
then it'd be nice if you could check whether or not the
preferred and current SSH s/w public key formats are or are
not commensurate. If they are, that's fine. If not, then we
can allocate a new code point, which is also easy.

So bottom line is there's no problem here I think.

Cheers,
S.

[1] https://datatracker.ietf.org/doc/draft-moonesamy-sshfp-ed25519/

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 12:23:58 -0700

> I don't think the reasons for the TLS WG to ask for our input are nebulous, as you put it. I'd say they were taking a responsible approach, charging us as experts to explore the alternatives carefu…

No one has indicated any weakness in any of the options: to a
first-order approximation the choice will not impact security. (There
is a second-order effect where the performance of 512-x vs
448-Goldilocks will influence choices about which security level to
use, but it's second order, and
I think we're sensitive enough to performance to minimize it) At the
128 level there is really nothing to get excited about. We're going to
get it right: we can't get it wrong. (Assuming we've checked the
curves independently)

At the higher security levels the debate become slightly more
interesting: we need E-521 as it's the most efficient curve above
2^512 (I'm ignoring the constant on Pollard rho, which everyone seems
to do nowadays). The question becomes Ed448 vs Curve41417, where
whichever
is faster wins out. (Or the NUMS curve of intermediate size).

(There is one question of point format: for odd reasons people seem to
think ECDH and ECDSA keys should be interchangeable, and so want
twisted Edwards everywhere. But we don't know anything about ECDSA
that would let us do the analysis to say that is okay!)

> That request to us does not mean anyone is ignoring existing drafts, as you write. I am also not aware of this IETF-wide requirement that you mention. I believe it's a "nice to have", but not a har…

I may have read too much into emails indicating possible wider adoption.

> You will note from my previous emails summarising the meeting in Toronto that backwards compatibility with the existing wire format is regarded as being desirable but not essential by the TLS WG le…

This is (partially a) nonissue: RFC 4492 defines points as opaque
bytevectors, and provides a set of point formats to describe their
formating, so there is no formatting requirement on the point. There
is one for signatures, but as we are not introducing new signatures we
don't need to worry about it.

> The fact that the small group who run OpenSSH has adopted a couple of schemes based on a particular curve does not necessarily make that curve the right choice for TLS. I also don't regard that as…

When is the last time you used SSH and it wasn't OpenSSH? Furthermore,
they are not alone: most public greenfield crypto projects I have seen
use Curve25519 or variants such as Curve41417.

On what criteria can we possibly pick a curve? All the criteria we've
mentioned are met by both sides. It will come down to narrow
performance differences, which turns into a compiler tickling
competition. (Automatic compiler ticklers are useful here).  Maybe
when we start measuring implementations there will be a clear set of
choices, but I predict we will end up basically flipping a coin: so
much for requirements-driven!

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 27 Jul 2014 13:26:32 -0700

On Sun, Jul 27, 2014 at 11:25 AM, Paterson, Kenny <[email-masked]
> wrote:

> Watson,
>
> There was certainly support for Curve25519 at the CFRG interim phone
> conference, from my reading of the transcript.
>
> I don't think the reasons for the TLS WG to ask for our input are
> nebulous, as you put it. I'd say they were taking a responsible approach,
> charging us as experts to explore the alternatives carefully and make
> recommendations. This choice will affect the future security of TLS for
> years - or decades - to come. So we have to get it right.
>

This reflects my understanding as well.

> That request to us does not mean anyone is ignoring existing drafts, as
> you write. I am also not aware of this IETF-wide requirement that you
> mention. I believe it's a "nice to have", but not a hard requirement.

Speaking only for myself, I don't think there's anything particularly
mysterious here. The TLS WG is not chartered to do this kind of analysis
so we've turned to the CFRG. It would clearly be most efficient if the IETF
had a common set of cryptographic primitives where possible. It's true
that TLS was the first WG to try to write down a specific request, but it
seems likely that our needs are mostly common with other protocols.

To take a specific set of cases. TLS has three major uses for public key
crypto of this type:

- Key establishment
- Digital signatures over handshake messages (ServerKeyExchange,
  CertificateVerify, etc.)
- Digital signatures over certificates.

It seems likely that key establishment shares common requirements for
multiple protocols. Similarly, it would be quite convenient if the
signatures
used in TLS were the same as those used for the certificates used for TLS,
even though the latter are not defined in TLS. So, when I say an IETF-wide
set of recommendations that's the kind of thing I mean.

I wasn't aware that any of this was particularly controversial.

-Ekr

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 13:39:55 -0700

> seems likely that our needs are mostly common with other protocols.

This kind of analysis is much easier than the kind the TLS WG has to engage
in to ensure no more surprises. In particular since a lot of the
issues have to do
with performance and uptake, it's not clear the CFRG knows more about them then
the TLS WG.

> I wasn't aware that any of this was particularly controversial.

You had a draft in hand, got a reply that "yeah, looks good", and then
went back to ask for
a completely different design process, for reasons never discussed.
It's the second round
that's confusing me.

What was wrong with the curve25519 draft?

Sincerely,
Watson Ladd

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 27 Jul 2014 14:37:09 -0700

> a completely different design process, for reasons never discussed.

This does not match my understanding of the history.

Rather, here's my memory:

1. We asked the CFRG for a recommendation.

2. The CFRG held an interim discussion where a lot of good things
were said about Curve25519 but the CFRG never made a recommendation
to the TLS WG, but instead said it would come back and make
a recommendation.

3. The TLS Chairs sent the CFRG chairs a written request to make
such a recommendation (my memory is that they actually asked us
to write something down, but I don't immediately see it in my mail.)

Which brings us to the current process being run in CFRG.

-Ekr

---

From: Watson Ladd <[email-masked]>
Date: Sun, 27 Jul 2014 15:33:14 -0700

> Which brings us to the current process being run in CFRG.

And that's exactly the problem: instead of asking "is this proposed
curve secure" or "are the arguments in favor of
Curve25519 largely correct" you want CFRG to evaluate things it really
can't. How do we know if uptake in TLS will
be slowed by being non-Weierstrass?  How do we evaluate if
implementors want to implement Montgomery and
twisted Edwards arithmetic vs. just one?

I don't see why this couldn't have ended in March with "well, no
security concerns were identified, so Curve25519
will be in TLS".

Sincerely,
Watson Ladd