[1425] in cryptography@c2.net mail archive
Re: Diffie Hellman timings
daemon@ATHENA.MIT.EDU (Jon Leonard)
Fri Sep 5 23:35:36 1997
To: frantz@netcom.com (Bill Frantz), cryptography@c2.net
Date: Fri, 5 Sep 1997 14:44:40 -0700 (PDT)
From: "Jon Leonard" <jleonard@divcom.umop-ap.com>
Cc: jleonard@divcom.umop-ap.com (Jon Leonard)
In-Reply-To: <v0300782ab0360ce85d81@[207.94.249.183]> from "Bill Frantz" at Sep 5, 97 12:25:03 pm
Bill Frantz wrote:
> Diffie Hellman requires 2 modular exponentations on each side for a key
> exchange. My preliminary testing indicates that if the exponent and
> modulus are both 1024 bits, this operation takes about a second on a 166
> MHz Pentium. A 1024 bit modulus and a 512 bit exponent take about 1/2
> second. I think the following argument will allow us to speed up the first
> modExp.
>
> Assume we are using Diffie Hellman to derive 3 independent keys for 3DES.
> For this use we need 56*3 ==> 168 bits of entropy. If each side
> contributes 84 bits of entropy, this allows us to limit the exponent of the
> first Diffie Hellman modular exponentation to 84 bits. The expected size
> for the second modExp exponent will be about the size of the modulus, so it
> will represent the bulk of the time.
>
> Does anyone have insight into the validity of the above argument. I.e., Is
> it safe?
This is not safe. Rather, it doesn't have as much security as you'd think
it would.
To start with, combining two things with limited entropy results in something
with less entropy than the sum of the input entropies. In the above example,
it takes more than 84 bits of entropy in each half to give 168 combined, and
you can't get all 168 bits of entropy out in a 168 bit chunk. Exploiting
this may take infeasable amounts of compute power, of course.
Combining the two 512 bit exponents using Diffie-Helman key exchange will
skew your resulting distribution, as well. In effect, the resulting
exponent is the product of the two, and will have the non-flat distribution
that results from multiplying two numbers chosen with (hopefully) flat
distribution. Again, I don't know how to exploit this, but it makes me
very nervous.
Unless you can find some expert cryptographer to give a non-obvious reason
why this would be secure, don't do it.
> -------------------------------------------------------------------------
> Bill Frantz | The Internet was designed | Periwinkle -- Consulting
> (408)356-8506 | to protect the free world | 16345 Englewood Ave.
> frantz@netcom.com | from hostile governments. | Los Gatos, CA 95032, USA
Jon Leonard
