Rendus populaires par le ver Conficker, les algorithmes de génération de noms de domaine (Domain Generation Algorithm) permettent d’éviter aux cybercriminels la complexité de la mise en place d’un réseau P2P pour un canal de contrôle, sans tomber dans la trivialité des IP ou domaines codés en dur dans le binaire. La graine de ces algorithmes est généralement basée sur la date, mais on se souvient du bon vieux Torpig qui utilisait également les tendances Twitter du jour (astuce simple néanmoins très efficace pour empêcher la génération des domaines avant le jour J). Dans ce billet, nous allons montrer quelques méthodes pour automatiser la génération de noms de domaine DGA, en prenant l’exemple simple du ransomware Locky.
Méthode 1 : transcription manuelle
Voici une trace réseau d’une exécution de Locky le 01/04/2016 :
Le malware contacte :
- 4 IP codées en dur dans le binaire dépacké
- puis, si aucune connexion n’a pu être effectuée, 8 noms de domaines faisant penser à un DGA
En analysant le code réseau, on se rend compte que l’algorithme DGA de Locky est initialisé par une graine stockée sur 4 octets et faisant partie d’une petite configuration au sein du binaire dépacké :
Une rapide analyse permet de comprendre le rôle de chaque élément de la configuration :
- AffiliateId : identifiant de botnet, utilisé comme paramètre affid dans la requête GET de récupération de la clé publique
- DGASeed : graine servant à initialiser le DGA, 0x4d dans notre échantillon
- Sleep : nombre de secondes d’attente avant la création de la clé HKCU\Software\Locky (défaut : 0x1e = 30s)
- Svchost : recopie ou non sous le nom svchost.exe (défaut : non)
- Reg : persistance ou non via la clé Run de HKCU (défaut : non)
- ExcludeRussian : exclusion ou non des systèmes en langue Russe (défaut : oui)
- ServerIPs : liste des 4 IP à contacter
Le DGA est simple et peut se décomposer en 3 étapes :
1) initialisation par la graine ci-dessus ainsi que l’année, le mois et le jour courant, via quelques opérations arithmétiques simples. Un index incrémental est également passé à la fonction via le registre ECX
2) boucle de génération des caractères un par un
3) génération de l’extension par calcul d’un index dans une chaîne fixe de TLD
On voit que l’algorithme est très simple et peut s’implémenter à la main en quelques lignes de Python (v32() est simplement la troncature à 32 bits) :
def dga(seed, index, year, month, day):
c1 = 0xb11924e1
c2 = 0x27100001
c3 = 0x2709A354
eax = v32(v32((year + 0x1bf5)) * c1)
eax = v32(v32((ror(eax, 7) + seed + c2)) * c1)
eax = v32(ror(eax, 7) + (day>>1) + c2)
eax = v32(ror(eax*c1, 7) + month + c3)
eax = v32(ror(eax*c1, 7) + rol(index, 0x15))
eax = v32(eax + rol(seed, 0x11) + c2)
eax = v32(ror(eax*c1, 7) + c2)
out = ""
for i in range(5 + eax%0xb):
eax = v32(rol(eax, i) * c1)
eax = v32(ror(eax, 7) + c2)
out += chr(ord('a') + eax%0x19)
eax = v32(ror(eax*c1, 7) + c2)
eax = v32(2*(eax%0xe))
out += "." + "rupweuinytpmusfrdeitbeuknltf"[eax:eax+2]
return out
Exécutons cette fonction pour la journée du 01/04/2016 :
>>> for i in range(8):
... print dga(0x4d, i, 2016, 04, 01)
...
puyyjnyqg.de
rvayxaf.be
mfedlavimoyjwhx.it
oyleagxyifobk.pw
xehxcvwmwwm.de
sgdgacta.nl
uhlbso.eu
pqpmoscxhbrabk.yt
Les 8 domaines générés pour ce jour sont bien conformes à la capture Wireshark. Mais qu’en est-il des autres jours ? On pourrait évidemment modifier la date de Windows et lancer Wireshark pour chaque jour et faire la comparaison avec notre script… Légèrement fastidieux. On préfère générer les domaines pour l’ensemble des mois d’avril et mai : l’idée est de les comparer avec une génération automatisée afin de valider notre implémentation.
$ cat dga.py
[...]
seed = 0x4d
begin = datetime.datetime(2016, 4, 1)
end = datetime.datetime(2016, 5, 31)
domains_per_day = 8
date = begin
while date <= end:
# Seed/date header
print "0x%x %s" % (seed, date.strftime("%Y-%m-%d"))
for i in range(domains_per_day):
# Domain
print dga(seed, i, date.year, date.month, date.day)
date += datetime.timedelta(days=1)
print ""
$ ./dga.py > dga_0x4d_method1_manual.txt
$ md5sum dga_0x4d_method1_manual.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method1_manual.txt
Méthode 2 : méthode traditionnelle avec GDB/Python
Le DGA de Locky est très simple et a pu être implémenté rapidement mais s’il avait été plus complexe, il n’aurait pas été envisageable de le faire entièrement manuellement. Une méthode permettant de contourner ce problème consiste à instrumenter une machine virtuelle avec GDB et Python, comme déjà présenté dans un précédent billet sur Zeus P2P et Dyreza. On va dans ce cas utiliser deux breakpoints :
1. En début de fonction, par exemple juste après l’appel à GetSystemTime(), afin d’initialiser les registres et la pile dans l’état voulu :
- ESI contient la graine
- EDI contient l’index
- une variable pointe vers une structure SYSTEMTIME dont les offsets 0, 2 et 6 contiennent respectivement l’année, le mois et le jour
2. On laisse le malware s’exécuter jusqu’à un second breakpoint où le domaine correspondant à ces paramètres est généré. On incrémente alors l’index et, en écrasant quelques instructions par un saut, on revient au premier breakpoint pour générer un autre domaine. Si l’index atteint 8, on le remet à zéro et on passe au jour suivant.
Le script GDB/Python suivant implémente cette méthode en générant automatiquement tous les domaines d’avril et mai 2016 :
#! /usr/bin/env python
# Locky DGA generator based on GDB
# Sylvain SARMEJEANNE, CERT-LEXSI 04/2016
import gdb
import datetime
SEED = 0x4d
DATE_BEGIN = datetime.datetime(2016, 4, 1)
DATE_END = datetime.datetime(2016, 5, 31)
DOMAINS_PER_DAY = 8
OUTPUT_FILE = "/home/sylvain/malwares/locky/dga_0x%x_method2_gdb.txt" % SEED
BP_BEGIN = 0x406d67
BP_END = 0x406e95
SYSTEMTIME = 0x0012f7d8
pchar = gdb.lookup_type("char").pointer()
class LockyDGA(gdb.Breakpoint):
def __init__(self, specs):
for spec in specs:
super(LockyDGA, self).__init__(spec, gdb.BP_BREAKPOINT)
self.seed = SEED
self.idx = 0
self.datetime = DATE_BEGIN
gdb.execute("set logging file %s" % OUTPUT_FILE)
gdb.execute("set logging overwrite on")
gdb.execute("set logging on")
gdb.execute("set height 0")
def stop(self):
eip = long(gdb.parse_and_eval("$eip").cast(gdb.lookup_type("int").pointer())) & 0xffffffff
if eip == BP_BEGIN:
# Setting up the registers
gdb.execute("set $esi=%i" % self.seed)
gdb.execute("set $edi=%i" % self.idx)
# Setting up the stack
gdb.execute("set *(short*)0x%x=%i" % (SYSTEMTIME, self.datetime.year))
gdb.execute("set *(short*)(0x%x+2)=%i" % (SYSTEMTIME, self.datetime.month))
gdb.execute("set *(short*)(0x%x+6)=%i" % (SYSTEMTIME, self.datetime.day))
if self.idx == 0:
# Ouput the seed/date header
gdb.write("0x%x %s\n" % (self.seed, self.datetime.strftime("%Y-%m-%d")), gdb.STDLOG)
return False
elif eip == BP_END:
# Output the domain pointed to by edx
gdb.write("%s\n" % gdb.Value(gdb.parse_and_eval("$edx")).cast(pchar).string(), gdb.STDLOG)
self.idx += 1
if self.idx == DOMAINS_PER_DAY:
self.idx = 0
self.datetime += datetime.timedelta(days=1)
if self.datetime > DATE_END:
gdb.execute("set logging off")
return True
gdb.write("\n", gdb.STDLOG)
# Jump back to BP_BEGIN
gdb.execute("set *0x406e95=0xfffecde9")
gdb.execute("set *(0x406e95+4)=0xff")
return False
LockyDGA(["*0x%x" % BP_BEGIN, "*0x%x" % BP_END])
Le résultat est stocké dans dga_0x4d_method2_gdb.txt. Comme il s’agit de l’exécution du malware lui-même dans une machine virtuelle complète, on considère les domaines ainsi générés comme la référence. Comparons avec les domaines issus de notre implémentation manuelle (méthode 1) :
$ md5sum dga_0x4d_method1_manual.txt dga_0x4d_method2_gdb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method1_manual.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method2_gdb.txt
Notre implémentation manuelle semble correcte.
Méthode 3 : sandbox légère
La méthode précédente fonctionne parfaitement mais pour un malware aussi simple que Locky, on aimerait quelquechose de plus léger à utiliser. Après tout, pourquoi devrions-nous instrumenter un système d’exploitation complet alors que nous voulons simplement exécuter quelques instructions assembleur basiques ? Miasm fournit une sandbox qui répond tout à fait à ce problème.
On commence par initialiser la sandbox Miasm :
parser = Sandbox_Win_x86_32.parser(description="PE sandbox")
parser.add_argument("filename", help="Locky binary")
options = parser.parse_args()
sb = Sandbox_Win_x86_32(options.filename, options, globals())
On ajoute un breakpoint à l’adresse où le nom de domaine est généré en mémoire :
def end(jitter):
sb.jitter.run = False
return True
sb.jitter.add_breakpoint(0x406e95, end)
Le premier bloc appelle memset() pour réinitialiser la zone où le domaine est généré, on va simplement émuler ce memset() en Python avec un deuxième breakpoint :
def memsetzero(jitter):
sb.jitter.vm.set_mem(domain, "\x00"*32)
sb.jitter.pc = BP_CALL+5
return True
sb.jitter.add_breakpoint(0x406de6, memsetzero)
Miasm a créé une zone mémoire pour la pile à partir de l’adresse 0x130000 :
>>> sb.jitter.vm
Addr Size Access Comment
0x130000 0x10000 RW_ Stack
On positionne par exemple EBP à 0x13f000 :
sb.jitter.cpu.EBP = 0x13f000
Le domaine sera généré à une adresse arbitraire en mémoire et on y fait pointer var_40 comme le veut le code du DGA :
domain = 0x900000
sb.jitter.vm.add_memory_page(domain, PAGE_READ | PAGE_WRITE, "\x00"*32)
sb.jitter.vm.set_mem(EBP-0x40, pack("<I", domain))
Enfin, on initialise la graine, l’index et la date (c’est IDA qui indique que la variable stockant l’adresse vers la structure SYSTEMTIME est décalée de 0x24) :
sb.jitter.cpu.ESI = SEED
sb.jitter.cpu.EDI = idx
sb.jitter.vm.set_mem(EBP-0x24, pack("<H", 2016))
sb.jitter.vm.set_mem(EBP-0x24+2, pack("<H", 04))
sb.jitter.vm.set_mem(EBP-0x24+6, pack("<H", 01))
L’exécution sera lancée depuis l’adresse située juste après l’appel à GetSystemTime() :
sb.run(0x406d67)
IDA indique que la chaîne de caractères des TLD est présente en 0x413D5C ; elle a déjà été mappée par le parser PE de Miasm car elle est située dans la section .rdata du binaire dépacké :
>>> sb.jitter.vm
Addr Size Access Comment
0x411000 0x7000 R__ 'locky_unpack.exe': '.rdata\x00\x00'
>>> sb.jitter.vm.get_mem(0x413D5C, 28)
'rupweuinytpmusfrdeitbeuknltf'
Si ce mapping n’avait pas été réalisé automatiquement, il aurait été possible de l’ajouter manuellement :
sb.jitter.set_str_ansi(0x413d5c, "rupweuinytpmusfrdeitbeuknltf")
L’émulation génère correctement le premier nom de domaine du 01/04/2016 :
$ python -i ./dga_miasm_sb.py locky_unpack.exe
>>> sb.jitter.vm.get_mem(0x900000, 12)
'puyyjnyqg.de'
Sur un schéma quasi-identique au script GDB de la méthode 2, le script suivant génère les noms de domaine pour les mois d’avril et mai 2016 via une sandbox Miasm :
#! /usr/bin/env python
# Locky DGA generator based on a thin Miasm sandbox
# Sylvain SARMEJEANNE, CERT-LEXSI 04/2016
from miasm2.analysis.sandbox import Sandbox_Win_x86_32
from miasm2.jitter.csts import PAGE_READ, PAGE_WRITE
from struct import pack
import datetime
SEED = 0x4d
DATE_BEGIN = datetime.datetime(2016, 4, 1)
DATE_END = datetime.datetime(2016, 5, 31)
DOMAINS_PER_DAY = 8
idx = 0
date = DATE_BEGIN
BP_BEGIN = 0x406d67
BP_CALL = 0x406de6
BP_END = 0x406e95
EBP = 0x13f000
SYSTEMTIME = EBP-0x24
domain = 0x900000
var_40 = EBP-0x40
var_2C = EBP-0x2C
def begin(jitter):
# Setting up the registers
sb.jitter.cpu.ESI = SEED
sb.jitter.cpu.EDI = idx
# Setting up the stack
sb.jitter.vm.set_mem(SYSTEMTIME, pack("<H", date.year))
sb.jitter.vm.set_mem(SYSTEMTIME+2, pack("<H", date.month))
sb.jitter.vm.set_mem(SYSTEMTIME+6, pack("<H", date.day))
if idx == 0:
# Output the seed/date header
print "0x%x %s" % (SEED, date.strftime("%Y-%m-%d"))
return True
def memsetzero(jitter):
sb.jitter.vm.set_mem(domain, "\x00"*32)
sb.jitter.pc = BP_CALL+5
return True
def end(jitter):
global idx, date
# Output the domain pointed to by edx
print sb.jitter.get_str_ansi(sb.jitter.cpu.EDX)
idx += 1
if idx == DOMAINS_PER_DAY:
idx = 0
date += datetime.timedelta(days=1)
if date > DATE_END:
sb.jitter.run = False
return True
print ""
# Jump back to BP_BEGIN
sb.jitter.pc = BP_BEGIN
return True
parser = Sandbox_Win_x86_32.parser(description="PE sandbox")
parser.add_argument("filename", help="Locky binary")
options = parser.parse_args()
sb = Sandbox_Win_x86_32(options.filename, options, globals())
sb.jitter.cpu.EBP = EBP
sb.jitter.vm.add_memory_page(domain, PAGE_READ | PAGE_WRITE, "\x00"*32)
sb.jitter.vm.set_mem(var_40, pack("<I", domain))
sb.jitter.vm.set_mem(var_2C, "\x11\x00\x00\x00")
sb.jitter.add_breakpoint(BP_BEGIN, begin)
sb.jitter.add_breakpoint(BP_CALL, memsetzero)
sb.jitter.add_breakpoint(BP_END, end)
sb.run(BP_BEGIN)
Les domaines ainsi générés sont conformes à notre référence :
$ ./dga_miasm_sb.py > dga_0x4d_method3_miasm_sb.txt
$ md5sum dga_0x4d_method2_gdb.txt dga_0x4d_method3_miasm_sb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method2_gdb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method3_miasm_sb.txt
Méthode 4 : exécution symbolique
4.1 Initialisation du DGA
Dans les méthodes automatisées 2 et 3, nous avons simplement exécuté le code de Locky sans en comprendre le fonctionnement. Lorsque l’objectif est de réimplémenter l’algorithme en C ou Python par exemple, ces méthodes ne sont pas applicables. Si la complexité du DGA est telle que la méthode manuelle (méthode 1) n’est pas réalisable en un temps raisonnable, il nous faut un outil pour générer automatiquement une version haut niveau de l’algorithme à partir des instructions assembleur. Miasm possède pour cela un moteur d’exécution symbolique.
On commence par désassembler le bloc initialisant le DGA de Locky, entre les adresses 0x406d67 et 0x406dfa (cf méthode 1 pour les trois étapes de l’algorithme) :
c = Container.from_stream(open("/home/sylvain/malwares/locky/locky_unpack.exe"))
machine = Machine('x86_32')
mdis = machine.dis_engine(c.bin_stream)
mn = machine.mn
bloc_begin = 0x406d67
mdis.dont_dis = [0x406dfa]
blocs = mdis.dis_multibloc(bloc_begin)
ira = machine.ira()
for bloc in blocs:
ira.add_bloc(bloc)
On lance l’exécution sur ce premier bloc :
sb = symbexec(ira, mn.regs.regs_init)
sb.emul_ir_blocs(ira, bloc_begin)
Dans le code, on observe que plusieurs opérations sont effectuées sur le registre EAX et que la valeur résultante finie par être stockée dans var_14 (EBP+0xFFFFFFEC). Observons donc les zones mémoire modifiées suite à l’exécution symbolique :
>>> sb.dump_mem()
@32[(EBP_init+0xFFFFFFEC)] (((((ESI_init <<< 0x11)+((EDI_init&0x7) <<< 0x15)+(((((((((ESI_init+((({@16[(EBP_init+0xFFFFFFDC)],0,16, 0x0,16,32}+0x1BF5)*0xB11924E1) >>> 0x7)+0x27100001)*0xB11924E1) >>> 0x7)+{@16[(EBP_init+0xFFFFFFE2)][1:16],0,15, 0x0,15,32}+0x27100001)*0xB11924E1) >>> 0x7)+{@16[(EBP_init+0xFFFFFFDE)],0,16, 0x0,16,32}+0x2709A354)*0xB11924E1) >>> 0x7)+0x27100001)*0xB11924E1) >>> 0x7)+0x27100001)
L’expression peut paraître complexe à première vue mais on y reconnait tout de même les multiplications et additions avec les constantes déjà vues à l’étape 1, les rotations à gauche (<<<) et droite (>>>) ainsi que l’utilisation de différentes variables de pile. Nous allons simplifier cette expression à l’aide de Miasm. On peut déjà remplacer les lectures des registres ESI et EDI respectivement par la graine et l’index :
sb.symbols[machine.mn.regs.ESI] = ExprId("seed")
sb.symbols[machine.mn.regs.EDI] = ExprId("index")
Nous remplaçons également les lectures de la structure SYSTEMTIME sur la pile par des identifiants plus lisibles :
VAR_SYSTEMTIME = 0xFFFFFFDC
sb.symbols[ExprMem(ExprId("EBP_init") + ExprInt(VAR_SYSTEMTIME, 32), 16)] = ExprId("year", 16)
sb.symbols[ExprMem(ExprId("EBP_init") + ExprInt(VAR_SYSTEMTIME+2, 32), 16)] = ExprId("month", 16)
sb.symbols[ExprMem(ExprId("EBP_init") + ExprInt(VAR_SYSTEMTIME+6, 32), 16)] = ExprId("day", 16)
Il s’agit des mêmes initialisations que celles réalisées avec GDB ou la sandbox légère des méthodes 2 et 3. Après une nouvelle exécution, on obtient :
>>> sb.dump_mem()
@32[(EBP_init+0xFFFFFFEC)] (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+((({year,0,16, 0x0,16,32}+0x1BF5)*0xB11924E1) >>> 0x7)+0x27100001)*0xB11924E1) >>> 0x7)+{day[1:16],0,15, 0x0,15,32}+0x27100001)*0xB11924E1) >>> 0x7)+{month,0,16, 0x0,16,32}+0x2709A354)*0xB11924E1) >>> 0x7)+0x27100001)*0xB11924E1) >>> 0x7)+0x27100001)
On peut encore simplifier en remplaçant les constantes par les identifiants c1, c2 et c3, en utilisant le moteur de simplification de Miasm :
def simplify_basic(expr):
pattern1 = ExprInt(0xb11924e1, 32)
replace1 = ExprId("c1")
pattern2 = ExprInt(0x27100001, 32)
replace2 = ExprId("c2")
pattern3 = ExprInt(0x2709A354, 32)
replace3 = ExprId("c3")
simplifications = {
pattern1:replace1,
pattern2:replace2,
pattern3:replace3,
}
return expr.replace_expr(simplifications)
Concernant les variables year et month, elles sont issues de champs de 16 bits d’une structure SYSTEMTIME et sont zéro-étendues à 32 bits par l’instruction movzx. Dans le langage intermédiaire de Miasm, cela correspond à une expression ExprCompose, notée avec des accolades. Pour plus de lisibilité, nous allons par exemple simplifier {year,0,16, 0x0,16,32} en year et idem pour month :
pattern4 = ExprCompose([(ExprId("year", 16), 0, 16), (ExprInt(0, 16), 16, 32)])
replace4 = ExprId("year", 32)
pattern5 = ExprCompose([(ExprId("month", 16), 0, 16), (ExprInt(0, 16), 16, 32)])
replace5 = ExprId("month", 32)
Concernant la variable day, Locky utilise l’instruction shr ecx, 1, ce que Miasm convertit en une composition de ecx[1:16] zéro-étendue à 32 bits. On va simplifier en day >> 1 uniquement :
pattern6 = ExprCompose([(ExprSlice(ExprId("day", 16), 1, 16), 0, 15), (ExprInt(0, 17), 15, 32)])
replace6 = ExprOp(">>", ExprId("day", 32), ExprInt(1, 32))
Avec ces 6 simplifications basiques, on obtient l’expression suivante :
>>> var_14 = simplify_basic(sb.symbols.symbols_mem[ExprId("EBP_init", 32) + ExprInt(0xFFFFFFEC, 32)][1])
>>> "var_14 = %s" % var_14
'var_14 = (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2)'
On a ainsi converti le bloc d’initialisation en une ligne tout à fait lisible.
Dans les zones mémoire modifiées, on note aussi la mise à zéro de la variable var_10 :
>>> sb.dump_mem()
@32[(EBP_init+0xFFFFFFF0)] 0x0
La sortie de la boucle du DGA se fait par comparaison de var_10 avec EBX calculé dans ce premier bloc :
>>> "nb_loops = %s" % simplify_basic(sb.symbols[machine.mn.regs.EBX])
'nb_loops = (({(((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)'
On y reconnait var_14 ; on va donc simplifier l’expression de var_14 en un identifiant var_14 pour plus de lisibilité :
>>> ebx = simplify_basic(sb.symbols[machine.mn.regs.EBX])
>>> ebx = ebx.replace_expr({var_14:ExprId("var_14")})
>>> "nb_loops = %s" % ebx
'nb_loops = (({var_14,0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)'
Cette expression représente la taille du nom de domaine généré : 5 + var_14%0xB.
Dans les registres modifiés par ce bloc initial, EDI est initialisé à 0x10 :
>>> sb.dump_id()
EDI 0x10
Le premier bloc peut donc se résumer ainsi :
var_14 = (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2)
nb_loops = (({var_14,0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)
var_10 = 0x0
edi = 0x10
4.2 Boucle du DGA
Ce bloc d’initialisation étant compris, nous pouvons passer à la boucle du DGA. Son exécution symbolique n’atteint pas la fin du bloc :
>>> sb.symbols[machine.mn.regs.EIP]
ExprCond(<cond>, ExprInt(uint32(0x406e1bL)), ExprInt(uint32(0x406e1eL)))
Le moteur d’exécution symbolique se heurte au saut conditionnel basé sur une comparaison entre var_2C et EDI et ne sait quelle branche prendre. On sait qu’EDI est initialisé à 0x10 par le bloc précédent ; nous allons forcer la variable à zéro car le saut n’a pas d’incidence sur l’algorithme lui-même :
sb.symbols[ExprId('EDI', 32)] = ExprInt(0x10, 32)
sb.symbols[ExprMem(ExprId('EBP_init', 32) + ExprInt(0xffffffd4, 32))] = ExprInt(0, 32)
On en profite également pour initialiser les variables vues au bloc précédent :
sb.symbols[ExprMem(ExprId("EBP_init", 32) + ExprInt(0xFFFFFFEC, 32))] = ExprId("var_14", 32)
sb.symbols[ExprMem(ExprId('EBP_init', 32) + ExprInt(0xfffffff0, 32))] = ExprId("var_10", 32)
Cette fois-ci, l’exécution atteint bien la fin du bloc et les zones mémoire suivantes ont été altérées :
>>> sb.dump_mem()
@32[(EBP_init+0xFFFFFFF0)] (var_10+0x1)
@32[(EBP_init+0xFFFFFFEC)] ((((var_14 <<< ({var_10[0:8],0,8, 0x0,8,32}&0x1F))*0xB11924E1) >>> 0x7)+0x27100001)
var_10, initialisée à zéro dans le bloc précédent, est incrémentée de 1 dans la boucle et sert donc de compteur. var_14 se simplifie comme vu précédemment :
>>> var_14 = simplify_basic(sb.symbols.symbols_mem[ExprId("EBP_init", 32) + ExprInt(0xffffffec, 32)][1])
>>> "var_14 = %s" % var_14
'var_14 = ((((var_14 <<< ({var_10[0:8],0,8, 0x0,8,32}&0x1F))*c1) >>> 0x7)+c2)'
Dans cette expression, var_10 est zéro-étendue sur 32 bits, on peut simplifier :
pattern7 = ExprCompose(((ExprSlice(ExprId('var_10', 32), 0, 8), 0, 8), (ExprInt(uint24(0x0L)), 8, 32)))
replace7 = ExprId('var_10', 32)
On obtient ainsi :
>>> "var_14 = %s" % var_14
'var_14 = ((((var_14 <<< (var_10&0x1F))*c1) >>> 0x7)+c2)'
Le caractère généré par le DGA est présent dans EDX en fin de boucle :
>>> edx = simplify_basic(sb.symbols[machine.mn.regs.EDX])
>>> "char = %s" % edx
'char = {(({((((var_14 <<< ({var_10[0:8],0,8, 0x0,8,32}&0x1F))*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0x19)[0:8]+0x61),0,8, ({((((var_14 <<< ({var_10[0:8],0,8, 0x0,8,32}&0x1F))*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0x19)[8:32],8,32}'
On y reconnait l’expression de var_14 vue juste avant, d’où la simplification suivante :
>>> edx = edx.replace_expr({simplify_basic(var_14):ExprId("var_14")})
>>> "char = %s" % edx
'char = {(({var_14,0,32, 0x0,32,64} umod 0x19)[0:8]+0x61),0,8, ({var_14,0,32, 0x0,32,64} umod 0x19)[8:32],8,32}'
C’est simplement 0x61 + var_14%25, avec 0x61 = ord(‘a’). Cette boucle se résume donc ainsi :
var_14 = ((((var_14 <<< (var_10&0x1F))*c1) >>> 0x7)+c2)
char = {(({var_14,0,32, 0x0,32,64} umod 0x19)[0:8]+0x61),0,8, ({var_14,0,32, 0x0,32,64} umod 0x19)[8:32],8,32}
var_10 = (var_10+0x1)
4.3 Extension
Il ne reste plus que les quelques blocs générant l’extension. A l’adresse 0x406e74, c’est le registre EAX qui sert d’indice dans la chaîne des TLD :
>>> "eax = %s" % simplify_basic(sb.symbols[machine.mn.regs.EAX])
'eax = (({(((@32[(EBP_init+0xFFFFFFEC)]*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0xE)[0:32]*0x2)'
EBP_init+0xFFFFFFEC correspondant à var_14, on peut simplifier :
sb.symbols[ExprMem(ExprId("EBP_init", 32) + ExprInt(0xFFFFFFEC, 32), 32)] = ExprId("var_14", 32)
On obtient alors :
>>> "eax = %s" % simplify_basic(sb.symbols[machine.mn.regs.EAX])
'eax = (({(((var_14*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0xE)[0:32]*0x2)'
On a désormais tous les éléments de l’algorithme sous forme d’expressions Miasm :
# Initialisation
var_14 = (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2)
nb_loops = (({var_14,0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)
var_10 = 0x0
# Boucle de nb_loops iterations
var_14 = ((((var_14 <<< (var_10&0x1F))*c1) >>> 0x7)+c2)
char = {(({var_14,0,32, 0x0,32,64} umod 0x19)[0:8]+0x61),0,8, ({var_14,0,32, 0x0,32,64} umod 0x19)[8:32],8,32}
var_10 = (var_10+0x1)
# Extension
eax = (({(((var_14*c1) >>> 0x7)+c2),0,32, 0x0,32,64} umod 0xE)[0:32]*0x2)
4.4 Génération du code C
L’objectif étant de transcrire cet algorithme, et donc ces expressions Miasm, en C et Python, on va utiliser les traducteurs de Miasm. Par exemple sur l’initialisation de var_14 :
>>> "var_14 = %s" % var_14
'var_14 = (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2)'
>>> "var_14 = %s" % Translator.to_language('C').from_expr(var_14)
'var_14 = ((((rot_right(32, (((((((rot_left(32, seed, 0x11) &0xffffffff)&0xffffffff)+((rot_left(32, (((index&0xffffffff)&(0x7&0xffffffff))&0xffffffff), 0x15) &0xffffffff)&0xffffffff)+((rot_right(32, (((((((rot_right(32, (((((((rot_right(32, ((((((seed&0xffffffff)+((rot_right(32, ((((((year&0xffffffff)+(0x1bf5&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(shift_right_logic_32(day , 0x1)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(month&0xffffffff)+(c3&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff)'
Pour le nombre d’itérations :
>>> "nb_loops = %s" % ebx
'nb_loops = (({var_14,0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)'
>>> "nb_loops = %s" % Translator.to_language('C').from_expr(ebx)
'nb_loops = (((((umod64((vm_cpu_t*)jitcpu->cpu, ((((uint64_t)(var_14 & 0xFFFFFFFF)) << 0) | (((uint64_t)(0x0 & 0xFFFFFFFF)) << 32)), 0xb)>>0) & 0xFFFFFFFF)&0xffffffff)+(0x5&0xffffffff))&0xffffffff)'
On note que la traduction en C utilise parfois des fonctions tierces comme rot_left(), rot_right(), shift_right_logic_32() ou umod64(). Ces fonctions sont implémentées dans miasm2/jitter/vm_mngr.{c,h}. En copiant le code C ainsi généré par Miasm depuis toutes nos expressions simplifiées, on obtient le code suivant :
int dga(unsigned int seed, unsigned short index, unsigned short year, unsigned short month, unsigned short day) {
unsigned char c;
unsigned int eax;
unsigned int c1 = 0xb11924e1;
unsigned int c2 = 0x27100001;
unsigned int c3 = 0x2709A354;
char *tld = "rupweuinytpmusfrdeitbeuknltf";
// Seed/date header
if(index == 0)
printf("0x%x %i-%02i-%02i\n", seed, year, month, day);
// Initialisation
unsigned int var_14 = ((((rot_right(32, (((((((rot_left(32, seed, 0x11) &0xffffffff)&0xffffffff)+((rot_left(32, (((index&0xffffffff)&(0x7&0xffffffff))&0xffffffff), 0x15) &0xffffffff)&0xffffffff)+((rot_right(32, (((((((rot_right(32, (((((((rot_right(32, ((((((seed&0xffffffff)+((rot_right(32, ((((((year&0xffffffff)+(0x1bf5&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(shift_right_logic_32(day , 0x1)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(month&0xffffffff)+(c3&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff);
unsigned int nb_loops = (((((umod64(((((uint64_t)(var_14 & 0xFFFFFFFF)) << 0) | (((uint64_t)(0x0 & 0xFFFFFFFF)) << 32)), 0xb)>>0) & 0xFFFFFFFF)&0xffffffff)+(0x5&0xffffffff))&0xffffffff);
unsigned int var_10 = 0;
// Loop
while(1) {
var_14 = ((((rot_right(32, ((((rot_left(32, var_14, (((var_10&0xffffffff)&(0x1f&0xffffffff))&0xffffffff)) &0xffffffff)&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff);
var_10 = (var_10+0x1);
c = ((((uint32_t)((((((umod64(((((uint64_t)(var_14 & 0xFFFFFFFF)) << 0) | (((uint64_t)(0x0 & 0xFFFFFFFF)) << 32)), 0x19)>>0) & 0xFF)&0xff)+(0x61&0xff))&0xff) & 0xFF)) << 0) | (((uint32_t)(((umod64(((((uint64_t)(var_14 & 0xFFFFFFFF)) << 0) | (((uint64_t)(0x0 & 0xFFFFFFFF)) << 32)), 0x19)>>8) & 0xFFFFFF) & 0xFFFFFF)) << 8));
printf("%c", c);
if(var_10 >= nb_loops)
break;
}
// Extension
eax = (((((umod64(((((uint64_t)(((((rot_right(32, (((var_14&0xffffffff)*(c1&0xffffffff))&0xffffffff), 0x7) &0xffffffff)&0xffffffff)+(c2&0xffffffff))&0xffffffff) & 0xFFFFFFFF)) << 0) | (((uint64_t)(0x0 & 0xFFFFFFFF)) << 32)), 0xe)>>0) & 0xFFFFFFFF)&0xffffffff)*(0x2&0xffffffff))&0xffffffff);
printf(".%c%c\n", tld[eax], tld[eax+1]);
return 0;
}
Il ne reste plus qu’à tester la génération des noms de domaine d’avril et mai :
int main() {
int d, i;
for(d=1;d<=30;d++) {
for(i=0;i<8;i++)
dga(0x4d, i, 2016, 04, d);
printf("\n");
}
for(d=1;d<=31;d++) {
for(i=0;i<8;i++)
dga(0x4d, i, 2016, 05, d);
printf("\n");
}
return 0;
}
$ gcc -W -Wall dga.c -o dga
$ ./dga > dga_0x4d_method4_miasm_symb_c.txt
$ md5sum dga_0x4d_method2_gdb.txt dga_0x4d_method4_miasm_symb_c.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method2_gdb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method4_miasm_symb_c.txt
Miasm a correctement généré l’algorithme et sa transcription en C est correcte.
4.5 Génération du code Python
La conversion en Python ne se passe malheureusement pas aussi bien :
>>> "var_14 = %s" % Translator.to_language('Python').from_expr(var_14)
NotImplementedError: Unknown operator: >>>
>>> "nb_loops = %s" % Translator.to_language('Python').from_expr(ebx)
NotImplementedError: Unknown operator: umod
Qu’à cela ne tienne, la représentation textuelle des expressions Miasm est déjà très proche du Python, donc il est possible de générer du code Python valide à l’aide de quelques substitutions par expressions régulières. L’expression Miasm représentant var_14 dans l’étape initiale est du code Python valide à l’exception des rotations gauche et droite :
>>> "var_14 = %s" % var_14
'var_14 = (((((seed <<< 0x11)+((index&0x7) <<< 0x15)+(((((((((seed+(((year+0x1BF5)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+(day >> 0x1)+c2)*c1) >>> 0x7)+month+c3)*c1) >>> 0x7)+c2)*c1) >>> 0x7)+c2)'
Nous allons remplacer dans cette représentation l’opération a <<< b par un identifiant rol(a,b) et a >>> b par ror(a,b) à l’aide du code suivant :
def expr2python_op(e_s, e):
jok1 = ExprId("jok1", 32)
jok2 = ExprId("jok2", 32)
# seed <<< 0x11 => rol(seed,0x11)
to_match = ExprOp("<<<", jok1, jok2)
result = MatchExpr(e, to_match, [jok1, jok2])
if result:
return ExprId("rol(%s,%s)" % (result[jok1], result[jok2]))
# bla >>> 0x7 => ror(bla, 0x7)
to_match = ExprOp(">>>", jok1, jok2)
result = MatchExpr(e, to_match, [jok1, jok2])
if result:
return ExprId("ror(%s,%s)" % (result[jok1], result[jok2]))
return e
En ajoutant cette fonction au moteur de simplification de Miasm, on obtient du code Python valide pour var_14 :
>>> expr2python = {ExprOp:[expr2python_op]}
>>> expr_simp.enable_passes(expr2python)
>>> "var_14 = %s" % expr_simp(var_14.copy())
'var_14 = (c2+ror((c1*(c2+rol((index&0x7),0x15)+rol(seed,0x11)+ror((c1*(c3+month+ror((c1*(c2+ror((c1*(c2+ror((c1*(year+0x1BF5)),0x7)+seed)),0x7)+(day >> 0x1))),0x7))),0x7))),0x7))'
De la même manière pour le calcul du modulo :
>>> "nb_loops = %s" % ebx
'nb_loops = (({var_14,0,32, 0x0,32,64} umod 0xB)[0:32]+0x5)'
def expr2python_slice(e_s, e):
jok1 = ExprId("jok1", 32)
jok2 = ExprId("jok2", 64)
to_match = ExprSlice(ExprOp('umod', ExprCompose(((jok1, 0, 32), (ExprInt(uint32(0x0L)), 32, 64))), jok2), 0, 32)
result = MatchExpr(e, to_match, [jok1, jok2])
if result:
return ExprId("(%s%%%s)" % (result[jok1], result[jok2]))
return e
>>> expr2python = {ExprOp:[expr2python_op], ExprSlice:[expr2python_slice]}
>>> expr_simp.enable_passes(expr2python)
>>> "nb_loops = %s" % expr_simp(ebx.copy())
'nb_loops = ((var_14%0xB)+0x5)'
Il s’agit de code Python valide et les autres expressions peuvent être converties de la même manière. Il ne reste qu’une étape, celle de l’ajout d’appels à v32() pour garantir les opérations arithmétique sur 32 bits :
def exprv32(e_s, e):
jok1 = ExprId("jok1", 32)
jok2 = ExprId("jok2", 32)
jok3 = ExprId("jok3", 32)
jok4 = ExprId("jok4", 32)
# Apply v32 on each +
to_match = ExprOp("+", jok1, jok2)
result = MatchExpr(e, to_match, [jok1, jok2])
if result:
return ExprId("v32(%s+%s)" % (result[jok1], result[jok2]))
# Apply v32 on each *
to_match = ExprOp("*", jok1, jok2)
result = MatchExpr(e, to_match, [jok1, jok2])
if result:
return ExprId("v32(%s*%s)" % (simplify_basic(result[jok1]), simplify_basic(result[jok2])))
return e
>>> exprv32 = {ExprOp:[exprv32]}
>>> expr_simp.enable_passes(exprv32)
Finalement, var_14 et nb_loops ont comme expressions Python :
>>> "var_14 = %s" % expr_simp(var_14.copy())
'var_14 = v32(c2+ror(v32(c1*v32(c2+rol((index&0x7),0x15)+rol(seed,0x11)+ror(v32(c1*v32(c3+month+ror(v32(c1*v32(c2+ror(v32(c1*v32(c2+ror(v32(c1*v32(year+0x1BF5)),0x7)+seed)),0x7)+(day >> 0x1))),0x7))),0x7))),0x7))'
>>> "nb_loops = %s" % expr_simp(ebx)
'nb_loops = v32((var_14%0xB)+0x5)'
Il ne nous reste plus qu’à copier/coller dans un script toutes les expressions générées automatiquement et converties en Python :
def dga(seed, index, year, month, day):
var_14 = v32(c2+ror((c1*(c2+rol((index&0x7),0x15)+rol(seed,0x11)+ror((c1*(c3+month+ror((c1*(c2+ror((c1*(c2+ror((c1*(year+0x1BF5)),0x7)+seed)),0x7)+(day >> 0x1))),0x7))),0x7))),0x7))
var_10 = 0x0
nb_loops = v32((var_14%0xB)+0x5)
out = ''
while True:
var_14 = v32(c2+ror((c1*rol(var_14,var_10)),0x7))
out += chr(v32((var_14%0x19)+0x61))
var_10 = v32(var_10+0x1)
if var_10 >= nb_loops:
break
eax = v32((v32(c2+ror(v32(c1*var_14),0x7))%0xE)*0x2)
out += '.' + "rupweuinytpmusfrdeitbeuknltf"[eax:eax+2]
return out
Testons sur les mois d’avril et mai 2016 si tout fonctionne :
seed = 0x4d
begin = datetime.datetime(2016, 4, 1)
end = datetime.datetime(2016, 5, 31)
domains_per_day = 8
date = begin
while date <= end:
# Seed/date header
print "0x%x %s" % (seed, date.strftime("%Y-%m-%d"))
for i in range(domains_per_day):
# Domain
print dga(seed, i, date.year, date.month, date.day)
date += datetime.timedelta(days=1)
print ""
$ ./dga_miasm_symb.py > dga_0x4d_method4_miasm_symb.txt
$ md5sum dga_0x4d_method2_gdb.txt dga_0x4d_method4_miasm_symb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method2_gdb.txt
116cd7fdb273cd47f60c59841b81c769 dga_0x4d_method4_miasm_symb.txt
Parfait !
Conclusion
Les DGA utilisés par les malwares sont généralement simples et facilement traduisibles directement par un humain dans le langage de son choix. Mais en cas d’algorithme coriace ou de changements fréquents, il peut être utile d’automatiser cette tâche. Via une machine virtuelle classique, GDB permet de le faire mais si on cherche une solution plus légère, le framework Miasm s’avère très pratique. Sa sandbox permet d’émuler le code provenant d’un binaire et ainsi de générer très rapidement les domaines, sans se soucier des détails du DGA.
Si au contraire on cherche à reconstituer l’algorithme pour le réimplémenter dans un autre langage, le module d’exécution symbolique de Miasm permet de générer des expressions dans un langage intermédiaire correspondant aux zones mémoire ou registres modifiés, qu’il est possible de réduire via son moteur de simplification. La transcription en C ou Python peut alors être réalisée directement via le module Translator ou via des expressions régulières : on obtient ainsi l’algorithme lui-même et pas uniquement le résultat de son exécution.
