Subject: [Cfrg] Elliptic Curves - curve form and coordinate systems (ends on March 12th)

From: Alexey Melnikov <[email-masked]>
Date: Thu, 05 Mar 2015 23:31:01 +0000

CFRG chairs are starting discussion of the next topic:

Q4: draft-irtf-cfrg-curves-01 currently contains curves in both 
Montgomery form and Edwards form. The scalar multiplication routine is 
specified using Montgomery form (and is specific to Curve25519, which 
will need to be changed given our decision to include a higher security 
level curve). Its input is a scalar and the u-coordinate of a point on a 
Montgomery-form curve; its output is the u-coordinate of a point on a 
Montgomery-form curve. The DH function builds on this routine. Do we 
want to stay with specifying the inputs and outputs in Montgomery form 
for these routines? Or do we want to switch to an alternative curve form 
and coordinate system for defining the routines? If so, which form and 
coordinate system?

[Chairs are aware that it is possible to switch back and forward between 
different curve forms and coordinate systems, with associated costs, no 
matter which form is specified for the inputs and outputs of the 
routines. But we now have to decide *which* form we want to use for 
inputs and outputs, so as to ensure interoperability between Alice and 
Bob. Chairs did not want to implicitly force the choice of Montgomery 
form/coordinates without polling the group first.]

Once this issues is settled, we will be discussing (in no particular 
order. Chairs reserve the right to add additional questions) wire 
format, byte order and signature schemes. Please don't discuss any of 
these future topics at this time.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 5 Mar 2015 15:42:25 -0800

Montgomery form and Edwards form. The scalar multiplication routine is
specified using Montgomery form (and is specific to Curve25519, which will
need to be changed given our decision to include a higher security level
curve). Its input is a scalar and the u-coordinate of a point on a
Montgomery-form curve; its output is the u-coordinate of a point on a
Montgomery-form curve. The DH function builds on this routine. Do we want
to stay with specifying the inputs and outputs in Montgomery form for these
routines? Or do we want to switch to an alternative curve form and
coordinate system for defining the routines? If so, which form and
coordinate system?
different curve forms and coordinate systems, with associated costs, no
matter which form is specified for the inputs and outputs of the routines.
But we now have to decide *which* form we want to use for inputs and
outputs, so as to ensure interoperability between Alice and Bob. Chairs did
not want to implicitly force the choice of Montgomery form/coordinates
without polling the group first.]
> Once this issues is settled, we will be discussing (in no particular
order. Chairs reserve the right to add additional questions) wire format,
byte order and signature schemes. Please don't discuss any of these future
topics at this time.

If we specify the input as Montgomery form, how do we specify the wire
format separately?

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

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 06 Mar 2015 01:54:25 +0000

On 05/03/2015 23:31, Alexey Melnikov wrote:
> Q4: […] Do we want to stay with specifying the inputs and outputs
> in Montgomery form for [the scalar multiplication and DH]
> routines?

Yes, stick with Montgomery for DH/scalarmult.

The simplicity of X25519 is extremely hard to beat, and it has already
been widely deployed. I see no good reason to change that.

- -- 
/akr

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 5 Mar 2015 18:27:42 -0800

> been widely deployed. I see no good reason to change that.

+1 to both these remarks

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 6 Mar 2015 13:55:57 +0200

On Thu, Mar 05, 2015 at 11:31:01PM +0000, Alexey Melnikov wrote:
> Q4: draft-irtf-cfrg-curves-01 currently contains curves in both Montgomery
> form and Edwards form. The scalar multiplication routine is specified using
> Montgomery form (and is specific to Curve25519, which will need to be
> changed given our decision to include a higher security level curve). Its
> input is a scalar and the u-coordinate of a point on a Montgomery-form
> curve; its output is the u-coordinate of a point on a Montgomery-form curve.
> The DH function builds on this routine. Do we want to stay with specifying
> the inputs and outputs in Montgomery form for these routines? Or do we want
> to switch to an alternative curve form and coordinate system for defining
> the routines? If so, which form and coordinate system?

Montgomery u with infinity-to-zero-fold[1] for both.

Basically, offers excellent combination of performance, simplicity and small
implementation security gap.

[1] A.k.a. what Curve25519 does. The folding actually simplifies things
(infinity is no longer special case).

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 06 Mar 2015 09:45:42 -0800

> (infinity is no longer special case).

+1.  Despite my love for fancy point formats, the simplicity of 
Curve25519 is very valuable.

When it comes time for signatures, though, we will need at least a sign 
bit and possibly a different format.

-- Mike

---

From: Nadim Kobeissi <[email-masked]>
Date: Sun, 8 Mar 2015 11:13:15 +0100

Since I've never commented on this list about this before, I'd like to
quickly vouch for C25519's deployability/implementability/availability in
the field. It would be a mistake to lessen its inclusion now.

On Fri, Mar 6, 2015 at 6:45 PM, Mike Hamburg <[email-masked]> wrote:

>>> Montgomery
> +1.  Despite my love for fancy point formats, the simplicity of Curve25519
> is very valuable.
>

---

From: Adam Langley <[email-masked]>
Date: Thu, 12 Mar 2015 10:21:14 -0700

> the routines? If so, which form and coordinate system?

In the abstract I'd be happy with either the wire data being
Montgomery X, or a compressed (x,y) point on the Edward's curve. The
Montgomery ladder is pleasingly simple and I'd like to allow
implementations that only care about DH to be able to use it, but I
could live with Edwards form.

However, in practice, there's already a large population of code that
uses Montgomery X form and so I think that's probably the only viable
answer.

Cheers

AGL

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

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 12 Mar 2015 12:19:01 -0700

On 03/05/2015 03:31 PM, Alexey Melnikov wrote:
> will need to be changed given our decision to include a higher 
> security level curve). Its input is a scalar and the u-coordinate of a 
> point on a Montgomery-form curve; its output is the u-coordinate of a 
> point on a Montgomery-form curve. The DH function builds on this 
> routine. Do we want to stay with specifying the inputs and outputs in 
> Montgomery form for these routines? Or do we want to switch to an 
> alternative curve form and coordinate system for defining the 
> routines? If so, which form and coordinate system?
>
>
> [Chairs are aware that it is possible to switch back and forward 
> between different curve forms and coordinate systems, with associated 
> costs, no matter which form is specified for the inputs and outputs of 
> the routines. But we now have to decide *which* form we want to use 
> for inputs and outputs, so as to ensure interoperability between Alice 
> and Bob. Chairs did not want to implicitly force the choice of 
> Montgomery form/coordinates without polling the group first.]
>
>
>

A unified binary representation for a public key Q=k*G on the same curve 
is preferred, regardless of the fact that the Q is used with ECDH, 
ECDSA, EdDSA, PAKE, etc. My proposal incurs no (measurable) performance 
penalty for the proposed unification.

Consider the benefits of a single set of test vectors, code reuse, and 
the benefits of sharing pre-computed values. This proposal simply 
matches the capability of currently deployed ECC.

I propose the Montgomery curve representation (u, v), which can be used 
for signatures on the same curve.

"u" is identical to the sec 9 of 
https://tools.ietf.org/html/draft-agl-cfrgcurve-00.
"v" is calculated (at virtually no additional computational cost) as v = 
u^3 + 486662*u^2 + u

I am aware of the desire to enforce a key use type at the crypto level, 
but a widely used practice today on TLS servers is to require that a RSA 
server has both digitalSignature | keyEncipherment in its X.509 cert, 
otherwise such a TLS Web server cannot support ECDHE-RSA-AES128-SHA 
(digital signature) and AES128-SHA (RSA key transport) ciphersuites 
preferred by different clients with a single RSA key pair.

A sample of the interest in unified format can be found here:
https://github.com/agl/ed25519/blob/master/extra25519/extra25519.go 
(converts from Edwards to Montgomery for Curve25519)
https://github.com/dchest/ed2curve-js (dedicated to this conversion). 
Also please check other references listed in "Other libraries" there.

* An implementation that uses a Montgomery ladder simply ignores v (it 
only calculates v by reusing F(p) operations from its ECDH scalar 
multiplication code)
* This format allows more internal implementation choices
* The format is friendly for crypto algorithms that need to add points 
(as opposed to ECDH only)
* When a software library must implement both signatures and ECDH 
(something we assume to be common in the future) or even is interested 
in truly ephemeral public keys for ECDHE, the Montgomery ladder in sec 9 
is insufficient. Once that "other code" is written, it can do the job of 
Montgomery ladder at about the same speed.
* This proposal incurs 32 additional bytes of storage overhead for the 
public key, for the total of 64 bytes (compare this with 260+ bytes for 
RSA 2048).

Not sending u means that an implementation must incur ~10% performance 
penalty to recover v (unless the implementation is a Montgomery ladder, 
which doesn't need v). This is a headwind for any future internal 
improvement. On the other hand, calculating the v costs about 2M, under 
0.1% of the entire ECDHE cost.

---

From: Adam Langley <[email-masked]>
Date: Thu, 12 Mar 2015 12:53:31 -0700

On Thu, Mar 12, 2015 at 12:19 PM, Andrey Jivsov <[email-masked]> wrote:
> I propose the Montgomery curve representation (u, v), which can be used for
> signatures on the same curve.
>
> "v" is calculated (at virtually no additional computational cost) as v = u^3
> + 486662*u^2 + u

I'm going to display my ignorance here, but if "v" can be calculated
from just u with very little cost, why send it at all? The receiver
could equally calculate it if useful, no?

> * The format is friendly for crypto algorithms that need to add points (as
> opposed to ECDH only)

Wouldn't they need to know an extra bit? Given a point on the
Montgomery curve, (u,v), the "v" value is v^2, right? Doesn't that
discard the sign of v?

Cheers

AGL

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 12 Mar 2015 16:03:02 -0400

On Thu, Mar 12, 2015 at 3:53 PM, Adam Langley <[email-masked]>
wrote:

> u^3
> (as

I don't particularly care about performance differences unless they are at
least a factor of 2.

Robustness of implementation is another matter. That should be our
priority. Do not give any information that the security of the system
depends on the receiver checking.

If the points can be calculated by the receiver quickly, let them do that.
Otherwise we risk giving an attacker leverage by specifying bad points.

---

From: Paul Lambert <[email-masked]>
Date: Thu, 12 Mar 2015 13:03:23 -0700

]-----Original Message-----
]From: Cfrg [mailto:[email-masked]] On Behalf Of Andrey Jivsov
]Sent: Thursday, March 12, 2015 12:19 PM
]To: [email-masked]
]Subject: Re: [Cfrg] Elliptic Curves - curve form and coordinate systems
](ends on March 12th)
]
]On 03/05/2015 03:31 PM, Alexey Melnikov wrote:
]> CFRG chairs are starting discussion of the next topic:
]>
]> Q4: draft-irtf-cfrg-curves-01 currently contains curves in both
]> Montgomery form and Edwards form. The scalar multiplication routine is
]> specified using Montgomery form (and is specific to Curve25519, which
]> will need to be changed given our decision to include a higher
]> security level curve). Its input is a scalar and the u-coordinate of a
]> point on a Montgomery-form curve; its output is the u-coordinate of a
]> point on a Montgomery-form curve. The DH function builds on this
]> routine. Do we want to stay with specifying the inputs and outputs in
]> Montgomery form for these routines? Or do we want to switch to an
]> alternative curve form and coordinate system for defining the
]> routines? If so, which form and coordinate system?
]>
]>
]> [Chairs are aware that it is possible to switch back and forward
]> between different curve forms and coordinate systems, with associated
]> costs, no matter which form is specified for the inputs and outputs of
]> the routines. But we now have to decide *which* form we want to use
]> for inputs and outputs, so as to ensure interoperability between Alice
]> and Bob. Chairs did not want to implicitly force the choice of
]> Montgomery form/coordinates without polling the group first.]
]>
]>
]>
]> Once this issues is settled, we will be discussing (in no particular
]> order. Chairs reserve the right to add additional questions) wire
]> format, byte order and signature schemes. Please don't discuss any of
]> these future topics at this time.
]
]A unified binary representation for a public key Q=k*G on the same curve
]is preferred, regardless of the fact that the Q is used with ECDH,
]ECDSA, EdDSA, PAKE, etc. 

