Subject: [Cfrg] Curves specification possibly complete.

From: Adam Langley <[email-masked]>
Date: Wed, 19 Aug 2015 09:10:29 -0700

With the publication of -04
(https://tools.ietf.org/html/draft-irtf-cfrg-curves-04), I hope that
the work on specifying the curves is basically complete now. Whether
we wait for the signatures work to be completed is up to the chairs
but, either way, I'm hoping that text as currently included will not
need to be substantially revisited in the future.

So, now is a good time to let me know about any issues you find in -04
so that they don't interfere with discussions in the future.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 19 Aug 2015 19:34:26 +0300

> need to be substantially revisited in the future.

Would including recommended point format for the Edwards stuff be
useful?

E.g. Little-endian encoding of y in minimum bits, with LSB of x
in bit 7 of the last byte  (IIRC, this is the point format used
by EdDSA).

(Looks like using bit7 is simpler than using next available bit).

-Ilari

---

From: Adam Langley <[email-masked]>
Date: Wed, 19 Aug 2015 10:42:24 -0700

> (Looks like using bit7 is simpler than using next available bit).

I think we will need to specify this at some point. I don't have a
strong opinion about whether it should be considered part of the
"curves" or "signature" half.

Did you mean the sign of x rather than the LSB?

For edwards448 (i.e. Goldilocks), the last byte is fully used so we
would need to add another byte. I don't care whether the sign bit is
bit 7 or 0 or that, however.

Cheers

AGL

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 19 Aug 2015 21:17:44 +0300

> "curves" or "signature" half.

Well, there are some non-ECDH, non-signature uses of ECC, pretty
marginal tho.

> Did you mean the sign of x rather than the LSB?

No, the LSB of x.

Grabbing the LSB is easier than comparing the number to some
annoying constant, and unless x=0, x and -x (in which case x and -x
are the same) have the opposite LSB for GF(p).

For reasonably reduced values of special primes, LSB of x is XOR of
two bits in x.
 
> bit 7 or 0 or that, however.

I just think that if multiple curves is supported that placing it at
bit 7 is a bit easier than bit 0 ("next bit"). Very little difference
tho.

-Ilari

---

From: Deirdre Connolly <[email-masked]>
Date: Wed, 19 Aug 2015 15:21:59 -0400

On Wed, Aug 19, 2015 at 12:10 PM, Adam Langley <[email-masked]> wrote:
> the work on specifying the curves is basically complete now.
>

Some nits on clarity:

Section 4.2:

"That curve is also 4-isogenous to the following Edward's curve..."

Clarify that "that curve" is the Montgomery form ('curve448'), not the
first Edward's form immediately preceding that line.

"The 4-isogeny maps between the Montgomery curve this the Edward's curve are..."

I understood this to mean the maps are between the Montgomery curve
('curve448') and the last defined Edward's curve ('edwards448') but it
can be more explicit.

Also there are instances of "Edward's" and "Edwards" throughout,
whichever one is preferred should be used consistently.

Cheers,
-DC-

---

From: Deirdre Connolly <[email-masked]>
Date: Wed, 19 Aug 2015 15:38:03 -0400

On Wed, Aug 19, 2015 at 3:29 PM, Mike Hamburg <[email-masked]> wrote:
> This line is worth clarifying. However, both forms are 4-isogenous to "the following Edwards curve", because isomorphisms compose with isogenies.
>

Excellent, then maybe something like "'curve448' and the previous
Edwards curve are also 4-isogenous to [edwards448]" would make that
relationship more explicit.

Thanks!

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 19 Aug 2015 14:17:25 -0700

In reading through the section on  DH, I got a surprise and I would like to
verify that it is intentional.

The text says:

Alice and Bob can then use a key-derivation function that includes K, K_A
and K_B to derive a key.

The normal text would say that one uses a KDF function that includes K to
derive a key.  Is this text intentional?

Jim

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Adam Langley
> Sent: Wednesday, August 19, 2015 9:10 AM
> To: [email-masked]
> Subject: [Cfrg] Curves specification possibly complete.
> 
> (https://tools.ietf.org/html/draft-irtf-cfrg-curves-04), I hope that the
work on
> specifying the curves is basically complete now. Whether we wait for the
> signatures work to be completed is up to the chairs but, either way, I'm
hoping
> that text as currently included will not need to be substantially
revisited in the
> future.
> 
> So, now is a good time to let me know about any issues you find in -04 so
that
> they don't interfere with discussions in the future.
> 
> 
> Cheers
> 
> AGL
> 
> --
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Wed, 19 Aug 2015 17:21:16 -0700

> derive a key.  Is this text intentional?

Yes. Although using K alone is generally fine, some IETF protocols require
contributory behavior. Not hashing KA and KB would break these protocols.

> > So, now is a good time to let me know about any issues you find in -04
so

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 19 Aug 2015 18:14:15 -0700

From: Watson Ladd [mailto:[email-masked]] 
Sent: Wednesday, August 19, 2015 5:21 PM
To: Jim Schaad
Cc: Adam Langley; [email-masked]
Subject: Re: [Cfrg] Curves specification possibly complete.

> derive a key.  Is this text intentional?

Yes. Although using K alone is generally fine, some IETF protocols require contributory behavior. Not hashing KA and KB would break these protocols.

Watson,  I want to make sure that I am hearing you correctly.

You are stating that there is information in KA and KB which is not adequately reflected in K at all times.  And that this information is only needed for some protocols and not for others.

An expansion of when the information is needed would be appreciated.  

> > From: Cfrg [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Adam Langley
> > To: [email-masked] <mailto:[email-masked]> 
> > Adam Langley [email-masked] <mailto:[email-masked]>  https://www.imperialviolet.org
> >
> > [email-masked] <mailto:[email-masked]> 
> [email-masked] <mailto:[email-masked]>

---

From: Adam Langley <[email-masked]>
Date: Wed, 19 Aug 2015 19:33:30 -0700

On Wed, Aug 19, 2015 at 6:14 PM, Jim Schaad <[email-masked]> wrote:
> You are stating that there is information in KA and KB which is not
> adequately reflected in K at all times.  And that this information is only
> needed for some protocols and not for others.
>

The requirement in the draft that the all-zero output be rejected
should make this suggestion about the KDF inputs moot. But it's rarely
a bad idea to hash in more things.

About this specific issue: Tor was broken by it once upon a time,
although it was finite-field DH in that case. An attacker could change
the DH public value in a Tor relay handshake to zero in both
directions and then both sides would calculate zero as the key.
Everything would appear to work, but the attacker now knows the key.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 20 Aug 2015 10:06:51 -0700

> ('curve448') and the last defined Edward's curve ('edwards448') but it

I've clarified it to say that both are 4-isogenous to edwards448.

> whichever one is preferred should be used consistently.

I've banished "Edward's" in favour of "Edwards".

Thanks!

(I'll send out -05 in a sec.)

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Thu, 20 Aug 2015 10:17:01 -0700

> (I'll send out -05 in a sec.)

See https://mailarchive.ietf.org/arch/msg/cfrg/_9ts0QAI3Nt_DlVLlyC-8BZq7kI

Please send me anything for -06 tomorrow :)

Cheers

AGL

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 21 Aug 2015 23:01:45 +0200

> so that they don't interfere with discussions in the future.

1) There is no Security Considerations, perhaps they not required for
CFRG documents?

2) Given the dangers of side-channels, I believe a section discussing
that separately has merit.  Compare with A.3 in our document describing
Curve25519: https://tools.ietf.org/html/draft-ietf-tls-curve25519-01

For example, how about replacing the following short paragraph inside
the algorithm description:

   When implementing this procedure, due to the existence of side-
   channels in commodity hardware, it is important that the pattern of
   memory accesses and jumps not depend on the values of any of the bits
   of "k".  It is also important that the arithmetic used not leak
   information about the integers modulo p (such as having b*c be
   distinguishable from c*c).

with a section like the following.  I suggest placing this as section
5.1 and renumber your current '5.1 Test vectors' to section 5.2.

  5.1  Side-channel considerations

   Curve25519 and Curve448 were designed so that correct, fast,
   constant-time implementations are easier to produce.  In particular,
   using a Montgomery ladder as described in the previous section
   ensures that, for any valid value of the secret key, the same
   sequence of field operations are performed, which eliminates a major
   source of side-channel leakage.

   However, merely using a Montgomery ladder does not prevent all
   side-channels by itself, and it is important that the pattern of
   memory accesses and jumps not depend on the values of any of the bits
   of "k".  It is also important that the arithmetic used not leak
   information about the integers modulo p (such as having b*c be
   distinguishable from c*c), by avoiding data-dependant branches and
   memory access patterns.

   Techniques for implementing the field operations in constant time and
   with high performance are out of scope of this document.

   Side-channel attacks are an active reseach domain that still sees new
   significant results, so implementors of the Curve25519 function are
   advised to follow recent security research closely.

/Simon

---

From: Adam Langley <[email-masked]>
Date: Wed, 26 Aug 2015 09:18:34 -0700

> 1) There is no Security Considerations, perhaps they not required for

I'm not sure. What would even go in it? "See rest of document"?

>    advised to follow recent security research closely.

I'm not sure that all those words are needed, but it does seem
reasonable to highlight the side-channel concerns by putting a section
title above them rather than having them be at the end of a longish
section.

So I've made it a section in -06 (which will be out in a minute) and
included some of your text. Thanks!

AGL

---

From: Yoav Nir <[email-masked]>
Date: Wed, 26 Aug 2015 21:30:43 +0300

> On Aug 26, 2015, at 7:18 PM, Adam Langley <[email-masked]> wrote:
> 
> I'm not sure. What would even go in it? "See rest of document”?

This could get some push-back, but perhaps a variation on the section in RFC 5069?

https://tools.ietf.org/html/rfc5069#section-7

Yoav

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 26 Aug 2015 22:51:35 +0100

Drat! I was half done with -05 and there you go making it better:-)

