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
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
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
participants (4)
-
Brian A. LaMacchia -
Hal -
hughes＠ah.com -
Perry E. Metzger