Storing password hashes without a correlation to the user account

Question

I read an interesting article about an alternative way to store password hashes ans was rather intrigued.

A better way to store password hashes?

The primary concept is having a large table full of salted password hashes that doesn't have any key tying them to a user; the user records would contain only the unique salt. When a user attempts authentication, the provided password is then hashed with their salt, and if it exists, they are authenticated.

This allows for a huge amount of fake data, making the hash table practically useless to an attacker, not to mention far to large to copy/transport easily (eg, via USB key).

Is this a sound method?

What kinds of metrics can we use to compare this with the more common method of storing a hash in the user record? Any Experts care to give us a comparison?

Answer 1

Maybe I don't understand but if I were an attacker I would do the following:

I would steal both tables. Then I would select a user I am interested in (e.g. an administrator) and start hashing passwords using his salt and look if the resulting hash is to be found in the hash table.

So what's the difference? (except that I have to lookup if the computed hash exists instead of just comparing (DB servers are good at such tasks)

P.S.: The author also argues that the size of the table might make it harder for the attacker to steal it. That's a good point. (Unless he doesn't steal it but runs the lookup queries on the site's DB servers)

It is an interesting idea that should be topic of more (academic) research.

P.P.S.: The author suggests a method to fix the hidden backdoor problem here. On first impression this seems to fix it.

Answer 2

I think its silly. It will just be more expensive to verify which you can already control with bcrypt. Also, theres a small chance one of the many user with a weak password will collide with an admin's salt+strongpass. When there are 1M users you'll have 1M more chances a password will match. It's also harder to control performance. And what happens if you want to reset a users password? You'd have orphans passwords which will also be checked if a password matches.

Theres also logical problems like: what if you want to shard the DB so users from certain continents have servers dedicated to them? There are too many problems. All this to prevent someone from guessing your password when they stole the hash? If the hash is stolen you have other concerns like what else is stolen. Just use bcrypt with more passes for a slower time which doesnt cause collision and other drawbacks mention.

Silly...

-edit- I rethought what the performance difference will be. After thinking about it, hashes could be sorted and organized so you don't actually need to look at as many as one may think. The difference is instead of CPU performance of checking out the password its CPU+disk/ram. The biggest difference is how much data a hacker would need to take. But remember, the burden is on you as well. I rather force more CPU time (which is possible with bcrypt) then how much disk space i need.

It may be more noticeable or take longer for a intrude to transfer all that data but if the CPU time is long enough that it takes several weeks to decode a 6letter password (remember you can force users to use longer passwords) and you notice intrusions the week of (let alone day) then you can lockdown all old passwords. It not worth making your data fat in the name of security. (Thats kind of like security through obscurity, except its just fat rather then a secret)

Answer 3

I posted a follow-up article which explains in more details what my design goals are, and also why collisions are not a problem here: http://www.opine.me/all-your-hashes-arent-belong-to-us/

This approach decouples hashes from specific users, and fuzzes your hash tables with random data. This is not as a replacement for scrypt, but instead attempts to increase the cost of an attack across new axis--storage and bandwidth--which should help deter and increase detection of attempts to steal your hashes.

An additional benefit is that attackers can no longer target specific users without first managing to steal a large portion of a database of which you can directly set the size.

Answer 4

Okay, so you are trying to protect against an attacker who HAS access to your database from benefiting from it.

If I was said attacker I would cycle through your user table and create new hashes for a standard password for all of the users. As you are using a salt that will mean that the hash table grows by the number of users, but since you have such a bloated hash table you are unlikely to notice.

In short, I am not sure you are gaining any additional protection but you are losing on performance which will get worse as the solution scales or users come and go.

Answer 5

This is beyond insecure.

First, the means for authentication just checks for hash existence in the table, there is no such thing as fake data in the table. If you add a hash to the table, fake or genuine, then you have just added a hash that is valid for all accounts. So, if you have a table with one million hashes then there exists at least one million valid passwords for EACH account. Increasing the number of hashes in the table with additional fake data merely increases the number of valid passwords as well. Thinking intuitively, what is easier to accomplish: finding a password that generates a specific hash or finding a password that generates one of many hashes?

