MalDev - Binary Entropy Reduction

Introduction

Entropy là đại lượng dùng để đo mức độ ngẫu nhiên của tập dữ liệu. Có một vài loại entropy chẳng hạn như Gibbs Entropy, Boltzmann Entropy, và Rényi Entropy. Tuy nhiên, trong ngữ cảnh của bảo mật, loại entropy thường dùng là Shannon Entropy, có giá trị từ 0 đến 8. Mức độ ngẫu nhiên của tập dữ liệu càng nhiều thì entropy càng tăng.

Malware thường có entropy cao hơn các file thông thường do chúng thường nén, mã hóa hoặc đóng gói dữ liệu nhằm che giấu các signature.

Hình bên dưới so sánh entropy của các phần mềm thông thường và các mẫu malware:

Có thể thấy, các mẫu malware có entropy dao động từ 7.2 đến 8 còn các phần mềm thông thường có entropy dao động từ 5.6 đến 6.8.

Seealso

Hình ảnh trên lấy từ Threat Hunting with File Entropy – Practical Security Analytics LLC

Measuring a File’s Entropy

Để đo entropy của file thì ta có thể dùng công cụ PEStudio hoặc Sigcheck - Sysinternals. Để đơn giản hóa, ta sẽ sử dụng một Python script với hàm tính Shannon entropy được hiện thực như sau:

def calc_entropy(buffer):
    if isinstance(buffer, str):
        buffer = buffer.encode()
    entropy = 0
    for x in range(256):
        p = (float(buffer.count(bytes([x])))) / len(buffer)
        if p > 0:
            entropy += - p * math.log(p, 2)
    return entropy

Đoạn code trên sử dụng công thức sau:

H (X) = - i = 1 \sum n p (x_{i}) lo g_{2} p (x_{i})

Trong đó, $p (x_{i})$ chính là xác xuất của byte $x_{i}$ với $x_{i} \in [0, 255]$ . Giá trị này được tính bằng cách lấy tổng số lần xuất hiện của byte $x_{i}$ (buffer.count(bytes([x]))) rồi chia cho tổng số lượng byte của file (len(buffer)).

Ngoài khả năng tính entropy của toàn bộ file, nó còn có thể tính entropy của từng section trong file PE với flag -pe:

Algorithm Selection

Cách đầu tiên để làm giảm entropy chính là sử dụng thuật toán mã hóa có entropy thấp. Ví dụ, thuật toán mã hóa bằng phép XOR với 1-byte key¹ sẽ không làm tăng entropy quá nhiều nhưng nó là một thuật toán mã hóa yếu và có thể bị phá.

Một cách khác hiệu quả hơn để làm giảm entropy là sử dụng các thuật toán obfuscate² thay vì sử dụng mã hóa chẳng hạn như IPv4fuscation hay UUIDfuscation. Các thuật toán obfuscate cho ra dữ liệu có tổ chức và sắp xếp hơn các byte ngẫu nhiên được sinh ra bởi các thuật toán mã hóa.

Inserting English Strings

Một phương pháp khác để làm giảm entropy là thêm vào code các chuỗi tiếng Anh ngẫu nhiên. Do tiếng anh chỉ có 26 chữ cái và do đó mà chỉ có 52 (26 x 2) giá trị khác nhau cho 1 byte được lưu vào file thực thi. Con số này nhỏ hơn rất nhiều so với số lượng giá trị khả dĩ mà thuật toán mã hóa sinh ra (255 giá trị).

Nếu sử dụng kỹ thuật này, ta nên cố định việc dùng chữ cái viết hoa hoặc viết thường để làm giảm số lượng giá trị khả dĩ của từng byte.

Tuy nhiên, kỹ thuật này có một điểm yếu là các chuỗi tiếng Anh ở trong file thực thi có thể được dùng làm signature.

Padding By Same Bytes

Chúng ta cũng có thể padding bản mã của payload bằng cách byte giống hệt nhau. Lý do mà ta sử dụng các byte giống hệt nhau là do chúng có entropy bằng 0.00 (entropy của bản thân phần padding).

