How to search fields encrypted using a unique initialization vector?

Question

I understand that it is good practice to use a unique initialization vector for encrypting each record, but how is it then possible to search on that field?

Currently I use a single IV, which means I can reconstruct the encrypted search string for, say, an email address and query that field in the database. If I start using unique initialization vectors I wouldn't be able to reconstruct the encrypted search string.

My environment is ASP.NET, Entity Framework and SQL Server. Perhaps this is easier directly on the database, but my query is going through LINQ-to-Entities.

[My first question - finally I can't find an answer on SO!]

Answer 1

With a unique IV, you'd have to decrypt every record in order to match on encrypted contents, since as you know you get a different value every time you encrypt the same one.

Assuming this is not acceptable (it would be fine on a tiny table, but not on anything with a decent number of records), one alternative would be to hash the value and store a hash in the database, in a separate column. You'd search by the hash, and you'd decrypt only the matching record(s) just to confirm it's truly a match.

The problem with hashing something that you're encrypting as well is that most things worth encrypting (credit cards, account numbers, etc.) have only a fixed number of possible inputs. Even with a unique salt attached to the hash, hashing is bad on credit cards for example, because there are only X billion or trillion or whatever possible card numbers, so if you have a salt, a hash, and a decent processor, you can reverse engineer the card number in a reasonably short time.

If you're working with something with a large number of possible inputs though, this solution might work.

Another alternative is that if there's a piece of the encrypted data which is reasonably unique-ish, but not necessarily secret (last-4 for a credit card number for example), you can store that part in plaintext, and use it to filter down your large dataset into a very small resultset, and then decrypt each record in that resultset to compare it against your search criteria.