Subject: Re: [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)

From: Andrey Jivsov <[email-masked]>
Date: Tue, 11 Dec 2012 15:37:16 -0800

On 12/11/2012 03:15 PM, Peter Gutmann wrote:
> Andrey Jivsov <[email-masked]> writes:
>
>> I thought that it would be useful for the Internet community to have an IETF
>> document that describes how to encode an ECC point.
>
> Maybe I'm missing something here, but wouldn't this just consist of:
>
> -- Snip --
>
> See [1].
>
> [1] X9.62-2005, "Public Key Cryptography for the Financial Services Industry:
> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 2005.
>
> -- Snip --
>
> That's what every existing RFC that uses ECC seems to be using.
>
> Peter.
>

Hello Peter.

"X9.62-2005" in the search engine lends me on a page that asks for $100. 
I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is more 
popular as a reference (assuming they are identical regarding the point 
compression method).

I claim that what I submitted is better in many respects than SEC1.

Let me expand on one of the benefits not covered in the spec. It's very 
likely that an employee of a commercial company thinking about using 
[SEC1] compression with any ECC method would get an order from the legal 
department to stay away from compression. The fact that somebody on the 
Internet posted something to the contrary has little weight for them. My 
contribution is an attempt towards a compact representation that is 
actually usable in practice. It's the most direct extension to the 1985 
idea by [Miller] (see my document for details).

Thank you.

---

From: Rene Struik <[email-masked]>
Date: Wed, 12 Dec 2012 09:17:11 -0500

Hi Andrey:

One can already implement the x-coordinate only representation of an 
elliptic curve point simply by converting the affine representation into 
compressed representation and randomizing the compression "bit". The 
reverse operation then yields the point or its inverse (which have the 
same x-coordinate).

To my knowledge, this does not require any changes to data formatting 
(nor additional bytes).

Best regards,

Rene

On 12/11/2012 6:37 PM, Andrey Jivsov wrote:
> "X9.62-2005" in the search engine lends me on a page that asks for 
> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is 
> more popular as a reference (assuming they are identical regarding the 
> point compression method).
>
> Let me expand on one of the benefits not covered in the spec. It's 
> very likely that an employee of a commercial company thinking about 
> using [SEC1] compression with any ECC method would get an order from 
> the legal department to stay away from compression. The fact that 
> somebody on the Internet posted something to the contrary has little 
> weight for them. My contribution is an attempt towards a compact 
> representation that is actually usable in practice. It's the most 
> direct extension to the 1985 idea by [Miller] (see my document for 
> details).
>
> Thank you.
>
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

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

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 12 Dec 2012 11:02:41 -0800

I have the same comment as Scott, but I am not sure exactly what Rene 
means.

I will assume that Rene says that because there are two y for each x, 
one can calculate the corresponding y or p-y and choose one at random.

The format I proposed indeed fits very well with the feature of the 
ECDH-based  protocol that Scott refers to (which covers ECC encryption 
and key agreement). As the draft shows, one simply drops the y 
coordinate to obtain the compact representation, while there are no 
extra steps for ECDH key generation (because ECDH keys are not sensitive 
to maintaining the "right" y).

The extra key generation step is only needed for ECDSA keys.

On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote:
>
>
>> -----Original Message-----
>> From: [email-masked] [mailto:[email-masked]] On Behalf Of
>> Rene Struik
>> Sent: Wednesday, December 12, 2012 9:17 AM
>> To: Andrey Jivsov
>> Cc: [email-masked]; [email-masked]; Peter Gutmann
>> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
>> elliptic curve point (ECC point compression)
>>
>> Hi Andrey:
>>
>> reverse operation then yields the point or its inverse (which have the same
>> x-coordinate).
>>
>> To my knowledge, this does not require any changes to data formatting (nor
>> additional bytes).
>
> That randomization of the y-component works fine for ECDH (at least, if you use only the x-component of the shared secret); however, it doesn't work for ECDSA public keys.
>
>>
>> Best regards,
>>
>> Rene
>>
>>>>> I thought that it would be useful for the Internet community to have
>>>>> an IETF document that describes how to encode an ECC point.
>>>>
>> Cfrg mailing list
>> [email-masked]
>> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Rene Struik <[email-masked]>
Date: Wed, 12 Dec 2012 14:22:57 -0500

Hi Andrey:

I just wanted to understand the problem one tries to solve. My simple 
suggestion was aimed at realizing the same effect.

[I had a short offline exchange with Scott Fluhrer on this, including on 
the ECDSA verification angle - summarized by the sentence below]

In most common implementations, ECDSA signature verification cost is 
roughly the same, no matter whether one know the y-coordinate of the 
signature verification key or not.

