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

From: Yaron Sheffer <[email-masked]>
Date: Sat, 01 Dec 2012 12:31:49 +0200

Actually, I think we have it wrong. There is no reason for a *valid* 
peer to send an incorrect KE. And IKEv2 already protects against a MITM 
doing such a thing. As we all know, the protocol assumes that 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 
security 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 algorithm:
>
> - There's the public value xG (where x is our secret); this is passed 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 generation function) will be only the x coordinate; the y coordinate will not be used.
>
> Yes, this implies that doing point compression on the shared secret value 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 secret value; instead, it was about the repesentation that appeared in the KE payload (that is, the one that is specified to have both the x and y coordinates).
>
> As for Dan's question, it was about whether we should validate the public value we get from the peer, well, the public value does have explicit x and y coordinates, and so it makes sense to check them.
>
>
> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 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; [email-masked]
> Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 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 of
>        the Diffie-Hellman common value.
>
> In fact RFC 5903 replaced 4753 just to say that the encoding consists only 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 <[email-masked]> 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
>>> ECC Brainpool Curves (defined in RFC 5639) for IKEv2 Key Exchange
>>> https://datatracker.ietf.org/doc/draft-merkle-ikev2-ke-brainpool/
>>>
>>> Since there was considerable objection to the point compression
>>> method in the WG, we have removed this option altogether and define
>>> only the uncompressed KE payload format, which is in full accordance
>>> with RFC 5903.
>>>
>>>
>>> Any feedback is welcome.
>>
>>   I see that there is a requirement that an implementation MUST verify
>> that the D-H common value is not the point-at-infinity. Do you think
>> there should also be a requirement that an implementation MUST verify
>> that the x- and y-coordinates received from a peer satisfy the
>> equation of the negotiated curve (and abort the exchange if not)?
>>
>>   regards,
>>
>>   Dan.
>
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sat, 1 Dec 2012 18:44:34 +0000

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 implementation; let us call this bogus point P, and its small order n.  We would then generate sk's based on the point (e mod n)P (where e is the value of our ECDH secret); because n is small, that allows the attacker to recover the value (e mod n).

If we reuse the same ECDH secret for multiple exchanges (which is normally safe), this allows someone who controls some of the peers we talk to to recover 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:[email-masked]] 
Sent: Saturday, December 01, 2012 5:32 AM
To: Scott Fluhrer (sfluhrer)
Cc: Yoav Nir; Johannes Merkle; IPsecme WG; Manfred Lochter; Sean P. Turner; Dan Harkins; [email-masked]
Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Exchange

Actually, I think we have it wrong. There is no reason for a *valid* peer to send an incorrect KE. And IKEv2 already protects against a MITM doing such a thing. As we all know, the protocol assumes that 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 security 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:
>>   I see that there is a requirement that an implementation MUST 
>> verify that the D-H common value is not the point-at-infinity. Do you 
>> think there should also be a requirement that an implementation MUST 
>> verify that the x- and y-coordinates received from a peer satisfy the

---

From: Yaron Sheffer <[email-masked]>
Date: Sat, 01 Dec 2012 21:28:48 +0200

Hi Scott,

OK, I see your point (no pun intended). Regarding ECDH secret reuse, can 
you please review http://tools.ietf.org/html/rfc5996#section-2.12. That 
section was supposed to cover the relevant security considerations. In 
fact I think 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 needs to be spelled out and not left as an exercise to the reader. 
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 sessions.

Thanks,
	Yaron

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 03 Dec 2012 11:52:16 +0100

Hi Yaron,

> 
> OK, I see your point (no pun intended). Regarding ECDH secret reuse, can you please review
> http://tools.ietf.org/html/rfc5996#section-2.12. That section was supposed to cover the relevant security
> considerations. In fact I think your attack is alluded to in the paper we reference from that section (see Sec. 5, first
> paragraph).
> 

I agree with you that this is a general issue that should be addressed generally. Yet, as a precaution, I could also
include such a requirement in the current draft.

> If this needs to become a MUST requirement for IKEv2 peers using ECDH, it needs to be spelled out and not left as an
> exercise to the reader. 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 sessions.
> 

