Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

[Dan Brown <[e-mail]>]

> From: Cfrg <[e-mail]> On Behalf Of Michael D'Errico
>
> If the length of your Diffie-Hellman secret exponent is on the order of the
> number of bits of security you are trying to achieve, then it's too short.

Yes, but that's already well-known.  Doubling the number of bits avoids 
various square-root time attacks such as Shank's baby-step-giant-step and 
Pollard rho/lambda attacks (e.g. kangaroo). E.g. 256 bit keys for 128-bit 
security.

> If you count the number of trailing one bits and call this M, then brute 
> force
> finding the secret takes 1/M the time you would expect.

Is your "attack" generic enough to work against composite N?  If so, then 
consider the next speculative argument.

Any given P should divide a composite number N with M trailing one bits, e.g. 
N = P(-1/P mod 2^M), right?  Finding a discrete log mod N allows finding them 
mod P, by reducing the logs mod P-1.

Of course, N is larger, so logs mod N should naturally take little longer than 
in mod P, but is it by a factor log2(M)?

Well, if the key sizes are fixed at K bits, then exhaustive search or Pollard 
rho-type attacks (respectively) should take the same number of mod P or mod N 
operations, 2^K or 2^(K/2) (respectively).  The runtime factor in modular 
arithmetic (between N vs P) is something like 1+log2(M)/log2(N), which seems 
smaller than log2(M).  So, if generic, then your attack should affect all P 
almost equally, right?

> This translates to a loss of log2(M) bits of security of the secret.
As already explained so well by Mike H., brute force attacks do not define the 
security of Diffie--Hellman, because there are better attacks.  Even your 
hypothetical sped-up exhaustive search would still be slower than Pollard rho 
variants or number field sieve (unless the keys have <=2log2(M) bits).

You do not claim to speed up Pollard rho or NFS, right?

If so, the best attacks are unchanged (AFAICT), and thus security is 
unchanged, right?

> As an example, if you have a requirement that your secret exponent X can not
> be determined in 2^64 operations and assume you can just generate a random
> 64-bit number to use as the Diffie-Hellman exponent, and if you are using 
> any
> of the published MODP or FFDHE parameters, then your secret is actually only
> giving you about 58 bits of security.  (This revised estimate may be 
> optimistic.)

It gives 32 bits of security, due to Shank's baby-step giant-step algorithm, 
which takes about 2^32 operations mod P, noticeably less than 2^58 ops.


----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.