Subject: [IPsec] Re: Last call comments for draft-lepinski-dh-groups-01

From: Paul Hoffman <[email-masked]>
Date: Wed, 10 Oct 2007 10:22:53 -0400

At 1:32 PM +0300 10/9/07, <[email-masked]> wrote:
>1) Section 1 says:
>
>    "Sixteen additional groups subsequently have been defined and
>    assigned values by IANA for use with IKE (v1 and v2).  All of
>    these additional groups are optional in the IKE context.  Of
>    the twenty-one groups defined so far, eight are MODP groups
>    (exponentiation groups modulo a prime), ten are EC2N groups
>    (elliptic curve groups over GF[2^N]) and three are ECP groups
>    (elliptic curve groups over GF[P]).
>
>This is not totally correct. As of this writing, no EC2N groups
>have been assigned values for use with IKEv2.  Also, eight of the
>ten EC2N groups for IKEv1 are not documented in any RFC. (And yes,
>I'm aware of draft-ietf-ipsec-ike-ecc-groups -- but that hasn't
>been approved yet, and requires changes before approval.)

draft-lepinski-dh-groups needs to track 
draft-ietf-ipsec-ike-ecc-groups very carefully. If there is any 
mis-match, we will have interoperability problems in the future.

>2) For IKEv1/IKEv2, the document should explicitly specify how
>ECC points are converted to octet strings (for KE payloads
>and resulting shared secret value). Currently, there are at
>least three incompatible options (RFC 4753, RFC 2409, and
>draft-ietf-ipsec-ike-ecc-groups-10 drafts). I'd suggest just
>saying "the same way as in RFC 4753".

This bodes really poorly for interoperability. 
draft-lepinski-dh-groups needs to be revised to specify one of the 
methods, and that needs to be discussed on the IPsec mailing list. I 
would not assume that implementers would prefer RFC 4753 over 
draft-ietf-ipsec-ike-ecc-groups.

--Paul Hoffman, Director
--VPN Consortium

_______________________________________________
IPsec mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ipsec

---

From: <[email-masked]>
Date: Thu, 11 Oct 2007 10:38:30 +0300

Paul Hoffman wrote:

> methods, and that needs to be discussed on the IPsec mailing list. 
> I would not assume that implementers would prefer RFC 4753 over 

I suggested "the same way as in RFC 4753" not because I particularly
prefer that point-to-octet-string conversion method, but because I
would prefer not having three different methods (two is bad enough).

(Note that the current ecc-groups-10 draft actually tries to 
modify the definitions of groups 19/20/21 from RFC 4753: it
reuses the same numbers but with different point-to-octet-string
conversion method.)

Best regards,
Pasi

---

From: Chinh Nguyen <[email-masked]>
Date: Mon, 15 Oct 2007 09:54:28 -0400

> reuses the same numbers but with different point-to-octet-string

Note that interoperability issues involve more than the representation 
of the ECC point (KE payload in IKE). The shared secret is also 
different between RFC 4753 (x + y) and draft-ietf-ipsec-ike-ecc-groups 
(x only). This has implications for the generation of the symmetric keys.

I believe that the representation in draft-ietf-ipsec-ike-ecc-groups is 
more widely used including other standards such as SEC, FIPS 186-2, IEEE 
1363, and ANSI X9.62.

D. Brown at Certicom is writing an update to 
draft-ietf-ipsec-ike-ecc-groups which attempts to resolve this 
interoperability issue. In a nutshell, both formats are supported. 
Practically speaking when it comes to IKE, the responder supports both 
format and chooses the format based on the one chosen by the initiator.

Regards,

Chinh

--
http://www.certicom.com

---

From: Daniel Brown <[email-masked]>
Date: Mon, 15 Oct 2007 12:30:51 -0400

Hi,

Attached is the draft I prepared a while back in an attempt to address 
Working Last Call comments.

As Chinh states, one of the goals of this draft is to allow both the 4753 
approach, and the older approach (i.e. ANSI/IEEE/SECG point representation 
and NIST/ANSI/IEEE/SECG key derivation), in such a way that the approach 
is determined independently of the group.

Comments are welcome on whether this is worthwhile goal, and if so, better 
ways to attain this goal.

Best regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: "Scott Fluhrer" <[email-masked]>
Date: Mon, 15 Oct 2007 17:41:27 -0400

_____  

From: Daniel Brown [mailto:[email-masked]] 
Sent: Monday, October 15, 2007 12:31 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]
Subject: Re: [IPsec] Re: Last call comments for draft-lepinski-dh-groups-01

Hi, 

As Chinh states, one of the goals of this draft is to allow both the 4753
approach, and the older approach (i.e. ANSI/IEEE/SECG point representation
and NIST/ANSI/IEEE/SECG key derivation), in such a way that the approach is
determined independently of the group. 

The only complaint I have about this approach is that it appears to mandate
Certicom IPR for any implementation of the draft.  As the previous
definition of groups 19-21 in RFC4753 did not mandate this IPR, I don't know
if this is an improvement.
 
Background: Certicom claims IPR on the technique of "point compression",
which is the method of representing an EC point by giving the entire X
coordinate, along with a single bit which represents which of the two
possible Y coordinates is meant.  Now, the draft does not mandate that you
use point compression when forming a KE payload, however, for
interoperability purposes an implementation would appear to be required to
understand a point-compressed KE payload, and this would appear to be
sufficient for infringement.  In contrast, RFC4753 places the entire X and Y
coordinates in the KE payload, thus avoiding this IPR.
 
My suggestion would be to leave groups 19-21 outside the scope of this
draft, and leave them as defined by RFC4753.  This would mean that we would
use different point representation for different EC groups; that would
appear to me to be a lesser evil.

Best regards,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Daniel Brown <[email-masked]>
Date: Mon, 15 Oct 2007 18:05:00 -0400

"Scott Fluhrer" <[email-masked]> wrote on 10/15/2007 05:41:27 PM:

> 
> The only complaint I have about this approach is that it appears to 
> mandate Certicom IPR for any implementation of the draft.  As the 
> previous definition of groups 19-21 in RFC4753 did not mandate this 
> IPR, I don't know if this is an improvement.
> 
> Background: Certicom claims IPR on the technique of "point 
> compression", which is the method of representing an EC point by 
> giving the entire X coordinate, along with a single bit which 
> represents which of the two possible Y coordinates is meant.  Now, 
> the draft does not mandate that you use point compression when 
> forming a KE payload, however, for interoperability purposes an 
> implementation would appear to be required to understand a point-
> compressed KE payload, and this would appear to be sufficient for 
> infringement.  In contrast, RFC4753 places the entire X and Y 

Suppose support of point compression is explicitly defined to only be a 
MAY.    The aim is that parties who really need point compression have 
specification to comply with, but nobody else will be forced to support 
it.  Similarly, users of point compression will not expect to interoperate 
with everbody else.  Would that alleviate your complaint?

Also, keep in mind that this draft is intended for Informational Track.

> 
> My suggestion would be to leave groups 19-21 outside the scope of 
> this draft, and leave them as defined by RFC4753.  This would mean 
> that we would use different point representation for different EC 
> groups; that would appear to me to be a lesser evil.
>

---

From: <[email-masked]>
Date: Tue, 16 Oct 2007 11:57:34 +0300

