XOR is Not as Fancy as Malware Authors Think

FireEye recently posted some research about an attack leveraging the NetSupport Remote Access tool. The first stage of this attack uses a lot of obfuscation tricks to try to make reverse engineering more difficult.

David Ledbetter and I were chatting about some of the lengths the malware authors went through to obfuscate the content.

One of the major sources of complication is a complicated, iterative XOR:

(Image credit FireEye)

Unlike most malware that obfuscates content by XORing the content with a single byte / key, this malware appears to do something much more clever. See the content starting at ‘var tmpKeyLength = 1;’?

  1. XOR each character of the content with the first byte of the encryption key
  2. XOR characters of the content with bytes from the encryption key in the following pattern: 1, 2, 1, 2, 1, 2, 1, 2, …
  3. XOR characters of the content with bytes from the encryption key in the following pattern: 1, 2, 3, 1, 2, 3, 1, 2, 3, …

When malware uses step #1 alone -- or even a repeating single-key XOR -- I like to call it “Encraption”. It appears complicated, but is vulnerable to many forms of cryptanalysis and can be easily broken. Given that this malware did several levels of Encraption, did they manage to finally invent something more secure than a basic repeating key XOR?

Not even close.

XOR is Associative

One of the biggest challenges with using XOR in cryptography is that it is associative: you can rearrange parenthesis without impacting the final result. For example, consider again a single byte key and the following double XOR encryption:

  1. Take the content
  2. XOR each character by the value ‘123’
  3. XOR each character by the value ‘321’
  4. Emit the result

If we were to add parenthesis to describe the order of operations:

(Content XOR 123) XOR 321

Because XOR is associative, you can rearrange parenthesis (order of operations) to make it:

Content XOR (123 XOR 321)

Which gives 314:

image

So, encraption with two keys is still just encraption with a single key and is vulnerable to all of the same attacks.

But what about that rolling key?

The malware above used something more like a rolling key, however. It didn’t take a couple of single bytes. If the content was 100 bytes, it did 100 rounds of XOR based on the key. Surely that must be secure.

Fortunately? Unfortunately? The answer is no. If we remember the malware’s algorithm:

    1. XOR each character of the content with the first byte of the encryption key
    2. XOR characters of the content with bytes from the encryption key in the following pattern: 1, 2, 1, 2, 1, 2, 1, 2, …
    3. XOR characters of the content with bytes from the encryption key in the following pattern: 1, 2, 3, 1, 2, 3, 1, 2, 3, …

Consider the perspective of a single character. It gets encrapted by one byte of the key, and then a different byte of the key, and then a different byte of the key… and so on. And because XOR is associative, as we demonstrated above, that is the same thing as the single character being encrapted by a single byte.

A PowerShell Demonstration

Let’s take a look at a demonstration of this in PowerShell.

First, let’s look at a faithful re-implementation of the original algorithm:

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017

$stringToEncrypt = [char[]] "Hello World!"
$encrypted = $stringToEncrypt.Clone()
$key = 97,4,13,252,119,31,208,156,196,56

$tmpKeyLength = 1
while($tmpKeyLength -le $key.Length)
{
    $tmpKey = $key[0..$tmpKeyLength]
    for($i = 0; $i -lt $encrypted.Length; $i++)
    {
        $encrypted[$i] = $encrypted[$i] -bxor $tmpKey[$i % $tmpKey.Length]
    }
    $tmpKeyLength++
}

"Encrypted:"
([byte[]]$encrypted) | Format-Hex | Out-String

When you take a look at the result, here’s what you get:

image

Pretty impressive! Look at all those non-ASCII characters. This must be unbreakable!

To get the equivalent single-pass encraption key, we can just XOR the encrapted string with the original string. How?

XOR is Commutative

We can do this because XOR is commutative as well: you can rearrange the order of terms without impacting the result.

If Encrapted is:

Content XOR Key1 XOR Key2 XOR Key3

then we do:

Encrapted XOR Content

then we get:

Content XOR Key1 XOR Key2 XOR Key3 XOR Content

Because XOR is commutative, we can rearrange terms to get:

Content XOR Content XOR Key1 XOR Key2 XOR Key3

Anything XOR’d with itself can be ignored

One of the reasons XOR encraption works is that anything XOR’d with itself can be ignored. For example:

Encrypted = Content XOR Key

Decrypted = Encrypted XOR Key

By XORing some content with a key twice, you get back the original content. So back to where we got with the last section, if we XOR the final result with the original content and rearrange, we get:

Content XOR Content XOR Key1 XOR Key2 XOR Key3

That gives us an equivalent single key that we can use: Key1 XOR Key2 XOR Key3.

Here’s an example of figuring out this new single-pass key:

001
002
003
004
005
006
007
008

$newKey = New-Object 'char[]' $stringToEncrypt.Length
for($i = 0; $i -lt $stringToEncrypt.Length; $i++)
{
    $newKey[$i] = $encrypted[$i] -bxor $stringToEncrypt[$i] 
}

""
"Equivalent key: " + (([int[]]$newKey) -join ",")

And the result:

image

And to prove they give equivalent results:

001
002
003
004
005
006
007
008
009

$encrypted = $stringToEncrypt.Clone()
for($i = 0; $i -lt $encrypted.Length; $i++)
{
    $encrypted[$i] = $encrypted[$i] -bxor $newKey[$i]
}

""
"Easy encrypted:"
([byte[]]$encrypted) | Format-Hex | Out-String

image

The Nelson Moment

This is where we get to point and laugh a little. Remember how the malware repeatedly XORs the content with various bits of the key? It did far more damage than the malware author realized. Let’s consider the character in the content at position 0 for a moment:

    1. XOR with byte 0 of the key
    2. XOR with byte 0 of the key (thereby stripping the encraption altogether!)
    3. XOR with byte 0 of the key
    4. XOR with byte 0 of the key (thereby stripping the encraption altogether!)

Let’s consider byte 1 of the content

    1. XOR with byte 0 of the key
    2. XOR with byte 1 of the key
    3. XOR with byte 1 of the key (thereby stripping the work done in step 2)
    4. XOR with byte 1 of the key
    5. XOR with byte 1 of the key (thereby stripping the work done in step 4)

Depending on the length of the key and the content, this pattern of alternating doing work and removing the work that was previously done continues. This now takes what could have been a potentially strong key of 100s of bytes down to a super expensive way to compute single key!! Here’s a demo of encrapting some GUIDs:

image

Notice that some characters (28 at the beginning, c9 at offset 0x48) didn’t even get encrypted at all?

Remember folks, don’t roll your own crypto, and especially don’t roll your own crapto.

Leave a Reply