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

From: Johannes Merkle <[email-masked]>
Date: Mon, 05 Nov 2012 14:35:07 +0100

We have submitted a new revision of the Internet Draft Using the ECC Brainpool Curves (defined in RFC 5639) for IKEv2
Key Exchange
https://datatracker.ietf.org/doc/draft-merkle-ikev2-ke-brainpool/

Last week, this draft has also been submitted to the Independent Submission Editor.

The draft specifies 4 new code points for the IKEv2 transform ID registry (224, 256, 384 and 512 bit curve) and
specifies the encoding of the KE payload with and without point compression. The test vectors are shared with Dan's
draft on IKEv1 http://tools.ietf.org/html/draft-harkins-brainpool-ike-groups-01. I have removed the "twisted curves" and
included a note how to use them internally (for efficient implementation) using input / output transformations.

Any feedback is welcome.

-- 
Johannes

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Mon, 5 Nov 2012 19:17:41 +0000

Hi Johannes,

Some quick comments:

I strongly encourage you to remove the "Compressed" point format.  Doing
so will minimize the changes between RFC 5903 and make the draft easier to
support, and improve the overall implementation by making it simpler.
Also, it is not clear that there is any advantage to the "compressed"
format.   It saves at most 64 bytes in total for a complete IKEv2 key
establishment, and since IKEv2 exchanges typically send a lot more data
than that, it sounds like a false economy to add complexity in order to
avoid a little bit of data.

The paragraph starting "The corresponding twisted curves ..." is a
distinct and self-contained topic.  I suggest putting it into its own
section.  

In some places, the draft gives [SEC1] as a normative reference, where
RFC6090 is also applicable (Sections 4.1 and 6 apply jn Section 2.2 of
draft-merkle-ikev2-ke-brainpool, for instance).

David

On 11/5/12 8:35 AM, "Johannes Merkle" <[email-masked]> wrote:

>We have submitted a new revision of the Internet Draft Using the ECC
>Brainpool Curves (defined in RFC 5639) for IKEv2
>Key Exchange
>specifies the encoding of the KE payload with and without point
>compression. The test vectors are shared with Dan's
>draft on IKEv1 
>http://tools.ietf.org/html/draft-harkins-brainpool-ike-groups-01. I have
>removed the "twisted curves" and
>_______________________________________________
>IPsec mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/ipsec

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 07 Nov 2012 12:57:05 +0100

Hi David,

> avoid a little bit of data.

I do not think that using point compression is complex. The rule, how to determine the representation of the KE payload
(by bit length) is very simple and common crypto libraries like OpenSSL provide EC point expansion functions, so there
is not much an implementation could do wrong.

On the other hand, there may be environments where every byte savings counts. For instance, when using IPsec for
communications between military radio equipment, bandwidth can be very limited. Another example could be implementation
in embedded environments. For instance, I have talked with major car manufacturers who are really concerned about
bandwidth limitations on their internal bus in the context of secure communication between control units. IKE is an
option for such communications.

Point compression is a quite common technique and supported by relevant ECC standards, i.e. ANSI X9.62/X9.63, IEEE P1363
and SEC, but also by many IETF standards like TLS, CMS, PKIX, SSH. IMHO, IKE should allow this option like TLS does.
Actually for IKE, the bandwidth limitations may be more relevant than for TLS, where point compression is supported as well.

> distinct and self-contained topic.  I suggest putting it into its own
This is a good point, I will do this in the next revision.

> draft-merkle-ikev2-ke-brainpool, for instance).

RFC 6090 does not define a FieldElement-to-OctetString conversion but only Integer-to-OctetString. In order to use a
reference to RFC 6090, I would have to change the text to
+++
... by representing the field element as integer in the interval [0,p-1] and then using the Integer-to-OctetString
conversion method specified in [RFC6090]...
+++
This makes the whole sentence more difficult to comprehend. On the other hand, I do not see any advantage in pointing to
RFC 6090 instead to SEC1.

Johannes

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Wed, 7 Nov 2012 14:48:00 +0000

Hi Johannes,

On 11/7/12 6:57 AM, "Johannes Merkle" <[email-masked]> wrote:

>I do not think that using point compression is complex.

Sure, it is not a giant amount of complexity, but is any complexity
warranted here?   If the compressed format is omitted, then the formats
for all five of the EC groups registered in Diffie-Hellman Group Transform
IDs, and that of the brainpool curves, would be identical, so that an
implementation of the brainpool curves could be handled as "same software
operating on different group parameters".   That is much preferable to
having different group logic for different DH Group IDs.

>The rule, how to determine the representation of the KE payload
>(by bit length) is very simple and common crypto libraries like OpenSSL
>provide EC point expansion functions, so there

Well, there are some steps that could be done wrong: a receiver-side
implementation could fail to check and handle lengths correctly, it could
fail to compute the y-coordinate from the x-coordinate correctly, either
of which could result in an exploitable vulnerability.  This might seem
like a minor point, but it is clear that crypto protocols should avoid
complexity, especially in how they parse data (this brings to mind an
interesting recent presentation on this is
<http://www.ists.dartmouth.edu/events/abstract-sassaman-patterson.html>).

>
>On the other hand, there may be environments where every byte savings
>counts. For instance, when using IPsec for
>communications between military radio equipment, bandwidth can be very
>limited. Another example could be implementation
>in embedded environments. For instance, I have talked with major car
>manufacturers who are really concerned about
>bandwidth limitations on their internal bus in the context of secure
>communication between control units. IKE is an

I don't think the byte savings of any protocol option can be justified by
considering only the number of bytes that it would eliminate from the
communications.  What matters is the relative savings, that is, the total
number of bytes in the communications with and without that option.  How
many bytes will IKEv2 take, in an embedded context, say, with and without
the compressed format?  It should be possible to estimate a minimum based
on draft-kivinen-ipsecme-ikev2-minimal-01.   Looking at the table of
payloads in Section 2, it appears that the total bytes exchanged is going
to be considerably larger than that saved by the compressed format.

>
>Point compression is a quite common technique and supported by relevant
>ECC standards, i.e. ANSI X9.62/X9.63, IEEE P1363
>and SEC, but also by many IETF standards like TLS, CMS, PKIX, SSH. IMHO,
>IKE should allow this option like TLS does.

A minor point: the use of ECC in TLS is not part of the standard, but is
an informational extension.  More importantly, the TLS ECC RFC allows the
negotiation of supported point formats; only uncompressed format is a
MUST-implement (see Section 5.1.2 of RFC4492).  In contrast,
draft-merkle-ikev2-ke-brainpool-00 requires all implementations to support
compressed format.   There is a clear preference in IETF to avoid having a
compressed format as a MUST-implement, so I am concerned that keeping it
in the draft will be an inhibitor.

One way that you could change the draft to make the compressed format
optional is to define a different DH Group ID for each of the existing
groups and each of the formats, which would double the number of groups.
This might be acceptable to the WG if the number of groups could be kept
small.  

>Actually for IKE, the bandwidth limitations may be more relevant than for
>TLS, where point compression is supported as well.
>
>> 
>RFC 6090 does not define a FieldElement-to-OctetString conversion but
>only Integer-to-OctetString. In order to use a
>... by representing the field element as integer in the interval [0,p-1]
>and then using the Integer-to-OctetString
>This makes the whole sentence more difficult to comprehend. On the other
>hand, I do not see any advantage in pointing to

I didn't mean to suggest eliminating the reference to SEC1, sorry if I was
unclear on that.   What I was meant to suggest is text like "The
compressed format is equivalent to the compact representation of Section
4.2 of RFC6090, using the conversion between integers and octet strings of
Section 6 of the same reference."

Let me take a step back here and explain some of my motivations.   Here is
the big picture as I see it: it is good for IKE to embrace ECC, and it is
reasonable thing to have some diversity of ECC parameters, to provide a
fallback in case of unanticipated future results in cryptanalysis.  So I
would like to see the brainpool IKE groups be something that IPsec
implementers are comfortable with implementing (and I'm making suggestions
that I hope will move the draft in that direction).  Additionally, if in
the future we do end up having additional ECC parameters that get
contributed to IKE, it would be a good thing for the WG to have
established a precedent favoring a consistency across ECP groups.

Thanks and regards,

David

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 07 Nov 2012 19:21:45 +0100

Hi David,

> having different group logic for different DH Group IDs.

I see your point, but I am not sure, if it is good to maintain a limitation of the previous RFCs for the new curves as
well. At least not, if we agree that point compression is a reasonable feature (which is still discussed below).

> of which could result in an exploitable vulnerability.  This might seem

Point compression is simply the ommission of the x-value, and for point expansion, functions are included in OpenSSL and
other crypto libraries. Thus, such mistakes should only occur if someone decides to implement the arithmetic by itself
but is incapable of doing it correctly (and does not perform sufficient testing). This seems to me a quite a case of
carelessness and I don't think, that an RFC should be so fool-proof to prevent that. There are certainly much more
complex aspects in IKE than point compression.

> to be considerably larger than that saved by the compressed format.

If using certificate-based authentication, probably the largest payload is the CERT. It contains a public key and a
signature, which, when using the same curve as for KE, are (together) 3-4 times larger than a compressed KE payload. In
addition, some smaller data fields as the DNs, algorithm identifiers, validity, serial, and some ASN.1 overhead.
But according to RFC 5480 one can use point compression for the public key contained in the certificate as well, which
means that the implementation must be able to handle this anyway.

I agree with you that the saving is small, but from what I have heard about constrained environment, even a saving below
10% can be desirable.

> an informational extension.  

This is also true for ECC in IKEv2. Furthermore, the TLS RFCs are WG document, as the IANA registry for elliptic curves
requires IETF consensus.  (I know that by heart, as I am currently also working on the standardization of the Brainpool
curves for TLS.)

> More importantly, the TLS ECC RFC allows the
> MUST-implement (see Section 5.1.2 of RFC4492).  

That is a good point, but unfortunately in IKE, KE methods are not negotiated at all. This is not only an special issue
for ECC or point compression. If the other peer does not understand the curve you are using or ECC at all, that you end
up in INVALID_KE_PAYLOAD notification and have to re-try.

Yes, introducing point compression doubles the number of new possibilities to choose from: 8 instead of 4 in the case of
the 4 groups defined in the draft. But this number is still moderate.

> In contrast,
An interesting idea. However, I am not sure if making one encoding optional would not increase interoperability problems
due to the lack of negotiation for KE group or point representation. But I would make point compression optional, if you
and the other folks on the list think that is enhances interoperability.

> This might be acceptable to the WG if the number of groups could be kept

First, the number is already small compared to the name space.

As to the definition of separate transform IDs, I don't understand, why only this should allow point compression to be
optional. The transform Id serves for identifying the group. The encoding (compressed or uncompressed) can be determined
from the length of the KE payload and the group.

> Section 6 of the same reference."
I can do this, but adding this text does not make RFC 6090 a normative reference, right? Or do you mean to replace the
explicit description how to encode in compressed format with this reference?

> established a precedent favoring a consistency across ECP groups.
I understand and please be ensured that I take your critics as constructive and fruitful.

regards,
Johannes

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 7 Nov 2012 21:12:47 +0200

Johannes Merkle writes:
> I see your point, but I am not sure, if it is good to maintain a
> limitation of the previous RFCs for the new curves as 
> well. At least not, if we agree that point compression is a
> reasonable feature (which is still discussed below). 

Every single option adds complexity, so I do not think we should add
more optional things. 

> If using certificate-based authentication, probably the largest
> payload is the CERT. It contains a public key and a signature,
> which, when using the same curve as for KE, are (together) 3-4 times
> larger than a compressed KE payload. In addition, some smaller data
> fields as the DNs, algorithm identifiers, validity, serial, and some
> ASN.1 overhead. But according to RFC 5480 one can use point
> compression for the public key contained in the certificate as well,
> which means that the implementation must be able to handle this
> anyway.

You can replace X.509 cert in CERT payload with hash and url, which
will make the payload to be around 60 bytes or so depending on the
length of the url used (5 bytes for header + 20 bytes for hash, and 29
bytes for url in format of "http://123.123.123.123:1234/"). Bit more
if the URL has IPv6 address.

> I agree with you that the saving is small, but from what I have
> heard about constrained environment, even a saving below 10% can be
> desirable.

Not sending the CERT, but replacing it with hash and url offers much
bigger savings, and people are not even doing that.

> That is a good point, but unfortunately in IKE, KE methods are not
> negotiated at all. This is not only an special issue for ECC or
> point compression. If the other peer does not understand the curve
> you are using or ECC at all, that you end up in INVALID_KE_PAYLOAD
> notification and have to re-try.

Note, that negotiating the use of point compression without retry or
not would waste more bytes then the point compression saves... The KE
payload is in the first packet, which means that to be able to
negotiate it beforehand would require one extra roundtrip. The IKEv2
headers + notify payloads etc would be 2 * (28 + 8 bytes) = 72 bytes
which is already quite big EC key Y part... 

> Yes, introducing point compression doubles the number of new
> possibilities to choose from: 8 instead of 4 in the case of the 4
> groups defined in the draft. But this number is still moderate.

I would prefer not to do that.

> As to the definition of separate transform IDs, I don't understand,
> why only this should allow point compression to be optional. The
> transform Id serves for identifying the group. The encoding
> (compressed or uncompressed) can be determined from the length of
> the KE payload and the group.

If I remember right the reason IKEv2 does not use point compression
for the current groups was that there was some IPR. Is that issue
already been cleared?
-- 
[email-masked]

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 08 Nov 2012 09:26:45 +0100

Hi Tero,

> Every single option adds complexity, so I do not think we should add

Point compression is not the focus of our draft. Given the opposition it is facing here, I suggest to wait for further
replies and if point compression turns out to be objected by the majority on this list, I will not insist on this feature.
BTW: In an earlier thread Dan Haskins has already indicated his preference to leave point compression out.

> bigger savings, and people are not even doing that.
You can not be sure that this option isn't used is some constrained environments.

Just a note: the relative saving of point compression is larger when sending hash + URL instead of the CERT.

> which is already quite big EC key Y part... 

What I had in mind are constraint environments where using bandwidth saving techniques like point compression can be
assumed to be the default.

> for the current groups was that there was some IPR. Is that issue

The the patent expires in 2014.
http://cr.yp.to/patents/us/6141420.html

-- 
Johannes

---

From: "Derek Atkins" <[email-masked]>
Date: Wed, 7 Nov 2012 13:27:32 -0500

Hi,

On Wed, November 7, 2012 1:21 pm, Johannes Merkle wrote:
> Hi David,
>
> Point compression is simply the ommission of the x-value, and for point
> expansion, functions are included in OpenSSL and
> other crypto libraries. Thus, such mistakes should only occur if someone
> decides to implement the arithmetic by itself
> but is incapable of doing it correctly (and does not perform sufficient
> testing). This seems to me a quite a case of
> carelessness and I don't think, that an RFC should be so fool-proof to
> prevent that. There are certainly much more

You're making the assumption that an implementor is using OpenSSL or has
already implemented point compression.  IMHO that is not a reasonable
assumption.  Many implementations use their own crypto libraries and
therefore would have to implement these compression and expansion
functions, including all the potential errors thereto.  So saying "it's
easy, it's in OpenSSL" is not, IMHO, a reassuring statement or argument.

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 8 Nov 2012 10:57:36 -0800 (PST)

Hi Derek,

> easy, it's in OpenSSL" is not, IMHO, a reassuring statement or argument.

  Decompression is just a square root and a discriminator to say whether
the result is y or -y. All the brainpool curves are of the form p mod 4 = 3,
where p is the prime defining the curve. For such curves the square root
of n would be n^((p+1)/4) mod p. This is straightforward to implement
with any big number library.

  regards,

  Dan.

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Thu, 8 Nov 2012 21:24:32 +0000

On 11/8/12 3:26 AM, "Johannes Merkle" <[email-masked]> wrote:

>Point compression is not the focus of our draft. Given the opposition it
>is facing here, I suggest to wait for further
>replies and if point compression turns out to be objected by the majority
>on this list, I will not insist on this feature.
>BTW: In an earlier thread Dan Haskins has already indicated his
>preference to leave point compression out.
>
>> 

What's the scenario here?   If hash + URL is sent, the certificate still
has to be retrieved.  It might not be part of the IKE exchange, but moving
it to HTTP doesn't mean that it doesn't contribute to bytes on the wire
(or over the air, in the case of wireless).

David

>What I had in mind are constraint environments where using bandwidth
>saving techniques like point compression can be

---

From: Yoav Nir <[email-masked]>
Date: Thu, 8 Nov 2012 23:44:23 +0200

> (or over the air, in the case of wireless).

Since we tend to meet the same people all the time (or communicate with the same parties), usually the hash+URL would lead to retrieving the certificate from a cache, rather than from a remote web server.

Of course, if my implementation is running on a "thing", it doesn't have a cache and this argument doesn't apply.

Yoav

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 8 Nov 2012 23:53:06 +0200

David McGrew (mcgrew) writes:
> has to be retrieved.

Usually not, as it is already cached in the client. I.e. it only needs
to fetched first time unknown hash is seen. After fetching it first
time, and validating the cert the recipient of the hash + URL does not
need to fetch it again when the same peer connects later.

In most cases the devices talking to each other using IPsec is quite
small set of devices, so caching their certificates does not take too
much resources (especially if you just store the public key, hash and
end of validity time (i.e. when you need to do something next time,
either fetch CRL, or revalidate the cert because it expired etc). 

> It might not be part of the IKE exchange, but moving it to HTTP
> doesn't mean that it doesn't contribute to bytes on the wire (or
> over the air, in the case of wireless).

The another reason for this feature in IKEv2 is to make the IKE_AUTH
packet smaller, so it does not need to be fragmented. IKE_AUTH packet
is UDP and there are some problems in some environments if it gets too
big and starts to get fragmented. This option moves big parts of the
IKE_AUTH packet away from UDP packet to separete TCP session.
-- 
[email-masked]