CTF easy_hash 题目解析：多项式与自定义哈希逆向

CTF easy_hash 题目解析：多项式与自定义哈希逆向

一、题目信息

• 题目名称：easy_hash
• 比赛名称：DASCTF NOV X 联合出题人 2022 年度积分榜争夺赛
• 题目描述：闲来无事自己写了个 hash，你能看懂嘛？
• 附件：interesting.py

二、题目分析

拿到题目后，首先分析附件代码的逻辑。题目主要包含两个核心函数：myhash 和 encode。

1. 自定义哈希函数 myhash

这个函数是题目的核心难点之一，它的处理流程如下：

def myhash(x):
    res = []
    end = b""
    bytescipher = long_to_bytes(x)
    # 1. 处理前缀（无法被 8 整除的剩余部分）
    a = bytescipher[:len(bytescipher) % 8]
    res.append(a)
    res.append(long_to_bytes(crc32(a)))
    # 添加前缀的 CRC32 校验值
    # 2. 处理 8 字节对齐的数据块
    t = (len(bytescipher) // 8)
    bytescipher = bytescipher[len(bytescipher) % 8:]
    for i in range(t):
        a = bytescipher[i*8:i*8+8]
        res.append(a)
        res.append(long_to_bytes(crc32(a)))
        # 添加每个数据块的 CRC32 校验值
    # 3. 拼接并转换
    for i in res:
        end += i
    res = bytes_to_long(end)
    # 4. 截断操作
    res = (res + (res >> 500)) & (2**500 - 1)
    return res

关键点分析：

• 输入数据被分割成若干块：一个长度为 len % 8 的前缀，和若干个 8 字节的块。
• 输出结构为：[前缀] + [CRC32(前缀)] + [块 1] + [CRC32(块 1)] + ...。
• 最后进行了截断，保留了低 500 位。

2. 加密函数 encode

def encode(pt):
    a = []
    b = []
    a.append(myhash(pt))
    for i in range(3):
        a.append(myhash(a[i]))
    # 构建哈希链
    # 计算多项式
    for j in range(4):
        secret = (a[0] + a[1]*a[j] + a[2]*a[j]**2 + a[3]*a[j]**3) % P
        b.append([a[j], secret])
    return b

逻辑梳理：

• a[0] = myhash(flag)
• a[1] = myhash(a[0])
• a[2] = myhash(a[1])
• a[3] = myhash(a[2])
• 对于每个 a[j]，计算多项式 $f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 \pmod P$。

3. 已知条件

题目给出了 FLAG[1] 的值：

FLAG[1] = [a[1], secret]

其中 a[1] 和对应的 secret 是已知的整数，大质数 P 也是已知的。

三、解题思路

步骤一：计算哈希链的后续节点

题目给出了 a[1]，根据哈希链的迭代关系：

• $a[2] = \text{myhash}(a[1])$
• $a[3] = \text{myhash}(a[2])$

我们可以直接计算出 a[2] 和 a[3]。

步骤二：反推 a[0]

我们知道多项式方程： $$ secret \equiv a[0] + a[1] \cdot a[1] + a[2] \cdot a[1]^2 + a[3] \cdot a[1]^3 \pmod P $$

现在除了 $a[0]$ 以外，其他所有变量都已知。我们可以轻松反推 $a[0]$： $$ a[0] \equiv secret - a[1]^2 - a[2] \cdot a[1]^2 - a[3] \cdot a[1]^3 \pmod P $$

步骤三：验证并逆向 myhash

计算出 a[0] 后，我们可以验证 myhash(a[0]) 是否等于已知的 a[1]。如果相等，说明我们的计算正确。 接下来是最关键的一步：从 a[0] 逆向还原出原始的 flag。 观察 myhash 的结构，它是 [数据块] + [CRC32 校验值] 的拼接。 由于 CRC32 是确定性的校验算法，且输出为 4 字节，我们可以尝试解析 a[0] 的字节流：

1. 尝试不同的前缀长度（0-7 字节）。
2. 提取前缀后的 4 字节，验证是否为该前缀的 CRC32 值。
3. 如果匹配，继续以'8 字节数据 + 4 字节 CRC32'的格式解析后续数据。
4. 校验所有块的 CRC32 值，如果全部正确，则提取出的数据块拼接起来即为原始 flag。

四、详细解题过程

1. 计算 a[2] 和 a[3]

利用题目给出的 myhash 函数和已知的 a[1]：

a2 = myhash(known_a1)
a3 = myhash(a2)

2. 求解 a[0]

代入多项式方程求解：

# f(a[1]) = a[0] + a[1]*a[1] + a[2]*a[1]**2 + a[3]*a[1]**3
term1 = known_a1 * known_a1
term2 = a2 * (known_a1 ** 2)
term3 = a3 * (known_a1 ** 3)
a0 = (known_secret - term1 - term2 - term3) % P

验证 myhash(a[0]) == known_a1，结果为 True，验证通过。

3. 逆向解析 Flag

得到的 a[0] 转换为字节后长度为 54 字节。我们编写脚本尝试解析：

a0_bytes = long_to_bytes(a0)
# 尝试前缀长度从 0 到 7
for prefix_len in range(8):
    # ... 提取前缀和 CRC ...
    # 验证 CRC32
    # ... 提取后续数据块并验证 ...

经过尝试，当前缀长度为 2 时，所有 CRC32 校验均通过：

• 前缀 (2 字节): DA
• 数据块 1 (8 字节): SCTF{th1
• 数据块 2 (8 字节): s_is_the
• 数据块 3 (8 字节): _fe3st_q
• 数据块 4 (8 字节): uest1on}

拼接得到完整 Flag。

五、完整解题代码

from Crypto.Util.number import bytes_to_long, long_to_bytes
from zlib import crc32

# ==================== 已知参数 ====================
P = 93327214260434303138080906179883696131283277062733597039773430143631378719403851851296505697016458801222349445773245718371527858795457860775687842513513120173676986599209741174960099561600915819416543039173509037555167973076303047419790245327596338909743308199889740594091849756693219926218111062780849456373

# 题目给出的 FLAG[1]
known_a1 = 1768672211043417187765307394749760760531160781992300779145800061219666992833602547480090118225665457075744297987672863699370162614965380859290914620736
known_secret = 89139545215288033432210221492974990584987914397112840989583439688211128705545477536596587262069032020212762581490561288493533363888589066045095054475929099275247145877699370608950340925139625068446642116123285918461312297390611577025368805438078034230342490499137494400676347225155752865648820807846513044723

# ==================== 函数定义 ====================
def myhash(x):
    res = []
    end = b""
    bytescipher = long_to_bytes(x)
    a = bytescipher[:len(bytescipher) % 8]
    res.append(a)
    res.append(long_to_bytes(crc32(a)))
    t = (len(bytescipher) // 8)
    bytescipher = bytescipher[len(bytescipher) % 8:]
    for i in range(t):
        a = bytescipher[i*8:i*8+8]
        res.append(a)
        res.append(long_to_bytes(crc32(a)))
    for i in res:
        end += i
    res = bytes_to_long(end)
    res = (res + (res >> 500)) & (2**500 - 1)
    return res

# ==================== 解题步骤 ====================
# Step 1: 计算哈希链后续节点
a2 = myhash(known_a1)
a3 = myhash(a2)

# Step 2: 从多项式方程反推 a[0]
# f(a[1]) = a[0] + a[1]*a[1] + a[2]*a[1]**2 + a[3]*a[1]**3
term1 = known_a1 * known_a1
term2 = a2 * (known_a1 ** 2)
term3 = a3 * (known_a1 ** 3)
a0 = (known_secret - term1 - term2 - term3) % P

# Step 3: 验证哈希链
assert myhash(a0) == known_a1, "验证失败"

# Step 4: 逆向解析 myhash
a0_bytes = long_to_bytes(a0)
flag_bytes = b""
# 尝试不同的前缀长度
for prefix_len in range(8):
    if len(a0_bytes) < prefix_len + 4:
        continue
    prefix = a0_bytes[:prefix_len]
    prefix_crc = a0_bytes[prefix_len:prefix_len+4]
    if prefix_crc != long_to_bytes(crc32(prefix)):
        continue
    # 前缀 CRC 匹配，开始解析后续块
    blocks = [prefix]
    pos = prefix_len + 4
    valid = True
    while pos + 12 <= len(a0_bytes):
        block = a0_bytes[pos:pos+8]
        block_crc = a0_bytes[pos+8:pos+12]
        if block_crc == long_to_bytes(crc32(block)):
            blocks.append(block)
            pos += 12
        else:
            valid = False
            break
    if valid and pos == len(a0_bytes):
        flag_bytes = b''.join(blocks)
        break

try:
    print(f"Flag: {flag_bytes.decode()}")
except:
    print(f"Flag (hex): {flag_bytes.hex()}")

六、运行结果

Flag: DASCTF{th1s_is_the_fe3st_quest1on} 

七、总结

这道题虽然名为 easy_hash，但考察的知识点比较全面：

1. 代码审计能力：理解自定义哈希函数和加密流程。
2. 代数基础：利用模运算性质求解多项式方程中的未知数。
3. 逆向思维：在无法直接求逆的情况下，利用哈希函数的结构特性（数据 + 校验）进行数据还原。
4. CRC32 特性：理解 CRC32 是校验码而非加密算法，可用于数据完整性验证和结构解析。

整体来说是一道质量很高的密码学题目，不仅考察了数学推导，还考验了对数据结构的分析能力。