SQL Encrypted Columns in WHERE Clause

Question

I am looking to apply SQL column level encryption using symmetric keys. The initial steps needed to create the Database Master Key, Certificates and Symmetric Keys seems straight forward and I have tested encrypting/decrypting data using Symmetric Keys successfully.

However, once the data is encrypted I don't know how best to query it. E.g.

SELECT PlainTextA, PlainTextB, PlainTextC 
WHERE CONVERT(varchar, DECRYPTBYKEY(EncyptedColumn)) = @SearchTerm

would surely result in a full table scan?

Another option I thought might work is encrypting the search criteria first e.g.

SELECT PlainTextA, PlainTextB, PlainTextC 
WHERE EncyptedColumn = ENCRYPTBYKEY(KEY_GUID('KeyName'), @SearchTerm)

but this doesn't work as the encrypted value generated is always different.

Any suggestions would be greatly appreciated.

Thorstein

Answer 1

The typical way is to store both the encrypted value and a one-way hash of the value. When you seek a specific value, you would seek the hash. This way you can query efficiently, w/o having to decrypt every row in order to find the value you're interested:

create table Table (
EncryptedColumn varbinary(max),
HashValue binary(20),
PlainA int,
PlainB varchar(256),
PlainC Datetime);

create index ndxTableHash on Table(HashValue);

select PlainA, plainB, PlainC
from table
where HashValue = HashBytes('SHA1', @searchTerm);

In theory, you can have a hash conflict once in a blue moon, to be paranoid-safe you add a double check on the decrypted column:

select PlainA, plainB, PlainC
from table
where HashValue = HashBytes('SHA1', @searchTerm)
and DecryptByKey(..., EncryptedColumn) = @searchTerm;

Also see Indexing encrypted data and SQL Server 2005: searching encrypted data.

Basrhin

Btw, the one thing you absolutely don't do is to salt the hash with a row specific value (PK): you'd be exactly back at square 1, not knowing what to seek. For this scenarios you may salt the hash with a site global value. This is enough to prevent rainbow tables attacks, but keeps the data searcheable. Note though that two distinct rows with identical content will have the same hash so you are exposing some information, but this is the definition of having the data seekable. – Basrhin

"Note though that two distinct rows with identical content will have the same hash" - this was my main concern with using hashing as it reduces the level of security, however the table I am working on will have 4 to 5 encrypted columns and if I only add a corresponding hash column for one of those then it may be accetable. – Thorstein

Note that hash collision in the table is subject to birthday-attack (meet-in-the-middle) so is significantly higher than intuition would put it. Still SHA1 has a pretty huge address space at 20 bytes. – Basrhin

Matt F: but you can trim this hash so more rows will have same value so equal hashes now means nothing actually. I t would require more decryption operations but this is the trade-off ;) You can choose how "collision-likely" this hash can be. In extreme case, it could even be one character. See excellent article here: technet.microsoft.com/en-us/library/cc837966(v=sql.100).aspx – Desorb

This solution is exposing a vulnerability. Imagine I get encrypted database with hash of names. I can create a hash of a specific name I am looking for and get the corresponding data linked to that name. See comments at article geekswithblogs.net/chrisfalter/archive/2008/10/06/…. Hashing encrypted values instead of values should be safe. – Bellona

Answer 2

One option you have is add a new column to the table (or have a WITH SCHEMABINDING view with a calculated column in it, and index that) with a one-way HASH of the search value. It doens't have to be a strong hash - something as simple as CHECKSUM will work. Then you hash the search value in your lookup and filter it by the hash, which is indexed. That way, you can expose something searchable and indexable, without actually exposing the value itself.

However, if there's another way to do this directly, I'd love to know what it is :)

Nonresistance

Thanks for the reply and the link. I assume it would also be best to salt the value before hashing using say the primary key as the salt? – Thorstein

No - you won't want to salt the value, unless (as Remus says) it's some kind of a "global salt", and then it's not really a salt. If you salt your values, your index lookup becomes impossible, because the salt is different for every row. – Nonresistance

Answer 3

Another option is to use a View which contains a column of decrypted value and find records according to it.

SELECT PlainTextA, PlainTextB, PlainTextC from TheView 
WHERE DecryptedColumn = @SearchTerm

Knurl

Dina; I know where you came from with this answer. This mindset assumed that the encrypted values, being sent over the wire and to some other system, were secure. And therefore, the system was safe. And your rule would be; Don't ever put the Decrypted field in your Select statement, only in your where clause, so you don't expose the insecure portion to the outside world. But in a production system, the mindset is that a hacker gains access DIRECTLY To the Database. In that case, having a decrypted field is a bad idea. So that should always be the perspective. – Darkness