Subject: [Cfrg] re-using Diffie-Hellman exponentials

From: "Dan Harkins" <[email-masked]>
Date: Wed, 7 Jan 2009 16:51:50 -0800 (PST)

Hi,

  There is an open issue in the IPsecme WG of the IETF about how to
reuse Diffie-Hellman exponentials "securely".

  A proposal has been made to increment the private value as a way
to quickly generate a new Diffie-Hellman exponential. For MODP
groups that would be multiplying the old exponential by the group's
generator, modulo the prime. For ECP groups it would be adding the
group's generator to the old exponential (point).

  An entity that employs this scheme should check the peer's exponential
for a small sub-group to prevent attack. The following check has also
been proposed:

  for MODP: perform the group operation on the peer's exponential and
            the order of the group-- if g^y is peer's exponential then
            check (g^y)^q, for order q-- and if the result is not 1
            then abort.

  for ECP: perform the group operation on the peer's exponential and
           the cofactor of the curve-- if Y is the peer's exponential
           (point) then check h*Y, for cofactor h-- and if the result
           is the "point at infinity" then abort.

Are these checks sufficient? Is there anything else that should be done?
What about characteristic-two curves? Same as ECP?

  regards,

  Dan.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Bodo Moeller" <[email-masked]>
Date: Thu, 8 Jan 2009 15:46:40 +0100

> group's generator to the old exponential (point).

Why would you be doing this rather than just continue to use the
prevoius DH value?  (The raw DH result between two parties that do
this will be the same, allowing for caching.  If you want to generate
new outputs as symmetric key material, you can just change other
inputs to the key derivation function.)

Bodo

---

From: <[email-masked]>
Date: Thu, 8 Jan 2009 17:17:11 +0200

> inputs to the key derivation function.)

At least I had always assumed that when RFC 4306 spoke about reusing
DH exponentials (in Section 2.12), it meant exactly this (just use the
previous x and g^x). The last paragraph also talks about both parties
doing it (storing previous g^y and g^xy) -- since the random nonces
(Ni and Nr) are also fed to the key derivation function, the resulting
keys SK_d etc. will be different.

Best regards,
Pasi

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 8 Jan 2009 10:29:05 -0800 (PST)

This also needs protection against a small sub-group attack though.
So the question remains. Are the checks I mentioned satisfactory?

  Dan.

---

From: "[email-masked]" <[email-masked]>
Date: Thu, 8 Jan 2009 23:11:38 +0200

> So the question remains. Are the checks I mentioned satisfactory?

Hmm -- I thought that all the MODP groups defined for IKEv2 were of
the form p=2q+1, so the small subgroup attack doesn't work?
(because there are no small subgroups)

For ECDH groups, something might be still needed, though. Does
e.g. X9.63 say something about this? (I don't have a copy)

Best regards,
Pasi

---

From: "Scott Fluhrer" <[email-masked]>
Date: Thu, 8 Jan 2009 16:46:39 -0500

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of [email-masked]
> Sent: Thursday, January 08, 2009 4:12 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: Re: [Cfrg] re-using Diffie-Hellman exponentials
> 
> Dan Harkins wrote:
> Hmm -- I thought that all the MODP groups defined for IKEv2 
> were of the form p=2q+1, so the small subgroup attack doesn't work?

Not quite, there are the groups 22, 23, 24 (defined in RFC 5114), which are
of the form p = mq + 1 (where q is 160-256 bits).  Whether there are any
small subgroups in those modulii (other than the trivial subgroups {1} and
{1, p-1}) depends on the factorization of m, and I don't know if that's
known.

> 
> For ECDH groups, something might be still needed, though. 
> Does e.g. X9.63 say something about this? (I don't have a copy)

I was under the impression that all the ECC curves defined for IKEv2 were of
prime order, and hence did not have any subgroups at all (other than the
trivial one consisting only of the point at infinity).  Can someone confirm
that?

---

From: Daniel Brown <[email-masked]>
Date: Thu, 8 Jan 2009 16:47:54 -0500

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Dan Harkins
> Sent: Wednesday, January 07, 2009 7:52 PM
> To: [email-masked]
> Subject: [Cfrg] re-using Diffie-Hellman exponentials
> 
> 

This check is neither sufficient nor necessary.

X9.63 and X9.62 and NIST SP 800-56A and SEC1 (and probably IEEE 1363 and ISO #####) do the following checks:

1. make sure the point Y is on the curve
2. make sure the point Y is not the point at infinity
3. check that n*Y is the point at infinity, where n is the order the generator

Check 3 is considered optional when the "cofactor DH" or MQV is used.  

For the ECP curves, cofactor h=1 so cofactor DH and standard DH are the same and therefore step 3 is optional.  Indeed, when cofactor h=1, step 1 and step 3 are equivalent.

> What about characteristic-two curves? Same as ECP?

For characteristic-two curves, step 3 is not equivalent to Step 1, so it is required for standard DH.

Best regards,

Dan Brown

---

From: Greg Rose <[email-masked]>
Date: Thu, 8 Jan 2009 14:10:07 -0800

> {1, p-1}) depends on the factorization of m, and I don't know if  

I believe the factorizations are known, but it doesn't really matter.  
The best way to check that you are not in a small subgroup is to check  
that you *are* in the correct subgroup, that is, check that x != 1 and  
x^q == 1.

Greg.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 8 Jan 2009 15:21:28 -0800 (PST)

> (because there are no small subgroups)

  Groups 22-24 are not p=2q+1.

> e.g. X9.63 say something about this? (I don't have a copy)

  I don't have a copy of that either.

  Dan.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 9 Jan 2009 19:07:21 -0500

Are we talking about adding these checks against small subgroup attacks to
IKE?
Or to some other protocol?

If it's IKE, why do you think you need these small subgroup checks?

IKE (both v1 and v2) does NOT require these checks.

You can read the formal analysis of these protocols and convince yourself
that the security proof works without resorting to these tests.

Or, if you want informal rationale, there are two elements in IKE that make
sure you do not need these (sometimes very costly) checks:

(1) In IKE the DH values exchanged by the parties are fully and explicitly
authenticated and hence an attacker cannot change them in transit to a small
subgroup (or anything else) without being detected

(2) If your peer to a session sends you an element in a small subgroup your
session key may be weak (predictable) but your long-term security and the
security of other sessions is NOT compromised at all. As for the session key
being weak in this case there is not much you can do about it: when you
share a key with a crook you cannot guarantee a strong key. For example,
that crook can use a DH value in the right group but with a fully
predictable DH exponent (such as one from the set 1, 2, 3,.., 10).

What makes sure in IKE that (2) is not a problem is that the DH
exponentation in IKE does NOT involve your own private key. This is the
source of problems in other protocols for which the small-subgroup tests are
othen required.

If you still see a reason to add these checks to IKE, please let me know.

Of course, if IKE is changed to something else such as EC-DH or MQV, the
story may be different.

Hugo

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 9 Jan 2009 16:49:08 -0800 (PST)

Hi Hugo,

  It was my (possibly incorrect) understanding that an attacker who
chose an exponent from a small subgroup whose order v << q (where q is
the order of the group) in an exchange with me could iterate through
0...v and determine my private key mod v. After a few such attacks
using different orders that are relatively prime (using possibly
different sub-groups) my entire private key can be recovered.

  If that's the case then that attacker would be able to obtain the
session key for any other past or future exchange I had with other
parties in which I reused my DH exponential.

  Therefore, I thought it would be prudent to do this check if DH
exponentials were being reused. I'm not proposing this check in the
case where your private value is distinct and random each time, just
when the DH exponential is reused.

  If my understanding of this issue is wrong please let me know.
Also, I do not understand this sentence, "the DH exponentation in IKE
does NOT involve your own private key." What does it involve then?

  regards,

  Dan.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 9 Jan 2009 20:04:48 -0500

I see. Sorry for the misunderstanding.
I came into the middle of the discussion, read your msg,  and did not notice
that the setting was the reusing of DH values (even though the subject of
the thread should have been an indication that that was the case :)
Anyway, exponent reuse does require testing for small orders (except if the
cofactor is very small)

In general, it is better to resist the temptation of reusing exponents. in
some cases a better alternative may be to producee different DH values (and
store the exponents) off-line to avoid the need to generate them in real
time.

Hugo