Protecting passwords against cracking with rehash

One of the problems with the way that passwords are usually verified is that all of the information needed to do the verification is in one place. The password table contains everything that is needed (salt + hash) to verify a password. So if that table is compromised, and that seems to happen a lot, most users are vulnerable because hash cracking technology is, sooner or later, going to crack the vast majority of those passwords by dictionary attack and brute force. Efforts to defeat this have mostly centered around making it harder for the crackers by using iterated memory- and time-intensive algorithms to do the hashing.

Another (an additional) approach is to also hash using a secret value that is stored securely. This is recommended in NIST SP 800-63B, Digital Identity Guidelines: Authentication and Lifecycle Management, in the last paragraph of Section 5.1.1.2. This keyed (or “secret salt”) hashing step can be isolated from everything else and treated as a black box that accepts password hashes and outputs a rehashed value. The premise is that it’s easier to protect a secret in a black box than it is to protect a database of hashes and salt values that is used directly by the verifying application.

With the additional use of a secret-keyed hash with a sufficiently complex key, it is impractical to dictionary attack a database of hashed secrets unless the key is known.

Hashing passwords with individual random salt values is still essential. Without that step, it might be possible for an attacker to create fake accounts with known passwords, then compromise the password file and see if any of those hash values appear elsewhere in the database. I am also a believer in defense-in-depth, so I also recommend continued use of iterated hashing so that security is no weaker than the current situation if the key is somehow obtained by an attacker.

Some people have commented that this requires the use of a hardware security module (HSM). While HSMs are the ideal black boxes and provide excellent protection for the key, they can be expensive to obtain and deploy, especially in cloud environments. As an alternative, I have written a sample application, rehash, that implements a very simple web API to accept a hashed password, hash it with a private key, and return the result. The rehash application should run on a machine separate from that doing the password verification, and separate from anything else that could compromise the secret key. The rehashed password would be stored in the password verification table and, when a password is entered, the iterated hashed password is rehashed and that value checked against the table.

I have huge respect for the people in the password cracking community that I have met. They have done groundbreaking work in understanding user behavior and using that to optimize the search for passwords in their cracking process. But it is time that we implement something that makes this sort of cracking entirely impractical, rather than just ratcheting up the work factor for them.

I welcome any comments on the rehash application, either through comments here or (perhaps better) by opening an issue on GitHub.