The DGA of Qakbot.T

Qakbot, Akbot or Qbot is an older banking trojan from 2009 that underwent multiple modifications — Symantec calls the current version Generation 10, Microsoft arrived at letter “U” . Since at least September 2013, Qakbot relies on a domain generation algorithm (DGA) for C&C communication. On January 11, the blog malware-traffic-analysis.net showed such a DGA empowered Qakbot sample that was spread by the Rig Exploit Kit. Others have reversed the algorithm already, but I could not find any public documentation or implementation of the algorithm online, and therefore publish my notes here. I only reversed one sample and did not spend much time finding other versions of the DGA, so please interpret my results with caution.

The DGA in Qakbot is interesting for multiple reasons:

• Qakbot uses the Mersenne Twister (MT) as pseudorandom number generator. This not surprising, as the bot is written in Microsoft Visual C++ 5.0 where the MT is the default pseudo random number generator. Still, to my knowledge, it is the only DGA that uses a MT; Usually, DGAs are based on linear congruential generators (LCG) or hash functions like MD5.
• Qakbot tries to detect packet capture tools. If it finds one, it does not abort like many other malware would, but instead generates decoy domains to fool researchers. On the one hand, this is innocent-looking to a researcher compared to staying silent. On the other hand, the operators of Qbot could register decoy domains to track labs that leak DNS queries.
• Qakbot uses low level Windows sockets for it’s network traffic. For example, instead of using gethostbyname or DNSQuery to resolve domains, it will craft the DNS packet manually and send it with ws2_32.send. This bypasses hooks on the common DNS APIs.

Reverse Engineering

I reversed this sample from December 23, 2015:

MD5

1e135d7e024f2fb57182ae3313acae6d

SHA-256

be9625921253dca2929c849d3ea04fa9d406113bda9459af2c79487e7afdac88

upload date

2015-12-23 20:51:54

malwr link

link

The sample unpacks to this executable. The executable decrypts and loads this Qakbot dll. Microsoft detects all three stages as Qakbot.T, which is the second latest version of Qakbot from around July 2014.

Seeding

The seed to initialize the Mersenne Twister is calculated in four steps:

1. The current date is determined by making an HTTP request to one of three popular websites (offset 10009417 in the next graphic).
2. The date string is reformatted into a different string, which also includes a hard-coded seed value (0 or 1).
3. The CRC32 checksum of the resulting string is calculated (the two last steps are done in date_to_crc, called at 1000942A).
4. Qakbot tries to detect packet capture software. If it does, it increments the CRC sum by one.

The CRC sum then initializes the Mersenne Twister (call at 10009444):

Step 1: Current Date

The date is determined by making an HTTP GET request to one of the following websites:

• google.com
• microsoft.com
• cnn.com

Qakbot starts with google.com and only tries the other two options if Google is down. Qbot uses low level sockets for networking, which means it manually has to forge the requests. For example, this is the data it sends to google.com:

The request data is built with sprintf, and then sent using sockets:

The response is read until the HTTP header “Date: “ is found. Qbot cuts the first 6 letters, which correspond to “Date: “, and returns the resulting date string. For example, “Thu, 21 Jan 2016 23:31:32 GMT”:

Step 2: Formatting the Date and Hard-Coded Magic Value

The date string is split at the space character into an array of string pointers, for example: [“Thu,”, “21”, “Jan”, “2016”, “23:31:32”, “GMT”]. Only the day (“21”), month (“Jan”) and year (“2016”) are used. These values are first transformed as follows:

• The day is converted to an integer, which is then mapped to 0, if the day was 1-10; mapped to 1 if the day was 11-20; and 2 otherwise. In the example above, the value would become 2.
• The month is converted to lowercase, i.e., “Jan” becomes “jan”.
• The year is taken as is.

The resulting three values, plus a fourth hard-coded integer value, are then formatted according to:

%u.%s.%s.%08x

There are only two known possible magic values: 0 and 1. For example, for the magic value 1 the seed string on January 1, 2016 is:

1.jan.2016.00000001

Step 3: CRC-32

The string is turned into a 32bit value by calculating the CRC checksum, so “1.jan.2016.00000001” becomes 0xC758FFB8.

Step 4: Packet Capture Detection

Qakbot has a hardcoded list of executable names that are indicative of lab environments:

The tools are:

• tcpdump.exe
• windump.exe
• ethereal.exe
• wireshark.exe
• ettercap.exe
• rtsniff.exe
• packetcapture.exe
• capturenet.exe
• wireshark.exe

If Qbot detects any of those executables running, or if it finds the WinPCap Library wpcap.dll installed, it will increase the CRC sum by one. The CRC is used to initialize the Mersenne Twister, and the small increment is enough to lead to completely different random numbers.

The way the day string is transformed leads to two periods of 10 days at the start of the month, and a period of 8 to 11 days at the end of the month. During those periods the domains won’t change.

