红帽杯2021 file_store

题目下载: file_store.zip

做这道题之前可以先学习一下 Huffman 编码，同时这道题还涉及到大量的 stl 使用，可以锻炼 stl 逆向分析能力。Huffman 一般用于数据压缩，与题目名比较吻合。这道题其实是利用 Huffman 编码对 flag 文件进行编码，解题方法是解压 Huffman 编码过的文件即可。

这道题压缩方案是利用传统 Huffman 树构造方法，统计词频并根据词频高低构造 Huffman 树，用 01 串表示词在 Huffman 树中的位置，最后将 01 串转换成字节流。

要解压缩某个数据，必须要有该数据文件对应的 Huffman 树的结构，因此题目提供了 flag.txt.shuffled 文件，该文件打乱了 flag.txt 的顺序，但是词频没有变，使用该文件构造 Huffman 树，即可对 flag.bin 解压。

⚠️这道题中，词 = 字符，词频就是字符出现的次数

Huffman 树的构造

函数地址: 40184A

1. 词频统计

Huffman 树中节点的构造依赖于词频分析，“词”的含义不是一个单词，而是一个字节。词频越高意味使用次数越多，就越靠近跟节点，01 串表示的路径就跟短，有利于压缩。

逆向 stl 的时候经常遇到 “迭代器”

2. 为每一个不重复的字符创建 Huffman 节点，高度为1，并将新创建的节点加入到 Huffman 森林（arrayResult 数组）

3. 从 Huffman 森林中选出某些树合并

标准 Huffman 树是选出权制最小的两棵子树合并，但是这道题似乎并不是这样

循环退出的条件是 Huffman 森林中只有一颗🌲

4. 遍历计算路径 函数地址: 4016D6

0 代表走左，1代表走右

遍历函数到达叶子结点的时候，将 01 路径串与字符通过 stl map 建立关联。

输入文件 flag.txt.shuffled ，并在此处尝试 dump 关联的键值对即可获取 01串与真实数据之间的编码关系.

dump ida 脚本如下, 该脚本使用方法是在 40171D call find 处设置条件断点为 bp_dumper() 即可.

import idaapi
import idc

def decode_stl_str(p):
    size = idc.read_dbg_qword(p + 0x8)
    dataPtr = idc.read_dbg_qword(p)
    buf = []
    for i in range(size):
        buf.append(idc.read_dbg_byte(dataPtr + i))
    return bytearray(buf)

# bp 40171D
reverseMap = {}
def bp_dumper():
    global reverseMap
    pNodeVal = idc.get_reg_value('rsi')
    nodeVal = idc.read_dbg_byte(pNodeVal)
    rbp = idc.get_reg_value('rbp')
    pStr = idc.read_dbg_qword(rbp - 0x58)
    huffmanCode = decode_stl_str(pStr).decode('utf-8')
    print(chr(nodeVal), huffmanCode)
    reverseMap[huffmanCode] = chr(nodeVal)
    return False

当所有的键值队都记录之后，print(reverseMap) 就可以得到对应关系, 我得到的数据如下

huffman = {'00000000': 'T', '00000001': '6', '0000001': '1', '0000010000': 'L', '0000010001': 'R', '0000010010': '}', '0000010011': 'M', '0000010100': ';', '0000010101': 'C', '0000010110': '{', '0000010111': 'x', '0000011000': 'F', '0000011001': 'J', '0000011010': 'q', '0000011011': '9', '000001110': 'G', '000001111': '4', '000010000': '2', '000010001': "'", '000010010': '7', '000010011': 'W', '0000101': '-', '00001100': 'k', '00001101': '3', '0000111': 'b', '0001': 'i', '001': 'e', '0100': 'n', '01010': 'f', '010110': 'y', '010111': 'u', '0110': 'o', '0111': 'r', '10000': 'l', '1000100': 'S', '1000101': 'v', '100011': 'g', '10010': 'd', '1001100': 'H', '1001101': 'p', '10011100': 'A', '100111010': '8', '100111011': '\r', '100111100': '5', '1001111010': ':', '10011110110': '(', '10011110111': ')', '100111110': '\n', '100111111': 'B', '1010': 't', '101100': 'w', '101101': 'm', '1011100': ',', '1011101': '.', '101111': 'c', '1100': 'a', '11010': 'h', '11011': 's', '111': ' '}

二叉树数据结构

1. 叶结点

叶结点才是带数据的结点

2. 非叶子节点

这两种结构的第二个 dd 的数据可以用来区分叶节点或者非叶子节点，区分值 0FFFFFFFF

叶子节点和非叶子节点的数据类型结构不一样，但是却通过非叶子节点中同一个指针字段指向，很少见。

后续小细节

1. 01 字符串转字节流 40878C

下断点观察数据即可

2. 最后一步输出还有一个加密算法

这是一种类似rc4 带入密文即可得到明文的加密算法, 动态调试修改数据即可解密。

3. 解压过程

我直接暴力匹配 01串前缀，匹配成功的则删除待解压数据的前缀，最终删除所有待解压数据，得到已经解压的数据

data = bytearray(data)
s = ''
for i in data:
    s += bin(i)[2:].zfille(8)

flag = ''
while s != '':
    for prefix in huffman:
        if s.startswith(prefix):
            flag += huffman[prefix]
            s = s[len(prefix): ]

最后得到 flag