Subject: [Cfrg] On the use of Montgomery form curves for key agreement

From: Brian LaMacchia <[email-masked]>
Date: Mon, 1 Sep 2014 18:46:34 +0000

Folks,

Here are the points that must be considered regarding the potential selection of a Montgomery form curve (and its realization using the Montgomery ladder):

1.       Requiring a Montgomery form curve for key agreement and for a particular security level means that implementations of protocols with both key agreement and digital signatures must implement both Montgomery curve arithmetic and additionally curve arithmetic for another curve form.  From an engineering perspective there is thus a clear drawback to requiring different curve forms for key agreement and digital signature at the same security level.

2.       Assuming that implementations will implement more than one security level, choosing X25519 for ECDHE at the 128 bit security level will require implementations to use different curve arithmetic for the 128 bit security level than other security levels.  Again from an engineering standpoint this is a negative.

3.       Despite repeated claims to the contrary, there is little evidence that there is a consistent and significant performance benefit to X25519. Indeed, as both the performance numbers in http://eprint.iacr.org/2014/130.pdf as well as the more recent performance numbers posted by Andrey Jivsov demonstrate, the performance of X25519 does not significantly differ from that of (twisted) Edwards curves for (non-ephemeral) ECDH at the same size.  For the case of ECDHE, Dan Bernstein has argued for a definition of “ephemeral” that would allow keys to be re-used for some amount of time allowing X25519 implementations to amortize the cost of operations which are particularly expensive for X25519 over multiple uses of the same key.​ Such arguments are intended to wrap requirements around specific curves, which is inappropriate for this process. There has been no legitimate argument put forward for repeated use of ephemeral keys in ECDHE.  As a consequence, the adoption of a definition of “ephemeral” that does not allow key re-use (as previously recommended) means that implementations of X25519 would require conversions between curve forms to avoid a significant loss in performance. These conversions are a negative from an engineering perspective.

Those arguing for adoption of X25519 are requesting that CFRG (a) treat the 128 bit security level different from other security levels, (b) force implementations of multiple security levels of key agreement to implement different curve arithmetic for different security levels, (c) force implementations of protocols with both key agreement and digital signatures to implement different curve arithmetic for those two operations, even at the same security level, (d) force point conversions between curve forms to avoid efficiency loss in ECDHE, and (e) to do (a)-(d) for no clear gain in performance. These points overwhelmingly contradict arguments in favor of forcing the use of the Montgomery form for key agreement, especially for only a single security level.

--bal

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 1 Sep 2014 11:54:46 -0700

On Mon, Sep 1, 2014 at 11:46 AM, Brian LaMacchia <[email-masked]> wrote:
> Folks,
>
>
>
> Here are the points that must be considered regarding the potential
> selection of a Montgomery form curve (and its realization using the
> Montgomery ladder):
>
>
>
> 1.       Requiring a Montgomery form curve for key agreement and for a
> particular security level means that implementations of protocols with both
> key agreement and digital signatures must implement both Montgomery curve
> arithmetic and additionally curve arithmetic for another curve form.  From
> an engineering perspective there is thus a clear drawback to requiring
> different curve forms for key agreement and digital signature at the same
> security level.

You can do arithmetic on a curve points given in Montgomery form
without a Montgomery ladder implementation by converting to a
different coordinate system.  I'm not sure why you'd want to in
anything other than the tiniest embedded implementation, but you
could.

Also, can we please stop claiming that things are "clear" problems?
This isn't clearly a problem.  As has been noted as nauseum on this
list, most of the work is in the field arithmetic, and a Montgomery
ladder and, say, Edwards EC arithmetic can share that.

>
> 2.       Assuming that implementations will implement more than one security
> level, choosing X25519 for ECDHE at the 128 bit security level will require
> implementations to use different curve arithmetic for the 128 bit security
> level than other security levels.  Again from an engineering standpoint this
> is a negative.

You're pre-supposing that other security levels wouldn't use
Montgomery coordinates.

[...]

>
> Those arguing for adoption of X25519 are requesting that CFRG
= (a) treat the
> 128 bit security level different from other security levels,

This is the first time that I've seen this request on this list.

> (b) force
> implementations of multiple security levels of key agreement to implement
> different curve arithmetic for different security levels,

I really don't see any justification for this claim.

> (c) force
> implementations of protocols with both key agreement and digital signatures
> to implement different curve arithmetic for those two operations, even at
> the same security level,

This would be an option available to implementers, not a requirement.

> (d) force point conversions between curve forms to
> avoid efficiency loss in ECDHE, and

Now I'm completely lost.  I honestly have no idea what you mean by this.

> (e) to do (a)-(d) for no clear gain in
> performance. These points overwhelmingly contradict arguments in favor of
> forcing the use of the Montgomery form for key agreement, especially for
> only a single security level.
>

--Andy

---

From: Brian LaMacchia <[email-masked]>
Date: Tue, 2 Sep 2014 00:46:04 +0000

See responses inlined below

-----Original Message-----
From: Andy Lutomirski [mailto:[email-masked]] 
Sent: Monday, September 1, 2014 11:55 AM
To: Brian LaMacchia
Cc: [email-masked]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

>> particular security level means that implementations of protocols with 
>> both key agreement and digital signatures must implement both 
>> Montgomery curve arithmetic and additionally curve arithmetic for 
>> another curve form.  From an engineering perspective there is thus a 
>> clear drawback to requiring different curve forms for key agreement 
>> and digital signature at the same security level.

>You can do arithmetic on a curve points given in Montgomery form without a Montgomery ladder >implementation by converting to a different coordinate system.  I'm not sure why you'd want to in >anything other than the tiniest embedded implementation, but you could.

Yes, technically you could do that, but I haven’t seen anyone suggest that was in any way practical or interesting.  To be clear, the reason you would want to change to another form in ECDHE is for significant performance gains in the fixed-base key generation. 

>This isn't clearly a problem.  As has been noted as nauseum on this list, most of the work is in the field >arithmetic, and a Montgomery ladder and, say, Edwards EC arithmetic can share that.

I respectfully disagree; yes the field arithmetic is common, but the curve arithmetic is not and I really don’t think the complexity of the curve arithmetic can just be swept under the rug.  Writing and maintaining two sets of curve arithmetic – both of which need to be side-channel resistant – has cost, and why maintain two when only one is needed? 

>> level, choosing X25519 for ECDHE at the 128 bit security level will 
>> require implementations to use different curve arithmetic for the 128 
>> bit security level than other security levels.  Again from an 
>> engineering standpoint this is a negative.

>You're pre-supposing that other security levels wouldn't use Montgomery coordinates.

That’s correct, and I based that statement on what’s been submitted to CFRG and the conversation to date.  Do you disagree?  Except for X25519 no other curves mandating use of Montgomery form are currently on the table (e.g. Bernstein et al use the Edwards form over 2^414-17).  Yes, some Edwards curve implementations might choose to move back-and-forth between the two forms if they think that helps them, but (a) that should be an option left up to implementers if CFRG chooses an Edwards curve, not a requirement, and (b) as our recent research shows such manipulations are unlikely to be helpful anyway.

>> Those arguing for adoption of X25519 are requesting that CFRG (a) treat the

>This is the first time that I've seen this request on this list.

See previous reply.  No one is arguing for mandatory use of Montgomery form at any other security level.  

>> (b) force
>> implementations of multiple security levels of key agreement to 
>> implement different curve arithmetic for different security levels,

>I really don't see any justification for this claim.

See previous reply; there are no Montgomery form curves on the table for the 192- and 256-bit security levels.  

>> (c) force
>> implementations of protocols with both key agreement and digital 
>> signatures to implement different curve arithmetic for those two 
>> operations, even at the same security level,

>This would be an option available to implementers, not a requirement.