Given this, it seems that for ECDSA signature verification and ECDH the 
argument for yet another construct seems to be somewhat weak: my simple 
suggestion would also work, does not require new formatting, or 
transition periods (and, to my knowledge, does not read on any 
"nontechnical issues").

I hope this helps.

Best regards, Rene

On 12/12/2012 2:02 PM, Andrey Jivsov wrote:
> extra steps for ECDH key generation (because ECDH keys are not 
> sensitive to maintaining the "right" y).
>
>> That randomization of the y-component works fine for ECDH (at least, 
>> if you use only the x-component of the shared secret); however, it 
>> doesn't work for ECDSA public keys.
>>
>>>
>>> Best regards,
>>>
>>> Rene
>>>

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 12 Dec 2012 12:51:10 -0800

On 12/12/2012 12:10 PM, Scott Fluhrer (sfluhrer) wrote:
>> From: Andrey Jivsov [mailto:[email-masked]]
>> Sent: Wednesday, December 12, 2012 2:03 PM
>> To: Scott Fluhrer (sfluhrer)
>> Cc: Rene Struik; [email-masked]; [email-masked]; Peter Gutmann
>> I will assume that Rene says that because there are two y for each x, one can
>> calculate the corresponding y or p-y and choose one at random.
>>
>> The format I proposed indeed fits very well with the feature of the ECDH-
>> based  protocol that Scott refers to (which covers ECC encryption and key
>> agreement). As the draft shows, one simply drops the y coordinate to obtain
>> the compact representation, while there are no extra steps for ECDH key
>> generation (because ECDH keys are not sensitive to maintaining the "right"
>> y).
>>
> Actually, as Rene pointed out to me privately, it isn't much more for ECDSA, at least with the standard algorithm.
>
> The ECDSA verification is a check whether r = (uG + vQ)_x, where Q is the public key.  If you are given only the x coordinate of Q, what you do is to pick a corresponding y coordinate (so you get a point S where either S=Q or S=-Q, where Q is the original public key), and check if one of these two holds:
>
> r = (uG + vS)_x
> r = (uG - vS)_x
>
> If either does, the signature verifies.  This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small.

Signature verification is a very common crypto operation (i.e. verifying 
the certificate chain, verifying e-mail signatures in the users's 
mailbox, etc).

It's important to optimize the format for most common operations.

Given that we always have to calculate -/+ y from x, I will ignore this 
cost in the rest of this message.

My proposal: no performance overhead for any operation with a public 
key. No storage overhead. Potentially will work with more than ECDH and 
  ECDSA because it restores the precise y.

Other proposals: at least one byte storage overhead, one point addition, 
IPR issues.

The seeming magic with my proposal happens because it shifts the cost or 
determining the bit of y into the the key generation stage. Key 
generation is an offline operation. Keys can be pre-generated even for 
ephemeral keys used for encryption. However, in most cases the only 
additional overhead that my proposal adds to generation is at most one 
F(p) subtraction (negligible to the cost of a single point addition).

Thank you.

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 12 Dec 2012 15:59:19 -0800

As a side note, I wonder how much the performance cost of decompression 
is a practical issue in protocols where ECC is used.

In summary, if I am to pick the defaults, I would say that the static 
keys should be uncompressed, while the messages encrypted to compressed 
ephemeral keys. Here is what I mean:

Let's look first at persistent data structures in various protocols.

Decompression applies to public keys. For signature verification it 
means static (v.s. ephemeral) keys, which can be decompressed and 
cached. The stated decompression cost is only an issue for corner cases 
when we are verifying a stream of short messages signed by random 
identities.

Consider an e-mail client application application (MUA), to be specific. 
Let's say the application is first loaded and it's verifying a large 
number of incoming e-mails. Many of them are likely to be from the same 
senders. It's likely that these are the same signers encountered in the 
past sessions. Thus, the keys could have been cached locally and it 
doesn't matter if compression is used for these keys. If the keys are 
unavailable (a case when the decompression cost cannot be amortized), 
they will be retrieved over the network from a key server. The network 
latency will dominate the cost of point decompression here. On the other 
hand, the saving is here only for the static public key.

It's more of an issue for decryption of messages, when ephemeral keys 
are used. Especially because the point compression provides the most 
benefits for encrypted messages, given that they are typically encrypted 
to N>1 recipients, thus there is at least N*33 byte space improvement 
(for P-256) and each key produces M messages over its lifetime. Is the 
performance a practical concern here v.s. a space saving of N*M*33 given 
that the message need to parsed and the content decrypted?

