Re: D-H key exchange - how does it work?

The problem with "strong" primes, primes for which (p-1)/2 is prime, is
that they are hard to find.  It takes hours and hours of searching to find
a 1024 bit strong prime on a workstation.  Granted, you don't need to change
very often perhaps, but some people would like to change every day.  They
may need a dedicated prime-searching machine to do that.

(The best way I know to find strong primes is to find a prime q and then
check 2q+1 for primality.  Finding 1024 bit primes takes a long time, and
the chances that 2q+1 is prime is very low.)

It's much easier to find a "strongish" prime, one for which (p-1)/k is
prime, where k is on the order of 100 or so.  Take your prime q in the above
and try kq+1 for k=2,4,6,....  This only takes a few minutes after you find
q.

The question is, how good are strongish primes?  What fraction of elements
of the group will have short periods, given that p-1 has a pretty small
number of prime factors?

Also, given a strong or strongish prime, are the chances that
g^x has a small period good enough that it makes sense to check for that
case?  Any event whose chances are smaller than your computer making a
mistake is generally not worth checking for.

Hal

It takes hours and hours of searching to find
   a 1024 bit strong prime on a workstation.  Granted, you don't need to change
   very often perhaps, but some people would like to change every day.  

If they really want to change that often, they can buy a dedicated
machine.  There's no good cryptographic reason to change that often,
if the modulus is large enough.  In addition, changing the modulus can
have unpleasant effects on traffic analysis, if not done properly.

   (The best way I know to find strong primes is to find a prime q and then
   check 2q+1 for primality.  Finding 1024 bit primes takes a long time, and
   the chances that 2q+1 is prime is very low.)

Well, there are faster ways.  One can combine the sieve for q with a
sieve for p.  The biggest problem is that there are just a lot fewer
primes with the above property.

   The question is, how good are strongish primes?  

Just fine.  The complexity of taking discrete logs is dependent on the
largest prime factor of the modulus.

   What fraction of elements
   of the group will have short periods, given that p-1 has a pretty small
   number of prime factors?

If q is the largest prime factor, then about p/q will have short
periods, namely, those divisible by q.  When p=2q+1, there is one
element of order 1 (namely 1), one element of order 2 (namely -1, aka
2q), and every other element has order 2q or q.  For primes of the
form p=kq+1, there are about k with short periods.

Eric

Eric Hughes says:
>    It takes hours and hours of searching to find a 1024 bit strong
>    prime on a workstation.  Granted, you don't need to change very
>    often perhaps, but some people would like to change every day.
> 
> If they really want to change that often, they can buy a dedicated
> machine.  There's no good cryptographic reason to change that often,
> if the modulus is large enough.

I dunno. The paper by LaMacchia and Odlysko on how to break
Diffie-Hellman quickly once you've done a lot of precomputation on a
static modulus is sufficiently disturbing to me that I would prefer to
be able to change modulii fairly frequently if possible. If the
opponent knows a way thats a constant factor of a few tens of
thousands cheaper to do discrete logs, it might be worth their while
to spend a large sum on doing that precomputation once in the hopes of
breaking lots of traffic.

> In addition, changing the modulus can have unpleasant effects on
> traffic analysis, if not done properly.

Of what sort?

> Just fine.  The complexity of taking discrete logs is dependent on the
> largest prime factor of the modulus.

It is BELIEVED dependent -- lets be precise...

Perry

I dunno. The paper by LaMacchia and Odlysko on how to break
   Diffie-Hellman quickly once you've done a lot of precomputation on a
   static modulus is sufficiently disturbing to me that I would prefer to
   be able to change modulii fairly frequently if possible.

Quoting K. McCurley about the above mentioned work: "Their experience
seems to suggest that it is possible to compute discrete logarithms in
groups GF(p)^* with p \wavyequals 10^100." [in _The Discrete Logarithm
Problem_, collected in _Cryptology and Computational Number Theory_]

The security of a 1000-bit modulus is just fine, thank you very much.
Some military applications evidently use twice that, though.  You need
to change it as often as you change RSA keys.  Since you can factor if
you can take discrete logs, you've got to worry about the security of
your RSA keys at the same time.

   > In addition, changing the modulus can have unpleasant effects on
   > traffic analysis, if not done properly.

   Of what sort?

For D-H, the modulus must be transmitted in the clear.  Unless you use
a different modulus for each conversation, there is a persistency to
the moduli that gives rise to a pseudo-identity.

Eric

Eric Hughes says:
>    > In addition, changing the modulus can have unpleasant effects on
>    > traffic analysis, if not done properly.
> 
>    Of what sort?
> 
> For D-H, the modulus must be transmitted in the clear.  Unless you use
> a different modulus for each conversation, there is a persistency to
> the moduli that gives rise to a pseudo-identity.

You don't HAVE to transmit the modulus in the clear. Its often
worthwhile to use D-H for key exchange even if both sides know the
other's RSA public keys. Why? Because then the keys used for
conventional session encryption need not be compromised for historical
traffic even if the RSA keys are later compromised.

Perry

> For D-H, the modulus must be transmitted in the clear.  Unless you use
   > a different modulus for each conversation, there is a persistency to
   > the moduli that gives rise to a pseudo-identity.

   You don't HAVE to transmit the modulus in the clear. 

But we were talking about changing moduli and its effect on traffic
analysis.  If you change the modulus each conversation, you have two cases:

  1. Transmit before the conversation
  2. Transmit at the beginning of the conversation

For case 1., you could, conceivably, transmit the modulus for the next
exchange in a previous (encrypted) conversation, but that introduces
lots of system complexity, state, and general nastiness.  If the
modulus is previously transmitted unencrypted, then we're back to the
beginning.

For case 2., you can transmit the modulus in the clear or encrypted.
If in the clear, then you have the TA issues as before.  If encrypted,
you need some method of generating an encryption key, like D-H, which
we're trying to do.  So you could use a fixed modulus to encrypt for a
second exchange; that's slow, and when the modulus goes, you reveal
the same TA data as before.  If you don't use D-H, and, say, public
key derived things are used, then you even more directly reveal TA.

The above analysis is not very rigorous.  It merely points out where
some of the problems are.

   Its often
   worthwhile to use D-H for key exchange even if both sides know the
   other's RSA public keys. 

It's called forward secrecy.  Sure.  But the issue at hand is TA.

Eric

Date: Fri, 20 May 94 09:55:36 -0700
   From: hughes@ah.com (Eric Hughes)
   Sender: owner-cypherpunks@toad.com
   Precedence: bulk

      I dunno. The paper by LaMacchia and Odlysko on how to break
      Diffie-Hellman quickly once you've done a lot of precomputation on a
      static modulus is sufficiently disturbing to me that I would prefer to
      be able to change modulii fairly frequently if possible.

   Quoting K. McCurley about the above mentioned work: "Their experience
   seems to suggest that it is possible to compute discrete logarithms in
   groups GF(p)^* with p \wavyequals 10^100." [in _The Discrete Logarithm
   Problem_, collected in _Cryptology and Computational Number Theory_]

Right.  Basically, what we found was that you needed the same amount of
computation to factor a (k+10)-digit composite as to compute discrete
logarithms in a field with k-digit modulus p.  The discrete log problem
is brittle---you do a lot of precomputation for a particular modulus p
and then finding individual discrete logs in GF(p) is easy---so you
need to think carefully about the lifetime of the information you're
going to encrypt and choose the size of your modulus accordingly.

					--bal