From: David Wagner <daw@CS.BERKELEY.EDU>
Newsgroups: isaac.lists.bugtraq
Subject: Re: MS Chap v2 analysis
Date: 13 Jul 1999 15:22:11 -0700
Message-ID: <7mec4c$t2e$1@blowfish.isaac.cs.berkeley.edu>
References: <CB6657D3A5E0D111A97700805FFE65870B48E463@RED-MSG-51>

In article <CB6657D3A5E0D111A97700805FFE65870B48E463@RED-MSG-51>,
Paul Leach  <paulle@MICROSOFT.COM> wrote:
> > From: Burton Rosenberg [mailto:burtonr@citrix.com]
> >
> > the parallel structure of generating the challenge response [...]
> > cuts down the strength of the PasswordHash from 16 to 14 bytes.
>
> Correct. But since the best attack is against the passwords themselves, the
> reduction from 16 bytes to 14 bytes of strength from the password hash isn't
> the primary issue.

I disagree strongly!  This property greatly increases the performance
of a dictionary attack---by a factor of about 65536, to be precise.

Suppose we hash all the entries in a dictionary containing N words.
Sort the results by the last two bytes in their hash, and burn this on
a CD-ROM.  Then, when we see a MS Chap v2 exchange, we recover the last
two bytes of the PasswordHash (using the method outlined by B Rosenburg)
and look at the appropriate entries on the CD-ROM.  We will only need
to examine N/65536 dictionary entries, and each of those can be tested
by brute force.

This reduces the cost of a dictionary attack by a factor of 65536,
which is devastating, especially when you consider that most passwords
contain relatively low entropy.

I think this alone is enough to consider MS Chap v2 seriously broken...