Metamorphic compiler

I decided to revisit the idea I described in “Recompiling Metamorphism” (Valhalla #2). Existing metamorphic viruses operate at the instruction and basic-block level, which severely limits the mutations they can perform. I believe we need to work with the program as a whole. I started with a simple language I called CBD — Crazy Bootstrapping Device — a B-like language, and given the complete absence of a specification, more of a UB-like one. It sort of worked, but problems surfaced in the most unexpected places, so the next language was a strict subset of C. The name CBD was too good to change, but the language is actually C now.

Not so perfect hash

The API hashing technique is used so frequently in malware that it has already received its own MITRE number. Meanwhile, all we need to do is find a known subset of strings within a known set. Ideally, the stored data—unlike the familiar four-byte hashes—should look “decent,” meaning they should be small numbers.

The first idea that came to mind was to take the list of all glibc exports and build a minimal perfect hash - that is, a hash function that maps n values to the numbers from 0 to n-1. One of the simplest and efficient approaches is CHD (Compress-Hash-Distribute). First, we compress the keys into buckets using one hash $h_1$, and then we choose a function $h_2$ and an offset $d$ such that $(h_2 + d) \mod n$ produces unique values, roughly like this:

Runtime hooks

I was looking for a way to improve the hook mechanism in the XZ backdoor and found a method that allows you to achieve the same thing without disassembling functions or performing other expensive operations. To intercept symbol resolution, the backdoor impersonates an audit library and patches the runtime linker. It needs the offsets of the dl_naudit and dl_audit fields in _rtld_global_ro, and l_audit_any_plt in link_map:

Searching for non-exported symbols

To install hooks, we need to know the address of the required function. If debugging information is available or the function is present in the symbol table, that’s simple — but what if it’s declared as static? If the function we need contains strings, we’ll try to search for those.

Multiplicative PRIDE

Last time, I explored how PRIDE works. It turned out that the initial value and the generator in the group $Z_n$ under addition are simply split into two variables. Can we do something similar with multiplication? Let’s try the following example:

pride-mul.c

        for (a = 1; a < n; a++)
        for (b = 1; b < n; b++) {
                /* GCD(b, n)       A062955 phi(n^2) - phi(n)
                   GCD(a * b, n)   A127473 phi(n)^2 */
                if (gcd(b, n) != 1)
                        continue;
                bzero(o, sizeof(o));
                for (y = 0, i = 0; i < n; i++) {
                        /* x = (a + b * i) % n; */
                        x = (y + a) % n;
                        y = (y + b) % n;
                }
        }

Although it looks very similar to the previous one, this is not group addition, but an affine transformation in the ring $Z_n$, of the form x = a + b * i, where GCD(b, n) == 1.

If you calculate the number of possible permutations for different n, you get sequence A062955 in OEIS:

for a in `seq 1 16`; do ./a.out $a|sort|uniq|wc -l; done|xargs
0 1 4 6 16 10 36 28 48 36 100 44 144 78 112 120

That is: $\phi(n^2) − \phi(n) = (n − 1) \times \phi(n)$, where $\phi$ is Euler's totient function.

XZ backdoor: strings, tries and automata

One of the interesting features in the XZ backdoor is string searching using a trie, and for the same reason, it runs catastrophically slowly, which led to its discovery. But we were taught that tries are supposed to enable fast search. How do bitmap tries work, and how can you make search fast?

XZ backdoor: hiding the key in opcodes

The XZ backdoor uses many interesting techniques, some of which are known, and some not. When I was reading Kaspersky's analysis, I was intrigued by the steganographic function that reconstructs the author's public key — required for signature verification — from the compiled code. The set of instructions in which the key is hidden — ADD, OR, ADC, SBB, AND, SUB, XOR, CMP and MOV — looked familiar to me. The Mistfall viruses (and as a tribute to Mistfall, Lacrimae) use invariants of these opcodes for mutation.

Let's try to store something in the opcodes.