Re: Some stuff about Diffie-Hellman (and more :-)
Quite a few misconceptions here, I'm afraid: From: rcain@netcom.com (Robert Cain)
In the Diffie-Hellman exchange there is a well-known-prime, w, and a well-knwon-modulus, m.
w is supposed to be a "generator" of the group of integers mod m. It does not have to be prime. It is supposed to be such that the series w**0, w**1, w**2,...,w**m-1 does not repeat but goes through all the integers less than m. Testing for such w's is pretty easy if you know the factorization of m, involving a few arithmetic tests.
For those interested that don't know I think it then proceeds as follows (don't have notes in front of me so please someone correct me if I'm misremembering it) where ** is the power or exponentiation operator and % is the modulus operator:
1) Bob generates a one time random prime, b, then computes
b does not have to be prime; it is a random number less than m.
B = (w ** b) % m and sends B to Carol.
2) Carol generates a one time random prime, c, then computes
Likewise, c does not have to be prime; it is a random number less than m.
C = (w ** c) % m and sends C to Bob.
3) Bob generates a session key:
Carol does this, not Bob.
K = (B ** c) % m
4) Carol generates a session key:
Bob does this, not Carol.
K = (C ** b) % m [...] Now, the tutorial over :-), the question is; is there a "standard" well-known-prime, w, and a "standard" well-known-modulus, m, and if
^^^^^-- generator
not, let's define one.
I don't think there is a need for this. The two sides need to agree on a pair but they could just pick it at the beginning. If everyone uses the same m,w it would help attackers of the scheme to focus their efforts on these numbers. I believe there was some discussion of using well-known numbers in the Digital Signature Standard (which is based on the same problem as DH) but I don't know what the resolution was.
I suppose that PGP uses a well known pair but they are big and not easy to hand around without going through media (I think.)
PGP does not uses DH and has no well known numbers. If you do want well known numbers, I really think it will not be that bad just to put them into the program. Coming up with an algorithm to choose and test a generator from scratch is probably going to be larger and certainly going to be far slower than just hard-wiring the number in. Hal
Hal says:
From: rcain@netcom.com (Robert Cain)
Now, the tutorial over :-), the question is; is there a "standard" well-known-prime, w, and a "standard" well-known-modulus, m, and if ^^^^^-- generator not, let's define one.
I don't think there is a need for this. The two sides need to agree on a pair but they could just pick it at the beginning. If everyone uses the same m,w it would help attackers of the scheme to focus their efforts on these numbers.
Indeed, a paper has been published on how to break Sun Secure RPC based on the idiotic decision by someone at Sun to standardise the modulus used. It is basically a matter of precomputing a lot of data based on the numbers which allows you to break any particular discrete log in that field on the fly. The suggestion by Mr. Cain to use a single generator and modulus for all traffic is astonishingly naive. Perry
Indeed, a paper has been published on how to break Sun Secure RPC based on the idiotic decision by someone at Sun to standardise the modulus used.
It wasn't standardization that was the problem. The Sun modulus was just too small. My take on the idiocy was that the designers were assuming that because they didn't know how to break such a large modulus, that no one else did either.
The suggestion by Mr. Cain to use a single generator and modulus for all traffic is astonishingly naive.
It's not naive (as such), it's just that any such modulus must be chosen with extreme care. Here are some very basic rules of thumb: -- Don't use a 2^k modulus. In addition to the exponentiation taking place faster, they're much easier to break. -- Use a single large prime p for the modulus of size > 600 bits. -- Make sure that you can prove that your generator actually generates the group. This requires knowing the factors of p-1. Burt Kaliski told me that he picked a D-H modulus by searching for a pair of primes < q, p=2q+1 >. It took a _long_, _long_ time, but it was then easy to show that the element 2 generated the group. It may be that there is a clever attack based on the generator 2, but I haven't seen one published. Eric
Eric Hughes says:
Indeed, a paper has been published on how to break Sun Secure RPC based on the idiotic decision by someone at Sun to standardise the modulus used.
It wasn't standardization that was the problem. The Sun modulus was just too small. My take on the idiocy was that the designers were assuming that because they didn't know how to break such a large modulus, that no one else did either.
Standardization was also a problem. It meant that the effort to break one exchange could be used to break all of them at once. This seems like a very bad thing. Perry
Perry E. Metzger sez:
Indeed, a paper has been published on how to break Sun Secure RPC based on the idiotic decision by someone at Sun to standardise the modulus used. It is basically a matter of precomputing a lot of data based on the numbers which allows you to break any particular discrete log in that field on the fly. The suggestion by Mr. Cain to use a single generator and modulus for all traffic is astonishingly naive.
Now wait a minute, Perry. If a device is going to use other than a set of known moduli or even just one, how are two devices going to each know what the other is using without a listner knowing? I think it is pretty much agreed that devices that use "secret" numbers are not very practical. What you say seems to indicate that D-H as we know and love it has been rendered obsolete because it depends on the modulus being known. What am I missing? Peace, Bob -- Bob Cain rcain@netcom.com 408-354-8021 "I used to be different. But now I'm the same." --------------PGP 1.0 or 2.0 public key available on request.------------------
Robert Cain says:
Perry E. Metzger sez:
Indeed, a paper has been published on how to break Sun Secure RPC based on the idiotic decision by someone at Sun to standardise the modulus used. It is basically a matter of precomputing a lot of data based on the numbers which allows you to break any particular discrete log in that field on the fly. The suggestion by Mr. Cain to use a single generator and modulus for all traffic is astonishingly naive.
Now wait a minute, Perry. If a device is going to use other than a set of known moduli or even just one, how are two devices going to each know what the other is using without a listner knowing?
You don't care if a listener hears the information on the modulus and generator. It doesn't matter. You can broadcast it in the clear. The point I was making was that if you always use the same modulus the attacker can expend the effort to attack your modulus just once and can then crack individual D-H sessions trivially. If you change each time, you can't be attacked in this way. .pm
Perry E. Metzger sez:
You don't care if a listener hears the information on the modulus and generator. It doesn't matter. You can broadcast it in the clear.
Ah. Now I understand what you meant.
The point I was making was that if you always use the same modulus the attacker can expend the effort to attack your modulus just once and can then crack individual D-H sessions trivially. If you change each time, you can't be attacked in this way.
Good idea. Think I'll steal it. I'll just let the little beastie search for good ones while it isn't doing anything else and isn't running off its batteries. :-) Peace, Bob -- Bob Cain rcain@netcom.com 408-354-8021 "I used to be different. But now I'm the same." --------------PGP 1.0 or 2.0 public key available on request.------------------
Hal sez:
Quite a few misconceptions here, I'm afraid:
That'll teach me to write these things purely from memory without my references.
From: rcain@netcom.com (Robert Cain)
In the Diffie-Hellman exchange there is a well-known-prime, w, and a well-knwon-modulus, m.
w is supposed to be a "generator" of the group of integers mod m. It does not have to be prime. It is supposed to be such that the series w**0, w**1, w**2,...,w**m-1 does not repeat but goes through all the integers less than m. Testing for such w's is pretty easy if you know the factorization of m, involving a few arithmetic tests.
Yes, I remember that now about w but I believe that m should be prime.
For those interested that don't know I think it then proceeds as follows (don't have notes in front of me so please someone correct me if I'm misremembering it) where ** is the power or exponentiation operator and % is the modulus operator:
1) Bob generates a one time random prime, b, then computes
b does not have to be prime; it is a random number less than m.
Absolutely correct.
B = (w ** b) % m and sends B to Carol.
2) Carol generates a one time random prime, c, then computes
Likewise, c does not have to be prime; it is a random number less than m.
Again, correct.
C = (w ** c) % m and sends C to Bob.
3) Bob generates a session key:
Carol does this, not Bob.
K = (B ** c) % m
4) Carol generates a session key:
Bob does this, not Carol.
Oops, one more check of those equations and that would probabaly have jumped out at me. Sorry for swapping them (but as a newbie here I now know that you folks have your chops (a drumming term) when it comes to the math of this stuff.)
Now, the tutorial over :-), the question is; is there a "standard" well-known-prime, w, and a "standard" well-known-modulus, m, and if ^^^^^-- generator not, let's define one.
I don't think there is a need for this. The two sides need to agree on a pair but they could just pick it at the beginning. If everyone uses the same m,w it would help attackers of the scheme to focus their efforts on these numbers. I believe there was some discussion of using well-known numbers in the Digital Signature Standard (which is based on the same problem as DH) but I don't know what the resolution was.
Well, any two pair of boxes that are going to employ this have to use the same numbers obviously so they will be available to crunch any given exchange against and the only thing anyone can "focus their efforts" on is the exchange itself and I don't think knowing w amd m for a long time helps that problem any. I am just think that a pair should be selected, every implementation should use them to help with interoperability and they should be defined with simply stated, remembered and coded algorithms rather than just a long string of digits.
I suppose that PGP uses a well known pair but they are big and not easy to hand around without going through media (I think.)
PGP does not uses DH and has no well known numbers.
Ah, I assumed it did somewhere because Phil and I had a fair bit of email about this last year and he convinced me that D-H was the way to go because cracking one session gives no help toward breaking the next one.
If you do want well known numbers, I really think it will not be that bad just to put them into the program. Coming up with an algorithm to choose and test a generator from scratch is probably going to be larger and certainly going to be far slower than just hard-wiring the number in.
Maybe larger but I'll bet a lot easier to remember. :-) The slowness need not be a factor since a developer only need generate them once and save them in non-volatile ram which will be required for public keys anyway. If they just exist as numbers, we have to get them on some media that we can then use to transfer them into a device or type them in. It just seems easier if a simple algorithm could be specified. I'm not anal about this I just thought it an easier way and one that is more likely to insure interoperability. Peace, Bob -- Bob Cain rcain@netcom.com 408-354-8021 "I used to be different. But now I'm the same." --------------PGP 1.0 or 2.0 public key available on request.------------------
participants (4)
-
Hal -
hughes＠ah.com -
Perry E. Metzger -
rcain＠netcom.com