Subject: [Cfrg] big-endian short-Weierstrass please

From: Dan Brown <[email-masked]>
Date: Tue, 27 Jan 2015 15:41:50 +0000

Dear CFRG,

IEEE 1363-2000, ANSI X9, NIST 800-56A and SEC1 use 

#10) short-Weierstrass representation for EC points, which is nice because
any elliptic curve, including the latest and greatest, can be represented in
this form, and 

#01) big-endian (MSB-first) octet string representation for prime-field
elements, which is admittedly somewhat arbitrary (with no effect on
security) although somewhat consistent with various old-fashioned notations
for numbers

#11) KDFs based on hash functions SHA1 and SHA2 which are kind of big-endian

If raw Curve25519 implementations operate on input and outputs of byte
strings, in whatever order and curve shape, then it shouldn't be too hard
for applications using the raw Curve25519 implementation to shift the
input/output coordinates from/to short Weierstrass (yes, one has to choose
the a-value for this), and then unsort/sort the octets into MSB-first order

I appreciate that currently, TLS is thinking to use Curve25519 a named
curve, specified by an OID, and then determine all point representations,
including the internal used ones used in the KDF and signatures, based on
the named curve.  That should work too for TLS and any easily updatable
software.  

But I wonder if there are any old implementations of the standards I listed
above, that accept generic specified short Weierstrass curves, but lock
together the KDF and raw ECDH operations.  Users stuck with such
implementations couldn't gain _all_ the benefits of Curve25519, side channel
resistance or whatever, but surely there's some residual benefits for them
to use Curve25519 with a generic representation: maybe the rigidity
Curve25519, or interoperability with other users with the newfangled
software, not to mention the blessing of the collective wisdom of CFRG.  

If the argument is that no such implementations could exist, or that the
implementations, or even old ECC standards, are so bad that we should try to
discourage interoperability, then please present that case.

Best regards,

Daniel Brown

Research In Motion Limited

---

From: David Gil <[email-masked]>
Date: Tue, 27 Jan 2015 17:54:56 +0000 (UTC)

A lot of older software (and hardware) that support arbitrary elliptic curves over Fq, q>3 assume that h=1. Those implementations will not handle Edwards curves correctly.

See, e.g., http://golang.org/pkg/crypto/elliptic/#CurveParams

I would prefer to break backwards compatibility for the sake of correctness. (And I would suspect that some implementations that claim to support arbitrary cofactor are broken: There has not been any reason before to really exercise the h!=1 case.)
- dlg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 28 Jan 2015 13:48:44 -0500

> discourage interoperability, then please present that case.

It sounds to me like you're presenting a choice between two options for
the CFRG:

 0) help more people move to better curves, without moving anyone to
    better algorithms or requiring anyone to move to better
    implementations.

 1) Allow people who can move to better algorithms, implementations, and
    curves to do so in one step, while leaving people with brittle
    software behind if the new system is adopted in exclusion to the
    old.

It seems like the answer to this would be governed by your perception of
(a) existing curves compared algorithms and implementations, and (b) how
you expect the rollout+deprecation process to happen, but even
considering both of these choices independently, it seems like (1) is
better.

Curves vs. Algorithms and Implementations
=========================================

If you feel that the existing curves themselves are the main source of
concern, but not the algorithms and implementations, you might lean a
little bit toward (0).  However, there seems to be a general consensus
that existing implemetations and algorithms themselves are problematic
-- for example, libraries like OpenSSL have rewritten their P-256
implementations in the last year, and deterministic signature mechanisms
are clearly better than traditional ECDSA.  So (1) is more appealing --
if we can fix more things during this transition, we should fix them.

Rollout and Deprecation
=======================

There is existing code that is never going to change.  There is existing
code that can be minorly changed by tweaked parameters.  And there is
existing code that can be easily, fully upgraded.

The first group is never going to disappear, and unfortuately, members
of that group might be too important for every tool to just ignore the
group entirely (consider systems that want to talk to home routers or
networked printers, or systems that are only willing to use NIST
curves).  So tools that require backward compatibility that covers these
systems will need to have some level of fallback interoperability to
existing practice in both curves and algorithms.

But if we're going to have the fallback to existing practice anyway, we
can also use that to cover those implementations that can only accept
minor changes.

(1) seems like the better option to me, from an overall ecological point
of view.  Let's take advantage of this transition time to include
important fixes in all areas, for those who can make them.

As for byte-ordering: higher levels of abstraction (both on the wire and
logically) all prefer fixed-length bitstrings anyway.  So that's the
interface that we should use for the primitive.  We should declare
something explicit so that libraries know what to produce to get
canonical bitstrings, and move on.  Little-endian is fine.

Regards,

       --dkg

---

From: Dan Brown <[email-masked]>
Date: Wed, 28 Jan 2015 21:23:27 +0000

Well, maybe everybody could agree on this middle ground? 

00) Continue (or start) to allow generic ECC modes in IETF protocols, such
as the specified curve option RFC 4492, while specifically encouraging
implementers to use best practices, e.g. recommend constant-time for private
key operations, checks for MOV, etc., to help implementers look out for the
known pitfalls, perhaps collected in an RFC. 

10) Continue to use the old ECC standards' big-endian short Weierstrass
formats to specify arbitrary curves whenever the above-mentioned optional
generic ECC modes are actually used.  

01) Continue to use big-endian short-Weierstrass point and KDF input formats
for these generic ECC modes, at least whenever the curve is specified using
big-endian short-Weierstrass.  So, just to be clear, if somebody happens to
specify Curve25519 using the big-endian short Weierstrass a and b, then the
old formats will be honoured, not the new.  So, this would be backwards
compatible optional way to use Curve25519.

11) For curves indicated via names or OIDs, use a format determined by that
name.

This middle ground refers to formats only: not signature algorithms, key
agreement algorithms.

