| ...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 [EMAIL PROTECTED]