Does the hash algorithm used for password hashing affect rainbow table generation?

Question

re question non-random-salt-for-password-hashes Mr Potato Head states that the use of md5 instead of SHA-512 makes generating rainbow tables easier? I'd have thought that once your rainbow table is generated that the algorithm used is irrelevant? It would make no difference to how you use the rainbow table to check for known hashs? And is there any way to know what hashing algorithm was used any way?

Edit update:

I think that proper hashing of your password tables is required, not to protect your application, but to protect everyone else where users will re-use passwords and ids.

Answer 1

He said that

Use of SHA-512 is going to prove to be more of a pain for someone generating a rainbow table than MD5,

It's simply more expensive to compute a SHA-512 hash than to compute a MD5 hash.

Answer 2

Its purely a performance issue. MD5 is simpler than SHA-512, so you can generate more rainbow tableentries or more brute force attacks in a given timeframe.

Answer 3

Enough With The Rainbow Tables: What You Need To Know About Secure Password Schemes touches on this briefly. It starts out with a mini-rant about people misunderstanding rainbow tables and the actual level of danger they present, but then turns into a good discussion of the implications of password hashing algorithm performance.

On your final question, the more direct answer is that, by examining the output alone, you can only determine the number of bits in the output of the final hashing algorithm. Depending on the algorithm, this may or may not be unique, but, if the algorithm's any good, there won't be any detectable patterns that will identify it exactly. (I say "final" because the output of MD5-only will look the same as the end result of SHA512-then-MD5, since the last step is the same in both cases.)

More practically, though, anyone who can steal your password database can probably steal your source code as well, so they can just look at your source to see what your algorithm is and duplicate it for their attacks on your database.

Answer 4

Actually, the time to generate the tables is quite irrelevant since you do this only once.

The time to crack is much more relevant. Rainbow tables are just a way of reducing the number of hash operations needed to recover a password, but you will still need apply the hash function while cracking a password. For example a rainbow table can reduce the number of hash operations by a factor of 10'000. If you have a slower hash (e.g. SHA-512), cracking will be slower.

Note that a good password hash function not only includes salt, it also applies the hash function several thousand times. Hashing will still be fast for all practical purposes but cracking (by whatever method) will be thousands of times slower.