Defeating code virtualization: a keygen for a VM-protected crackme

This is the second half of a crackme writeup. Part one deals with the packaging: a file whose every real section is empty on disk, a three layer packer that resolves its own imports by hashing names off the PEB, and a background thread that hashes .text and calls TerminateProcess about 200 ms after you touch the branch byte. It ends with a standalone build that prints “Access granted” for any name and any serial, which is the lesser solve and worth having mainly because of what it leaves behind.

What it leaves behind is where this part starts. The sections are dumped out of a live process and rebuilt into an image that loads statically at 0x140000000. validate at 0x140001260 is a single jmp into the virtualised section, and there is no readable native form of the check anywhere in the file. The watchdog’s kill switch is hooked, so the process tolerates being tampered with. And the same section dumps run inside Unicorn, which gives a copy of validate with no process wrapped around it.

None of that tells me what the serial has to be. That is this half of the job: getting inside the virtual machine, working out what it computes, and running it backwards.

Turning the VM into a value reader

To get at the real algorithm I needed to see what the virtual machine was computing, and I still was not going to attach a debugger to find out.

The setup is entirely external. Hook TerminateProcess so I can tamper freely, VirtualAllocEx a scratch buffer, drop in a stub that loads (name, len, serial_lo, serial_hi) into the argument registers, calls validate at 0x140001260, and writes eax back into the buffer, then fire the whole thing off with CreateRemoteThread. That gets me the real VM running at full speed on any input I care to give it.

Then there is the trick that carried the entire middle of this project. The VM keeps its virtual registers in a stack frame addressed by r13, and it leaves through this instruction:

0x14004765E  mov rax, [r13+0x178]      ; 49 8B 85 78 01 00 00

At that point r13 is still pointing at a fully populated frame, because the stack does not get torn down for another two instructions, and the displacement is four bytes sitting at a fixed offset inside the instruction. Patch it to any value X and validate hands back frame slot [r13+X] instead of the result.

With the remote thread caller in front of it, that let me read any value the VM computed for any name and serial without understanding a single byte of its bytecode. It reproduced the name hashes I already knew, which is what convinced me to trust it, so I scanned the whole frame in 8 byte steps and diffed it across name changes and serial changes:

The shape falls out of that. It folds the name into three values, pushes the serial through something that produces two more, and compares. Sixty four bits of serial mapping onto two 32-bit words is a bijection, which means every name has essentially one valid serial and a keygen has to invert the thing rather than go looking for a match.

I then spent a while trying to crack that transform as a black box and got nowhere. It is not affine, and the four-way XOR test rules out anything GF(2)-linear. It is not a plain multiply, it is not the name hash applied to the serial bytes in either endianness, and it does not separate into the two halves. Feeding it serial = 2^k for each k and watching which output bits moved did show a triangular influence pattern, which is what multiplication looks like, and that was as far as sampling was ever going to get me. You cannot read a multiplier off a set of samples. I had to go and read the code.

The anti-single-step trap

The plan was an in-process single-step tracer: a vectored exception handler, the trap flag set before the call into validate, and every single-step exception logging the instruction pointer and all sixteen general purpose registers on the way past.

Before any of that worked I lost an evening to my own harness. The handler kept a counter, the counter kept coming back zero, the process was dead by the time I looked, and I concluded the VEH was never being invoked. It was being invoked fine. ReadProcessMemory on a process that has already exited returns zeros rather than failing, so I had not been reading a counter at all, I had been reading the absence of one, and the two are indistinguishable from the calling side.

With that sorted, stepping was fine outside the VM and died at a very specific instruction inside it, the eighth one:

0x1400281F0  lea  rsp,[rsp-0x200]     ; VM frame
0x1400281F8  mov  [rsp+0x128],r13
0x140028200  mov  r13,rsp
0x140028203  mov  [r13+0x178],rax
0x14002820A  mov  [r13+0x78],rcx      ; name pointer
0x14002820E  mov  [r13+0x1B0],rdx     ; name length
0x140028215  pushfq                   ; step 8
0x140028216  pop  rax                 ; RFLAGS into rax
             ... store rax to [r13+0x48]

pushfq pushes RFLAGS, RFLAGS carries the trap flag, and if you are single-stepping then TF is set and sitting there in plain sight. The VM reads it, files it away in its own frame, and kills the process a while later so the death is nowhere near the detection. I found the instruction by binary searching the step count, running N steps and checking whether the process was still breathing, which also meant I could stop just short of the fatal one and still have a live process to read the bytes from. 9C is pushfq.

The fix is two lines in the handler. After each step, if the byte at Rip-1 is 0x9C, go and clear bit 8 of the value that instruction just pushed at [Rsp], so the pop rax underneath reads flags with the trap flag already gone. You are not hiding TF from the processor, which you cannot do, you are removing it from the copy the program is about to look at. With that in place the whole validate call, all 9,483 host instructions of it, traces cleanly and the process lives.

One more thing had to be right. The VM throws UD2 exceptions of its own and dispatches them through its own handlers as control flow, so my handler acts only on STATUS_SINGLE_STEP and forwards everything else with CONTINUE_SEARCH, leaving the VM’s exception machinery working normally underneath me.

Reading the algorithm out of a trace

A single trace tells you which way the code went. It takes two of them before the data shows up.

I traced validate for serial 0 and again for serial 1 and diffed the registers step by step, which needed two corrections before the diff meant anything. Traces from separate runs of the process disagree everywhere, because ASLR has moved every stack pointer, so both calls had to happen in the same thread. And the second call inherits whatever the first one left lying in registers, so I zeroed the scratch registers in between. After that the difference between the two traces is nothing but the serial’s own data flow, and it shows the first six thousand steps hashing the name with the transform sitting at steps 6055 to 6300.

It is worth spelling out what a single logical operation costs inside a machine like this, because it is the thing that makes VM protectors expensive to read. h ^= h << 13 is not an xor. It is imul rdi, 0x2000 to do the shift, followed by the identity a ^ b == (a + b) - 2 * (a & b) assembled out of add, and, shift and sub, so no literal xor ever appears in the trace at all. Every real instruction has a jump after it to the next one, so two logical operations are never adjacent. Constants show up as mov exx, 0xAABBCCXX then xor exx, 0xAABBCCYY, where the XOR of the low bytes is a dispatch displacement, meaning a lot of what looks like arithmetic is really control flow decode. On top of that there are and, or, inc and cmovo operations on live registers whose results go nowhere. The one saving grace is the movups traffic, which turns out to be the register file being copied around rather than anything computational, so a general purpose register tracer really does see everything that matters. Fifteen lines of real arithmetic, 9,500 instructions.

Watch it execute, though, and the multiplies are just there:

Working backwards through the trace, decoding each imul, rol and xor and checking every step numerically against values read out of the live VM, the transform came out as a two-word rotate-multiply-xor hash. With golden = 0x9E3779B9, everything mod 2^32:

1
2
3
val     = ROL(golden + lo, 7) * 0x85EBCA77
serialB = ROL(val XOR hi, 13) * 0xC2B2AE3D        ; frame +0x1A8
serialA = (serialB XOR val)   * 0x27D4EB2F        ; frame +0x078

The low half goes in before the first round, added to the golden seed. The high half arrives mid-hash as an XOR, which I found by tracing a pair of inputs that varied only in the high half. And serialA is built from serialB’s state as it was before that XOR, with one more multiply on top.

Every multiplier is odd, so every step is invertible mod 2^32 and the map as a whole is a bijection:

Which means you can pick any pair of target values, invert, and get the serial that produces them. It matched the live VM on 24 random serials out of 24, and I was fairly sure at that point I was nearly finished.

The decoy that fires only when you are right

I had been assuming the check was serialA == hashB and serialB == hashC, on the strength of those values sitting next to each other in registers when the transform finished. Inverting onto them got me denied. So did all nine pairings of the two serial values against the three name hashes, which was the point at which I stopped guessing and went looking for the comparison itself.

Every equality in this VM ends the same way, in a sign-fold zero test finishing with shr r32, 0x1F, so I scanned the section for that byte pattern and worked out which of the hits actually run on the passing path. Two of them do, plus one inside the name hashing loop that fires once per character.

Gate one is at 0x140039DD1, and there is no cmp in it anywhere:

140039DD1  mov  rcx, rbp      ; rcx = serialA
140039DD4  mov  rdx, rcx
140039DD7  xor  rcx, rax      ; rax = K1
140039DDA  not  rdx
140039DDD  and  rdx, rax
140039DE0  shl  rdx, 1
140039DE3  sub  rcx, rdx      ; serialA - K1, zero if equal

That is a - b written as (a ^ b) - 2 * (~a & b), with ((d | -d) >> 31) & 1 ^ 1 after it to turn zero into one. No cmp, no test, no conditional jump, and nothing a decompiler is going to label as a comparison. The value on the other side of it is not hashB either. It is something else derived from the name, 0xFF7F7605 in the case of “AAAA”, and I will call it K1 from here. That one fact explains every denial up to this point, because I had been aiming at the wrong target from the very beginning.

So I inverted the transform to land serialA == K1, ran it, read frame slot +0x78 to check my work, and got 0xAB13482B. Which is the wrong value, and the obvious reading is that my model of the transform was broken somewhere.

The evidence would not sit still though, and this is the part of the project I enjoyed most. The model had matched the live VM on 24 out of 24 random serials and diverged on precisely one input, the single case I had engineered to hit K1. When I forced six different serial pairs to produce serialA == K1, every one of them came back as 0xAB13482B. Six inputs cannot map to one output under a bijection, so whatever that value is, it is not being computed from my serial. It is being put there.

The trace shows how. Immediately after the equality test, at 0x140039EC3, there is a cmovb gated on the flag that test produced, and it overwrites the copy of serialA on its way into the frame with a fixed constant, only in the case where it matched. The gate itself is reading the raw register, so a correct serial still sails through. The only thing that gets poisoned is the copy stored in the place an analyst would naturally go and look.

I have a lot of respect for that. It is not rejecting wrong answers, which would be normal, it is corrupting the observable for right ones. Model the transform, invert onto the target, then check the frame slot to confirm, and the binary tells you that you have failed at the exact moment you succeeded. The reasonable conclusion from there is that your model is wrong, and off you go to re-derive something that was already correct.

What settled it was control flow rather than data. A serial that hits K1 runs 308 extra instructions and goes down a different handler, 0x14003A232 instead of 0x14003BB01, so the gate had clearly passed and forked the path even while the frame slot was lying about it. The value the code branches on is the one worth believing.

That other handler turns out to be a nested VM frame, a virtual machine inside the virtual machine, and it is where the second expected value gets computed and stored.

Gate two at 0x14003AD1C is the same idiom again, this time comparing serialB against that value, which I will call K2. It only runs once gate one has passed, which is why nothing I had tried previously ever got near it. The return value is the AND of the two flags and there is no third gate behind them. For “AAAA”, K1 is 0xFF7F7605 and K2 was sitting in the trace as 0xAB13E338:

1
2
3
granted ==  (serialA == K1)  AND  (serialB == K2)

Invert(0xFF7F7605, 0xAB13E338)  ->  46ED-7053-AD03-9091

validate returned 1, which was the first serial the untouched binary had ever accepted from me.

From one name to any name

A serial for one name is not a keygen. K1 and K2 get computed inline and never land anywhere readable, so I could either pull them out of the binary once per name, or work out what they actually are.

Pulling them out is easy and gets you something usable the same day. Run validate with serial 0 and read K1 out of rax at 0x140039DD7, since it is computed whatever serial you pass. Build a serial that satisfies gate one so the nested hash runs, and read K2 out of rax at 0x14003ABAA. Invert, format, done. It works against the live process and it works offline too, by loading the unpacked sections into Unicorn with code hooks at those two addresses, and a name that keygen had never seen was generated purely in emulation and then accepted by the real binary.

An emulator is not understanding, though. It runs the algorithm without ever telling you what the algorithm is, and there is no way to turn it into fifteen lines of Go. So I went after the closed form, and that is where most of the time on this project actually went.

The method was a controlled corpus, single characters first, then A, AA, AAA, AAAA, then real names, which exposes the per-character recurrence and leaves you with ground truth to test any formula against. After that I brute-forced structures rather than keys, trying multiply-add, (h ^ c) * M, (h * M) ^ c, (h + c) * M, and (ROL(h, r) ^ c) * M for every rotation. Everything failed, which was itself informative, because it meant the mixer had more than one operation in it and no amount of curve fitting was going to land on it.

