Detect specific algorithms running in a virtual machine via behavior analysis

Question

Let us suppose that I have a program that perform some well known cryptographic routines like AES, RSA or whatever. I would like to detect when such algorithms run, on which key material and possibly on which input and output data streams.

The idea is to run the whole program inside a virtual machine and then instrument the virtual machine itself to study the behavior of the program. For example, I might implement heuristics to check whether AES S-box is computed (when you see certain bytes and some clock cycles later the corresponding bytes in S-box show up in some register, then you might have a clue that S-box is being run). Tracing down how those bytes were moved across memory before might lead me to where the encryption key is stored.

The point of doing all of this in a virtual machine is that I can make up the environment so that the program is unable to detect that I am trying to spy on him. This way I would like to avoid all the mess with protectors and whatever and just see how it behaves.

Are there already attempts at reverse engineering programs in a similar way? By "similar way" I mean running the program in a virtual machine and looking how it moves data around the memory and on the registers, in order to find patterns that may help me to track down the information I am seeking.

In case it helps, the architecture I would like to use is x86 and the practical program is the one that I described above: interception of known cryptography procedure.

Answer 1

As Guntram mentioned, the PANDA project is built to make this kind of thing possible. Essentially, it adds instrumentation points to QEMU so that you can build plugins that perform analysis on a whole system as it executes.

One challenge is that the kinds of analyses you want to do are extremely computationally intensive, to the point where it's not really feasible to perform them while the system is actually running. To solve this in PANDA, we have record and replay. Essentially, this lets you make a recording of a whole-system execution and then replay it later with instrumentation enabled. Recording itself incurs only a small overhead, and arbitrarily expensive analyses can then be performed on the replay without altering the execution. This basic idea is explained in more detail in a paper by Chow et al., Decoupling dynamic program analysis from execution in virtual environments.

Currently we have two papers that are relevant to the kind of RE you're looking at:

• Tappan Zee (North) Bridge: This is probably closest to the kind of thing you're talking about. Essentially, it involves tracking every memory access in the system and then splitting them up according to address space, program counter, and calling context. The resulting streams of data can then be mined for interesting artifacts (encryption keys, URLs, etc.), which tells you where various algorithms and functionality are located in the system.
• Repeatable Reverse Engineering for the Greater Good with PANDA: This is a more general look at using PANDA for reverse engineering, with three case studies: creating a keygen for Starcraft, diagnosing a use-after-free bug in Internet Explorer, and extracting the censorship blacklist used by the LINE IM client on Android.

A drawback of PANDA is that it does not, strictly speaking, use virtualization. Instead, it uses QEMU in TCG (i.e., emulation) mode. This makes it more detectable, since there are a number of bugs in QEMU's CPU emulation that are not present when using hardware virtualization. However, unless the program you're analyzing explicitly tries to detect QEMU, this is unlikely to be a problem.

Answer 2

I recommend you taking a look to the following presentation from Recon 2012:

Cryptographic Function Identification in Obfuscated Binary Programs

If I'm not wrong, this is exactly the same you want to do.

Answer 3

A nice idea!

I don't know of an existing solution directly matching your approach. But you might use "Virtual Machine Introspection" as a key term to find out about similar approaches. The 2003 paper "A Virtual Machine Introspection Based Architecture for Intrusion Detection" by Garfinkel and Rosenblum describes such a strategy. It is used here to perform intrusion detection - i.e. they already monitored intra-VM code behavior in 2003.

In the last 11 years, the tools got smarter. One approach which seems promising to me: Once you can access the main memory of a running VM from the outside, you can easily parse it with Volatility - i.e. reconstruct user-mode processes, their Virtual Memory etc. However, this is mainly sufficient for static analyses only. So you could grab existing software from main memory without it having a chance to detect your acquisition tool (*). The extracted code could then be analyzed outside the VM like usual in IDA etc.

A more tricky part would be how to dynamically record and analyze execution flows without introducing additional helper Code inside the VM.

(*) One downside of your approach is that the code in question might already behave in a hostile way since it can detect itself running in A VM. That's usually a quite simple thing to do. So the subject might not be able to see that it is being monitored from outside the VM, but even the fact that it is run inside a VM is a quite suspect thing...