Idea for user/pass hashing to prevent rainbow tables, would it work?

Question

I'm very new to cryptography (and security in general, for that matter), but I had an idea that I'm sure is very flawed, but is worth asking. If a computer user, online account, etc, needs to verify a username and password, wouldn't this work well?

1. Upon signup, ask for username and password as usual
2. Hash username (charliebucket)
3. Hash username, colon, password (charliebucket:NgWB9pLx), using username hash as salt for user:pass hash.
4. Upon login, hash username and user:pass
5. Check if user:pass hash is the same, using hash of username as salt
6. If user:pass hash succeeds, log in.

In my theory, this would prevent rainbow tables two-fold. If you require 8-character and up usernames and passwords, the pre-hash string will be at least 17 characters, making it unlikely that it would be on a rainbow table. But even if it were, it would take 3+ quadrillion years on a desktop PC, I'd assume it would take a good thousand on a million-dollar cluster.

As I said, I'm fairly new, and don't fully understand anything related to cryptography or hashing (besides "password go in, hash come out"), but I thought there might be a circumstance where this could be used.

Answer 1

The goal for salts is that they be unique to each account and that they be values highly unlikely to appear in a rainbow table. Here, if usernames are unique then so are the salts. Since hash values are long and random, they won't be in rainbow tables. So hashing the username looks like it provides a good salt value to the extent that usernames are unique in your system.

If you're storing password hashes, you should probably be using bcrypt to do so. Bcrypt is a hashing scheme, but it's more flexible and is designed to mitigate more of the typical password attacks than just rainbow tables. For example, your scheme defeats rainbow tables but it doesn't prevent a brute-force attack where the target's username is known, whereas bcrypt also takes that attack into consideration.

So you have a good salt and your scheme will thwart rainbow table attacks. But good password verification schemes should strive for more.

As a non-cryptographic aside, for flexibility I would recommend not hard-coding the salt derivation in the scheme, regardless of what hashing scheme you choose. Derive the salt in the beginning and then store it separately in the database. This way the salt can be updated or changed if necessary. (Also, no one has to go look at code to figure out how it's generated.) If you choose not to store the salt in the database, then you can never change an account's salt should the need arise and you also have to have to update the password hash if the username ever changes.

Answer 2

So you have something like $(u, h)$ in your password database, with $h = H(H(u), (u, p))$. It is quite likely that existing rainbow tables will not be suitable to crack these passwords.

But if your method would find wide-spread use (or only one high-value use), one can create a new rainbow table, either for a specific user name or all possible/probable user names (then it will get correspondingly bigger/slower).

The size of your immediate hashes $H(u)$ is not important here - an attacker building a rainbow table would simply iterate over all the user names, not all the hashes.

Also, when attacking a specific user, the salt alone does not help - we simply do a brute-force (dictionary) search over all likely/possible passwords, calculate the two hashes and check, just like the verifier does. And with a fast hash (like the ones in the SHA family, even more MD5) one can check lots of passwords in quite a small time - even more when using GPUs.

The normal solution is to use a slow hash function, not a fast one.