Specific replies to previous message inserted below (but somewhat
independently of the comment above).

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Daniel Kahn Gillmor
> > But I wonder if there are any old implementations of the standards I
> > listed above, that accept generic specified short Weierstrass curves,
> > but lock together the KDF and raw ECDH operations.  Users stuck with
> > such implementations couldn't gain _all_ the benefits of Curve25519,
> > side channel resistance or whatever, but surely there's some residual
> > benefits for them to use Curve25519 with a generic representation:
> > maybe the rigidity Curve25519, or interoperability with other users
> > with the newfangled software, not to mention the blessing of the
collective
> wisdom of CFRG.
> >
> > If the argument is that no such implementations could exist, or that
> > the implementations, or even old ECC standards, are so bad that we
> > should try to discourage interoperability, then please present that
case.
> It sounds to me like you're presenting a choice between two options for
the
> CFRG:

That's another way to put it, though I was not exactly asking for 0 they way
you put it. Specifically, I was _not_ proposing to stop anybody from moving
ahead to newer implementations.  I was only aiming to maintain having
backwards interoperability with old implementations.  For example, RFC 4492
allows curves to be specified in Weierstrass form, not just as named form.
I don't know if any TLS implementations support the specified curve option,
but if they do, then it would be nice if the new implementations could talk
to them, using the new curves.  

Well, in that case, I suppose that the new implementations talking to old
implementations could just as well revert to old point formats, to send on
the wire, and to compute shared secrets.  There might side be channels on
the old side, but at least the new side would be safe: stopping half the
leak might have some small value.  Of course, for that, new implementations
would have to support big-endian short-Weierstrass, but they wouldn't use it
normally, except for backwards compatibility.

> you expect the rollout+deprecation process to happen, but even considering
> both of these choices independently, it seems like (1) is better.

Yes, about (a) and (b).  Still not sure about (1). 

> Curves vs. Algorithms and Implementations
concern,
> but not the algorithms and implementations, you might lean a little bit
toward
> (0).  However, there seems to be a general consensus that existing
> implemetations and algorithms themselves are problematic
are
> clearly better than traditional ECDSA.  So (1) is more appealing -- if we
can fix
> more things during this transition, we should fix them.

Hmm, yes, I think that most of the claimed security benefits for Curve25519
have to do with implementability: efficiency, avoiding security pitfalls in
implementations.  More precisely, these are claimed as the primary benefits.
The rigidity of the curve is claimed only a secondary benefit (compared to
the primary benefits), as I understand the claims.  In any case, that's how
I'd classify the benefits the Curve25519 and similar.

> Rollout and Deprecation
code that
> can be minorly changed by tweaked parameters.  And there is existing code
> that can be easily, fully upgraded.
> 
> The first group is never going to disappear, and unfortuately, members of
that
> group might be too important for every tool to just ignore the group
entirely
> (consider systems that want to talk to home routers or networked printers,
or
> systems that are only willing to use NIST curves).  So tools that require
> backward compatibility that covers these systems will need to have some
level
> of fallback interoperability to existing practice in both curves and
algorithms.
> But if we're going to have the fallback to existing practice anyway, we
can also
> use that to cover those implementations that can only accept minor
changes.

Ok, I'm the last person to know about software upgrades etc., but I do
understand that the old standards allowed specified curves, which in theory
allows the curve choice to be updated on the fly, without upgrading the
software.

Note: I know that X9.62 and SEC1 placed restrictions on the field size and
curve sizes.  The SEC1 field sizes were meant to encourage interoperability.
Suppose these old standards were updated to allow new curves.  Ok, more
work.  Change formats, yet more work.  But, doable.  

Aside: interoperability which seems necessary for non-monopoly security.  We
don't want everybody to use the same software, right?  Interoperablity
sometimes involves conceding perfection for something good enough, right?
 
> (1) seems like the better option to me, from an overall ecological point
of view.
> Let's take advantage of this transition time to include important fixes in
all
> areas, for those who can make them.
> 
> 
> 
> 
interface that
> we should use for the primitive.  We should declare something explicit so
that
> libraries know what to produce to get canonical bitstrings, and move on.

Done that, almost. Old ECC standards chose octet strings for EC public key
reps and for KDF inputs.  They just chose the prevailing big-endian approach
and moved on (perhaps never expecting this decision to be revisited, and
furthermore being told to move on ;-)

One and half exceptions to octet string only formats, hence the "almost"
above. (1/2) EC standards chose preserve integers in ECDSA: F_p field
elements were mapped into the field F_n, by preserving integers and reducing
mod n, which would have been equivalent to converting to fixed-length
big-endian octet string and then converting back to integers,  (3/2) for
ASN.1 representation of ECDSA signatures the old EC standards encode the
integers in (r,s) as ASN.1 integer types.  An alternative would have been
for the EC standards to convert integers (r,s) in a signature to octet
strings before going into ASN.1, but if you are using ASN.1 already, why not
keep integers as integers?

> Little-endian is fine.

Ignoring any backwards interoperability, I would agree, in fact, it is
probably better if it works better with current computer architecture.
Isn't maintaining backwards interoperability usually supposed to a good
thing?

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 28 Jan 2015 17:30:28 -0500

On Wed 2015-01-28 16:23:27 -0500, Dan Brown wrote:
> For example, RFC 4492 allows curves to be specified in Weierstrass
> form, not just as named form.  I don't know if any TLS implementations
> support the specified curve option, but if they do, then it would be
> nice if the new implementations could talk to them, using the new
> curves.

Over in the TLS WG, we're working on actively deprecating the custom
curve selection mechanism and moving strictly toward pre-named curves
(this is true for finite-field DH as well).  Custom curve and FFDHE
group selection will be gone in TLS 1.3.