+1  

]My proposal incurs no (measurable) performance
]penalty for the proposed unification.
]
]Consider the benefits of a single set of test vectors, code reuse, and
]the benefits of sharing pre-computed values. This proposal simply
]matches the capability of currently deployed ECC.
]
]I propose the Montgomery curve representation (u, v), which can be used
]for signatures on the same curve.
]
]"u" is identical to the sec 9 of
]https://tools.ietf.org/html/draft-agl-cfrgcurve-00.
]"v" is calculated (at virtually no additional computational cost) as v =
]u^3 + 486662*u^2 + u
]
]I am aware of the desire to enforce a key use type at the crypto level,

Please - no such limitations.  The public key should be able to be used
for either or both ECDH and signatures.

Paul

]but a widely used practice today on TLS servers is to require that a RSA
]server has both digitalSignature | keyEncipherment in its X.509 cert,
]otherwise such a TLS Web server cannot support ECDHE-RSA-AES128-SHA
](digital signature) and AES128-SHA (RSA key transport) ciphersuites
]preferred by different clients with a single RSA key pair.
]
]A sample of the interest in unified format can be found here:
]https://github.com/agl/ed25519/blob/master/extra25519/extra25519.go
](converts from Edwards to Montgomery for Curve25519)
]https://github.com/dchest/ed2curve-js (dedicated to this conversion).
]Also please check other references listed in "Other libraries" there.
]
]* An implementation that uses a Montgomery ladder simply ignores v (it
]only calculates v by reusing F(p) operations from its ECDH scalar
]multiplication code)
]* This format allows more internal implementation choices
]* The format is friendly for crypto algorithms that need to add points
](as opposed to ECDH only)
]* When a software library must implement both signatures and ECDH
](something we assume to be common in the future) or even is interested
]in truly ephemeral public keys for ECDHE, the Montgomery ladder in sec 9
]is insufficient. Once that "other code" is written, it can do the job of
]Montgomery ladder at about the same speed.
]* This proposal incurs 32 additional bytes of storage overhead for the
]public key, for the total of 64 bytes (compare this with 260+ bytes for
]RSA 2048).
]
]Not sending u means that an implementation must incur ~10% performance
]penalty to recover v (unless the implementation is a Montgomery ladder,
]which doesn't need v). This is a headwind for any future internal
]improvement. On the other hand, calculating the v costs about 2M, under
]0.1% of the entire ECDHE cost.
]
]_______________________________________________
]Cfrg mailing list
][email-masked]
]http://www.irtf.org/mailman/listinfo/cfrg

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 12 Mar 2015 13:04:25 -0700

I apologize (need more coffee). I meant to write v = SQRT(u^3 + 
486662*u^2 + u). The SQRT can be calculated (for almost free) during X/Z 
calculation by the sender at the end of scalarmult, because the sender 
must do 1/Z, but there is no apparent way to avoid SQRT for the receiver 
(unless the received doesn't need v and only works on u). The sign is 
embedded in v (and v can be adjusted  p-v as needed for signatures; ECDH 
doesn't care).

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 12 Mar 2015 20:06:20 +0000

> If the points can be calculated by the receiver quickly, let them do that. Otherwise we risk giving an attacker leverage by specifying bad points.

+1!

---

From: Adam Langley <[email-masked]>
Date: Thu, 12 Mar 2015 13:17:14 -0700

On Thu, Mar 12, 2015 at 1:04 PM, Andrey Jivsov <[email-masked]> wrote:
> I apologize (need more coffee). I meant to write v = SQRT(u^3 + 486662*u^2 +
> u). The SQRT can be calculated (for almost free) during X/Z calculation by
> the sender at the end of scalarmult, because the sender must do 1/Z, but
> there is no apparent way to avoid SQRT for the receiver (unless the received
> doesn't need v and only works on u). The sign is embedded in v (and v can be
> adjusted  p-v as needed for signatures; ECDH doesn't care).

Ah, thanks. That makes a lot more sense.

The point format could certainly be (u,v) and that could unify the
format for signature and DH public keys. I think the impression in the
past has been that we are willing to pay a little CPU time to
eliminate some implementation pitfalls. Here the pitfall would be
omitting to check that (u,v) is a point on the curve—something that
sending compressed points avoids.

So we could say that the format is u + the sign bit of v. The sign bit
can even be packed into the MSB of u in the case of curve25519. So we
could get a unified DH and signature point format and safety with
that, although existing implementations would only be compatible when
receiving. So I think that would lead to a lot of deployments that
would always set the sign bit to zero because they're actually an
existing curve25519 implementation underneath.

When we've had compatible DH and signature formats (i.e. ECC X.509
signatures with X9.62 encoding) it's actually been a problem, not a
blessing. CAs have had to remove the keyAgreement bit from these
certificates so that they aren't accidentally used for fixed-DH in
TLS.

Cheers

AGL

---

From: Nico Williams <[email-masked]>
Date: Thu, 12 Mar 2015 15:23:14 -0500

On Thu, Mar 05, 2015 at 11:31:01PM +0000, Alexey Melnikov wrote:
> Montgomery form and Edwards form. The scalar multiplication routine
> is specified using Montgomery form (and is specific to Curve25519,
> which will need to be changed given our decision to include a higher
> security level curve). Its input is a scalar and the u-coordinate of

I don't understand the parenthetical.  What does including a higher
security-level curve have to do with whether Curve25519 uses Montgomery
form?

> a point on a Montgomery-form curve; its output is the u-coordinate
> of a point on a Montgomery-form curve. The DH function builds on
> this routine. Do we want to stay with specifying the inputs and
> outputs in Montgomery form for these routines? Or do we want to
> switch to an alternative curve form and coordinate system for
> defining the routines? If so, which form and coordinate system?

Stay, not switch.

Yesterday I posted an extended reply about this as a follow-up to
Watson's reply about this:

http://www.ietf.org/mail-archive/web/cfrg/current/msg06438.html

> between different curve forms and coordinate systems, with
> associated costs, no matter which form is specified for the inputs
> and outputs of the routines. But we now have to decide *which* form
> we want to use for inputs and outputs, so as to ensure
> interoperability between Alice and Bob. Chairs did not want to
> implicitly force the choice of Montgomery form/coordinates without
> polling the group first.]

There is no need to switch back and forth between code representations
unless one wishes to use a private key both for ECDH *and* other ECC
purporses (e.g., signatures) where Montgomery is a pessimization.  Even
should such a use-case arise, as you point out, conversions are
possible.

> format, byte order and signature schemes. Please don't discuss any
> of these future topics at this time.

Sure, though of course, if we accept that each curve can dictate what
point representation to use [up to and including separately for each use
type, ECDH, signatures, ...], then there's no point getting exercised
about Curve25519's choice of marshalling format (including endianness)
(but there would be a point to getting exercised about changing that).

Nico
--

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 12 Mar 2015 13:26:41 -0700

Hi Andrey,

Have you considered the extra complexity to compute which is the correct v at the end of the Montgomery ladder?  If you want a unified point format that every operation uses, you need a way to compute the sign of v.

I get 4 u0 v1 v2 = (1 - u1 u2 - u0 u2 + u0 u1) (1 - u1 u2 + u0 u2 - u0 u1) and symmetrically.  This doesn’t require a square root if you know the input’s v coordinate, but it does increase complexity.  At some point you might as well go full decaf, particularly if there’s no trivial patch to existing curve25519() functions.

Cheers,
— Mike

> On Mar 12, 2015, at 1:04 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> I apologize (need more coffee). I meant to write v = SQRT(u^3 + 486662*u^2 + u). The SQRT can be calculated (for almost free) during X/Z calculation by the sender at the end of scalarmult, because the sender must do 1/Z, but there is no apparent way to avoid SQRT for the receiver (unless the received doesn't need v and only works on u). The sign is embedded in v (and v can be adjusted  p-v as needed for signatures; ECDH doesn't care).
>

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 12 Mar 2015 13:40:40 -0700

Or maybe I’m misunderstanding.  Are you still figuring that an ECDH implementation will only use the u output from the Montgomery ladder?

In that case, the ladder doesn’t have this added complexity, but I prefer Adam’s suggestion to use a sign bit instead of sending the full v coordinate.  In that case also, ECDH wouldn’t output the sign bit, so it wouldn’t be a completely unified point format, but that’s fine.

Cheers,
— Mike

> On Mar 12, 2015, at 1:26 PM, Michael Hamburg <[email-masked]> wrote:
> 
> Hi Andrey,
>

---

From: Dan Brown <[email-masked]>
Date: Thu, 12 Mar 2015 21:03:51 +0000

> -----Original Message-----
> From: Adam Langley
> 
> pitfalls. Here the pitfall would be omitting to check that (u,v) is a point on the
> curve—something that sending compressed points avoids.

 [DB] Compressed points are not really what protects against bad points (though I've also forgotten that fact a few times too).  For Curve25519, the protection is from the XZ (oops UW?) coordinates, i.e. the Montgomery ladder, plus twist security. In other words, upon receiving v for ECDH, just discard v.  (* Well, maybe there's protection from the field size too, see below.)
 
Last fall, I sent CFRG an example of an order 11 compressed bad point for P256 (perhaps some people manually/automatically ignore my messages, understandably ;-)

I have not worked out the details of a similar example for Curve25519. To be applicable, some Curve25519 user would have to decompress to XYZ (oops UVW) coordinates.  I'm not aware of anybody using XYZ coordinates for Curve25519, or any good reason to do so.  But bad compressed points could probably be found for some XYZ coordinate addition rules. (* Well, I didn't check if there's a realistic bad decompression for 5 mod 8 fields, i.e. a natural way to produce false square roots).

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 12 Mar 2015 15:06:22 -0700

> Or maybe I’m misunderstanding.  Are you still figuring that an ECDH implementation will only use the u output from the Montgomery ladder?

Correct, the Montgomery implementation would always use u (disregard v 
on input).

The shared secret is u, as produced by the existing Montgomery ladder 
code. If the implementation is a mix of e.g. Twisted Edwards calculation 
for fixed base and Montgomery for variable base, the Montgomery ladder 
code doesn't change at all.

Ephemeral keys can be pre-calculated (or reused) and thus the <1% cost 
applies to the worst-case scenario. Public keys in certificates live for 
years.

> In that case, the ladder doesn’t have this added complexity, but I prefer Adam’s suggestion to use a sign bit instead of sending the full v coordinate.  In that case also, ECDH wouldn’t output the…

Adam's proposal is a step in the direction I advocate, except that I 
point that sending only 1 bit, i.e. the point compression, has 10% 
penalty during decompression. For this reason I think that the sender 
should "help" the recipient avoid it for about 10% saving for both.

The cost of decompression is 10% for each ECDHE or signature verification.

I wonder how many trees will die due to everybody decompressing the v 
for the life of each certificate :-) ?

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 12 Mar 2015 22:33:43 +0000

>security-level curve have to do with whether Curve25519 uses Montgomery