Maximum Number of Domains

Qbot generates the domains in batches. The second arguments determines how many domains to generate at once:

After the batch of domains is used up without success, Qbot loops back to generate additional domains, up to a total of 5000 domains:

Batches of Domain

The routine to generate the algorithmically generated domains first decrypts and splits the list of top level domains:

com, net, org, info, biz, org

For my samples the domains are .com, .net, .org, .info, .biz and .org (a second time):

Qakbot then generate five domains by calling the dga routine (shown later).

The five domains are then shuffled:

or in pseudo code:

n = domains.length
for i = 1 to n
    swap domains[i] with domains[Random(1,n)]

This randomizes the sequence, although not uniformly (see exercise 5.3-3 on page 129 of Introduction to Algorithms, 3rd Edition).

The DGA

The dga routine takes five arguments:

1. OUT: pointer to the domain
2. IN: (unused) an integer (256)
3. IN: the Mersenne twister.
4. IN: the array of top level domains
5. IN: the length of the top level array

The next image shows the disassembly:

The routine calls generate_random_string, which takes the minimum and maximum length as input, to determine the second level domain. The dga routine then appends a random top level domain. The routine generate_random_string disassembles to:

The routine first picks a length by using the Mersenne-Twister. Then it calls the Mersenne-Twister for the determine length to pick letters between a and y. The letter z is not included due to the same modular arithmetic bug that many other DGAs share (for example: Necurs, Ramnit, Ranbyus, Tinba, Geodo/Emotet, Cryptolocker, or Corebot).

Further details of the DGA can be seen from the reimplementation of the DGA shown next.

Reimplementation

The following Python code generates the domains for any given date and seed value:

import binascii
from datetime import datetime
from ctypes import c_uint
import argparse

def date_to_seed(date, seed):
    dx = (date.day-1) // 10 
    data = "{}.{}.{}.{:08x}".format(
            dx if dx <= 2 else 2,
            date.strftime("%b").lower(), 
            date.year, 
            seed)
    crc = c_uint(binascii.crc32(data.encode('ascii')))
    return crc

def _int32(x):
    return int(0xFFFFFFFF & x)

class MT19937:

    def __init__(self, seed):
        # Initialize the index to 0
        self.index = 624
        self.mt = [0] * 624
        self.mt[0] = seed  # Initialize the initial state to the seed
        for i in range(1, 624):
            self.mt[i] = _int32(
                1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)

    def extract_number(self):
        if self.index >= 624:
            self.twist()

        y = self.mt[self.index]
        y = y ^ y >> 11
        y = y ^ y << 7 & 2636928640
        y = y ^ y << 15 & 4022730752
        y = y ^ y >> 18

        self.index = self.index + 1
        return _int32(y)

    def twist(self):
        for i in range(0, 624):
            y = _int32((self.mt[i] & 0x80000000) +
                    (self.mt[(i + 1) % 624] & 0x7fffffff))
            self.mt[i] = self.mt[(i + 397) % 624] ^ y >> 1

            if y % 2 != 0:
                self.mt[i] = self.mt[i] ^ 0x9908b0df
        self.index = 0

    def rand_int(self, lower, upper):
        r = self.extract_number()
        r &= 0xFFFFFFF
        t = lower + float(r) / (2**28)*(upper - lower + 1) 
        t = int(t)
        return t
        

def dga(date, tlds, nr_domains=5, sandbox=False, seed=0):
    seed = date_to_seed(date, seed).value + sandbox
    mt = MT19937(seed)

    for i in range(nr_domains):
        tld_nr = mt.rand_int(0, len(tlds) - 1)
        length = mt.rand_int(8, 25)
        domain = ""
        for l in range(length):
            domain += chr(mt.rand_int(0, 25) + ord('a'))
        domain += "." + tlds[tld_nr]
        print(domain)

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("-d", "--date", 
            help="date for which to generate domains")
    parser.add_argument("-s", "--sandbox",
            help="domains when sandbox is detected", action="store_true") 
    parser.add_argument("-n", "--nr",
            help="nr of domains", type=int, default=5000) 
    parser.add_argument("-m", "--seed",
            help="seed", type=int, choices={0,1}, default=0) 
    args = parser.parse_args()

    if args.date:
        d = datetime.strptime(args.date, "%Y-%m-%d")
    else:
        d = datetime.now()

    tlds = ["com", "net", "org", "info", "biz", "org"]
    dga(d, tlds, args.nr, args.sandbox, args.seed) 

You also find the code on GitHub.

Samples

There are two different hard-coded seeds, 0 and 1. The seed 1 is much rarer. In fact, I only found the one sample analyzed in this blog post. Seed 0, on the other hand, is very common with hundreds of sample.

Seed 1

Seed 0

Archived Comments