You’ve just made my point for me: if using the Montgomery form was just an option for implementers that they could consider using if they saw a benefit, that would be perfectly fine and well in line with the IETF tradition of standardizing protocols and letting implementations compete.  But that’s not the way X25519 is defined.  (OK, I guess one could do everything in Edwards and then at the very end convert to Montgomery coordinates in order to just send the X coordinate, but why do all that work and why do it only at that security level, for little to no performance gains?)

Alternatively and for the record, it seems to me that it would be perfectly reasonable for CFRG to decide to specify only Edwards curves (*not* twisted, just plain Edwards curves) as Mike Hamburg and others have suggested, and leave *all* of the optimizations as implementation choices.  So whether someone wants to use twisted Edwards curves, the Montgomery ladder, some other improvement, etc., would be completely up to them.  

>> (d) force point conversions between curve forms to avoid efficiency 
>> loss in ECDHE, and

>Now I'm completely lost.  I honestly have no idea what you mean by this.

OK, please go take a look at Section 6 of the NUMS paper (http://eprint.iacr.org/2014/130, starting on page 20), which describes the situation in detail.  Here’s the short version: for ECDHE you need one fixed-base and one variable-base computation, but you can’t take advantage of the Montgomery ladder for fixed-based computations so if you want an efficient implementation you do the fixed-base computation in (twisted) Edwards and the variable-base computation using the Montgomery ladder.  This is what’s called the “hybrid” solution in the paper.  Doing that, and the necessary coordinate conversion in between, turns out to be slightly slower than simply doing both computations in twisted Edwards in the first place.  

--bal

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 1 Sep 2014 18:06:14 -0700

On Mon, Sep 1, 2014 at 5:46 PM, Brian LaMacchia <[email-masked]> wrote:

> Yes, technically you could do that, but I haven’t seen anyone suggest that
> was in any way practical or interesting.

https://github.com/jedisct1/libsodium/issues/77

-- 
Tony Arcieri

---

From: Watson Ladd <[email-masked]>
Date: Mon, 1 Sep 2014 18:06:44 -0700

> I respectfully disagree; yes the field arithmetic is common, but the curve arithmetic is not and I really don’t think the complexity of the curve arithmetic can just be swept under the rug.  Writin…

Have you read DJB's email in which the entire code implementing the
montgomery ladder in tweetnacl is presented? Every argument that
Curve25519 is inferior has to deal with the applications that are
adopting it, today. And so far the Microsoft group has been unable to
deal with this.

> That’s correct, and I based that statement on what’s been submitted to CFRG and the conversation to date.  Do you disagree?  Except for X25519 no other curves mandating use of Montgomery form are c…

One could trivially send Curve241417 points in Montgomery form.
Furthermore the curve doesn't mandate a particular set of coordinates.
This has been stated several times on this list.

> See previous reply.  No one is arguing for mandatory use of Montgomery form at any other security level.

I don't see how this arguments work. Whatever advantages Montgomery
form has (independent of the adoption of Curve25519)  are independent
of security level. Now, if in 2006 Edwards form had been known,
Curve25519 would likely not have been presented in the way it was. The
fact that it is in Montgomery form is a historical accident.

But guess what: the rail gage in England is the size of two horses.
Refer is misspelled in HTTP. A 3/4 inch copper pipe doesn't have a
single dimension 3/4 of an inch big. Wet and dry cups are different (a
fact that made my mother incapable of following US baking recipes
without a scale). The question should be "is there any reason not to
adopt X25519 given the widespread adoption, lack of security
weaknesses, and strong desire for faster ECDH performance?".

> You’ve just made my point for me: if using the Montgomery form was just an option for implementers that they could consider using if they saw a benefit, that would be perfectly fine and well in lin…

Did you read the "Curve25519: New Speed Records" paper? The X25519
function is the x coordinate of a curve y^2=x^3+486662x^2+x over
E(F_p^2), with x restricted to lie in F_p.  How is this different from
the definition of P256 in terms of leaving things open to
implementors?

> Alternatively and for the record, it seems to me that it would be perfectly reasonable for CFRG to decide to specify only Edwards curves (*not* twisted, just plain Edwards curves) as Mike Hamburg a…

Which is the case anyway: your code could implement Weierstrass
coordinates and interop with X25519. But leaving the choice of
coordinates open isn't a possibility.

The question we need to answer is what goes on the wire? That needs to
have an answer. And how the computations take place is largely
irrelevant, although we do need to address security considerations,
some of which our choice of coordinates and curve influence. What's
the difference between specifying twisted Edwards and Edwards from
this perspective?

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

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

---

From: Benjamin Black <[email-masked]>
Date: Mon, 1 Sep 2014 18:50:47 -0700

On Mon, Sep 1, 2014 at 6:06 PM, Watson Ladd <[email-masked]> wrote:
>
>
> >
> > Alternatively and for the record, it seems to me that it would be
perfectly reasonable for CFRG to decide to specify only Edwards curves
(*not* twisted, just plain Edwards curves) as Mike Hamburg and others have
suggested, and leave *all* of the optimizations as implementation choices.
 So whether someone wants to use twisted Edwards curves, the Montgomery
ladder, some other improvement, etc., would be completely up to them.
> the difference between specifying twisted Edwards and Edwards from

The various working groups and standards bodies have already answered the
question of what goes on the wire. The TLS request was for new curves. As
we all seem to agree implementers are and should be free to use whatever
form they wish internally as long as the external representation is fixed,
there is general support for specifying curves in Edwards form, and
existing protocols all define X/Y coordinates on the wire, then I see an
opportunity for broad consensus here.

b

---

From: Watson Ladd <[email-masked]>
Date: Mon, 1 Sep 2014 19:05:43 -0700

On Mon, Sep 1, 2014 at 6:50 PM, Benjamin Black <[email-masked]> wrote:
> question of what goes on the wire. The TLS request was for new curves. As we
> all seem to agree implementers are and should be free to use whatever form
> they wish internally as long as the external representation is fixed, there
> is general support for specifying curves in Edwards form, and existing
> protocols all define X/Y coordinates on the wire, then I see an opportunity
> for broad consensus here.

The standards define short Weierstrass coordinates as what goes on the
wire, not arbitrary pairs X,Y. Furthermore, things like the
representability of the identity, small order points, etc. introduce
enough differences from existing practice that one has to check
carefully how well the specs deal with them.

Sincerely,
Watson Ladd

---

From: Benjamin Black <[email-masked]>
Date: Mon, 1 Sep 2014 20:14:48 -0700

> carefully how well the specs deal with them.
In neither RFC4492 nor X9.62-1998 do I see anything that constrains X,Y
coordinate formats to being short Weierstrass only. I am aware that strict
compliance with ECDSA requires short Weierstrass, but that, too, is an
implementation detail for those electing to use the new curves. If you have
a specific section of a standard in mind, please point me to it.

The rest of your message would be good guidance to provide back to TLS-WG
along with the curves so they can correctly and securely implement them.

b

---

From: Robert Ransom <[email-masked]>
Date: Tue, 2 Sep 2014 00:25:20 -0700

On 9/1/14, Brian LaMacchia <[email-masked]> wrote:
>>You can do arithmetic on a curve points given in Montgomery form without a
>> Montgomery ladder >implementation by converting to a different coordinate
>> system.  I'm not sure why you'd want to in >anything other than the
>> tiniest embedded implementation, but you could.
>

I've suggested that
(<http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html>).

To summarize:

* If the point format contains an Edwards-form y coordinate instead of
a Montgomery-form x coordinate, implementations which use the
Montgomery ladder, for whatever reason, must incur a significant extra
cost.  (The Montgomery ladder is far simpler than the algorithms you
recommend, and can be implemented with far less RAM than any tolerably
efficient scalar-multiplication routine based on Edwards form, so many
implementations will use the Montgomery ladder in practice, and some
implementations must use it.)

* If the point format consists of a Montgomery-form x coordinate
(possibly together with a sign bit for an Edwards-form x coordinate),
point decompression to projective Edwards (or twisted Edwards) form
costs only trivially more.  There is a small added cost over Dr.
Bernstein's ‘Curve41417’ ECDH implementation (but only because it is
sub-optimal), and essentially no added cost for your algorithms (which
must double their input before table construction).

