# Why don't we use MACs to store passwords?

These days, the best practice for storing passwords is to use a scheme like scrypt or bcrypt. The goal of these schemes is to make dictionary attack inefficient for an attacker but it also slows down legitimate use of the function.

If you're doing thousands of password checks per second, there is a real world cost of this slow down.

I'm wondering why we can't simply use a MAC? You choose a random salt, $s$, for each password you want to store. You then compute: $MAC(s || password, k)$ and stores the result and the salt.

This construction operates quickly and seems to me to have superior security properties to scrypt and bcrypt. The only draw back is that we now have to securely store $k$. This limits its usefulness in some contexts but not in others.

For password based file encryption, this scheme wouldn't be suitable but for storing passwords for a website, we can use a HSM device to keep the attacker from getting $k$.

Yet I've never seen any advice that suggest we store passwords in this way. Why is this?

-
For smaller websites a HSM is too annoying to deploy. But I'd expect big websites like google to encrypt their password hashes with HSMs. –  CodesInChaos Nov 10 '13 at 16:21

As K.G. and nightcracker note, the reason we don't recommend this method of password storage is that it becomes insecure if the secret $k$ is compromised. Given that the whole point of password hashing is to protect the passwords in the event that your server is compromised, it's generally not safe to assume that the compromise won't include the secret key $k$.

That said, obviously the safest thing to do would be to use both a key-stretching KDF (like PBKDF2, bcrypt or scrypt) and a secret key, e.g. as:

$$\rm hash = KDF( MAC( password, key ), salt )$$

or simply as:

$$\rm hash = KDF( password \,||\, key,salt )$$

where $\rm key$ is a secret key, $\rm salt$ is a unique per-user salt, and $\rm KDF$ is a slow key-derivation function suitable for password hashing.

-
It is possible to design systems where a key has better protection than the password database, and this design may make sense in certain cases. But in general, I don't think it does, which is why we use slow kdf's. –  K.G. Nov 10 '13 at 20:07

You can, but you don't because you need secure storage for $k$ as well as a secure computing platform. Those things are expensive.

-
Let's not forget that your database is supposedly also secure, and that scrypt is only for the case where a breach (be it a legal or illegal breach) happens. If such a breach happens, why can't it happen on $k$ as well? –  nightcracker Nov 10 '13 at 13:21
I would like to add, that of course a MAC is generally no well suited for this task, because its common security definitions in no way guarantee any confidentiality. I.e. a MAC can be secure but leak the message, which makes this entire thing pointless. So for this to even make sense you would have require more than just a secure MAC. Some specific common MACs, such as HMAC, however would probably work. –  Maeher Nov 10 '13 at 14:45
@Maeher: Specifically, any PRF or, more generally, a privacy-preserving MAC (PP-MAC) would do. Bellare has proven that HMAC is a PRF and/or a PP-MAC as long as the compression function of the underlying hash is one; we currently believe this to be true for e.g. the SHA-2 hashes, but the only reason for that belief is that no-one has managed to break them (and published it) so far. –  Ilmari Karonen Nov 10 '13 at 19:33
After nearly a decade of significant advances on MD5, there are still no significant attacks on HMAC-MD5. That does give us some confidence in HMAC-SHA256. –  K.G. Nov 10 '13 at 20:03
@nightcracker There is a marked difference in the difficulty of successfully getting a SQL injection attack to return arbitrary data and extracting a cryptographic key from a HSM. –  Simon Johnson Nov 11 '13 at 7:06