DGA-based Botnet Detection

There are essentially two types of magic in the world – those that deceive an audience in to believing something impossible has occurred, and that which is best defined by Arthur C. Clarke as “any sufficiently advanced technology is indistinguishable from magic”.

The antivirus industry is rife with the former – there’s no shortage of smoke and mirror explanations when it comes to double-talking “dynamically generated signature signature-less engines” and “zero false-positive anomaly detection systems”.

I’m going to introduce you to the later kind of magic. Technological approaches so different from traditional approaches that, for many folks out there in Internet-land, it’s indistinguishable from magic. More than that though, I’m going to try to explain how such techniques are reversing the way in which threat discovery has occurred in the past. However what I’m not going to do is to even try to explain a fraction of the math and analytics that lies behind that magic – at least not in a blog!
Oh where, oh where should we start?

Let’s begin, for arguments sake, by classifying malware as a tool; a weapon to be more precise. In the physical world it would be easy to associate “malware” with the bullets from a gun, and the gun in turn likened to perhaps a drive-by download site or a phishing email. In response to that particular physical threat, there are a number of technological approaches that have been deployed in order to counter the threat – we have metal detectors and x-ray machines to alert us to the presence of guns, sniffing technologies to identify the presence of explosive materials, CCTV and behavioral analysis systems to identify the suspects who may be hiding the gun.

A fundamental premise of this layered detection approach is that we’ve encountered the threat in the past and already classified it as bad – i.e. as a “weapon”. Gun equals bad, knife equals bad, metal corkscrew equals bad, and so on. Meanwhile everything else is assumed to be good – like an ostrich egg – until it happens to be used as a weapon (such as when “Russell pleaded guilty to assault using an ostrich egg as a weapon, assault, and breaching a protection order“) and inevitably some new detection technique is proposed to detect it.

Traditionally the focus has been on “preventing” the threat. In particular, detecting the presence of a known threat and stopping it from reaching its target. In the physical world, in general, the detection technologies are pretty robust – however (and it’s a big “however”), the assumption is that the technology needed to provide this prevention capability is ubiquitous, deployed everywhere it could potentially be needed, and that it works every time. Sure, at high value targets (such as airports) you’ll find such technology employing its optimal capability, elsewhere though (such as the doorway into your home) it’ll not be encountered. There are obvious parallels with the cyber-world here – except arguably the Internet-equivalent technologies are a little more ubiquitous, but considerably less capable in preventing the malware threat.

For the mob hitman, serial killer, or other kind of mass murderer, the threat of sparsely deployed metal detectors is an easily avoided problem. Subversion or avoidance of the detection systems is pretty easy and, more importantly, an appropriate choice of location negates the problem entirely. Even then, such a detection strategy, operated in isolation, isn’t a serious inhibitor for new murders. If such a technology exists to only detect the guns and bullets, but is not capable of providing attribution (e.g. this gun was used in 16 different murders over the last 2 weeks and the owner of this gun is the murderer), then the criminal only ever loses a tool each time they get caught – since the prevention technology is divorced from association with the victims (past or prospective).

But there’s an entirely different side to dealing with that kind of threat – and that’s the forensics element. While our not-so-friendly murderer can avoid the detection technologies, they’re much less capable of avoiding the evidence of violent past actions. Starting from the first murder, it is possible to build a case that points to a specific criminal by analyzing the components of the crime scene(s).
I know, the argument is that everything should be done to prevent the crime in the first place. That’s clearly very difficult in the physical world, but you’re basically living in a fantasy land of Goblins and Unicorns if you’re expecting it to work better in the cyber-world.

Which basically brings me to the discussion (and subsequent detection) of the latest generation of sophisticated malware – malware that uses domain generation algorithms (DGA) to locate their command and control infrastructure and upload their stolen data. Malware with this capability are designed to evade all those conventional prevention technologies and, once successfully deployed within their victim populace, evade all other methods of traffic filtering and takedown processes. Even if a malware sample is accidentally captured, its DGA capabilities will go undetected.
Detecting DGA-based malware is, as I implied earlier, both “magic” and a reversal of conventional prevention approaches. In order to detect DGA-based threats early on, you start with the victims first…