If the ECDH key is chosen at random for each negotiation, then the attacker can only gain knowledge on the shared secret
and private key of the current negotiation. There is no other secret information involved that could be learned.

Johannes

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 3 Dec 2012 14:47:54 +0200

Johannes Merkle writes:
> > http://tools.ietf.org/html/rfc5996#section-2.12. That section was
> > supposed to cover the relevant security considerations. In fact I
> > think your attack is alluded to in the paper we reference from
> I agree with you that this is a general issue that should be
> addressed generally. Yet, as a precaution, I could also include such
> a requirement in the current draft.

Looking at the ECDH problems there seems to be in specifications (i.e.
what checks are needed, RFC5114 refering to wrong RFC (it should refer
to 5903 not 4753) etc, it seems we need to do something for this. I do
not think it is good idea to include this kind of things as errata.
Also I do not think we should include generic ECDH processing rules in
to the draft specifying some EC groups.

I think it would be best to take the ECDH processing rules (mostly
from 5903 but also add the checks if those are needed) and create new
RFC that will update 5996. This document should not include any
groups.

Then the question is what to do to 5114. The 5114 points to the 4753
and there is the problem that 4753 was modified with errata. This
means that 5114 is also affected by the same errata, meaning complient
implementatation should follow the same errata, i.e. the same format
that is defined in the 5903.

We should have made that 5903 to include also the 2 other groups from
the 5114, i.e. groups 25 and 26, and we really should have obsoleted
ALL ECP groups (19-21, 25-26) and allocated new numbers for all of
those. 

If that new document includes all ECDH processing rules, perhaps that
can be made to update all previous ECDH RFCs, and it can say all ECDH
curves use exactly same processing rules?
-- 
[email-masked]

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 3 Dec 2012 14:27:50 +0000

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 needed.  It does refer to the Menezes and Ustaoglu paper, which is quite good, however, it would be better if you spell out exactly what tests the implementer would need to run for each IKE group.  An implementation might have problems determining from the paper what is appropriate; for example, groups 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 labeled 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 check 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 leakage from a small subgroup attack (see section 2.1 of the paper); hence, you need to check both that the peer's public value is in range (1 < r < p-1) and that r**q = 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 peer's public value satisfies the curve equation, that is, y**2 = x**3 + ax + b mod p.  Note that even though the paper specifically targets odd characteristic EC curves, their advice of checking the curve equation is equally applicable to even characteristic curves as well. 

Now, as for whether checking the peer's public value ought to be a requirement, even if you aren't reusing private keys, I would still say that it ought 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, points that are actually on the curve).  If you just take bit patterns you received 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 happen to be valid.  If the implementation uses the standard textbook point addition/doubling code, we can predict what will happen -- however, a specific 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 the cost of doing the ECDH phase two), I would strongly urge anyone to do this check.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Yaron Sheffer
Sent: Saturday, December 01, 2012 2:29 PM
To: Scott Fluhrer (sfluhrer)
Cc: Johannes Merkle; Manfred Lochter; Yoav Nir; Dan Harkins; IPsecme WG; [email-masked]; Sean P. Turner
Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Exchange

Hi Scott,

OK, I see your point (no pun intended). Regarding ECDH secret reuse, can you please review http://tools.ietf.org/html/rfc5996#section-2.12. That section was supposed to cover the relevant security considerations. In fact I think 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 needs to be spelled out and not left as an exercise to the reader. 
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 sessions.

Thanks,
	Yaron

On 12/01/2012 08:44 PM, Scott Fluhrer (sfluhrer) wrote:
> Cc: Yoav Nir; Johannes Merkle; IPsecme WG; Manfred Lochter; Sean P. 
> Turner; Dan Harkins; [email-masked]
> peer to send an incorrect KE. And IKEv2 already protects against a 
> MITM doing such a thing. As we all know, the protocol assumes that 
> messages
>>>> only the uncompressed KE payload format, which is in full 
>>>> accordance with RFC 5903.
>>>>
>>>>
>>>> Any feedback is welcome.
>>>
>>> verify that the D-H common value is not the point-at-infinity. Do 
>>> you think there should also be a requirement that an implementation 
>>> MUST verify that the x- and y-coordinates received from a peer 
>>> satisfy the equation of the negotiated curve (and abort the exchange if not)?
>>>
>>>    regards,
>>>
>>>    Dan.
>>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 3 Dec 2012 14:39:18 +0000