Ví dụ, hình ảnh sau cho thấy shellcode của msfvenom có entropy giảm từ 5.88325 xuống 3.77597 sau khi đệm thêm 285 byte 0xEA.

Điểm yếu của kỹ thuật này là nó sẽ làm tăng kích thước của file malware.

CRT Library Independent

CRT (hay C Runtime) library là một interface chuẩn dành cho ngôn ngữ C của Microsoft. Nó bao gồm nhiều hàm và macro liên quan đến việc quản lý vùng nhớ (memcpy), mở hoặc đóng file (fopen) và xử lý chuỗi (strcpy).

Việc loại bỏ CRT library có thể làm giảm đáng kể entropy. Hình ảnh bên dưới so sánh entropy của file trước và sau khi xóa CRT library:

EntropyReducer

Cũng có thể dùng công cụ EntropyReducer của Maldev Academy.

Một cách tổng quát, công cụ này sẽ obfuscate payload cũng như là làm giảm entropy của nó bằng cách sử dụng cấu trúc dữ liệu danh sách liên kết (Linked List) và thuật toán sắp xếp Merge Sort (là một thuật toán sắp xếp phù hợp cho linked list³).

Hình bên dưới minh họa cho cách mà EntropyReducer tổ chức lại payload để làm giảm entropy với BUFF_SIZE là 4 và NULL_BYTES là 2:

Chúng ta sẽ phân tích chi tiết cách mà EntropyReducer thực hiện obfuscate và deobfuscate payload.

Obfuscation Algorithm

Normalizing and Padding the Payload

Đầu tiên, nó sẽ kiểm tra xem kích thước của payload đầu vào có phải là bội số của BUFF_SIZE hay không. Nếu không, nó sẽ tính toán kích thước mới của buffer chứa payload mà có các byte đệm.

BOOL InitializePayloadList(IN PBYTE pPayload, IN OUT PSIZE_T sPayloadSize, OUT PLINKED_LIST* ppLinkedList)
{
 
    // variable used to count the linked list elements (used to calculate the final size)
    // it is also used as the node's ID
    unsigned int x = 0;
 
 
    // setting the payload size to be multiple of 'BUFF_SIZE'
    SIZE_T	sTmpSize = NEAREST_MULTIPLE(*sPayloadSize, BUFF_SIZE);
    if (!sTmpSize)
        return FALSE;
 
	// ...
}

Với NEAREST_MULTIPLE được định nghĩa như sau:

// set the 'sPayloadSize' variable to be equal to the next nearest number that is multiple of 'N'
#define NEAREST_MULTIPLE(sPayloadSize, N)(SIZE_T)((SIZE_T)sPayloadSize + (int)N - ((SIZE_T)sPayloadSize % (int)N))

Bỏ qua các phép ép kiểu, macro trên thực hiện tính toán như sau:

sPayloadSize % N là để tính phần dư khi đem sPayloadSize chia lấy dư cho N.
N - sPayloadSize % N là để tính số byte cần đệm thêm vào sPayloadSize để có được bội số của N.
sPayloadSize + N - sPayloadSize % N là bội số nhỏ nhất N mà sPayloadSize có thể đạt được bằng cách đệm thêm.

Sau khi có kích thước mới của buffer chứa payload, EntropyReducer sẽ thực hiện cấp phát vùng nhớ và sao chép payload vào vùng nhớ đó:

// new padded buffer 
PBYTE	pTmpBuffer = (PBYTE)HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sTmpSize);
if (!pTmpBuffer)
	return FALSE;
 
memcpy(pTmpBuffer, pPayload, *sPayloadSize);

Constructing the Payload Linked List

Sau đó, với mỗi BUFF_SIZE byte ở trong payload, hàm InitializePayloadList sẽ tạo ra một node ở trong danh sách liên kết tương ứng:

// variable used to count the linked list elements (used to calculate the final size)
// it is also used as the node's ID
unsigned int x = 0;
 
// for each 'BUFF_SIZE' in the padded payload, add it to the linked list
for (int i = 0; i < sTmpSize; i++) {
	if (i % BUFF_SIZE == 0) {
		*ppLinkedList = InsertAtTheEnd((PLINKED_LIST)*ppLinkedList, &pTmpBuffer[i], x);
		x++;
	}
}