Nothing. The point is that the current text concerning the scalar
multiplication routine is very tied to Curve25519, and needs to be
modified if it is to be able to handle other curves - either by
generalising it or including separate and parallel text for each
additional curve. No-one is proposing to harm Curve25519 in any way!

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 12 Mar 2015 16:47:51 -0700

>> If the points can be calculated by the receiver quickly, let them do that. Otherwise we risk giving an attacker leverage by specifying bad points.

The point is moot for PKI: an entity receiving an X.509 certificate 
explicitly trusts (u,v). Likewise, the same is true for other signing 
keys like OpenPGP.

it's easy to confirm that (u, v) satisfies v^2 == u^3 + 486662*u^2 + u 
for static ECDH keys.

It would be difficult to avoid point validation today if:

* one uses a well-known software library
* in the context of already established protocols, one intends to 
interoperate with others or make product usable by US or other 
governments, which means at least P-256 support
* one ever applies for FIPS 140 certification, which requires point 
validation

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 12 Mar 2015 17:21:31 -0700

> On Mar 12, 2015, at 3:06 PM, Andrey Jivsov <[email-masked]> wrote:
> I wonder how many trees will die due to everybody decompressing the v for the life of each certificate :-) ?

Sending data over LTE costs 328-615 microjoules per bit [1], presumably mostly on the base station.  Split the middle on that, and figure an extra 256 bits takes 0.12 joules.

[1] http://www.theatlantic.com/technology/archive/2013/04/cell-networks-are-energy-hogs/274961/ <http://www.theatlantic.com/technology/archive/2013/04/cell-networks-are-energy-hogs/274961/>

802.11n takes a couple orders of magnitude less energy, so that would be a millijoule.

A Curve25519 point decompression taking 30 microseconds on a 2-watt cell phone processor would take 60 microjoules.  An Ed448-Goldilocks point decompression taking 16 microseconds on a 30-watt server core is half a millijoule.

Remind me how compression takes more energy?

— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 12 Mar 2015 18:18:24 -0700

On 03/12/2015 05:21 PM, Michael Hamburg wrote:
>
>> On Mar 12, 2015, at 3:06 PM, Andrey Jivsov <[email-masked] 
>> <mailto:[email-masked]>> wrote:
> Sending data over LTE costs 328-615 microjoules per bit [1], 
> presumably mostly on the base station.  Split the middle on that, and 
> figure an extra 256 bits takes 0.12 joules.
>
> [1] 
> http://www.theatlantic.com/technology/archive/2013/04/cell-networks-are-energy-hogs/274961/
>
> A Curve25519 point decompression taking 30 microseconds on a 2-watt 
> cell phone processor would take 60 microjoules.  An Ed448-Goldilocks 
> point decompression taking 16 microseconds on a 30-watt server core is 
> half a millijoule.
>

That's interesting about LTE. I was viewing it from the need to buy more 
servers and saving battery life of mobile devices -- computational heat, 
but your are right about some cost of transmitting the bytes.

I assume that decompression means a square root F(p), which is ~ 10% of 
scalar mult.

X.509 verifiers must pay 10% more computational cost to decompress, 
while not every public key is transmitted. An implementation could cache 
a decompressed public key of a sub-CA but this is an additional 
(external to crypto) complexity for 10% saving.

It seems to me that public key crypto offers the worst possible tradeoff 
between computation cost / space efficiency. For lower-hanging fruits 
please consider: TLS removing compression of the record layer, a TLS 
record padding proposal for 1.3 against traffic analysis (up to ~16K), 
an average X.509 certificate ~1K, TLS handshake size at about 4K, and 
the benefits of TLS session reuse / Session ticket.

I am not against compression. It makes sense e.g. when an SMIME message 
is encrypted to multiple recipients, but then again did users care about 
this for larger RSA keys?

---

From: Jakob Breier <[email-masked]>
Date: Fri, 13 Mar 2015 13:18:23 +0100

On 12.03.2015 20:19, Andrey Jivsov wrote:
> public key, for the total of 64 bytes (compare this with 260+ bytes 
> for RSA 2048). 

The storage costs and transmission costs might be insignificant for 
machines, but I'd like to point out the human storage and transmission 
costs. Take a look at SSH keys for example. Compare how well you can 
visually parse several lines of keys in an authorized_keys file in these 
three formats:

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDRTSfbRohGanse3u4gnu8wOId85f5KKyEzo/l
MabVM4J92n6r4NPgN46pQ3bTc8XzLO5zHXY/mPSwQru3Ks+6Mcut7bDo0ohPcLcdIYGTbqXkfz3
KNDbdXwPMcaPamLmugNnj9UK2cPe8Q7F9DGSLaQc1eiC0JS/Qm0gG3ULqX3DEDFQbLBzH326Lov
9gplu/U7D0bBiM7q7VQs32sz11L4KWY3RzUhuy6bQ7GGrkGvp78l7f+56AvQNeIV8fDOWKNE73s
Q3NybxWxQ771c5c+AZGYzkERlHWjxaxGA6V8ZUiE2VftHZMY4k6z4DC9hiadxwmr85qWriC7RrT
OjmN9 Alice-HomePc

ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBLB
RUKndAEfMluniDolf8eJIdhh1l9C2iXKtnbvbM9vFbBMQ+l47i7wusn4G2RMYsFPbwlV4XQt4TT
sEwkrcLss= Alice-HomePc

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAICxtv8s7nwLqhkhryoY+w/u9ZrY7dr0ZPZhYuOS
bxTIb Alice-HomePc

They are in turn: RSA (2048 bit), 65 byte long nistp256 key and 32 byte 
long ed25519 key (apparently, openssh already uses point compression for 
this format). The difference would be even more pronounced, if the SSH 
key storage format was more efficient, but the result of factor two 
decrease from 64 byte to 32 byte keys is still significant. And these 
are keys that you often copy and paste as plain text instead of sending 
pubkey files, e.g. when you add one to GitHub or instant message it to a 
friend.

Another example is TextSecure, the end-to-end encrypted messenger app, 
that allows you to verify the 33 byte "identity" (32 byte Curve25519 key 
+ 0x05 prefix) by comparing them manually as 66 hex characters (or 
scanning a QR-code). Threema, another encrypted messenger app, also 
directly compares the public key (32 byte Curve25519) in the QR-code. 
(Threema does also feature a 128bit fingerprint, though, that can be 
compared by reading it aloud.)

As all three examples feature interactive protocols anyway, they could 
use fingerprints instead, but for various reasons don't and thus profit 
from short key sizes.

An example that does not have the alternative of using fingerprints are 
key revocation certificates. I have a few of these printed out for RSA 
keys and I fear the day I actually have to type them in.
Also, if we'll ever have a chance to bring strong end-to-end 
cryptography to the masses, then we need inexperienced users to backup 
their private key. And I trust my parents far more to securely store, 
and later on use, a slip of paper - which means writing down and later 
typing back in the key - than a USB stick / a memory card / a CD / …, 
all which have to be periodically checked whether they are still 
readable. And while this would be totally impractical with RSA keys, 
with EC keys this becomes borderline usable. And here the difference 
between 64 and 32 bytes is enormous.

Best regards,
Jakob Breier

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 13 Mar 2015 08:43:06 -0400

On Fri, Mar 13, 2015 at 8:18 AM, Jakob Breier <[email-masked]>
wrote:

>> public key, for the total of 64 bytes (compare this with 260+ bytes for RSA
>> 2048).
>>
>

+1

The main reasons I am interested in ECC systems as a replacement for RSA
are:

* The short key size is more compatible with URI/fingerprint.
* New ways to deal with the problem of defective key generation[1].
* Better work factor safety margin (WF-128  rather than 112)
* Only feasible approach beyond 128 bit WF.

Performance is the easiest to measure but not the reason for making a
change.

[1] Comodo Group has pending IPR claims.

---

From: Rene Struik <[email-masked]>
Date: Fri, 13 Mar 2015 10:50:08 -0400

Hi Jakob:

This confuses different discussions:

a) use of public key in computations.
Here, Andrey Jivsov's point was that receipt of a full point (x,y) on a 
curve, rather than a compressed point or simply the x-coordinate, does 
not artificially impose a performance penalty on all implementations 
except x-coordinate-only ones (Montgomery).
b) representation of public key in white list.
Here, one can use many methods to map a public key Q to a condensed 
(perhaps, even human-recognizable) format f(Q).
This condensed format could take the form affine format curve point, 
compressed format, hash, leftmost n-octets, hash value, etc.

My own take:

Ad a):
I fully agree with Andrey Jivsov's point and think using x-coordinate 
only representations imposes a "moat" around ECC implementations, by 
imposing a levy on all implementations that, for whatever reason, may 
want to use something else than Montgomery arithmetic. {Please note that 
this levy is incurred (in the context of ECDH) during *online* 
computations.} Such fully specified points are particularly useful in 
settings, including multiple-point multiplication, combined key 
computations and signature verifications, batch computations, since may 
allow significant performance advantages in those settings.

Ad b):
This is a non-issue in representation discussions with CFRG with ECC, 
since dealing with protocol issues, not user interfaces.
Nevertheless, here is a comparison that illustrates some condensed 
representations that are possibly in a completely standardized way, 
resp. "cooked up" for user interfaces:

Comparison example:
example P-256 public key, with affine coordinates (x,y),
x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 7d 81 2d 
eb 33 a0 f4 a1 39 45 d8 98 c2 96
y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 33 57 6b 
31 5e ce cb b6 40 68 37 bf 51 f5
a) standardized affine format: (0x04 || x-coord || y-coord) {65 octets}
b) standardized compressed format: (0x03 || x-coordinate) {33 octets}
c) non-standard, x-coordinate-only: x-coordinate {32 octets}
d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 03 
7d 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}

example Curve25519, Alice's public key (source: 
draft-irtf-agl-cfrgcurve-00):
x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 3a 0d 26 
38 1a f4 eb a4 a9 8e aa 9b 4e 6a
c) non-standard, x-coordinate-only: x-coordinate {32 octets}

