Private Key Generation from Passwords/phrases

[Travis H.]

On Sun, Jan 21, 2007 at 12:13:09AM -0500, Steven M. Bellovin wrote:
> Could you explain this?  It's late, but this makes no sense at all to
> me.

I probably wasn't clear, you bring out my realization that there
are a number of unwritten assumptions going on here.

> Similarly, the size of the output is irrelevant; we're not talking
> about cryptanalysis here.

Well, I can't disagree, since I also approved of truncating it to
its original size, but I wouldn't want to induce collisions by
making the salted input space much larger than the output space,
or else the work factor goes down for the attacker, right?

> 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.

I'll have to look at that.

> 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.

Well, birthday paradox here, but what you say is true.  IIRC, standard
cracker practice back when tftp'ing password files was popular was to
pool them all and sort by salt, then computing the most common salts
and the most common passwords.

> 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.

Really?  What about rainbow tables?  I heard recently that there was a
relatively complete MD5 rainbow table online with an ajax/js interface
for searching it.  Unless I'm missing something obvious, this basically
eliminates the advantage of hashing unsalted passwords with MD5 to null.

I look favorably on the formats that allow you to iterate a OWF over
the password N times, and that store N in the entry.  That way, if the
costs of running the algorithm go down, you can just increase the
number of times it has been run on every entry in the file without
requiring any interaction from end-users.  This kind of scaling with
the world is needed, because cryptanalysis isn't a stagnant field, and
Moore's Law still holds, and I find the idea of having to change
between incompatible systems just to keep the same level of security,
and on someone else's schedule, to be undesirable.
-- 
``Unthinking respect for authority is the greatest enemy of truth.''
-- Albert Einstein -><- <URL:http://www.subspacefield.org/~travis/>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20070121/49ef4c89/attachment.pgp>