oThe over-flexibility in EC group selection isn't widely used, and when
it is used, there is no clear way for a receiving implementation to have
confidence in the structure of the arbitrary curves provided (even
simple primality-testing is probably too expensive for most to do at
runtime), or to have a reasonable (efficient, constant-time)
implementation.

I don't think this is a particularly useful half-measure.  I'd rather
see implementations pick up new, reasonably-vetted curves than try to
muddle through supporting arbitrary curves provided by the peer.

     --dkg

---

From: Nico Williams <[email-masked]>
Date: Wed, 28 Jan 2015 17:10:10 -0600

> muddle through supporting arbitrary curves provided by the peer.

+1

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 28 Jan 2015 23:20:44 +0000

On 28/01/2015 22:30, Daniel Kahn Gillmor wrote:

> I'd rather see implementations pick up new, reasonably-vetted 
> curves than try to muddle through supporting arbitrary curves 
> provided by the peer.

+1.

- -- 
/akr

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 28 Jan 2015 15:32:10 -0800

On Tue, Jan 27, 2015 at 7:41 AM, Dan Brown <[email-masked]> wrote:

> listed above, that accept generic specified short Weierstrass curves, but
> lock together the KDF and raw ECDH operations.  Users stuck with such
> implementations couldn’t gain _*all*_ the benefits of Curve25519, side
> channel resistance or whatever, but surely there’s some residual benefits
> for them to use Curve25519 with a generic representation: maybe the
> rigidity Curve25519, or interoperability with other users with the
> newfangled software, not to mention the blessing of the collective wisdom
> of CFRG.
>

I *strongly* oppose this entire proposal.

For D-H, Montgomery x-coordinates are way less error prone. Field
arithmetic bugs in Weierstrass implementations are common, and furthermore
old Weierstrass implementations that need to interoperate with Montgomery
x-coordinate representation can convert to Weierstrass. For signatures we
should be using Edwards for similar reasons.

My employer is doing something of this nature I can't disclose and it is
working quite well for us. That is just my personal opinion: I am not
speaking on behalf of my employer.

If you accept that we should be using Montgonery x-coordinates and Edwards
group elements to represent public keys (for D-H and signatures
respectively), then we get to djb's recent arguments that big endian is
more error prone.

Big-endian short-Weierstrass is the the most error-prone representation we
could possibly use, and legacy implementations can easily still use more
modern formats on the wire then convert to the representation they
implement natively.

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 28 Jan 2015 23:38:49 +0000

On 1/28/15, 18:10 , "Nico Williams" <[email-masked]> wrote:

>>……

The problem is - reasonably-vetted by who? NIST? DJB? Yourself? All of the
above?

Attractiveness of the ability to select a custom curve is similar to that
of PGP Web of Trust: you can make a choice for yourself, rather than being
forced into what other experts (or “experts” :) decide for you.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 28 Jan 2015 19:37:59 -0500

> group selection will be gone in TLS 1.3.

Right. The objective here is to dump all the existing code in the trash and
start again. Because we want the implementations to have constant time
implementations and to preclude the possibility of malicious point attacks
by choosing curves that allow us to easily compute y from an x, and only
sending the x.

What we want to avoid at all costs is patent encumbrances. Dumping
Weierstrass is a pretty good start because that was the favorite curve of
the folk who applied for most of the patents.

The only area where I did have concerns is that to be able to deploy crypto
on these platforms I have to be able to buy FIPS certified hardware or
equivalent. But I think we can probably put pressure on our vendors to
deliver in time. Before the new curves can be used in browsers for certs,
the browser providers are going to have to be satisfied.

In the near term, the application for this will be to make the use of an
ECDH ephemeral essentially cost free and the certified hardware issue is
not a show stopper. But I don't want to do that in a way that makes it
difficult to move to EC certificates in the future.

I don't accept that big endian is more error prone. The existing code for
X.509v3 crypto is all big endian. Changing that will introduce a new code
path and opportunity for error.

> muddle through supporting arbitrary curves provided by the peer.

I don't see how we can reasonably use custom groups in IETF protocols
because both sides have to agree to use the same group. And when one side
can propose the use of a malicious curve, the opportunity for perfidy is
created.

The Web PKI has never permitted the use of arbitrary curves in certs:

[https://cabforum.org/wp-content/uploads/BRv1.2.3.pdf]

CAs SHALL confirm that the RSA Public Key is at least 2048 bits or that one
of the following ECC curves is used: P-256, P-384, or P-521.

Now it should be quite easy to add the new curves to the list. I suspect
that unless the browser providers are feeling really generous, they will
expect us to end of life our existing ECC certs to get the new ones added.

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 29 Jan 2015 07:13:18 +0000

On 29/01/2015 00:37, Phillip Hallam-Baker wrote:

> Right. The objective here is to dump all the existing code in the 
> trash and start again. Because we want the implementations to have 
> constant time implementations and to preclude the possibility of 
> malicious point attacks by choosing curves that allow us to easily 
> compute y from an x, and only sending the x.
> 
> Weierstrass is a pretty good start because that was the favorite 
> curve of the folk who applied for most of the patents.

+1 to all of this.

> The only area where I did have concerns is that to be able to 
> deploy crypto on these platforms I have to be able to buy FIPS 
> certified hardware or equivalent.

It's probably going to have to be "equivalent", unless NIST surprise us
and come to like the curves and algorithms we do.

> Before the new curves can be used in browsers for certs, the 
> browser providers are going to have to be satisfied.

…and we're going to need a signature algorithm. Our draft doesn't have
one of those, and it seems what we're planning to do is do that in a
second phase, as you address.

> … But I don't want to do that in a way that makes it difficult to 
> move to EC certificates in the future.

Agreed.

> I don't accept that big endian is more error prone. The existing 
> code for X.509v3 crypto is all big endian. Changing that will 
> introduce a new code path and opportunity for error.

Two points here.

1. There's a special circle of hell reserved for those who maintain
   X.509v3 code, where they debug ASN.1 parsers for all eternity! <g>

   Seriously though, if I want to dump some TLS code in the bin and
   rewrite it because it's too hairy, X.509 would be the first thing on
   the list.

2. I think that may well be an engineering decision, for the TLS WG or
   PKIX WG. What we've got here is the wire format of the raw function,
   and I continue to think that's the best approach to keep.

   TLS WG already discussed this and used that directly - little-endian
   and everything - for their Curve25519 key-exchange draft. I see no
   reason to second-guess that. They then also specified new curve
   point formats should be opaque octet strings to them, with no
   special treatment. Doesn't sound like they think endian-swapping for
   transport wire formats is worth it from an engineering perspective.

   It'd probably have to be PKIX WG who figure out how to put the wire
   format of whatever signature algorithm we - later - specify into
   whatever format they specify. If they want LE, or BE, or BCD, or
   ASCII base-10, or wrap it in ASN.1 with an OID and a ribbon on top,
   isn't that properly for them to decide? Either way, I don't think
   that's a big deal: if they really want to endian-swap, they can, but
   I'm not sure we should pre-empt them here.

> Now it should be quite easy to add the new curves to the list. I 
> suspect that unless the browser providers are feeling really 
> generous, they will expect us to end of life our existing ECC
> certs to get the new ones added.

I can't speak for them of course, but that's not the impression I get
from either them or CAs? We aren't _replacing_ NIST curves as far as I
know in a near-term timescale, but providing a better alternative for
the future. NIST seem to have much less sway with NGOs than previously.

There will probably be a steady transition to using them, but, say,
those who need FIPS (as above) may never be able to, unless NIST
shadow our recommendations - which would honestly surprise me, but who
knows?

- -- 
/akr

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 29 Jan 2015 10:04:01 +0000

On 29/01/15 07:13, Alyssa Rowan wrote:
> unless NIST surprise us and come to like the curves and algorithms
> we do.

Well, NIST are planning a workshop on the topic so you have
the opportunity to submit a position paper or comment to the
effect that they ought do exactly that. Sometimes they are
fairly reasonable after all (though perhaps that is not the
overall impression one gets of 140-1;-)

Cheers,
S.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 29 Jan 2015 08:21:15 -0500

On Thu, Jan 29, 2015 at 5:04 AM, Stephen Farrell <[email-masked]>
wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>

Fortunately the decision making body relevant here isn't NIST, it is
CABForum which is the browser providers and CAs. And the issue there is
simply 'can we do this safely'.

So by FIPS-140 equivalent, what is meant is something that we can get a
group of experts to agree is equivalent and safe. It probably means that
the hardware is certified FIPS-140 but not necessarily for the particular
algorithm. This may or may not require wording changes but I don't expect
they would be controversial.

On the NIST side, I think that in the current circumstances it is very
likely we get a FIPS published on the new curves and algorithms. In the
medium term it is more or less certain. NIST exists to serve the needs of
commerce, not the other way round.

Snowden has changed the game in several ways. First, as in the Sony hack,
the real damage is done by revealing the trash talk inside the NSA. I have
my own theories about how the BULLRUN slides got made: Majors trying to
make Colonel by spinning their activities as meeting the director's fetish
for cyber-attack. Majors who don't make colonel become civilians so they
are likely to bend the truth. Only in the process they are essentially
saying that the NSA has been performing sabotage operations on other
government agencies. That type of behavior has consequences within a
bureaucracy, not just without.

The second, more important game change is that the NSA demonstrated that it
is unable to keep its own secrets, let alone advise the rest of government
on how to do it. And as BULLRUN demonstrates, it can't be trusted to do so
even if they were capable. Snowden has ended many military careers and
brought the survival of the NSA into question. I don't expect changes under
this president, but I think it very likely that the NSA loses
responsibility for information security assurance under the next and NIST
is the logical home.

So in these circumstances I expect NIST is very likely to be sanctioning
FIPS for the new curves, with or without NSA approval. The new curves are
technically superior and far more likely to appear in COTS products.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 29 Jan 2015 11:30:10 -0500

> The problem is - reasonably-vetted by who? NIST? DJB? Yourself? All of the

If this lengthy process we're involved in doesn't turn out to be
reasonable vetting by a multistakeholder group, i'll be sorely
disappointed.

> forced into what other experts (or “experts” :) decide for you.

This is different from the PGP Web of Trust.  If i'm communicating with
a new peer using TLS, and they want to use MagicCurveX that i've never
seen before, my TLS client is not going to be able to evaluate it
properly, certainly not before the TLS handshake expires.

Anyone can of course decide what curves are worth using, and can apply
their own analysis with their peers to come to that decision.  But if
you're communicating with the arbitrary outside world, there needs to be
some broader consensus about which curves to commonly use.

The act of naming and identifying the curve doesn't mean it's good, of
course; We have named codepoints for curves insufficient for modern
cryptanalysis, like sect163k1.  But you're right, people should be able
to use curves internally that no one else has to weigh in on.
fortunately, we can already do that (at least in TLS); we have a range
of the codepoints set aside for private use (RFC 4492):

  Values 0xFE00 through 0xFEFF are reserved for private use.

At any rate, saying that being able to select your curve using the
parameterized curve space, but leaving the algorithms and structure
(e.g. ECDSA, short-weierstrass) fixed by "experts" doesn't get all the
way the autonomy you want.  Better to use the private-use range, where
you can establish not just a curve of your choice, but also the
algorithms, point formats, etc.

  --dkg

---

From: Hanno Böck <[email-masked]>
Date: Thu, 29 Jan 2015 17:40:29 +0100

On Thu, 29 Jan 2015 07:13:18 +0000
Alyssa Rowan <[email-masked]> wrote:

> It's probably going to have to be "equivalent", unless NIST surprise
> us and come to like the curves and algorithms we do.

I hope I'm not telling any state secrets about NISTs plans here, but in
a conversation at RWC John Kelsey said something like "if the rest of
the Internet agrees on a good curve then probably NIST will just agree
to that".

I certainly understood it in a way that if CFRG comes up with something
that gets widespread support NIST will adopt that as their new
standard, too.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Dan Brown <[email-masked]>
Date: Thu, 29 Jan 2015 16:50:04 +0000

> Sent: Thursday, January 29, 2015 11:30 AM
> To: [email-masked]
> Subject: Re: [Cfrg] big-endian short-Weierstrass please
> 
> > The problem is - reasonably-vetted by who? NIST? DJB? Yourself? All of
> > the above?
> 
> If this lengthy process we're involved in doesn't turn out to be reasonable
> vetting by a multistakeholder group, i'll be sorely disappointed.
> 
> > Attractiveness of the ability to select a custom curve is similar to
> > that of PGP Web of Trust: you can make a choice for yourself, rather
> > than being forced into what other experts (or “experts” :) decide for you.
> 
> This is different from the PGP Web of Trust.  If i'm communicating with a new
> peer using TLS, and they want to use MagicCurveX that i've never seen before,
> my TLS client is not going to be able to evaluate it properly, certainly not before
> the TLS handshake expires.
> 
> Anyone can of course decide what curves are worth using, and can apply their
> own analysis with their peers to come to that decision.  But if you're
> communicating with the arbitrary outside world, there needs to be some
> broader consensus about which curves to commonly use.

[DB] Isn't TLS 1.3 proposing a DH group negotiation mechanism, where peers could configure their supported set of (EC)DHE group, then at run-time find something in the intersection of their supported curves?  Having an option to fully specify a custom curve in this mix is not requiring any peers to support MagicCurveX.  

> 
> The act of naming and identifying the curve doesn't mean it's good, of course;
> We have named codepoints for curves insufficient for modern cryptanalysis, like
> sect163k1.  But you're right, people should be able to use curves internally that
> no one else has to weigh in on.
> fortunately, we can already do that (at least in TLS); we have a range of the
> codepoints set aside for private use (RFC 4492):
> 

[DB] Wouldn't users of these private values have to then customize their software this?  Well, I guess TLS would work for that.  So, it seems that the advantage of specified curves, is that if a trustworthy WebSiteABC TLS server, elects to use MagicCurveX, then anonymous TLS clients could connect to WebSiteABC, relying on the current trust of the WebSiteABC, and their own software.

---

From: Nico Williams <[email-masked]>
Date: Thu, 29 Jan 2015 11:16:53 -0600

> The problem is - reasonably-vetted by who? NIST? DJB? Yourself? All of the

Besides the answers given already, this question is kinda strange.  Why
say "by whom"?  It's implied in "vetted" that the entities doing the
vetting are acceptable to the user.  And anyways, the question is not
relevant to Daniel K. G.'s point, which was: negotiate from sets of
known curves rather than negotiate arbitrary curves whose parameters get
sent to you by your peer.  If we do this then each curve can have its
own point format on the wire, with whatever endianness it wants.

(Mind you, point format could be yet another set of parameters to
negotiate, but why bother with so much complexity?)

Generalization often is nice, but here it would mean having to engage in
an expensive effort to write a pile of code that we wouldn't otherwise
need only for the sake of generalization.  I don't see a win there.

Dan B. doesn't need us to use a generic point encoding for all curves in
order for his preferred curves to be usable.  There is no advantage to
be had in using a generic point encoding here, and plenty of
disavantages (among them: more code, instant obsolescence of existing
implementations of curves we might end up approving of).  Please no.

> forced into what other experts (or “experts” :) decide for you.

Yes, you might trust your selection, but if your peers don't then you
lose.  The flip side is that if you want to talk to a peer that wants
you to use their curve, you might have to trust them, and how would you
know whether to trust them?  In a small network you could manage this,
and one generic point encoding will help you, but you could pick one
from a set of more than one.  And anyways, it'd be a small network --
why should the Internet community bend over backwards to make it easy
for you to pick your very own curves for use in your very own small
network?  There are still no advantages to be found in your proposition
for having one generic point format for all curves.

Outside your small network only pre-defined curves will work.  The
vetting is what we're doing now.  It doesn't have to happen only here,
and we needn't be the only vetters, but we don't need a single generic
point encoding to allow multiple vetters.

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Thu, 29 Jan 2015 09:25:53 -0800

On Jan 29, 2015 8:50 AM, "Dan Brown" <[email-masked]> wrote:
> > To:[email-masked]
reasonable
> > This is different from the PGP Web of Trust.  If i'm communicating with
a new
> > Anyone can of course decide what curves are worth using, and can apply
their
> [DB] Isn't TLS 1.3 proposing a DH group negotiation mechanism, where
peers could configure their supported set of (EC)DHE group, then at
run-time find something in the intersection of their supported curves?
Having an option to fully specify a custom curve in this mix is not
requiring any peers to support MagicCurveX.
> > The act of naming and identifying the curve doesn't mean it's good, of
course;
> > fortunately, we can already do that (at least in TLS); we have a range
of the
> [DB] Wouldn't users of these private values have to then customize their
software this?  Well, I guess TLS would work for that.  So, it seems that
the advantage of specified curves, is that if a trustworthy WebSiteABC TLS
server, elects to use MagicCurveX, then anonymous TLS clients could connect
to WebSiteABC, relying on the current trust of the WebSiteABC, and their
own software.

This is not how TLS negotiation works: the client offers and the server
picks. Due to vulnerabilities in all versions of TLS (still unfixed) one
always has to check the offered parameters for correctness.

That's on top of the fact that people don't want to use Curve25519 because
it's Curve25519. They want to use it because the design choices support
high speed secure implementations.

It's possible to get the existing extension to do this, but only if we have
a magic list of what to offer, and do all sorts of contortions in our
calculations. Much easier to negotiate an extension as the TLS WG
extensively discussed.

Sincerely,
Watson Ladd

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

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 29 Jan 2015 12:36:15 -0500

On Thu, Jan 29, 2015 at 11:30 AM, Daniel Kahn Gillmor <[email-masked]

+1

Deploying and implementing cryptosystems requires an enormous amount of
expertise and they can fail in many different ways of which a flaw in the
cryptographic algorithm security is very very rare.

We are not using the web of trust model to develop code so why on earth try
to apply it to choice of algorithm?

The reason for applying web of trust is when there is no good alternative.
I have written papers recently where I show how we might make the web of
trust tractable and practical but that is because validating credentials
for six billion people is a very different problem.

> some broader consensus about which curves to commonly use.

More importantly, I can't use your curves unless you can prove to me that
they are secure. And the fact we are having trouble doing that in this
group proves that it is not possible to achieve that in a protocol.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 29 Jan 2015 09:50:37 -0800

On Jan 29, 2015 9:36 AM, "Phillip Hallam-Baker" <[email-masked]>
wrote:
>
>
>
> On Thu, Jan 29, 2015 at 11:30 AM, Daniel Kahn Gillmor <
the
that
>
> We are not using the web of trust model to develop code so why on earth
try to apply it to choice of algorithm?
>
> The reason for applying web of trust is when there is no good
alternative. I have written papers recently where I show how we might make
the web of trust tractable and practical but that is because validating
credentials for six billion people is a very different problem.

We are not having trouble with that  in this group. Nobody disputes that
any of the proposed curves are secure, or the details of generation.

Instead, we're arguing about endiannes. I've tried to gather which primes
everyone wants in one list, crickets.  Tony Arceli posts about signatures,
5 messages. Big v. Little, 40.

Of course a malicious party can leak whatever you send them.

Sincerely,
Watson Ladd

---

From: Dan Brown <[email-masked]>
Date: Thu, 29 Jan 2015 17:58:03 +0000

>From: Watson Ladd [mailto:[email-masked]]
>>  >>server, elects to use MagicCurveX, then anonymous TLS clients could 
>> connect to WebSiteABC, relying on the current trust of the WebSiteABC, and 
>> their own software.

>always has to check the offered parameters for correctness.

[DB] Ah, too bad. I guess named curves (and FFDHE groups) is, among other 
things, one way to fix this problem with TLS.  (I vaguely recalled a proposal 
for the server being able to suggest alternatives outside the clients' list, I 
guess I misremembered.)

Anyway, to paraphrase others, a downside of TLS limiting curves to a small 
set, is this limitation can be spun sourly, albeit a tad unfairly, as 
pressuring users to use particular curves. That said, leaving in arbitrary 
curves, can also be spun badly, too, catch 22.

>it's Curve25519. They want to use it because the design choices support high 
>speed secure implementations.

[DB] Right, but other users might want to use some other curves with high 
speed secure implementations, e.g., maybe a larger curve, but they disagree 
with CFRG advice about rigidity, etc.

>It's possible to get the existing extension to do this, but only if we have a 
>magic list of what to offer, and do all sorts of contortions in our 
>calculations. Much easier to negotiate an extension as the TLS WG extensively 
> >discussed.

---

From: Nico Williams <[email-masked]>
Date: Thu, 29 Jan 2015 12:13:44 -0600

> curves, can also be spun badly, too, catch 22.

We can haz both even, though I don't see the value in it; known curves
FTW.  The key is to have a relatively open curve registry (open -> less
than IESG Protocol Action should be needed to register, probably Expert
review).

The same is true for traditional DH.  We've had known groups for a long
time.  Some protocols (e.g., SSHv2) allow negotiation of arbitrary
groups, but a) it takes a long time to generate them, b) it takes longer
to validate (then use) them than it would to just use an off-the-shelf
group.  I would say that arbitrary group negotiation is a failure in all
cases.

