Article 2939 of comp.lang.java.security:
In article <slrn5j2ktp.l44.mdw@sol4.ebi.ac.uk>,

Tom L. Tran <toml@metainfo.com> wrote:

>> I'm looking for a secure client-server key exchange protocol, which does
>> not use "patent" public-key, using password as initial secrete key. ...

Mark Wooding <mdw@ebi.ac.uk> wrote:

>Kerberos is described in Bruce Schneier's book, near the back. ...
>I'll have a quick stab at defining a protocol.  Please embarass me by
>pointing out its weaknesses.

Sorry guys, but Kerberos was shown to have a verifiable plain-text
attack by Bellovin & Merritt in a 1990 paper.
Mark's does too:

>Alice wants to log into a server, which knows her (hashed) password P.
>
>  1. Alice sends the server her name.
>
>  2. The server finds P, generates a key K_S, and sends Alice E_P(K_S).
>
>  3. Alice decrypts the key with her password, generates a key K_A, and
>     sends the server E_{K_S}(K_A).
>
>  4. Both sides calculate a hash of K_A and K_S, and use the result as
>     an encryption key for subsequent communication.
>
>  5. The two sides perform some kind of exchange of random numbers to
>     ensure that they've got the same key.  Maybe the server sends
>     E_K(R_S), Alice responds with E_K(R_S + 1, R_A) and the server
>     replies with E_K(R_A + 1).

Here's a verifiable plain-text attack:

Let M1 = E_P[K_S) and M2 = E_{K_S}(K_A).
Pick up or build dictionary of candidate passwords.
For each candidate P'
	compute Ks' = D_P'(M1)
	compute Ka' = D_{Ks'}(M2)
	calculate the hash of Ks' and Ka' to get a candidate K'.
	decrypt E_K(R_S) with K' to get Rs',
	decrypt E_K(R_S + 1, R_A), and see if the result is (Rs' + 1, ...)
	When R_S + 1 = Rs' + 1, you've verified that P' = P.
		(Or at least you've narrowed the field.)

All schemes that completely avoid public-key techniques,
seem to unravel in this way, permitting verification.

The only working methods I know of require at least a
one act of signing, sealing, or DH exchange.

Tom, unless you're particularly impatient, some early
PK patents are expiring soon.  Though you may want also 
want to be aware of patents on password methods that use PK.

------------------------------------------------------
David P. Jablon
Integrity Sciences, Inc.
dpj@world.std.com
http://world.std.com/~dpj/