From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Yaron Sheffer <yaronf.ietf@gmail.com>
Thread-Topic: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key
 Exchange
Thread-Index: AQHNz/olcML1jJ9U4EC5RJIM/xfJWZgHG0cg
Date: Mon, 3 Dec 2012 14:27:50 +0000
Message-ID: <A113ACFD9DF8B04F96395BDEACB340421CB714@xmb-rcd-x04.cisco.com>
References: <50B8A287.9090509@secunet.com>
 <074557eff2f722f10198aac4fb2f8d9c.squirrel@www.trepanning.net>
 <4613980CFC78314ABFD7F85CC30277210EDCE571@IL-EX10.ad.checkpoint.com>
 <A113ACFD9DF8B04F96395BDEACB340421C9045@xmb-rcd-x04.cisco.com>
 <50B9DC95.80202@gmail.com>
 <A113ACFD9DF8B04F96395BDEACB340421CA383@xmb-rcd-x04.cisco.com>
 <50BA5A70.6030808@gmail.com>
In-Reply-To: <50BA5A70.6030808@gmail.com>
Accept-Language: en-US
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: Johannes Merkle <johannes.merkle@secunet.com>,
 Manfred Lochter <manfred.lochter@bsi.bund.de>, Yoav Nir <ynir@checkpoint.com>,
 Dan Harkins <dharkins@lounge.org>, IPsecme WG <ipsec@ietf.org>,
 "rfc-ise@rfc-editor.org" <rfc-ise@rfc-editor.org>,
 "Sean P. Turner" <turners@ieca.com>
Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2
 Key	Exchange
Precedence: list

As for http://tools.ietf.org/html/rfc5996#section-2.12, it's fine as far as=
 it goes, however (IMHO) it rather punts on what self-checks are actually n=
eeded.  It does refer to the Menezes and Ustaoglu paper, which is quite goo=
d, however, it would be better if you spell out exactly what tests the impl=
ementer would need to run for each IKE group.  An implementation might have=
 problems determining from the paper what is appropriate; for example, grou=
ps 22-24 would be considered "DSA groups" by the nomenclature of the paper =
(see section 2.1); however nowhere in the IKE documents are they actually l=
abeled as such.

Here is a quick run-down:
- Standard MODP groups (1, 2, 5, 14-18): informational leakage from a small=
 group attack is minimal (see section 2.2 of the paper); hence, the only ch=
eck needed is a verification that the peer's public value r is in range (1 =
< r < p-1)

- MODP groups with small subgroups (22-24): there is some informational lea=
kage from a small subgroup attack (see section 2.1 of the paper); hence, yo=
u need to check both that the peer's public value is in range (1 < r < p-1)=
 and that r**q =3D 1 mod p (where q is the size of the subgroup)

- EC groups; there is some informational leakage possible (see section 2.3)=
; hence, you need to check that the peer's public value is valid; that is, =
it is not the point-at-infinity, and that the x and y parameters from the p=
eer's public value satisfies the curve equation, that is, y**2 =3D x**3 + a=
x + b mod p.  Note that even though the paper specifically targets odd char=
acteristic EC curves, their advice of checking the curve equation is equall=
y applicable to even characteristic curves as well.=20


Now, as for whether checking the peer's public value ought to be a requirem=
ent, even if you aren't reusing private keys, I would still say that it oug=
ht to be.  If we look at the ECDH point addition/doubling code, well, they =
are designed to work correctly if you give them valid points (that is, poin=
ts that are actually on the curve).  If you just take bit patterns you rece=
ived in a packet from the peer, and just give them to the EC routines, well=
, there's no inherent requirement what might happen if the values don't hap=
pen to be valid.  If the implementation uses the standard textbook point ad=
dition/doubling code, we can predict what will happen -- however, a specifi=
c implementation might decide to do something different.  Because of this (=
and because checking is so cheap -- we're talking maybe 1% of the cost of t=
he cost of doing the ECDH phase two), I would strongly urge anyone to do th=
is check.

-----Original Message-----
From: ipsec-bounces@ietf.org [mailto:ipsec-bounces@ietf.org] On Behalf Of Y=
aron Sheffer
Sent: Saturday, December 01, 2012 2:29 PM
To: Scott Fluhrer (sfluhrer)
Cc: Johannes Merkle; Manfred Lochter; Yoav Nir; Dan Harkins; IPsecme WG; rf=
c-ise@rfc-editor.org; Sean P. Turner
Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Ex=
change

Hi Scott,

OK, I see your point (no pun intended). Regarding ECDH secret reuse, can yo=
u please review http://tools.ietf.org/html/rfc5996#section-2.12. That secti=
on was supposed to cover the relevant security considerations. In fact I th=
ink your attack is alluded to in the paper we reference from that section (=
see Sec. 5, first paragraph).

If this needs to become a MUST requirement for IKEv2 peers using ECDH, it n=
eeds to be spelled out and not left as an exercise to the reader.=20
But we have to understand whether this is a general requirement, or it only=
 applies to peers that are reusing ECDH private keys for multiple IKE sessi=
ons.

Thanks,
	Yaron

On 12/01/2012 08:44 PM, Scott Fluhrer (sfluhrer) wrote:
> I would humbly disagree.  A peer might try to send us an invalid KE, with=
 a bogus point that acts as if it were of small order with our implementati=
