51-字符串哈希

Maldevacademy大约 6 分钟安全开发

介绍

哈希（Hashing）是一种用于创建固定大小数据表示的技术，称为哈希值或哈希码。哈希算法被设计为单向函数，这意味着使用哈希值计算原始输入数据在计算上是不可行的。哈希码通常更小，而且处理起来更快。比较字符串时，可以使用哈希快速确定两个字符串是否相等，而无需比较字符串本身，尤其是在字符串很长的情况下。

在恶意软件开发中，字符串哈希是一种有用的方法，可以隐藏实现中使用的字符串，因为字符串可以作为签名，帮助安全供应商检测恶意二进制文件。

字符串哈希

本模块介绍一些字符串哈希算法。务必了解，这些算法的输出是一个十六进制格式的数字，因为这样更加简洁明了。本模块讨论了以下字符串哈希算法：

Djb2
JenkinsOneAtATime32Bit
LoseLose
Rotr32

可用的字符串哈希算法远远多于本模块讨论的这些算法，你可以在 VX-API GitHub 仓库open in new window 中找到其中一些算法。

Djb2

Djb2 是一种简单且快速的哈希算法，主要用于生成字符串的哈希值，但也可用于其他类型的数据。它的工作原理是遍历输入字符串中的字符，并使用每个字符根据特定算法更新一个运行哈希值，如下面的代码片段所示。

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

hash 是当前哈希值，c 是输入字符串中的当前字符，<< 是位移左移操作符。

产生的哈希值是一个整数，它对于输入字符串来说是唯一的。众所周知，Djb2 会产生哈希值的良好分布，从而导致不同字符串与其各自的哈希值之间碰撞的概率很低。

下面显示的 Djb2 实现来自 VX-API GitHub 存储库open in new window。

#define INITIAL_HASH	3731  // 添加随机哈希
#define INITIAL_SEED	7     

// 从 ASCII 输入字符串生成 Djb2 哈希
DWORD HashStringDjb2A(_In_ PCHAR String)
{
	ULONG Hash = INITIAL_HASH;
	INT c;

	while (c = *String++)
		Hash = ((Hash << INITIAL_SEED) + Hash) + c;

	return Hash;
}

// 从宽字符输入字符串生成 Djb2 哈希
DWORD HashStringDjb2W(_In_ PWCHAR String)
{
	ULONG Hash = INITIAL_HASH;
	INT c;

	while (c = *String++)
		Hash = ((Hash << INITIAL_SEED) + Hash) + c;

	return Hash;
}

JenkinsOneAtATime32Bit算法

JenkinsOneAtATime32Bit算法基于遍历输入字符串中的字符，根据每个字符的值逐步更新运行哈希值的工作原理。更新哈希值的算法如下面的代码片段所示。

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

其中，hash是当前哈希值，c是输入字符串中的当前字符。

生成的哈希值是一个32位整数，该整数对于输入字符串来说是唯一的。JenkinsOneAtATime32Bit算法可以生成相对均匀的哈希值分布，从而导致不同字符串与其各自的哈希值发生冲突的概率较低。

下面所示的JenkinsOneAtATime32Bit实现来自VX-API GitHub 仓库open in new window。

#define INITIAL_SEED 7

// 从 ASCII 输入字符串生成 JenkinsOneAtATime32Bit 哈希值
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;
}

// 从宽字符输入字符串生成 JenkinsOneAtATime32Bit 哈希值
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 算法

LoseLose 算法通过遍历字符串中的每个字符并对每个字符的 ASCII 值求和来计算输入字符串的哈希值。更新哈希值的算法如下所示。

hash = 0;
hash += c; // 对输入字符串中的每个字符 c 执行

LoseLose 算法产生的哈希值是一个唯一对应于输入字符串的整数。但是，由于哈希值的分布不佳，可能会发生碰撞。为了解决这个问题，算法的公式已更新，如下所示。

hash = 0;
hash += c; // 对输入字符串中的每个字符 c 执行
hash *= c + 2; // 为了增加随机性

这并不能使其成为一个好的哈希算法，但确实在一定程度上有所改进。下面显示的 LoseLose 实现来自 VX-API GitHub 存储库open in new window。

#define INITIAL_SEED	2

// 从 ASCII 输入字符串生成 LoseLose 哈希
DWORD HashStringLoseLoseA(_In_ PCHAR String)
{
	ULONG Hash = 0;
	INT c;

	while (c = *String++) {
		Hash += c;
		Hash *= c + INITIAL_SEED;	//更新
	}
	return Hash;
}

// 从宽字符输入字符串生成 LoseLose 哈希
DWORD HashStringLoseLoseW(_In_ PWCHAR String)
{
	ULONG Hash = 0;
	INT c;

	while (c = *String++) {
		Hash += c;
		Hash *= c + INITIAL_SEED;	//更新
	}

	return Hash;
}

Rotr32

Rotr32 字符串哈希算法通过对输入字符串中的字符进行迭代，对它们的 ASCII 值求和，然后对当前的哈希值应用按位循环左移，从而生成一个哈希值。输入值和一个计数（即 INITIAL_SEED）用于对值进行右移，然后与用计数的相反数左移的原始值进行逻辑或运算。

所得哈希值是一个 32 位整数，对于输入字符串是唯一的。Rotr32 可以生成相对较好的哈希值分布，从而导致不同字符串及其哈希值之间发生冲突的概率较低。

下面显示的 Rotr32 实现来自 VX-API GitHub 存储库open in new window。

#define INITIAL_SEED        5

// 应用按位循环左移的帮助器函数
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 )
}

// 根据Ascii输入字符串生成Rotr32哈希
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;
}

// 根据宽字符输入字符串生成Rotr32哈希
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;
}

栈字符串

在 C/C++ 编程语言中，字符串可以表示为一个字符数组，这样可以将字符彼此分开，从而帮助避开基于字符串的检测。例如，字符串“hello world”可以表示为下面的数组。

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

使用 HxD 二进制编辑器搜索字符串“hello world”不会返回任何结果。

然而，栈字符串不足以将字符串隐藏在一些调试器和逆向工程工具中，因为它们可以包含检测它们的插件。

示例

下面我们将使用本模块中提到的算法对字符串“MaldevAcademy”进行哈希运算。字符串将以 ASCII 和 Wide 格式进行哈希运算。请注意，根据哈希算法的不同，ASCII 和 Wide 格式可能不会始终生成相同哈希值。