As a “Crypto Girl” should, I wish to report that the latest Android malware, Android/DroidKungFu, uses AES encryption.

It is certainly not the first time Android malware use cryptographic encryption – we have already seen use of DES in Android/Geinimi or Android/HongTouTou – but this would appear to be the first use of AES on Android (AES has already been reported in Symbian malware such as SymbOS/InSpirit).

In Android/DroidKungFu, the malware uses AES to encrypt the two exploits it uses:

• CVE-2009-1185: packaged as gjsvro. located in the malware’s assets
• CVE-2010-EASY (rage against the cage): named ratc,  in the malware’s assets

We can’t really figure out why the malware authors specifically used AES, as a simple XOR on the exploits would have bypassed hash-based AV-signatures (signatures based on a hash of those executables). Is it just because there’s an AES class available?

The malware decrypts the files using a hard-coded key in a malicious utility class (named Utils):

private static byte[] defPassword = { 70, 117, 99, 107, 95, 115, 69, 120,
  121, 45, 97, 76, 108, 33, 80, 119 };

To decrypt the exploits, we can write some Java source code that reads the encrypted assets, decrypts it with AES using the hard-coded key, and dumps the decrypted data.

The decryption routine can be copy-pasted from a disassembly of the malware:

public static byte[] decrypt(byte[] paramArrayOfByte)
throws Exception  {
 byte[] arrayOfByte = defPassword;
 SecretKeySpec localSecretKeySpec = new SecretKeySpec(arrayOfByte, "AES");
 Cipher localCipher = Cipher.getInstance("AES");
 localCipher.init(2, localSecretKeySpec);
 return localCipher.doFinal(paramArrayOfByte);
}

Then, reading the asset and dumping the output is just a matter of using the Java FileInput/OutputStream
and ByteArrayInput/OutputStream classes.

ByteArrayOutputStream bout = new ByteArrayOutputStream();
FileInputStream fin = new FileInputStream(filename);
int c;
while ((c = fin.read()) != -1) {
  bout.write(c);
}
bout.close();
fin.close();
byte [] decrypted = decrypt(bout.toByteArray());
ByteArrayInputStream bin = new ByteArrayInputStream(decrypted);
String outputfilename = filename + ".decrypt";
FileOutputStream fout = new FileOutputStream(outputfilename);
while ((c = bin.read()) != -1) {
  fout.write(c);
}
fout.close();
bin.close();

A quick look to the strings shows the assets are decrypted successfully:

$ strings ratc.decrypted
...
/system/lib/proc/%d/cmdline/sbin/adb
[*] CVE-2010-EASY Android local root exploit (C) 2010 by 743C
[*] checking NPROC limit ...
[-] getrlimit...

Android/DroidKungFu was discovered by Pr. Xuxian Jiang and his team. Thanks for sharing samples.

Stay tuned!

– the Crypto Girl

When analyzing a new botnet, I tend to focus heavily on the network messages. After all, they are the glue that holds the botnet together. So one of the first things I did, when working on our new analysis of the Ozdok/Mega-D botnet, was to look at the messages and discover that they were encrypted. Of course this is not unusual, and after deciding the encryption was not something simple, I went to the bot code to see what was being used.

It soon developed that the encryption used was DES (Data Encryption Standard), in ECB mode. The cryptographic functions used are in the Microsoft Windows standard ADVAPI32 library. Clearly this should not be vulnerable to cryptanalysis or a brute force attack, not in the time available for anti-virus scanning. It was easy to find the key, which can be seen in the disassembled code below.

00408DE4    C645 EC 61     MOV BYTE PTR SS:[EBP-14],61        ; key ‘a’
00408DE8    C645 ED 62     MOV BYTE PTR SS:[EBP-13],62        ; ‘b’
00408DEC    C645 EE 63     MOV BYTE PTR SS:[EBP-12],63        ; ‘c’
00408DF0    C645 EF 64     MOV BYTE PTR SS:[EBP-11],64        ; ‘d’
00408DF4    C645 F0 65     MOV BYTE PTR SS:[EBP-10],65        ; ‘e’
00408DF8    C645 F1 66     MOV BYTE PTR SS:[EBP-F],66         ; ‘f’
00408DFC    C645 F2 67     MOV BYTE PTR SS:[EBP-E],67         ; ‘g’
00408E00    C645 F3 68     MOV BYTE PTR SS:[EBP-D],68         ; ‘h’

So the key was “abcdefgh”, really nothing more than a lower case text password. Maybe the botnet herder was not too worried about security and expected to change the key frequently, but this did seem a little weak.

This made me wonder how weak this key really is. The only practical approach would be a brute force attack, where we try all the keys to see which one works. The DES key is 56 bits long, meaning there are 2**56 possible keys (2 to the 56th power), or in decimal numbers 2**56 = 72,057,594,037,927,935, that is 72 million billion keys.

But if only lower case letters are used, as they are in the bot, the number of keys to try is only 26**8 = 208,827,064,576. And it gets worse. DES only uses 56 bits for the key, and the 8 letters have 8 x 8 = 64 bits, so there are 8 bits too many. The official way to fix this is to drop the lowest bit from each letter, so that “b” (01100010) and “c” (01100011) both become 01100010. This means if we try “b”, we don’t need to try “c” because it is the same. The key “abcdefgh” is the same as “abbddffg“, and the real number of lower case letter keys to try is 14**8 = 1,475,789,056. Not impossible millions of billions, but just a billion and a half.

How much time would it take to search that many keys? One way to get a rough idea is to decrypt a large file and see how long it takes. A 800,000,000 byte file has 100,000,000 eight byte blocks, and takes that many DES operations to decrypt. This should give some idea of the time needed to test 100,000,000 keys. Running this test with mcrypt on an Intel Core2 Quad Q8400 (R) at 2.66 ghz, results in a decryption time of less than 70 seconds, about 1.4 million keys per second. For 1,475,789,056 keys that would be 1033 seconds or about 17 minutes.

If digits and lower case letters are allowed, there are 19**8 = 16,983,563,041 keys, and the search time would be 11,888 seconds or 198 minutes. Include upper case letters and there are 33**8 = 1,406,408,618,241 keys, and the time goes up to 984,486 seconds or 273 hours. To search all of the 72,057,594,037,927,935 possible keys at this rate would require 50,440,315,827 seconds, or about 1599 years.

The search times would certainly be far shorter with software written specially for this purpose and a more powerful computer. Even better times could be achieved with a hardware DES processor, especially if several were run in parallel. In the test 1.4 million decryptions were done per second, but some dedicated chips claim to process as many as 30 million DES decryptions per second.

So for the lower case letter key found in Ozdok, we are almost at the point where the key can be searched quickly enough for antivirus purposes. For keys with a wider range of values the times become too great, at least for the present time.

Part of the problem here derives from a basic weakness in the setting of encryption keys. Users typically will be asked to enter the key, so it can only include ordinary text bytes. The range of key values is seriously limited by this. DES aggravates the problem by folding text characters together, further reducing the real world key space. It is possible to process the password into a better key, but that does not help much if the algorithm used for this is known, and normally it cannot be kept secret. One practical way to reduce the problem is to employ an encryption system with a longer key, but only a fraction of the larger key space will be used.

In any case we can certainly learn something from these calculations. Keys and passwords with a limited range of characters are not just unsafe, they can actually compromise an otherwise secure system.

To find out more about the Ozdok/Mega-D botnet and its hidden messages, take a look at the new analysis.

Recently I’ve been working on an analysis of Sasfis botnet communications. During the tests I noticed that when the bot installs itself, it adds a registry key named “idid”, with some random looking data in it. The data was added under the name “url0″, so it seemed like it must be an encrypted URL. Here is an example from one of the bot variants:

Key Name:          HKEY_CLASSES_ROOT\idid

Name:            url0

00000000   1e 9b 6d d8  89 e6 c4 50  7f fd 13 6b  fa e2 f4 17

00000010   1a 80 78 cc  d6 bb c4 55  73 b5 07 77  a4 81 3a 71

00000020   a4 98 ba d8  2c 85 17 ad  ce c0 b1 a5  9f c8 07 0b

But what URL could this be, if it is one? Most of these bytes are not in the normal text range, so it would have to be encrypted. Even when there was no network connection, the url0 data was added, so I knew it must be hard coded into the bot. From the tests I had been doing, I also knew that the bot contained a hard coded URL for its Command and Control server. So it seemed possible that the C&C URL was encrypted here, but of course I would have to prove that.

The first 16 bytes of the url0 values, from six bot tests, with their test identifiers (T3, M2 etc.), are listed below. The list is sorted by the opening bytes. They fall into two groups where the first seven bytes are identical. The T2 data is slightly different from the ones below it, but the one different byte (f1) could be the result of an encryption error.

T3   1e 9b 6d d8  89 e6 c4 50  7f fd 13 6b  fa e2 f4 17

