Hashing SSNs and other limited-domain information

I'm currently working on an application where we receive private health information. One of the biggest concerns is with the SSN. Currently, we don't use the SSN for anything, but in the future we'd like to be able to use it to uniquely identify a patient across multiple facilities. The only way I can see to do that reliably is through the SSN. However, we (in addition to our customers) REALLY don't want to store the SSN.

So naturally, I thought of just SHA hashing it since we're just using it for identification. The problem with that is that if an attacker knows the problem domain (an SSN), then they can focus on that domain. So it's much easier to calculate the billion SSNs rather than a virtually unlimited number of passwords. I know I should use a site salt and a per-patient salt, but is there anything else I can do to prevent an attacker from revealing the SSN? Instead of SHA, I was planning on using BCrypt, since Ruby has a good library and it handles scalable complexity and salting automagically.

It's not going to be used as a password. Essentially, we get messages from many facilities, and each describes a patient. The only thing close to a globally unique identifier for a patient is the SSN number. We are going to use the hash to identify the same patient at multiple facilities.

First, much applause and praise for storing a hash of the SSN.

It appears as if you're reserving the SSNs as a sort of 'backup username.' In this case, you need another form of authentication besides the username - a password, a driver's license number, a passport number, proof of residence, etcetera.

Additionally, if you're concerned that an attacker is going to predict the top 10,000 SSNs for a patient born in 1984 in Arizona, and attempt each of them, then you can put in an exponentially increasing rate limiter in your application.* For additional defense, build in a notification system that alerts a sys-admin when it appears that there is an unusually high number of failed login attempts.**

*Example exponentially increasing rate limiter: After each failed request, delay the next request by (1.1^N) seconds, where N is the number of failed requests from that IP. Track IP and failed login attempts in a DB table; shouldn't add too much load, depending on the audience of your application (do you work for Google?).

**In the case where an attacker has access to multiple IPs, the notification will alert a sys-admin who can use his or her judgment to see if you have an influx of stupid users or it's a malicious attempt.

SHA-256 is a good hashing function, but it is quite too fast for this case. I need something where I can control the complexity, such as bcrypt or PBKDF2. My concern is even with all of the salting features, it will still not be enough to prevent reversal.

Preston Marshall 2010-07-23 19:00:07

@Preston Marshall If you desire a slow message digest function then you are confused on why they are so useful. NIST will never approve a slow message digest function. The whole point is that the function is very fast in one direction, but very computationally complex to reverse. The matter of brute force should be addressed using a salt.

Rook 2010-07-23 19:38:08

@Preston Marshall It doesn't matter if you use an encryption function when the real value is less than 9999 guesses away.

Rook 2010-07-23 19:39:01

@Preston Marshal bcrypt is using blowfish (a very old block cipher) as a message digest function. The properties are the same, and speed is still a describable attribute.

Rook 2010-07-23 19:45:19

@The Rook: See this article for why SHA256 is bad and bcrypt is good: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the-rainbow-tables-what-you-need-to-know-about-s.html

Preston Marshall 2010-07-23 21:58:40

@Preston Marshall This guy is not a cryptographer. He is suggesting to use a deprecated block cipher, twofish is the replacement for blowfish. He is also in direct conflict with NIST, the which is the authority for cryptographic functions.

Rook 2010-07-23 22:09:16

@Preston Marshall a slow message digest is a terrible trade off, you are burning your own resources needlessly and not gaining any appreciable security. A far better trade off would be to hide the salt from the attacker, the attacker must obtain the salt before it can be brute forced. John the Ripper works well for salted hashes using any primitive.

Rook 2010-07-23 22:14:21

@Preston Marshall But your ignoring the most important part, its the matter of the weakest link in the chain, your trying to protect 4 numbers from an attacker, it doesn't matter how many times you call sha-512 or blowfish or any combination of the two. Four number cannot hold enough entropy to be a reasonable secret.

Rook 2010-07-23 22:37:07

But wouldn't a slow algorithm, especially one where the slowness can be increased help thwart offline attacks?

Preston Marshall 2010-07-23 22:37:29

@Preston Marshall I don't see how this helps at all. Especially when the attacker only has to make 1k guesses and you have to make this calculation every time someone logs in.

Rook 2010-07-23 23:44:49

@Preston Marshall thanks for the check, but upvote? Does that mean you know this is the right answer but you don't like it? Haha!

Rook 2010-07-26 04:33:53

Something like that. You pretty much nailed it with the fact that SSNs don't have enough entropy to begin with, the rest is irrelevant.

Preston Marshall 2010-07-26 06:23:53

Preston Marshall 2010-07-23 18:57:07

No points / applause / praise for storing a long hash of a SSN. It is functionally equivalent to storing the SSN.

Slartibartfast 2010-08-05 03:34:19

@slartibarfast: Functionally equivalent yes. In the case their database gets compromised or stolen, he just prevented his company from leaking identifying information.

Ben Walther 2010-08-05 21:48:10

ansaurus

tags:

views:

answers:

Hashing SSNs and other limited-domain information

related questions