On 3/13/2015 8:18 AM, Jakob Breier wrote:
>> * This proposal incurs 32 additional bytes of storage overhead for 
>> the public key, for the total of 64 bytes (compare this with 260+ 
>> bytes for RSA 2048). 
>
> visually parse several lines of keys in an authorized_keys file in 
> these three formats:
>
> ssh-rsa 
> AAAAB3NzaC1yc2EAAAADAQABAAABAQDRTSfbRohGanse3u4gnu8wOId85f5KKyEzo/l
> ecdsa-sha2-nistp256 
> AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBLB
> ssh-ed25519 
> AAAAC3NzaC1lZDI1NTE5AAAAICxtv8s7nwLqhkhryoY+w/u9ZrY7dr0ZPZhYuOS
> bxTIb Alice-HomePc
>
> They are in turn: RSA (2048 bit), 65 byte long nistp256 key and 32 
> byte long ed25519 key (apparently, openssh already uses point 
> compression for this format). The difference would be even more 
> pronounced, if the SSH key storage format was more efficient, but the 
> result of factor two decrease from 64 byte to 32 byte keys is still 
> significant. And these are keys that you often copy and paste as plain 
> text instead of sending pubkey files, e.g. when you add one to GitHub 
> or instant message it to a friend.
>
> that allows you to verify the 33 byte "identity" (32 byte Curve25519 
> key + 0x05 prefix) by comparing them manually as 66 hex characters (or 
> use fingerprints instead, but for various reasons don't and thus 
> profit from short key sizes.
>
> An example that does not have the alternative of using fingerprints 
> are key revocation certificates. I have a few of these printed out for 
> RSA keys and I fear the day I actually have to type them in.

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Mar 2015 08:20:28 -0700

On Fri, Mar 13, 2015 at 7:50 AM, Rene Struik <[email-masked]> wrote:
> curve, rather than a compressed point or simply the x-coordinate, does not
> artificially impose a performance penalty on all implementations except
> x-coordinate-only ones (Montgomery).

This isn't artificial: use of compressed and x only coordinate
representations has security benefits, because it makes the simplest
implementation very simple.

> I fully agree with Andrey Jivsov's point and think using x-coordinate only
> representations imposes a "moat" around ECC implementations, by imposing a
> levy on all implementations that, for whatever reason, may want to use
> something else than Montgomery arithmetic. {Please note that this levy is
> incurred (in the context of ECDH) during *online* computations.} Such fully
> specified points are particularly useful in settings, including
> multiple-point multiplication, combined key computations and signature
> verifications, batch computations, since may allow significant performance
> advantages in those settings.

But we're discussing ECDH, which isn't any of these cases. Of course,
there is no performance penalty: the Montgomery ladder is the fastest
variable scalar multiplication. Users who don't care about performance
can incur the square root cost: they don't care. Users who do care
about performance are already going to use the Montgomery ladder.

>
> Ad b):
> This is a non-issue in representation discussions with CFRG with ECC, since
> dealing with protocol issues, not user interfaces.
> representations that are possibly in a completely standardized way, resp.
> "cooked up" for user interfaces:
>
> Comparison example:
> x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 7d 81 2d eb
> 33 a0 f4 a1 39 45 d8 98 c2 96
> y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 33 57 6b 31
> 5e ce cb b6 40 68 37 bf 51 f5
> d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 03 7d
> 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}
>
> x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 3a 0d 26 38
> 1a f4 eb a4 a9 8e aa 9b 4e 6a
>> this format). The difference would be even more pronounced, if the SSH key
>> storage format was more efficient, but the result of factor two decrease
>> from 64 byte to 32 byte keys is still significant. And these are keys that
>> you often copy and paste as plain text instead of sending pubkey files, e.g.
>> when you add one to GitHub or instant message it to a friend.
>>
>> that allows you to verify the 33 byte "identity" (32 byte Curve25519 key +
>> 0x05 prefix) by comparing them manually as 66 hex characters (or scanning a
>> QR-code). Threema, another encrypted messenger app, also directly compares
>> the public key (32 byte Curve25519) in the QR-code. (Threema does also
>> feature a 128bit fingerprint, though, that can be compared by reading it
>> aloud.)
>>
>> As all three examples feature interactive protocols anyway, they could use
>> fingerprints instead, but for various reasons don't and thus profit from
>> short key sizes.
>>
>> key revocation certificates. I have a few of these printed out for RSA keys
>> and I fear the day I actually have to type them in.
>> Also, if we'll ever have a chance to bring strong end-to-end cryptography
>> to the masses, then we need inexperienced users to backup their private key.
>> And I trust my parents far more to securely store, and later on use, a slip
>> of paper - which means writing down and later typing back in the key - than
>> a USB stick / a memory card / a CD / …, all which have to be periodically
>> checked whether they are still readable. And while this would be totally
>> impractical with RSA keys, with EC keys this becomes borderline usable. And
>> here the difference between 64 and 32 bytes is enormous.
>>
>> Best regards,
>> Jakob Breier
>>

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

---

From: Rene Struik <[email-masked]>
Date: Fri, 13 Mar 2015 12:07:43 -0400

Hi Watson:

I think your assessment is technically incorrect. Please see details below.

Rene

> implementation very simple.
RS>>
As Andrey Jivsov already pointed out in an email long time ago, using 
affine coordinates (x,y) allows
i) those implementers that wish to perform x-coordinate only arithmetic 
to do so: they simply discard the y-coordinate of a received affine point;
ii) those implementers that do wish to use a different method can do so, 
without the need to perform point decompression. They could also carry 
out point validation, at cost of roughly 2S+M for Montgomery curves with 
small 'A' value (S=field squaring; M= field multiply), which is << 1% of 
total cost and completely trivial.

Note: I know that you might bring up that people can "forget" to 
implement this known check that is known for over 15 years, but then 
people can also "forget" to check whether Curve25519 DH keys are equal 
to zero, so that discussion leads nowhere, since only speculates on 
levels of sloppy behavior one attributes to implementers in one case, 
but magically not in another.
<<RS
> But we're discussing ECDH, which isn't any of these cases.
RS>> For a counter-example, please see my SAC 2010 paper on combined key 
computations and signature verification. That paper illustrated that the 
incremental cost of ECDSA signature verification would shrink 
considerably when combined with ECDH key computation, rather than when 
executed separately. See, e.g., 
http://link.springer.com/chapter/10.1007%2F978-3-642-19574-7_9. The 
paper suggests that essentially one gets ECDSA verifies for roughly half 
the computational cost compared to when not using these tricks, with a 
footnote at the end suggesting that improvements may be even more 
pronounced with twisted Edwards curves (since depending on relative 
Double/Add cost). {Of course, actual improvements depend on 
implementation platform and scalar multiplication details, but can be 
shown to hold accross the board, when one applies one's favorite picks 
there.}

The point of my note was that enforcing x-coordinate only 
representations would block approaches, such as, e.g., those in that SAC 
2010 paper, whereas using affine coordinates does not. Shouldn't 
implementers be able to have some design freedom, if that would suit 
them? (Esp. since speed has been touted as one of the triggers to 
consider new curve forms?)
<<RS
> Of course,

---

From: Nico Williams <[email-masked]>
Date: Fri, 13 Mar 2015 11:33:37 -0500

On Fri, Mar 13, 2015 at 10:50:08AM -0400, Rene Struik wrote:
> Here, Andrey Jivsov's point was that receipt of a full point (x,y)
> on a curve, rather than a compressed point or simply the
> x-coordinate, does not artificially impose a performance penalty on
> all implementations except x-coordinate-only ones (Montgomery).

A "penalty" of some sort is involved in *all* possible choices, and
there isn't one that is ideal for all use-cases.  Others have pointed
this out.

ECDH-only applications will exist and will be a/the common case.  Add to
this the simplicity arguments, and clearly x-only Montgomery is a better
choice for ECDH.

Some trade-offs:

 - x-only -> you must either have a Montgomery ladder implementation
             *and* other implementations if you *also* support
             signatures

             or

             you must have point conversion code *and* use it for ECDH
             (10% penalty)

   Obviously (I think), the first choice is better: it's a development-
   and compile-time cost, with the small additional run-time cost of
   extra text footprint IF you need both around (point coversion also
   has this extra text footprint at run-time).

 - (x,y)  -> bandwidth waste Montogmery ladder implementations

   This is not nothing (see Mike H.'s posts).

Similarly for (x,sign(y)).

> compressed format, hash, leftmost n-octets, hash value, etc.

For (b), I don't see why x-only isn't good enough.  Can you elaborate?

Nico
--

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Mar 2015 10:12:08 -0700

>>> curve, rather than a compressed point or simply the x-coordinate, does
not
> ii) those implementers that do wish to use a different method can do so,
without the need to perform point decompression. They could also carry out
point validation, at cost of roughly 2S+M for Montgomery curves with small
'A' value (S=field squaring; M= field multiply), which is << 1% of total
cost and completely trivial.

Y recovery complicates the Montgomery ladder significantly.

> Note: I know that you might bring up that people can "forget" to
implement this known check that is known for over 15 years, but then people
can also "forget" to check whether Curve25519 DH keys are equal to zero, so
that discussion leads nowhere, since only speculates on levels of sloppy
behavior one attributes to implementers in one case, but magically not in
another.
> <<RS

The consequences of getting the identity are minor. The consequences of
accepting points of small order are loss of the private key.

>>> I fully agree with Andrey Jivsov's point and think using x-coordinate
only
computations and signature verification. That paper illustrated that the
incremental cost of ECDSA signature verification would shrink considerably
when combined with ECDH key computation, rather than when executed
separately. See, e.g.,
http://link.springer.com/chapter/10.1007%2F978-3-642-19574-7_9. The paper
suggests that essentially one gets ECDSA verifies for roughly half the
computational cost compared to when not using these tricks, with a footnote
at the end suggesting that improvements may be even more pronounced with
twisted Edwards curves (since depending on relative Double/Add cost). {Of
course, actual improvements depend on implementation platform and scalar
multiplication details, but can be shown to hold accross the board, when
one applies one's favorite picks there.}

Combs still work for fixed based mults.

>
> The point of my note was that enforcing x-coordinate only representations
would block approaches, such as, e.g., those in that SAC 2010 paper,
whereas using affine coordinates does not. Shouldn't implementers be able
to have some design freedom, if that would suit them? (Esp. since speed has
been touted as one of the triggers to consider new curve forms?)
>>> This is a non-issue in representation discussions with CFRG with ECC,
since
>>> representations that are possibly in a completely standardized way,
resp.
>>> d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 03
7d
>>>>> public key, for the total of 64 bytes (compare this with 260+ bytes
for RSA
>>>> visually parse several lines of keys in an authorized_keys file in
these
>>>> this format). The difference would be even more pronounced, if the SSH
key
>>>> that allows you to verify the 33 byte "identity" (32 byte Curve25519
key +
>>>> As all three examples feature interactive protocols anyway, they could
use
>>>> key revocation certificates. I have a few of these printed out for RSA
keys
>>>> Also, if we'll ever have a chance to bring strong end-to-end
cryptography

---

From: Rene Struik <[email-masked]>
Date: Fri, 13 Mar 2015 13:34:11 -0400

Hi Watson:

I do not want this exchange to take ad infinitum, since I think I made 
my point.

One note, though:  the scenario where the DH key is the identity 
corresponds to a point of order one (the smallest order theoretically 
possible), which, if not checked for, immediately results in an 
unsecured channel (or, more aptly, a channel secured with a fixed key 
[akin to using as key an all-zero string or empty string password]).

Rene
==

On 3/13/2015 1:12 PM, Watson Ladd wrote:
>
>
> On Mar 13, 2015 9:08 AM, "Rene Struik" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> > Hi Watson:
> >
> >> On Fri, Mar 13, 2015 at 7:50 AM, Rene Struik <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >>>
> >>> Hi Jakob:
> >>>
> on a
> > As Andrey Jivsov already pointed out in an email long time ago, 
> using affine coordinates (x,y) allows
> > i) those implementers that wish to perform x-coordinate only 
> arithmetic to do so: they simply discard the y-coordinate of a 
> received affine point;
> > ii) those implementers that do wish to use a different method can do 
> so, without the need to perform point decompression. They could also 
> carry out point validation, at cost of roughly 2S+M for Montgomery 
> curves with small 'A' value (S=field squaring; M= field multiply), 
> which is << 1% of total cost and completely trivial.
>
> The consequences of getting the identity are minor. The consequences 
> of accepting points of small order are loss of the private key.
>
> >
> > RS>> For a counter-example, please see my SAC 2010 paper on combined 
> key computations and signature verification. That paper illustrated 
> that the incremental cost of ECDSA signature verification would shrink 
> paper suggests that essentially one gets ECDSA verifies for roughly 
> half the computational cost compared to when not using these tricks, 
> with a footnote at the end suggesting that improvements may be even 
> more pronounced with twisted Edwards curves (since depending on 
> relative Double/Add cost). {Of course, actual improvements depend on 
> representations would block approaches, such as, e.g., those in that 
> SAC 2010 paper, whereas using affine coordinates does not. Shouldn't 
> >>>> [email-masked] <mailto:[email-masked]>
> >>> email: [email-masked] <mailto:[email-masked]> | 
> Skype: rstruik
> >>> [email-masked] <mailto:[email-masked]>
> > email: [email-masked] <mailto:[email-masked]> | Skype: 
> rstruik

---

From: Jakob Breier <[email-masked]>
Date: Fri, 13 Mar 2015 18:39:38 +0100

Hey Rene,

thanks for your reply. I was well aware of the distinction between a) 
and b). The implicit argument, which I did not spell out unfortunately, 
was that

1. It's desirable to have as few point formats for a curve as possible 
(KISS rule). Elliptic curve cryptography might be a mess already, but if 
we never start simplifying things, it will still be a mess in 20 years. 
I'd like to be able to point people to the new IETF curves when the CFRG 
is through and tell them "use these curves / point formats (and if 
possible only those) and life will be as easy as ECC can get". A 
separate x-coordinate-only format for Montgomery multiplication is worth 
it in my opinion because of the implementation simplicity it affords, 
but having an additional compressed format is probably not.

2. Implementers will likely not go through the hassle of adding an 
additional compressed point format, but instead use the wire format they 
have to support. I'd like to be proven wrong on this, though.
As evidence I point to the OpenSSH key formats. They could already have 
used compressed points with nistp256 and, as far as I can tell, OpenSSL 
as well as the chosen storage format even supports them (the latter of 
which you have pointed out - thanks btw, I didn't recognize that 
before). But they only switched when they were forced to move away from 
OpenSSL to support Ed25519 and imported the SUPERCOP implementation [1] 
which *only* supports compressed points [2]. So only having one "right" 
format apparently did make the difference between having nice user 
facing point formats or not.

Please note however, that all the points I've made so far are second 
order arguments. While I would love to finally have short asymmetric 
keys, the far more important aspect for me is to assert that 
implementers cannot screw up point validation. And point compression 
seems to be necessary towards that end. I'll not rehash the reasons why 
implementers cannot be entrusted with such an easy step as plugging 
variables into an equation - this has already been amply discussed on 
this list and those reasons either convince you already, or don't.

I've only brought up the "human bandwidth" line of reasoning (which I 
nonetheless find significant) and caused the associated extra noise, 
because I'm afraid that point validation alone does not swing the tide 
towards compressed points.

Best regards,
Jakob Breier

[1] 
https://lists.mindrot.org/pipermail/openssh-unix-dev/2013-December/031871.html
[2] See e.g. the python implementation 
http://ed25519.cr.yp.to/python/ed25519.py , especially encodepoint and 
decodepoint.

On 13.03.2015 15:50, Rene Struik wrote:
> Here, Andrey Jivsov's point was that receipt of a full point (x,y) on 
> a curve, rather than a compressed point or simply the x-coordinate, 
> does not artificially impose a performance penalty on all 
> implementations except x-coordinate-only ones (Montgomery).
> want to use something else than Montgomery arithmetic. {Please note 
> that this levy is incurred (in the context of ECDH) during *online* 
> computations and signature verifications, batch computations, since 
> may allow significant performance advantages in those settings.
>
> Ad b):
> x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 7d 81 
> 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96
> y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 33 57 
> 6b 31 5e ce cb b6 40 68 37 bf 51 f5
> d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 
> 03 7d 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}
>
> x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 3a 0d 
> 26 38 1a f4 eb a4 a9 8e aa 9b 4e 6a

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 13 Mar 2015 19:41:47 +0200

On Fri, Mar 13, 2015 at 01:34:11PM -0400, Rene Struik wrote:
> 
> One note, though:  the scenario where the DH key is the identity corresponds
> to a point of order one (the smallest order theoretically possible), which,
> if not checked for, immediately results in an unsecured channel (or, more
> aptly, a channel secured with a fixed key [akin to using as key an all-zero
> string or empty string password]).

If key exchange is any good, then either that will be detected or the
channel is insecure anyway (since you have undetected MITM).

-Ilari

---

From: Watson Ladd <[email-masked]>
Date: Fri, 13 Mar 2015 10:43:18 -0700

On Mar 13, 2015 10:34 AM, "Rene Struik" <[email-masked]> wrote:
>
> Hi Watson:
>
> I do not want this exchange to take ad infinitum, since I think I made my
point.
corresponds to a point of order one (the smallest order theoretically
possible), which, if not checked for, immediately results in an unsecured
channel (or, more aptly, a channel secured with a fixed key [akin to using
as key an all-zero string or empty string password]).

Any attack requiring cooperation of one side doesn't count. A protocol that
properly hashes transcripts doesn't have the problem with zero keys that
TLS does. But there is no similar protection for missing validation.
on a
>> > i) those implementers that wish to perform x-coordinate only
arithmetic to do so: they simply discard the y-coordinate of a received
affine point;
>> > ii) those implementers that do wish to use a different method can do
so, without the need to perform point decompression. They could also carry
out point validation, at cost of roughly 2S+M for Montgomery curves with
small 'A' value (S=field squaring; M= field multiply), which is << 1% of
total cost and completely trivial.
>> > RS>> For a counter-example, please see my SAC 2010 paper on combined
key computations and signature verification. That paper illustrated that
the incremental cost of ECDSA signature verification would shrink
representations would block approaches, such as, e.g., those in that SAC
2010 paper, whereas using affine coordinates does not. Shouldn't
implementers be able to have some design freedom, if that would suit them?
(Esp. since speed has been touted as one of the triggers to consider new
curve forms?)
resp.
>> >>> d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77
03 7d
>> >>>>> * This proposal incurs 32 additional bytes of storage overhead for
the
these
>> >>>> They are in turn: RSA (2048 bit), 65 byte long nistp256 key and 32
byte
>> >>>> An example that does not have the alternative of using fingerprints
are
cryptography

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 13 Mar 2015 10:46:01 -0700

>   - (x,y)  -> bandwidth waste Montogmery ladder implementations

Is "wasting" of 32 extra per TLS/SSH session that important?

Considering average TLS session reuse rate today, this is 16 bytes per 
TLS session (and is likely to be fewer bytes than this).

---

From: Rene Struik <[email-masked]>
Date: Fri, 13 Mar 2015 14:10:06 -0400

As already said, one can have another series of emails on the impact of 
entirely speculative levels of sloppy behavior one attributes to 
implementations in one case but magically not in the other, as you seem 
to do, but - frankly - the CFRG email archive is already bursting out of 
its seams with emails repeating the same refrain (which I mentioned in 
my note below as "leading nowhere").

Moreover, it is entirely orthogonal to the succinct points I made.

{Apologies to others on the CFRG mailing list for having to state the 
first sentence above.}

==

On 3/13/2015 1:43 PM, Watson Ladd wrote:
>
>
> On Mar 13, 2015 10:34 AM, "Rene Struik" <[email-masked] 
> > I do not want this exchange to take ad infinitum, since I think I 
> made my point.
> >
> Any attack requiring cooperation of one side doesn't count. A protocol 
> that properly hashes transcripts doesn't have the problem with zero 
> keys that TLS does. But there is no similar protection for missing 
> validation.
> >
> > Rene
> > ==
> >
> >> >> On Fri, Mar 13, 2015 at 7:50 AM, Rene Struik 
> <[email-masked] <mailto:[email-masked]>> wrote:
> >> >>>
> >> >>> Hi Jakob:
> >> >>>
> >> > ii) those implementers that do wish to use a different method can 
> do so, without the need to perform point decompression. They could 
> also carry out point validation, at cost of roughly 2S+M for 
> Montgomery curves with small 'A' value (S=field squaring; M= field 
> multiply), which is << 1% of total cost and completely trivial.
> >>
> >> The consequences of getting the identity are minor. The 
> consequences of accepting points of small order are loss of the 
> private key.
> >>
> >> >
> >> > RS>> For a counter-example, please see my SAC 2010 paper on 
> combined key computations and signature verification. That paper 
> illustrated that the incremental cost of ECDSA signature verification 
> would shrink considerably when combined with ECDH key computation, 
> rather than when executed separately. See, e.g.,

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 13 Mar 2015 11:39:37 -0700

So, here is my view on this.

For ECDH, it is strongly preferable to have x-only output, so that the Montgomery ladder works.  It is also preferable if the ECDH ephemerals can be produced by the Montgomery ladder with minimal or no modification, because that reduces code size for embedded applications.  The fastest and simplest ECDH variable-base implementations will use the Montgomery ladder, so sending the y-coordinate is a waste.  Therefore, there’s a big advantage to x-only or x+sign for the wire format.

Between x-only and x+sign, there’s very little difference for ECDH.  The sign takes an extra bit (+0 bytes for Curve25519 and +1byte for Goldilocks).  If a sign bit is required, Montgomery ladder ECDH-only implementations can set it arbitrarily (eg, to 0).  If the bit is omitted, non-Montgomery implementations can choose it arbitrarily, since it doesn’t affect the shared secret.

For non-ECDH, x-only is insufficient, and most systems will need to decompress points if they’re compressed.  There’s very little security or performance difference between the two options: compression prevents some attacks but adds complexity; it saves time and energy on radio links but costs time and energy on wired ones or when the point is cached.  I prefer compressed points, but I admit that this is largely for aesthetic reasons.

However, if we choose x+sign then we can use it for both point formats.  That’s a big enough deal to make me prefer it.

It is also possible to use an implicit sign bit, eg “y/x is always positive” (positive meaning even, or maybe less than p/2).  This can be done with Andrey Jivsov’s trick of negating the secret key if y/x is not positive.  But that doesn’t work as a wire format for eg PAKE or MQV.  A more general solution is to invert x if y isn’t positive (the decaf trick), since (x,y) -> (1/x,-y/x^2) is the 2-torsion action and negates y/x.

As with x+sign, this implicit sign bit would not be used in the Montgomery ladder’s output, so it would affect only signatures and the like.  The advantage of implicit sign bit is that it gives all EC points the same format as the Montgomery ladder for very little cost.

— Mike

> On Mar 13, 2015, at 10:46 AM, Andrey Jivsov <[email-masked]> wrote:
> 
> Considering average TLS session reuse rate today, this is 16 bytes per TLS session (and is likely to be fewer bytes than this).
> 
>>

---

From: "Salz, Rich" <[email-masked]>
Date: Fri, 13 Mar 2015 19:08:13 +0000

> Considering average TLS session reuse rate today, this is 16 bytes per TLS
> session (and is likely to be fewer bytes than this).

Given OPTLS, it's likely to be twice that savings.

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 13 Mar 2015 13:50:51 -0700

When proposing uncompressed form of a point I recognize that diverse 
applications have opposite requirements regarding storage/computational 
efficiency. One way to come closer to pleasing everybody is the following:

* CFRG defines the canonical point representation as (u,v) u in 
Montgomery form, v=SQRT(u^3 + 486662*u^2 + u). (v might be in any other 
form to avoid the SQRT for the recipient.) This is a 64 byte octet 
string, always padded, on the wire.

* Define the compressed version as u, done with e.g. memcpy( dest_u, 
src_uv, is_compressed ? 32 : 64 ). In other words, the compression is 
done by the non-crypto code. This is easy for ECDH applications. For 
non-ECDH -- use "my trick" (in public domain since 2013 whatever I 
"invented", if any), or don't adopt the compressed form.

With this approach the support for compression and uncompressed input 
doesn't require changes to existing single-format APIs. The compression 
is trivially done outside of crypto API. The decompression is handled by 
the existing API (presumably by an import function), which knows that if 
the input is 32 bytes -- the (non-Montgomery) implementation will need 
to recover the second half, otherwise, it is importing a point in 
canonical representation.