I've only one substantive comment so far though and some (very
ignorable nits). I hope to get time to read it in more detail but
since that mightn't happen or you may be on -99 before I get to
it, my comments on -05 are below.

I do think this is sufficiently baked to go forward in case that
isn't clear.

Cheers,
S.

Only one substantive comment:

- The (currently missing) security considerations (or somewhere)
should describe why Curve25519 is ok when used in contexts where we'd
otherwise ask for 128 bit strength, (basically because it's close
enough), and also why the 224 bit level is considered a good choice.
There was a lot of debate on the list about that, and I've seen the
issue come up elsewhere so this text will avoid re-litigating that and
should be worthwhile even if it takes a little time to agree.

nitty-nits: (which are ok to ignore)

- title/abstract: we're not including the signature scheme based on
these curves in this document. But we do talk about ECDH.  Shouldn't
that be reflected in the title/abstract?

- intro: wouldn't a reference to RFC6090 be useful as well as or
instead of [SEC1]? 6090 does after all have references to very old
descriptions of ECC.

- intro, para 2: wouldn't it be more accurate to say that these curves
lend themselves to natural constant-time implementations rather than
say that they "support" constant time?

- intro: references for Montgomery and Edwards would be good.  (And
ones suited for implementers, not mathematicians.)

- section 5, para 1: be good to say that the 32 byte output is for
X25519 and the 56 for X448. (Yes, it's obvious but good to be
precise.)