DGA-based malware use an algorithm to pick out candidate domain names in order to hunt for their prospective C&C servers. The vast majority of the domain names they’re looking for simply don’t exist. In the world of DNS, attempting to resolve a domain name that doesn’t exist will result in a “no such domain” (i.e. an NX) response from an authoritative DNS server somewhere down the line. So, in essence, DGA’s are noisy if you’re watching DNS activity – and lots of NX responses are a key feature of an infected host. Unfortunately, the average Internet-connected device typically tries to look up lots of things that don’t exist, and there’s often a lot of legitimate NX traffic which can disguise the flapping of the malware.

Assuming some kind of algorithmic basis to the domain candidates being created by the malware, you could suppose that it would be possible to develop a unique signature for them. If only it was that easy – the criminals are smarter than that. And you’re also assuming that you’ve already encountered a copy of the malware before in order to create a signature for that particular DGA-based malware.

Instead there’s a much better way – you monitor all your DNS traffic and NX responses, and you identify clusters of devices (or IP addresses) that are generating roughly similar domain name requests. This first pass will provide a hint that those devices share some kind of common ailment (without ever needing to know what the malware is or have ever encountered a sample before). In a second pass you focus upon identifying just the domain names that are structurally very similar across all the afflicted assets and classify that DGA based upon a number of features. Classifying the DGA makes it easier for attribution and uniquely tracking a new threat.

At this point you’re pretty much sure that you have a new malware outbreak and you know who all the victims are, and you can easily track the growth (or demise) of the botnet within your network. Unfortunately you’re also dealing with a brand new threat and you probably don’t have a malware sample… and that’s where an additional layer of analytics comes into play and more “magic” happens as you automatically begin to identify the domain names that are tried by the DGA-based malware that actually succeed and engage with the criminals server.

Let’s work through a simple example uncovered last week by Damballa Labs. Over the weekend one of our NX monitoring tools identified a few thousand IP addresses within our customer base that were generating clusters of NX DNS traffic very similar to the following:

9ftor9srimbna-q.com, 0sso151a47nztrxld6.com, 0ubpccgkvzrnng.com, dq2yl1zxcmvko2.com, wfj-5i5p4uhq8tylhiz.com, 1sj4rh1i5l8-4tca.com, zv7dfcgtusnttpl.com, om2air5ah5lisj7.com, qmyuvaftpgve2tzwhcjr.com, fndskzqmsob5r2bzby.com, f5p2vxn7dcdkujhbguqb.com, 6q5sigkfu3fl3q.com, zpbm3emcuosopagdttxi.com , trsmw3wceik79krk5.com, qtxfmfyulnnjpxwqo.com, ikh9w-3vdmlndafja.com, udf-szhubujmuhp1jj.com, 4v8hohrphizcas.com, nhb72anz8ifdyzgckqf.com, rcu4n0lzoghuj2.com, dklfebjexiabttkwvgos.com, fjg56xwoupqpdxr.com, drxyuezdllerpd.com, t407bqgh56jbkv4ua.com, 49ubufqnjzvhct.com, n7c3qfpslcjosy-5.com, nvnzihl6krkyfo8zp.com 

While you’d be hard pressed to write a “signature” for the domain names that wouldn’t cause false positives out the wazoo, the features of the combined victim’s traffic (frequency, distribution, commonality, etc.) work fine as a way of associating them to a shared new threat.

Armed with this knowledge, it is then possible to identify similarly structured domain names that were successfully resolved by the victims that also shared timing elements or appeared to alter the flow of NX domain responses. For example, if the DGA-based malware is designed to locate a “live” C&C server, once it’s found a server it probably doesn’t need to keep on looking for more and will likely stop generating NX domain traffic for a period of time.

Based upon our observations of this particular botnet outbreak, it was possible to identify the following C&C servers being operated by the criminals:

• ###.133. ###.247 – idpd1y###-elywj.com
• ###.133. ###.247 – k7-cwubgsrqj###rb.com
• ###.133. ###.247 – omz###1k1vgrqf.com
• ###.133. ###.247 – taqwucpzj###an.com
• ###.133. ###.247 – vhrey###-ooz6ig.com
• ###.133. ###.75 – o###pp1k1vgrqf.com
• ###.133. ###.75 – rm6dol7###cxje-ajl.com
• ###.133. ###.191 – id###yzib-e###j.com
• ###.133. ###.191 – k7-c###gsrqjebzrb.com
• ###.133. ###.191 – ###gpp1k1vgrqf.com
• ###.133. ###.191 – rm6dol###wcxje-ajl.com
• ###.133. ###.191 – taqwucpzj###an.com
• ###.133. ###.191 – vhreyveh-ooz###.com

[NOTE: We've temporarily obfuscated some of this data while we continue to investigate and enumerate the global pool of victims. We'll release the technical details of this particular DGA-based botnet soon…]


So, by this point we know who the victims are, how many C&C servers the criminals are operating, what their IP addresses are and, subsequently, which hosting facilities they are operating from:

• AS13237 LAMBDANET-AS Lambdanet Communications Deutschland GmbH

What about the malware piece? While we know who the victims are, it would be nice to know more about the tool that the criminals behind this botnet prefer and ideally to get to know them more “personally” – if you know what I mean…

As it happens, there are some malware samples that have been discovered in the very recent past that also like to contact C&C’s running upon the same hosts at this facility. For example:

• d977ebff137fa97424740554595b9###

Fortunately, while the malware sample wasn’t detected by any antivirus products, it had previously been automatically executed within our dynamic analysis environment and we’d already extracted all of its observable network features, including an additional (successful) C&C engagement:

• m8###ecc9lsnks6kbcrv7.com using ###.133. ###.75, ###.133. ###.191, and ###.23. ###.139

This, in turn, helped identify the following additional hosting facility based in the Netherlands:

• AS49981 WORLDSTREAM WorldStream

There’s obviously much more to this particular threat, and if you’d like to get involved digging into it and helping with the attribution please let me know…

But, getting back on track, this approach in identifying brand new threats – while sounding like magic to many – works really well! We’ve found it to be immensely scalable and fantastically accurate.

However, there’s one fly in the ointment (as it were)… the approach identifies new threats long before the malware component is typically uncovered by the security community and is independent of the the vector used to infect the victims,the malware tool that was deployed and ultimately the actual endpoint device type.

Think of it this way. Based upon the forensics of the blood splattered bodies and evidence left in the room that the murderer left behind, we know that the victims were bludgeoned to death with an ovoid object approximately 6 inches in diameter, weighing 3 pounds and composed of a calcium shell. We also know that the murderer was 5 foot 11 inches, weighed 240 pounds and wears size 11 Reeboks.

You can keep your metal detectors for all the good that’ll do in this case…

Virtual Execution and the Emperors New Clothes

Some ideas sound so attractive in principle that it’s hard to fathom why the Internet security industry hasn’t leapt up and down all over them already. Take for instance the idea of automatically processing malware within a virtualized host, capturing the network traffic that’s generated, automatically generating an IDS signature for the malicious traffic, and then deploying the signature to a network protection platform. It sounds so enticingly simple – almost elegant. So why isn’t everyone doing this? Why aren’t we protected from malware? Because it doesn’t really work, and never has – at least not against any contemporary portfolio of targeted threats and crimeware!

The idea of automatically generating signatures for network borne threats isn’t precisely new. In fact the concept dates back to the early 1980′s and predates network-propagated malware attacks by quite a margin.

Back in 1997, network-based intrusion detection systems (IDS) really started to take off as a viable commercial security technology – with ISS rolling out their RealSecure – and the first (internal vendor) prototype systems were developed for automatic signature development. Even in those early days where malware threats were exceedingly noisy and clumsy on the network, it was difficult to develop reliable signatures that wouldn’t let loose a tide of false positive results. Any automatically generated signature needed to be reviewed by skilled engineers and “soak tested” in pliable customer networks – and subsequently tweaked or dropped, depending upon false positives observations.

Fifteen years later new vendors continue to reinvent the wheel and rediscover the pain behind the promise. Take for example Palo Alto Networks’ Wildfire and FireEye’s Virtual Execution Engine approaches (what’s with the “fire” thing?). Both capture suspicious binaries observed traversing their customer’s networks and hand them over to a software virtualization system for controlled execution and (eventual) automatic signature generation. Those signatures (basically a Snort regex-based signature) and then pushed to IDS sensors to alert upon.

What’s the matter with that? Well, for anything beyond the most ubiquitous and dumb malware out there, the approach will either result in false positive alerts or fail to alert altogether. The latter is more common than the former because the systems are tuned that way. After all, no one likes to be woken up late at night due to a false positive – so if you miss the threat entirely, who’s ever going to know?

There are way too many reasons why automated signature systems like FireEye and Wildfire continue to fail in detecting and diagnosing todays targeted threats (note that this isn’t a problem unique to just them – it applies to the other dozen or so near-identical products from other vendors).

You may remember a paper I published mid-2011 on the topic “Automated In-Network Malware Analysis: Why Virtual Machines Can Sputter and Miss“. That paper alone provides numerous examples of what the badguys are doing to bypass automated analysis systems and the perils of not operating analysis platforms that replicate real victim systems (which is an Achilles Heel of these appliance-led “protection” systems).

Out of all the possible ways the badguys can usurp these auto-generated malware detection engines, let’s look at one of the more recent ones – malware that makes use of Domain Generation Algorithms (DGA).

DGA Evasion

Last week Damballa Labs released a report and case study on the current generation of DGA-based crimeware and you’ll likely have noted that of the 12 newly uncovered DGA’s, 6 of them were associated with advanced (but mainstream) crimeware families. Now here’s the rub, if you’re reliant upon an automated system for malware analysis to generate “protection” signatures for your IDS, I hope you’re enjoying the Emperor’s new clothes because you’re naked to the C&C communications of Shiz, Bimital, BankPatch, Expiro.Z, Bonnana, and recent generations of Zeus (to name but a few).

How is that possible? Simply put, several of the features of DGA’s are designed to intentionally bypass these kinds of dynamic protection technologies. By not using static domain names for their C&C lookups, and by ensuring that their network communications look like standard HTTP/HTTPS traffic, any automatically generated “call back” signature will be based upon redundant and outdated information before it’s even deployed – and subsequently never trigger against real crimeware traffic.

As the crimeware sample executes within the virtualized analysis environment (and assuming that it’s not bothering to conduct any anti-VM evasion in the first place (which is a fallacy of course)) it will initiate its DGA and attempt to look up a number of dynamically calculated domain names. Those domain names and the C&C servers they are hunting for reflect the current date/time of the malware’s execution. At a different date or time additional malware samples will generate their own sets. The net result is that, assuming the vendor’s product can create a signature in the first place, the signature will be for only a single malware sample at a fixed (past) point in time. Adding that signature to the IDS and alerting system can only result in false positive detections – and lost incident response cycles.

With an evasion technique as successful as the modern DGA, it is not a surprise to see it being adopted by additional crimeware families.

There is a technique for identifying DGA’s and the victims of DGA-based crimeware. The dynamism of DGA operational use means that the detection technologies need to more flexible and operate independently of static signatures. As such, the current generation of DGA-based threat detection focuses upon DNS-level observations and utilizes clustering and spectral analysis approaches.

Being Stealthy with DGA Technology

Do you remember all the fuss about Conficker many moons ago and its odd method of locating C&C servers? Instead of relying upon a static list of preconfigured domain names that corresponded to the location of the badguys C&C servers, it used an algorithm to calculate candidate domain names – and then tried reaching out to a handful of the candidates in a vein attempt to locate an active C&C server.