on; let us call this bogus point P, and its small order n.  We would then g=
enerate sk's based on the point (e mod n)P (where e is the value of our ECD=
H secret); because n is small, that allows the attacker to recover the valu=
e (e mod n).
>
> If we reuse the same ECDH secret for multiple exchanges (which is normall=
y safe), this allows someone who controls some of the peers we talk to to r=
ecover the secret value for exchanges he does not control; this is not good=
.
>
> Hence, we need to either mandate checking the point we receive, or forbid=
 ECDH secret reuse.
>
> -----Original Message-----
> From: Yaron Sheffer [mailto:yaronf.ietf@gmail.com]
> Sent: Saturday, December 01, 2012 5:32 AM
> To: Scott Fluhrer (sfluhrer)
> Cc: Yoav Nir; Johannes Merkle; IPsecme WG; Manfred Lochter; Sean P.=20
> Turner; Dan Harkins; rfc-ise@rfc-editor.org
> Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2=20
> Key Exchange
>
> Actually, I think we have it wrong. There is no reason for a *valid*=20
> peer to send an incorrect KE. And IKEv2 already protects against a=20
> MITM doing such a thing. As we all know, the protocol assumes that=20
> messages
> #3 and #4 can be observed by an attacker, and protects against malicious =
changes to any of the 4 messages, including the KE value.
>
> In other words, I would say this is a QA-level test that MAY be performed=
 by the sender. Not one that MUST be performed by the recipient.
>
> By the way, there are related protocols that need this test for their sec=
urity and do include it: SPSK, and my own RFC 6631 (IKEv2 with PACE).
> See e.g. https://tools.ietf.org/html/rfc6631#section-3.4.
>
> Thanks,
> 	Yaron
>
>
> On 12/01/2012 12:00 AM, Scott Fluhrer (sfluhrer) wrote:
>> With ECDH, there are two separate EC points that are output by the algor=
ithm:
>>
>> - There's the public value xG (where x is our secret); this is passed=20
>> in the KE payload
>> - There's the shared secret value xyG (where x is our shared secret, and=
 y is the peer's secret); this is used in the key derivation function.
>>
>> What RFC5903 says is:
>> - The public value xG will be expressed as explicit x, y coordinates.
>> - The shared secret value xyG (that is, the value we give to the sk gene=
ration function) will be only the x coordinate; the y coordinate will not b=
e used.
>>
>> Yes, this implies that doing point compression on the shared secret valu=
e doesn't make much sense (as point compression discards all but one bit of=
 y -- the format that RFC5903 chooses already discards all the bits of y). =
 However, the argument about point compression was never about the shared s=
ecret value; instead, it was about the repesentation that appeared in the K=
E payload (that is, the one that is specified to have both the x and y coor=
dinates).
>>
>> As for Dan's question, it was about whether we should validate the publi=
c value we get from the peer, well, the public value does have explicit x a=
nd y coordinates, and so it makes sense to check them.
>>
>>
>> -----Original Message-----
>> From: ipsec-bounces@ietf.org [mailto:ipsec-bounces@ietf.org] On=20
>> Behalf Of Yoav Nir
>> Sent: Friday, November 30, 2012 4:39 PM
>> To: Johannes Merkle
>> Cc: IPsecme WG; Manfred Lochter; Sean P. Turner; Dan Harkins;=20
>> rfc-ise@rfc-editor.org
>> Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2=20
>> Key Exchange
>>
>> Hi Johannes,
>>
>> Dan't question made me realise something I hadn't noticed before.
>>
>> In section 2.3, the draft says:
>>      For the encoding of the key exchange payload and the derivation of
>>      the shared secret, the methods specified in [RFC5903] are adopted.
>>
>>      In an ECP key exchange in IKEv2, the Diffie-Hellman public value
>>      passed in a KE payload consists of two components, x and y,
>>
>> However, according to RFC 5903:
>>         The Diffie-Hellman shared secret value consists of the x value o=
f
>>         the Diffie-Hellman common value.
>>
>> In fact RFC 5903 replaced 4753 just to say that the encoding consists on=
ly of x, not both x and y.
>>
>> This also relates to Dan't question. If the y value is missing, what is =
there to verify?
>>
>> Yoav
>>
>> On Nov 30, 2012, at 7:57 PM, Dan Harkins <dharkins@lounge.org> wrote:
>>
>>>
>>>    Hi Johannes,
>>>
>>> On Fri, November 30, 2012 4:11 am, Johannes Merkle wrote:
>>>> We have submitted a new revision of the Internet Draft on Using the=20
>>>> ECC Brainpool Curves (defined in RFC 5639) for IKEv2 Key Exchange=20
>>>> https://datatracker.ietf.org/doc/draft-merkle-ikev2-ke-brainpool/
>>>>
>>>> Since there was considerable objection to the point compression=20
>>>> method in the WG, we have removed this option altogether and define=20
>>>> only the uncompressed KE payload format, which is in full=20
>>>> accordance with RFC 5903.
>>>>
>>>>
>>>> Any feedback is welcome.
>>>
>>>    I see that there is a requirement that an implementation MUST=20
>>> verify that the D-H common value is not the point-at-infinity. Do=20
>>> you think there should also be a requirement that an implementation=20
>>> MUST verify that the x- and y-coordinates received from a peer=20
>>> satisfy the equation of the negotiated curve (and abort the exchange if=
 not)?
>>>
>>>    regards,
>>>
>>>    Dan.
>>
>> _______________________________________________
>> IPsec mailing list
>> IPsec@ietf.org
>> https://www.ietf.org/mailman/listinfo/ipsec
>> _______________________________________________
>> IPsec mailing list
>> IPsec@ietf.org
>> https://www.ietf.org/mailman/listinfo/ipsec
>>
_______________________________________________
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec