C++哈希表bucket机制与Pwn题解分析

一、哈希表与bucket基础

1. 哈希表基本概念

哈希表是一种通过哈希函数将键(key)映射到索引位置的数据结构，核心特点：

• 使用哈希函数计算键的存储位置
• 理想情况下实现O(1)时间复杂度的查找、插入和删除
• 需要处理哈希冲突问题

2. bucket机制详解

bucket是哈希表中的基本存储单元：

• 每个bucket对应一个哈希值或哈希值范围
• 相同哈希值的元素存储在同一个bucket中
• 通常实现为链表或其他容器(如数组、向量)

3. C++中的bucket操作

在std::unordered_map和std::unordered_set中提供以下关键操作：

二、题目分析：novel1

1. 程序基本信息

• 保护机制：Partial RELRO, no canary, no PIE
• 关键漏洞：栈溢出
• 主要函数：part1、part2、RACHE

2. 关键函数分析

part1函数

• 功能：向哈希表中插入键值对
• 参数：idx(键), value(值)

part2函数

• 功能：处理特定bucket中的元素
• 关键操作：使用std::copy将bucket内容复制到栈上

std::copy漏洞点

std::copy<std::__detail::_Local_iterator<...>, std::pair*<...>>(
    begin,  // bucket起始迭代器
    end,    // bucket结束迭代器 
    v3);    // 目标栈数组

• 将整个bucket内容复制到栈数组v3
• 无边界检查导致栈溢出

3. 利用思路

1. bucket控制：通过精心选择idx使多个键落入同一bucket
2. 栈溢出：利用std::copy将大量数据复制到栈上
3. ROP链构造：覆盖返回地址实现控制流劫持

4. 利用步骤详解

1. 爆破bucket索引：

for j in range(1,100):
    # 测试哪些idx会落入同一bucket
    part1(i*j, 10)  # 插入多个元素
    part2(j)        # 触发bucket复制

2. 栈迁移准备：

• 利用author字段输入ROP链
• 使用magic gadget控制rsp

3. 泄露libc地址：

payload = p64(pop_rdi_rbp) + p64(puts_got) + p64(puts)

4. 最终利用：

• 使用ret2syscall而非system（避免rsp下移问题）
• 构造execve("/bin/sh",0,0)

三、题目分析：anyip

1. 协议分析

协议包结构：

def pack(func, para1, content):
    buf = p16(func)                  # 2字节功能号
    buf += b"\x00" + p8(para1)       # 1字节参数 
    buf += b"\x00"*4 + b"\x01\x07\x00\x00"  # 固定魔数
    buf += content                   # 可变内容

2. 功能函数

• 0x4444：队列操作
• 0x2222：栈操作（存在POP无检查漏洞）
• 0x3333：字符串处理
• 0x1111：文件读取

3. 漏洞利用

1. 栈负向溢出：

• 通过多次POP使stackTop变为负数
• 覆盖队列控制结构(qFront, qEnd)

2. 任意写构造：

• 覆盖stack的base指针绕过检查
• 修改log文件名指针指向"flag"

3. 字符串构造技巧：
   通过fuzz发现输入"peuoIfnSm"可得到"SomeIpfun"

四、关键知识点总结

1. 哈希表安全要点

• bucket溢出风险
• 哈希碰撞攻击防范
• 迭代器失效问题

2. Pwn题通用技巧

1. 保护机制分析：

• No canary → 栈溢出可能
• No PIE → 地址固定
• Partial RELRO → GOT可写

2. 漏洞挖掘方法：

• 关注无边界检查的复制操作
• 注意负数索引处理
• 分析数据结构交互边界

3. 利用限制绕过：

• 栈迁移解决空间不足
• ret2syscall替代system
• 数据段复用技巧

3. 逆向分析技巧

• C++符号解析
• STL容器识别
• 迭代器模式分析

五、防御建议

1. 编码层面：

• 所有复制操作添加边界检查
• 使用安全容器替代原生STL
• 负数索引特殊处理

2. 编译层面：

• 开启所有保护机制(Canary, PIE, FULL RELRO)
• 使用现代C++安全特性

3. 架构层面：

• 敏感操作添加权限控制
• 实现输入验证机制
• 关键数据结构隔离保护