Private Key Generation from Passwords/phrases

[Steven M. Bellovin]

On Sat, 20 Jan 2007 18:41:34 -0600
"Travis H." <travis+ml-cryptography at subspacefield.org> wrote:

> 
> BTW, dictionary attacks can probably be effectively resisted by
> making the hashes of passwords twice as big, and using a random value
> concatenated with the password before hashing, and storing it
> alongside the hash (it's like crypt(3) salting, but more so).  If the
> password is important to keep from disclosure beyond the needs of
> this security system, one could even truncate the output of the hash
> to half its size, so that there's multiple preimages; since you
> doubled the hash size to begin with, you end up with the same
> security factor against guessing, I believe.

Could you explain this?  It's late, but this makes no sense at all to
me.  Dictionary attacks work by guessing -- if the random salt is
visible to the attacker, I don't know what "more so" might mean.
Similarly, the size of the output is irrelevant; we're not talking
about cryptanalysis here.  As best I can tell, increasing the output
size and/or the salt size increases the size of a precomputed
dictionary, but that's not the only form of dictionary attack -- see M.
Bishop, ?An Application of a Fast Data Encryption Standard
Implementation,? Computing Systems 1(3) pp. 221?254 (Summer 1988), for
example.

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.

There is also some benefit if the attacker is precomputing
dictionaries, but there the size of the search space is large enough
that the salt factor isn't that important given even minimal quality
checks.


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

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