[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: password-based authentication



Some comments to Hugo Krawczyk and Shai Halevi on their
recent paper follow, plus a suggested enhancement.

At 06:39 PM 8/18/98 +0300, Hugo Krawczyk wrote:
>if you are among those that care about doing IKE
>using human passwords, you may want to take a look at
>the paper:
>"Public-key Cryptography and Password Protocols"
>by Halevi and Krawczyk.
>The paper will appear in the upcoming ACM Security conference.
	<http://www.research.ibm.com/security/pub-passw.ps>


Hugo and Shai,

Thanks for making your paper available to the IPSEC mailing list.
I was fascinated by your proof that public-key crypto is
necessary for optimal password verification, as many have
suspected.  But in your focus on proving resistance to
eavesdropper attack, I think you've overlooked other
equally important characteristics of "zero-knowledge"
methods.

You've cited several methods, such as EKE, which
can prove knowledge of a password without revealing it
to anyone.  But, beyond stating that these methods rely
on heuristic assumptions, the paper doesn't analyze or
compare these techniques with alternatives, and the
protocol shown (proposed as suitable for IPSEC) does not
provide their full benefit.  This seems inconsistent with
your struggle towards optimal security, and your inclusion
of other enhancements that rely on a "merely-heuristic" basis
for security.

Fortunately, I think there are natural ways to apply EKE-style
techniques to strengthen your method.  I'll show some
reasons for doing this, and one specific enhancement.

Consider your "Mutual Authentication and DH Key Exchange"
method, using notation adapted from the paper:
-----------------------------------------------------------------
	spwd		the shared password (perhaps small)
	pk_s		server's public key (perhaps uncertified)
	f		a challenge/response-style hash function
	g		a Diffie-Hellman generator
	r,x		random numbers chosen by server (S)
	k,y		random numbers chosen by user (U)
	k'		negotiated Diffie-Hellman key

Protocol:
	S->U:  r, g^x, pk_s
	U:     t = f(spwd; r, g^x, g^y, k, U, S)
	       c = ENC_pk_s(k, t)
	U->S:  g^y, c
	S->U:  z = PRF_k(c)
	U,S:   k' = PRF_k(g^(x y))
-----------------------------------------------------------------

The weakness here is in using an ordinary challenge/response
function for t:  Whenever pk_s is not properly verified,
an attacker masquerading as S can perform an off-line
attack on t to determine the password.
This can happen in several ways:

(1)	U thoughtlessly hits "Enter" or "OK" when asked
	if the key is valid.  This one motivated your
	suggestion to display a list of "public passwords"
	(a.k.a. "fingerprints" for PGP fans) from which the
	user would select the correct one.

(2)	U finds the displayed public password in the list
	("moss mont ton half vary pit"), glances at the card
	from his pocket to confirm it, but doesn't notice
	that it isn't a perfect match (The real key is
	"moss mont ton rear rage fun").

(3)	U notices that the keys don't match, but thinks
	they're "close enough".  (Hey, I said "U", not me! :-)

(4)	Instead of using a card, U blindly trusts a
	simplistic verification system, where anyone with
	$10 and an email address gets a "certified" key.

(5)	U's system makes key verification optional,
	and U neglects to use it.

(6)	U confirms that the key corresponds to a named provider,
	but doesn't notice that the name isn't quite right.

One might argue that a well-designed system with well
informed and well behaved users won't permit such mistakes,
but we all know that kind of stuff happens.

All these attacks are blocked when the password is
mutually verified using a zero-knowledge trick,
if U shares the password only with the intended party.
This automatically prevents others from cracking
the password, and gives assurance that U is really
talking to S.  The assurance is independent of whether
pk_s is chosen by S or an attacker, and occurs without
any extra action or special attention by the user.

Since you've proven that some kind of public-key
trick is needed to do optimal password-verification, and
you've gone to the expense of using one, why not go
all the way?  Prove to U that S knows spwd too.

Here's one proposal:
-------------------------------------------------------
Let S and U use g = PRG(spwd), which converts
the password into a pseudo-random group generator.
Replace spwd in the hash function f with a value derived
from k', which is now a password-authenticated key.
Finally, make S prove knowledge of k' to U.

Enhanced protocol, slightly rearranged:
	S->U:  r, g^x, pk_s
	U:     k' = PRF_k(g^(x y))
	       t = f(PRF_k(k'); r, g^x, g^y, k, U, S)
	       c = ENC_pk_s(k, t)
	U->S:  g^y, c
	S->U:  z = PRF_k(c)
	S:     k' = PRF_k(g^(x y))
and finally
	S->U:  PRF_k'(c)

(I presume that added constraints prevent small-subgroup
 confinement, as needed in original method too.)
-------------------------------------------------------

This kind of enhancement adds negligible computation,
and it cleanly prevents attacks using an invalid pk_s,
as shown above, or even someone breaking ENC_pk_s.

The benefits of zero-knowledge tricks go far beyond just
preventing eavesdropper brute-force attack and providing
forward secrecy.  They eliminate more reasons to blame
the user for protocol failure.

Best regards,

David

----------------------------
David P. Jablon
dpj@world.std.com
<http://world.std.com/~dpj/>



Follow-Ups: References: