ADVANCED POLYMORPHISM PRIMER
PART THE FIRST
By Dark Angel
Phalcon/Skism

           With the recent proliferation of virus encryption "engines," I was
      inspired to write my own.  In a few short weeks, I was able to construct one
      such routine which can hold its own.  A polymorphic encryption routine is
      nothing more than a complex code generator.  Writing such a routine, while
      not incredibly difficult, requires careful planning and perhaps more than a
      few false starts.

           The utility of true polymorphism is, by now, an accepted fact.
      Scanning for the majority of viruses is a trivial task, involving merely the
      identification of a specific pattern of bytes in executable files.  This
      approach is quick and may be used to detect nearly all known viruses.
      However, polymorphism throws a monkey wrench into the works.  polymorphic
      viruses encode each copy of the virus with a different decryption routine.
      Since (theoretically) no bytes remain constant in each generated decryption
      routine, virus detectors cannot rely on a simple pattern match to locate
      these viruses.  Instead, they are forced to use an algorithmic appproach
      susceptible to "false positives," misleading reports of the existence of the
      virus where it is not truly present.  Creating a reliable algorithm to
      detect the polymorphic routine takes far more effort than isolating a usable
      scan string.  Additionally, if a virus detector fails to find even one
      instance of the virus, then that single instance will remain undetected and
      spawn many more generations of the virus.  Survival, of course, is the
      ultimate goal of the virus.

           Before attempting to write a polymorphic routine, it is necessary to
      obtain a manual detailing the 80x86 instruction set.  Without bit-level
      manipulation of the opcodes, any polymorphic routine will be of limited
      scope.  The nice rigid structure of the 80x86 instruction set will be
      readily apparent after a simple perusal of the opcodes.  Exploitation of
      this structured instruction set allows for the compact code generation
      routines which lie at the heart of every significant polymorphic routine.

           After examining the structure of the opcodes, the basic organisation of
      the polymorphic routine should be laid out.  Here, an understanding of the
      basics behind such routines is required.  The traditional approach treats
      the decryption routine as a simple executable string, such as
      "BB1301B900022E8137123483C302E2F6."  A true (advanced) polymorphic routine,
      by contrast, views the decryption routine as a conceptual algorithm, such
      as, "Set up a 'pointer' register, that is, the register whose contents hold
      a pointer to the memory to be decrypted.  Set up a counter register.  Use
      the pointer register to decrypt one byte.  Update the pointer register.
      Decrement the count register, looping if it is not zero."  Two routines
      which fit this algorithm follow:

      Sample Encryption 1
      ------ ---------- -
           mov  bx,offset startencrypt   ; here, bx is the 'pointer' register
           mov  cx,viruslength / 2       ; and cx holds the # of iterations
      decrypt_loop:
           xor  word ptr [bx],12h        ; decrypt one word at a time
           inc  bx                       ; update the pointer register to
           inc  bx                       ; point to the next word
           loop decrypt_loop             ; and continue the decryption
      startencrypt:

      Sample Encryption 2
      ------ ---------- -
      start:
           mov  bx,viruslength           ; now bx holds the decryption length
           mov  bp,offset start          ; bp is the 'pointer' register
      decrypt_loop:
           add  byte ptr [bp+0Ch],33h    ; bp+0Ch -> memory location to be
                                         ; decrypted at each iteration
           inc  bp                       ; update the pointer register
           dec  bx                       ; and the count register
           jnz  decrypt_loop             ; loop if still more to decrypt

           The number of possibilities is essentially infinite.  Naturally,
      treating the decryption as an algorithm rather than as an executable string
      greatly increases the flexibility in creating the actual routine.  Various
      portions of the decryption algorithm may be tinkered with, allowing for
      further variations.  Using the example above, one possible variation is to
      swap the order of the setup of the registers, i.e.

           mov  cx,viruslength
           mov  bx,offset startencrypt

      in lieu of

           mov  bx,offset startencrypt
           mov  cx,viruslength

           It is up to the individual to decide upon the specific variations which
      should be included in the polymorphic routine.  Depending upon the nature of
      the variations and the structure of the polymorphic routine, each increase
      in power may be accompanied with only a minimal sacrifice in code length.
      The goal is for the routine to be capable of generating the greatest number
      of variations in the least amount of code.  It is therefore desirable to
      write the polymorphic routine in a manner such that additional variations
      may be easily accommodated.  Modularity is helpful in this respect, as the
      modest overhead is rapidly offset by substantial space savings.

           The first step most polymorphic routines undergo is the determination
      of the precise variation which is to be encoded.  For example, a polymorphic
      routine may decide that the decryption routine is to use word-length xor
      encryption with bx as the pointer register, dx as a container for the
      encryption value, and cx as the counter register.  Once this information is
      known, the routine should be able to calculate the initial value of each
      variable.  For example, if cx is the counter register for a byte-length
      encryption, then it should hold the virus length.  To increase variability,
      the length of the encryption can be increased by a small, random amount.
      Note that some variables, in particular the pointer register, may not be
      known before encoding the rest of the routine.  This detail is discussed
      below.

           Of course, selecting the variables and registers will not in and of
      itself yield a valid decryption routine; the polymorphic routine must also
      encode the actual instructions to perform the job!  The cheesiest
      polymorphic routines encode a single "mov" instruction for the assignment of
      a value to a register.  The more complex routines encode a series of
      instructions which are functionally equivalent to the simple three byte
      "mov" statement yet far different in form.  For example,

           mov  ax, 808h

      could be replaced with

           mov  ax, 303h                 ; ax = 303h
           mov  bx, 101h                 ; bx = 101h
           add  ax, bx                   ; ax = 404h
           shl  ax, 1                    ; ax = 808h

           Recall that the registers should be encoded in a random order.  The
      counter variable, for example, should not always be the first to be encoded.
      Predictability, the bane of polymorphic routines, must be avoided at all
      costs.

           After the registers are encoded, the actual decryption loop should then
      be encoded.  The loop can perform a number of actions, the most significant
      of which should be to manipulate the memory location, i.e. the actual
      decryption instruction, and to update the pointer register, if necessary.
      Finally, the loop instruction itself should be encoded.  This can take many
      forms, including "loop," "loopnz," "jnz," etc.  Possible variations include
      altering the decryption value register and the counter register during each
      iteration.

           This is the general pattern of encoding.  By placing garbling, or "do-
      nothing," instructions between the essential pieces of code, further
      variability may be ensured.  These instructions may take many forms.  If the
      encoding routines are well-designed, the garbler can take advantage of the
      pre-existing code to generate null instructions, such as assignments to
      unused registers.

           Once the decryption routine has been written, it is necessary to
      encrypt the virus code.  The traditional approach gives the polymorphic
      routine the job of encrypting the code.  The polymorphic routine should
      therefore "remember" how the precise variation used by the decryptor and
      adjust the encryption routine in a complementary fashion.  An alternate
      approach is for the polymorphic routine to simultaneously encode both the
      encryption and decryption routines.  Although it adds overhead to the code,
      it is an extremely flexible approach that easily accommodates variations
      which may be later introduced into the polymorphic routine.

           Variable-length decryptors come at a significant trade-off; the exact
      start of the decryption cannot be known before encoding the decryptor.
      There are two approaches to working around this limitation.  The first is to
      encode the pointer register in a single instruction, i.e. mov bx,185h and to
      patch the initial value once it is known.  This is simplistic, though
      undesirable, as it decreases the variability of the routine.  An alternate
      approach is to encode the encryption instruction in the form xor word ptr
      [bx+185h], cx (as in Sample encryption 2, above) instead of xor word ptr
      [bx], cx (as in Sample encryption 1).  This increases the flexibility of the
      routine, as the initial value of the pointer register need not be any fixed
      value; correct decryption may be assured by adjusting the offset in the
      decryption instruction.  It is then possible to encode the pointer register
      with multiple instructions, increasing flexibility.  However, using either
      method alone increases the predictability of the generated code.  A better
      approach would be to incorporate both methods into a single polymorphic
      routine and randomly selecting one during each run.

           As an example of a polymorphic routine, I present DAME, Dark Angel's
      Multiple Encryptor and a simple virus which utilises it.  They appear in the
      following article.  DAME uses a variety of powerful techniques to achieve
      full polymorphism.  Additionally, it is easy to enhance; both the encoding
      routines and the garblers can be extended algorithmically with minimal
      effort.  In the next issue, I will thoroughly comment and explain the
      various parts of DAME.