Encryption and query performance

I am trying to implement encryption but have run into some serious performance issues. I am required to encrypt the SSN in our database. In and of itself, this is not a problem. The problem comes in because there is also a need to be able to query the table based on the SSN. Since the SSN is encrypted, the query basically performs an index scan, decrypting each value as it goes along. As a result, the query for one record out of 10 million records in the table takes three minutes. It needs to occur immediately.

If I could encrypt my SSN parameter and then compare it to the encrypted value in the column, it would work fine. Unfortunately, everytime you encrypt a particular value, the resultant encrypted value is different. Hence, I have to decrypt the column to match my parameter, instead of encrypting th parameter to match the column.

Does anyone have any suggestions to help alleviate this problem

Thanks,

Laurentiu,

Thanks for the links. They supplied the information that I was afraid I'd find. In the example of using the MAC key, is there a benefit of having one column containing the encrypted SSN, if another column contains the MAC of the plaintext That is, if the MAC of the plaintext is secure enough to be able to use for indexing, then are things more secure by separately encrypting the SSN with a symmetric key

Two ideas that were proposed for our situation were:

1.) Encrypt the SSN and also store, let's say the last four of the SSN in plaintext. Our last four field would be included in the query condition. That would, in effect, reduce the amount of the index searched by a factor of 10000 (e.g search and decrypt only 1000 of the 10 million records)

2.) Create a separate table containing the plaintext SSN (indexed) and the encrypted value of the PK to the customer table. The SSN would be plaintext, but would not be linkable to any particular customer. Searches by SSN would use this table to retrieve the one row and then decrypt the encrypted value of the PK to link to the customer table. I'm not sure I like this idea, as the SSN are all visible, regardless of whether they can be linked to a particular person.

What are your thoughts on either of these ideas

Thanks,

Larry

Again, thanks for your reply. Your answer makes sense to me. I, too, was not real keen on leaving SSN (or parts of it) in plaintext, but I was running short on other ideas and short on time. I hope you'll forgive my ignorance when it comes to HMAC, actually when it comes to encryption in general. When I looked at Raul's sample code for implementing this solution, I'll have to admit I was rather intimidated by it. I wish I had more time to really digest the whole thing. I will re-read his blog and try to digest it completely. Are there any other places where I might be able to get a crash course on HMAC's

Thanks,

Larry

Laurentiu,

The example you pointed me to in Raul's blog implements the encryption and the generation of the MAC in a trigger. All of our data access logic (INSERTs and UPDATEs) currently resides in stored procedures. What are benefits or drawbacks to implementing the encryption logic in triggers as opposed to the stored procedures that we already have

You can generate the HMAC in procedures as well. Raul's example shows how you can compute the HMACs without changing existing stored procedures - this is why he's doing the HMAC computations in a trigger. If changing the stored procedures is not an issue for you, then you can move the HMAC computation in their code.

Also, for HMAC generation, you can find out more by looking at a cryptography book or at online resources. The algorithm that Raul uses is to concatenate the original value (the sensitive data) with a secret value (@key) and then to compute a SHA1 hash of the resulting concatenation - that is the HMAC of the original value:

SELECT @RetVal = HashBytes( N'SHA1', convert(varbinary(8000), @Message) + @Key )

Thanks

Laurentiu