> with CFRG advice about rigidity, etc.

See point above about a curve registry.  For protocols like SSHv2 where
there's a large private-use namespace for curve names, a registry is not
even required, and the Internet can come to consensus by market
mechanisms.

A generic point format for all curves to use is simply not something we
need for anyone's favorite curves (or curve families) to be deployable.

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 29 Jan 2015 13:18:44 -0500

On Thu, Jan 29, 2015 at 12:50 PM, Watson Ladd <[email-masked]> wrote:
>
> > More importantly, I can't use your curves unless you can prove to me
> that they are secure. And the fact we are having trouble doing that in this
What I meant is that we had great difficulty in choosing curve parameters
that were not suspect so we developed objective criteria that effectively
removed the 'malicious curve' issue.

At this point I am pretty certain that I will not want to use my existing
crypto boxes for the new curves. I certainly don't want my keys for the
algorithms we chose for their constant time implementation friendliness
being implemented on legacy hardware.

I am not keeping score here, but my understanding is that we have a rough
consensus for P255 for the performance curve as it is as near as damnit 256
bits, very fast and has a lot of deployment support. Arguing over a single
bit seems illogical for a performance curve that is going to be used in TLS
for ephemeral encryption, particularly if we can fix the TLS key agreement
algorithm so that ephemeral agreed keys are always at least as random as
both the master key and the ephemeral inputs.

