Private Key Generation from Passwords/phrases

[Steven M. Bellovin]

On Mon, 22 Jan 2007 16:57:34 -0800
Abe Singer <abe at sdsc.edu> wrote:

> On Sun, Jan 21, 2007 at 12:13:09AM -0500, Steven M. Bellovin wrote:
> > 
> > One sometimes sees claims that increasing the salt size is
> > important. That's very far from clear to me.  A collision in the
> > salt between two entries in the password file lets you try each
> > guess against two users' entries.  Since calculating the guess is
> > the hard part, that's a savings for the attacker.  With 4K possible
> > salts, you'd need a very large password file to have more than a
> > very few collisions, though.  It's only a benefit if the password
> > file (or collection of password files) is very large.
> 
> Definition of "very large" can vary. (alliteraiton intended).  Our
> userbase is about 6,000 active users, and over the past 20 years
> we've allocated at least 12,000 accounts.  So we definitely have
> collisions in 4k salt space. I'm not speaking to collisions in
> passwords, just salts.
> 
> UCSD has maybe 60,000 active users.  I think "very large" is very
> common in the University environment.
> 
Is that all in one /etc/passwd file (or the NIS equivalent)?  Or is it a
Kerberos KDC?  I note that a salt buys the defense much less in a
Kerberos environment, where capture of the KDC database lets an
attacker roam freely, and the salt simply protects other sites where
users may have used the same password.

Beyond that, 60K doesn't make that much of a difference even with a
traditional /etc/passwd file -- it's only an average factor of 15
reduction in the attacker's workload.  While that's not trivial, it's
also less than, say,  a one-character increase in average password
length.  That said, the NetBSD HMAC-SHA1 password hash, where I had
some input into the design, uses a 32-bit salt, because it's free.



		--Steve Bellovin, http://www.cs.columbia.edu/~smb

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com