(I do believe that using Edwards-form point formats in the Ed25519
signature system and the Curve41417 ECDH system was a bad decision --
in particular, if Ed25519 had used a Montgomery-form point format
instead, it would have been far more convenient for many applications
-- but I disagree strongly with your claim that using a different
point format for a signature system's nonces is inherently bad.  I'll
post more details about that at some point, hopefully soon.)

>  To be clear, the reason you would
> want to change to another form in ECDHE is for significant performance gains
> in the fixed-base key generation.

This is false, and you clearly know that: your own research group's
paper gives performance figures for a ‘hybrid’ ECDHE implementation
which uses Edwards form internally for key generation, and uses the
Montgomery ladder for the variable-base scalar multiplication.

(For everyone else, the added cost (during key generation) of encoding
a projective Edwards-form point to a Montgomery-form point format
rather than an Edwards-form point format is trivial: two additions.)

Robert Ransom

---

From: Brian LaMacchia <[email-masked]>
Date: Tue, 2 Sep 2014 07:58:21 +0000

-----Original Message-----
From: Robert Ransom [mailto:[email-masked]] 
Sent: Tuesday, September 2, 2014 12:25 AM
To: Brian LaMacchia
Cc: Andy Lutomirski; [email-masked]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

>> want to change to another form in ECDHE is for significant performance 
>> gains in the fixed-base key generation.

>This is false, and you clearly know that: your own research group's paper gives performance figures for >a ‘hybrid’ ECDHE implementation which uses Edwards form internally for key generation, and uses the >Montgomery ladder for the variable-base scalar multiplication.
>
>(For everyone else, the added cost (during key generation) of encoding a projective Edwards-form >point to a Montgomery-form point format rather than an Edwards-form point format is trivial: two >additions.)

Hi Robert,

I think you misread that portion of my email as being about the cost of conversion between coordinate formats, when I was in fact referring to the overall “hybrid” implementation.  If you go back and reread the entire message, you’ll see a more detailed comment on exactly this point at the bottom of my reply to Andy.  

--bal

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 02 Sep 2014 09:30:25 +0100

Just on this point...

On 02/09/14 02:50, Benjamin Black wrote:
> question of what goes on the wire.

That's not correct. When CFRG finish doing a great job here, then
the TLS WG will have to assign new codepoints for ciphersuites and
there is nothing stopping them defining new encodings at that point
if that's needed. That'd just not be a big deal. And the same is
true of other IETF activities. So what goes on the wire should be
a non-issue for this discussion really.

There is a connection with Russ' point about code re-use, but that's
much better considered in the way Russ framed it, as an implementation
issue and not as a protocol issue. Note that I'm not saying here that
I share Russ' concerns or conclusions, (not having implemented any
ECC myself) but I do think his question is the right one to ask.

S.

---

From: Robert Ransom <[email-masked]>
Date: Tue, 2 Sep 2014 01:50:12 -0700

On 9/2/14, Brian LaMacchia <[email-masked]> wrote:
>>This is false, and you clearly know that: your own research group's paper
>> gives performance figures for >a ‘hybrid’ ECDHE implementation which uses
>> Edwards form internally for key generation, and uses the >Montgomery
>> ladder for the variable-base scalar multiplication.
>>
>>(For everyone else, the added cost (during key generation) of encoding a
>> projective Edwards-form >point to a Montgomery-form point format rather
>> than an Edwards-form point format is trivial: two >additions.)
>
> Hi Robert,
>
> I think you misread that portion of my email as being about the cost of
> conversion between coordinate formats, when I was in fact referring to the
> overall “hybrid” implementation.

I'll quote that portion again, with all possible context:

> was in any way practical or interesting.  To be clear, the reason you would

I interpret “change to another form in ECDHE” to mean “change the
ECDHE protocol to use another form” (in context, a form other than
Montgomery form).  I still consider that to be the most reasonable
interpretation of that phrase, given the full context.

If you meant “convert a point used in ECDHE to another form” (other
than Montgomery form), then your statement is poorly worded and still
clearly false: the performance improvement that you are referring to
for fixed-base scalar multiplication relies on the base point being
provided in the form of a precomputed table.  The cost of converting a
base point into that ‘format’ is greater than the benefit can possibly
be for a single operation, so you cannot possibly be referring to the
table precomputation as ‘chang[ing] to another form *in ECDHE*’
(emphasis added).

>  If you go back and reread the entire
> message, you’ll see a more detailed comment on exactly this point at the
> bottom of my reply to Andy.

I did see that.  However:

* Your research group only considered one type of processor in its
benchmarks, and made all design decisions based on the performance of
its implementations on that processor.  The results do not show which
point format (or coordinate-field shape) will provide the best
performance in a small processor (or other device) with limited
memory, or in a processor with no (or small) cache RAM.  (I expect
that some implementations will be forced to use the Montgomery ladder
even for signature verification, due to extreme memory or cache
limitations.)

* Your research group didn't know that the Montgomery ladder can
tolerate leading zero bits, so they implemented the Montgomery ladder
with an unnecessarily long scalar.  As a consequence, I don't trust
your initial benchmarking results for the Montgomery ladder.  Have you
corrected that implementation issue and published new benchmark
results?

* Your research group's paper did not, as of the last time I read it,
explicitly state whether the twisted-Edwards-form benchmark results
used compressed or uncompressed points.  As Dr. Bernstein has pointed
out, specifying an uncompressed point format in a standard meant to
have multiple independent implementations introduces the risk that
someone will omit input validation, so I would oppose the use of an
uncompressed point format in any IETF protocol.  Do your benchmark
results for twisted-Edwards ECDHE include the cost of point
compression?

(Disclaimer: I've implemented software which uses uncompressed
Edwards-form points; I now believe that both “uncompressed” and
“Edwards-form” were bad design decisions.)

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Tue, 2 Sep 2014 08:19:50 -0700

> a non-issue for this discussion really.

Aren't we replacing SEC1? And doesn't SEC1 specify encodings, which
other WGs use?

If we end up saying "pairs of integers" then we get a mess, where
software implementing the curves has to implement a large number of
encodings. If we specify things as strings of bytes, that's easy to
deal with. I've heard some people say this was a mistake, but I am
unconvinced by those arguments.

Sincerely,
Watson Ladd

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 02 Sep 2014 16:33:23 +0100

> Aren't we replacing SEC1? And doesn't SEC1 specify encodings, which

CFRG is not replacing anything, but rather picking new additional
curves.

If those new curves turn out to be way more popular then maybe
over time they'll displace use of others, but only time will
tell that, not CFRG.

> unconvinced by those arguments. 

The point is that afaik none of those arguments help to pick
new curves. If CFRG want to suggest something for on-the-wire
formats after having picked some curves that's fine and it may
or may not be adopted by various IETF protocols, depending on
how well it fits their needs I guess.

Main point is: I don't believe wire-format issues make any
difference when picking new curves.

S.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 2 Sep 2014 08:37:08 -0700

> difference when picking new curves.

*None* of the arguments advanced so far help with picking new curves.
What possible difference is there between NUMS and the DJB/Tanja
curves? None, because you can always put one in the form of the other.
The only solution is a coinflip.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 02 Sep 2014 16:39:49 +0100

> The only solution is a coinflip.

Well, that's well beyond the scope of my teeny weeny comment:-)

S.

---

From: Nico Williams <[email-masked]>
Date: Tue, 2 Sep 2014 10:50:15 -0500

> difference when picking new curves.

+1.   We absolutely should not be constrained as to choice of curve by
wire format issues.

Indeed, something like the opposite should be true: we should add any
wire formats needed for those curves we want to use!

Nico
--

---

From: Tanja Lange <[email-masked]>
Date: Tue, 2 Sep 2014 18:29:59 +0200

Dear Brian,
 
Most of this is going in circles; the points you raise were discussed 
on the mailing list before and during the Toronto meeting. I would 
appreciate it if instead of starting a new round of this you could 
reply to some earlier emails.

>    both key agreement and digital signatures must implement both Montgomery
>    curve arithmetic and additionally curve arithmetic for another curve
>    form.  From an engineering perspective there is thus a clear drawback to
>    requiring different curve forms for key agreement and digital signature at
>    the same security level.
> 
As several people pointed out now and in previous discussions, this
is conflating wire format, implementation, and curve form.

For security and ease of correct implementation I prefer Montgomery-x
for the wire format for DH and a compressed (but uniquely decompressible)
wire format for signatures.

>    2.       Assuming that implementations will implement more than one
>    security level, choosing X25519 for ECDHE at the 128 bit security level
>    will require implementations to use different curve arithmetic for the 128
>    bit security level than other security levels.  Again from an engineering
>    standpoint this is a negative.
> 
This is arguing about one particular suggestion and, again, mixes
wire format, implementation, and curve form.

>    3.       Despite repeated claims to the contrary, there is little evidence
>    that there is a consistent and significant performance benefit to
>    X25519. Indeed, as both the performance numbers in
>    http://eprint.iacr.org/2014/130.pdf as well as the more recent performance
>    numbers posted by Andrey Jivsov demonstrate, the performance of X25519
>    does not significantly differ from that of (twisted) Edwards curves for
>    (non-ephemeral) ECDH at the same size.  For the case of ECDHE,
>    Dan Bernstein has argued for a definition of "ephemeral" that would allow
>    keys to be re-used for some amount of time allowing X25519 implementations
>    to amortize the cost of operations which are particularly expensive for
>    X25519 over multiple uses of the same key.* Such arguments are intended to
>    wrap requirements around specific curves, which is inappropriate for this
>    process. There has been no legitimate argument put forward for repeated
>    use of ephemeral keys in ECDHE.  As a consequence, the adoption of a
>    definition of "ephemeral" that does not allow key re-use (as previously
>    recommended) means that implementations of X25519 would require
>    conversions between curve forms to avoid a significant loss in
>    performance. These conversions are a negative from an engineering
>    perspective.
> 

This is mostly about curve choices, not requirements. As far as the 
requirement of 'ephemeral = once' is concerned we've been through 
this discussion. For a speed comparison one can choose to go for
"KG+DH" or for "KG+nDH" for some value of n or look at several data 
points. However, for the security of the implementation, the system
must not break if the DH key is reused. I already said that after my
talk in Toronto. 

To say it simpler:
Requirement: security MUST not decrease if DH keyis reused
Selection criterion: speed of KG+nDH (incl., maybe exclusively, n=1)

There has been enough ripping into items a0-e) already, 
so I skip that apart from pointing out that you're arguing 
against one particular curve and mixing that with the requirements.
How about my up and coming T255.5? (just kidding).

Regards
	Tanja

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Sep 2014 16:53:40 -0000

Brian LaMacchia writes:
> For the case of ECDHE, Dan Bernstein has argued for a definition of
> “ephemeral” that would allow keys to be re-used for some amount of
> time

Several reports have indicated that Microsoft's standard TLS library
(SChannel) reuses ephemeral DH keys (specifically TLS ECDHE keys) for
two hours. Are those reports not accurate?

Even if keygen were implemented as variable-base scalarmult without the
complication of a separate fixed-base scalarmult function, wouldn't you
agree that this key reuse makes the cost of key generation irrelevant?
Wouldn't you expect other implementors to reuse keys for this reason?

Obviously two hours is not the right choice: repressive police states
can certainly seize equipment within that time interval. In my message
dated 1 Aug 2014 01:36:59 -0000, I suggested 10 seconds as an upper
limit. However, this doesn't change the DH performance picture!
Variable-base scalarmult is dominant for DH, including ephemeral DH.

I concluded that CFRG should consider the performance of variable-base
scalarmult (for DH), fixed-base scalarmult (for signing), and
double-base scalarmult (for signature verification). But I don't expect
this to produce different curve choices from considering solely
variable-base scalarmult---which is also the most fundamental operation
and the usual focus of DH performance analyses in the literature.

> allowing X25519 implementations to amortize
> the cost of operations which are particularly expensive for X25519
> over multiple uses of the same key. 

The "expensive for X25519" claim here is completely wrong. X25519 allows
all the usual speed benefits from all the usual fixed-base speedups. As
Mike Hamburg put it in his mail message dated 7 Aug 2014 11:57:45 -0700,
optimized fixed-base scalarmult "will pretty much always cost about a
third of what the variable-base scalar multiply costs."

Concretely,

   https://github.com/floodyberry/ed25519-donna
   https://github.com/agl/curve25519-donna
   
support all Curve25519/X25519/Ed25519 operations under discussion: DH
keygen (curved25519_scalarmult_basepoint is the fast version), DH
shared-secret computation, signature keygen, signing, and verification.
These are faster than the speeds announced by Microsoft for each of
these operations (and of course also for combinations of operations in
ECDHE etc.) on the CPU that Microsoft has selected for benchmarks. Also,
unlike Microsoft's library, these actually do the work of signing etc.

There are many X25519 implementations, reflecting the wide use of X25519
in many real-world protocols. It's of course true that reusing DH keys
practically eliminates keygen cost, which is exactly why typical users
don't care about DH keygen time, which is exactly why typical DH
implementations prioritize simplicity over DH keygen optimizations. This
has given you the flexibility to cherry-pick X25519 implementations that
don't bother speeding up keygen, and to misrepresent the performance of
those implementations as the keygen performance of X25519, even though
faster X25519 keygen code has been available for longer than Microsoft's
library has. Your position is not defensible.

> There has been no legitimate argument put forward for
> repeated use of ephemeral keys in ECDHE.

If a server notices keygen time, it can gain far more performance by
reusing a key 100 times than by switching to fixed-base scalarmult.
Reusing keys also costs less code in many settings than implementing
fixed-base scalarmult, but even without this simplicity argument you
have to admit that there's a legitimate performance argument.

Out of curiosity: If it wasn't for performance, why did Microsoft's TLS
library ever reuse ephemeral DH keys in the first place? Would you say
that the Microsoft reason was illegitimate? Even if you're sure that it
was illegitimate, wouldn't you agree that taking this reuse off of the
CFRG radar screen would require a blanket prohibition on this reuse in
all IETF protocols, and that no such prohibition exists?

> Assuming that implementations will implement more than one security 
> level than other security levels.  

No. All Edwards (and twisted Edwards) curves, at all security levels,
are compatible with choosing Montgomery coordinates for ECDHE. See my
message dated 25 Aug 2014 23:43:05 -0000 for the relevant formulas.

When Tanja Lange and I introduced Edwards-curve cryptography, we
correctly and publicly predicted that Edwards coordinates would be close
in performance to Montgomery coordinates. However, nothing has ever
matched the amazing _simplicity_ of the Montgomery X-coordinate for DH.
This simplicity is more than just a time-saver; it also removes many
opportunities for DH implementors to screw up security.

> and digital signature at the same security level.

The Montgomery approach to DH is exceptionally simple---costing very few
lines of code for a unified DH+signatures implementation (as TweetNaCl
demonstrates), and at the same time saving many more lines of code for a
pure DH implementation. If the picture looks like

   * complexity 300: DH using Montgomery
   * complexity 500: DH using Edwards
   * complexity 600: DH using Edwards + signatures using Edwards
   * complexity 610: DH using Montgomery + signatures using Edwards

you can't claim that there is a "clear drawback" to DH using Montgomery.

---Dan

---

From: Benjamin Black <[email-masked]>
Date: Tue, 2 Sep 2014 14:33:34 -0700

Why would new cipher suites be required to use new curves? Do you mean new
named curve code points rather than cipher suites?

Though our reasons are different, it sounds like we agree on leaving wire
formats to the WGs.

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 02 Sep 2014 14:37:02 -0700

> difference when picking new curves.