M2   1e 9b 6d d8  89 e6 c4 5f  60 ff 12 7b  bd ea f3 4c

T2   f1 9b 20 62  fc 48 d0 3e  27 fc 1d f7  94 5a ff 3f

T1   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

M1   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

M5   f8 9b 20 62  fc 48 d0 2b  2a fd 17 e2  87 46 ea 7e

Looking at this, it seems fairly likely that each group was encrypted with the same key. And if these are URLs, the seven common bytes at the beginning of each line could be “http://”, if we are on the right track.

The obvious move at this point is to test this theory. We can start with the first row of hex data from the T3 and M2 tests, recover the key for T3 using the hard coded URL for that variant, then find out if the key is correct by decrypting M2 with it. The worksheet below shows the hard coded URL and the url0 registry data for T3 in the first two lines. At the bottom is the URL in text format and in the plain line are the equivalent hex bytes.

T3 http://gnfdt.cn/loader/bb.php

00000000   1e 9b 6d d8  89 e6 c4 50  7f fd 13 6b  fa e2 f4 17 (encrypted in reg)

key

plain      68 74 74 70  3a 2f 2f 67  6e 66 64 74  2e 63 6e 2f (url in hex format)

text       h  t  t  p   :  /  /  g   n  f  d  t   .  c  n  /  (known URL)

We will assume that the key was XORed with the plaintext to produce this encryption. That is the most likely case, but if we are wrong it will be necessary to try some other methods. From this basis we will now XOR the encrypted and plain bytes to recover the key.

T3 http://gnfdt.cn/loader/bb.php

00000000   1e 9b 6d d8  89 e6 c4 50  7f fd 13 6b  fa e2 f4 17 (encrypted in reg)

key        76 ef 19 a8  b3 c9 eb 37  11 9b 77 1f  d4 81 9a 38 (recovered key)

plain      68 74 74 70  3a 2f 2f 67  6e 66 64 74  2e 63 6e 2f (url in hex format)

text       h  t  t  p   :  /  /  g   n  f  d  t   .  c  n  /  (known URL)

Now we have some key bytes, but there is no proof that they are real. To prove that, we can use the key bytes to decrypt M2. The result is below. Part of the URL that is hard coded into the M2 bot has been revealed.

M2 http://hqdedikit.com/mld/bb.php

00000000   1e 9b 6d d8  89 e6 c4 5f  60 ff 12 7b  bd ea f3 4c (encrypted in reg)

key        76 ef 19 a8  b3 c9 eb 37  11 9b 77 1f  d4 81 9a 38 (recovered key)

plain      68 74 74 70  3a 2f 2f 68  71 64 65 64  69 6b 69 74 (decrypted hex)

text       h  t  t  p   :  /  /  h   q  d  e  d   i  k  i  t  (decrypted text)

So our case is proved, the hard coded URL is the one hidden in the registry key. We can easily extend this through the rest of the encrypted data to show the whole URL, and remove any lingering doubt.

But what would we do if each bot variant had its own key? The method above would not work, but there are other ways to approach this problem. One way is to check whether this is a repeating key encryption system. They are very common, and if it is we can make comparisons within one URL, instead of using two as we did above.

Let’s try this method with T3. The simple way is to use the whole URL to find as many key bytes as possible, then look for repetitions.

T3 http://gnfdt.cn/loader/bb.php

00000000   1e 9b 6d d8  89 e6 c4 50  7f fd 13 6b  fa e2 f4 17

key        76 ef 19 a8 b3 c9 eb 37  11 9b 77 1f  d4 81 9a 38

plain      68 74 74 70  3a 2f 2f 67  6e 66 64 74  2e 63 6e 2f

text       h  t  t  p   :  /  /  g   n  f  d  t   .  c  n  /

00000010   1a 80 78 cc  d6 bb c4 55  73 b5 07 77  a4 81 3a 71

key        76 ef 19 a8 b3 c9 eb 37  11 9b 77 1f  d4

plain      6c 6f 61 64  65 72 2f 62  62 2e 70 68  70

text       l  o  a  d   e  r  /  b   b  .  p  h   p

Here we can see that the key starts to repeat at the start of the second row. So the key length is 16 bytes, and again we have proved that the key holds the hard coded URL. Decrypting the next byte at the end provides a little bonus, 0×81 XOR 0×81 = 0×00, the null terminator for the string. Decryption from this point onward exposes bytes that appear to be random.

