Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Exchange

From: Andrey Jivsov <[email-masked]>
Date: Wed, 02 Jan 2013 23:07:00 -0800

Sorry for bringing up this so late, but I just noticed the discussion 
about the point compression in this thread.

I posted the "Compact representation of an elliptic curve point" 
http://tools.ietf.org/html/draft-jivsov-ecc-compact that I think is 
helpful as a generic definition of a compressed point.

I know that 
https://datatracker.ietf.org/doc/draft-merkle-ikev2-ke-brainpool/ -03 
moved away from the compressed representation, but the preceding 
discussion is one of the reasons why I created this draft. It's 
unfortunate that with current state of ECC at IETF there is always an 
uncertainty/complexity such as "do we use an uncompressed point or 
compressed point; and there is IPR". There is also an issue of what's 
hashed and how the {x,y} is encoded. In the end in practice this means 
that there is no compression used.

I want to add as an alternative point of view that for new features or 
protocols there is also a way to reduce complexity by using only the 
compact point representation, such as in 
http://tools.ietf.org/html/draft-jivsov-ecc-compact.

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 04 Jan 2013 13:10:00 +0100

Hi Andrey,

point compression has been deleted from the draft due to the strong objections in this WG. The possibility to choose
from two distinct encodings was considered inappropriate complexity given the limited benefit.

Generally, I think that your draft has its value, albeit probably not for IKE.

Some nits:
Line 256:
   Recall that the x is an integer in the underlying finite field.
should be
   Recall that the x is an element in the underlying finite field represented by an integer.
                           ^^^^^^^                                ^^^^^^^^^^^^^^^^^^^^^^^^^
Line 352:
   When p = 4*k+3, as is the case of [SuiteB] the Brainpool curves
should be
   When p = 3 mod 4, as is the case of [SuiteB] and the Brainpool curves
            ^^^^^^^                             ^^^
Remark: Writing p = 4*k+3 is unfortunate, as k has been used to denote the private key in Section 4.2

Section 5:
   First, key pairs must be generated as defined in Section 4.2 to allow
   compact representation.
But, as you have pointed out in Section 3:
   Some protocols, such as ECDH, don't depend on the exact value of
   the y.
Thus, in these protocols, it does not matter, if the key is "compliant" or not. This should be explained, not only in
Section 5 but also in the beginning of Section 4.2.

regards,
Johannes

Andrey Jivsov schrieb am 03.01.2013 08:07:
> Sorry for bringing up this so late, but I just noticed the discussion about the point compression in this thread.
> 
> I posted the "Compact representation of an elliptic curve point" http://tools.ietf.org/html/draft-jivsov-ecc-compact
> that I think is helpful as a generic definition of a compressed point.
> 
> I know that https://datatracker.ietf.org/doc/draft-merkle-ikev2-ke-brainpool/ -03 moved away from the compressed
> representation, but the preceding discussion is one of the reasons why I created this draft. It's unfortunate that with
> current state of ECC at IETF there is always an uncertainty/complexity such as "do we use an uncompressed point or
> compressed point; and there is IPR". There is also an issue of what's hashed and how the {x,y} is encoded. In the end in
> practice this means that there is no compression used.
> 
> I want to add as an alternative point of view that for new features or protocols there is also a way to reduce
> complexity by using only the compact point representation, such as in http://tools.ietf.org/html/draft-jivsov-ecc-compact.
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
> 
>

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 04 Jan 2013 12:23:43 -0800

Thank you, Johannes, for your comments. I will integrate them in the 
next revision.

I do agree that for online protocols like IKE and TLS the point 
compression of the ephemeral ECDH is not that beneficial.

Point compression is more beneficial for storage security for reasons of 
performance and storage efficiency. For storage efficiency side: when 
there are multiple recipients per message, each associated with one 
ECDH-related field, it's possible for ECDH-specific payload to get 
arbitrary large for a fixed short message. For the performance argument: 
if the message was encrypted to N recipients, to decode it only one 
recipient will be used, and thus the calculation of 'y' is done once but 
the space is saved for N.

Even for certificates that have one public key there is some benefit, 
given that the certificates are pre-precessed for chain validation and 
are often cached.

---

From: Stephen Kent <[email-masked]>
Date: Mon, 07 Jan 2013 10:52:08 -0500

On 1/4/13 3:23 PM, Andrey Jivsov wrote:
> ...
>
> Point compression is more beneficial for storage security for reasons 
> of performance and storage efficiency. For storage efficiency side: 
> when there are multiple recipients per message, each associated with 
> one ECDH-related field, it's possible for ECDH-specific payload to get 
> arbitrary large for a fixed short message. For the performance 
> argument: if the message was encrypted to N recipients, to decode it 
> only one recipient will be used, and thus the calculation of 'y' is 
> done once but the space is saved for N.
Are you confident that this attempt at space efficiency is consistent 
with S/MIME processing rules?
Or are you suggesting that S/MIME and other secure email standards 
become alg-specific to take
advantage of this optimization?
> given that the certificates are pre-precessed for chain validation and 
Most IETF security protocols make use of X.509 (PKIX) certs. X.509 certs 
always contain just one key.
So I'm puzzled by the phrase "Even for certificates that have one public 
key ..."