The ridiculously high assurance prime is a different matter. Perhaps what
CFRG should do is to choose both P512 curve and P448.

Curves are a different matter... I doubt that it really matters very much
and the differences in speed are likely to turn out to depend on whose
hardware is used.

Easiest to explain is probably the best criteria.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 29 Jan 2015 21:05:47 +0200

> We are not having trouble with that  in this group. Nobody disputes that any of the proposed curves are secure, or the details of generation.
> 
> Instead, we're arguing about endiannes. I've tried to gather which primes everyone wants in one list, crickets.  Tony Arceli posts about signatures, 5 messages. Big v. Little, 40.
> 
That's Parkinson’t law of triviality at work. Few understand why one prime is better than another. A few more understand about implementing signature algorithms, but we all understand endianness.

Although that would make the signature algorithms the bike shed, and the endianness coffee.

Regarding primes I think there were a bunch of people saying “yeah, let’s pick goldilocks" a while ago.  Hopefully we know enough about signatures to not make the bike shed of asbestos (in the book the argument is about the material for the bike shed, not the color)

Yoav

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 29 Jan 2015 19:46:49 +0000

>>> they are secure. And the fact we are having trouble doing that in this group
>>> proves that it is not possible to achieve that in a protocol.
>> 
>> We are not having trouble with that  in this group. Nobody disputes that any
>> of the proposed curves are secure, or the details of generation…