But now consider another scenario, what would we do if we had no idea what the encrypted URLs were? If we have bots with different URLs using the same key, the problem is not beyond solution. To demonstrate I will use the data from T1 and M1, from the other key group. It turns out, in the end, that only the first two lines of hex are needed for this, so the example below will not show the third line.

First we need to locate the key repetition. We can try “http://” at the start to find the first seven key bytes. With these key bytes we can  decrypt at different locations until some URL-like text appears. The bot code probably processed this as DWORDs, so we will take a shortcut by checking at four byte intervals, and use only four key bytes for each decryption. If this fails we will have to try decrypting at different intervals, possibly even at every byte. The “?” marks below indicate decrypted bytes outside the normal text range, which we would not expect in a URL.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff 90 ef 54 12  90 ef 54 12

plain      68 74 74 70  3a 2f 2f     ac 13 43 e3  01 be be 2d

text       h  t  t  p   :  /  /      ?  ?  C  ?   ?  ?  ?  -

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12 90 ef 54 12 90 ef 54 12 90 ef 54 12

plain      63 6e 2f 6d  3a ec 84 2f  b7 51 5c ea  15 d8 10 95

text       c  n  /  m :  ?  ?  /   ?  Q  \  ?   ?  ?  ?  ?

The true decryption appears to be “cn/m”, at the start of the second row. None of the others is even close. So it looks like we have found the key repetition and the key length. With this information we can set up our work sheet, with the known key bytes and decryptions they give us filled in. It can be seen below, where the decrypted parts confirm our work so far.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff

plain      68 74 74 70  3a 2f 2f

text       h  t  t  p   :  /  /

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff

plain      63 6e 2f 6d  6c 64 2f

text       c  n  /  m   l  d  /

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff

plain      68 74 74 70  3a 2f 2f

text       h  t  t  p   :  /  /

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff

plain      74 2f 6c 6f  61 64 65

text       t  /  l  o   a  d  e

Now we need to extend the URL text parts to uncover more key bytes. In other words we need to make some good guesses, but because the structure of URLs is well known to us, this should not be too difficult.

Notice that the second text line under T1 starts with “cn/mld/”. This looks like a “.cn” top level domain, so let’s fill in the “.” and apply the key byte we get.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff                           11

plain      68 74 74 70  3a 2f 2f                           2e

text       h  t  t  p   :  /  /                            .

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff 11

plain      63 6e 2f 6d  6c 64 2f                           96

text       c  n  /  m   l  d  /                            ?

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff                           11

plain      68 74 74 70  3a 2f 2f                           65

text       h  t  t  p   :  /  /                            e

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff 11

plain      74 2f 6c 6f  61 64 65                           00

text       t  /  l  o   a  d  e                           

Now we have some more decrypted bytes. There is a null at the end of M1, this must be the URL string terminator, and a non-text byte (0×96), but let’s ignore that one for now. It may be junk from beyond the end of the URL string, and we will know soon enough if this was a bad guess. At the end of the first M1 line the text character is an “e”, so that we now have “et/loade”. This looks like it must be “.net/loader”, so next we will fill this in and decrypt some more.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff 5f 34 98 11

plain      68 74 74 70  3a 2f 2f 6d                  65 72 2e

text       h  t  t  p   :  /  /  m e  r .

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff 5f 34 98 11

plain      63 6e 2f 6d  6c 64 2f 62                  00 dc 96

text       c  n  /  m   l  d  /  b ? ?

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff 5f                  34 98 11

plain      68 74 74 70  3a 2f 2f 75                  2e 6e 65

text       h  t  t  p   :  /  /  u .  n e

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff 5f 34 98 11

plain      74 2f 6c 6f  61 64 65 72                  68 70 00

text       t  /  l  o   a  d  e  r h  p

There is nothing very obvious here, but at the end of the second row of M1 we have “hp”. This looks like it could be “.php”, so let’s try that next.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff 5f 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 6d           61  64 65 72 2e

text       h  t  t  p   :  /  /  m            a   d e  r  .

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff 5f 90  f5 34 98 11

plain      63 6e 2f 6d  6c 64 2f 62           68  70 00 dc 96

text       c  n  /  m   l  d  /  b            h   p ?  ?

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff 5f 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 75           69  74 2e 6e 65

text       h  t  t  p   :  /  /  u            i   t .  n  e

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff 5f           90  f5 34 98 11

plain      74 2f 6c 6f  61 64 65 72           2e  70 68 70 00

text       t  /  l  o   a  d  e  r            .   p h  p

This looks good, and now we have some good hints. In T1, in the first line, it looks like we have “//m?loader.” and in the second line another “.php” is developing. We can put these in.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff 5f     90 78 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 6d     6c 6f 61  64 65 72 2e

text       h  t  t  p   :  /  /  m      l  o a   d  e  r  .

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff 5f 90 78 90  f5 34 98 11

plain      63 6e 2f 6d  6c 64 2f 62     2e 70 68  70 00 dc 96

text       c  n  /  m   l  d  /  b      .  p h   p  ?  ?

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff 5f 90 78 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 75     6c 69 69  74 2e 6e 65

text       h  t  t  p   :  /  /  u      l  i i   t  .  n  e

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff 5f 90 78 90  f5 34 98 11

plain      74 2f 6c 6f  61 64 65 72     62 62 2e  70 68 70 00

text       t  /  l  o   a  d  e  r      b  b .   p  h  p

Now, in the second line of M1, we have “bb.php”, and it looks like this also appears in “mld/b?.php” at second line of T1. With this we can fill in the last missing byte.

T1 00000000   f8 9b 20 62  fc 48 d0 32  3c fc 17 f1  91 51 ea 3f

key        90 ef 54 12  c6 67 ff 5f 45 90 78 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 6d  79 6c 6f 61  64 65 72 2e

text       h  t  t  p   :  /  /  m   y l  o  a   d  e  r  .

00000010   f3 81 7b 7f  aa 03 d0 3d  27 be 08 f8  85 34 44 87

key        90 ef 54 12  c6 67 ff 5f  45 90 78 90  f5 34 98 11

plain      63 6e 2f 6d  6c 64 2f 62  62 2e 70 68  70 00 dc 96

text       c  n  /  m   l  d  /  b   b .  p  h   p  ?  ?

M1 00000000   f8 9b 20 62  fc 48 d0 2a  2e fc 11 f9  81 1a f6 74

key        90 ef 54 12  c6 67 ff 5f 45 90 78 90  f5 34 98 11

plain      68 74 74 70  3a 2f 2f 75  6b 6c 69 69  74 2e 6e 65

text       h  t  t  p   :  /  /  u   k l  i  i   t  .  n  e

00000010   e4 c0 38 7d  a7 03 9a 2d  6a f2 1a be  85 5c e8 11

key        90 ef 54 12  c6 67 ff 5f 45 90 78 90  f5 34 98 11

plain      74 2f 6c 6f  61 64 65 72  2f 62 62 2e  70 68 70 00

text       t  /  l  o   a  d  e  r   / b  b  .   p  h  p

So even if the URLs are unknown, we can still decrypt them if bots with different URLs use the same key. In fact all of the pairs from this group {T1-M1, M1-M5, and T1-M5} can be solved without any really difficult guessing, and using all three makes it much easier. Even when it is not clear what text to fill in next, we can always try different guesses until we find the right one.

Of course the weaknesses in this encryption could have been avoided, or at least reduced. For example, not re-using keys would have helped. What we may be seeing here is evidence that, like many computer users, bot herders don’t take security as seriously as they should.

It had been a while since we’d last seen a malware transferring credits to pre-paid phone cards. Our last encounter dated back to SymbOS/Flocker!tr.python early January 2009. It is happening again, with Java/GameSat.A!tr, a Java ME midlet which is currently in the wild.

Indosat, an Indonesian telecom operator, offers IM3 (Indosat Multimedia 3) customers the ability to transfer (small) funds between two accounts. This is known as ‘pulse transfer’ or ‘M3-Transfer’ and it works by … SMS, without PIN nor registration ! The money is transferred from one IM3 account to another IM3 account (a transfer fee is charged to the sender).

This sounds quite handy, but… absolutely anything but secure, so it comes as no surprise cyber-delinquents make use of it.

In Flocker, from 5000 to 10000 Indonesian rupees (0.45 – 0.90 USD) were transferred to IM3 accounts controlled by the malware author.

Now, Java/GameSat.A!tr typically gets onto your mobile phone as a ‘modification to Opera Mini’. Of course, it does not modify Opera Mini at all. Instead, it uses IM3 fund transfer to access non-free on-line divination, chat or dating services. The end-user gets charged up to 20000 Rp (1.8 USD) – not mentioning the transfer fee – each time he/she opens the application or tries to access the non-free services.

I could make up my own divination service on that matter, and tell end-users they are probably about to lose roughly two dollars, get plenty of SMS spam and absolutely no advice or dates whatsoever.

– The Crypto Girl

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 0x003e, 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 = 0x9d
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.