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: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org] 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; > rfc-...@rfc-editor.org; 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: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org] 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; > rfc-...@rfc-editor.org; 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:yaronf.i...@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. >> Turner; Dan Harkins; rfc-...@rfc-editor.org >> 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: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org] 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; >>> rfc-...@rfc-editor.org >>> 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 <dhark...@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 >>>>> 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 >>> 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 > _______________________________________________ > IPsec mailing list > IPsec@ietf.org > 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 +49 201 54 54-3091 Telefax +49 201 54 54-1325 Mobil +49 175 2224439 johannes.mer...@secunet.com www.secunet.com _______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec