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

[Johannes Merkle <[e-mail]>]

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 what I said for odd characteristic EC curves applies to even as well -- that checking is necessary, but it is not sufficient.
> 

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

> -----Original Message-----
> From: [e-mail] [mailto:[e-mail]] On Behalf Of Scott Fluhrer (sfluhrer)
> Sent: Monday, December 03, 2012 9:28 AM
> To: Yaron Sheffer
> Cc: Johannes Merkle; Manfred Lochter; Yoav Nir; Dan Harkins; IPsecme WG; [e-mail]; Sean P. Turner
> Subject: Re: [IPsec] I-D on Using the ECC Brainpool Curves for IKEv2 Key Exchange
> 
> 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: [e-mail] [mailto:[e-mail]] 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; [e-mail]; 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:
>> 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:[e-mail]]
>> 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; [e-mail]
>> 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:
>>> 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: [e-mail] [mailto:[e-mail]] 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; 
>>> [e-mail]
>>> 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 <[e-mail]> 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
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/ipsec
>>> _______________________________________________
>>> IPsec mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/ipsec
>>>
> _______________________________________________
> IPsec mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ipsec
> _______________________________________________
> IPsec mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/ipsec
> 
> 


-- 

Mit freundlichen Grüßen,
Johannes Merkle

Biometrie & Hoheitliche Dokumente
secunet Security Networks AG
Mergenthaler Allee 77
65760 Eschborn
Germany
Telefon [phone]
Telefax [phone]
Mobil   [phone]
[e-mail]
www.secunet.com