How can I be secure with a global salt?

Question

If I understood the basic of password hashing and storing, what we need are:

1. a "strong" salt
2. a "real" random salt
3. a unique salt per password
4. a password hashing function with a high CPU cost

We hash the passwords using 1, 2, 3 and 4 using PHP crypt() and CRYPT_BLOWFISH with a "medium" cost.

We have a new need: we need to be able compare the hashes because we have noticed that low level fraud/spam/scamsters use the same passwords. We do not need to know the password of an abuser but only to know that a profile is using the same password as a previously identified abuser.

So we are thinking about having 2 fields in our database:

• passwordA: used for login procedure (this field would use 1, 2, 3 and 4)

crypt($password, '$2y$06$' . $uniqueSalt);

• passwordB: used to "compare" (this field would us 1, 2 and 4)

crypt(md5(md5($password) . $globalSaltA) . $globalSaltB, '$2y$10$' . $globalSaltC);

Global salts A and B would be stored only in the application code.

To compensate the missing point 3 for passwordB, we have increased the "cost" which is a lot higher.

Following the comment, I understood how unsecure this strategy is if an attacker gets a full access (database + code) on the server. However, if the attacker only gets the database, we are fine.

Companies doing detection of credit card fraud have the same issue with the credit card numbers. They cannot store them but need to compare them.

So what strategy/solution would you advice?

Answer 1

The core problem: if your server can efficiently compare a hashed password with (potentially) all the hashed passwords for all the user, then so can an attacker. An attacker who grabs a copy of your server files/database will be in position to run an offline dictionary attack, i.e. hashing potential password and look for a match.

Normal password hashing uses a per-password salt to prevent parallel attacks: we want the attacker to pay the full computational price of the hash function (which is made expensive through many iterations) for each password and each user account. However, if several password hashes use the same salt, then the attacker can try a potential password against all of them for the cost of one hash function invocation. Thus, your "global salt" substantially weakens the scheme: it allows the attacker to attack 1000 accounts for the cost of attacking one.

The important point: your problem is one of temporality. Indeed, you don't actually want to compare a new user password with all the passwords of all other users; what you want is to compare the password chosen by each user at registration time against a limited list of "passwords of known offenders". Unfortunately, when a registered user falls into "offender" status, he is already registered, and his password has not been kept around, only the hash thereof. So, really, you would like to be able to access the password used for registration after the registration has taken place.

A possible solution: use escrowing, aka asymmetric encryption. Create a RSA key pair. Store the public key on the server. Do NOT store the corresponding private key on the server; instead, store it elsewhere, e.g. on a laptop computer which is kept offline (or maybe just on a few USB flash drives).

When a user registers, hash his password as usual (with PBKDF2, many iterations, a new random salt, etc). But, also, encrypt the password (not the hash) with the RSA key, and store the encryption result in your database, along with the hash. Encryption only needs the public key, and is randomized, so this encrypted version does not give extra leverage to an attacker who gets a copy of the database contents. When a user logs in, the password hash is used, as usual.

When a user turns out to be a spammer, get the private key and decrypt the escrowed password. That way, you obtain the "bad password" and can add it to the list of passwords to reject upon registration. That list can be kept as cleartext: since the corresponding accounts have been closed, then there is no problem with that. Take care to do the decryption on a "safe" machine, preferably offline: you really do not want to see that private key stolen.

---

A word of caution: spammers are like bacteria, in that they tend to evolve with regards to external constraints. If you filter out spammers based on their habit of reusing passwords for registration, then you will soon train them into generating random passwords. Thus, I predict that if you install such a system, then it will cease to be effective at kicking spammers out after a relatively short time; after that, it will just be dead weight in your database (not a lot of it, because a RSA-encrypted short message with a 2048-bit RSA key is just 256 bytes, but dead weight nonetheless).

Answer 2

You can't. It undoes the security of having a unique salt (or any salt for that matter) entirely. The point of having a unique salt is that it prevents use of a rainbow table to identify the password. Storing with a global salt allows that table to be attacked with a rainbow table and most likely identify the original password in many cases.

The alternative to this is to generate a list of salts to try a new password against (the ones associated with previous spammers). It makes a new user creation a slightly more difficult operation since you have to run the password hash multiple times, however it is the only secure way to do what you are talking about. New user creation should also be the only time you need to do this step, so it shouldn't be too, too big of a hit. I'd also only recommend doing it when other indicators seem to support it being a spam user if you want to further reduce the impact.

You could also store bad passwords after they are identified to keep the list short. For example, previous user with salt 1234 had a hash abcd. When a new user submits password "ImSpam" and you try it against salt 1234, you see that it is abcd and now know the actual password for that salt, so you can stop checking against it and only disallow the password entirely. This should keep the list relatively short. You could also have old spam users age out potentially since if you haven't been attacked by that spammer in a while, chances are decent that they gave up.

Answer 3

Lets call the uniquely salted hashes "better" and the global/singly salted hashes "worse". For performance reasons you might want to keep the better hashes on the user database so you can authenticate users fast. I'd recommend moving the "worse" hashes to a different, more secured server with a thin, simple, authenticated interface consisting of two methods, AddPassword(userId, password), and Blacklist(spammerUserId).

AddPassword would simply report success or failure. Blacklist would add the spammer's Id to the blacklist, and return a list of all userIds matching the spammer's password. But beware - anyone who has access can run a dictionary against your Blacklist method, poisoning legitimate users and gaining lists of matching passwords.

Internally, you could store them however you want: hashed, salted, encrypted, or clear text. You just have to keep that machine securely locked up.

Answer 4

As @AJHenderson already said, the simple answer is that you can't. You understand why a unique salt is needed, and you're not missing out on any mathematical trick for this, it's really impossible in combination with a unique salt. That said, this is how I would solve the problem:

1. I would add a new database field called something like UnsaltedPassword and fill it with all NULL values. Every time someone registers or changes his/her password, fill it with a hash of the password, only without salt and ten times stronger than the other hashing method.

2. Modify the login procedure so it checks whether the user has a NULL value in that field, and if the user does, fill the field. If this would cause too much load, perform the hashing feature only for certain accounts, like people with a low postcount or simply by random chance (e.g. perform the hash with a chance of 1 in 10).

3. Finally I'd add checking for duplicate passwords whenever the field is filled, and checking against a blacklist as well. People with duplicates might be flagged (possibly also told that they use a weak password), and the blacklist immediately gets banned (or hellbanned, if possible).

Password changes don't occur that often compared to logins (all the times the other hash function with salt needs to be run), so I think it makes sense to have two different hash fields in the database for different purposes. Also a ten times stronger should be doable, or perhaps you could do even more (1 to 2 seconds hashing time is what I'd aim for since it's pretty much a one-time deal). It's probably more expensive for attackers to crack these than to just apply the unique salt.