Encryption and "WHERE encrypted_column LIKE"

[joshsackett]

I am starting an encryption project for my database and I'm performing
some tests on decryption speed. A lot of my application queries use a
LIKE parameter in the WHERE clause. To keep from changing my
application I am performing all the work on the back-end; creating
views, triggers and UDFs to encrypt/decrypt the data. A problem has
arisen around the LIKE parameter, though.

Currently:
SELECT SSN, FNAME, LNAME FROM USERS WHERE LNAME LIKE 'BON%'

will become:
SET @NEWVALUE = dbo.decrypt_has h('BON%')
SELECT SSN, FNAME, LNAME FROM USERS_VIEW WHERE LNAME_HASH LIKE
@NEWVALUE

This will not work. A hash can only compare a string value to a string
value. Has anyone else worked with this type of encryption and how did
you get around using LIKE?

Thanks,
Josh

[David Portas]

Re: Encryption and "WHERE encrypted_colum n LIKE"

Using TSQL to encrypt in a UDF is a non-starter. It's always going to
destroy performance because any non-trivial encryption algorithm is likely
to be unfeasibly slow implemented in TSQL.

Firstly, what is the goal of encrypting the data? Understand that encryption
is not a good way to control access to a database. There are legitimate uses
of encryption in a database but encrypting user's names seems a little
unusual. Since your example code doesn't even seem to include a key for the
decryption function I don't quite understand what you are trying to
implement here.

If you really need encryption then Google for some of the third-party
solutions available. You'll also find previous posts on this topic in the
microsoft.publi c.sqlserver.* hierarchy.

--
David Portas
SQL Server MVP
--

[Erland Sommarskog]

Re: Encryption and "WHERE encrypted_colum n LIKE"

David Portas (REMOVE_BEFORE_ REPLYING_dporta s@acm.org) writes:[color=blue]
> Using TSQL to encrypt in a UDF is a non-starter. It's always going to
> destroy performance because any non-trivial encryption algorithm is likely
> to be unfeasibly slow implemented in TSQL.[/color]

You could call an extended stored procedure from the UDF to perform
the actual encryption. Of course, it will still be slow since the UDF
and XP calls are expensive in themselves. Then again, Encryption
and high performance do not really go well together.

As for the problem posted, I would suggest that what is needed is:

SELECT SSN, FNAME, LNAME FROM USERS_VIEW
WHERE dbo.decrypt(LNA ME_HASH) LIKE 'BON%'

Which is not going to perform well at all.




--
Erland Sommarskog, SQL Server MVP, esquel@sommarsk og.se

Books Online for SQL Server SP3 at

http://www.microsoft.com/sql/techinfo/productdoc/2000/books.asp

[Greg D. Moore \(Strider\)]

Re: Encryption and "WHERE encrypted_colum n LIKE"


"joshsacket t" <joshsackett@gm ail.com> wrote in message
news:1117212160 .020006.275040@ z14g2000cwz.goo glegroups.com.. .[color=blue]
> I am starting an encryption project for my database and I'm performing
> some tests on decryption speed. A lot of my application queries use a
> LIKE parameter in the WHERE clause. To keep from changing my
> application I am performing all the work on the back-end; creating
> views, triggers and UDFs to encrypt/decrypt the data. A problem has
> arisen around the LIKE parameter, though.[/color]

I was just reading an article on this I think in this month's SQL Server
magazine.

I'll agree that encrypting last name is a bit "different" .

One thing they suggested for things like credit card numbers is a) being
able to index on a column OTHER than the ccn so you can get the row(s) in
question and only decrypt that absolute minimum needed and if you DO need to
use the ccn, b) store the last 4 digits unencrypted to use that to help
narrow your search.