Second, the DB performance is a most likely a non-factor. The SQL lookup required would be searching for the existence of a primary key. Primary keys are always indexed so the lookup will always use the index and should at most need to scan one record. Additionally, the lookup would involve a covering index so the query would merely return the value stored in the index and not even have to use the actual table data fetched from disk. The performance of the query would be most likely be constrained by how much of the index can be held in memory at one time.

Answer 6

Summary. This is a clever idea that in principle might help improve security a little bit, but in practice probably doesn't help enough to be worthwhile. To really evaluate the idea, you have to measure quantitatively how much it helps, and when you do that, I think you find that the idea provides almost-negligible benefit. Nonetheless, it is a clever idea and one that in some sense "almost worked". I salute the author of this idea for thinking outside the box. Even though the idea turns out not to be useful, at least the author was trying something creative and innovative.

The purpose. Let's be clear on what the goals are for this scheme. It is not intended to be perfect: it not intended to make password-hashing impossible, merely to make it a little bit more expensive. So, to measure how much it helps, we need to measure exactly how much more expensive it makes password-cracking (see below). Also, this proposal is not intended a replacement for using a proper password hashing function (scrypt, bcrypt, or PBKDF2), but rather a supplement. It might add only a modest amount of additional security, but hey, I'd take anything I can get: if it significantly increases the cost to the attacker, at essentially no increase in cost to the good guys, that would be a great tradeoff.

Unfortunately, it turns out that things are not so rosy. The benefit is negligible.

Database size. Let me start off by refuting one argument that I totally don't buy at all. One person raised the suggestion that if you add enough bogus chaff to the list of password hashes, then the database will be too big for the attackers to steal. Baloney. I don't buy that argument at all. There are limits to how much chaff you can add, because you need to be able to store the database, back it up, etc. And given those limits, I don't believe the size will be a barrier to theft of the database. So let's just agree to take that argument off the table. Instead, I want to focus on the aspect of the proposal that I think does improve security.

Cost of password cracking. So how much does this proposal help? It forces an adversary who wants to crack your password to do many lookups into this table. That sounds like something that might make password-cracking expensive. But to see how much it helps, we need to measure precisely how much more expensive it makes password-cracking.

So, let's do a comparison between plain bcrypt (the current state-of-the-art), vs this proposal with bcrypt. Suppose the attacker has stolen a copy of the database. With plain bcrypt, if the attacker wants to try one billion guesses at my password, the attacker has to compute the bcrypt hash one billion times. We can make that go pretty slow, let's say 10 milliseconds per hash, so that might take about 100 million CPU-seconds, or about 4 CPU-months. So that's our baseline.

With this proposal, the attacker has to compute the bcrypt hash one billion times, and check each resulting password hash to see whether any of them appears in the database of password hashes. The latter sounds like it might be expensive: it could easily take 10 milliseconds to do a database lookup, so maybe we've introduced the cost from 10 milliseconds per guess to 20 milliseconds per guess? Sounding promising.

But wait, don't get too optimistic. The attacker can optimize the password-cracking attack if she uses just a little bit of ingenuity. Rather than checking each of the billion bcrypt-hashes, one by one, as they are generated, it is more efficient to batch them up and check them all at the end. The attacker could compute one billion bcrypt hashes, save all the results (all one billion of them), and then check whether there is any overlap between those billion bcrypt-hashes and the hashes in the database. The latter operation can be done quite efficiently; it is just a database join operation. For instance, you can concatenate the two lists, sort them, and look for duplicates (since you've sorted them, you know duplicates will be moved next to each other, so checking for duplicates becomes very easy). Such a merge-join operation can probably be done in minutes.

Let's tally up the total cost to the attacker if we are using this new proposal. The attacker spends about 4 CPU-months generating one billion bcrypt-hashes, then spends a few minutes doing the merge-join operation. The total time is 4 CPU-months plus a few CPU-minutes. Compare to if we use standard bcrypt hashing (without this proposal); there the attacker's cost would be 4 CPU-months. The difference is negligible.

Bottom line. In conclusion, if you take a careful look at the cost of password-cracking, you'll find that this proposal does not seem to increase the cost of password-cracking by a noticeable amount. Therefore, I do not believe this proposal is worth implementing: while it is a clever attempt, it doesn't really help in the end. That's a shame, but so it goes.