Cấu trúc LINKED_LIST có định nghĩa như sau:

struct LINKED_LIST;
typedef struct _LINKED_LIST
{
	BYTE			pBuffer	[BUFF_SIZE];	// payload's bytes
	BYTE			pNull	[NULL_BYTES];	// null padded bytes
	INT			ID;			// node id
	struct LINKED_LIST*	Next;			// next node pointer	
 
}LINKED_LIST, * PLINKED_LIST;

Có thể thấy, mỗi node có một buffer tên là pNull chứa các null byte giúp làm giảm entropy của payload.

Hàm InsertAtTheEnd có nguyên mẫu như sau:

PLINKED_LIST InsertAtTheEnd(IN OUT PLINKED_LIST LinkedList, IN PBYTE pBuffer, IN INT ID);

Mục đích của hàm này là tạo ra một node mới với pBuffer và ID được truyền vào:

// creating a new node
PLINKED_LIST pNewNode = (PLINKED_LIST)HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(LINKED_LIST));
if (!pNewNode)
	return NULL;
memcpy(pNewNode->pBuffer, pBuffer, BUFF_SIZE);
pNewNode->ID = ID;
pNewNode->Next = NULL;

Sau đó, InsertAtTheEnd thêm node vừa tạo vào cuối danh sách liên kết LinkedList:

// new tmp pointer, pointing to the head of the linked list
PLINKED_LIST pTmpHead = (PLINKED_LIST)LinkedList;
 
// if the head is null, it will start at the new node we created earlier
if (LinkedList == NULL) {
	LinkedList = pNewNode;
	return LinkedList;
}
 
// else we will keep walking down the linked list till we find an empty node 
while (pTmpHead->Next != NULL)
	pTmpHead = pTmpHead->Next;
 
// pTmpHead now is the last node in the linked list
// setting the 'Next' value to the new node
pTmpHead->Next = pNewNode;
 
// returning the head of the linked list
return LinkedList;

Finalizing the Serialized Payload Size

Cuối cùng, InitializePayloadList sẽ cập nhật payload size (sPayloadSize) như sau:

// updating the size to be the size of the whole *serialized* linked list
*sPayloadSize = SERIALIZED_SIZE * x;

Với x là số lượng node còn SERIALIZED_SIZE là kích thước của 3 thành phần đầu tiên (không tính con trỏ đến node tiếp theo) trong một node, được định nghĩa như sau:

// this will represent the seraizlized size of one node
#define SERIALIZED_SIZE			(BUFF_SIZE + NULL_BYTES + sizeof(INT))

Sorting the Linked List with Merge Sort

Đến bước này, EntropyReducer sử dụng Merge Sort để sắp xếp các node ở trong danh sách liên kết thông qua hàm MergeSort:

VOID MergeSort(PLINKED_LIST* top, enum SORT_TYPE eType) {
    PLINKED_LIST tmp = *top, * a, * b;
 
    if (tmp != NULL && tmp->Next != NULL) {
        Split(tmp, &a, &b);				/* (divide) split head into "a" and "b" sublists */
 
        /* (conquer) sort the sublists */
        MergeSort(&a, eType);
        MergeSort(&b, eType);
 
        *top = Merge(a, b, eType);				/* (combine) merge the two sorted lists together */
    }
}

Với enum SORT_TYPE có các giá trị như sau:

typedef enum SORT_TYPE {
	SORT_BY_ID,
	SORT_BY_BUFFER
};

Splitting the Linked List with Fast & Slow Pointers

Hàm Split:

// split the nodes of the list into two sublists
void Split(PLINKED_LIST top, PLINKED_LIST* front, PLINKED_LIST* back) {
    PLINKED_LIST fast = top->Next;
    PLINKED_LIST slow = top;
 
    /* fast pointer advances two nodes, slow pointer advances one node */
    while (fast != NULL) {
        fast = fast->Next;		/* "fast" moves on first time */
        if (fast != NULL) {
            slow = slow->Next;	/* "slow" moves on first time */
            fast = fast->Next;	/* "fast" moves on second time */
        }
    }
 
    /* "slow" is before the middle in the list, so split it in two at that point */
    *front = top;
    *back = slow->Next;
    slow->Next = NULL;			/* end of the input list */
}

