malware►reverse►rust
Rusty matryoshka - a Rust crypter that does things its own way

Rusty matryoshka - a Rust crypter that does things its own way

TL;DR

Static analysis of a Rust crypter/loader:

  • Embedded x64 DLL split into ~200 fragments interleaved between .rdata and .data, PE headers stored apart with MZ / PE\0\0 wiped
  • base64url with a shuffled alphabet (Fisher-Yates + splitmix64) and a junk char every 57
  • splitmix-looking XOR keystream with non-standard constants I couldn’t find documented anywhere
  • Custom bit-level LZ container
  • Control-flow flattening + opaque predicates fed by TLS values, which Ghidra just gives up on

Chapter I - First look

The sample is a ~1 MB PE32+ GUI binary. Nothing fancy at first sight:

1
2
$ file loader.exe
loader.exe: PE32+ executable for MS Windows 6.00 (GUI), x86-64, 7 sections
  • Linked with LLD, .pdb path named after a fake software brand (and a version resource for the same fake company)
  • ~90 imports, nothing scary: no VirtualAlloc, no CreateRemoteThread… GetProcAddress / LoadLibraryA are there, so everything interesting is resolved at runtime
  • TLS callbacks present
  • .rdata and .data both start with huge base64url-looking strings, glued together with… English words?
1
...here said then more different these all get\x0036iGHHmSVLeIro_i_WSW5c9LQ...

That’s entropy padding: sprinkle boring words around the encoded data so the sections don’t look like pure random. Cute.

The first decent lead comes from Ghidra’s crypto constants scan: a function using 0x9E3779B97F4A7C15 (golden ratio, splitmix64) right next to a base64 alphabet. Let’s start there.

Chapter II - The string/payload decoder

Shuffled base64url

The alphabet A-Z a-z 0-9 - _ is built on the stack, then shuffled with a Fisher-Yates driven by a standard splitmix64. The seed is seed_param ^ global ^ 0x8ac8579f9dbfd643. The global itself is used to rebuild the 0xbf58476d1ce4e5b9 multiplier (global + 0x518d1e1edfd8e721), so you need the right global or nothing works.

