Re: Private Key Generation from Passwords/phrases

[Steven M. Bellovin]

On Sat, 20 Jan 2007 18:41:34 -0600
Travis H. [EMAIL PROTECTED] 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 [EMAIL PROTECTED]

Re: 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/


pgpI8slDM82ce.pgp
Description: PGP signature