[1446] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Bill Frantz)
Tue Sep 9 16:45:43 1997
Date: Tue, 09 Sep 1997 12:27:31 -0700
To: cryptography@c2.net
From: Bill Frantz <frantz@communities.com>
First let me try to answer the direct questions and clear up the
misunderstandings my posts always seem to produce (sigh).
Lewis McCarthy <lmccarth@cs.umass.edu> wrote:
>Bill Frantz writes:
>> 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.
>
>Perhaps I misunderstand you. A private exponent with just 84 bits
>of entropy gives you only about 42 bits of strength versus a Pollard-
>style search of the exponent space, which is fairly worthless. 168 bits
>of strength throughout the system sounds like overkill. If you're
>aiming for that, each participant should use at least 336 bit exponents,
>and a modulus considerably larger than 1024 bits.
I would like to get a final real strength of about 90 bits. We are using
3DES as it is a conservative, well examined, way of getting 90 bits. Once
we have bought into 3DES, my view is that we might as well try to make the
3 keys independent to help cover errors in the random number generation or
other parts of the protocol. (On the other hand, the performance
requirements are also important, so I am looking for safe speed ups.)
>
>> 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.
>
>Um, do you mean the expected size of the second modexp base (i.e. the
>size of the public exponential received from the peer) ?
Yes. I don't see a hack to reduce the size of the exponent in the second
modExp. i.e. When Alice receives "Y = g**y mod p" from Bob and calculates
"secret = Y**x mod p".
>----------------------------------------
"Jon Leonard" <jleonard@divcom.umop-ap.com> wrote:
>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.
I was planning on taking the resulting secret and running it through SHA1
to generate 20 bytes for the 3 DES keys. I haven't figured how to get the
21st byte. I could do a second hash with different padding, or XOR the
bytes of the secret, or...
>----------------------------------------
Paulo Barreto <pbarreto@nw.com.br> writes:
>At 17:11 05.09.97 -0400, Lewis McCarthy <lmccarth@cs.umass.edu> wrote:
>As for the DH implementation, I'd suggest elliptic curves so that your keys
>are kept in a manageable size.
I would love to use elliptic curves. There are only a few problems: (1)
Many of the best elliptic systems are still patented. (2) I don't have a
clue about the math or how to implement it. (I'm still trying to read
"Elliptic Curve Cryptography".) Perhaps I can use it in version 2 of the
protocol.
----------------------------------------------
More general comments:
First a disclaimer: This next bit may be really stupid. I haven't played
mathematics in 35 years. My understanding of the notation and intuitions
are very rusty.
I don't quite see how limiting the range of x in the discrete log problem
of finding x = log-g(X) simplifies the Pollard algorithm. (I am using the
description of the algorithm in section 3.6.3 of Menezes et. al.'s
"Handbook of Applied Cryptography".)
Take as a concrete example:
the modulus of the group p is a 1024 bit prime.
x is an 84 bit number.
With modular exponentiation, the possible values of x do not form a group.
The values generated using Pollard's algorithm will range over all the
numbers 0<=n<p. As such, it will still have to search Order(sqrt(p))
operations.
There are a few other "features":
(1) Even the best choices of p (where (p-1)/2 is also prime) reveal 1 bit
of the shared secret. (If p-1 is devisable by 2**n, then n bits can be
recovered. The Pohlig-Hellman algorithm also allows you to take advantages
of the factors of p-1.)
(2) Eric Messick and I estimate that if you can store a bit on 10 carbon
atoms, the storage to hold a lookup table for the log with a range of 84
bits will weigh a bit over 1 metric ton and fit in a standard office. This
observation makes 84 bits scary for moderate time frames.
Phil Karn <karn@qualcomm.com> wrote:
>I made the exact same suggestion several years ago. At the time,
>nobody seemed to have a good answer. Diffie and Hellman both thought
>that making the secret exponent at least double the length of the
>eventual shared key should be safe from birthday attacks, but they
>emphasized this was mostly intuition. I didn't follow up on the issue,
>so I don't know if there have been any harder results since.
My final conclusion is that 84 bits is unsafe. 168 might be OK, but I
think I will chicken out and use 1024. Certainly unless awful performance
makes me re-visit the problem (where I will also consider making p smaller,
ugh).
Bill Frantz Electric Communities
Capability Security Guru 10101 De Anza Blvd.
frantz@communities.com Cupertino, CA 95014
408/342-9576 http://www.communities.com