If this refers to which tag to use (i.e. 02, 03, 04 in SEC1), no tag at 
all, endianess, or even point compression, then I can see this.

However, the actual bytes representing a point imply a 10% penalty in 
dual-key uses for "another use" due to the inversion in F(p) (and 
possibly double inversion).

If the format is selected to favour variable base ECDH (Montgomery X), 
there is a 10% penalty to perform digital signature with this key or 
some server-side optimization that depend on the ability to add two points.

The reverse of this is true if the coordinates are on the Edwards curves.

At least this is what follows from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html, 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05035.html, if the 
types of the curves under consideration are Montgomery and -1 twisted 
Edwards.

If it's possible to reduce this penalty for some curves and encodings, 
performance and security being equal, this is a plus for these curves 
(even though the encoding issue will formally be decided later).

---

From: Benjamin Black <[email-masked]>
Date: Tue, 2 Sep 2014 14:43:17 -0700

On Tue, Sep 2, 2014 at 8:19 AM, Watson Ladd <[email-masked]> wrote:

> Aren't we replacing SEC1?
>
>
As others have said, no, that is not what I understand to be the goal here.

b

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 02 Sep 2014 22:47:22 +0100

Hiya,

On 02/09/14 22:37, Andrey Jivsov wrote:
> 10% penalty in dual-key uses

I'm not clear what you mean by this, in terms of what protocol
it would affect.

Can you give me an example of such an IETF protocol? Without
having thought much about it, I think there are always different
codepoints allocated for DH and signatures, and I doubt we'd
want the same private values shared anyway, so I'm not sure
if that's a real or a theoretical issue.

Thanks,
S.

---

From: Benjamin Black <[email-masked]>
Date: Tue, 2 Sep 2014 14:47:11 -0700

On Tue, Sep 2, 2014 at 8:37 AM, Watson Ladd <[email-masked]> wrote:

> curves?

One notable difference is between the generation algorithms. While the
distinction might not be relevant to you, it is relevant to many others.

b

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 02 Sep 2014 22:54:14 +0100

> named curve code points rather than cipher suites?

Sorry, yes, could be one or the other. Either way, the blob could
be interpreted differently for new curves vs. NIST curves if that
made sense and it'd be no big deal. Worst case, you'd need to
update some RFC with text describing encoding of NIST curve blobby
stuff;-)

Just in case: I'm not saying that any particular approach here is
better or not, I'm only saying there's nothing to help pick a new
curve.

> Though our reasons are different, it sounds like we agree on leaving wire

Yep.

S

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 02 Sep 2014 14:58:35 -0700

> if that's a real or a theoretical issue.
A few examples of dual-key use and a bit braader question of whether 
would want to add points as oppose to only do scalar multiplication.

Some TLS server side fixed-base optimization will benefit from point 
addition.

While OpenPGP RFC 4880 has a concept of a "bundle of keys" things are 
easier when the top key can have both encryption and signing capability. 
There are products that add X.509 certs to PGP keys.

Signing a certificate request for a DH key to prove key possession.

Protocols for applications with space-saving requirements : keys on URLs 
or e-mail aliases, pre-generate keys "for everybody" to represent 
identities. Keys that are handled by humans (e.g. typed in base32 
encoding), etc

---

From: Nico Williams <[email-masked]>
Date: Tue, 2 Sep 2014 17:59:57 -0500

>> if that's a real or a theoretical issue.

+1.  We generally strive for key hygiene.  We'd not use a key for
different purposes.

What is the use of using the same key for DH and signatures in the
same protocol?  I can only think of a round-trip optimization, but
what I have in mind is very handwavy and not likely to be a win
(partly because it means losing PFS).

> A few examples of dual-key use and a bit braader question of whether would
> want to add points as oppose to only do scalar multiplication.
>

Can you give some more details of what this would mean protocol-wise?

> While OpenPGP RFC 4880 has a concept of a "bundle of keys" things are easier
> when the top key can have both encryption and signing capability. There are
> products that add X.509 certs to PGP keys.

Yes, I could see this.  Though key bundles have been around for long
enough (and in widespread enough use) that it doesn't seem likely to
matter much.

> Signing a certificate request for a DH key to prove key possession.

A self-signed DH cert.  OK, this one makes some sense, but if the
price is losing PFS or paying extra CPU cycles if you want PFS, then
it seems not worthwhile.

On the other hand, if using the same key for DH and signatures is
worthwhile, then it seems likely that point form conversion won't be a
big deal.  No?

> Protocols for applications with space-saving requirements : keys on URLs or
> e-mail aliases, pre-generate keys "for everybody" to represent identities.
> Keys that are handled by humans (e.g. typed in base32 encoding), etc

Yes, this is a clear win.  But again, any point conversion penalty
seems minor for such a protocol.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 02 Sep 2014 16:52:46 -0700

> Can you give some more details of what this would mean protocol-wise?
The format on the wire is not affected, but if there is a penalty for 
point addition, this is a property that didn't exist for, say P-256.

Consider the following example of an optimization a server might have to 
produce a fresh ephemeral key (proof omitted but I think is possible):

Generate n keypairs {ki, kiG}. There are about n^2/2 of the unique 
pairs. The ephemeral key is {ki+kj}G, which is done with a single point 
addition. Thus, sqrt(n) keygens provide n ephemeral keys.

This can be viewed as a special case of fixed-point optimization.

> enough (and in widespread enough use) that it doesn't seem likely to

Signatures in OpenPGP "live" on the top key. It's more challenging to 
add X.509 certs to subkeys. X.509 certs on subkeys might go into 
notation packets, but notations are a part of self-signatures are 
therefore signed by the top key, which poses challenges if one wants to 
do management like removal of certificates (by untrusted entity like a 
key server)

> worthwhile, then it seems likely that point form conversion won't be a

Also CSRs for DH keys, if you want to do ECDSA-like signature with a DH key.

Keys with 10% penalty should be viewed as "optimized" for particular use 
based on the choice of coordinate system.

Compare this with conversion between Montgomery coordinates and Short 
Weierstrass coordinates 
(http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html): there 
is no such penalty for such a pair.

> seems minor for such a protocol.

Depends on the case. If you think something like SMIME/CMS on outgoing 
e-mails, they will likely get signed+encrypted (to self, when placed 
into the Sent folder) . Not an issue for TLS clients, though.
...

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 2 Sep 2014 17:20:21 -0700

There isn’t actually a 10% penalty for switching forms unless you are translating between two different wire formats.  If one side or the other is internal to the application, it will be projective, which makes translation free unless the format is compressed.

There’s a 10% penalty for decompressing points, if they’re compressed going down the wire.  This is true almost no matter how you compress them, except that you can do the Montgomery ladder without decompressing if you have a suitable coordinate.  So for example:

Montgomery x only: Can’t add points at all.  Technically can check signatures, but don’t do it this way.  Ladderable.

Montgomery (x,y): No 10% penalty for decompression.  Ladderable (you can recover y at the end for cheap).

Montgomery (x,bit): Needs decompression before you can add, costing 10%.  Ladderable, but the recovery may be complicated depending on how the bit is computed.

Montgomery 1/sqrt(x): Needs decompression before you can add, costing 10%.  Ladderable.  Uses p==3 mod 4.

Edwards (x,y): No 10% penalty for decompression.  Not ladderable (there’s an Edwards ladder but it isn’t as efficient).

Edwards (bit,y): Needs decompression before you can add, costing 10%.  Not ladderable.

Edwards x/y: Needs decompression before you can add, costing 20% (unless someone can improve?).  Ladderable.

By “ladderable”, I mean that you can do a nearly-unmodified 5M+4S Montgomery ladder without decompression, then recompress at the cost of about one exponentiation in the base field.

Because I believe point compression to be commonly desirable, and ladderability to be “nice to have”, I’m currently using 1/sqrt(x) as a wire format for all points in my software.

Also, before someone says the Montgomery ladder isn’t actually faster: in my experience it is faster even at 512 bits if it lets you skip decompression, but at that size it only beats Edwards by 5-10%, so not a big deal.