* Each protocol selects a single format: either (u) or (u,v). I believe 
TLS/PKI should do (u,v). Storage security, esp. cases of encrypting to 
multiple recipients, bandwidth-constrained or memory-constrained 
applications, or keys entered by humans will prefer (u).

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 13 Mar 2015 15:26:42 -0700

I just realized that this is attached to a poll which supposedly just ended.  That said, does anyone want to change their input to the poll?

I personally am still happy with Montgomery u for ECDH.  For non-ECDH, we can discuss further since that’s not what the poll is about, but I still prefer u with an implicit or explicit sign bit.

— Mike

PS: In my earlier email with implicit sign bit, I wrote “invert x if y isn’t positive” which of course should be “invert x if y/x isn’t positive”.

> On Mar 13, 2015, at 1:50 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> When proposing uncompressed form of a point I recognize that diverse applications have opposite requirements regarding storage/computational efficiency. One way to come closer to pleasing everybody is the following:
> 
> * CFRG defines the canonical point representation as (u,v) u in Montgomery form, v=SQRT(u^3 + 486662*u^2 + u). (v might be in any other form to avoid the SQRT for the recipient.) This is a 64 byte octet string, always padded, on the wire.
> 
> * Define the compressed version as u, done with e.g. memcpy( dest_u, src_uv, is_compressed ? 32 : 64 ). In other words, the compression is done by the non-crypto code. This is easy for ECDH applications. For non-ECDH -- use "my trick" (in public domain since 2013 whatever I "invented", if any), or don't adopt the compressed form.
> 
> With this approach the support for compression and uncompressed input doesn't require changes to existing single-format APIs. The compression is trivially done outside of crypto API. The decompression is handled by the existing API (presumably by an import function), which knows that if the input is 32 bytes -- the (non-Montgomery) implementation will need to recover the second half, otherwise, it is importing a point in canonical representation.
> 
> * Each protocol selects a single format: either (u) or (u,v). I believe TLS/PKI should do (u,v). Storage security, esp. cases of encrypting to multiple recipients, bandwidth-constrained or memory-constrained applications, or keys entered by humans will prefer (u).

---

From: "D. J. Bernstein" <[email-masked]>
Date: 16 Mar 2015 00:22:55 -0000

One of the OpenSSL security fixes this year was correcting a bug in
point validation. The bug is estimated to allow more than 2^192 bogus
(x,y) pairs for NIST P-256, and presumably a few of those have order
below 2^66. Finding these medium-order points is an open problem for the
moment, but anyone who _can_ find them can use an active invalid-point
attack to break Microsoft's two-hour ECDH keys with <2^70 computations,
and thus to decrypt all other connections made during that two-hour
period. (The computations don't have to finish within the two hours.
Maybe this work can even be shared across multiple ECDH keys; I'd have
to look at other protocol details to figure this out.)

How many years did it take for this bug to be found in a very widely
used cryptographic library? Who's reviewing all the other NIST P-256
implementations to see whether they even _try_ to validate points, never
mind whether they get it right?

With the Montgomery ladder, the curve is reused in every step, and a bug
that corrupts computations will simply move to different points on the
same curve or its twist. Next-generation curves such as Curve25519
guarantee that _none_ of those points have dangerous orders. The fault
attack in

   https://www.di.ens.fr/~fouque/pub/fdtc08.pdf

worked only because it targeted old-fashioned curves that weren't
twist-secure, such as NIST P-224. With proper choices (twist-secure
curve, and scalar bits set accordingly) Montgomery-ladder ECDH doesn't
need _any_ input validation.

In particular, input 0 is handled correctly without any special tests,
contrary to Rene's comments and earlier comments from Microsoft. See
https://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html.

Here's another interesting data point regarding code simplicity. In
flipping through Microsoft's "constant-time" ECCLib_v1.1, I noticed

   temp = (scalar[0] & val1) - val2; // ki = (k mod 2^w)/2^(w-1)
   *digits = (int)temp;
   digits++;
   res = scalar[0] - temp;           // k = (k-ki)/2^(w-1)
   borrow = (temp > 0) & (scalar[0] < (unsigned int)temp);

inside the fixed_window_recode() function. The scalar is, apparently,
supplied by an attacker, and I would expect the compiler in most cases
to turn the comparisons into variable-time branches, leaking scalar bits
through timing---clearly violating the "constant-time" promise. With the
Montgomery ladder, the scalar bits are used in a much simpler way,
minimizing the number of opportunities to screw up the implementation.

> A sample of the interest in unified format can be found here:

You misunderstand. There are two different types of ECDH keygen code
available for X25519:

   * _simple_ key generators that use the Montgomery ladder;
   * _fast_ key generators that use precomputed Edwards points and
     convert the output to Montgomery format.

Both of these approaches produce identical Montgomery x-coordinates on
the wire. The fact that the fast implementations use Edwards internally
doesn't mean that all implementations want to do this (for most people
simplicity is more important than this extra burst of keygen speed) and
certainly doesn't mean that it's a good idea to use anything other than
Montgomery x on the wire for ECDH.

  [ send an extra coordinate v along with the Montgomery x ]
> An implementation that uses a Montgomery ladder simply ignores v

Well, yes, this is what any sensible ECDH receiver will do, so why waste
the network traffic? Meanwhile you're forcing the ECDH key generator to
compute v in the first place---a significant increase in the complexity
of the simplest (Montgomery ladder) keygen software.

> implement both signatures and ECDH

Switching from a "unified" format to Montgomery x for ECDH usually makes
this type of software _simpler_. The underlying issue is that there are
actually three different scalar-multiplication operations of interest:

   * double-scalar multiplication (signature verification);
   * fixed-base-point single-scalar multiplication (signing/keygen); and
   * variable-base-point single-scalar multiplication (ECDH).

For example, in Microsoft's library these are ECC_DBLMUL_TE,
ECC_MUL_FIXED_TE, and ECC_MUL_TE. Ripping all the ECDH-specific
functions out of the library (ECC_MUL_TE, fixed_window_recode, etc.),
and replacing them with a Montgomery ladder, would _simplify_ the code.

Furthermore, even if you can find a signature+ECDH library where a
"unified" format _reduces_ complexity rather than _increasing_ it, the
percentage saved will obviously be quite small---whereas sticking to
Montgomery x for ECDH saves a _much_ larger percentage of a pure ECDH
implementation.

> a single set of test vectors, code reuse, and the benefits of sharing
> pre-computed values

Every function needs its own test vectors in any case. Pre-computed
values are shared in any case. As for code reuse, see above.

> no (measurable) performance penalty

The extra network traffic is a measurable performance penalty, and is
more important than the CPU time saved for decompression inside
signature verification. See below.

Michael Hamburg writes:
  [ compression ]
> saves time and energy on radio links

Yes, obviously.

> but costs time and energy on wired ones

No.

Time: Curve25519 decompression takes roughly 5 microseconds on a typical
server CPU core, but this is less than the time that the core needs to
receive 256 bits from the Internet---unless you've bought a single
quad-core server to handle more than 200Mbps of Internet traffic; this
doesn't make economic sense.

Energy: 10 USD of electricity will pay for about 10 watt-years of this
125-watt quad-core CPU, i.e., a month of CPU time, i.e., 2000000000000
decompressions, saving 64 terabytes of Internet traffic---a month of
continuous traffic at 200Mbps, as above. Some ISPs do sell noticeable
fractions of 200Mbps for 10 USD/month, but that's because they know that
most users won't use the network anywhere near continuously.

> or when the point is cached

No. You pay _once_ to decompress a point the first time you use it, and
after that you cache the decompressed version. (I'm assuming that it's
cheaper for you to store the extra bytes than to recompute them; if not,
you should cache the compressed version.) Local caching doesn't affect
the performance impact of compression on the wire.

---Dan

---

From: Rene Struik <[email-masked]>
Date: Sun, 15 Mar 2015 23:53:34 -0400

Hi Dan:

All fair, and interesting anecdotical reading, but entirely orthogonal 
to the technical discussion at hand.

If one sends points in affine format, this does not preclude any 
recipient to still discard the y-coordinate and carrying out 
x-coordinate-only arithmetic (as you seem to advocate, as the *only* 
choice). What it *does* allow, though, is *freedom of choice* for 
implementers, instead of depriving people this freedom ("Ein Diktat", if 
one wishes). This freedom of choice is what some people seem to be 
advocating (including me) and which you seem to abhor. I try and fail to 
understand why this is.

One should not give the false impression that anything but Montgomery 
arithmetic is error- and security-vulnerability prone. Why not sticking 
to the point?

It is not easy to distill the technical point relevant to the question 
at hand from your email.

I think it would still serve the community to make a concise (say, one 
short para of no more than 150 words) *technical* argument (without 
jabs, etc.).

Best regards, Rene

[excerpt of my email of Fri March 13, 2015, 10.50am EDT]
I fully agree with Andrey Jivsov's point and think using x-coordinate 
only representations imposes a "moat" around ECC implementations, by 
imposing a levy on all implementations that, for whatever reason, may 
want to use something else than Montgomery arithmetic.

Best regards, Rene

---

From: Rene Struik <[email-masked]>
Date: Mon, 16 Mar 2015 00:09:22 -0400

Hi Dan:

It seems you confuse the sender and recipient side here: on the sender's side, the incremental cost of computing an affine point representation from an x-coordinate-only one is quite insignificant, whereas, indeed, on the recipient's side, this incremental cost is quite high. Hence, the entire discussion.

Rene

[excerpt of email Dan Bernstein as of Sun March 15, 2015, 8.22pm EDT]

Meanwhile you're forcing the ECDH key generator to
compute v in the first place---a significant increase in the complexity
of the simplest (Montgomery ladder) keygen software.

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 15 Mar 2015 21:44:32 -0700

Rene,

Dan’s technical point is that except in the most network-glutted environments (maybe a datacenter LAN), it’s essentially always cheaper in both time and energy and money to compute v on the recipient’s side instead of sending it, if you aren’t using the Montgomery ladder.  Furthermore it doesn’t add much complexity to compute on the recipient’s side.  And if you are using the Montgomery ladder — which saves complexity instead of adding it — then sending the extra coordinate is an utter waste.

Dan,

I’m not convinced that the Montgomery ladder is automatically safe from fault attacks on a twist-secure curve.  The ladder’s internal state has an invariant, that P+Q=R.  If that condition is violated, you could end up somewhere different.  The ladder does use the curve constant at every step, but I’m not sure that automatically gives immunity.  But it does make the attacker’s job harder.

— Mike

> On Mar 15, 2015, at 9:09 PM, Rene Struik <[email-masked]> wrote:
> 
> Hi Dan:
>

---

From: Viktor Dukhovni <[email-masked]>
Date: Mon, 16 Mar 2015 04:49:06 +0000

> https://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html.

Dan, thanks for the detailed comments.  I support the emphasis on
implementation simplicity they represent (including potentially
taking away choices, when such choices are more prone to mistakes
than "the right way").  That is, I suport removing inessential
degrees of freedom.

One quick question.  I did not think that Rene was saying that the
Montgomery ladder computes multiples of 0 incorrectly.  Rather,
the concern is I believe that when one of the parties to an ECDH
agreement sends zero as their public key, the output is then zero
regardless of the public key of the other party.

This may allow an attacker to force a given session key, depending
on how the ECDH output is used to construct session keys (whether
additional nonces are used.  Can you comment on situations (in
higher level protocols) under which participants in ECDH might want
to explicitly reject 0 as the peer's public key?  (I don't know
whether any protocols in wide use that employ ECDH are potentially
exposed to this issue, if it is an issue.)

If I recall correctly, with X25519, such a key will never arise if
both peers choose their secret keys per the specification (the
private "exponent" is never 0, and I think it is always smaller
than the order of the group).

