Technical details of Srizbi's domain generation algorithmThis post will dive into the algorithm by which Srizbi decides which domain name to contact on a given day
For this analysis, I [Julia] reverse engineered the following sample:
MD5:8adb642389b8bf999e2017d731edcb00 bot.sys (Linked on Mon Dec 10 03:57:34 2007 ? if the timestamps can be trusted.)
Which is not only unpacked, but the author left the debugging symbols in. The original name for this project is revealed by: c:\reactor3\client\Release\client.pdb
The bot (Srizbi) is loaded into the NT Kernel as a device driver,
and then mucks around with the pointers for several kernel functions, like
ZwEnumerateKey, ZwOpenKey, ZwQueryValueKey, ZwCreateFile, ZwLoadDriver,
etc. These are all fairly common rootkit techniques, which probably
deserve a post of their own. This post is about the pseudo-random DNS
name generation.
When Srizbi can't contact 208.72.169.22 or 208.72.169.136 or ? ? its
primary C&C servers (all hosted at McColo, but you know this story by
now), after ten attempts, it switches to a backup server ? four backup
servers in fact, with randomly generated names. It then cycles through
these destinations forever, until something tells it what it wants to
hear.
These backup DNS names were not registered, which made everyone ask:
Who would code a backup DNS name into a bot, and then fail to register
that name? I speculated that it may have been an unknown feature of the
code base that the bot author used, assuming that they didn't write that
much of the code, or even read any of it.
Upon examining the binary in IDA, the mechanism became obvious.
There is a call to KeQuerySystemTime, and then RtlTimeToTimeFields to
get the current year, month, and day. This is done in a loop four times
with a call to the function at the bottom of this post. The date is swizzled around in various ways, such as if there are more than 12 months, the quotient is converted to years, and
leap-years are calculated, and other transforms like that. The returned day count is rounded down to the nearest third day. (i.e. Julian days
which are even multiples of three.)
An array of eight bytes (only the low nibble is used) is created from
every other byte from the XOR of the current day, and the magic number
in this specific sample, 0x5BE741E3.
The third byte of the day, is XOR'd over all eight bytes in this
array, and each byte is multiplied by the current iteration of the far
outside loop ? the one driving the creation of four DNS names ? mod fifteen.
This leaves you with eight bytes, with each byte in the range 0 to 14
inclusive. Each byte is used as an index into the string:
"qwertyuiopasdfghjklzxcvbnm" ? of which only the first 15 letters can
ever be used. This is why all of the DNS names never use the letter h,
or z, or m, etc.
As the function is linear, if you have the four DNS names, or
even just the first one, and the date it was generated, you can crank through this function
backwards to get the magic number, which varies between most samples. We identified 55 unique magic numbers throughout the hundreds of samples we analyzed.
q w e r t y u i o p a s d f g h j k l z x c v b n m0 1 2 3 4 5 6 7 8 9 a b c d e - - - - - - - - - - -
So, given a name like yrytdyip.com, the array of eight bytes that
gives you that string is, y=5, r=3, y=5, t=4, d=12, y=5, i=7, p=9, or
0x5354c579 when you put it all together.
The first name the bot spits out has been multiplied by one, so it's the
exact same thing that's in memory after all of the above. The next one is
multiplied by two, and then the modulus is taken on each byte to keep
their values below fifteen. The third one is multiplied by three, mod 15.
And the fourth multiplied by four, mod 15.
So, for example:
5*2 = 10%15 ? 10
5*3 = 15%15 ? 0
5*4 = 20%15 ? 5
12*2 = 24%15 ? 9
12*3 = 36%15 ? 6
12*4 = 48%15 ? 3
So the Multiplication table looks like this:
0 1 2 3 4 5 6 7 8 9 a b c d e0 2 4 6 8 a c e 1 3 5 7 9 b d
0 3 6 9 c 0 3 6 9 c 0 3 6 9 c
0 4 8 c 1 5 9 d 2 6 a e 3 7 b
Here are some real-world examples:
yrytdyip.com 5354c579 2008-11-13 (times one)
auaopagr.com a6a89ae3 2008-11-13 (times two)
qpqduqud.com 090c606c 2008-11-13 (times three)
ydywryfu.com 5c5135d6 2008-11-13 (times four)
ererseqg.com 2323b20e 2008-11-17 (times one)
tutuitqf.com 4646740d 2008-11-17 (etc.)
upupruqd.com 6969360c 2008-11-17
ododgoqs.com 8c8ce80b 2008-11-17
These examples are from the same bot, but they are more than three days
apart, so the Julian date has rolled over:
Nov 13, 2008 ? 318 = (106*3)
Nov 16, 2008 ? 321 = (107*3)
Nov 19, 2008 ? 324 = (108*3)
XORing two of these DNS names together, reveals the byte from the current
date, which is repeatedly used: (The two days shown XOR's here, obviously.)
0x2323b20e ^ 0x5354c579 = 0x70777777 (That's [EBP+day+3])
So, on Nov 19, all of the bots in this Botnet
incremented to the next set of DNS names. They do this every three
days, and would have for the rest of forever, until someone (either related to the Botnet or not) told the bots what to do. The details for this are in a previous post.
This is the function that does most of this work. It's only somewhat
crudely commented right now, but it should be evident what is happening.
; Attributes: bp-based frame
build_dns_name proc near
var_something= dword ptr -0Ch
var_random= dword ptr -4
arg_year= dword ptr 8
arg_month= dword ptr 0Ch
arg_day= dword ptr 10h
arg_that_new_buffer= dword ptr 14h
arg_iteration= dword ptr 18h
; register ecx: (null)
push ebp
mov ebp, esp
sub esp, 0Ch
push ebx ; still 0
push esi
push edi
push [ebp+arg_day]
mov [ebp+var_random], 5BE741E3h ; Mystery number for XORs
push [ebp+arg_month]
push [ebp+arg_year]
call normalize_date ; Not entirely certain yet what this returns
push 3
xor edx, edx
pop ecx
mov ebx, eax ; Julian date or maybe (years since 1970)+(day-1)
div ecx
lea ecx, [ebp+var_something]
sub ebx, edx ; days mod 3
mov [ebp+arg_day], ebx ; every three days
xor esi, esi
first_loop:
mov al, byte ptr [ebp+esi+arg_day]
xor al, byte ptr [ebp+esi+var_random]
mov dl, al
shr dl, 4
mov [ecx], dl
inc ecx
and al, 0Fh
mov [ecx], al
inc ecx
inc esi
cmp esi, 4
jl short first_loop
mov byte ptr [ebp+arg_day+3], bl ; days mod 3
mov ebx, [ebp+arg_iteration] ; range 0:3
and byte ptr [ebp+arg_day+3], 0Fh
xor esi, esi
inc ebx ; range 1:4
second_loop:
movzx eax, byte ptr [ebp+arg_day+3]
lea ecx, [ebp+esi+var_something]
movzx edx, byte ptr [ecx] ; 8 bytes of stuff from above
xor eax, edx
imul eax, ebx ; dns name loop iteration
push 15
cdq ; extend sign of EAX info EDX
pop edi
idiv edi ; mod 15
inc esi
cmp esi, 8
mov [ecx], dl ; remainder mod 15
jl short second_loop
mov eax, [ebp+arg_that_new_buffer]
xor ecx, ecx
third_loop:
movzx edx, byte ptr [ebp+ecx+var_something]
mov dl, byte ptr ds:aQwertyuiopasdfghjklzxcvbnm[edx] ; "qwertyuiopasdfghjklzxcvbnm"
mov [eax], dl
inc eax
inc ecx
cmp ecx, 8
jl short third_loop
mov byte ptr [eax], 0
dec eax
loc_11FCB:
mov cl, [eax+1]
inc eax
test cl, cl
jnz short loc_11FCB
mov edi, eax
mov esi, offset a_com ; ".com"
movsd
movsb
pop edi
pop esi
pop ebx
leave
retn 14h
build_dns_name endp
Julia Wolf (edits by Alex Lanstein) @ FireEye Malware Intelligence Lab
Questions/Comments to research [@] fireeye [.] com
Source:
Technical details of Srizbi's domain generation algorithm