Steve

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 07 Jan 2013 10:31:16 -0800

> advantage of this optimization?

If you are asking if my proposal is compatible with the current format 
that IETF standards use, which is by and large is SEC1, then, no, my 
proposal is not binary identical to the SEC1. The issue of this 
interoperability is discussed in the spec.

While I believe that my proposal, which is written for modp curves, is 
superior to (modp subset of) SEC1, I realize that adding an alternative 
compact representation / point compression to existing standards is an 
uphill battle. For existing standards that define some point compression 
I would only say that if one finds that the point compression is not 
actually used / configured in real-world implementations, please take a 
look at my proposal as it may be a format that will eventually find its 
way into the implementations if standardized (IPR issues is one such a 
concern).

For any new format / protocol / feature, RFC 6090 + 
http://tools.ietf.org/html/draft-jivsov-ecc-compact should be a more 
natural path.

> So I'm puzzled by the phrase "Even for certificates that have one public

I agree that the statement was unclear. I was saying that because the 
certificates contain only one public key, the space saving is only 
size-of-the-curve+1 byte per certificate. Nonetheless, given that 
certificates need to be pre-processed and validated, and these results 
are often cached, the overhead of calculation of the 'y' is probably not 
material.

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 08 Jan 2013 11:21:57 +0100

Andrey,

>
> For any new format / protocol / feature, RFC 6090 + http://tools.ietf.org/html/draft-jivsov-ecc-compact should be a more
> natural path.

Well, RFC 6090 is not always a good reference, at least it is very unfortunate that the signature scheme KT-I is not
fully compatible with ECDSA (Errata 2777).

> I agree that the statement was unclear. I was saying that because the certificates contain only one public key, the
> space saving is only size-of-the-curve+1 byte per certificate. Nonetheless, given that certificates need to be
> pre-processed and validated, and these results are often cached, the overhead of calculation of the 'y' is probably not
> material.

For X.509 certificates, the ANSI format is already well established, so the alternative method is hardly relevant there.
As you said, it is more a suggestion to consider for new specifications.

-- 
Johannes

---

From: Stephen Kent <[email-masked]>
Date: Tue, 08 Jan 2013 11:52:09 -0500

Folks,

I think my initial concern has been misunderstood, or maybe I 
misunderstood the
purported benefits of the proposed mechanism.

When I asked about compatibility with existing S/MIME specs, I was not 
referring to
details of how the EC public key is represented in  a cert, per se.

Andrey's message on 1/4 said:

"Point compression is more beneficial for storage security for reasons 
of performance and storage efficiency. For storage efficiency side: when 
there are multiple recipients per message, each associated with one 
ECDH-related field, it's possible for ECDH-specific payload to get 
arbitrary large for a fixed short message. For the performance argument: 
*if the message was encrypted to N recipients, to decode it only one 
recipient will be used, and thus the calculation of 'y' is done once but 
the space is saved for N. *

My question was whether this technique, in bold above, is compatible 
with the current, normal
processing for S/MINE, or whether it would require S/MIME to operate 
differently (at the originator
or at any recipient) in order to reduce the overhead in the fashion 
alluded to above.

I don;t think that question has been answered.

Steve

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 08 Jan 2013 11:35:17 -0800

I believe that the compact representation of the point documented here 
http://tools.ietf.org/html/draft-jivsov-ecc-compact is suitable for any 
IETF protocol. It doesn't expect changes of processing rules, that would 
be a non-starter.

For example, consider how it would work for IKE 
http://tools.ietf.org/html/rfc4753. Section 7 tells that IKE KE uses x|y 
sequence. My proposal would change it to x.

The bring a question of "isn't there up to 1 bit of entropy present in 
y"? I prove in the spec that it's valued as zero, i.e. it doesn't add 
anything to the security. Regardless, of the answer to whether there is 
0 or 1 of entropy present in y, the ambiguity of y/-y must be resolved 
and the method I propose does so by a minor tweak to the key generation, 
to generate a "compliant" key ( As a matter of fact, no tweaks are 
needed for ECDH keys, only for ECDSA keys. ECDH keys are always 
"compliant" when only the x of the shared point is used. )

This means that the IKE initiators and responders generate their 
ephemeral keys in such a way that the simple dropping of the y is what 
constitutes the compact representation.

This works the same way for SMIME with ECDH. Sender is free to generate 
a "compliant" ephemeral ECDH and the rest of processing rules are 
identical to current SMIME with point compression method.

BTW, I believe that a crypto software should always generate only 
"compliant" ECC keys, because there is no loss of security in doing so. 
Then the compact representation is worry free and is never conditioned 
on the type of the key.