- section 5, para 2: you start with u[0] and end with u[n] - isn't it
more common to end with u[n-1] there? In this case it doesn't matter
as you don't say n=32 or n=56 but maybe there's a small chance that
might trip up some coder somewhere (though it's hard to see how so
consider this a totally pedantic nit, offered just to see who else
wants to be pedantic:-)

- section 5: the RFC editor will ask if you want "CODE BEGINS" markers
around the python code.

- section 5, last para on p8: you say here it's important to not do a
bad thing, but you don't say (or provide a reference as to) how to
avoid the bad thing.

- I think section 7 could now be placed in an appendix.

- section 7: trace of Frobenius needs a reference, as do MOV degree
and CM discinimant. If the current references explain those then say
so.

- I think this draft should have security considerations that say a
little about good implementations, mainly via reference if possible.

- An RFC6982 "implementation status" section could be useful here as I
guess we don't really want all and sundry writing the code for all
this. Note that that could be useful even if the text doesn't end up
in the RFC - people will find it anyway. (And I think 6982 was wrong
in saying such sections should be deleted before RFC publication.)

To re-iterate - all these nits are just that and I am ok if they are
utterly ignored.

---

From: Adam Langley <[email-masked]>
Date: Sat, 29 Aug 2015 09:28:05 -0700

