Subject: [IPsec] Question on exponent size as discussed in RFC 3526

From: "Ricky Charlet" <[email-masked]>
Date: Wed, 27 May 2009 13:01:46 -0400

Hi folks,

	I'm having difficulty interpreting RFC3526, "More Modular
Exponential (MODP) Diffie-Hellman groups" section 1, "Introduction".
Quoting from the RFC

---------cut------------
The exponent size used in the Diffie-Hellman must be selected so that
   it matches other parts of the system.  It should not be the weakest
   link in the security system.  It should have double the entropy of
   the strength of the entire system, i.e., if you use a group whose
   strength is 128 bits, you must use more than 256 bits of randomness
   in the exponent used in the Diffie-Hellman calculation.
----------paste---------

Alright here... I'm trying to interpret what is meant, in very pragmatic
terms, by "exponent size".  I take the exponent to be the 'a' or 'b' in
the Diffie-Hellman calculations... That is the random number chosen by
each peer in an implementation specific way. 

What confuses me is the juxtaposition of the statement that it must be
double the size of the group but with examples given which are *far*
below sizes of even the weakest groups. In fact, the examples seem to
indicate a corilation with key sizes of symetric key ciphers/hmacs. 

So should a exponent size be double the size of the Diffie-Hellman "p",
or double the size of the symetric key? Or is there a formula for
"strength of group in bits" that I am missing?

In RFC 3766, "Determining Strengths for Public Keys", I found this:
---------cut--------------
 Because of
   Pollard's rho method, the search space in a DH key exchange for the
   key (the exponent in a g^a term), must be twice as large as the
   symmetric key.  Therefore, to securely derive a key of K bits, an
   implementation must use an exponent with at least 2*K bits.  See
   [ODL99] for more detail.
--------paste----------------

So I think I'm very close to answering my own question... The exponent
must be twice the size of the symentric key in use. I hesitate because
that is not quite what RFC3526 says ( "twice the size of the group" ). 

Any illumination would be appreciated.

--
Ricky Charlet 
[email-masked]
USA 408-495-5726

---

From: "Scott Fluhrer" <[email-masked]>
Date: Wed, 27 May 2009 13:48:56 -0400

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of Ricky Charlet
> Sent: Wednesday, May 27, 2009 1:02 PM
> To: [email-masked]; [email-masked]; [email-masked]; 
> [email-masked]; [email-masked]
> Subject: [IPsec] Question on exponent size as discussed in RFC 3526
> 
> Hi folks,
> 
> 	I'm having difficulty interpreting RFC3526, "More 
> Modular Exponential (MODP) Diffie-Hellman groups" section 1, 
> "Introduction".
> Quoting from the RFC
> 
> ---------cut------------
> Alright here... I'm trying to interpret what is meant, in 
> very pragmatic terms, by "exponent size".  I take the 
> exponent to be the 'a' or 'b' in the Diffie-Hellman 
> calculations... That is the random number chosen by each peer 
> in an implementation specific way. 

I don't know what you mean by 'a' or 'b'; there's no standard naming
convention for the various parts of the operation.  For phase 1, the
operation is:

  g ** e mod p

where:
  g is the generator listed in the RFC (for all groups listed in this RFC,
it is 2)
  p is the prime listed in the RFC
  e is a random exponent
  ** is the (modular) exponentiation operation

When you chose a random value e, you need to pick a value out of a range.
The "exponent size" is the number of random bits you use; that is, if you
pick a 200 bit exponent size, you would pick a random number between 1 and
2**200.

> 
> What confuses me is the juxtaposition of the statement that 
> it must be double the size of the group but with examples 
> given which are *far* below sizes of even the weakest groups. 
> In fact, the examples seem to indicate a corilation with key 
> sizes of symetric key ciphers/hmacs. 

The reason that the examples seem to indicate a correlation with the
symmetric key sizes is because there is a correlation with the symmetric key
sizes.  When attacking a system that uses DH to generate keys, the attacker
has three possible strategies to employ:

- Attack the generated symmetric keys directly
  For example, if the symmetric keys are 128 bit AES keys, the attacker can
brute force that with O(2**128) effort.

- Use a generic group attack based on the exponent length to recover the
private exponent
  If the attacker knows that one side picks N bit exponents, then the
attacker can recover that exponent in about O(2**(N/2)) work (see Pollard
Rho or Big Step/Little Step methods)

- Use a NFS-based attack to recover the exponent
  This attack recovers the private exponent with time dependant only on the
modulus

For the last one, well, we don't have any really good models on how long it
would take; the 'Strength Estimates' in section 8 reflect two different
guesses by various experts.

On the other hand, for picking exponent length, what we want to do is make
sure that it isn't the weakest part of the system; if we pick a length
that's double the symmetric key size, then we know that the attack based on
exponent length will take about as long as attacking the symmetric key
directly.  

> 
> So should a exponent size be double the size of the 
> Diffie-Hellman "p", or double the size of the symetric key?

Double the size of the symmetric key.  BTW: double the size of p would be
silly; it turns out that:

  x ** e mod p == x ** (e mod p-1) mod p

(This is known as "Fermat's Little Theorem", and is true for any x, e and
prime p).  So, if you pick an exponent larger than p, there's an equivilant
exponent smaller than p that does exactly the same thing, and would probably
work a lot faster.
 
> Or is there a formula for "strength of group in bits" that I 
> am missing?
> 
> 
> So I think I'm very close to answering my own question... The 
> exponent must be twice the size of the symentric key in use. 
> I hesitate because that is not quite what RFC3526 says ( 
> "twice the size of the group" ).

Actually, it's closer to "twice the size of the strength of the group".  The
"strength of the group" is its resistance to the attack #3 I have listed
(NFS).
 
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: "Ricky Charlet" <[email-masked]>
Date: Wed, 27 May 2009 14:57:36 -0400

Hi Scott,
	Thanks for your reply. Unfortunatly, your reply continues my
exact same confusion. Should e be twice the size of the key you need or
twice the size of the dh group in use? 

You state that 

> the reason that the examples seem to indicate a correlation with the
> sizes.  

And
> exponent length will take about as long as attacking the symmetric key

And
> silly; it turns out that:

These statements combine into a very forceful endorcement of the idea
that the exponent should be double the size of the key you need to
generate. 

> "strength of the group" is its resistance to the attack #3 I 

That really threw me. I have been taking the term "group" to mean the
size of the modp group in bits (which is basically the size of p). In
the context of the introdution section of RFC 3526, I'm pretty sure this
is what was meant: definition group = dh group. But you seem to have a
different defintion of 'group'?

--
Ricky Charlet 
[email-masked]
USA 408-495-5726 

> From: Scott Fluhrer [mailto:[email-masked]] 
> Sent: Wednesday, May 27, 2009 10:49 AM
> To: Charlet, Ricky (SC100:0000); [email-masked]; 
> [email-masked]; [email-masked]; 
> Subject: RE: [IPsec] Question on exponent size as discussed 
> in RFC 3526
> 
> 
>  
>

---

From: "Scott Fluhrer" <[email-masked]>
Date: Wed, 27 May 2009 16:53:49 -0400

> From: Ricky Charlet [mailto:[email-masked]] 
> Sent: Wednesday, May 27, 2009 2:58 PM
> To: Scott Fluhrer; [email-masked]; [email-masked]; 
> [email-masked]; [email-masked]; [email-masked]
> 	Thanks for your reply. Unfortunatly, your reply 
> continues my exact same confusion. Should e be twice the size 
> of the key you need or twice the size of the dh group in use? 

Twice the size of the key you need.

> > symmetric key sizes is because there is a correlation with the 
> > symmetric key sizes.
> 
> And
> > On the other hand, for picking exponent length, what we 
> want to do is 
> > make sure that it isn't the weakest part of the system; if 
> we pick a 
> > length that's double the symmetric key size, then we know that the 
> > attack based on exponent length will take about as long as 
> attacking 
> > the symmetric key directly.
> 
> And

No; the distinction you appear to be missing is that 'size of the group' !=
'strength of the group'.

'The size of the group' is, basically, p (well, actually, it's (p-1)/2,
because we're working in a subgroup of that size; that's only one bit less,
and so we can ignore it).

'The strength of the group' is how much effort it is to solve the discrete
log problem in that group.  This is considerably less than the size of the
group.

Now, for most symmetric ciphers, there's really no such distinction; an 128
bit AES key has a size of 128 bits and (to the best of our knowledge) it
takes about 2**128 trial decryptions to recover the key, and so it has a
strength of 128 bits.   Counterexample: 3DES, which has a key size of either
168 or 192 bits (depending on whether you count the ignored bits), and
appears to have a strength of about 112 bits (assuming you have access to a
huge amount of memory).

However, this isn't true for DH; the group size and the strength differ
widely.  For example, take DH group 14; that has a group size of 2048 bits;
however, using NFS, it is believed that you can recover a private exponent
after between 2**110 and 2**160 operations (and, yes, that's a large range;
no one is quite sure how NFS scales with a modulus that size), and so
appears to have a strength of between 110 and 160 bits.

---

From: "Ricky Charlet" <[email-masked]>
Date: Wed, 27 May 2009 16:57:19 -0400

Ah, thanks. You helped me tremedously there with the size-of-group vs
strength-of-group distinction.

Very much appreciated.

--
Ricky Charlet 
[email-masked]
USA 408-495-5726 

> Sent: Wednesday, May 27, 2009 1:54 PM