[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 ;)