[color=blue]
>
> Currently:
> SELECT SSN, FNAME, LNAME FROM USERS WHERE LNAME LIKE 'BON%'
>
> will become:
> SET @NEWVALUE = dbo.decrypt_has h('BON%')
> SELECT SSN, FNAME, LNAME FROM USERS_VIEW WHERE LNAME_HASH LIKE
> @NEWVALUE
>
> This will not work. A hash can only compare a string value to a string
> value. Has anyone else worked with this type of encryption and how did
> you get around using LIKE?
>
> Thanks,
> Josh
>[/color]

[Steve Kass]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

Josh,

Hashing is not encryption, and hashing something like a last name
is useless, except for obfuscation. Only the 1,000,000 most common
last names in the world (if not 10,000) account for virtually everyone,
so if someone has a hash (say SHA1) of a last name, they basically
have the last name and can look up the hash in a small dictionary of
hashed last names. When hashing is appropriate, such as for creating
a message digest, it is not reversible. The sum of this is that
something based on the idea of "decrypting a hash" is flawed.


That said, the more you want to do efficiently with the encrypted
value, the less useful the encryption. If you can use LIKE or
other comparisons efficiently in predicates with the encrypted value,
you're letting your users play "Twenty Questions" with your data:

1. Does Secret start with the letter 'L' (LIKE 'L%')?
2. It does? Good. Does it satisfy WHERE Secret >= 'LN'?
3. No? Ok, does it satisfy WHERE Secret > 'LG'?
....

If you're just obfuscating the data with a reversible obfuscator,
you might just as well do this when someone needs a LIKE result:

select ...
from users_view
where dbo.deobfuscate (LNAME) like ' BON%'

If that's too slow, maybe you can manage to add dbo.deobfuscate (LNAME)
to the underlying table and index that computed column, hoping the
index will be used by the query. I'm not sure whether you can make
this work, but as Erland said, encryption and performance don't
go well together. Security and availability are Heisenbergian: you
can't have both, and the more of one you have, the less you have of
the other. This is as unavoidable as any law of physics.

Steve Kass
Drew University


joshsackett wrote:
[color=blue]
> I am starting an encryption project for my database and I'm performing
> some tests on decryption speed. A lot of my application queries use a
> LIKE parameter in the WHERE clause. To keep from changing my
> application I am performing all the work on the back-end; creating
> views, triggers and UDFs to encrypt/decrypt the data. A problem has
> arisen around the LIKE parameter, though.
>
> Currently:
> SELECT SSN, FNAME, LNAME FROM USERS WHERE LNAME LIKE 'BON%'
>
> will become:
> SET @NEWVALUE = dbo.decrypt_has h('BON%')
> SELECT SSN, FNAME, LNAME FROM USERS_VIEW WHERE LNAME_HASH LIKE
> @NEWVALUE
>
> This will not work. A hash can only compare a string value to a string
> value. Has anyone else worked with this type of encryption and how did
> you get around using LIKE?
>
> Thanks,
> Josh
>[/color]

[joshsackett]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

First off, thanks to everyone who has provided their input. Secondly,
let me continue down the path I started:

My client performs searches on SSN, FNAME & LNAME. Any of these columns
can currently be included in a "LIKE" search. I am researching
encryption methods for the database that have minimal impact on the
application. The only way to accomplish this is to change the table
names, encrypt the data and create views to access the tables. The
problem (as you know) is that in order to perform a comparison on an
encrypted column is to completely decrypt the column and then compare.
This is not acceptable performance wise.

The next option is to not change the DB but the application. So to have
the application perform a search against an indexed, encrypted column I
would write (in essence)
SELECT dbo.decrypt(ENC _SSN), dbo.decrypt(ENC _FNAME),
dbo.decrypt(ENC _LNAME), ADDRESS FROM UserTable WHERE ENC_LNAME =
dbo.encrypt(SMI TH) .

This is MUCH faster. The problem now is how to perform a LIKE search?
dbo.encrypt(SMI TH) will look nothing like dbo.encrypt(SMI ). The only
thing I can think of is to create another column containing the first 2
(or so) characters of the last name and perform a straight comparison
on that column using a SUBSTRING of the original LastNameString and
then decrypt all the matching columns and perform a like search on
those. Example:

@LastNameString = 'WILLI%'
@ShortLNS = SUBSTRING(@Last NameString,1,2)

SELECT dbo.decrypt(ENC _SSN), dbo.decrypt(ENC _FNAME),
dbo.decrypt(ENC _LNAME), ADDRESS
FROM UserTable
WHERE dbo.decrypt(ENC _LNAME) LIKE @LastNameString
AND
-- This next section limits the search result but only by
26^ShortColumnL ength.
-- So in this case 26^2 = 676 unique rows (max.. assuming someone's
last name starts with "ZZ" :)
dbo.decrypt(ENC _LNAME) IN
(
SELECT dbo.decrypt(ENC _LNAME) from UserTable
WHERE SHORT_LNAME = @ShortLNS
)

[joshsackett]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

I got it! This can be performed for every searchable column. Wrap the
entire thing in a stored procedure (expand as needed) and viola!

@LastNameString = 'WILLI%'
@ShortLNS = SUBSTRING(@Last NameString,1,2)

DECLARE @tbl_enc_lname TABLE
(enc_lname varchar(30))
INSERT INTO @tbl_enc_lname
SELECT enc_lname FROM users WHERE short_lname = @ShortLNS

SELECT
dbo.decrypt(enc _ssn),dbo.decry pt(enc_fname),d bo.decrypt(enc_ lname),
address from users
WHERE
dbo.decrypt(enc _lname) LIKE @LastNameString
AND
enc_lname IN
(
SELECT enc_lname from @enc_lname_hold er
)

SQL Statistics:
44 unique last names out of 100,000 rows
2,301 rows returned

SQL Server Execution Times:
CPU time = 5428 ms, elapsed time = 7118 ms.

SQL Server IOSTATS:
Table '#21D600EE'. Scan count 0, logical reads 4494, physical reads 0,
read-ahead reads 0.
Table 'users'. Scan count 2, logical reads 497, physical reads 0,
read-ahead reads 0.
Table 'users'. Scan count 2, logical reads 7234, physical reads 0,
read-ahead reads 0.
Table '#21D600EE'. Scan count 1, logical reads 22, physical reads 0,
read-ahead reads 0.

Hardware:
Single Pentium 4 - 1.7GHz
384MB RAM
Dell Inspiron 8200 Notebook
SQL Server Desktop Edition

[joshsackett]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

SELECT enc_lname from @enc_lname_hold er
should read
SELECT enc_lname from @tbl_enc_lname

[David Portas]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

> The only way to accomplish this is to change the table[color=blue]
> names, encrypt the data and create views to access the tables.[/color]

This makes no sense at all. You would be better off creating SPs to access
the data unencrypted and then denying all permissions on the base tables. As
I said before, encryption is not the way to control access to data.

--
David Portas
SQL Server MVP
--

[pb648174]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

I agree.. what good does it do to encrypt the DB data when the method
for decrypting it exists in the database? If anyone gets the database
(which is I assume what you are worried about) they can simply use the
routine that already exists in the DB to get the data. I assume this is
some sort of privacy feature...

I will say though, that we had a product where people kept asking us if
the usernames and passwords were encrypted in the database. We got sick
of repeatedly explaining why not, so we did a simple encryption on them
so that we could say, "yes, they are" and move on to the next topic.

[joshsackett]

Re: Encryption and &quot;WHERE encrypted_colum n LIKE&quot;

David: If someone steals my physical database files or the backups then
they have access to the data, so it must be encrypted. I am not merely
trying to keep people out, I am trying ot make sure that if someone
gets the data they cannot read it.

pb: The routine to decrypt the data exists in the database but you must
run a stored procedure with the routine alias and password before your
run a query if you wish to pull unencrypted data. Check out the program
XP_CRYPT (search Google) and you'll see where I am going with this.