Subject: Re: Secure Remote Password interest

From: Vernon Schryver <[email-masked]>
Date: Wed, 21 Mar 2001 09:25:01 -0700 (MST)

> From: James Carlson <[email-masked]>

> ...
> Have you read the SRP documentation (RFC 2945)?  This is an asymmetric
> system.  The mechanism described has these properties:
>
> 	- Authentication of a peer can be done using a non-invertible
>           hash of the passphrase.
>
> 	- Proof of identity requires access to the original
>           passphrase.
>
> 	- The hash cannot be used as proof of identity.

That also describes the ancient UNIX user authentication scheme. 
What SRP and other so called zero-knowledge schemes add are ways to not
put the cleartext password on the wire and ways to make the old UNIX 
hash computation perhaps 1000 times slower.

> > Does that community really understand the issue, or is it only reacting
> > to the extremely energetic salesmanship of advocates of the various
> > mechanisms that improve the security of cleartext password protocols?
>
> This is not a cleartext password protocol.

Yes, but there are good (and bad) reasons why the people selling SRP
and so called zero-knowledge authentication systems so often contrast
their systems with protocols using cleartext and badly chosen passwords.

> > Is the CHAP shared secret problem worthy of attention, since in
> > some important sense it is neither fixable nor fixed by this protocol?
>
> Please explain that statement.

I think the CHAP shared secret problem is that both authenticator and
authenticatee must know something determined by a shared secret.  In
real life, passwords have only a couple dozen bits of entropy but there
are 2**24 milliseconds in a week.  At best passwords used by humans are
among 3 or 4 word strings from a college dictionary plus all of "Bartlett's
Familiar Quotations."  That implies that given access to the hash of
the secret and time to try 1,000,000's of guesses, access to a hash of
the passphrase is equivalent to access to the passphrase.

If the shared secret involved 100 bits of entropy, then SRP would be
a complete fix.  Perhaps at heart the problem is that the difference
between 100 and 20 bits of entropy is not a factor of 5 or even 80,
but of 1,000,000,000,000,000,000,000,000.

> The shared secret problem (at least as fixed by this protocol) is that
> the authenticator must also have access to the passphrase in order to
> authenticate.  This allows the authenticator to masquerade as the
> authenticatee, and for common deployments invites attack of the
> database that holds many shared secrets.
>
> SRP does not have those problems.

If SRP were used with passwords with hundreds of bits of entropy
(e.g. smart cards), that would be accurate, but this is real life. 
What an Internet Service Provider can ask a customer to type into a Windows
dialog box is severely restricted, not by Microsoft but by human nature.
Every third time when I type a Microsoft product key with its apparent
128 bits of entropy, get one of the letters or digits wrong or transposed,
and fail to see it for several minutes, I'm reminded of this fact.

> > Because people consistently choose bad passphrases and because computers
> > have become so fast, you must treat digests of passwords as if they
> > were cleartext.  If the bad guys can get a copy of the authenticator's
> > database of verifiers, why can't they do dictionary attacks to recover
> > the cleartext passwords?
>
> Dictionary attacks are always possible against stolen hashes.
> However, they can be made quite infeasible.  You're right that this
> protocol doesn't prevent fools from choosing bad passwords.
> Determined fools are hard to stop.  However, with well-chosen
> passphrases, SRP is a significant set up from CHAP.

Yes, but have you tried choosing UNIX passwords that be remembered
and typed accurately and that are resistent to the standard dictionary
based hash breaking tools?  I have and have been extremely discouraged.

My point is that the draft ought to say that unless the secrets have 100
bits of entropy, there is little difference between this scheme and CHAP
and therefore the file of hashes must be kept as secret as the UNIX
/etc/passwd file or CHAP cleartext passwords, and that in real lifew,
passwords are exceptional if they have 20 instead of 10 bits of entropy.

> The "hash" used for SRP passphrases isn't your run-of-the-mill message
> digest.  It's the result of modular exponentiation.  I expect that
> it's attackable using the same methods as are used for RSA.  For long
> keys, that's hard.  (On a 366MHz P-II and using a 1500 bit modulus, I
> was able to try one key every 10 seconds.)

The Diffie-Hellman code I've used and shipped was all in C, but needed
only about a second per exponentiaion on a Dell 200 MHz P-II with Borland's
5.0 C compiler.  If you don't care about portability, you can make even
that a lot faster.  Still, if this SRP-PPP proposal needs even 1 second
of computing per PPP authentication, then I doubt PPP hardware vendors or
customers will be enthused--to grossly understate that problem.  But that's
not my point.

The lesson to be learned from the history of UNIX passwords is that if
the authentication computations are quick enough to be tolerable, then
they are too quick to significantly increase security for long.  The UNIX
authentication scheme used a modified form of DES intended to require a
similar amount of computing.  The idea was that the so much time was
required to compute the UNIX hash that dictionary attacks were infeasable,
although the phrase "dictionary attack" was not used.  Consider the
implications of the growing availability of hardware accelerators for HTTPS
on how long modular exponentiations will require in 5 or 10 years.

> > In other words, the warning in last paragraph of section 4 is far too
> > weak given what most people will infer from the claim about cleartext
> > passwords in the start of the draft.  Please let's not make a new mistake
> > like the incorrect claims about the security of MSCHAP compared to CHAP.
>
> MS-CHAP's error is not comparable here.  MS-CHAP merely throws a thin
> veneer of MD4 on top of a vaguely CHAP-ish protocol.  It uses this
> hash as the shared secret -- neither authenticator nor authenticatee
> needs access to the "user password."  The hash alone is enough to
> authenticate with MS-CHAP.

Yes, but that was not the big mistake of MSCHAP.  The mistake was not
that MSCHAP was a bad idea, since it was a good idea,  The problem
was that the MSCHAP selling was based on snake-oil.  It was sold as
being significantly more secure than CHAP, when it fact it was only
more secure against the unithinking or unmotivated.  That is worthwhile,
but nothing to write home about.  (Never mind the errors that made
MSCHAP significantly less secure in some situations, since they have
nothing to do with the good idea in MSCHAP.)

This PPP proposal with the passwords that will be used in real life
is better than CHAP, but *PLEASE* let's not over-sell it.

> SRP is different.  An authenticatee cannot use the hash alone to
> authenticate.

No!  If an authenticatee can reduce the set of possible secrets to, for
example, the words in a college dictionary, and has merely a typical 2000
vintage PC, then an authenticatee can break the hash within 24 hours.

A less inaccurate description of the advantage of SRP is that if
the secret is uncharacteristically and implausibly well chosen or
if the authenticatee that cannot do more than one D-H exponentiation
in a second, then the authenticatee cannot use the hash alone.

Vernon Schryver    [email-masked]

---

From: James Carlson <[email-masked]>
Date: Wed, 21 Mar 2001 11:48:13 -0500 (EST)

Vernon Schryver writes:
> authenticatee must know something determined by a shared secret.

Here we disagree.  Storing something that's trivially useful on a
server is quite a different thing from storing something that's hard
to use.

We can't set policy here.  Perhaps it would be a good thing to have a
BCP on choosing passwords, how often to change them, and such.  This
is not a problem with the protocol, though.

What the protocol really does is stop people from asking for stupid
changes.  A frequently asked question is "how do I encrypt my CHAP
passwords?"  Another is "how do I make it work with
LDAP/NIS/whatever?"  The proper answer is "no."  Those things are
avoided with SRP.

As I said before, SRP isn't going to make stupid users smarter.  I
have no illusions about that and I suspect that it's a fundamentally
unsolvable problem.  All that can be done is make the smart ones
safer.  SRP *does* do that.

>  In

It depends.  Small things, like abbreviations (the common password on
many Xylogics systems was once "LicGio"; would you get that out of
your dictionary?) make the attack much harder.

> and fail to see it for several minutes, I'm reminded of this fact.

I agree that's a problem, but I think it's out of scope.  We don't
deal with user interfaces here, do we?

> based hash breaking tools?  I have and have been extremely discouraged.

I agree that there's user interface and deployment issues here.

> passwords are exceptional if they have 20 instead of 10 bits of entropy.

OK; I can note that good password choice is hard and that choosing bad
passwords makes a dictionary attack much easier.

The situation is still far better than CHAP.  If you steal the secrets
from a CHAP authenticator, then you're in with no work at all.  It
doesn't matter how good the secrets are.

The real issue is that users have to evaluate the threat model and
adjust accordingly.  For many common configurations, SRP is simply
much better than CHAP.  It doesn't have the same exposure.

In general, I think SRP does enough.  Who is going to spend millions
to break security on something that's worth only a few dollars, like
an ISP account?  If what you're protecting is a lot more valuable,
then you need to take that into account, but that's out of our scope.

> 5.0 C compiler.

The time I quoted was actually for the entire authentication exchange
with a 1500 bit modulus.  There are several exponentiations and other
operations in there.

Probably not an issue, though.

> nothing to do with the good idea in MSCHAP.)

No.  In fact, the MD4 hash is the shared secret.  It is therefore
equivalent to CHAP.  It's not a good idea.  It's not worthwhile.  (And
yes there are also flaws that make it *less* secure than CHAP.)

> is better than CHAP, but *PLEASE* let's not over-sell it.

OK.  Any suggested text?

> in a second, then the authenticatee cannot use the hash alone.

I mean text that would be useful in a draft.  :-/

-- 
James Carlson, Internet Engineering       <[email-masked]>
SUN Microsystems / 1 Network Drive         71.234W   Vox +1 781 442 2084
MS UBUR02-212 / Burlington MA 01803-2757   42.497N   Fax +1 781 442 1677
Second Edition now available - http://people.ne.mediaone.net/carlson/ppp