Hàm trên sử dụng kỹ thuật fast & slow pointer để tìm node ở giữa list. Nếu không sử dụng kỹ thuật này, chúng ta sẽ cần hai vòng lặp: một vòng lặp duyệt qua danh sách liên kết để tính kích thước và một vòng lặp để tìm node ở giữa.

Như vậy, nửa đầu danh sách bắt đầu từ top và kết thúc ở slow còn nửa sau danh sách bắt đầu ở slow->Next.

Việc gán thành phần Next của slow là NULL sẽ giúp phân tách hai list (khiến cho việc duyệt qua danh sách front sẽ kết thúc ở slow).

Merging Sorted Nodes

Hàm Merge:

// merge two linked lists 
PLINKED_LIST Merge(PLINKED_LIST top1, PLINKED_LIST top2, enum SORT_TYPE eType) {
    if (top1 == NULL)
        return top2;
    else
        if (top2 == NULL)
            return top1;
 
    PLINKED_LIST pnt = NULL;
 
    int iValue1 = 0;
    int iValue2 = 0;
 
    switch (eType) {
	// this is used to deobfuscate
    case SORT_BY_ID: {
        iValue1 = (int)top1->ID;
        iValue2 = (int)top2->ID;
        break;
    }
   // this is used to obfuscate
    case SORT_BY_BUFFER: {
        iValue1 = (int)(top1->pBuffer[0] ^ top1->pBuffer[1] ^ top1->pBuffer[2]);   // calculating a value from the payload buffer chunk
        iValue2 = (int)(top2->pBuffer[0] ^ top2->pBuffer[1] ^ top2->pBuffer[2]);   // calculating a value from the payload buffer chunk
        break;
    }
    default: {
        return NULL;
    }
    }
 
    /* pick either top1 or top2, and merge them */
    if (iValue1 <= iValue2) {
        pnt = top1;
        pnt->Next = Merge(top1->Next, top2, eType);
    }
    else {
        pnt = top2;
        pnt->Next = Merge(top1, top2->Next, eType);
    }
    return pnt;
}

Giá trị dùng để làm tiêu chí so sánh giữa các node là iValue1 và iValue2. Nếu chúng ta sắp xếp theo ID thì iValue sẽ là ID của node. Nếu chúng ta sắp xếp theo buffer thì iValue sẽ là kết quả của việc XOR 3 byte đầu của buffer bên trong node.

Sau khi tính các giá trị iValue, hàm Merge sẽ so sánh chúng để tìm ra node có iValue nhỏ hơn hoặc bằng trong 2 node được so sánh. Có 2 trường hợp sẽ xảy ra:

Nếu node đầu tiên (top1) nhỏ hơn thì ta gán pnt (danh sách kết quả sau khi sắp xếp) là top1 (đồng nghĩa với việc cho top1 vào danh sách kết quả) và gán con trỏ Next của pnt cho kết quả của việc so sánh top1->Next với top2.
Ngược lại, ta cho top2 vào danh sách kết quả và gán con trỏ Next của pnt cho kết quả của việc so ánh top1 với top2->Next.

Trong trường hợp ta đã duyệt qua hết danh sách ban đầu của top1 hoặc top2 (xảy ra khi một danh sách có 1 node và một danh sách không có node nào) thì các điều kiện if-else ở đầu hàm sẽ kết thúc việc đệ quy:

if (top1 == NULL)
        return top2;
else
	if (top2 == NULL)
		return top1;

Cuối cùng, hàm MergeSort sẽ chia nhỏ danh sách ra làm nhiều danh sách con và gộp chúng lại sử dụng hàm Merge.

Serializing the Linked List to a Buffer

Để lưu danh sách liên kết vào file, ta cần thực hiện serialize nó vào một buffer ở dạng mảng. EntropyReducer thực hiện điều này như sau:

PLINKED_LIST	pTmpHead	= pLinkedList;
SIZE_T			BufferSize	= NULL;
PBYTE			BufferBytes = (PBYTE)LocalAlloc(LPTR, SERIALIZED_SIZE);
 
// Serialize the linked list
while (pTmpHead != NULL) {
 
	// this buffer will keep data of each node
	BYTE TmpBuffer [SERIALIZED_SIZE] = { 0 };
 
	// copying the payload buffer
	memcpy(TmpBuffer, pTmpHead->pBuffer, BUFF_SIZE);
	// no need to copy the 'Null' element, cz its NULL already
	// copying the ID value
	memcpy((TmpBuffer + BUFF_SIZE + NULL_BYTES), &pTmpHead->ID, sizeof(int));
	
	// reallocating and moving 'TmpBuffer' to the final buffer
	BufferSize += SERIALIZED_SIZE;
 
	if (BufferBytes != NULL) {
		BufferBytes = (PBYTE)LocalReAlloc(BufferBytes, BufferSize, LMEM_MOVEABLE | LMEM_ZEROINIT);
		memcpy((PVOID)(BufferBytes + (BufferSize - SERIALIZED_SIZE)), TmpBuffer, SERIALIZED_SIZE);
	}
 
	// next node
	pTmpHead = pTmpHead->Next;
}

Việc tái cấp phát trong mỗi lần lặp là do ta không biết trước số lượng node có trong danh sách liên kết.

Giá trị BufferBytes + (BufferSize - SERIALIZED_SIZE) chính là offset đến vùng nhớ chứa thông tin của một node sau khi nó được serialized.

Sau khi được serialized thì chúng ta có thể ghi buffer BufferBytes có chứa payload đã được obfuscated và giảm entropy vào file.

Deobfuscation Algorithm

Deserializing the Buffer into a Linked List

Do bước cuối của Obfuscation Algorithm là serialize danh sách liên kết, bước đầu tiên của thuật toán deobfuscate sẽ là deserialize và chuyển buffer ở dạng mảng thành một danh sách liên kết.

// deserialize (from buffer to linked list - this must be done to re-order the payload's bytes)
for (size_t i = 0; i < sFuscatedSize; i++) {
	if (i % SERIALIZED_SIZE == 0)
		pLinkedList = InsertAtTheEnd(pLinkedList, &pFuscatedBuff[i], *(int*)&pFuscatedBuff[i + BUFF_SIZE + NULL_BYTES]);
}

Với i + BUFF_SIZE + NULL_BYTES chính là offset đến ID của một node đã bị serialized.

Reordering Nodes by ID

Sau khi deserialize thì ta tiến hành sort theo ID:

// re-ordering the payload's bytes
MergeSort(&pLinkedList, SORT_BY_ID);

Reassembling the Original Payload

Cuối cùng, ta lặp qua danh sách liên kết, lấy ra buffer của từng node và cho vào buffer chứa shellcode mà ta cần thực thi:

while (pTmpHead != NULL) {
	BYTE TmpBuffer[BUFF_SIZE] = { 0 };
 
	// copying the 'pBuffer' element from each node
	memcpy(TmpBuffer, pTmpHead->pBuffer, BUFF_SIZE);
 
	BufferSize += BUFF_SIZE;
 
	// reallocating to fit the new buffer
	if (BufferBytes != NULL) {
		BufferBytes = (PBYTE)LocalReAlloc(BufferBytes, BufferSize, LMEM_MOVEABLE | LMEM_ZEROINIT);
		memcpy((PVOID)(BufferBytes + (BufferSize - BUFF_SIZE)), TmpBuffer, BUFF_SIZE);
	}
 
	pTmpHead = pTmpHead->Next;
	x++; // number if nodes
}

Cleaning Up Memory: Freeing the Linked List

Việc giải phóng vùng nhớ của danh sách liên kết được thực hiện bằng cách dùng 2 con trỏ như sau:

// free linked list's nodes
pTmpHead = pLinkedList;
PLINKED_LIST pTmpHead2 = pTmpHead->Next;
 
while (pTmpHead2 != NULL) {
 
	if (!HeapFree(GetProcessHeap(), 0, (PVOID)pTmpHead)) {
		// failed
	}
	pTmpHead    = pTmpHead2;
	pTmpHead2   = pTmpHead2->Next;
}

