12

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?

Community
  • 1
Toto
  • 193
  • 8
  • 5
    Global salt = pepper – Shurmajee Oct 08 '13 at 06:32
  • 1
    Side note, I believe you'll find that companies doing detection of credit card fraud **do** store the numbers. PCI allows them to do that as long as they're rendered unreadable by encryption or an equivalent. And they need the original numbers to handle things like account updates - when you get a replacement card, a notification goes out that old card X equals new card Y. Rather than playing with games to weaken and strengthen hashes, maybe you should just encrypt the "compare" versions and be really careful the key can't be compromised at the same time as the database. – gowenfawr Oct 10 '13 at 03:30

4 Answers4

12

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).

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
3

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.

AJ Henderson
  • 41,816
  • 5
  • 63
  • 110
  • What we understood is that salt does not prevent the succes of an attack, but costs resulting in CPU needs does. That's why we increased the cost value to `10` and added more salt and md5 to prevent rainbow table usage. But a collision/birthday attack may be possible. We see abusers hourly. The issue is that the analysis is done by a statistical risk assessment application that we feed with raw data so we need to compare a "representation" of the password in a way or in an other. The tool recalculate the risk level of each user each time new raw data is added (So we can spot missed abuser). – Toto Oct 07 '13 at 15:01
  • 1
    @Toto - you are reducing the complexity by orders of magnitude by not salting though. If you are going to store the result of any global salt, you might as well not salt at all for any storage as that is the point of failure and has the least complexity to solve. The idea of a salt is that it requires a separate attack on every password. A global salt/no salt allows for all weak passwords to be found in one fell swoop. The unique salts prevent the weak passwords from being easily identified. – AJ Henderson Oct 07 '13 at 15:27
  • I also described what you need to do, for a new user, take their provided password and hash it with each of the known bad user salts and see if it matches. Once you identify a password of a bad user (based on their second attempt to register with it) then you can store that password as bad and remove the salt from the list as the password is no longer unknown. – AJ Henderson Oct 07 '13 at 15:28
  • Good point! Unfortunately we cannot implement this solution because the risk assessment is done continuously and not only at the profile creation. :( – Toto Oct 07 '13 at 15:55
  • @Toto - well if you can throw enough processing power at it, you can randomly search users logins running their password against the bad hashes when they login or change passwords, but that's far less efficient. You can also run ongoing tests of the identified bad password list against existing unique salts to identify problems once they are first detected. – AJ Henderson Oct 07 '13 at 15:59
0

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.

John Deters
  • 33,650
  • 3
  • 57
  • 110
0

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.

Luc
  • 31,973
  • 8
  • 71
  • 135
  • I think I am missing something because unsalted hashing (even with high number of rounds/cost) is unsecure (rainbow dictionaries), isn't it? – Toto Oct 09 '13 at 21:29
  • @Toto : I guess Luc meant database table, instead of field. A new table, without any link to the main user database table would do it, but storing this information together with the username is really bad. That's because unsalted passwords can be easily attacked with rainbow tables. It would be trivial to generate a rainbow table with common passwords and look for matches. Then, when you get a match, the login can be performed if the attacker also knows what's the login name for that password. – jpkrohling Oct 11 '13 at 10:01
  • Previous comment was too big. Final remark: in any case, I don't think the technique exposed by Luc would answer the question, as the owner of the website would need to know both the username *and* the password, and there's no safe way of doing what was asked in the question, as the exact same thing that the website owner would need to do could be done by the attacker. The closest to a solution is what was mentioned in another answer, in that the password is stored also in the *encrypted* version and the private key is kept offline. – jpkrohling Oct 11 '13 at 10:07
  • @jpkrohling "unsalted passwords can be easily attacked with rainbow tables". Well would you want to generate a rainbow table where each hash takes 0.1s (after which you still need to run it against the user database), or crack the salted passwords (without rainbow table) which take only 0.001s per hash per user? So yeah, I meant storing it in the same table. – Luc Oct 12 '13 at 11:06