Cheers,
— Mike

> On Sep 2, 2014, at 4:52 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> The format on the wire is not affected, but if there is a penalty for point addition, this is a property that didn't exist for, say P-256.
> 
> Consider the following example of an optimization a server might have to produce a fresh ephemeral key (proof omitted but I think is possible):
> 
> Generate n keypairs {ki, kiG}. There are about n^2/2 of the unique pairs. The ephemeral key is {ki+kj}G, which is done with a single point addition. Thus, sqrt(n) keygens provide n ephemeral keys.
> 
> Signatures in OpenPGP "live" on the top key. It's more challenging to add X.509 certs to subkeys. X.509 certs on subkeys might go into notation packets, but notations are a part of self-signatures are therefore signed by the top key, which poses challenges if one wants to do management like removal of certificates (by untrusted entity like a key server)
> 
>> 
> Keys with 10% penalty should be viewed as "optimized" for particular use based on the choice of coordinate system.
> 
> Compare this with conversion between Montgomery coordinates and Short Weierstrass coordinates (http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html <http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html>): there is no such penalty for such a pair.
> 
> Depends on the case. If you think something like SMIME/CMS on outgoing e-mails, they will likely get signed+encrypted (to self, when placed into the Sent folder) . Not an issue for TLS clients, though.
> ...
> 
> [email-masked] <mailto:[email-masked]>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>

---

From: Brian LaMacchia <[email-masked]>
Date: Wed, 3 Sep 2014 05:09:41 +0000

Hi Dan,

Regarding the specific issue you raised concerning Microsoft’s TLS implementation, as you will recall Tanja first mentioned this issue to me during dinner in Toronto.  She said she found it as part of testing Internet Information Server for your Dual_EC_DRBG research which appeared at USENIX Security two weeks ago.  Her comment, and your subsequent mentions on this mailing list are the only reports of the issue of which I am personally aware.  In any event, I did look into this for you and can now confirm that there is indeed an issue and that it is in the SChannel platform implementation of TLS itself (not IIS).  

The folks in Windows who own SChannel have asked me to ask you to please open a case with the Microsoft Security Response Center on this issue.  You can do that by sending an e-mail message to the address [email-masked] describing the issue you and Tanja found.  If you CC me on the e-mail I can give some additional internal information to the MSRC case officer to whom it is assigned.  As I am in Microsoft Research and not the Operating System Group (where Windows is), MSRC will be your best contact for updating you on the progress of your case.

Thanks again for reporting this.

As for your suggestion regarding a blanket prohibition on reuse of any ephemeral cryptographic keys across all IETF protocols, given the current environment that does indeed seem like a good idea to me.  I guess what we’d really want to do is have CFRG issue a BCP on this point, if that’s something the IRTF is allowed to do (I don’t know the answer to that process question).  Perhaps CFRG can take that issue up once the curve selection process has concluded.

--bal

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of D. J. Bernstein
Sent: Tuesday, September 2, 2014 9:54 AM
To: [email-masked]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

Several reports have indicated that Microsoft's standard TLS library
(SChannel) reuses ephemeral DH keys (specifically TLS ECDHE keys) for two hours. Are those reports not accurate?

Even if keygen were implemented as variable-base scalarmult without the complication of a separate fixed-base scalarmult function, wouldn't you agree that this key reuse makes the cost of key generation irrelevant?
Wouldn't you expect other implementors to reuse keys for this reason?

Obviously two hours is not the right choice: repressive police states can certainly seize equipment within that time interval. In my message dated 1 Aug 2014 01:36:59 -0000, I suggested 10 seconds as an upper limit. However, this doesn't change the DH performance picture!
Variable-base scalarmult is dominant for DH, including ephemeral DH.

I concluded that CFRG should consider the performance of variable-base scalarmult (for DH), fixed-base scalarmult (for signing), and double-base scalarmult (for signature verification). But I don't expect this to produce different curve choices from considering solely variable-base scalarmult---which is also the most fundamental operation and the usual focus of DH performance analyses in the literature.

> allowing X25519 implementations to amortize the cost of operations 
> which are particularly expensive for X25519 over multiple uses of the 
> same key.

The "expensive for X25519" claim here is completely wrong. X25519 allows all the usual speed benefits from all the usual fixed-base speedups. As Mike Hamburg put it in his mail message dated 7 Aug 2014 11:57:45 -0700, optimized fixed-base scalarmult "will pretty much always cost about a third of what the variable-base scalar multiply costs."

Concretely,

support all Curve25519/X25519/Ed25519 operations under discussion: DH keygen (curved25519_scalarmult_basepoint is the fast version), DH shared-secret computation, signature keygen, signing, and verification.
These are faster than the speeds announced by Microsoft for each of these operations (and of course also for combinations of operations in ECDHE etc.) on the CPU that Microsoft has selected for benchmarks. Also, unlike Microsoft's library, these actually do the work of signing etc.

There are many X25519 implementations, reflecting the wide use of X25519 in many real-world protocols. It's of course true that reusing DH keys practically eliminates keygen cost, which is exactly why typical users don't care about DH keygen time, which is exactly why typical DH implementations prioritize simplicity over DH keygen optimizations. This has given you the flexibility to cherry-pick X25519 implementations that don't bother speeding up keygen, and to misrepresent the performance of those implementations as the keygen performance of X25519, even though faster X25519 keygen code has been available for longer than Microsoft's library has. Your position is not defensible.

> There has been no legitimate argument put forward for repeated use of 
> ephemeral keys in ECDHE.

If a server notices keygen time, it can gain far more performance by reusing a key 100 times than by switching to fixed-base scalarmult.
Reusing keys also costs less code in many settings than implementing fixed-base scalarmult, but even without this simplicity argument you have to admit that there's a legitimate performance argument.

Out of curiosity: If it wasn't for performance, why did Microsoft's TLS library ever reuse ephemeral DH keys in the first place? Would you say that the Microsoft reason was illegitimate? Even if you're sure that it was illegitimate, wouldn't you agree that taking this reuse off of the CFRG radar screen would require a blanket prohibition on this reuse in all IETF protocols, and that no such prohibition exists?

> bit security level than other security levels.

No. All Edwards (and twisted Edwards) curves, at all security levels, are compatible with choosing Montgomery coordinates for ECDHE. See my message dated 25 Aug 2014 23:43:05 -0000 for the relevant formulas.

When Tanja Lange and I introduced Edwards-curve cryptography, we correctly and publicly predicted that Edwards coordinates would be close in performance to Montgomery coordinates. However, nothing has ever matched the amazing _simplicity_ of the Montgomery X-coordinate for DH.
This simplicity is more than just a time-saver; it also removes many opportunities for DH implementors to screw up security.

> and digital signature at the same security level.

The Montgomery approach to DH is exceptionally simple---costing very few lines of code for a unified DH+signatures implementation (as TweetNaCl demonstrates), and at the same time saving many more lines of code for a pure DH implementation. If the picture looks like

---Dan

---

From: Tanja Lange <[email-masked]>
Date: Wed, 3 Sep 2014 07:27:04 +0200

Dear Brian,
> Regarding the specific issue you raised concerning Microsoft’s TLS implementation, as you will recall Tanja first mentioned this issue to me during dinner i
>
I actually made this statement in public in the Q&A after my talk
when David McGrew asked about the ephemeral key case.

> As for your suggestion regarding a blanket prohibition on reuse of any ephemeral cryptographic keys across all IETF protocols, given the current environment that does indeed seem like a good idea t…
What exactly do you think the security implications of key reuse are?
 
Defining ephemeral in a time-based manner ist quite normal; the important
thing to guarantee PFS is to delete the key afterwards, not whether it is
used for 1 connection or 10 seconds (with potentially 0 connections).

All the best
	Tanja

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 3 Sep 2014 19:13:17 +0000

Hi,

On 03/09/2014 06:27, "Tanja Lange" <[email-masked]> wrote:

>Dear Brian,
>> Regarding the specific issue you raised concerning Microsoft¹s TLS
>>implementation, as you will recall Tanja first mentioned this issue to
>>me during dinner i
>>

This is indeed true as the minutes should show. But it was a topic of some
passionate discussion at the dinner later, IIRC.

>> As for your suggestion regarding a blanket prohibition on reuse of any
>>ephemeral cryptographic keys across all IETF protocols, given the
>>current environment that does indeed seem like a good idea to me.  I
>>guess what we¹d really want to do is have CFRG issue a BCP on this
>>point, if that¹s something the IRTF is allowed to do (I don¹t know the
>>answer to that process question).  Perhaps CFRG can take that issue up
>>once the curve selection process has concluded.
>>

For what it's worth, ephemeral reuse invalidates all the formal security
analyses (in the provable security tradition) for key exchange protocols
that I know of. It certainly invalidates those proofs that I understand
for the TLS Handshake. Would be interesting if the miTLS guys could say
what it means for their TLS proofs from Crypto'14.

My feeling is that this can be got around in the random oracle model for
protocols that hash the DH shared value and various other components by
using a suitable gap assumption or strong DH assumption. However, some
care would be needed in the analysis. Coming up with a standard model
proof for some specific protocol seems much harder because of the obvious
"correlation" between shared DH values that different parties would end up
with. Hashing with a random oracle of course destroys such relations.

There's probably a nice research paper in this for someone - if it's not
already been done (indeed writing such a paper has been on my to do list
for some time - since long before this thread got started).

Cheers

Kenny

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 3 Sep 2014 16:20:33 -0700

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Paterson, Kenny
Sent: Wednesday, September 03, 2014 12:13 PM
To: Tanja Lange; Brian LaMacchia
Cc: [email-masked]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

Hi,

On 03/09/2014 06:27, "Tanja Lange" <[email-masked]> wrote:

>I actually made this statement in public in the Q&A after my talk when 
>David McGrew asked about the ephemeral key case.

>> As for your suggestion regarding a blanket prohibition on reuse of 
>>any ephemeral cryptographic keys across all IETF protocols, given the 
>Defining ephemeral in a time-based manner ist quite normal; the 
>important thing to guarantee PFS is to delete the key afterwards, not 
>whether it is used for 1 connection or 10 seconds (with potentially 0
connections).

For what it's worth, ephemeral reuse invalidates all the formal security
analyses (in the provable security tradition) for key exchange protocols
that I know of. It certainly invalidates those proofs that I understand for
the TLS Handshake. Would be interesting if the miTLS guys could say what it
means for their TLS proofs from Crypto'14.

[JLS] I would hope that it does not invalidate all of the proofs or the
static-ephemeral and static-static key exchange protocols that are used by
S/MIME and other off-line protocols have a real problem.

Jim

My feeling is that this can be got around in the random oracle model for
protocols that hash the DH shared value and various other components by
using a suitable gap assumption or strong DH assumption. However, some care
would be needed in the analysis. Coming up with a standard model proof for
some specific protocol seems much harder because of the obvious
"correlation" between shared DH values that different parties would end up
with. Hashing with a random oracle of course destroys such relations.

There's probably a nice research paper in this for someone - if it's not
already been done (indeed writing such a paper has been on my to do list for
some time - since long before this thread got started).

Cheers

Kenny

---

From: Markulf Kohlweiss <[email-masked]>
Date: Thu, 4 Sep 2014 07:22:33 +0000

Hi all,

Mostly in reply to Kenny's comments on provable security and miTLS. We discussed this internally and have very partial results that should be extended. 

The miTLS master-secret KEM does not distinguish between one-time use of the KEM public key, and reuse. So the main proof (of a theorem that does not model PFS) also holds for TLS-DHE in settings where server public keys are reused. On the other hand the KEM abstraction does not allow for client-side reuse of ephemeral values. In KEM terminology: Enc always uses fresh randomness.

What are you most concerned about client or server side reuse of ephemeral secrets?

How one would model PFS in such a time-based manner is fascinating. The current, again rudimentary modelling of PFS in miTLS (you have to dig in the appendix) only models signing key compromise, but not temporal ephemeral secret compromise. 

Best,
Markulf

PS. I added Cedric in CC to fact check what I am saying. In these subtle issues the verification of the implementation may be more detailed than the paper crypto proof. 

-----Original Message-----
From: Paterson, Kenny [mailto:[email-masked]] 
Sent: 03 September 2014 20:13
To: Tanja Lange; Brian LaMacchia
Cc: [email-masked]
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement

Hi,

>David McGrew asked about the ephemeral key case.

This is indeed true as the minutes should show. But it was a topic of some passionate discussion at the dinner later, IIRC.

>whether it is used for 1 connection or 10 seconds (with potentially 0 connections).

For what it's worth, ephemeral reuse invalidates all the formal security analyses (in the provable security tradition) for key exchange protocols that I know of. It certainly invalidates those proofs that I understand for the TLS Handshake. Would be interesting if the miTLS guys could say what it means for their TLS proofs from Crypto'14.

My feeling is that this can be got around in the random oracle model for protocols that hash the DH shared value and various other components by using a suitable gap assumption or strong DH assumption. However, some care would be needed in the analysis. Coming up with a standard model proof for some specific protocol seems much harder because of the obvious "correlation" between shared DH values that different parties would end up with. Hashing with a random oracle of course destroys such relations.

There's probably a nice research paper in this for someone - if it's not already been done (indeed writing such a paper has been on my to do list for some time - since long before this thread got started).

Cheers

Kenny

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 5 Sep 2014 09:46:25 +0000

Markulf,

Thanks for the reply. It's server-side reuse that is of concern here
(that's where the heavy lifting is done).

I now recall that our Crypto'13 paper [1] also uses a KEM abstraction and
in Section 7 treats the case where the server has a static DH key; this is
not exactly the same as ephemeral reuse, but I think it's close enough
that the analysis should go through under the same assumption (PRF-ODH).

The result would be that ephemeral reuse is OK in TLS, so long as the
reused ephemeral value does not leak. Clearly, if a reused ephemeral value
leaks, then all the related sessions are insecure; but it should be the
case that all the other, unrelated sessions (using different ephemeral
values) are still secure. However, I do not immediately see how a proof of
this follows from any of our results in [1] (since we do not consider
ephemeral compromise, and allow only non-adaptive corruption).

There's still the question of what kind of forward security one can hope
for in case of ephemeral reuse. This was not treated in our paper, but I
think it should be achievable. It might be worth looking into the paper by
Jager et al from Crypto'12 [2] to see how their analysis holds up under
ephemeral reuse. I'm cc-ing Tibor Jager to see if he can shed any light on
this.

And of course, the analyses in [1] and [2] are only in the single
ciphersuite setting, so the analysis is not complete (I thought I should
say that before you pointed it out ;-) ).

Cheers

Kenny

[1] http://eprint.iacr.org/2013/339.pdf

[2] http://eprint.iacr.org/2011/219

On 04/09/2014 08:22, "Markulf Kohlweiss" <[email-masked]> wrote:

>Hi all,
>
>Mostly in reply to Kenny's comments on provable security and miTLS. We
>discussed this internally and have very partial results that should be
>extended. 
>
>The miTLS master-secret KEM does not distinguish between one-time use of
>the KEM public key, and reuse. So the main proof (of a theorem that does
>not model PFS) also holds for TLS-DHE in settings where server public
>keys are reused. On the other hand the KEM abstraction does not allow for
>client-side reuse of ephemeral values. In KEM terminology: Enc always
>uses fresh randomness.
>
>How one would model PFS in such a time-based manner is fascinating. The
>current, again rudimentary modelling of PFS in miTLS (you have to dig in
>the appendix) only models signing key compromise, but not temporal
>ephemeral secret compromise.
>
>Best,
>Markulf
>
>PS. I added Cedric in CC to fact check what I am saying. In these subtle
>issues the verification of the implementation may be more detailed than
>the paper crypto proof.
>
>This is indeed true as the minutes should show. But it was a topic of
>some passionate discussion at the dinner later, IIRC.
>
>"correlation" between shared DH values that different parties would end
>up with. Hashing with a random oracle of course destroys such relations.
>

