Why not a changeling?

[zuul () LLS SE (Daniel Petzen)]

    An idea for a morphing virus.

DISCLAIMER
  I'm not good at this. I haven't written any scrambling algorithms, self
modifying code, self extracting executables or any real virus. Ever. I
haven't subcribed to vuln-dev more than a few weeks, but I haven't found
any indications that this idea (the combination) have been discussed
erlier. I'll therefore put forward this hoping it isn't a waste of your
bandwith, even if it is a bit verbose.

BACKGROUND
  When the Melissa virus struck I heard the most astounding claim: the
virus scanners failed to detect the virus as it was compressed with an, at
that point, unknown algorithm. The virusprogram therefore didn't
decompress the payload and didn't match any pattern in the code that
decoded the payload. This really amused me and my collegue at work as we
thought it was a really good joke. We debated how this could best be
exploited during a coffe break and forgot all about it.
  Lately, I've come to believe that it wasn't a joke and just to be sure I
decided to write down what we discussed and post it here. It can't be
worse than that it's bloody obvious and already have been tried.

BASICS
  The virus would be divided into two functional units: the scrambler and
the payload. The payload could be anything ranging from binaries to entire
archives. It doesn't matter. For a start we can consider the scrambler to
have two functions: (de)scrambling the payload and execute/interprete the
descrambled payload.

PATTERN MATCHING: ASSUMED LOGIC
  A wild assumption of mine regarding pattern matching would be that it
has two extremes that depends on the smallest chunks of data to compare.
As these chunks are made smaller, the match gets less and less exact, but
the chance of matching malicious patterns increases. The opposite goes for
increasing the size of the chunks. I would vager that the appliance of
logical rules combined with data (like regexp) follows the same rules,
even if de-nesting and logical chains were used.

PATTERN MATCHING: HOW TO SCRAMBLE CODE
  Our thought was that all programs are constructed of functional blocks
that are stored as chunks of sequential data. How does one detect that
it's a certain program by looking at these patterns? Some people claim
there are opcodes that only exists in malicious progams. I'd say that is
false. The esiest way would probably be to identify a code sequence that
is unique for that program and do a pattern match on it.

  The code could be chopped up in so small chunks that they become too
general for a patternmatch. Think of it: if you extract some source code
from a program it becomes very general. The smaller the part, the more
general it becomes. If you then do the same with highly optimized output
from a C compiler, the result would probably be even more general.

PATTERN MATCHING (I): THE PAYLOAD
  This is probably a piece of cake. Given enough enthropy _very_ simple
algorithms should be able to generate non-deterministic data that would
elude all types of pattern matching.

PATTERN MATCHING (II): THE (DE)SCRAMBLER
  The (de)scrambler code should be chopped up as theorized earlier. The
ways to do this are many. It could for example be done by simply jumping
to the first chunk of code. That chunk ends by adjusting the PC with a
pre-calculated offset to next chunk and so on. The chunks could be
separated with random data chunks. The jumps could also be made with
jumptables. Both jump methods could be combined. The code chunks could
fetch, decode and execute scrambled code on the fly. The implementations
are endless.

BOTTOM LINE
  _IF_ it's possible to chop up code in such extent that it becomes to
general for pattern matching, this technique could be used to create a
mutating virus.

  zuul