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
> 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
> Double the size of the symmetric key. BTW: double the size
> of p would be
> 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.
Yet in your last statement you also said:
> 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).
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
rchar...@nortel.com
USA 408-495-5726
> -----Original Message-----
> From: Scott Fluhrer [mailto:sfluh...@cisco.com]
> Sent: Wednesday, May 27, 2009 10:49 AM
> To: Charlet, Ricky (SC100:0000); ipsec@ietf.org;
> kivi...@ssh.fi; mika.k...@helsinki.fi;
> hila...@purplestreak.com; paul.hoff...@vpnc.org
> Subject: RE: [IPsec] Question on exponent size as discussed
> in RFC 3526
>
>
>
>
> > -----Original Message-----
> > From: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org]
> > On Behalf Of Ricky Charlet
> > Sent: Wednesday, May 27, 2009 1:02 PM
> > To: ipsec@ietf.org; kivi...@ssh.fi; mika.k...@helsinki.fi;
> > hila...@purplestreak.com; paul.hoff...@vpnc.org
> > 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------------
> > 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.
>
> 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?
> >
> >
> > 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" ).
>
> 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).
>
> >
> >
> > Any illumination would be appreciated.
> >
> >
> > --
> > Ricky Charlet
> > rchar...@nortel.com
> > USA 408-495-5726
> > _______________________________________________
> > 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