---

From: Nico Williams <[email-masked]>
Date: Mon, 8 Sep 2014 13:51:34 -0500

> used for 1 connection or 10 seconds (with potentially 0 connections).

+1.

What matters is that the private key be destroyed some time after it's
been used.  That amount of time cannot be zero (it could, with the
right hardware, but that's another story).  It has to be some small
amount of time.  .01 seconds or 10 seconds doesn't make much
difference -- it doesn't make _any_ substantial difference.

As for key reuse (as opposed to how long after use the key is
destroyed), obviously it cannot be bad, otherwise we'd only have
ephemeral-ephemeral DH.  But we've been using DH with static keys
since DH was invented.

No plausible case has yet been made against ephemeral DH key reuse.  I
can't think of a plausible case against it.  I'm inclined to believe
there is no plausible case to be made against it within the current
published literature.

PFS depends on timely destruction of private keys, not non-reuse.

Nico
--

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 8 Sep 2014 12:34:03 -0700

> there is no plausible case to be made against it within the current

OK, I'll bite.

If the various standards are to be interpreted as permitting parties
to reuse their ephemeral DH keys for a short time, *which party* is
allowed to do so?  I bet that, if both parties in a DH exchange reuse
their ephemeral keys in multiple DH exchanges with each other, the
security properties of various protocols degrade in varying amounts
from "anything resembling a security proof is invalidated" to
"completely insecure".

Certainly the any exchange of the form K = H(g^(a+b)) followed by use
of most AEADs (e.g. GCM, most things using Poly1305, etc) starting
with IV 0 and key K (or a hash of K) will fail catastrophically.

In summary, I think that a protocol intended to allow ephemeral key
reuse needs to specify that reuse is allowed (so the proofs can be
designed correctly) and to specify *how* the keys may be reused (to
avoid catastrophic failure).

> PFS depends on timely destruction of private keys, not non-reuse.

And integrity, and possibly even confidentiality, depends on non-reuse
of derived keys... :)

I hope that OpenSSL doesn't already reuse ECDH keys on the client.
The code is entirely incomprehensible, so my five minutes of trying to
understand it went nowhere at all.

--Andy

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Mon, 08 Sep 2014 22:00:55 +0200

>> ephemeral-ephemeral DH.  But we've been using DH with static keys
Key reuse is bad if the implementation has side channels. Well, arguably that
should never be the case, but anyway.

> with IV 0 and key K (or a hash of K) will fail catastrophically.
This can certainly be a catastrophic failure in some protocol, but in TLS at
least I think the random values from the hello messages prevent this particular
mode of failure.

> avoid catastrophic failure).
However, I agree with this point.

> understand it went nowhere at all.
I would assume they don't: on server you must select one curve, while on the
client curve selection is dynamic. I take this as an indication that they reuse
keys on the server but not on the client. But do not trust me on this!

Manuel.

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 8 Sep 2014 13:04:02 -0700

> keys on the server but not on the client. But do not trust me on this!

Except that even this isn't true in OpenSSL 1.1 (I think).  Servers
can finally specify a preference list for curves.  I think it's still
safe, though.

--Andy

---

From: Nico Williams <[email-masked]>
Date: Mon, 8 Sep 2014 16:26:54 -0500

> with IV 0 and key K (or a hash of K) will fail catastrophically.

This is true, but we have nonces for this.  Alternatively, if we want
no nonces (to avoid them being used to leak key material) then one
party at least must never reuse keys.  The party where reuse gets the
most wins is the server-side.

> And integrity, and possibly even confidentiality, depends on non-reuse

Yes, of course.  Again, nonces.

Nico
--

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 12 Sep 2014 01:06:35 -0700

On 09/02/2014 05:20 PM, Michael Hamburg wrote:
> There isn’t actually a 10% penalty for switching forms unless you are
> translating between two different wire formats.  If one side or the
> other is internal to the application, it will be projective, which makes
> translation free unless the format is compressed.

[ http://www.ietf.org/mail-archive/web/cfrg/current/msg05045.html ]

I followed up on the idea that one can convert between Montgomery 
canonical compressed representation to Edwards projective coordinates 
without extra one or two inverses. Here are my notes, confirming the above.

To convert from Montgomery M(x,y): y^2 = x^3 + A*x^2 + x to -1 twisted 
Edwards coordinate (x_e,y_e) on the curve E(x,y): -x^2+y^2 = 1 + 
d*x^2*y^2 the following formula is used:

x_e = sqrt( -(A+2) ) * x / y
y_e = (x-1)/(x+1)

O = (0,0) for M
O = (0,1) for E, (0,-1) is exceptional

d = -(A-2)/(A+2)

y is not sent and we calculate it based on y_e and E(x,y) equation as 
follows:

x_e = sqrt( (y_e^2-1) / (d*y_e^2+1) )

The numerator and denominator in the above formula are:

y_e^2-1 = -4x = Y^2 - T^2
d*y_e^2+1 = d*Y^2+T^2

Y = x - 1
T = x + 1

This is x_e = sqrt( (T^2-Y^2)/(-dY^2-T^2) ) and this can be calculated 
in terms of Montgomery x at no additional cost, but this is not enough 
because y_e = Y/T would require an additional inverse. In addition, 
there may be a second extra inverse corresponding to the conversion back 
to the canonical representation.  These two inverses would have added 
20% performance penalty, a significant hit in some instances. For 
example, Curve25519 is 50% faster than NIST P-256 between openssl 
optimized for AVX2 v.s. curve25519-donna on the same modern x86_64 CPUs.

Fortunately, it is possible to avoid the overhead of conversion both ways:
* from affine Montgomery compressed coordinates (x only) to affine -1 
twisted Edwards  coordinates (from which one can use projective coordinates)
* from projective -1 twisted Endwards coordinates to Montgomery

First, let's look at conversion to Edwards affine coordinates. This 
conversion has a nice property that it's affine-to-affine.

The following 3 "tricks" will be used to accomplish this.

The simultaneous square root and inversion are explained in section 5 of 
http://ed25519.cr.yp.to/ed25519-20110705.pdf )

The "Montgomery trick" is easily generalized to any number of inverses 
as follows, shown for 3. To calculate 1/a, 1/b, 1/c, we do

t = 1/(abc), 1/a = bct, 1/b = act,  1/c = abt.

Also, sqrt(zz) = zz/sqrt(zz).

( See also http://moderncrypto.org/mail-archive/curves/2014/000064.html, 
http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html )

x_e = sqrt(T^2-Y^2) / sqrt(-dY^2-T^2) =
(T^2-Y^2) / sqrt( (T^2-Y^2)(-dY^2-T^2) )

With this in mind, here is the algorithm:

1. t = (T^2-Y^2)*(-d*Y^2-T^2) * T^2

2. tt = sqrt(1/t) ( paying the cost close to 1 inverse )

3. x_e = tt * (T^2-Y^2) * T

4. y_e = tt^2 * (T^2-Y^2)*(-d*Y^2-T^2) * T ( this is 1 / T )
    y_e = Y * y_e

5. Test that E(x_e,y_e)==0 (otherwise more thoughts are needed for point 
x validation and handling of O)

The sign of x_e will need to be adjusted, not discussed here.

Finally, the conversion back to Montgomery representation is simpler.

Let's assume that there is a projective (x/z, y/z) representation. 
(Other internal representations should work as well, as long as there is 
an inverse calculation to piggy-back on)

We know that Montgomery x is obtained from Edwards y_e as follows:

x = -(y_e+1)/(y_e-1).

To calculate affine y_e = y_e'/z_e' we calculate x directly from 
projective y_e' as follows:

x = - (y_e'+z_e')/(y_e'-z_e').

Thank you.