So I traced a single character iteration with an instruction logger instead. Sitting in the noise was 0x811C9DC5, which is the FNV-1a 32-bit offset basis, and right next to it that same value XORed with 0x41, which is the FNV state after eating the letter A. hashB fell over in one go after that, mostly because it never leaves rbp and I could watch both its accumulator and its operations at every character boundary:

1
2
hashB: h = 0x811C9DC5
       per byte c: h = (h ^ c) * 0x01000193; h ^= h >> 15

Textbook FNV-1a with an extra xorshift per byte, and it verified against eight names first try.

hashA lives in rdi and took longer. It reuses 0x85EBCA77 from the serial transform, which is a nice bit of economy on the author’s part, and it implements h ^= h << 13 as a multiply by 0x2000 plus the same XOR identity as everywhere else. Its finalise fit nothing I tried until I noticed the output was simply a rotate right by 7 of the input. There was one false start worth mentioning: I assumed the multiplicand was seed + char, but 0x1B8735D4 is even and therefore has no modular inverse, so the odd operand had to be the prime instead. Checking parity first would have saved me a couple of hours.

1
2
hashA: h = 0x1B873593
       per byte c: h = (h + c) * 0x85EBCA77; h ^= h << 13; h = ROR(h, 7)

Two hashes in an afternoon. hashC took days, and every technique that had worked so far fell over on it. Nothing fit (h OP c) * p with any finalise, it was not a finalise of any combination of hashA and hashB, and its raw accumulator matched no single or double multiply, no 15-bit split, and nothing from the Murmur or xxHash families.

The reason is the strongest thing this protector does, and I did not see it for an embarrassingly long time. hashC’s value never stays still. It gets pushed to the stack, popped back into a different register, and byte-swapped between operations, so it shows up as 0x4BD4AA15 and as its byte swap 0x15AAD44B in alternation while hopping between r11, the stack and r9. At one boundary two registers that were both supposed to be holding it disagreed by one. Everything I had been sampling was only intermittently the real state, so the fitting was never going to converge, because the data going into it was contaminated. It is the register renaming that beats you here, not the arithmetic, which is worth saying because the arithmetic is the part that looks intimidating.

So the tooling escalated, which is roughly the shape of the whole project: value reader, then single-step tracer, then emulator, then taint tracking, then a slicer, each one built only because the previous one hit a wall. Forward taint was hopeless, since the VM performs and, or and cmovo on live registers as opaque predicates and taint spreads to everything inside a few hundred instructions. Backward slicing is what broke it open. Record a full trace of instructions and memory, then walk backwards from the value you care about, find the last instruction that wrote it, add its source registers and stack slots as new targets, and keep going. Junk never enters the slice because nothing downstream ever consumes it. That is the entire idea and it took about 200 lines.

The first backward slice of the hashC accumulator handed me sub r11, ebx, with ebx holding hashA_prev + c, which makes the accumulator h = 0x811C9DC5; per char: h -= (hashA_prev + c). It verified across the whole chain and even explained the off-by-one between registers as a timing artefact. I was pleased with myself for about an hour.

Then nothing would fit the finalise from that accumulator to hashC, and the reason is that the accumulator is a decoy. It is a complete, self-consistent, entirely verifiable hash whose value never reaches the answer. The VM computes a whole dead sub-hash for no purpose other than handing an analyst something plausible to chase, and I chased it.

Slicing the frame value itself instead, and fitting over candidate inputs, the answer landed on hashB, with a multiplier I had already watched feeding the finalise. Eleven names to confirm. The habit I took away from that one is to slice from whatever value actually reaches the decision, and never from the thing that merely looks like the state.

K1 came quickly afterwards. I knew from the data that K1 ^ hashC was always 17 bits or fewer for every name I had, so the only question was what that quantity was, and the obvious guess was right on 18 names out of 18. K2 only exists once gate one has passed, so I ran a serial engineered to satisfy it and backward-sliced the store at 0x14003ABAA. With the noise stripped out, that slice is a textbook avalanche on hashA, and you can read the shift widths straight off the and masks, 0x1FFF for 13 and 0xFFFF for 16, with the multiplier sitting in the imul.

1
2
3
hashC = (hashB ^ (hashB >> 16)) * 0x7FEB352D
K1    = hashC ^ (hashC >> 15)
K2    = fmix(hashA):  h = hashA; h ^= h >> 13; h *= 0x846CA68B; h ^= h >> 16

