Improving Search Performance when using SQL Server 2008 Encrypted Columns

This is a story of courage, honor, and data encryption. In addition to being something of a tribute to one of my favorite games of all time, I do feel I need to preface this post with a bit of a disclaimer.

Generally, when I describe this problem to someone, we go through pretty much the same conversation.

Why didn't you try Sql Server 2008 Transparent Data Encryption? Why don't you just update your ACL? Why don't you try this? Or that?

Well, sometimes the environment, either technologically or politically, precludes some of your better options. Ultimately, you have to go with your best permissible solution to solve the problem at hand. That being said, let's say you've been charged with securing your organizations PII. Your only option is to encrypt the column with SQL Server's column encryption.

You start looking at the impact this is going to have on your current and future applications. If you're like me, one of the first concerns you're going to have is performance. For example, let's say you have the need to search on the encrypted field. A good example of an encrypted field that you'll likely have to search is the Social Security Number.

In my original benchmarks, I found the following results:Knowing that I was going to have to improve this performance, I started playing with some searching alternatives. First of all, it's obviously much faster to search an indexed column (especially one that is clustered), so my first goal was to generate an indexed column.

Ryan McGarty (my best friend and a damn fine programmer) and I discussed and quickly ruled out a basic hash. Sure, it'd be fast to search an indexed column containing the hash value, but that opens you up to a relatively simple plain text attack (especially with a known set of possible values). I decided that you could reduce the threat and still speed up the search by using hash buckets a la hashtables instead.