No, in this group we don’t seem to be having trouble with that. But I’m sure
NIST did not have any trouble with security of their selected curves.
Likewise, BRAINPOOL didn’t seem to worry about security of theirs (ask
Tanja, she was there :), DJB is certain of his curves, etc.

See my point? How would you convince others that BRAINPOOL might have had
something up their collective sleeve, but you don’t?
>> removed the 'malicious curve' issue.

Exactly.

> Curves are a different matter... I doubt that it really matters very much and
> the differences in speed are likely to turn out to depend on whose hardware is
> used. 
> 
 
Probably so.

---

From: Nico Williams <[email-masked]>
Date: Thu, 29 Jan 2015 13:59:19 -0600

> That's Parkinson’t law of triviality at work. Few understand why one prime is better than another. A few more understand about implementing signature algorithms, but we all understand endianness.

It's not.

I sent Watson a private response about that, but I guess we must have
this discussion on the list instead.

It seems consensus on curves is almost there.  The basepoint discussion
for Curve25519 could be restarted and it could draw lots of posts (I bet
it will), but otherwise I think it unsurprising that there's little
discussion.

Signature algorithms will be next up, but first things first.  Again, no
surprise about relative post numbers on this.

ECDH point representation on the wire, OTOH, may seem trivial in theory,
but it's not trivial in reality because there exists running code and
because there are patent issues.  It's utterly unsurprising that a
proposal that would instantly obsolete running, unencumbered code just
to generalize point representation so any arbitrary curve anyone can
think of can just be plugged in..., and which would also likely have the
side-effect of patent-encumbering new implementations.... would draw
many comments.

> Although that would make the signature algorithms the bike shed, and

We're past endianness.  Much of this thread has been about generic point
encoding (Dan Brown's proposal).

Some details really matter.  These aren't trivialities.

Nico
--

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 29 Jan 2015 12:02:05 -0800

> On Jan 29, 2015, at 11:46 AM, Blumenthal, Uri - 0558 - MITLL <[email-masked]> wrote:
> 
>>> > More importantly, I can't use your curves unless you can prove to me that they are secure. And the fact we are having trouble doing that in this group proves that it is not possible to achieve that in a protocol.
>>> We are not having trouble with that  in this group. Nobody disputes that any of the proposed curves are secure, or the details of generation…
> No, in this group we don’t seem to be having trouble with that. But I’m sure NIST did not have any trouble with security of their selected curves. Likewise, BRAINPOOL didn’t seem to worry about security of theirs (ask Tanja, she was there :), DJB is certain of his curves, etc.
> 
> See my point?

No. Are you saying that you will only use curves that NIST says are secure? Or that somehow CFRG has to convince NIST?

> How would you convince others that BRAINPOOL might have had something up their collective sleeve, but you don’t?

That seems irrelevant. Some people will never be convinced of some things that most other people agree to.

--Paul Hoffman

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 29 Jan 2015 20:23:06 +0000

>>No, in this group we don’t seem to be having trouble with that. But I’m
>>sure NIST did not have any trouble with security of their selected
>>curves. Likewise, BRAINPOOL didn’t seem to worry about security of
>>theirs (ask Tanja, she was there :), DJB is certain of his curves, etc.
>> 
>> See my point?
>
>No. Are you saying that you will only use curves that NIST says are
>secure? Or that somehow CFRG has to convince NIST?

No. How about “I trust neither NIST nor you, and probably you less than
NIST”? 

>That seems irrelevant.

???

>Some people will never be convinced of some things that most other people
>agree to.

:-)

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 29 Jan 2015 15:51:08 -0500

On Thu, Jan 29, 2015 at 3:02 PM, Paul Hoffman <[email-masked]> wrote:

> >>> We are not having trouble with that  in this group. Nobody disputes
> that any of the proposed curves are secure, or the details of generation…
> sure NIST did not have any trouble with security of their selected curves.

What is being argued against here is making room for DIY curves.

My point is that the only way to come up with an informed decision to use
someone else's curves is to apply a vast amount of domain specific
expertise plus really trust the supplier to not have something up their
sleeves.

We are working on a scheme to reduce the amount of scope of 'up our
sleeves' to the absolute minimum or close to it and getting what is surely
the best available expertise from the field to comment.

So I think we can come up with a decision here but the process makes me
certain that there is no possibility that two random computers could
negotiate a secure set of curves on the Internet via a protocol. Unless
that is we assume some form of out-of-band trust relationship.

My view is that we should pick Curve 25519 because it is a decent balance
of expediency and security for the performance curve and P512 because it
removes virtually all possibility of 'up their sleevesies' argument for the
highest assurance curve.

While it is true that there are multiple forms in which the curves might be
expressed, these issues are really very much less of a concern because
first, all the curves we are discussing are isomorphic.

