Securely storing and searching by social security number

Question

So I'm working on a supplemental web-based system required by an HR department to store and search records of former personnel. I fought the requirement, but in the end it was handed down that the system has to both enable searching by full SSN, and retrieval of full SSN. My protestations aside, taking some steps to protect this data will actually be a huge improvement over what they are doing with it right now (you don't want to know).

I have been doing a lot of research, and I think I have come up with a reasonable plan -- but like all things crypto/security related there's an awful lot of complexity, and it's very easy to make a mistake. My rough plan is as follows:

1. On first time run of the application, generate a large random salt, and a 128bit AES key using RijndaelManaged
2. Write out both of these into a plaintext file for emergency recovery. This file will be stored offline in a secure physcial location. The application will check for the presence of the file, and scream warnings if it is still sitting there.
3. Store the salt and key securely somewhere. This is the part I don't have a great answer for. I was planning on using DPAPI -- but I don't know how secure it really is at the end of the day. Would I be better off just leaving it in plaintext and restricting filesystem access to the directory its stored in ?
4. When writing a record to the database, hash the SSN along with the large salt value above to generate a field that is searchable (but not recoverable without obtaining the salt and brute forcing all possible SSNs), and AES encrypt the raw SSN value with a new IV (stored alongside) to generate a field that is retrievable (with the key/iv) but not searchable (because encrypting the same SSN twice should yield different output).
5. When searching, just hash the search value with the same salt and look it up in the DB
6. When retrieving, decrypt the value from the DB using the AES key/iv

Other than needing a way to store the keys in a relatively secure way (number 3 above) it seems solid enough.

Things that won't work for us:

• "Don't do any of this" Is not an option. This needs to be done, and if we don't do it they'll a) get mad at us and b) just pass all the numbers around in a plaintext document over email.

This will be internal to our network only, so we have that layer of protection at least on top of whatever is implemented here. And access to the application itself will be controlled by active directory.

Thank you for reading, and for any advice.

Update #1: I realized from the comments that it makes no sense to keep a private IV for the SSN retrieval field. I updated the plan to properly generate a new IV for each record and store it alongside the encrypted value.

Update #2: I'm removing the hardware stuff from my list of stuff we can't do. I did a bit of research, and it seems like that stuff is more accessible than I thought. Does making use of one of those USB security token things add meaningful security for key storage?

Answer 1

I've had to solve a similar problem recently and have decided to use an HMAC for the hashing. This would provide more security than a simple hash, especially as you can't salt the value (otherwise it wouldn't be searchable).

Then as you say, use AES with a random salt for the reversible encryption.

It maybe that you don't need to encrypt this data but I had no choice and this seemed like a reasonable solution.

My question on IT Security https://security.stackexchange.com/questions/39017/least-insecure-way-to-encrypt-a-field-in-the-database-so-that-it-can-still-be-in