-- 
	Viktor.

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 15 Mar 2015 22:26:52 -0700

> mind whether they get it right?

Don, are you referring to the 
https://www.openssl.org/news/secadv_20150108.txt

CVE-2014-3570 "1/2^64 on the single affected 32-bit platform (MIPS) and
1/2^128 on affected 64-bit platforms", "No exploits are known and straightforward bug attacks fail" ?

I read it as that this doesn't apply to 32 bit x86, and ignoring MIPS, this 1/2^128 for 64 bit
  without a known exploit (because the bug was at the very low level).

> Montgomery x on the wire for ECDH.

I like the _fast_ choice above. Most people will use libraries and I 
think it will make sense for a library to implement the _fast_ method 
for keygen. OpenSSL has already made this distinction for ECC: its P-256 
ECDSA is faster than its variable-base ECDH. When we get to using 
signatures with Curve25519, the speed of keygen benefits the speed of 
signatures on the server (e.g. a TLS server). Signers cannot reuse 
ephemeral keys and thus have the performance incentive to justify more 
complexity, following the OpenSSL model; likewise, signature 
verification needs point additions and can't use Montgomery. When a 
library has _fast_ keygen for signatures, it's logical to also use this 
code for ECDHE key generation. Having fast ECDHE key generation removes 
the necessity to reuse the ephemeral key pair, which promotes higher 
security and gives simplicity of no cache. Command-line applications, 
sandboxed code like JavaScript, etc typically cannot or should not cache 
ephemeral keys, and so _fast_ keygen is beneficial to e.g. 'openpgp-cmd 
--encrypt recipient -o file_out.pgp file_in.txt'.

In my proposal the v, the second coordinate, is only sent in the first 
flight (or a part of the public key in general). That's where we can 
expect that the Montgomery ladder will be less common. The second 
flight, the shared secret calculation, doesn't use v and thus there is 
no change to the Montgomery ladder.

> of the simplest (Montgomery ladder) keygen software.

The main rationale is that this allows more implementation choices. The 
past research on ECC optimizations was counting on the ability to add 
points. If the recipient must decompress, this works as 10% toll on 
present and future improvements.

For what it's worth, I added the calculation of v at the end of 
Montgomery ladder this weekend to curve25519-donna tree. The diff is: 
https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4 
.

The diff includes point validation, which is presently not invoked (or 
needed). The v is not serialized, but otherwise the pair of coordinates 
(u,v) is properly computed. The sign of u is not calculated here (let's 
say this is a ECDH case). Most of this work is copy and modify of the 
existing code based on "High-speed high-security signatures" sec 5. I 
had to solve the chicken-and-egg problem of calculating u=x/z and v = 
SQRT(u^3 + 486662*u^2 + u) in one pass (and there may be a faster way to 
do this?).

The performance penalty to calculate v is 3.0% (e.g. 14050/13660 op/sec 
on an 3.30GHz Ivy bridge x86_64).

> Montgomery x for ECDH saves a _much_ larger percentage of a pure ECDH

If a particular application must optimize code and data size, it should 
use the Montgomery ladder. There are many applications for which code 
size of the public key crypto is at the bottom of the priority list.

> doesn't make economic sense.

Each 32 bytes arrive every 1/((200*10^6/8)/32) = 0.00000128 seconds 
(every 1.2 microsec on 200 Mbps). While we seem OK with the *whole* 
quad-code CPU, the CPU is a precious resource on a busy server (so in 
reality we are not OK in this scenario). Why pay 10% penalty?

If we look at https://tools.ietf.org/html/rfc5246#section-6.2.1, the 
World is wasting 2 bytes per each

2^14 bytes of traffic in the best case scenario. There is also some waste in 4K handshake and block cipher padding that could be eliminated.

> the performance impact of compression on the wire.

This means that the crypto doesn't work as a blackbox anymore and 
requires dependency on caches.

Applying this to TLS, I came up with the following "decompressed cache" 
scenario. A Web browser is caching the server-cert issuing leaf CA 
public signing key, with the idea that this key will be used often to 
sign multiple Web server certs. This doesn't cover other cases like ECDH 
non-Montgomery, CRLs, and CA validation will cache the whole cert 
status. Out "decompression cache" doesn't avoid the first hit. It's 
interesting to see if such caching will be beneficial in practice. 
Bloated  caches may cause a slowdown.

Also please note that helping a receiver avoid 10% performance penalty 
lowers the latency.

Thank you.

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 16 Mar 2015 06:49:31 +0000

On 2015-03-16 05:26, Andrey Jivsov wrote:

> …without a known exploit (because the bug was at the very low 
> level).

Just because we got luckier this time, doesn't mean we will every time.

> I like the _fast_ choice above. Most people will use libraries

Bugs happen in libraries like OpenSSL or SChannel too. (And no, not
everyone does, look at the prevalance of RC4.)

> The main rationale is that this allows more implementation
> choices. The past research on ECC optimizations was counting on the
> ability to add points. If the recipient must decompress, this works
> as 10% toll on present and future improvements.

If it isn't at least as fast as that, why sacrifice the simplicity?

> If a particular application must optimize code and data size, it 
> should use the Montgomery ladder. There are many applications for 
> which code size of the public key crypto is at the bottom of the 
> priority list.

Simple code (and hardware) is easier to audit. That's why simplicity
was at the top of our original requirements list. It should stay there.

I'm clear I want to stick with the existing Montgomery-X wire format for
ECDH.

Changing that in any way harms simplicity, introduces interoperability
problems with the many existing implementations of X25519, and doesn't
bring any significant benefit to performance.

- -- 
/akr

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 15 Mar 2015 23:50:28 -0700

> On Mar 15, 2015, at 10:26 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> In my proposal the v, the second coordinate, is only sent in the first flight (or a part of the public key in general). That's where we can expect that the Montgomery ladder will be less common. The second flight, the shared secret calculation, doesn't use v and thus there is no change to the Montgomery ladder.

> Each 32 bytes arrive every 1/((200*10^6/8)/32) = 0.00000128 seconds (every 1.2 microsec on 200 Mbps). While we seem OK with the *whole* quad-code CPU, the CPU is a precious resource on a busy server (so in reality we are not OK in this scenario). Why pay 10% penalty?
> 
> If we look at https://tools.ietf.org/html/rfc5246#section-6.2.1, the World is wasting 2 bytes per each 

I understand that there are implementations out there other than the Montgomery ladder, and they
require more compute time if you don’t send a v coordinate.  It may be worth discussing further
whether the communication cost to send v is more or less than the cost for the recipient to compute
it, though I still expect that in most cases it is cheaper to recompute v.

But this just doesn’t make sense for ECDH.  You want to force *every* implementation, of
which the considerable majority will probably be the Montgomery ladder, to send and receive an
32 extra bytes.  You want to add non-negligible extra complexity to the simplest implementations
(IOT) to make this happen.  You want this so that a small (and so far hypothetical) minority of
implementations can make a tradeoff of compute time vs communication that *still* might be
unfavorable.  I just don’t see how this adds up.

Cheers,
— Mike

PS: If you think it’s good to add 32 bytes to public keys to speed up signature verification, please
consider the following proposal.  Instead of adding a second coordinate, add the u coordinate
of 2^128 * P and a sign bit.

Compared to your proposed algorithm, this u coordinate saves 128 doublings (~~ 128*6.2 M in
extensible or extended+Hisil’s lookhaead coordinates) at the cost of an extra decompression
(~256*0.9 M), an extra wNAF table precomputation (~8*8M), and an extra fixed table for g,
with a net savings of about 499M.  That’s more than double what the v-coordinate saves, and
almost the same math works for Ed448.

I don’t actually want to do this.  I’m just pointing out that “we should always trade space for time”
is a silly argument, and if you buy it then there are better ways to do it.

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 16 Mar 2015 01:04:43 -0700

> unfavorable.  I just don’t see how this adds up.

The protocols that cannot afford a few additional lines of code like in 
the diff 
https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4 
might standardize on u only ( as I wrote in 
http://www.ietf.org/mail-archive/web/cfrg/current/msg06480.html ). I 
would like to hear more about these protocols, though.

On the Internet in general (YouTube, Netflix streaming) and TLS in 
particular, it's hard to see that ~32 bytes per (not reused) handshake 
matter. This part of the Internet is currently using uncompressed points 
and RSA.

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 16 Mar 2015 09:00:30 +0000

On 16 March 2015 08:04:43 GMT+00:00, Andrey Jivsov <[email-masked]> wrote:

> […] TLS […] is currently using uncompressed points…

…and the TLS WG already declared consensus on removing those uncompressed ECC point formats for TLS 1.3.

We can specify whatever we want per-algorithm (opaque octet strings; we don't have to, and probably shouldn't, use the same point format for ECDH and signatures).

But if our recommendations took the opposite path of their consensus, required complicating changes to simpler, more-easily-auditable existing implementations, and potentially allowed for implementation fingerprinting, without a very, very good reason - that I don't feel you have - then I feel they could be quite poorly-received.

- --
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 16 Mar 2015 14:34:42 +0200

> exposed to this issue, if it is an issue.)

TLS 1.0-1.2 without extended_master_secret extension (which isn't
permaallocated yet) is affected. Fixed in TLS 1.3 draft.

Known Effects:
- Breaks TLS-Exporter, which breaks authentication in some
  applications.
- Breaks TLS-Unique if affected session is resumed, which breaks
  authentication in some applications.
- Allows data injection if affected session is resumed and then
  renegoitated.

Workarounds:
- RSA key exchange: No workarounds available.
- DHE key exchange: Workarounds not practical (primaility-proving
  is too slow).
- named-ffDHE (not standardized): Check for +-1 (MUST check in I-D)
- ECDHE key exchange: Check for low-order point or zero/inf shared.

> than the order of the group).

Correct, the case can't arise if both peers choose their keys to
the spec.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Mon, 16 Mar 2015 09:08:11 -0400

Hi Viktor:

You are correct: I have no idea where Dan Bernstein got that from. I *did* comment on the DH function, which, with Montgomery-style specification as in the "Curve25519" draft, is completely insecure, if one does not check the output to be nonzero. This is a form of the small subgroup attack and has been known for over 15 years.

BTW - I don't think this is properly captured in draft-irtf-cfrg-curves-01 and sent an offline note to suggest remedying this by replacing the last para prior to Section 8.1 of that draft to the following:

"Note that the (co-factor) Diffie-Hellman protocol presented here results in the all-zero key if it operates on an input corresponding to a point with order dividing the co-factor h of the curve. Failure to check the output for this condition leads to a trivial (and well-known) small subgroup confinement attack. The output of this protocol SHALL therefore be checked and, if this value is found to be zero, the protocol SHALL fail."

===

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 16 Mar 2015 15:32:17 +0200

On Mon, Mar 16, 2015 at 09:08:11AM -0400, Rene Struik wrote:
> Hi Viktor:
> 
> I *did* comment on the DH function, which, with Montgomery-style
> specification as in the "Curve25519" draft, is completely insecure,
> if one does not check the output to be nonzero.

Just hashing in the exchange keys is enough, and every protocol
should do this, except some do not (*cough* TLS *cough*).

SSH does hash the exchange keys and thus can't be attacked via
small subgroups, even if implementation doesn't check.

Also, It gets even worse with finite-field DH, since if arbitrary
fields are allowed, there is no realistic way to check, and even
if fields are fixed, there are small subgroups.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Mon, 16 Mar 2015 09:38:41 -0400

Hi Ilara:

