Re: Some stuff about Diffie-Hellman (and more :-)

In the Diffie-Hellman exchange there is a well-known-prime, w, and a
	 well-knwon-modulus, m.  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 = (w ** b) % m
	 	   and sends B to Carol.

	 	2) Carol generates a one time random prime, c, then computes
	 		C = (w ** c) % m
	 	   and sends C to Bob.

	 	3) Bob generates a session key:
	 		K = (B ** c) % m

	 	4) Carol generates a session key:
	 		K = (C ** b) % m

	 Carol and Bob have the same K because:
	 	K == (C ** b) % m == (B ** c) % m == (w ** (b * c)) % m

	 >From just the knowledge of B and C a snoop cannot determine
	 b from B, within computational reason (the root modulus being as
	 difficult as factoring), nor c from C, and because K cannot be 
	 determined from B and C without knowing b or c, she is screwed.

Close, but not quite.  The modulus m should be primed for best results.
Some folks have used a power of 2 for m, since that makes the modulus
operation easier, but it also makes cracking it easier, for comparable
sizes.  Next, the base w should be a primitive root of the group GF(m).

More seriously, your equations are subtly wrong -- Bob and Carol can't
do the calculations you've given.  Bob should calculate (C**b)%m -- he
knows b and C, but doesn't know c.  Similarly, Carol calculates (B**c)%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
	 not, let's define one.  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.)  When defined algorithmically they might be easier to actually
	 incorporate in a program or a product than great big numbers.  If this
	 has not been done, I propose a simply stated algorithm for finding a
	 "standard" w and m that will allow interoperation among all future
	 implementations of D-H as follows:

(deleted)

Two problems...  First, many attacks on the discrete log problem are
based on massive precomputation for a known modulus.  That probably
isn't an issue when you get to ~1K bits (*not* digits!).  Second, you
need to specify things far more concretely, and in particular define
the random number generation process.  You can't pick w till you know m.

	 I've found a solution to this that is more than sufficiently secure in
	 practice and even theoretically secure in most practical situations.

Well, I'd certainly be interested in hearing about it...  There have
been a number of mechanisms for preventing eavesdropping with DH;
a lot depends on what assumptions you want to make.  My attempts --
which involve the two parties sharing a weak (i.e., PIN- or password-grade
secret) can be found in /dist/smb/{neke,aeke}.ps on research.att.com.
There's also Rivest and Shamir's Interlock Protocol (April '84 CACM).
Davies and Price suggest using it for authentication, but Mike Merritt
and I showed that that doesn't work under certain circumstances.

		--Steve Bellovin

Earlier, smb@research.att.com wrote:

> There's also Rivest and Shamir's Interlock Protocol (April '84 CACM).
> Davies and Price suggest using it for authentication, but Mike Merritt
> and I showed that that doesn't work under certain circumstances.

Diffie, Wiener et al in "Authentication and Authenticated Key Exchanges"
(Designs, Codes and Cryptography, 2, 1992) discuss the need to combine key 
exchange and authentication, amongst other things. Anyway, the upshot is 
that a Station To Station protocol is developed and discussed which is 
based on the original D-H system. Damn, I don't have the paper which me,
so I'm not sure whether third party certification is needed.

The accompanying discussion, relating to secure protocol requirements and 
so on struck me as quite good at the time IMHO.

Matthew.
-- 
Matthew Gream, ph: (02)-821-2043
	M.Gream@uts.edu.au.

>Anyway, the upshot is 
>that a Station To Station protocol is developed and discussed which is 
>based on the original D-H system. 

The STS protocol is a regular D-H followed by a (delicately designed)
exchange of signatures on the key exchange parameters.  The signatures
in the second exchange that they can't be separated from the original
parameters.

>Damn, I don't have the paper which me,
>so I'm not sure whether third party certification is needed.

There is a digital signature required, so what is at root required is
a trusted public key of the other party.  One can use a certificate to
establish this trust and transmit it at session time, but any other
method of communicating a public key will work, include a trusted web
of trust or direct previous transmission.

STS is a well-thought out protocol, with many subtleties already
arranged for.  For the issue at hand, though, which is Ethernet
sniffing, it's authentication aspects are not required now, even
though they certainly will be in the near future.

Eric

smb@research.att.com sez:
> 
> Two problems...  First, many attacks on the discrete log problem are
> based on massive precomputation for a known modulus.  That probably
> isn't an issue when you get to ~1K bits (*not* digits!).

Hey, some of us have forgotton there are other number bases than
binary.  :-)

> Second, you
> need to specify things far more concretely, and in particular define
> the random number generation process.  You can't pick w till you know m.

I don't remember that a good w depends on m but if a well-known m
could be calculated that is prime and big enough (I suggested a way
to do this via algorithm) then it seems you are saying that a w
would then follow algoritmically from the choice of m.  Right?

> 
> 	 I've found a solution to this that is more than sufficiently secure in
> 	 practice and even theoretically secure in most practical situations.
> 
> Well, I'd certainly be interested in hearing about it...

With a little luck you shall.  I want to apply for a patent on it
first but have been reluctant (as well as too poor) to file because
I fear it being snagged at the application stage by the national
security laws that I am told allow them to do that and stamp it
top secret.  Can anybody verify or debunk that?

> There have
> been a number of mechanisms for preventing eavesdropping with DH;
> a lot depends on what assumptions you want to make.  My attempts --
> which involve the two parties sharing a weak (i.e., PIN- or password-grade
> secret) can be found in /dist/smb/{neke,aeke}.ps on research.att.com.

Yes, when there is private sharing of any info, several means exist
that are secure but that leaves the problem of exchanging this info
securely in the first place.  My method obviates the need for any prior
exchange.  I have ftp'ed your papers and mailed them to where I have a
PostScript printer.  I'm anxious to see what you have done.

> There's also Rivest and Shamir's Interlock Protocol (April '84 CACM).
> Davies and Price suggest using it for authentication, but Mike Merritt
> and I showed that that doesn't work under certain circumstances.

Yep, it has been found wanting.  There was some strong reason I found
it not applicable to my voice application but without my notes I cannot
recall it.  I spoke with Ron about that at last year's RSA conference
and he concurred.  Damned aging memory.  :-(


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.------------------