Story

Around the end of June, I found a new Kelihos binary that was being pushed to all the proxy peers from Kelihos’ job servers. At that time, I assumed the binary was just a typical bug fix build. But on July 14th, my Kelihos tracker stopped getting new peers. I then realized the update in late June was a new build which changed the communication protocol and encryption scheme. So, I took some days to reverse this new Kelihos build.

First Look

After successfully unpacking the build, I found it was compiled with the Crypto++ library which provides lots of C++ classes of cryptographic schemes. The new Kelihos build utilized public-key cryptography. Let’s take a look at the Peer Public Key Exchange first.

Peer Public Key Exchange

First, it generates a key pair using the class provided by Crypto++ library. Then, it generates a 0x10 bytes random number, using its private key to sign this data. Finally, it sends the public key and signed data to another proxy peer.

Now, let’s take a look the data structure:
Above is an example of such data.

The first QWORD is encrypted time info and tags.

• 03 10 48 40 – Data Block Length Info.
• 0x03 – Three data blocks
• 0x10 – Length of the first data block, 16 bytes of random data.
• 0x48 – Length of the second data block, local peer public key.
• 0x40 – Length of the third data block, data of the signed first data block (using RSASSA_PKCS1v15_SHA_Signer)
  

It then receives the following data after sending the data to another peer:

The first QWORD is encrypted time info and tags.

• 02 40 A1 – Data Block Length Info.
• 0x02 – Two data blocks
• 0x40 – Length of the first data block
• 0xA1 – Length of the second data block
  The first data block turns out to be encrypted data using the public key it just sent.

We can use the private key to decrypt it via using openssl:

The above decryption result (0x10 bytes) turns out to be the Blowfish key used to decrypt the 2nd data block.

After blowfish decryption, it shows the following:

Similar data structure as the send data, just without the encrypted time info and tags.

• 03 10 48 40 – Data block Length Info.
• 0x03 – Three data blocks
• 0x10 – Length of the first data block, 16 bytes of random data.
• 0x48 – Length of the second data block, remote peer’s public key.
• 0x40 – Length of the third data block, data of the signed first data block (Using RSASSA_PKCS1v15_SHA_Signer)
  Next, let’s verify the signature received using its public key.
  

Now, the public key exchange has finished. But the question here is: Why did it sign that 0x10 bytes? The answer is actually in the peer list exchange stage. So, let’s see how they exchange the peer list.

Peer List Exchange

Local Peer to Remote Peer

I’ll explain its routine here.

1. Serializes all the peer information into a certain storage structure.
2. Generates a random DWORD based on local time info. It is used to generate the header of the send data.
3. It uses 8 simple encryption algorithm to encrypt the serialized peer information. It then uses the first data block(0x10 bytes) mentioned in public key exchange to determine the encryption order.
4. It then uses Blowfish to encrypt the serialized peer information with random 0x10 bytes as the key.
5. The remote peer’s public key is used to encrypt the 0x10 bytes Blowfish key.
6. Then it generates 0x100 bytes, and inserts the first data block(0x10 bytes) mentioned in the public key exchange. Therefore, it hides the decryption algorithm determinators into those random bytes. Now, we knew the answer I raised before, during the public key exchange; it’s not only exchanging the public key, but it also makes sure the peers use the same encryption/decryption algorithm determinators. In my opinion, it’s kind of waste of space to put this data into the peer list exchange data since they should already know those determinators after the public key exchange stage.
7. Finally, it encrypts the above data using 2 of its 8 encryption algorithms (fixed order and specific algorithm).

Now, it has 3 data blocks in order:

1. Encrypted data contains random bytes and decryption algorithm determinators.
2. Encrypted Blowfish key.
3. Encrypted peer list information.

How does it organize those 3 data blocks?

1. It encrypts these 3 data blocks using 1 of the 8 encryption algorithms (specific algorithm).
2. Forms the data header (0x18 in length) using the DWORD generated base on local time info(I’ll use DWORD(x) to represent each DWORD in the following example):

• DWORD1 = generated using local time info.
• DWORD2 = DWORD1 + Length of Data Block 1
• DWORD3 = DWORD2 + Length of Data Block 2
• DWORD4 = DWORD3 + Length of Data Block 3
• DWORD5 = DWORD2 + 0xC5 + 0x3E8
• DWORD6 = DWORD6 + DWORD4 + 0x5F

1. Encrypts the DWORD2-6 using 1 of the 8 encryption algorithms (specific algorithm).
2. Puts DWORD1, encrypted DWORD2-6, and the encrypted 3 data blocks together and sends that to the remote peer.

Remote Peer to Local Peer

It receives encrypted peer list data sent to it by another peer. We can reverse the routine above to get the serialized peer list info:

The storage magic number and version info is highlighted in above pic.

Translated into English is:

So, they exchange 250 peer information each time. As I showed above there is still data pending which was not processed by my parser:

Above is the data can’t be processed by the parser. In the old build of Kelihos, the keyword 0x64 under the keyword 0x76 stores the job server IP address. What about this time?

After similar decryption, it shows:
The storage magic number and version info is highlighted in above pic.

Translated into English is: Yes! We’ve found Kelihos’ job server! If you want to take down Kelihos botnet, please make sure those servers are down.

Oh, wait. There is still data pending which is: It’s an update link. 🙂

Conclusions:

This new Kelihos build uses public key cryptography. It does protect its communication data since we can’t decrypt the data without the private key which is generated in each peer list exchange process. However, we still have the ways to track it after revealing its communication protocol and encryption schemes.

-Kyle Yang