The authors behind the Conficker variants experimented with a number of algorithms but, at the end of the day, they failed to construct a cohesive botnet. Despite that “minor flaw”, Conficker infected devices still account for a sizable fraction of known malware infections around the work – years after the threat was studied to death and detection/protection/cleanup solutions are available everywhere.

There were a few other malware families that briefly rode the coattails of Conficker – further refining the Domain Generation Algorithm (DGA) technique as a form of evasion against protection systems that relied upon blacklists, signatures and pseudo-signatures. But, after a few months, the threat had been largely forgotten.

“Forgotten” probably isn’t the right word. The Conficker Working Group is still tracking victims and hoping against hope to identify the masterminds behind the botnet should they ever attempt to set up a real C&C server and provide new instructions to the derelict zombie hoard they created. By “forgotten” (complete with quotes), what I refer to is a general complacency for the threat and the inability of today’s network protection systems and monitoring solutions to identify malware that makes use of DGAs.

The DGA threat was a technique uncovered by malware reverse engineers and rose to public attention because of the novelty of the method – rather than any advancement’s in detecting and mitigating the threat. DGAs are a pain – they’re supposed to be. They exist to defeat network detection and blocking technologies, and they did it really well. Today they’re doing it even better!

While DGA’s disappeared from a media perspective, they also disappeared from a threat protection perspective too. They disappeared largely because the badguys got better – not because they stopped using them or consigned them to history.

Damballa Labs released a report recently covering new DGA discoveries and global trends, as well as a blow-by-blow case study of one DGA-based crimeware campaign. Whilst I recommend that you read the reports yourself, there are a number of really important findings that you should pay attention to:

1. DGAs aren’t dead. Instead, they’re being added to already-stealthy crimeware at an alarming rate.
2. DGAs are being adopted as backup strategies. Even if the crimeware family is well known and it’s traditional C&C infrastructure is blocked or disabled (e.g. web filtering, firewall blacklists, etc.), the DGA fallback plan is kicking in and allowing the crimeware to receive new instructions and upload stolen data.
3. C&C servers are becoming more agile. The criminal operators behind the DGA-based crimeware are exposing their C&C servers for the minimum amount of time. Domains are registered and DNS configurations are made “just in time” (i.e. a few minutes before the algorithm is supposed to call the domain), and the C&C servers are shut down and removed immediately afterwards – something that can be done within an hour.
4. Dynamic analysis and auto-gen signature systems are failing. Automated systems that perform dynamic malware analysis on the DGA-based crimeware are producing irrelevant detection signatures. By the time the crimeware passes through the analysis and a signature is deployed for alerting/blocking, the crimeware family is already on to the next C&C server possibility.

While the addition of DGAs to already stealthy and advanced crimeware is a significant threat to corporate defenses, it should be noted that the processes now employed by their criminal operators concerning the registration of domain names, configuration of DNS, and addition/removal of C&C servers is equally advanced. Like a delicate ballet dance, professional cybercriminals are optimizing their deployments for the maximum gain and the lowest exposure.

That said, there are still ways of detecting both the employment of DGAs and their crimeware victims – and this can be done on a very large scale. Employing a number of novel techniques applied to DNS traffic, it is possible to automatically enumerate the threat. It’s not easy and bound to result in a number of patents, but it can be done – as hinted at in the Damballa Labs research report.

The obvious question: “If DGAs can now be detected, won’t the bad guys stop using them or modify them so they’re less detectable?” Well, it’s OK with me if the bad guys stop using them – but I doubt that that’s likely. The technique is stealthier than any other they have in their arsenal and will continue to work against the traditional/legacy network protection platforms for a long time to come. As for modification, there’s very little they can do beyond reducing the number of domains the algorithm tries per day (which makes it more susceptible to traditional blacklist approaches if they do), or they employ less randomness in their algorithms – which makes the approach less flexible and more cumbersome (which would slow down the detection of small botnets, and have no effect on large infection outbreaks).

In the meantime it looks like a sizable number of new DGAs have been hiding out there for the last year – undetected by the multitude of security vendors and researchers. I’m sure there are many more awaiting illumination.