Botnets surrounding us: an initial focus on Kad

This idea came up in my mind something like one year ago: implement a new P2P protocol that could serve a potential botnet by myself. After a while I realized that this is definitely not a simple task, not only because developing a new protocol from scratch is hard, but even because the testing would be really painful, then the bootstrap approach, then other issues…

Then a very good friend of mine (good old @emd3l) adviced me to use an already existing infrastructure, something like Skype (approach already used in some botnets and papers); then the final idea came by re-reading what the TDL-4 botnet is made of: the good old protocol Kad, eMule incarnation of the Kademlia P2P network, a pretty famous “distributed hash table for decentralized P2P computer network”, as Wikipedia describes it. This would solve the most of the problems told before: the only thing I needed to do is to write a simplified (under some aspects) version of a Kad client (just like eMule is) and then exploit the network to send “malicious” messages to the other botnet nodes connected.

While investigating on how the Kad network works, I realized that, apart from an overview of the concepts behind and from old versions analysis, there is not a real documentation about which are the messages, how they are used, which is the expected behaviour, etc… So I decided to write here what I find, step after step, in order to (hopefully) be useful to the others that want to use this protocol for whatsoever reason.

Client identification

Every client in the Kad network is identified by a 128-bit ID, called clientID (or contactID or KadID). It is also used to compute the distance between different clients, even if the so computed distance is different from the geographical one: nodes close in the Kad network might be very far geographically. This value is randomly chosen at the first startup, for each client (and then used for the next sessions). The distance is computed by simply XORing the two client IDs.

nodes.dat

The first thing I faced with when trying to write my “botnet” is the Kad bootstrap procedure: of course this is one of the important steps to perform because, without it, we’re out. This phase begins by reading a particular file called nodes.dat, in which the information about the other contacts is stored: it can be downloaded from the internet (if it’s the first time we bootstrap) or a local version can be used, where the information from the latest session is stored.

An important thing to understand is how these files are structured. Here I present their layout, which actually changes a little bit according to the version of the file itself.

  • unsigned int 32-bit: it says how many contacts are stored in the file. Actually in the new versions of nodes.dat this value is always set to 0, because the layout changed (in this way the older clients don’t read the content of the file).
    • (if the number of contacts is 0)unsigned int 32-bit: indicates the version of the file. If this value is set to 3, then this means that this nodes.dat file is a bootstrap-only file, and needs to be handled in a different way (see below).
      • (if the version is 1)unsigned int 32-bit: it says the version of the bootstrap file. The only accepted value, for now, is 1. If so, it proceeds reading the nodes.dat differently, else it keeps on reading it normally
    • (if the number of contacts is 0)unsigned int 32-bit: here it stored the number of contacts (the one valid for the new version)

OK, so this is the header of a standard nodes.dat file (the bootstrap version of it is a little bit different). Just after these bytes, there are listed the information about the contacts. Every contacts takes 25 bytes (this value can be used to check that the file is well formed).

  • unsigned int 128-bit: this is the contact ID for this node.
  • unsigned int 32-bit: the IP address of the node. The way it’s stored requires endianness inversion, in order to correctly parse it.
  • unsigned int 16-bit: the UDP port used by the node.
  • unsigned int 16-bit: the TCP port used by the node.
  • unsigned int 8-bit: the version of the client used. This is a very important value, as it different versions support different features. The values available for now are (I’ll update here the features as soon as I find them out):
    • 0x01 – eMule 0.46c (Kad 1.0 support)
    • 0x02 – eMule 0.47a (Kad 2.0 support)
    • 0x03 – eMule 0.47b
    • 0x05 – eMule 0.48a
    • 0x06 – eMule 0.49B1 (early obfuscation protocol support)
    • 0x07 – eMule 0.49a (full obfuscation protocol support)
    • 0x08 – eMule 0.49b
    • 0x09 – eMule 0.50a
  • (if the version of the file is at least 2)unsigned int 32-bit: the Kad UDP key used to obfuscate the packets (actually this key was present even before the obfuscation support, so probably it’s used for other stuff too).
  • (it the version of the file is at least 2)unsigned int 32-bit: the client to which the UDP key is referred to. Still need to found out what it really is.
  • (if the version of the file is at least 2)unsigned int 8-bit: if the node is a verified node (it has completed the handshaking procedure). Only verified contacts can be used to perform searches or when other nodes request for some contacts.

Each of these contacts is added to the Kad routing table.

If the nodes.dat file is a bootstrap file, then its layout pretty changes: the only information included is composed by the contact ID, the IP address, the UDP/TCP ports and the contact version. The contacts here included are added in a special list and just used to bootstrap: from this file only the 50 closest nodes are chosen, as if only the 50 nodes would be delivered in the file, they would be take care of too many requests from too many clients from the Kad network. Anyway, the only things missing from the previous format are the information about the contact Kad UDP key and the boolean value if the contact is verified or not.

Network protocol

UDP protocol is used by Kad to communicate. Each packet has a fixed structure that allows the clients to easily identify it as Kad packet. The first byte is the magic value:

  • 0xE4: Kad standard packet
  • 0xE5: Kad compressed packet

The second byte is an opcode and identifies the operation code for the packet. It can a request or a response and tells to the client in which way the rest of the packet needs to be parsed and processed. The rest of the packet is actually the payload and contains information relative to the operation to perform. Different type of packets will be analyzed later, as they are needed to build the botnet.

Along with the UDP port used for the message exchanging, another TCP port is used as service port: it is used for the files exchanging (upload and download).