For online protocols with ephemeral keys, such as ephemeral ECDH in TLS, 
the point compression is probably not worth much.

The point compression is optional today throughout the standards and it 
makes sense to keep it optional.

On 12/12/2012 03:02 PM, William Whyte wrote:
> Hi Scott,
> The problem here is that the standard speedup for ECDSA doesn't
> calculate uG and vS independently, but calculates uG+vS as a single
> operation. This takes much less time than the separate operations -- I
> estimate about 69% of the time for openssl using the NIST p256 curve.
> So the cost of doing verification without knowing Q_y is actually a
> factor of close to 1.44, since you have to do the separate
> calculations instead of the combined one.
>
> Generating the y coordinate isn't necessarily a small cost; it can
> also be pretty expensive since it involves taking a square root mod a
> prime. Obviously this cost also applies if you use any form of
> y-coordinate compression as well as if you omit the y-coordinate, so
> it's not necessarily a cost delta depending on what you're comparing
> with.
>
> I've seen implementations in which decompression added 12% to the
> running time for verify with NIST p256 and 23% to the running time for
> verify with NIST p224; with openssl, last time I checked two years
> ago, decompression added 12% to the running time for verify with NIST
> p256 and 180% to the running time with NIST p224 because the
> decompression algorithm at the time was, er, not optimized. (We
> actually implemented an improved decompression algorithm for openssl
> that brings the overhead back down to around 23%, but haven't had time
> to release it back to the main source tree yet -- it's possible that
> the openssl team have already improved it themselves).
>
> Cheers,
>
> William
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Dec 2012 16:52:03 +0000

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Dec 2012 20:10:53 +0000

r = (uG + vS)_x
r = (uG - vS)_x

> >> From: [email-masked] [mailto:[email-masked]] On Behalf
> >> Of Rene Struik
> >> Subject: Re: [Cfrg] [saag] A proposal for compact representation of
> >> an elliptic curve point (ECC point compression)
> >>
> >> Hi Andrey:
> >>
> >> elliptic curve point simply by converting the affine representation
> >> into compressed representation and randomizing the compression "bit".
> >> The reverse operation then yields the point or its inverse (which
> >> have the same x-coordinate).
> >>
> > That randomization of the y-component works fine for ECDH (at least, if
> you use only the x-component of the shared secret); however, it doesn't
> work for ECDSA public keys.
> >
> >>
> >> Best regards,
> >>
> >> Rene
> >>
> >>>>> I thought that it would be useful for the Internet community to
> >>>>> have an IETF document that describes how to encode an ECC point.
> >>>>
> >>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1]
> >>> is more popular as a reference (assuming they are identical
> >>> regarding the point compression method).
> >>>

---

From: William Whyte <[email-masked]>
Date: Wed, 12 Dec 2012 18:02:17 -0500

Hi Scott,

Cheers,

William

---

From: Vadym Fedyukovych <[email-masked]>
Date: Thu, 13 Dec 2012 13:21:13 +0200

On Wed, Dec 12, 2012 at 08:10:53PM +0000, Scott Fluhrer (sfluhrer) wrote:
> [...]
> [...]

This looks like a non-trivial change of threat model to me.

There may be two different messages signed with such a signature.
To be practical, one would consider generating (well, calculating) a key
to fit any two pre-selected messages later.
"IOY amount/10" could be an example for a nice article in game theory.

> [...]

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 17 Dec 2012 13:32:02 -0800

> If either does, the signature verifies.  This adds the cost of a single point addition (and the cost of generating the y coordinate of S); fairly small.
...

As was pointed out to me privately, two public keys Q and -Q will both 
verify the same signature. Let me explore this point further.

One interesting side effect of this modification to ECDSA is that it's 
now possible to have two X.509 certificates with different identities 
that will both verify the same signed document. The subjectKeyIdentifier 
(SKI) will be different (so that keys will appear different at 
cryptographic material level too)

It's my understanding that SMIME/CMS doesn't include identity of the 
signer into the signed attributes (which are the message digest, date of 
signing, etc, but not the issuer+SN or SKI).

So, it will be then a "feature" of the new ECDSA that each principal can 
have up to two digital identities that the protocol cannot distinguish 
from at the cryptographic level. Speaking in terms of X.509 format, 
everybody is advised to get a pair of X.509 certificates issued from the 
legitimate CA (or CAs): the main one and the other one for the rainy day 
to claim limited repudiation. A principal will be able to show to court 
that by manually modifying the signed message the document in question 
will appear to be signed by another digital identity.

X.509 certificate certification looks fine from this point.

This leads us to the thought that the canonization of the point is a 
good thing, and my proposal or SEC1 don't leave that 1 bit of uncertainty.