Usage

EntropyReducer sẽ nhận vào một file chứa raw payload và cho ra một file cùng tên có đuôi là .ER chứa payload đã được obfuscate và giảm entropy.

PS D:\tools\EntropyReducer\x64\Debug> .\EntropyReducer.exe .\calc.bin
                        #################################################################################
                        #                                                                               #
                        #          EntropyReducer - Designed By MalDevAcademy: @NUL0x4C | @mrd0x        #
                        #                                                                               #
                        #################################################################################
 
 
[i] BUFF_SIZE : [ 0x0004 ] - NULL_BYTES : [ 0x0001 ]
[i] Reading ".\calc.bin" ... [+] DONE
        >>> Raw Payload Size : 276
        >>> Read Payload Located At : 0x000002439656BC70
[i] Obfuscating Payload ... [+] DONE
        >>> Obfuscated Payload Size : 630
        >>> Obfuscated Payload Located At : 0x000002439657DDE0
[i] Writing The Obfuscated Payload ...[+] DONE
PS D:\tools\EntropyReducer\x64\Debug> ls
 
 
    Directory: D:\tools\EntropyReducer\x64\Debug
 
 
Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
-a----          3/7/2025   3:14 PM            276 calc.bin
-a----          3/7/2025   3:14 PM            630 calc.bin.ER
-a----          3/7/2025   3:12 PM          72192 EntropyReducer.exe
-a----          3/7/2025   3:12 PM        1101824 EntropyReducer.pdb

Kích thước của obfuscated payload được tính bằng công thức sau:

FinalSize = ((OriginalSize + BUFF_SIZE - OriginalSize % BUFF_SIZE ) / BUFF_SIZE) * (BUFF_SIZE + NULL_BYTES + sizeof(INT))

Với (OriginalSize + BUFF_SIZE - OriginalSize % BUFF_SIZE ) / BUFF_SIZE là số lượng node còn BUFF_SIZE + NULL_BYTES + sizeof(INT) là kích thước của từng node.

Include In Your Projects

Để sử dụng trong project, ta chỉ cần thêm file EntropyReducer.c và file EntropyReducer.h vào project. Sau đó, gọi hàm Deobfuscate để thực hiện deobfuscate.

Resources

Mastering Coding Interview Patterns: Fast and Slow Pointers (Java, Python, and JavaScript) | by Saquib Khan | Medium

Quartz 🪬

Explorer

MalDev - Binary Entropy Reduction

Introduction

Measuring a File’s Entropy

Algorithm Selection

Inserting English Strings

Padding By Same Bytes

CRT Library Independent

EntropyReducer

Obfuscation Algorithm

Normalizing and Padding the Payload

Constructing the Payload Linked List

Finalizing the Serialized Payload Size

Sorting the Linked List with Merge Sort

Splitting the Linked List with Fast & Slow Pointers

Merging Sorted Nodes

Serializing the Linked List to a Buffer

Deobfuscation Algorithm

Deserializing the Buffer into a Linked List

Reordering Nodes by ID

Reassembling the Original Payload

Cleaning Up Memory: Freeing the Linked List

Usage

Include In Your Projects

Resources

Table of Contents

Backlinks

Quartz 🪬

Explorer

MalDev - Binary Entropy Reduction

Introduction

Measuring a File’s Entropy

Algorithm Selection

Inserting English Strings

Padding By Same Bytes

CRT Library Independent

EntropyReducer

Obfuscation Algorithm

Normalizing and Padding the Payload

Constructing the Payload Linked List

Finalizing the Serialized Payload Size

Sorting the Linked List with Merge Sort

Splitting the Linked List with Fast & Slow Pointers

Merging Sorted Nodes

Serializing the Linked List to a Buffer

Deobfuscation Algorithm

Deserializing the Buffer into a Linked List

Reordering Nodes by ID

Reassembling the Original Payload

Cleaning Up Memory: Freeing the Linked List

Usage

Include In Your Projects

Resources

Footnotes

Table of Contents

Backlinks