Decrypting Pushdo Botnet Messages

While looking at some Pushdo botnet messages recently, I noticed a repeating pattern in the data. Here is an example, taken from an area where the pattern is most obvious:

0340  13 63 cc 69 13 63 cc 69 13 63 cc 69 53 63 cc 2b   .c.i.c.i.c.iSc.+
0350  13 63 cc 69 13 63 cc 69 13 63 cc 69 13 63 cc 69   .c.i.c.i.c.i.c.i
0360  13 63 cc 69 13 63 cc 69 13 63 cc 69 13 63 cc 69   .c.i.c.i.c.i.c.i

This looked to me like a flaw in the encryption that potentially could be used for detection purposes. It might even be possible to automatically break the encryption.

It is not hard to guess the cause of this pattern. The data was encrypted with a four byte key, and what we see here is the result of encrypting a block of nulls. Null blocks are an expected part of most program files and not unusual in data files, and this Pushdo message certainly contains both. Looking around in the message data, we can see that even where non-null data is mixed in, the underlying pattern can be recognized.

0030  — – — – — – 15 c8 fc 31 20 20 3f 19 1a 63 . .j…..1  ?..c
0040  d2 69 89 63 3c 1b 7c db 45 69 00 63 cc 69 13 63 .i.c<.|.Ei.c.i.c
0050  1c 69 21 94 04 47 25 94 fa 5e 3d 9c cc 7f 13 63 .i!..G%..^=….c
0060  cc 69 13 b3 cc 5f 22 91 fd 5c 2b 91 fd 5f 24 91   .i…_”..\+.._$.

If the encryption was done using a simple XOR, the four pattern bytes would serve as a key to decrypt the message data. But the Pushdo encryption algorithm is a bit more complicated than that. A recent in-depth analysis by Fortinet’s Kyle Yang reveals the encryption algorithm.

Pushdo encryption uses three key bytes, which we will refer to as key0, key1, and key2. A new key is generated whenever the infected computer is restarted. Here is how the encryption is done.

(plain byte 0) XOR key0 = (encrypted byte 0)
(plain byte 1) – key1 = (encrypted byte 1)
(plain byte 2) + key2 = (encrypted byte 2)
(plain byte 3) XOR (key1 + key2) = (encrypted byte 3)

One of the most important rules for encryption systems is that security should depend on the keys, not on the secrecy of the encryption algorithm. In this case a bit of reverse engineering has revealed the algorithm, so whatever security remains is provided by the keys.

At this point it looks like we have all the information we need to decrypt this message. We know how the encryption works, and we should be able to calculate the key from the repeating pattern. But it would be convenient for us to be able to use the pattern itself as the key, if that is possible.

Notice that the last encryption rule contains an unnecessary complication that does not improve security. Adding key1 and key2 only serves to produce another static key byte. For our decryption we can simplify this rule by combining key1 and key2:

(plain byte 3) XOR key1.2 = (encrypted byte 3)

The plus and minus operations must also be reversed, so the new rules for decryption are:

(encrypted byte 0) XOR key0 = (plain byte 0)

(encrypted byte 1) + key1 = (plain byte 1)

(encrypted byte 2) – key2 = (plain byte 2)

(encrypted byte 3) XOR key1.2 = (plain byte 3)

To find the key bytes from the pattern bytes, we can rearrange the decryption rules this way:

key0 = (plain byte 0) XOR (pattern byte 0)

key1 = (plain byte 1) – (pattern byte 1)

key2 = – (plain byte 2) + (pattern byte 2)

key1.2 = (plain byte 3) XOR (pattern byte 3)

The pattern bytes need to be aligned with the encryption rules before we can find the key bytes. We could test all four possibilities, but a quicker way to do this is by looking at the start of the data. We know from reverse engineering that the message has an 8 byte header, which means the data starts at frame offset 0×003e, so the pattern byte that falls here will correspond to key0. The pattern bytes are cc 69 13 63.

0030  — – — – — – 15 c8 fc 31 20 20 3f 19 1a 63 . .j…..1  ?..c
key   — – — – — – — – — – — – — – 13 63
0040  d2 69 89 63 3c 1b 7c db 45 69 00 63 cc 69 13 63 .i.c<.|.Ei.c.i.c
key   cc 69 13 63 cc 69 13 63 cc 69 13 63 cc 69 13 63

Based on this alignment the pattern byte identities are:

pattern byte 0 = 0×13
pattern byte 1 = 0×63
pattern byte 2 = 0xcc
pattern byte 1.2 = 0×69

Using the equations above, with the plain bytes set to zero, the key bytes are:

key0 = 0×13
key1 = 0×9d
key2 = 0xcc
key1.2 = 0×69

To test this we can decrypt some message data to see if we get the correct result. The block below was chosen at random from an area known to contain hard coded IP addresses.

0060  cc 69 13 b3 cc 5f 22 91 fd 5c 2b 91 fd 5f 24 91   .i…_”..\+.._$.
key   cc 69 13 9d cc 69 13 9d cc 69 13 9d cc 69 13 9d
plain 00 00 00 50 00 36 31 2e 31 35 38 2e 31 36 37 2e
text                  6  1  .  1  5  8  .  1  6  7  .

0070  01 50 13 7b cc 69 13 63 cc 39 13 94 03 5d 3d 94   .P.{.i.c.9…]=.
key   cc 69 13 9d cc 69 13 9d cc 69 13 9d cc 69 13 9d
plain 35 39 00 18 00 00 00 00 00 60 00 31 37 34 2e 31
text   5  9                             1  7  4  .  1

0080  ff 5a 3d 94 fc 5d 3d 95 fd 59 13 79 cc 69 13 63   .Z=..]=..Y.y.i.c
key   cc 69 13 9d cc 69 13 9d cc 69 13 9d cc 69 13 9d
plain 33 33 2e 31 30 34 2e 32 31 30 00 16 00 00 00 00
text   3  3  .  1  0  4  .  2  1  0

0090  cc 39 13 95 fe 58 3d 95 ff 59 3d 95 fa 5b 23 9b   .9…X=..Y=..[#.
key   cc 69 13 9d cc 69 13 9d cc 69 13 9d cc 69 13 9d
plain 00 50 00 32 32 31 2e 32 33 30 2e 32 2e 32 30 38
text            2  2  1  .  2  3  0  .  2  .  2  0  8

The IP addresses found above in the decrypted block match ones known to be used by this version of Pushdo, so we can safely say the decryption is correct. Automated detection should be possible by picking the key from the message and applying it to a known block like the one above. Even if the IP addresses are changed, their presence in this format can be detected, along with other parts of the structure they are held in.

Unfortunately, sooner or later the encryption algorithm will be changed. It can be recovered by reverse engineering, but we would like to handle the change automatically, if that is possible.

We have some knowledge about the unencrypted data, for example we know that the data block seen here contains a number of IP addresses in text format. More of this kind of predictable data can likely be found. So we should be able to find the key, and we have all of the encrypted data and some of the unencrypted data.

With this information it may be possible to derive the arithmetic or logic operations used to encrypt each of the four bytes. Simple operations like XOR, plus and minus should not be hard to identify. Only operations that do not destroy data can be used, so it may be possible to generate a list of acceptable operations that are not excessively complex. As we saw with the fourth rule, overly complex operations may be reduced to simpler ones. In this sort of analysis we would probably not even be aware of the reduction.