Since eMule 0.49B1 it is possible to obfuscate these packets by using the RC4 encryption system. Two different data can be used as a base for the encryption key:

  • the destination clientID
  • the destination Kad UDP key (if the destination clientID is not available yet)

One might ask “when the destination clientID could not be available?”. Well, in case of bootstrap process, if we contact a new node for the first time, we know the destination clientID, for sure, but when it’s its turn to reply, he doesn’t know (yet) all our details. The only thing he will know it’s our Kad UDP key (well, a modified version of it), as it’s included in the encrypted packet.

First of all two random bytes are generated: these will be part of the RC4 key.

  • If the clientID is going to be used, a buffer of 18 characters is created: the first 16 bytes will be filled with the clientID and the other two will be the two random bytes generated
  • If the Kad UDP key is to be used, a buffer of 6 characters will be created. The first four bytes will be filled with the following 32-bit number:
    • A 64-bit number is composed by the local 32-bit Kad UDP key and the destination IP address appended. Then the MD5 hash of this number is computed and the four 32-bit quadruplets of the 128-bit hash are XOR-ed together, obtaining a single 32-bit value. In the end a MOD 0xFFFFFFFE operation is performed and a 1 is added to the final result.

    Then this number is copied in the first 4 bytes of the buffer. The other two bytes will be filled with the two random bytes.

Then the MD5 value of the buffer is computed and the final value will be used as the RC4 key.

The first byte of the packet will be a modified random byte: a random value will be generated, but it will have the last bit set to 0. If the clientID has been used as a base for the key, then both last two bits will be 0, otherwise, the penultimate will be 1. A check if this byte is one of the magic numbers already used in eMule MUST be performed.

The second and the third byte will contain the random genereated two bytes used to randomize the RC4 key. The next 4 bytes will contain (in encryped form) the magic value 0x395F2EC1, used by the receiver to check that a packet has been correctly decripted. Then, even if padding is disabled for Kad, a padding value, telling us how many padding bytes are out there, is encrypted in the following byte.

Following this header, there are stored the receiver key and the sender key (this last one is the one used to encrypt the packet) in encryted form, and then there is the encrypted packet. In the end the packet will be:

  • 1 byte: marker bit
  • 2 bytes: random bytes used to generate the key
  • 4 bytes: magic value
  • 1 byte: number of bytes used for padding (always 0, even if the padding might be used up to 16 bytes)
  • 4 bytes: receiver key
  • 4 bytes: sender key
  • Encrypted data

The decryption is performed more or less in the same way, by extracting all the information from the packet and decrypting it. If the magic value is correctly decrypted, then the all the other operations are performed.

Routing table

One of the most articulate and interesting parts of the application, maybe even more than the command processing, is the handling of the routing table. In this table all the contacts are organised in a binary tree, in which the various nodes are called “zones“; each zone can have two child zones and so on, or, if the zone is just a leaf, has a K-bucket (called “bin“) in which the contacts are organized. The value K is set to 10 in the eMule implementation.

The binary tree that comes out from the routing table is not a perfect binary tree, as the leaves are not all at the same depth. When inserting a new contact, its distance from the local Kad client is computed and, level by level, if the n-th bit of the distance is 0, the right child is chosen, otherwise the left one is taken. If the zone is a leaf, the contact is inserted into the bin. When a bin is full, a check if the zone can be split in two is performed:

  • a routing zone can’t be split if it has reached the 128th level
  • a routing zone can be split if its level is equal or lower than the 5
  • if the level of the routing zone is greater than 5, then it can be split only if the index of the zone if lower than 5

With those rules, the maximum number of contacts allowed in the routing table is 6360.

The contacts are classified in 5 different types:

  • Type 0: contact active for more than 2 hours
  • Type 1: contact active since 1-2 hours
  • Type 2: contact active for less than 1 hour
  • Type 3: contact just created
  • Type 4: contact prompted for deletion

Of course, the more the type is lower the more the contact is reliable. When a new contact is to be inserted in the routing table, the following steps are performed:

  • Try to insert the contact in the root of the routing table
  • If it is a leaf
    • If the contact is already in the K-bucket
      • Yes, update it
    • Otherwise
      • If there’s still space in the K-bucket
        • Add the contact to the K-bucket
      • Otherwise
        • If the K-bucket can split, then split it. If the level-th bit of the distance is a 0, then try with the right child; otherwise try with the left one
  • Otherwise
    • If the level-th bit of the distance is a 0, then try with the right child; otherwise try with the left one
    • Restart the process

Every zone is frequently checked (no fixed value for intervals actually) by the OnSmallTimer function for old contacts that are prompted for deletion: if they are found, they are removed. In addition, a KADEMLIA2_HELLO_REQ message (will be analyzed later) is sent to the oldest contact of the k-Bucket, sending him the details of the local node. If the destination node version is at least 6 (eMule 0.49B1), the message sent will be obfuscated. The remote client has 2 minutes to reply: if it doesn’t, it will be declared as dead and removed.

Every 10 seconds another check is performed on just one routing zone by the OnBigTimer: if the zone is a leaf and can be split or at least the 80% of the K-bucket is empty, then a random lookup for a new contect is performed. Every zone is checked once an hour every time by this function. This function generates a new and random clientID that could belong to the current K-bucket and searches for it, in order to get new clients (the search for something in the Kad network will be explained later)

It took some time for me to figure this out and I think that this is enough for the first post on this new subject. In the next one I will explain the bootstrap process, with message details and so on…

Feel free to comment this post and spread the word.

Catch ya soon…

Advertisements

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