[pwg]

>encourage each of our users to select a passphrase, and even scour yahoo news from the past year, and other sources for three consecutive words, that the user can easily remember, such as "that truck driver" or "what he did". This in practice causes users to have a much better space of possible passwords to begin with

And with a wordlist of the 10,000 most common words, if you are not also using a key-stretch function (bcrypt, pbkdf2, etc.) all of those examples become quite trivial to a john-the-ripper ( http://www.openwall.com/john/ ) type attack. I.e., a three word phrase consisting of one each of the 10,000 most common words has at most 10000^3 combinations (1e+12). A 10 digit random password selected from letters, numbers, punctuation (94 digits) has 94^10 combinations (5e+19). 5e+19 is significantly larger than 1e+12)

[EGreg]

In theory, you are correct, of course. In practice, users do not select nearly close to 5e+19 unique passwords when asked to come up with a "random" password on their own. And if one is given to them, then it's inconvenient for them to remember 29c!8z79c. I would rather remember 5 words than 10 random letters, and 5 words would also equalize the space in your example.

Here is what I am pretty sure is true:

1) The salt just has to be unique enough to make rainbow table attacks on any significant portion of the userbase infeasible Any given rainbow table will only work for one salt. From this perspective, usernames are just fine as a salt.

2) The real danger is password re-use (http://xkcd.com/792/) and more generally, just lousy password selection (know anyone whose password is "password"?) Pass phrases are better (http://blogs.technet.com/b/robert_hensing/archive/2004/07/28...) and if we can deliver to the users a space of 10^14 possible phrases that actually sound like they make some sense, as an inspiration for them to choose a phrase of their own, then I think that's a good thing to do.

3) And of course, we use key strengthening, running the hash function a lot of times (a prime number of times, just in case ;)