Sigh, immediately after sending this, I remembered that even characteristic EC curves tend to have cofactors h>1, hence there is further checking required for them.  Scratch what I said that the what I said for odd characteristic EC curves applies to even as well -- that checking is necessary, but it is not sufficient.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Yaron Sheffer
Sent: Saturday, December 01, 2012 2:29 PM
To: Scott Fluhrer (sfluhrer)
Cc: Johannes Merkle; Manfred Lochter; Yoav Nir; Dan Harkins; IPsecme WG; [email-masked]; Sean P. Turner
Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Exchange

Hi Scott,

Thanks,
	Yaron

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 07 Dec 2012 11:49:55 +0100

Hi Scott,

> Sigh, immediately after sending this, I remembered that even characteristic EC curves tend to have cofactors h>1, hence there is further checking required for them.  Scratch what I said that the wh…

After having verified that the point (x,y) = P satisfies the curve equation and is not the point at infinity O, checking
n*P = O is sufficient. If the cofactor h is 1 then this last check is not even necessary. The validation algorithm is
defined in detail in SEC1, Section 3.2.2.1. This reference should be used for the validation requirements.

Checking n*P = O is costly, but fortunately, all NIST and Brainpool curves have cofactor 1 making this check uneccesary.

BTW: The check n*P = O can be omitted even for non-trivial cofactor, if h*P is used as public DH key instead of P, i.e.
if the Elliptic Curve Cofactor Diffie-Hellman Primitive described in Section 3.3.2 of SEC1 is used.

Johannes

-- 

Mit freundlichen Grüßen,
Johannes Merkle

Biometrie & Hoheitliche Dokumente
secunet Security Networks AG
Mergenthaler Allee 77
65760 Eschborn
Germany
Telefon +49 201 54 54-3091
Telefax +49 201 54 54-1325
Mobil   +49 175 2224439
[email-masked]
www.secunet.com

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 07 Dec 2012 11:52:00 +0100

Hi Tero,

> RFC that will update 5996. This document should not include any
I assume that my draft should refer to this RFC-to-be, right?

-- 
Johannes

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 07 Dec 2012 13:20:18 +0100

Hi Scott,

> - 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 check needed is a verification that the peer's public value r is in range (1 < r < p-
> 

For MODP groups, we can just refer to RFC 2631, Section 2.1.5

> - 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…
As I said in my earlier mail, we could refer to SEC1, Section 3.2.2.1

> Now, as for whether checking the peer's public value ought to be a requirement, even if you aren't reusing private keys, I would still say that it ought to be.  If we look at the ECDH point additio…

In general, the potential information leakage does not depend on the implementation. In case of ephemeral DH keys all
secret information involved in the DH-KE (the private DH key) is renewed in every execution. Thus, all that can be
learned is only relevant for the current session. And this information is known to the sending peer anyway.

However, if there is any statistical dependence between the private DH keys of different executions, the above argument
is not valid anymore. Thus, the validation of the H-key is necessary as soon as complete independence is not ensured,
e.g. by deploying an (P)RNG with insufficient entropy. The dependences should not be exploitable for attacks in case
that strong PRNG are used. But since you can not be certain about the security of a practical PRNG (its entropy source
or internal state may be influenced or leaked) it is always advisable to perform the public key validation.

Johannes

-- 

Mit freundlichen Grüßen,
Johannes Merkle

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 07 Dec 2012 14:47:51 +0200

Hi Johannes,

Scott and I are working on this draft. You can expect an initial version 
within a week.

Thanks,
	Yaron

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 7 Dec 2012 16:03:55 +0200

> I assume that my draft should refer to this RFC-to-be, right?

Most certainly, if we can agree to make such RFC, and get it published
fast enough. The question is, whether there is enough interest to make
such RFC, and who would be willing to work on such document. 
-- 
[email-masked]

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 7 Dec 2012 14:28:12 +0000

Well, no; step 2 of the check is unnecessary for the standard IKE groups (1, 2, 5, 14-18), and it is extremely expensive as written; and while there are optimizations possible, it's still not cheap.