[1450] in cryptography@c2.net mail archive
Re: Speeding up DH
daemon@ATHENA.MIT.EDU (Colin Plumb)
Tue Sep 9 23:11:25 1997
Date: Tue, 9 Sep 1997 20:33:53 -0600 (MDT)
From: Colin Plumb <colin@nyx.net>
To: cryptography@c2.net, frantz@communities.com
> 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.)
Okay. 3DES gives (as far as I've heard - am I wrong?) 112 bits at least, and
more like 128 (given sane amounts of memory), so that's safe.
>>> 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".
If you choose x and y to be "small", then you can't use a small g (constant
speedup), but you still get the small-exponent advantage (linear in exponent
size).
> 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".)
You can recover x in about sqrt(x) steps. This is *not* sqrt(p)!
If you choose x to have a limited range starting at some x0, then you
can just divide the resultant X = g^x = g^(x0+x1) by g^x0 and solve for
the resultant X1 = g^x1. You you have to randomly choose from a range
twice as large as the desired security parameter (e.g. 160 for 80
bits).
> 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.)
If p-1 is divisible by k, for any small factor k, then x mod k is
revealed, assuming g is a generator. Choosing g not a generator is
equivalent to choosing x a multiple of k (for some divisors k),
so it renders the leak useless. Note that this leaks output bits
from your RNG, so if there are any weaknesses in your RNG, an attacker
can see them.
(I'm not sure what the difficulty of this is - it's O(k) or O(sqrt(k)).)
If you look in PGP 5, you'll see some precomputed primes with (p-1)/2
prime, and some on-the-fly code that generates p-1/2 = k*q for k "as
small as possible" while still ensuring that a multiple of q in the
right range will be prime. This bounds k small enough that the leakage
is contained within the paranoia padding, so we don't worry about
generator or not.
> (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.
Thus, you want 168 bits of exponent x, which corresponds to a p size
slightly over 1024.
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.
I haven't heard of any.
> 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).
My choice in PGP5 was to use 3*80 bits = 240 for the exponent. No
attack I know is better than sqrt(x), but that provides safety against
a hypothetical future cbrt(x) attack and isn't that big a hit.
You still get a 4x speedup.
--
-Colin
