Passwords always should be salted. (meaning a -different- nonce for each password) This prevents rainbow tables from being useful. Instead of a raw hash function, you should (for maximum security) be using something specifically designed to be expensive: read pbkdf2, bcrypt, scrypt; This will make even dictionary attacks very difficult. If someone has cracked your db they also probably also have access to your HMAC key, at which point cracking can still be parallellized and is not significantly slowed.