1
2
3
4
5
6
7
8
9
alpha = bytearray(b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_')
st = (seed ^ G ^ 0x8ac8579f9dbfd643) & M
for i in range(2, 65):
    st = (st + 0x9e3779b97f4a7c15) & M
    z = ((st >> 30) ^ st) * ((G + 0x518d1e1edfd8e721) & M) & M
    z = ((z >> 27) ^ z) * 0x94d049bb133111eb & M
    z = (z >> 31) ^ z
    j = z % i
    alpha[i-1], alpha[j] = alpha[j], alpha[i-1]

The decoding loop has a funny detail: a counter goes up to 0x38 and then skips one char. So every 57th character is junk. In practice it’s almost always a -, a kind of disguised line break. My first decode attempt was misaligned by exactly that, and the stats gave it away:

1
2
>>> Counter(blob[1::57]).most_common(1)
[(45, 9803)]    # '-' 9803 times out of ~9810

The XOR keystream

The base64 output is XORed with an 8-bytes-per-block keystream. It looks like splitmix, but neither the increment nor the mixer are the usual ones:

1
2
3
4
5
6
7
8
9
10
def keystream_xor(buf, s):
    out = bytearray(buf)
    for i in range(len(out)):
        if i % 8 == 0:
            s = (s + 0xac2af1e5a7631881) & M
            z = ((s >> 22) ^ s) * 0x8f220a55af1de41b & M
            z = ((z >> 34) ^ z) * 0xa670702d6b2e329b & M
            z = (z >> 22) ^ z
        out[i] ^= (z >> (8 * (i % 8))) & 0xff
    return out

For strings, the initial state comes from a per-call-site key: (key ^ 0xda41c459bba8115e) + 0xac2af1e5a7631881. The compiler even special-cased key == 0xda41c459bba8115e, which made me waste some time thinking it was “the” key ¯\_(ツ)_/¯

Nice property for us: the mixer is invertible (xorshifts + odd multipliers). Guess 8 plaintext bytes → recover the state → recover the seed. Keep that in mind.

Bit-level LZ

No zlib, no LZ4: a home-made container, read bit by bit (LSB first inside a byte, values assembled MSB first):

1
2
3
4
5
6
7
bit 0        : 1 = compressed, 0 = raw
2 bits       : size code -> 32 / 24 / 16 / 8-bit size field
N bits       : decompressed size
tokens       : 0 + 8 bits           -> literal
               1 + 6 bits + W bits  -> match (len-3, dist-1)
               len == 0x3f          -> extended with bytes until < 0xff
W = clamp(bit_length(size - 1), 4, 15)

The size header turned out to be the best oracle of the whole analysis: wrong key → absurd size, good key → plausible size. First win:

1
2
>>> decode(blob_at(0x...), 0x12, 0x480ef8a85e72589d)
b'FindWindowA\x00'

Noice. The same routine (base64 → XOR → LZ) decodes every API/DLL/window class name, each with its own key, and caches the result in a Rust Once lazy cell.

Chapter III - Where is the payload?

The big strings are referenced… by nothing. Scanning the whole file for (ptr, len) pairs pointing inside them gives a table of ~200 slices jumping back and forth between .rdata and .data. Concatenate them in table order and you get one big encoded blob.

So, decode it with the routine above and done? Nope. Brute-forcing the key with known plaintext (MZ\x90\x00..., then the LLD DOS stub MZx\x00\x01..., raw and compressed modes, every plausible size) gave nothing.

Two reasons, found the hard way:

  1. There are actually two encoded strings: a small 3-fragment one and the big one. Each has its own 57-char alignment, and mixing them breaks everything.
  2. The payload is not decoded by the generic routine at all. It’s decoded inline in a huge flattened function, with its own XOR state.

Time to stop guessing and reverse properly.

Chapter IV - Flattening + TLS opaque predicates

Three functions (6 to 32 KB each) are fully flattened. Every block ends like this:

1
2
3
4
5
6
lea     rdx, [rip + X]
lea     rax, [rip + Y]
cmove   rdx, rax
movsxd  rax, dword ptr [rdx]
add     rax, r13
jmp     rax

and the conditions come from stuff like:

1
2
3
4
mov     rax, qword ptr [rsp + 0x40]   ; value loaded from TLS earlier
xor     eax, 0x61a90f55
...
cmp     rbx, rcx

Ghidra doesn’t resolve these jumps, so a big chunk of the code isn’t even inside a function.

The values are thread-local statics. Part of them comes straight from the .tls template, and part is rewritten at startup by a small routine that decodes a constant table (add / sub / xor with rolling constants). Since everything is deterministic, everything is recoverable statically.

So I wrote a small value-set analysis on top of capstone: track sets of constants in registers / stack / TLS, read globals from the image, fork on unknown conditions, resolve movsxd [table+idx] + base; jmp, and log (ptr, len, key) every time the string decoder is called. No emulation, just abstract interpretation over the disassembly.

1
2
3
4
site=0x...709 ptr=0x...4b6 len=0x12 key=0x6e6b48a30b89ca23  -> user32.dll
site=0x...66c ptr=0x...64e len=0x12 key=0x480ef8a85e72589d  -> FindWindowA
site=0x...4ae ptr=0x...4de len=0x24 key=0x6a0946bb4a25d78c  -> GetWindowThreadProcessId
site=0x...c5d ptr=0x...2b1 len=0x16 key=0x6928bb5e2118e6a3  -> Shell_TrayWnd

Two bugs on my side worth sharing, because they cost me the most time:

  • I first forgot one level of indirection on gs:[0x58] (TEB → TLS array → TLS block), so every TLS read returned 0 and every opaque predicate went the wrong way.
  • Even with the TLS template, things were off until I modelled the TLS init routine. Without it, a loop exit condition evaluated to a constant that the loop counter could never reach.

Once both were fixed, the CFG opened up and led straight to the inline decoder, with the XOR state as a plain movabs:

1
2
3
4
5
movabs  r11, 0x38c09f78dbf06d5f      ; initial state, small blob
...
movabs  rcx, 0xcda553fe090c27d7
sub     rcx, r13                     ; r13 = TLS value -> 0xac2af1e5a7631881
add     r11, rcx                     ; s += increment

Chapter V - Rebuilding the DLL

With that state, the small blob decompresses to 1024 bytes of PE headers… with MZ and PE\0\0 zeroed:

1
2
3
00000030: 0000 0000 0000 0000 0000 0000 4000 0000  ............@...
00000040: 0000 0000 6486 0800 ....                 ....d...
00000140: 0000 0000 0000 0000 2e74 6578 7400 0000  .........text...

Free gift: the section headers give the exact raw size of the sections. That’s the size field the big blob’s LZ header must contain. So, test every 64-bit immediate of .text as a direct XOR state and keep the one giving flag = 1 and that exact size:

1
0x...6ca 0x2ee4c3cacfb2abd2 flag 1 size 0x98600   <- the one

Decompress, glue headers + sections, restore the two signatures (analysis copy only):

1
2
$ file stage_rebuilt.bin
stage_rebuilt.bin: PE32+ executable for MS Windows 6.00 (DLL), x86-64, 8 sections

And of course… the extracted DLL is packed with the same crypter. Matryoshka all the way down.

Chapter VI - Detection

The XOR constants are rare enough to be a decent anchor. Tested on two builds, zero hits on ~1000 system DLLs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
rule Loader_Rust_SplitmixXor_BitLZ
{
    meta:
        author = "ghozt"
        description = "Rust crypter: shuffled base64url + splitmix-like XOR stream + bit-level LZ"
    strings:
        $xinc = { 81 18 63 A7 E5 F1 2A AC }   // 0xac2af1e5a7631881
        $xm1  = { 1B E4 1D AF 55 0A 22 8F }   // 0x8f220a55af1de41b
        $xm2  = { 9B 32 2E 6B 2D 70 70 A6 }   // 0xa670702d6b2e329b
        $xk   = { 5E 11 A8 BB 59 C4 41 DA }   // 0xda41c459bba8115e
        $b64  = "wxyz0123456789-_" ascii
    condition:
        uint16(0) == 0x5A4D and 3 of ($x*) and $b64
}

Caveat: nothing prevents the author from rolling these constants per build. The structural tricks are more robust anchors: 1-in-57 junk char, bit-level LZ, interleaved (ptr, len) fragment table, headers stored apart with wiped signatures, English filler.

Takeaways

  • None of the building blocks are new, but the combination is neat, and I couldn’t find any public write-up of this scheme or its constants
  • Brute force + known plaintext is great… until the payload doesn’t go through the function you’re attacking
  • When opaque predicates depend on TLS, model the TLS init, or your static analysis will lie to you
  • The LZ size header is a free oracle: use it