It looks like this proposal creates an interoperability problem: 
If an implementation of ecc-groups-10-WGLC-0 proposes any of 
groups 19/20/21, it will not be able to talk to a responder that 
implements groups 19/20/21 according to RFC 4753 (because the
KEi payload will use a different format that RFC 4753-only
implementations won't understand).

If you insist on including point compression (which RFC 4753 doesn't),
IMHO you need to either drop groups 19/20/21 from this document, or 
redefine them with different numbers.

(However, having multiple different formats for the same information 
is a recipe for interoperability problems, and poorly tested code 
in implementations -- possibly leading to security problems as well.
So I'd really recommend not doing this.)

Furthermore, the proposed text is slightly misleading:

> "For elliptic curve groups implemented in accordance with this
> document, the data in the KE payload when using this group SHOULD be
> the octet string representation specified in [SEC1], Section 2.3.3
> (this representation is also specified in [X9.62], [X9.63],
> [FIPS-186-2], and [IEEE-1363]) of the point on the curve chosen by
> taking the randomly chosen secret Ka and computing Ka*G, where * is
> the repetition of the group addition.  "

This text suggests that [SEC1], [X9.62], [X9.63], [FIPS-186-2], and
[IEEE-1363] all specify identical octet string representations for
points. This is not the case.

I haven't compared all of them, but at least the point-to-octet 
string conversion specified in [X9.62], Section A.5.7, can produce 
octet strings that can't be decoded by an implementation doing
octet string-to-point conversion according to [SEC1]. 

(Also, the "SHOULD" is probably not the intended word here;
it should be either plain "is" or "MUST").

Best regards,
Pasi

> -----Original Message-----
> From: ext Daniel Brown [mailto:[email-masked]] 
> Sent: 15 October, 2007 19:31
> To: [email-masked]
> Cc: [email-masked]; [email-masked]; Eronen Pasi (Nokia-NRC/Helsinki);

>     [email-masked]; Chinh Nguyen
> Attached is the draft I prepared a while back in an attempt to
> address Working Last Call comments.
> 
> As Chinh states, one of the goals of this draft is to allow both the
> 4753 approach, and the older approach (i.e. ANSI/IEEE/SECG point
> representation and NIST/ANSI/IEEE/SECG key derivation), in such a
> way that the approach is determined independently of the group.
>
> Comments are welcome on whether this is worthwhile goal, and if so,
> better ways to attain this goal.
> 
> 
> Best regards,
> 
> Dan Brown
> (905) 501-3857
> http://www.certicom.com
> 
>

---

From: Chinh Nguyen <[email-masked]>
Date: Tue, 16 Oct 2007 11:37:34 -0400

> implementations won't understand).

With regards to our IKE implementation, we default to RFC 4753 for 
groups 19/20/21 as initiator and use the other format for the other curves.

Perhaps it should explicitly state this fact ("MUST"?) in 
ecc-groups-10-WGLC-0.

> redefine them with different numbers.

My reading of the draft is that the proposed point-to-octet string 
format must be supported but not necessarily point compression itself. 
Namely, an implementation may choose to support only 04|X|Y.

Again, perhaps an explicit statement?

> octet string-to-point conversion according to [SEC1]. 

I assume you are referring to hybrid form (06|07) as specified in X9.62? 
  Formally, this is an incompatibility SEC1 and X9.62. But conversion 
from hybrid format to uncompressed/compressed format is easy.

As I noted in a previous e-mail, (non)-interoperability extends to the 
shared secret. In the other standards, as well as the current 
draft-lepinski-dh-groups-01, the shared secret is the x-coordinate. This 
is not the case with RFC 4753 which includes both x and y. Compare the 
shared-secret of the 256-bit curve in draft-lepinski-dh-groups-01 page 
21 and rfc 4753 page 9.

draft-lepinski-dh-groups-01 should also describe the format of the 
shared secret.

Chinh
--
http://www.certicom.com

---

From: "Scott Fluhrer" <[email-masked]>
Date: Tue, 16 Oct 2007 15:45:24 -0400

> From: Chinh Nguyen [mailto:[email-masked]] 
> Sent: Tuesday, October 16, 2007 11:38 AM
> To: [email-masked]
> Cc: [email-masked]; [email-masked]; [email-masked]; 
> [email-masked]; [email-masked]
> > If an implementation of ecc-groups-10-WGLC-0 proposes any of groups 
> > 19/20/21, it will not be able to talk to a responder that 
> implements 
> > groups 19/20/21 according to RFC 4753 (because the KEi payload will 
> > use a different format that RFC 4753-only implementations won't 
> > understand).
> 
> With regards to our IKE implementation, we default to RFC 
> 4753 for groups 19/20/21 as initiator and use the other 
> format for the other curves.
> 

That, at least to me, would seems to be reasonable.

> My reading of the draft is that the proposed point-to-octet 
> string format must be supported but not necessarily point 
> compression itself. 

Again, in that case, we can have a situation where two different
implementations support the same groups, but can't interoperate (because one
side insists on using the 02|X format, and the other side doesn't implement
it).  I'm not sure if that's a situation that the IETF would want to
encourage; can others comment?

Now, there may be ways around that (for example, if you receive a 02|X or
03|X format, pick one of the two possible Ys arbitrarily; you can try to
claim that you're just using Miller's 1986 observation that transmitting
only the X coordinate is sufficient in this case).  However, I am not a
lawyer, and I'm not sure if this would be considered a valid way to avoid
the IPR.

> 
> > I haven't compared all of them, but at least the 
> point-to-octet string 
> > conversion specified in [X9.62], Section A.5.7, can produce octet 
> > strings that can't be decoded by an implementation doing octet 
> > string-to-point conversion according to [SEC1].
> 
>   Formally, this is an incompatibility SEC1 and X9.62. But 
> conversion from hybrid format to uncompressed/compressed 
> format is easy.
> 
> As I noted in a previous e-mail, (non)-interoperability 
> extends to the shared secret. In the other standards, as well 
> as the current draft-lepinski-dh-groups-01, the shared secret 
> is the x-coordinate. This is not the case with RFC 4753 which 
> includes both x and y. Compare the shared-secret of the 
> 256-bit curve in draft-lepinski-dh-groups-01 page
> 21 and rfc 4753 page 9.
> 
> draft-lepinski-dh-groups-01 should also describe the format 
> of the shared secret.
> 
> Chinh
> --
> http://www.certicom.com
> 
>

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 17 Oct 2007 15:24:34 +0300

> That, at least to me, would seems to be reasonable.

As we do have one specified way how to format for the KE and shared
secrets defined as RFC (RFC4753), I see no point of using any other
format now. I think the draft-ietf-ipsec-ike-ecc-groups-10.txt should
be fixed to use the same format too, and not to define new formats.

If we want to add support for point compression, I see that only way
to do that is to add duplicate numbers for those elliptic curves one
with point compression and another without. We cannot really negotiate
the support for point compression as KE payload is already used in the
first packet we send from initiator to the responder. With separate
group numbers we could get interoperability by using
INVALID_KE_PAYLOAD notification with one extra round trip.

On the other hand if I have understood correctly the benefit from
point compression is saving less than 64 bytes from the final payload.
The first packet is 28 bytes of header + 44 bytes of SA payload (one
exact alogorithm set) + 8 (KE payload header len) + KE payload len +
36 (32 byte nonce payload) + 2 * 28 (2 * NAT detection payloads) = 172
bytes + KE data length. I.e using 512 bit elliptic curve that makes
the first packet 300 bytes without point compressioon and 236 bytes
with point compression. Both will still keep the packet length way
below the threshold that would start causing fragmentation and so on.
Bandwidth saving concerns for packets which are sent once for every 8
hours or so is not really meaningful.

> > draft-lepinski-dh-groups-01 should also describe the format 

The current text in draft-lepinski-dh-groups-01.txt says you use
formatting specified in the RFC2409. It does not really say anything
about IKEv2. RFC4306 does not specify how to use it with elliptic
curves. RFC2409 says we only send and use x (no mention of padding,
and only has EC2N groups). RFC4753 says we use both x and y (padded
and concatenated, and only has ECP groups).

Draft-lepinski-dh-groups-01.txt should be updated to refer to RFC4753
for IKEv2 case and use that formatting specified there.

The test vectors should be provided in format where both x and y of
the secret is given (even if some protocols referenced there do use
only x of it). There is no need to have exact payload encodings as is
done in RFC4753 as this draft defines groups for other use than IKEv2
too, but it would be useful to have both girx and giry and perhaps
g^ir too (using RFC4753 terminology to refer those values here).
-- 
[email-masked]