自定义 String 哈希算法教学文档

1. 哈希算法概述

1.1 定义

将字符串映射为唯一的整数(哈希值)的算法，公式表示为：H(s) = 唯一HASH值

1.2 特点

1. 唯一性(抗碰撞性)：理想状态下不同输入应生成唯一哈希值，根据鸽巢原理，哈希冲突必然存在，但碰撞概率非常低
2. 不可逆性(单向性)：从哈希值反推原始输入在计算上不可行(即使已知算法)

1.3 应用场景

1. 避免检测：将API名称转换为整数哈希值，消除可读字符串特征，降低静态分析风险
2. 减小shellcode体积：32位哈希值(4字节)通常比API名称字符串更短

2. ROTR32算法

2.1 算法原理

ROTR32(32位循环右移)是一种位运算操作，将32位整数的二进制表示向右循环移动指定位数，移出的位从左侧重新填充。

计算公式：

ROTR32(x, n) = (x >> n) | (x << (32 - n))

2.2 实现代码

C语言实现

#include <stdint.h>

uint32_t rotr32(uint32_t value, uint32_t shift) {
    return (value >> shift) | (value << (32 - shift));
}

uint32_t hash_string_rotr32(const char* str) {
    uint32_t hash = 0;
    for (; *str; ++str) {
        hash = rotr32(hash, 13) + *str;
    }
    return hash;
}

Python实现

def rotr32(value, shift):
    shift %= 32  # 确保移动位数在[0,31]范围内
    return ((value >> shift) | (value << (32 - shift))) & 0xFFFFFFFF

def hash_string_rotr32(s):
    hash_val = 0
    for c in s:
        hash_val = rotr32(hash_val, 13) + ord(c)
        hash_val &= 0xFFFFFFFF  # 限制为32位
    return hash_val

Go实现

func rotr32(value uint32, shift uint32) uint32 {
    return (value >> shift) | (value << (32 - shift))
}

func hashStringRotr32(s string) uint32 {
    var hash uint32 = 0
    for _, c := range s {
        hash = rotr32(hash, 13) + uint32(c)
    }
    return hash
}

MASM汇编实现

; 输入: esi = 字符串指针
; 输出: eax = 哈希值
hash_string_rotr32:
    xor eax, eax
    xor ecx, ecx
.loop:
    mov cl, [esi]
    test cl, cl
    jz .done
    ror eax, 13
    add eax, ecx
    inc esi
    jmp .loop
.done:
    ret

2.3 常见API哈希值示例

ws2_32.dll+WSAStartup = 4645344Ch
ws2_32.dll+WSASocketA = 0B83D505Ah
ws2_32.dll+connect = 6AF3406Dh
ws2_32.dll+recv = 0F1606037h
kernel32.dll+LoadLibraryA = 56590AE9h
kernel32.dll+VirtualAlloc = 0FBFA86AFh
kernel32.dll+GetProcAddress = 0E658B905h
kernel32.dll+VirtualProtect = 0E3918276h
kernel32.dll+ExitProcess = 0DE2D94D9h

3. CRC32算法

3.1 算法原理

CRC32是一种32位循环冗余校验算法，通过多项式除法生成固定长度的校验码。

计算流程：

1. 初始化：crc = 0xFFFFFFFF
2. 混合字节：crc ^ 0x01 = 0xFFFFFFFE
3. 8轮位操作：
   • 第1轮: 0xFFFFFFFE & 1 = 0 → 右移 → 0x7FFFFFFF
   • 第2轮: 0x7FFFFFFF & 1 = 1 → 右移并异或多项式 → (0x3FFFFFFF) ^ 0xEDB88320
   • ...(重复8次)
4. 最终取反：得到校验码

3.2 实现代码

C语言实现

#include <stdint.h>

uint32_t crc32(const char* str) {
    uint32_t crc = 0xFFFFFFFF;
    for (; *str; ++str) {
        crc ^= *str;
        for (int i = 0; i < 8; i++) {
            if (crc & 1) {
                crc = (crc >> 1) ^ 0xEDB88320;
            } else {
                crc >>= 1;
            }
        }
    }
    return ~crc;
}

Python实现

def crc32(s):
    crc = 0xFFFFFFFF
    for c in s:
        crc ^= ord(c)
        for _ in range(8):
            if crc & 1:
                crc = (crc >> 1) ^ 0xEDB88320
            else:
                crc >>= 1
    return (~crc) & 0xFFFFFFFF

Go实现

func crc32(s string) uint32 {
    crc := uint32(0xFFFFFFFF)
    for _, c := range s {
        crc ^= uint32(c)
        for i := 0; i < 8; i++ {
            if crc&1 == 1 {
                crc = (crc >> 1) ^ 0xEDB88320
            } else {
                crc >>= 1
            }
        }
    }
    return ^crc
}

4. 算法选择建议

1. ROTR32：

   • 实现简单，计算速度快
   • 在MSF和CS的stager中被广泛使用
   • 抗碰撞性良好

2. CRC32：

   • 主要用于数据校验
   • 计算过程稍复杂
   • 在pe_to_shellcode等项目中使用

5. 注意事项

1. 不同实现可能产生不同的哈希值，使用时需确保一致性
2. 汇编实现可能与高级语言实现有细微差异，需特别注意
3. 哈希冲突不可避免，但在实际应用中概率很低