That held across fifteen names, which was enough for me to stop checking.

The whole algorithm, and the keygen

Everything the binary computes to validate a serial. All values uint32, all arithmetic mod 2^32.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# fold the name
hashA:  h = 0x1B873593
        for each byte c:  h = (h + c) * 0x85EBCA77;  h ^= h << 13;  h = ROR(h, 7)

hashB:  h = 0x811C9DC5
        for each byte c:  h = (h ^ c) * 0x01000193;  h ^= h >> 15

# derive the two expected words
hashC = (hashB ^ (hashB >> 16)) * 0x7FEB352D
K1    = hashC ^ (hashC >> 15)                       # expected serialA
K2    = fmix(hashA)                                 # expected serialB

# transform the serial the user typed, as hi:lo
val     = ROL(0x9E3779B9 + lo, 7) * 0x85EBCA77
serialB = ROL(val ^ hi, 13)       * 0xC2B2AE3D
serialA = (serialB ^ val)         * 0x27D4EB2F

# granted if and only if
serialA == K1  and  serialB == K2

Two hashes, two derived constants, one invertible mixing of the input, one 64-bit equality. If the program ran that in a straight line it would be a twenty minute reverse.

To make a keygen you invert the transform to hit (K1, K2), where inv32 is the modular inverse of an odd 32-bit value, four rounds of Newton’s iteration and nothing more:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func invert(k1, k2 uint32) (lo, hi uint32) {
	vb := k2 ^ (k1 * inv32(c2a))
	lo = rotr(vb*inv32(c1), 7) - golden
	hi = vb ^ rotr(k2*inv32(c2), 13)
	return
}

func inv32(a uint32) uint32 {
	x := a // a*x is congruent to 1 mod 8 for odd a; Newton doubles the correct bits
	for i := 0; i < 4; i++ {
		x = x * (2 - a*x)
	}
	return x
}

The complete keygen is a single Go file with no dependencies, no emulator, no copy of the target and no tables. Name in, serial out.

1
2
3
4
$ go run keygen.go "Tejashwi Kalp Taru"
Name  : Tejashwi Kalp Taru
K1    : 62E2868F   K2: D5C10895
Serial: D007-22A4-39FD-2187

I ran it against the emulator for twenty names and got identical serials twenty times, then took a name neither of them had seen before and typed it into the original binary with nothing patched and nothing hooked:

Access granted, from the real check, on a serial worked out from the name and nothing else. That is what I had been after since the first denied prompt.

Downloads

• keygen-go.zip, the Go keygen, one file plus a README with known-good name and serial pairs.
• keygenme-challenge.zip, the original packed challenge. Windows x64, runs fine in a VM.
• keygenme-unpacked.zip, the unpacked image rebuilt as a PE, loading statically at 0x140000000. Every address in both parts lines up in it. It will not run, because a rebuilt image has no usable IAT. Part one explains where it came from.

I have deliberately not published the tracer, the slicer, the value reader or the emulator. The point here is the method, and you will learn far more from writing a 200 line backward slicer yourself than from running mine. All of them are described above in enough detail to rebuild.

What I am building next

My own protector, in Go, for Go programs. Almost everything in this space was designed for C and C++ binaries, and quite a lot of it does not survive contact with a Go binary. Stolen OEP is the clearest case, since it is standard equipment in a packer and costs almost nothing to implement, and in a Go binary it is a bad idea for reasons that go all the way down to how the runtime locates its own functions.

I wrote that up separately, with the runtime source and some measurements behind it: why Go binaries need a different protector.

The threat model I am designing against is this post. What worked here was backward slicing over a full instruction and memory trace, single-step tracing with the trap flag scrubbed out of the value the program reads, a live value reader driven by remote threads, and simply harvesting constants, because every mixing constant in this binary sat in plain sight as an imul operand.

The thing that actually cost me time was none of the headline features. It was not the packer, or the watchdog, or the anti-debug, or even the virtual machine as such. It was the register renaming, pushing values through the stack and byte-swapping them so that no logical value ever sits still anywhere. That beat every black-box method I had. Meanwhile the weakest part of the design was the check itself, because two equality gates on a bijective transform means there is nothing to search for, only something to invert, and a many-to-one or non-invertible check would have been far harder to attack with everything else left exactly as it is.