I concocted a hash function that produced a reasonable distribution within the buckets. My good friend and esteemed colleague David Govek pointed out that an MD5 hash would produce a pretty effective distribution between buckets (with high cardinality data like the social security number. David was right and I ended up with this hash function:

CREATE FUNCTION [dbo].[GroupData] 
(
 @String VARCHAR(MAX),
 @Divisor INT
) 
RETURNS INT
AS BEGIN

  DECLARE @Result INT;
  
  SET @Result = HASHBYTES('MD5', @String);
  
  IF (@Divisor > 0)
    SET @Result =  @Result % @Divisor;
  
  RETURN @Result;

END

I created the test data just as I had before, except that this time I also added the hash bucket. I created a clustered index on the bucket and I changed my select statement a little:

-- original select statement
SELECT *
FROM PersonData
WHERE 
  CONVERT(CHAR(9), DECRYPTBYKEY(SocialSecurityNumberEncrypted)) = '457555462'

-- hash key select statement
-- @Divisor is the divisor for the modulus operation in the hash function
SELECT *
FROM PersonData
WHERE 
  SocialSecurityNumberGroup = dbo.GroupData('457555462', @Divisor) AND
  CONVERT(CHAR(9), DECRYPTBYKEY(SocialSecurityNumberEncrypted)) = '457555462'

Here are my results:

So, what of the known plain text attack then?

So, I don't want to gloss over the plain text attack issue. Given the possible set of socials, the hashes would be very unlikely to have a collision. Thus, for most people, you'd be able to get their socials easily by hashing every possible social and joining to that table. By modulo dividing the hash value, I'm able to evenly distribute social security numbers among a known set of buckets. That means, I can control the approximate number of socials in each bucket given my set of values. I generally aim for about 1000 socials per bucket.

For example, an MD5 % 100 has a possible set of values from -100 to +100. That's 201 buckets so if you have 2010 rows of data to hash, you'll have about 10 rows per bucket. The benefit is that you now only have to decrypt 10 rows to find the exact row you're looking for. The detriment is that you've narrowed your possible result set. Within your own data set, you'd have narrowed it to 10 possible plaintext values; however, given that these values are unknown, you then have to look at the set of possible values.

Social security numbers have a set of possible values less than 1,000,000,000. It's hard to say exactly how many of them are the possible set of values, so let's say we're using only those socials currently in use by living Americans. The population of the United States at the time of writing was about 312,000,000. As I said, I usually aim for about 1,000 records per bucket. If I have 1,000,000 rows of data, I would modulo divide by 500 (1,001 buckets). If you knew my set of values, then you'd only have 1,000 possible values to reduce. Given that you know when and where I was born, you could probably narrow it to 20 or so possible socials.

But, you don't know my set of values, so you really have 312,000 values to chose from. Even if you did know the first 5 digits of my social security number (based on my state of issuance and my date of birth), your set of possible options would be so large, you'd probably be better off just pulling my credit report and getting my social that way.

Thus, while it seems to introduce a weakness to plain text attacks (and with low cardinality data it would be an issue), in the case of social security numbers, I don't believe it to be a reasonable attack.

Column Encryption in SQL Server 2008 with Symmetric Keys

Most of the time when I write blog posts, I do it to share ideas with my fellow developers. Sometimes I do it just so I can have a place to reference when I forget the syntax for something. This is one of those reference posts.

Recently I've been charged to column level encrypt some personally identifiable information. The present post is not intended to discuss the merits of column level encryption; rather, as I said it is to put a few code snippets up so that I can reference them later. If you should find yourself in a column level encryption predicament in a SQL Server 2008 environment, you may find these useful as well.

First thing's first. Get the database ready for column level encryption by creating a master key:

--if there is no master key create one
IF NOT EXISTS 
(
  SELECT * 
  FROM sys.symmetric_keys 
  WHERE symmetric_key_id = 101
)
CREATE MASTER KEY ENCRYPTION BY 
  PASSWORD = 'This is where you would put a really long key for creating a symmetric key.'
GO

Now, you'll need a certificate or a set of certificates with which you will encrypt your symmetric key or keys:

-- if the certificate doesn't, exist create it now
IF NOT EXISTS
(
  SELECT *
  FROM sys.certificates
  WHERE name = 'PrivateDataCertificate'
)
CREATE CERTIFICATE PrivateDataCertificate
   WITH SUBJECT = 'For encrypting private data';
GO

Once you have your certificates, you can create your key or keys:

-- if the key doesn't exist, create it too
IF NOT EXISTS
(
  SELECT *
  FROM sys.symmetric_keys
  WHERE name = 'PrivateDataKey'
)
CREATE SYMMETRIC KEY PrivateDataKey
  WITH ALGORITHM = AES_256
  ENCRYPTION BY CERTIFICATE PrivateDataCertificate;
GO

Before you can use your symmetric key, you have to open it. I recommend that you get in the habit of closing it when you're finished with it. The symmetric key remains open for the life of the session. Let's say that you have a stored procedure in which you open the symmetric key to decrypt some private data which your stored procedure uses internally. Someone who has access to the stored procedure can run it and then will have the key opened for use in decrypting private data. My point, close the key before you leave the procedure. Here's how you open and close keys.

-- open the symmetric key with which to encrypt the data.
OPEN SYMMETRIC KEY PrivateDataKey
   DECRYPTION BY CERTIFICATE PrivateDataCertificate;

-- close the symmetric key
CLOSE SYMMETRIC KEY PrivateDataKey;

Here's a little test script I wrote to demonstrate a few points. First, the syntax for encrypting and decrypting. Second, the fact that the the cipher text changes each time you do the encryption. This prevents a plain text attack.

-- open the symmetric key with which to encrypt the data.
OPEN SYMMETRIC KEY PrivateDataKey
   DECRYPTION BY CERTIFICATE PrivateDataCertificate;

-- somewhere to put the data
DECLARE @TestEncryption TABLE
(
  PlainText VARCHAR(100),
  Cipher1 VARBINARY(100),
  Cipher2 VARBINARY(100)
);

-- some test data
INSERT INTO @TestEncryption (PlainText)
SELECT 'Boogers'
UNION ALL
SELECT 'Foobar'
UNION ALL
SELECT '457-55-5462'; -- ignoranus

-- encrypt twice
UPDATE @TestEncryption
SET 
  Cipher1 = ENCRYPTBYKEY(KEY_GUID('PrivateDataKey'), PlainText),
  Cipher2 = ENCRYPTBYKEY(KEY_GUID('PrivateDataKey'), PlainText);

-- decrypt and display results  
SELECT
  *,
  CiphersDiffer = CASE WHEN Cipher1 <> Cipher2 THEN 'TRUE' ELSE 'FALSE' END,
  PlainText1 = CONVERT(VARCHAR, DECRYPTBYKEY(Cipher1)),
  PlainText2 = CONVERT(VARCHAR, DECRYPTBYKEY(Cipher2))
FROM @TestEncryption;

-- close the symmetric key
CLOSE SYMMETRIC KEY PrivateDataKey;

Conditional Check Constraints on SQL Server

I was on Stack Overflow the other day (something I'm just getting into . . . not sure I care that much for it yet, but we'll see. I'm definitely enjoying it more now that I'm not restricted on my behaviors because I lack reputation points).

In any event, someone asked me a question about conditional check constraints. The consensus seemed to be that you couldn't do it so I figured I'd post the solution on my blog as well.

Basically, the thought was that you couldn't put the check constraint on a subquery or an aggregate so you had to use a trigger only. Well, that's not technically true since you can write a function to do the aggregating for you. I'm not sure I like the idea, but it is in fact possible and I'm looking forward to reading all of your comments about the topic.

So, here's my script that comprises an entire test including a test table, the function, the constraint, some inserts, the results, and cleaning up:

CREATE TABLE CheckConstraint
(
  Id TINYINT,
  Name VARCHAR(50),
  RecordStatus TINYINT
)
GO

CREATE FUNCTION CheckActiveCount(
  @Id INT
) RETURNS INT AS BEGIN
  
  DECLARE @ret INT;
  SELECT @ret = COUNT(*) FROM CheckConstraint WHERE Id = @Id AND RecordStatus = 1;
  RETURN @ret;

END;
GO

ALTER TABLE CheckConstraint
  ADD CONSTRAINT CheckActiveCountConstraint CHECK (dbo.CheckActiveCount(Id) <= 1 OR RecordStatus <> 1);

INSERT INTO CheckConstraint VALUES (1, 'No Problems', 2);
INSERT INTO CheckConstraint VALUES (1, 'No Problems', 2);
INSERT INTO CheckConstraint VALUES (1, 'No Problems', 2);
INSERT INTO CheckConstraint VALUES (1, 'No Problems', 1);

INSERT INTO CheckConstraint VALUES (2, 'Oh no!', 1);
INSERT INTO CheckConstraint VALUES (2, 'Oh no!', 2);
INSERT INTO CheckConstraint VALUES (2, 'Oh no!', 1);
-- Msg 547, Level 16, State 0, Line 14
-- The INSERT statement conflicted with the CHECK constraint "CheckActiveCountConstraint". The conflict occurred in database "TestSchema", table "dbo.CheckConstraint".
INSERT INTO CheckConstraint VALUES (2, 'Oh no!', 2);

SELECT * FROM CheckConstraint;
-- Id   Name         RecordStatus
-- ---- ------------ ------------
-- 1    No Problems  2
-- 1    No Problems  2
-- 1    No Problems  2
-- 1    No Problems  1
-- 2    Oh no!       1
-- 2    Oh no!       2

ALTER TABLE CheckConstraint
  DROP CONSTRAINT CheckActiveCountConstraint;

DROP FUNCTION CheckActiveCount;
DROP TABLE CheckConstraint;

Stored Procedure to Unpivot a Table

When I first started blogging, I wrote a post about this 3 liner (well, technically) stored procedure to unpivot data. Well, I was new to blogging and I didn't really have all of the great tools that I have now, so it was a pretty crappy post.

Well, I was just flipping through my archives looking at the lack of SQL Server posts that I have and thought, "I really should rewrite that one and use a good highlighter and post some sample usage."

So, I did, but before I get to the stored procedure, why don't I explain a little bit about what unpivoting is? Sometimes you don't know what kind of data you're going to be collecting so you can't really create a third normal schema to store these data. Instead, you use something called an Attribute Value Pair table (or AVP for short).

This table ends up being tall instead of wide, but you can store any data you please in there. Problem is, how do you get to a full and meaningful record? Well, the process to take tall data and make it wide is called pivoting. If, however, you have wide tables and you need to seed this AVP table, that process is called unpivoting.

I had to do this several times and I didn't really care to write a view every time I had to unpivot, so I wrote a sproc instead. Here's that stored procedure and it should work on all SQL Server 2008 and SQL Server 2005:

CREATE PROCEDURE UnpivotTable
(
  @tableName AS VARCHAR(512),
  @whereClause AS VARCHAR(2000) = NULL,
  @commonColumns AS VARCHAR(2000) = NULL
) AS
-- ==========================================================
-- Author:        Patrick Caldwell
-- Create date:   2007/12/19
-- Description:   this procedure unpivots data in a table
--                specified in the parameters with an optional
--                where clause.  every line has been commented.
--                the commonColumns variable stores a list of
--                columns that should be on every row.
-- ==========================================================


-- a variable in which to store the query
DECLARE @query VARCHAR(MAX);

-- build the query
SELECT            @query = ISNULL(@query + ' ', '') + QueryLine
FROM
(
    SELECT        QueryLine = 'SELECT ' +
                    ISNULL(@commonColumns + ', ', '') +
                    'ColumnName = ''' + COLUMN_NAME + ''', ' +
                    'ColumnValue = CAST([' + COLUMN_NAME + '] AS NVARCHAR(4000)) ' +
                    'FROM ' + @tableName +
                    ISNULL(' WHERE ' + @whereClause, '') +
                    ' UNION ALL'
    FROM          INFORMATION_SCHEMA.COLUMNS
    WHERE         TABLE_SCHEMA + '.' + TABLE_NAME = @tableName

    UNION ALL

    SELECT        'SELECT ' +
                    ISNULL(@commonColumns + ', ', '') +
                    'NULL, NULL ' +
                    'FROM ' + @tableName + ' ' +
                    'WHERE 1 = 0'
) AS lines;

-- execute the query
EXEC(@query);

For the sake of example, I'm going to need a test table. Here's the one I'm using:

CREATE TABLE Pals
(
  Id TINYINT IDENTITY(1, 1), -- so what if I only have 255 pals?
  FirstName VARCHAR(128),
  LastName VARCHAR(128),
  Gender CHAR(1)
);

INSERT INTO Pals VALUES ('Lauren', 'Woody', 'F'); -- no, really . . . F
INSERT INTO Pals VALUES ('James', 'Brechtel', '?');
INSERT INTO Pals VALUES ('Ryan', 'McGarty', 'M');

And finally, here are some example usages:

EXEC UnpivotTable @tableName = 'dbo.pals'
/*
ColumnName ColumnValue
---------- -----------
Id         1
Id         2
Id         3
FirstName  Lauren
FirstName  James
FirstName  Ryan
LastName   Woody
LastName   Brechtel
LastName   McGarty
Gender     F
Gender     ?
Gender     M
*/

EXEC UnpivotTable @tableName = 'dbo.pals', @commonColumns = 'Id'
/*
Id   ColumnName ColumnValue
---- ---------- -----------
1    Id         1
2    Id         2
3    Id         3
1    FirstName  Lauren
2    FirstName  James
3    FirstName  Ryan
1    LastName   Woody
2    LastName   Brechtel
3    LastName   McGarty
1    Gender     F
2    Gender     ?
3    Gender     M
*/

EXEC UnpivotTable @tableName = 'dbo.pals', 
                  @commonColumns = 'Id', 
                  @whereClause = 'Gender = ''F'''
/*
Id   ColumnName ColumnValue
---- ---------- -----------
1    Id         1
1    FirstName  Lauren
1    LastName   Woody
1    Gender     F
*/

Converting Hexadecimal or Binary to Decimal on SQL Server 2008 and 2005

I just finished a blog post about Converting Decimal to Hexadecimal with T-SQL on SQL Server 2008 and 2005 and it got me thinking, "What if you have a hexadecimal string or a binary string and you want to convert it back to decimal?"

Well, in my previous article, I provided a SQL custom function that would allow you to convert from base 10 (decimal) to any other base you wanted. That way, you wouldn't need a Dec2Bin and a Dec2Hex function. Similarly, I don't think you should have both a Bin2Dec and a Hex2Dec to convert from binary or hexadecimal to decimal.

So, I wrote a custom function that converts from any base to base 10 and it looks a little like this:

CREATE FUNCTION ConvertFromBase
(
    @value AS VARCHAR(MAX),
    @base AS BIGINT
) RETURNS BIGINT AS BEGIN

    -- just some variables
    DECLARE @characters CHAR(36),
            @result BIGINT,
            @index SMALLINT;

    -- initialize our charater set, our result, and the index
    SELECT @characters = '0123456789abcdefghijklmnopqrstuvwxyz',
           @result = 0,
           @index = 0;

    -- make sure we can make the base conversion.  there can't
    -- be a base 1, but you could support greater than base 36
    -- if you add characters to the @charater string
    IF @base < 2 OR @base > 36 RETURN NULL;

    -- while we have characters to convert, convert them and
    -- prepend them to the result.  we start on the far right
    -- and move to the left until we run out of digits.  the
    -- conversion is the standard (base ^ index) * digit
 WHILE @index < LEN(@value)
        SELECT @result = @result + POWER(@base, @index) * 
                         (CHARINDEX
                            (SUBSTRING(@value, LEN(@value) - @index, 1)
                            , @characters) - 1
                         ),
               @index = @index + 1;

    -- return the result
    RETURN @result;

END

Here's a test query:

SELECT
   dbo.ConvertFromBase('110010110', 2) -- 406
  ,dbo.ConvertFromBase('120001', 3)    -- 406
  ,dbo.ConvertFromBase('626', 8)       -- 406
  ,dbo.ConvertFromBase('406', 10)      -- 406
  ,dbo.ConvertFromBase('196', 16)      -- 406
  ,dbo.ConvertFromBase('ba', 36);      -- 406

Converting Decimal to Hexadecimal with T-SQL on SQL Server 2008 and 2005

Yesterday, I was doing a little maintenance on our internal bugtracker.net installation. Bug tracker uses the first column of a result set to determine the background color of the issue. I wanted to create a nice fade effect between green and red, but that requires that I convert a decimal number to hexadecimal in SQL Server.

I didn't really want to write a Dec2Hex conversion function for SQL Server because I could very well end up needing a Dec2Bin function as well (if I ever wanted to convert decimal to binary in SQL), so I just wrote a custom function to convert a decimal number to any base between 2 and 36. The same SQL custom function can convert decimal numbers to hexidecimal or decimal to binary (if you need to go the other way, look here to convert any base to decimal in SQL). Here's what that looks like:

CREATE FUNCTION ConvertToBase
(
    @value AS BIGINT,
    @base AS INT
) RETURNS VARCHAR(MAX) AS BEGIN

    -- some variables
    DECLARE @characters CHAR(36),
            @result VARCHAR(MAX);

    -- the encoding string and the default result
    SELECT @characters = '0123456789abcdefghijklmnopqrstuvwxyz',
           @result = '';

    -- make sure it's something we can encode.  you can't have
    -- base 1, but if we extended the length of our @character
    -- string, we could have greater than base 36
    IF @value < 0 OR @base < 2 OR @base > 36 RETURN NULL;

    -- until the value is completely converted, get the modulus
    -- of the value and prepend it to the result string.  then
    -- devide the value by the base and truncate the remainder
    WHILE @value > 0
        SELECT @result = SUBSTRING(@characters, @value % @base + 1, 1) + @result,
               @value = @value / @base;

    -- return our results
    RETURN @result;

END

Here is a test query:

SELECT
   dbo.ConvertToBase(406, 2)   -- 110010110
  ,dbo.ConvertToBase(406, 3)   -- 120001
  ,dbo.ConvertToBase(406, 8)   -- 626
  ,dbo.ConvertToBase(406, 10)  -- 406
  ,dbo.ConvertToBase(406, 16)  -- 196
  ,dbo.ConvertToBase(406, 36); -- ba

Stored Procedure to Flip Staging Tables

We have several applications that are relatively data intensive. For the most part, the applications run just fine when executing simple queries against indexed tables. The problem comes when we need to aggregate data for reporting or perform queries against cross-joined or unioned tables. As a result, sometimes we create data tables that are periodically populated with the results of the slow cross-join or union and are subsequently indexed to optimize performance for future queries.


That's all well and good, but you can't really fill that table while the application is running queries against it, so what do you do? Well, you create a staging table, fill it, and the point your application at your new table, right?


Something I picked up from partitioning very large table during my data warehousing days is the idea that I can point a view at a table and treat it like a table and it will be almost as performant as the table with its indexes. Thus, if I want to have a staging table and a production table, I don't have to put any intelligence in my application; rather, I can leave the staging and swapping to the database.


For example, if I have a very large table of invoices (which I would, of course, love to have), then I could create two tables called Invoice1 and Invoice2. I could then point the view Invoice at Invoice1 and InvoiceStaging at Invoice2. Thus, any procedure or application that needs to build my staging table can do so always by referencing InvoiceStaging and my production table will always be referenced with Invoice.


The only difficulty really is switching the view to have it point to the new table and to point the staging view to the old table. I wrote a stored procedure that would look into a settings table, determine the current production and staging tables, swap them, and write the new settings back to the settings table. It was fine really and I didn't have any trouble with it, but one day I had an idea. I wrote this stored procedure to handle my switching for me and it does it all with nothing more than some of the system tables.

CREATE PROCEDURE [dbo].[FlipStagingTables]
(
  @TableName VARCHAR(255)
)
AS

  DECLARE @Active VARCHAR(255);
  DECLARE @Staging VARCHAR(255);

  SELECT 
    @Active = MAX(CASE v.name WHEN @TableName + 'Staging' THEN t.name ELSE NULL END),
    @Staging = MAX(CASE v.name WHEN @TableName THEN t.name ELSE NULL END)
  FROM sysdepends d
  INNER JOIN sysobjects v
    ON d.id = v.id
  INNER JOIN sysobjects t
    ON d.depid = t.id
  WHERE v.name IN (@TableName, @TableName + 'Staging');

  IF @Active IS NULL OR @Staging IS NULL
    SELECT @Active = @TableName + '1', @Staging = @TableName + '2';

  IF OBJECT_ID(@TableName) IS NOT NULL
    EXEC('ALTER VIEW ' + @TableName + ' AS SELECT * FROM ' + @Active);
  ELSE
    EXEC('CREATE VIEW ' + @TableName + ' AS SELECT * FROM ' + @Active);

  IF OBJECT_ID(@TableName + 'Staging') IS NOT NULL
    EXEC('ALTER VIEW ' + @TableName + 'Staging AS SELECT * FROM ' + @Staging);
  ELSE
    EXEC('CREATE VIEW ' + @TableName + 'Staging AS SELECT * FROM ' + @Staging);

  EXEC('TRUNCATE TABLE ' + @Staging);

A Table Valued Function to Split Strings


-- the function
CREATE FUNCTION SplitString
(
      @TargetString NVARCHAR(MAX),
      @Delimeter NVARCHAR(MAX)
)
 
-- the part repository
RETURNS @Parts TABLE
(
      PartId INT IDENTITY(1, 1),
      Part VARCHAR(MAX)
)
AS BEGIN
 
      -- just some variables to keep track of things
      DECLARE
            @CurrentIndex INT,
            @DelimeterIndex INT,
            @PartLength INT;
 
      -- initialize the loop
      SELECT
            @CurrentIndex = 0,
            @DelimeterIndex =CHARINDEX(@Delimeter, @TargetString, 0),
            @PartLength = @DelimeterIndex - @CurrentIndex;
 
      -- if the delimeter exists, continue the loop
      WHILE (@DelimeterIndex > 0) BEGIN
 
            -- add the part to the part repository
            INSERT INTO @Parts VALUES (SUBSTRING(@TargetString, @CurrentIndex, @PartLength));
 
            -- update the indexing information
            SELECT
                  @CurrentIndex = @CurrentIndex + @PartLength + LEN(@Delimeter),
                  @DelimeterIndex = CHARINDEX(@Delimeter, @TargetString, @CurrentIndex),
                  @PartLength = @DelimeterIndex - @CurrentIndex;
 
      END
 
      -- add whatever comes after the last delimeter
      INSERT INTO @Parts VALUES (SUBSTRING(@TargetString, @CurrentIndex, LEN(@TargetString) - @CurrentIndex + 1))
 
      RETURN
END