That said, I prefer the Edwards curves because I can explain them to other
folk without resorting to abstract math (now I have been given the link to
DJB's presentation at Chaos). The use of The Wierstrass forms are much less
friendly.

http://www.youtube.com/watch?v=l6jTFxQaUJA

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Thu, 29 Jan 2015 21:28:57 +0000

> someone else's curves is to apply a vast amount of domain specific expertise
> plus really trust the supplier to not have something up their sleeves.

Unless that “somebody else” is your boss, or somebody you have informed
reasons to trust.

Some people (and organizations :) tend to trust “their” experts, and not
trust “other” experts as much. As an example – why didn’t NSA adopt Russian
GOST, and why didn’t Russians adopt AES? Probably not because they question
the competence of the other side? :-)

I’m arguing that there is a need for DIY curves, on both personal and
“organizational” level.

> certain that there is no possibility that two random computers could negotiate
> a secure set of curves on the Internet via a protocol. Unless that is we
> assume some form of out-of-band trust relationship.

There should be a set of “universally” accepted curves, so that when you
want to talk to a complete stranger – both of you would use what the
“community” considers cryptographically OK (which belongs to that small
commonly shared set). But that’s only half of use cases.

There should be an option to specify “my own” curves, so that when, e.g. one
“team" member wants to talk to his peer – their software will pick that
special curve that was for whatever reasons approved by their boss, or
refuse to connect. Because in that context ability to establish a connection
with a stranger is underisable.

> My view is that we should pick Curve 25519 because it is a decent balance of
> expediency and security for the performance curve and P512 because it removes
> virtually all possibility of 'up their sleevesies' argument for the highest
> assurance curve…..

I see your point.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 29 Jan 2015 16:51:51 -0500

> with a stranger is underisable.

This is what having a private use range in a labelled registry is for.

For TLS, we have that already (0xfe00 - 0xfeff).

If you can agree out-of-band on a curve already, because your boss says
you should use it, fine, use the private range.  If you can't agree
out-of-band on a curve, having custom curves doesn't help you.

     --dkg

---

From: Nico Williams <[email-masked]>
Date: Thu, 29 Jan 2015 15:54:23 -0600

> I’m arguing that there is a need for DIY curves, on both personal and

That's not really what is causing debate.  The associated proposal for a
one-size-fits-all point representation is.  DIY curve negotiation could
include point representation negotiation, though the cost in terms of
generic code would be non-trivial, but then, so is the cost of DIY
curves in general, thus I don't mind that cost.

Drop the one-size-fits-all point representation proposal and this thread
goes quiet and we can expend effort on those remaining issues that
matter the most right now (amongst which DIY-curves isn't, not for me
anyways).

> commonly shared set). But that’s only half of use cases.

If a community can agree a priori on a set of specific curves, then
there's no need for DIY curves, just a registry of DIY curves.

OTOH, if the two strangers meeting by chance don't have a common
community yet still want to pick one of their DIY curves, then we need
DIY curve support in the protocol, and one has to wonder: why would the
other stranger trust the first as to choice of DIY curve?!  Which
thought leads me to conclude that we don't need DIY curves, just a
registry that is open enough to represent a superset of communities (the
two strangers still need to agree as to a common subset of that, of
course).

> with a stranger is underisable.

How do you not get this with a registry?

> > DJB's presentation at Chaos). The use of The Wierstrass forms are much less

There is that too.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 29 Jan 2015 18:33:28 -0500

On Thu, Jan 29, 2015 at 4:28 PM, Blumenthal, Uri - 0558 - MITLL <
[email-masked]> wrote:

> Some people (and organizations *:*) tend to trust “their” experts, and
> not trust “other” experts as much. As an example – why didn’t NSA adopt
> Russian GOST, and why didn’t Russians adopt AES? Probably not because they
> question the competence of the other side? :-)
>

And such people are more than welcome to make use of the existing extension
features in TLS 1.x.

If you think you have the ability to do this for yourselfs then do it.

However I should point out that for TLS 2 I think a very different approach
should be taken.

* Exactly one preferred (MUST) and one backup algorithm (SHOULD) defined in
the protocol with an algorithm numbering scheme that allows only 255 values
for each. The objective being to keep algorithm changes to once a decade.
This would require us to rev the TLS major version at least once every
other millennia.

* All other crypto to be identified by ASN.1 OID on a 'its your funeral'
basis.

The rationale for this is that the IETF currently has three types of
algorithm.

1) Those that we have vetted and trust.
2) Those that we have assigned numbers to
3) Those that we have not

The problem in my view is that people seem to think that algorithms of type
2 are somehow different than type 3 and this is really not the case. We do
not have the bandwidth to validate vanity crypto and algorithms like GOST
are mandated by governments who murder their citizens on the streets of
London with polonium laced teapots. So I really don't feel like giving any
accreditation to such folk.

So lets just have two types of crypto algorithm: Those we are really
confident of and those we make no comment on.

> commonly shared set). But that’s only half of use cases.

No, actually that is 100% of the uses for the Internet. All other cases are
'network' security and that is not our problem.

One of the problems with IP everywhere is that we have ended up in a
situation where it is assumed that we have a duty to solve every type of
networking problem.

I think providing security advice to people who don't want to follow our
security advice is the first thing to stop trying to do.

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 31 Jan 2015 23:32:18 -0800

On 01/29/2015 05:21 AM, Phillip Hallam-Baker wrote:
> the hardware is certified FIPS-140 but not necessarily for the
> particular algorithm. This may or may not require wording changes but I
> don't expect they would be controversial.

Unless the new curve is accepted along the lines of P-256 by NIST, it 
will be treated no much differently than CAMELIA (or DES).

Without this change, the new curve is a Non-Approved security function 
and it can only be used in non-Approved modes of operation. Crypto 
module documentation will need to make this clear, per FIPS 140-2.

It's a known trick to certify only AES and then somehow make an 
impression that other algorithms are covered by the same module. NIST 
put multiple notes to make this harder. Thus, NIST will need to 
explicitly bless the new curve. A precedent for this is the TLS KDF.