I do not understand this: if one uses k=H(X,Y,K), where X is one's own 
key contribution, where Y is the received one, where K the computed DH 
key using the Curve25519 function, and where H is a hash function, then 
taking for Y a point of order dividing the co-factor h=8 of the curve 
results in key K=0 and k=H(X,Y,0), .e., it is publicly computable.

Could you explain what you meant (or send some emergency morning coffee 
supplies)?

Best regards, Rene

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 16 Mar 2015 15:48:07 +0200

On Mon, Mar 16, 2015 at 09:38:41AM -0400, Rene Struik wrote:
> Hi Ilara:
> 
> I do not understand this: if one uses k=H(X,Y,K), where X is one's own key
> contribution, where Y is the received one, where K the computed DH key using
> the Curve25519 function, and where H is a hash function, then taking for Y a
> point of order dividing the co-factor h=8 of the curve results in key K=0
> and k=H(X,Y,0), .e., it is publicly computable.
> 

Yes, but authentication will fail (if no authentication is done, one can
just do classic MITM against Diffie-Hellman, no need to mess with small
subgroups).

-Ilari

---

From: Viktor Dukhovni <[email-masked]>
Date: Mon, 16 Mar 2015 13:56:20 +0000

On Mon, Mar 16, 2015 at 09:08:11AM -0400, Rene Struik wrote:

> You are correct: I have no idea where Dan Bernstein got that from. I *did*
> comment on the DH function, which, with Montgomery-style specification as
> in the "Curve25519" draft, is completely insecure, if one does not check
> the output to be nonzero. This is a form of the small subgroup attack and
> has been known for over 15 years.

But in this case the "attack" does not leak any secret key bits
from either party.  So depending on the higher level protocol there
may not be any issues, provided such an agreement between M and B
does not enable M to impersonate B in a communication between A
and B.

I gather then that this is the issue, and that such higher level
protocols should reject the zero public key (or avoid the problem
by ensuring that predictable ECDH output cannot lead to MiTM issues
on other traffic).

-- 
	Viktor.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 16 Mar 2015 07:14:15 -0700

>>> In my proposal the v, the second coordinate, is only sent in the first
flight (or a part of the public key in general). That's where we can expect
that the Montgomery ladder will be less common. The second flight, the
shared secret calculation, doesn't use v and thus there is no change to the
Montgomery ladder.
>>> 2^14 bytes of traffic in the best case scenario. There is also some
waste in 4K handshake and block cipher padding that could be eliminated.
the diff
https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4
might standardize on u only ( as I wrote in
http://www.ietf.org/mail-archive/web/cfrg/current/msg06480.html ). I would
like to hear more about these protocols, though.

Your patch is not computing the correct sign bit.

Why is having an alternative ECDH algorithm so important?  It's not any
faster, or easier to test, or simpler. The alternative implementations you
are suggesting are less secure and less fast.

---

From: Rene Struik <[email-masked]>
Date: Mon, 16 Mar 2015 10:58:08 -0400

Hi Viktor:

The key words in your email are "depending on", which does suggest that 
protocol analysis may become quite unwieldy and error-prone itself.

For some examples of authenticated key agreement schemes that are 
supposedly secure against, e.g., the unknown key share attack, but where 
this does not seem to hold any more if the DH key is publicly 
computable, see, e.g.,

    Alfred Menezes, Simon Blake-Wilson,
    Unknown Key Share Attacks Against the Station-to-Station (STS)
    Protocol,
    PKC 1999.

This suggests that what you seem to dismiss as an "attack", may indeed 
be one (i.e., one without your quotation marks).

Rene

---

From: Watson Ladd <[email-masked]>
Date: Mon, 16 Mar 2015 08:39:06 -0700

On Mon, Mar 16, 2015 at 7:58 AM, Rene Struik <[email-masked]> wrote:
> For some examples of authenticated key agreement schemes that are supposedly
> secure against, e.g., the unknown key share attack, but where this does not
> seem to hold any more if the DH key is publicly computable, see, e.g.,
>
> Unknown Key Share Attacks Against the Station-to-Station (STS) Protocol,
> PKC 1999.
>
> This suggests that what you seem to dismiss as an "attack", may indeed be
> one (i.e., one without your quotation marks).

No, the protocol analysis is very simple. If you hash the transcript
with the shared secret, and use that as the key, you never have to
worry about contributory behavior. Even if an attacker dictates the
computed key, that key will never match one computed by an honest
participant. The problem is this needs to include all messages sent
before the key is established. Most protocols do this and don't
require contributory behavior.

This is a standard technique for simplifying security analysis. Of
course, we've always described what's required to ensure contributory
behavior in Curve25519, and it's always the case that implementors
should know what the protocol requires as far as assuring contributory
behavior, namely rejecting 8 inputs. TLS is really the odd man out in
requiring contributory behavior.

But let's assume that we need contributory behavior. Then simply
returning an ignorable error code doesn't work. Instead the function
should return 32 random bytes if computing 0, so as to avoid ignoring
the errors.

Sincerely,
Watson Ladd

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 16 Mar 2015 10:10:07 -0700

> On Mar 16, 2015, at 1:04 AM, Andrey Jivsov <[email-masked]> wrote:
> 
> The protocols that cannot afford a few additional lines of code like in the diff https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4 might standardize on u only ( as I wrote in http://www.ietf.org/mail-archive/web/cfrg/current/msg06480.html ). I would like to hear more about these protocols, though.

Maybe this doesn’t exist in the use cases of TLS, even though IoT devices can be pretty limited.

I work in the deeply embedded space, where every byte of code or data costs something.  At some point I wrote NIST p256 math and point add, double, and isqrt in 600 bytes of code.  We ended up not needing it for that project but we are likely to need something similar for the next one.  It was isqrt instead of inverse so that we could decompress points, because even with code limitations we couldn’t afford to store public keys uncompressed in NVM.  The bandwidth wasn’t a problem in that project, though.

> On the Internet in general (YouTube, Netflix streaming) and TLS in particular, it's hard to see that ~32 bytes per (not reused) handshake matter. This part of the Internet is currently using uncompressed points and RSA.

I agree that we’re arguing over minutiae, but I’m not satisfied with “wasting 32 bytes for no clear purpose is a good idea because other people waste bytes too”.

— Mike

---

From: Nico Williams <[email-masked]>
Date: Mon, 16 Mar 2015 15:30:27 -0500

On Mon, Mar 16, 2015 at 01:04:43AM -0700, Andrey Jivsov wrote:
> The protocols that cannot afford a few additional lines of code like
> in the diff https://github.com/brainhub/curve25519-donna/commit/abc601836b75ba6399c775842647e0f3b66061c4
> particular, it's hard to see that ~32 bytes per (not reused)
> handshake matter. This part of the Internet is currently using
> uncompressed points and RSA.

If all the protocol is going to do with ECC is ECDH with ephemeral keys,
then no, there's no point at all to doing anything other than x-only.

For ECDH-only, x-only will do, always.  It's only when combining with
other primitives using the same ECC key that there's any need or win to
using more than x-only.  If that's desired, then define a (here: X25519)
curve's public key representation as: x-only for ECDH-only, and some
other form for the other cases.

Nico
--

---

From: David Leon Gil <[email-masked]>
Date: Mon, 16 Mar 2015 15:08:38 -0700

On Monday, March 16, 2015, Watson Ladd <[email-masked]> wrote:

> On Mon, Mar 16, 2015 at 7:58 AM, Rene Struik <[email-masked]
> <javascript:;>> wrote:
>

I'm really inclined to think that it is better to use an encoding format
that rejects points that do not ensure contributory behavior. I don't think
that it's wise to assume that protocol designers will understand when
this is required as well as you do.

(Indeed, I'm unaware of any Curve25519 implementation that checks for this
at present...)

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 17 Mar 2015 00:48:10 +0000

On Mon, Mar 16, 2015 at 08:39:06AM -0700, Watson Ladd wrote:

> Of course, we've always described what's required to ensure contributory

If I recall correctly it is simpler to reject the corresponding
single output (namely 0) than the 8 inputs that map to zero.
Admittedly my memory of the details is a bit fuzzy on this...

Since the output is sensitive, all one has to do is a constant-time
memcmp of the output with a 256-bit zero.

Does TLS need to defend against this?  It is not obvious that it
does.

-- 
	Viktor.

---

From: Nico Williams <[email-masked]>
Date: Mon, 16 Mar 2015 22:33:56 -0500

> this is required as well as you do.

Don't the alternatives have harder input validation problems?

Having to check for just one weak public key, that seems like a good
deal to me.

Nico
--

---

From: CodesInChaos <[email-masked]>
Date: Tue, 17 Mar 2015 10:52:54 +0100

On Mon, Mar 16, 2015 at 4:39 PM, Watson Ladd <[email-masked]> wrote:
> Of
> behavior, namely rejecting 8 inputs.
What's a bit annoying is that the encoding of those inputs has changed
over time together with the interpretation of the MSB.

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 17 Mar 2015 16:00:17 +0000

> What's a bit annoying is that the encoding of those inputs has changed over
> time together with the interpretation of the MSB.

Really?  Perhaps there were some bugs in the X25519 drafts, but I do not think the wire format has ever changed.  Can you provide specifics and, ideally, links?

	/r$

---

From: Watson Ladd <[email-masked]>
Date: Tue, 17 Mar 2015 09:05:43 -0700

> Does TLS need to defend against this?  It is not obvious that it

Yes, it does. This is the Triple Handshake variation I posted to the
TLS list about some time ago. Of course, properly designed protocols
don't have these problems, and protocol designers who aren't capable
of determining if contributory behavior is required, and changing the
protocol so it isn't, probably shouldn't be trusted to design
protocols where these things matter.

Sincerely,
Watson Ladd

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 17 Mar 2015 18:12:04 +0200

On Tue, Mar 17, 2015 at 04:00:17PM +0000, Salz, Rich wrote:
> Really?  Perhaps there were some bugs in the X25519 drafts, but I do not
> think the wire format has ever changed.  Can you provide specifics and,
> ideally, links?

I guess this refers to interpretation of public keys with high bit set.

Some implementations (notably the original) don't ignore the high bit,
whereas newer stuff (and some implementations switched midway) ignore
the high bit.

This affects what octet sequences with high bit set represent public
keys with low order.

-Ilari

---

From: CodesInChaos <[email-masked]>
Date: Wed, 18 Mar 2015 17:33:48 +0100

In fact several implementations started by ignoring the bit, then in
an attempt to achieve consistency I convinced them to use the bit
(conforming to the original specification) and finally after some
discussion they changed back to ignoring it (since ignoring makes
embedding a sign bit easier).

Bernstein documents which inputs (bitstrings) you need to ignore to
achieve contributory behaviour at:

http://cr.yp.to/ecdh.html

But that documentation assumes that the high bit is used. So a
blacklist based on that documentation will accept some low order
points with many implementations.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 18 Mar 2015 09:38:04 -0700

> points with many implementations.

All to save one byte! Let this be a lesson for everyone. Anyway, checking
if zero comes out always works. Or don't use protocols that require
contributory behavior: I can't think of anything that absolutely does, as
in we always have alternative protocols.

Sincerely,
Watson Ladd

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 19 Mar 2015 18:21:07 +0000

Hi,
Chairs are apologizing for the delay in closing this discussion topic.

Thank you for constructive discussion of the topic.

> Montgomery form/coordinates without polling the group first.]
Based on answers received, chairs declare rough consensus on using 
"u"-only form for DH for both curves that will be recommended by CFRG to 
IETF. Chairs took the post-March 12 discussion into consideration.
Note that this format need not be adopted for signatures.

Best Regards,
Alexey, on behalf of chairs.