Decrypting Encrypted Database Objects

2013-01-08 - Cryptography, General, SQL Server Internals

Introduction

A few weeks ago my friend Brent Ozar (B|T) needed a quick way to decrypt an encrypted stored procedure in a customer database. There are quite a few tools out there that allow you to do this kind of thing, but in this particular instance he could not use an external tool and was looking for a T-SQL only solution. My response to him was to just use a known plaintext attack against the encryption algorithm. He promptly reminded me that most of us DBAs don't have a degree in encryption:

Brent Ozar's response

(Direct link to the video.)

As I do have some experience in the encryption field, I promised to write an article explaining what exactly I meant with that suggestion.

Known Plaintext Attack

A known plaintext attack against an encryption algorithm can be use when you have the ability to get you hand on a particular data set in the encrypted and the unencrypted form.

In cryptology the unencrypted record is usually called the plaintext and the encrypted record is called ciphertext. In the case of a known plaintext attack, you are going to get your hands on the ciphertext for a piece of known plaintext, hence the name.

Most modern encryption algorithms are not vulnerable against this type of attack. If you have two given ciphertexts and the plaintext for one of them, it does not make it any easier to decrypt the second ciphertext. Actually, it is usually not hard at all to get a known plaintext-ciphertext pair, so most cryptologists consider an encryption algorithm that is vulnerable against this attack as useless.

SQL Server Object Encryption

Every T-SQL programmability object that is created in a SQL Server database is stored as un-compiled source code with comments and all in a system table. This table cannot be directly accessed. However, you can use this query to see the object definitions:

[sql] SELECT * FROM sys.sql_modules;
[/sql]

The information we are looking for is returned in the definition column.

When you create an object in a SQL Server database and specify WITH ENCRYPTION SQL Server does two things to prevent spying eyes from getting to the plaintext object definition. First the data is stored in the system table in encrypted form. Second, the above query returns a NULL value in the definition column for such objects. So, to get the plaintext of an encrypted object back, we need to solve both problems.

Finding the Encrypted Definition

The system table that the actual definition is stored in is called sys.sysobjvalues and it is not directly accessible. However, if you connect to SQL Server using the Dedicated Administrator Connection you can select from it. The information we are looking for is stored in a VARBINARY(MAX) column called imageval.

Solving the first problem wasn't that hard, so let's move on to the second.

Mounting the Attack

Presumably to save time during object access, the algorithm that SQL Server uses to encrypt object definitions is very simple. It just takes the bytes in the imageval column and uses bitwise XOR with a byte pattern (called key pattern) on it.

XOR has the nice property that it is fully symmetric. If you have a bit parrtern A and a key pattern B and the result of the XOR operation is A ^ B = C, then the following two equations are true too: C ^ B = A and C ^ A = B (In T-SQL ^ is the symbol for the bitwise XOR operation.)

The first one means, that to decrypt the ciphertext you just need to XOR it again with the same key pattern. That operation can be done practically in no-time on modern hardware.

The second one allows us to calculate the key from a known plaintext-ciphertext pair. We will use this later.

If you can manage to keep the byte pattern secret, XOR encryption is the most secure encryption algorithm we currently know. The problem is that it is practically impossible to keep the key pattern a secret unless you are using a real One-Time Pad. (The article talks about using modular addition instead of XOR. However, XOR is just a bitwise modular addition.)

The problems usually get introduced during the generation of the key pattern. If any kind of algorithm is used to generate the pattern, then cracking the encryption comes down to understanding that algorithm.

In the case of SQL Server's object encryption we don't even need to go that far. SQL Server uses a pattern that is generated from the object_id and the object_type of the encrypted object. (There might be other parameters in play, but I have never seen any evidence for that.) So if we can get SQL Server to encrypt a known object for us while using the same object_id as the object we are trying to decrypt, we could calculate the key pattern by just using XOR to combine the plaintext and the ciphertext.

To get SQL Server to do just that is easy. We just need to alter the encrypted object to temporarily replace it with a known object, grab the sys.sysobjvalues.imageval value and undo the replace operation. The undo piece is the possible by wrapping all this in a transaction.

The calculation afterwards to first get to the key pattern and then to the plaintext of the object we are after is not quite trivial, because we cannot just XOR two VARBINARY(MAX) values with each other. But it is still simple: We just have to use a loop going through the bytes one at a time to manually apply the XOR operation.

The Code

To make this all easy to use, I created a short stored procedure that automates all the steps involved:

[sql] CREATE PROCEDURE dbo.ObjectEncryptionCracker
@object_name NVARCHAR(MAX)
WITH ENCRYPTION
AS
BEGIN
DECLARE @secret VARBINARY(MAX);
DECLARE @known_encrypted VARBINARY(MAX);
DECLARE @known_plain VARBINARY(MAX);
DECLARE @object_type NVARCHAR(MAX);

SELECT @secret = imageval
FROM sys.sysobjvalues
WHERE objid = OBJECT_ID(@object_name);

DECLARE @cmd NVARCHAR(MAX);
SELECT @cmd = CASE type_desc
WHEN 'SQL_SCALAR_FUNCTION'
THEN 'ALTER FUNCTION ' + @object_name + '()RETURNS INT WITH ENCRYPTION AS BEGIN RETURN 0;END;'
WHEN 'SQL_TABLE_VALUED_FUNCTION'
THEN 'ALTER FUNCTION ' + @object_name + '()RETURNS @r TABLE(i INT) WITH ENCRYPTION AS BEGIN RETURN END;'
WHEN 'SQL_INLINE_TABLE_VALUED_FUNCTION'
THEN 'ALTER FUNCTION ' + @object_name + '()RETURNS TABLE WITH ENCRYPTION AS RETURN SELECT 0 i;'
WHEN 'SQL_STORED_PROCEDURE'
THEN 'ALTER PROCEDURE ' + @object_name + ' WITH ENCRYPTION AS RETURN 0;'
END
FROM sys.objects
WHERE object_id = OBJECT_ID(@object_name);

SELECT @cmd = REPLICATE(CAST(CHAR(32) AS NVARCHAR(MAX)), DATALENGTH(@secret)) + @cmd;

SELECT @known_plain = CAST(@cmd AS VARBINARY(MAX));

BEGIN TRAN;
EXEC(@cmd);
SELECT @known_encrypted = imageval
FROM sys.sysobjvalues
WHERE objid = OBJECT_ID(@object_name);
ROLLBACK;

DECLARE @i INT = 0;
DECLARE @plain VARBINARY(MAX) = 0x;

WHILE @i < DATALENGTH(@secret)
BEGIN
SET @plain = @plain
+ CAST(REVERSE(CAST(CAST(SUBSTRING(@secret, @i, 2) AS SMALLINT)
^ CAST(SUBSTRING(@known_plain, @i, 2) AS SMALLINT)
^ CAST(SUBSTRING(@known_encrypted, @i, 2) AS SMALLINT) AS BINARY(2))) AS BINARY(2));
SET @i += 2;
END

SET @cmd = N'SELECT (SELECT ''--''+CHAR(13)+CHAR(10)+''GO''+CHAR(13)+CHAR(10)+'
+ N'CAST(@plain AS NVARCHAR(MAX))+CHAR(13)+CHAR(10)+''GO''+CHAR(13)+CHAR(10)+''--'''
+ N' AS [processing-instruction(sql)] FOR XML PATH(''''),TYPE) AS [object_definition for '
+ REPLACE(@object_name, ']', ']]') + ']';
EXEC sp_executesql @cmd, N'@plain VARBINARY(MAX)', @plain;
END;
[/sql]

The procedure takes the name of the object we are trying to decrypt as parameter. It first determines the object type of that object and creates an ALTER statement for it. It then pads the beginning of that statement with enough spaces to cover all of the ciphertext. This gives us a clean uniform and most importantly long enough known plaintext. (This is now technically a Chosen-Plaintext-Attack, not just a Known-Plaintext-Attack, to be exact.)

Afterwards the procedure replaces the object inside of a transaction and captures the ciphertext for our known plaintext.

The last step is to do the XOR calculation in a loop and then return the decrypted object definition.

Currently the procedure can only handle functions and stored procedures. If you need to decrypt Views or Triggers, you can just add the missing alter statements to the CASE construct in the beginning. The procedure also needs to be able to replace the object. If the object is referenced by another object with schemabinding, you first need to remove that restriction manually.

Finally, you need to be connected to you instance using the Dedicated Administrator Connection when execution the procedure as it will not work otherwise.

Summary

To decrypt an encrypted SQL Server database object, the hardest part is to get access to the encrypted data. However, if you can use the Dedicated Administrator Connection, you have access to the data. Once there you can simply decrypt the definition using a key pattern that you can calculate out of the plaintext and the ciphertext of a known object of the same type and with the same object_id.

As always, if you have questions or feedback, feel free to use the comment functionality below.

Categories: Cryptography, General, SQL Server Internals

5 Responses to Decrypting Encrypted Database Objects

Leave a Reply