> should be worthwhile even if it takes a little time to agree.

I suspect this section to be inherently controversial :)

This is what I have for now:

-----
The security level (i.e. the number of "operations" needed for a
brute-force attack on a primitive) of curve25519 is slightly under the
standard 128-bit level. This is acceptable because the standard
security levels are primarily driven by much simplier, symmetric
primtives where the security level naturally falls on a power of two.
For asymmetric primitives, rigidly adhering to a power-of-two security
level would require compromises in other parts of the design, which we
reject. Additionally, comparing security levels between types of
primitives can be misleading under common threat models where multiple
targets can be attacked concurrently [bruteforce].

The ~224-bit security level of curve448 is a trade-off between
performance and paranoia. Large quantum computers, if ever created,
will break both curve25519 and curve448, and reasonable projections of
the abilities of classical computers conclude that curve25519 is
perfectly safe. However, some designs have relaxed performance
requirements and wish to hedge against some amount of analytical
advance against elliptic curves and thuscurve448 is also provided.
-----

> that be reflected in the title/abstract?

The title and abstract only promises to define curves so I think it's
OK that we don't define a signature scheme. But I've now mentioned in
the introduction that we'll specify how to do ECDH.

> instead of [SEC1]? 6090 does after all have references to very old

Done.

> say that they "support" constant time?

Done.

> ones suited for implementers, not mathematicians.)

I don't know of any references for Montgomery and Edwards curves that
aren't significantly mathematical I'm afraid.

> X25519 and the 56 for X448. (Yes, it's obvious but good to be

Done.

> consider this a totally pedantic nit, offered just to see who else

No, you're correct! Since it starts at zero it's best to run to n-1.

> - section 5: the RFC editor will ask if you want "CODE BEGINS" markers

I'm not sure and I don't know what the code begin/end markers in RFCs
are. Really the code should be treated as pseudo-code. Some of the
functions are actual Python, but some are not.

> bad thing, but you don't say (or provide a reference as to) how to

That's true, but I don't know how to fix it without making the draft
twice as long by including detailed discussions of constant-time
implementation. The current wording points out some obvious issues
(such as "optimising" squaring at run-time) but I don't think that we
can enumerate all the pitfalls.

> - I think section 7 could now be placed in an appendix.

Done.

> and CM discinimant. If the current references explain those then say

I've added a reference for MOV degree, but for the others the
reference would really be to a textbook on elliptic curves, which
seems unhelpful. I think people would just have to Google for them.

> in saying such sections should be deleted before RFC publication.)

I don't want to get into the fight about whether RFC 6982 sections
need to be deleted before publication and, assuming that they do
(since that's what's documented), it doesn't seem worthwhile to write
such a section to live only a short while.

Cheers

AGL

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 29 Aug 2015 19:01:18 +0100

Hiya,

> I suspect this section to be inherently controversial :)

Yeah sorry about that, but taking the hit once now is probably better
than doing it over and over in multiple IETF WGs. That said, I think
your text is very good *and* reflects the list discussion as I recall
it so if we're lucky nobody will quibble:-)

Cheers,
S.

PS: all your nit-unpicking is just fine