In this case you could, upon registration, generate a hash of the entered password for every salt used so far, then check these salted and hashed passwords against all the passwords already stored.

You could even cache all the salts used so far, this is potentially a smaller list than having to loop through all passwords every time to collect these.

If that is too expensive to compute on each registration, limit the number of salts you generate (pick randomly from a limited list) to reduce calculation time. That’ll still be safer (by far) than storing plain text passwords.

Note that if this is just for the sake of fraud detection, a security breach and resulting (huge) negative publicity is going to cost you much more, wiping out any advantages you gained from catching a few fraudsters this way.

Making the passwords accesible in plaintext in one way or another is already a HUGE security flaw. This is one of the most important security components on any site anywhere. I believe you already know that.

My recommendation is to find another way to deal with those frauds. Exposing user passwords like that is just not worth it. You win a little and lose a lot. If you do it, you’ll regret it later.

EDIT: I guess it depends a lot on what people can purchase on that site. You can check against the same passwords, the same IP, the same browser etc. but if someone wants to make 2 or more purchases, they can. If the goods we’re talking about are actual objects, then in my opinion the best way to detect such “frauds” are by comparing shipping addresses. Someone may use a different account/password/browser (that is easy), but they will rarely change their address to accomplish something like this.

Is the risk of the bad PR if your passwords leak worth it for the slight fraud-fighting gain you get? Personally, I wouldn’t.

If you really have to
“have a system that needs to restrict purchases to 1 (or a small number) per person”
(which sounds an impossible task) is there not something else you can use?

• Same IP address?
• Same browser?

assuming the “same password” is a good way to check for fraud, and considering that giving a way to revert the stored password into the plaintext is just a very bad idea, here’s how I would allow for duplicate detection :
I would still go with the “per user unique salt” scheme in order to identify my users.

In addition to that, I would also have a unique salt that’s used before performing another hash on the password. All the passwords would go through hashing and be stored in a DB (not in the same table as the user table), along with the number of times it’s been used. This would still allow a rainbow attack on this specific table, but you wouldn’t have the user<->password link.

In other word, your attacker would be reduced to use a bruteforce dictionary attack (which he would perform anyway, and which would probably give him access to a large number of your accounts). If your user base is small, nothing prevents you from putting dummy rows in that table, just to increase the size of the dictionary your attacker would have to use.

The key here is that you don’t care about which user has the newly typed password. The only thing that you’ll have access to is “how many users have this password”, which will allow you to reject the last subscriptions (no matter what, you can’t reject subscriptions before a certain number of users have used the same password).

It’s probably not a good idea to store plaintext passwords, but if you wanted to use “same password” as an indicator of fraud, here’s how I’d do it:

• When a user signs up, generate a hash using a different salt to the one you otherwise use.
• Truncate to the first n bits.

So for each user you’d have two distinct hashes — one with, say, 64 bytes. The other with 2 bytes, say. Theoretically, this will make your hashing 65,536 times weaker (not entirely confident with this; maybe somebody could support/refute).

You’d then be able to use this value as a weak indicator of fraud.

The only way I’d consider doing something like this is if you put a stand-alone machine in a locked room with only an RS232 connection between it and the web server. No network card, no wi-fi, no USB thumbdrives allowed.

Perform an unsalted hash on the web server, send only the hash and a user ID over the serial port, and get back a count of the number of users with matching hashes from the locked computer. Don’t cache the result on the webserver!

The locked computer can have a database of all the hashes stored by user ID and can do the comparison to say how many match.

Even then, this is all dependent on the discipline of the company involved. You don’t want to be poking holes in the air gap here.

If you are set on doing this, the ideal solution seems to me to use a Bloom filter of the known “bad passwords”.

The advantage is that even in a compromise, you only leak information about the passwords of known/suspected bad actors, and you never directly leak any password hashes. In addition, a dense Bloom filter is very fast to search and can be sized to have a low false positive rate. Also, if the Bloom filter is sized for a 1 in a million false positive rate, then even an attacker who has been able to steal your Bloom filter will find all of the real “bad passwords” plus one out of a million of his/her random password guesses.

Let’s say you have a 65,536 entry Bloom filter using 8 different hash functions. This will require just 8 kilobytes to store, and will hold more than exp(ln(1e-6)/8) * 65536 / 8 = 1,457 “bad” passwords before you hit a 1 in a million false positive rate.

The downside is that after you mark an account as bad, you’ll need to wait until the next login into that account to add the password to the Bloom filter (this only time you see cleartext passwords), and after you add a “bad password” to the Bloom filter, you won’t discover other accounts sharing the “bad password” until the next time they login.

The first problem can be easily overcome by expiring the cryptographic tokens/login cookies of a bad account, tricking the attacker into logging in immediately. Crypto tokens/login cookies should always contain a message-authentication-code-protected creation timestamp. This allows you to force periodic login and also keep a per-user earliestValidToken timestamp that you can bump up to the current time when they change their password (or if you need to expire their existing tokens for some other reason).

The second problem can be overcome using a combination of several methods. (1) It’s good to make users login every 2 weeks to keep them from forgetting their passwords (2) you probably mostly care about new account creation using “bad passwords” (3) assuming most accounts become spammy soon after creation, when you discover a spammy account, you can expire the crypto tokens/login cookies of all accounts created in the past N days (or maybe all accounts created after the spammy account).

As far as how to get your 8 hash functions, you need 8 16-bit hashes, or 128 bits of hash output to cut into 16-bit chunks. You’ll want your hash functions to use site-specific keys, to minimize the possibility of cross-site use of a stolen Bloom filter. Two invocations of Siphash-2-4 using two different keys is probably the fastest way to get your 128 bits of hash values. SHA-1 HMAC (truncate MAC to 128 bits) or AES CMAC are also perfectly acceptable.

If I understand you correctly you intend to use this information only internally within your organization to detect possible fraud?

Now I don’t know if you encrypt and salt the password on the client side using JavaScript or something similar before sending it to the server. But if not, then you could store unencrypted password at another db server in an isolated network not accessible from outside and run the checks on that?

Regarding checking for IP and browser I would guess that most people doing these types of fraud work through different proxies to change their ip around and use incognito features to “hide” their browser.

Update:
Some people here seem to miss the fact that a question was raised. It has nothing to do with our own personal believes of password treatment and best security practices.

If one agrees to what the person asking the question wants to do or not is not the point. The question was plain and simple:

Question: If it is determined that the fraud-detection ability of being to retrieve passwords is necessary, what are the best practices for storing passwords securely but in a way that is plaintext-accessible?

He doesn’t ask IF it’s 100% secure. He asks for practices of making it as secure as it can be.

Yes, it will most likely suck and be impossible to protect with a 100% success rate. But IF IT HAS TO BE DONE, how could he do it as secure as possible. There will ALWAYS be a way around anything not encrypted with a, as of yet, unbroken hash algorithm. It might be more or less dramatic and might require some C4 to get into a server room 100m bellow the surface and kill 10 armed guards hardwired to a system that kills them if they even try to leave the room (so that they themselves can’t steal the information and leave).

But it’s still not the point of the question. He wants to know how to store PLAIN TEXT passwords as securely as possible. From whom isn’t very specified and if he is the only one handling this system (and we assume he can trust himself) the only ones he has to protect the data from are outside parties. If not, then internal parties will also have to be taken into account.

Does it suck to store sensitive data as plaintext? HELL YES! Does the person asking the question deserve to know that? Yes!

Do we answer his question by only stating that? NO!