Quartz 🪬

MalDev - String Hashing

5 min read

String Hashing

Trong ngữ cảnh của lập trình malware, việc băm các chuỗi có trong mã nguồn giúp chúng không bị đánh dấu làm các signature bởi các giải pháp bảo mật.

Chúng ta sẽ xây dựng các thuật toán băm chuỗi sau:

  • Dbj2
  • JenkinsOneAtATime32Bit
  • LoseLose
  • Rotr32

Với kết quả đầu ra của các hàm trên là một số được biểu diễn dưới dạng thập lục phân.

Seealso

Tham khảo thêm các thuật toán băm chuỗi khác tại: vxunderground/VX-API: Collection of various malicious functionality to aid in malware development.

Dbj2

Thuật toán này hoạt động bằng cách lặp qua từng ký tự trong chuỗi và dùng ký tự đó để cập nhật giá trị băm:

hash = ((hash << 5) + hash) + c

Trong đoạn code trên, hash là giá trị băm còn c là ký tự hiện tại.

Kết quả của thuật toán này là một số nguyên dương (kiểu DWORD - unsigned long).

Hiện thực từ VX-API/VX-API/HashStringDjb2.cpp at main · vxunderground/VX-API:

#define INITIAL_HASH	3731  // added to randomize the hash
#define INITIAL_SEED	7     
 
// generate Djb2 hashes from Ascii input string
DWORD HashStringDjb2A(_In_ PCHAR String)
{
	ULONG Hash = INITIAL_HASH;
	INT c;
 
	while (c = *String++)
		Hash = ((Hash << INITIAL_SEED) + Hash) + c;
 
	return Hash;
}
 
// generate Djb2 hashes from wide-character input string
DWORD HashStringDjb2W(_In_ PWCHAR String)
{
	ULONG Hash = INITIAL_HASH;
	INT c;
 
	while (c = *String++)
		Hash = ((Hash << INITIAL_SEED) + Hash) + c;
 
	return Hash;
}

JenkinsOneAtATime32Bit

Tương tự với Dbj2, thuật toán này cũng lặp qua từng ký tự và dùng ký tự đó để cập nhật giá trị băm:

hash += c;
hash += (hash << 10);
hash ^= (hash >> 6);

Trong đoạn code trên, hash là giá trị băm còn c là ký tự hiện tại.

Kết quả của thuật toán này là một số nguyên dương (kiểu UINT32 - unsigned int).

Hiện thực từ VX-API/VX-API/HashStringJenkinsOneAtATime32Bit.cpp at main · vxunderground/VX-API:

#define INITIAL_SEED	7	
 
// Generate JenkinsOneAtATime32Bit hashes from Ascii input string
UINT32 HashStringJenkinsOneAtATime32BitA(_In_ PCHAR String)
{
	SIZE_T Index = 0;
	UINT32 Hash = 0;
	SIZE_T Length = lstrlenA(String);
 
	while (Index != Length)
	{
		Hash += String[Index++];
		Hash += Hash << INITIAL_SEED;
		Hash ^= Hash >> 6;
	}
 
	Hash += Hash << 3;
	Hash ^= Hash >> 11;
	Hash += Hash << 15;
 
	return Hash;
}
 
// Generate JenkinsOneAtATime32Bit hashes from wide-character input string
UINT32 HashStringJenkinsOneAtATime32BitW(_In_ PWCHAR String)
{
	SIZE_T Index = 0;
	UINT32 Hash = 0;
	SIZE_T Length = lstrlenW(String);
 
	while (Index != Length)
	{
		Hash += String[Index++];
		Hash += Hash << INITIAL_SEED;
		Hash ^= Hash >> 6;
	}
 
	Hash += Hash << 3;
	Hash ^= Hash >> 11;
	Hash += Hash << 15;
 
	return Hash;
}

LoseLose

Thuật toán LoseLose sẽ tính hash bằng cách lấy tổng các giá trị ASCII của từng ký tự:

hash = 0;
hash += c; // For each character c in the input string perform

Do dễ bị đụng độ giá trị băm, chúng ta sẽ điều chỉnh công thức tính hash một chút như sau:

hash = 0;
hash += c; // For each character c in the input string
hash *= c + 2;  // For more randomization

Hiện thực từ VX-API/VX-API/HashStringLoseLose.cpp at main · vxunderground/VX-API:

#define INITIAL_SEED	2
 
// Generate LoseLose hashes from ASCII input string
DWORD HashStringLoseLoseA(_In_ PCHAR String)
{
	ULONG Hash = 0;
	INT c;
 
	while (c = *String++) {
		Hash += c;
		Hash *= c + INITIAL_SEED;	// update
	}
	return Hash;
}
 
// Generate LoseLose hashes from wide-character input string
DWORD HashStringLoseLoseW(_In_ PWCHAR String)
{
	ULONG Hash = 0;
	INT c;
 
	while (c = *String++) {
		Hash += c;
		Hash *= c + INITIAL_SEED;	// update
	}
 
	return Hash;
}

Rotr32

Thuật toán này sẽ tính hash bằng cách công giá trị ASCII của từng ký tự với giá trị băm trước đó mà bị xoay bit sang phải:

Value = String[Index] + HashStringRotr32Sub(Value, INITIAL_SEED);

Với HashStringRotr32Sub là hàm dùng để xoay bit giá trị hash (Value) với số lượng bit sẽ xoay là INITIAL_SEED:

#define INITIAL_SEED	5	
 
// Helper function that apply the bitwise rotation
UINT32 HashStringRotr32Sub(UINT32 Value, UINT Count)
{
	DWORD Mask = (CHAR_BIT * sizeof(Value) - 1);
	Count &= Mask;
#pragma warning( push )
#pragma warning( disable : 4146)
	return (Value >> Count) | (Value << ((-Count) & Mask));
#pragma warning( pop ) 
}

Hàm HashStringRotr32Sub thực hiện phép xoay phải bit trên giá trị 32-bit Value với số bit cần xoay là Count (ở đây là INITIAL_SEED = 5). Khác với phép dịch bit thông thường (mà các bit bị đẩy ra ngoài sẽ mất đi)1, phép xoay bit sẽ giữ lại các bit bị đẩy ra khỏi bên phải và đưa chúng trở lại bên trái.

Các bước thực hiện:

  • Giới hạn Count: tạo Mask (có giá trị là 32) và tính Count &= Mask để đảm bảo Count nằm trong khoảng 0-31.
  • Dịch bit:
    • Dịch phải Value đi Count bit (Value >> Count).
    • Dịch trái Value đi 32 - Count bit (Value << (32 - Count)).
  • Kết hợp: Dùng phép OR (|) để gộp hai kết quả, hoàn thành phép xoay.

Hiện thực từ VX-API/VX-API/HashStringRotr32.cpp at main · vxunderground/VX-API:

// Generate Rotr32 hashes from Ascii input string
INT HashStringRotr32A(_In_ PCHAR String)
{
	INT Value = 0;
 
	for (INT Index = 0; Index < lstrlenA(String); Index++)
		Value = String[Index] + HashStringRotr32Sub(Value, INITIAL_SEED);
 
	return Value;
}
 
// Generate Rotr32 hashes from wide-character input string
INT HashStringRotr32W(_In_ PWCHAR String)
{
	INT Value = 0;
 
	for (INT Index = 0; Index < lstrlenW(String); Index++)
		Value = String[Index] + HashStringRotr32Sub(Value, INITIAL_SEED);
 
	return Value;
}

Stack Strings

Chúng ta cũng có thể khai báo chuỗi bằng cách sử dụng mảng ký tự như sau:

char string[] = { 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '\0' };

Bằng cách này, ta có thể né tránh được signature detection:

Resources

Footnotes

  1. xem thêm Bit shifting. ↩

Backlinks