Private Key Generation from Passwords/phrases

[Leichter, Jerry]

| ...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.
I've heard of one alleged case, over 20 years ago, of what appeared to
be an actual collision in Unix hashed passwords.  Some undergrads at
Yale somehow came into possession of the root password on the department
Unix server.  The story - I wasn't directly involved and can't vouch
for the details - was that one of the students involved noticed that
his hashed password exactly matched the root hashed password - including
the salt, of course.

It's interesting to look at some of the issues here.  The chance of a
matching pair of passwords *somewhere* gets you into birthday paradox
territory, so isn't all that unlikely; in fact, across the population
of Unix systems, even then, it was probably close to a certainty.  Of
course, knowing that two unspecified users, perhaps in distinct domains,
have the same hashed password, is not generally very useful.  The
chance of a match *with a particular user* - and of course root is the
user of greatest interest, though there would likely be other users
involved in administration whose passwords would be almost as useful
to know - is much less likely (linear as opposed to quadratic), and is
a possibility that is usually ignored:  If I know that root's hashed
password matched that of some user on another machine, what do I do
with that information?  Well ... in a university setting, I might
well be able to approach that other person and, especially in a more
innocent time, get him to share his password with me.

Even so, the probabilities are likely against me.  But I, again in the
world of 20+ years ago, there was another factor:  Dictionary attacks
were not considered plausible at the time, so there was little reason
to choose what we would today consider "good" passwords.  As I recall,
the root passwords on the Yale machines at that time were words - in
fact, names of ocean creatures.  (I think the compromised password was
"dolphin".)  Since students were also probaby choosing words from the
dictionary - and, within the confines of a single department at a single
school at a single time, were probably much more likely than random
chance would predict to pick the same word, as the same concepts and
words were "in the shared air" - the  effective search space was immensely 
smaller than that implied by the hashed password size.  In this setting,
the "chance dictionary search" becomes at least plausible.

A great illustration of the need to consider the full system setting!
(Note that against this particular "attack", a considerably larger
salt would have been quite effective at little cost.)

							-- Jerry

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