Secret Codes And SQL Server, Part 2: Pimp Your Encryption Algorithms.

crypt2_6

We had a little play around writing our own encryption algorithms and cracking them in Secret Codes And SQL Server, Part 1: Writing Our Own Encryption Algorithm and Cracking it.

I thought I’d see if we can go a step further and start having a look at how we could take those basic ideas and try to make them a little more secure.

In part 1 we looked at a basic XOR algorithm and how it could easily be cracked with a simple brute force attack, we then added some complexity by character shifting the characters, that made it slightly more resistant to a brute force attack but with a little statistical analysis we were still able to crack it.

Undercover Encryption Version 3: Soup Up The Key

One of the major weaknesses that our Caesar Cypher algorithm from Part 1 had was that it was a straight substitution algorithm and that a particular encrypted character always mapped directly to it’s unencrypted counterpart.  This made the sort of statistical analysis that we looked at very simple.

To get around this we need to find a way to make it possible for a single character to be encrypted in a number of different ways.

Previously we’d been using a single byte (8 bit) key, this key would be applied to each character of the plain text in turn.

What if we were to increase the size of our key to four bytes (32 bit)?

With a four byte key, we’d be able to apply a single key to multiple characters of plain text.  As an ASCII code is one byte, a single four byte key could be applied to four characters.

With our previous single byte key examples, what would have happened if we’d encrypted the string ‘AAAA’?  Let’s give it a go….


EXEC [dbo].[EncryptData_v2] 'AAAA', 156

ÞÞÞÞ

Four matching characters all representing ‘A’

Now lets have a think about what’s really happening here….

crypt2

But what if we were going to use a 32bit key, lets say something like,

11110000000011111010101001010101

and apply that to our four character string.

crypt2_2

In this case each 8 bit ASCII character is applied to a different portion of the key and the result?  Out string of matching characters now encrypts as a string of four different characters.  Lets have a look at the implementation of that in SQL.


CREATE PROC [dbo].[EncryptData_v3]
(@KEY BIGINT,
@PlainText VARCHAR(MAX))

AS

BEGIN

DECLARE @CypherText VARCHAR(MAX) = ''
DECLARE @Counter INT = 1;
DECLARE @TextBlock CHAR(4);
DECLARE @Block BIGINT = 0;
DECLARE @EncryptedBlock BIGINT = 0;

WHILE @Counter <= (DATALENGTH(@PlainText))
BEGIN
 --get next 4 byte block
 SET @TextBlock = SUBSTRING(@PlainText,@Counter, 4)

--get ACSII representation of @textblock
 SET @Block = CAST(ASCII(SUBSTRING(@TextBlock,1,1)) AS BIGINT) * 16777216 -- Left shift ASCII code by 3 bytes
 SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,2,1)) AS BIGINT) * 65536 -- Left shift ASCII code by 2 bytes
 SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,3,1)) AS BIGINT) * 256 -- Left shift ASCII code by 1 byte
 SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,4,1)) AS BIGINT)

--XOR 4 byte key against block
 SET @EncryptedBlock = @Block ^ @Key

--convert encrypted block into string
 SET @TextBlock = CHAR(@EncryptedBlock / 16777216) + CHAR((@EncryptedBlock / 65536) & 255) + CHAR((@EncryptedBlock / 256) & 255) + CHAR((@EncryptedBlock) & 255)

-- Build Cypher Text string
 SET @CypherText = @CypherText + @TextBlock

SET @Counter = @Counter + 4
END

SELECT @CypherText

END

So let’s give it a go using the example from above,


EXEC EncryptData_v3 4027558485, 'AAAA'

±Në

and BOOM!  We’re no have our encrypted character matching our unencrypted.  That’s going to make a statistical analysis attack much harder.  Ok, this isn’t water tight, we are going to get repetitions every fourth character so I don’t think I’d trust it in the real world but as with my examples in Part 1, I’m going to call that good enough to resist a Statistical Analysis Attack and as a 32bit key has over 4 billion possible values I’ll also say that it’s pretty strong against a brute force attack.

But hold on once again!  Those folks at MI5 have decoded our message yet again, how did they do it this time?

Plain Text Attack

crypt2_7

There’s one major flaw in any straight XOR based encryption routine and that is that if you know a section of the plain text and you know it’s corresponding cypher text, XORing the two against each other will give us the key that was used to encrypt the message.

Lets take a look at what happens if we XOR the plain text with the cypher text from our previous example.

crypt2_3

And with the key we’re going to be free to unencrypt any message that was encrypted using that key.

Below is the code for the ‘Crack-O-Matic’ a little procedure that will take in four characters of plain text and the corresponding cypher text characters and spit out the key.


CREATE PROC [dbo].[Crack_O_Matic_v3]
(@PlainText CHAR(4),
@CypherText CHAR(4))

AS

BEGIN

DECLARE @PlainBin BIGINT
DECLARE @CypherBin BIGINT

--get ACSII representation of @textblock
SET @PlainBin = CAST(ASCII(SUBSTRING(@PlainText,1,1)) AS BIGINT) * 16777216 -- Left shift ASCII code by 3 bytes
SET @PlainBin = @PlainBin + CAST(ASCII(SUBSTRING(@PlainText,2,1)) AS BIGINT) * 65536 -- Left shift ASCII code by 2 bytes
SET @PlainBin = @PlainBin + CAST(ASCII(SUBSTRING(@PlainText,3,1)) AS BIGINT) * 256 -- Left shift ASCII code by 1 byte
SET @PlainBin = @PlainBin + CAST(ASCII(SUBSTRING(@PlainText,4,1)) AS BIGINT)

--get ACSII representation of @textblock
SET @CypherBin = CAST(ASCII(SUBSTRING(@CypherText,1,1)) AS BIGINT) * 16777216 -- Left shift ASCII code by 3 bytes
SET @CypherBin = @CypherBin + CAST(ASCII(SUBSTRING(@CypherText,2,1)) AS BIGINT) * 65536 -- Left shift ASCII code by 2 bytes
SET @CypherBin = @CypherBin + CAST(ASCII(SUBSTRING(@CypherText,3,1)) AS BIGINT) * 256 -- Left shift ASCII code by 1 byte
SET @CypherBin = @CypherBin + CAST(ASCII(SUBSTRING(@CypherText,4,1)) AS BIGINT)

SELECT @PlainBin ^ @CypherBin

END

Shall we see it in action?  Lets plug in the plain text ‘AAAA’ and cypher text ±Në and have a look at what comes out.


EXEC Crack_O_Matic_v3 'AAAA', '±Në'

4027558485

And that’s our the key that we originally used to encrypt the message, drat foiled again!!!

Undercover Encryption Version 4: Shift The Key

So how do we protect our data from the plain text attack that we’ve seen above.  One way would be to introduce a second XOR operation.  Think about what would happen if we were to first XOR our data against the key and then bit shift the key and XOR the encrypted data against the newly bit shifted key?

Lets have a look…

crypt2_4

The plain text of 11011101 is encrypted as 00100010.

What happens now if we try to perform a plain text attack and XOR the plain text against the cypher text?

crypt2_5

The value that is returned no longer matches the key.  This is exactly how algorithms such as DES work, although there is a little more juggling about going on essentially DES will XOR the data against a key, the key is then bit shifted and the data is XORed again. This is repeated 16 times to produce the final cypher text.

How do we go about decrypting this?  All you need to do is just follow the whole process in reverse, firstly apply the cypher text against the bit shifted key and then apply it to the original key to return the plain text.

We can implement this in SQL with the following (I’m only going to go through two phases in the code here), the parameter @encrypt should be set to 1 when encrypting and 0 when decrypting.

CREATE PROC [dbo].[EncryptData_v4]
(@KEY BIGINT,
@PlainText VARCHAR(MAX),
@Encrypt BIT = 1)

AS

BEGIN

DECLARE @CypherText VARCHAR(MAX) = ''
DECLARE @Counter INT = 1;
DECLARE @TextBlock CHAR(4);
DECLARE @Block BIGINT = 0;
DECLARE @EncryptedBlock BIGINT = 0;
DECLARE @Key1 BIGINT = 0;
DECLARE @Key2 BIGINT = 0;

--generate keys
SET @Key1 = @Key

--left shift the key to form key 2
SET @Key2 = @Key * 2
IF @Key2 > 4294967295 --if MSB was 1, wrap around to the LSB
SET @Key2 = (@Key2 - 4294967296) + 1

WHILE @Counter <= (DATALENGTH(@PlainText))
BEGIN
--get next 4 byte block
SET @TextBlock = SUBSTRING(@PlainText,@Counter, 4)

--get ACSII representation of @textblock
SET @Block = CAST(ASCII(SUBSTRING(@TextBlock,1,1)) AS BIGINT) * 16777216 -- Left shift ASCII code by 3 bytes
SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,2,1)) AS BIGINT) * 65536 -- Left shift ASCII code by 2 bytes
SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,3,1)) AS BIGINT) * 256 -- Left shift ASCII code by 1 byte
SET @Block = @Block + CAST(ASCII(SUBSTRING(@TextBlock,4,1)) AS BIGINT)

IF @Encrypt = 1 --encrypt data
BEGIN
--begin first round XOR
--XOR 4 byte key against block
SET @EncryptedBlock = @Block ^ @Key1

--begin second round XOR
SET @EncryptedBlock = @EncryptedBlock ^ @Key2
END
ELSE --decrypt data, apply keys in reverse order
BEGIN
--begin first round XOR
--XOR 4 byte key against block
SET @EncryptedBlock = @Block ^ @Key2

--begin second round XOR
SET @EncryptedBlock = @EncryptedBlock ^ @Key1
END

--convert encrypted block into string
SET @TextBlock = CHAR(@EncryptedBlock / 16777216) + CHAR((@EncryptedBlock / 65536) & 255) + CHAR((@EncryptedBlock / 256) & 255) + CHAR((@EncryptedBlock) & 255)

-- Build Cypher Text string
SET @CypherText = @CypherText + @TextBlock

SET @Counter = @Counter + 4
END

SELECT @CypherText

END

Shall we see how that looks in action?


EXEC EncryptData_v4 4027558485, 'SQLUndercover', 1

CA²«~t›Œsˆ›b0ÞÞ

which of course we can decrypt by flicking the @encrypt flag to 0.


EXEC EncryptData_v4 4027558485, 'CA²«~t›Œsˆ›b0ÞÞ', 0

SQLUndercover

Looking good!  But those fiends at MI5 have managed to get hold of the first four characters of both our plain text and cypher text and are using the Crack-O-Matic to perform a plain text attack.  How did they get on?


EXEC Crack_O_Matic_v3 'SQLU', 'CA²«'

269549310

Well that key isn’t going to get them very far, it looks like we’ve finally out witted MI5 (BTW, the CIA gave up long ago).  Or have we?  We’ve still got a major problem, we’re using the same key to encrypt and decrypt data.  What that means is that anyone who knows the key to encrypt can also decrypt.

It looks like we’ve got a mole here at SQLUndercover and our key has been leaked to MI5.  They’ve only gone and foiled us again.

Please note that these and any algorithms in this series are purely for demonstration purposes, they’re not secure and we wouldn’t recommend using them in a production environment.

One thought on “Secret Codes And SQL Server, Part 2: Pimp Your Encryption Algorithms.

Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: