CTF BUUOJ [DASCTF NOV X联合出题人2022年度积分榜争夺赛！]easy_hash Writeup
CTF BUUOJ [DASCTF NOV X联合出题人2022年度积分榜争夺赛！]easy_hash Writeup —— 多项式与自定义哈希的逆向之旅
一、题目信息
- 题目名称：easy_hash
- 比赛名称：DASCTF NOV X联合出题人2022年度积分榜争夺赛
- 题目描述：闲来无事自己写了个hash，你能看懂嘛？
- 附件：
interesting.py
二、题目分析
拿到题目后，首先分析附件代码的逻辑。题目主要包含两个核心函数：myhash 和 encode。
1. 自定义哈希函数 myhash
这个函数是题目的核心难点之一，它的处理流程如下：
defmyhash(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 inrange(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)-1return res 关键点分析：
- 输入数据被分割成若干块：一个长度为
len % 8的前缀，和若干个 8 字节的块。 - 输出结构为：
[前缀] + [CRC32(前缀)] + [块1] + [CRC32(块1)] + ...。 - 最后进行了截断，保留了低500位。
2. 加密函数 encode
defencode(pt): a=[] b=[] a.append(myhash(pt))for i inrange(3): a.append(myhash(a[i]))# 构建哈希链# 计算多项式for j inrange(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)=a0+a1x+a2x2+a3x3(modP)f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 \pmod Pf(x)=a0+a1x+a2x2+a3x3(modP)。
3. 已知条件
题目给出了 FLAG[1] 的值：
FLAG[1]=[a[1], secret]其中 a[1] 和对应的 secret 是已知的整数，大质数 P 也是已知的。
三、解题思路
步骤一：计算哈希链的后续节点
题目给出了 a[1]，根据哈希链的迭代关系：
- a[2]=myhash(a[1])a[2] = \text{myhash}(a[1])a[2]=myhash(a[1])
- a[3]=myhash(a[2])a[3] = \text{myhash}(a[2])a[3]=myhash(a[2])
我们可以直接计算出a[2]和a[3]。
步骤二：反推 a[0]
我们知道多项式方程：
secret≡a[0]+a[1]⋅a[1]+a[2]⋅a[1]2+a[3]⋅a[1]3(modP)secret \equiv a[0] + a[1] \cdot a[1] + a[2] \cdot a[1]^2 + a[3] \cdot a[1]^3 \pmod Psecret≡a[0]+a[1]⋅a[1]+a[2]⋅a[1]2+a[3]⋅a[1]3(modP)
现在除了 a[0]a[0]a[0] 以外，其他所有变量都已知。我们可以轻松反推 a[0]a[0]a[0]：
a[0]≡secret−a[1]2−a[2]⋅a[1]2−a[3]⋅a[1]3(modP)a[0] \equiv secret - a[1]^2 - a[2] \cdot a[1]^2 - a[3] \cdot a[1]^3 \pmod Pa[0]≡secret−a[1]2−a[2]⋅a[1]2−a[3]⋅a[1]3(modP)
步骤三：验证并逆向 myhash
计算出 a[0] 后，我们可以验证 myhash(a[0]) 是否等于已知的 a[1]。如果相等，说明我们的计算正确。
接下来是最关键的一步：从 a[0] 逆向还原出原始的 flag。
观察 myhash 的结构，它是 [数据块] + [CRC32校验值] 的拼接。
由于 CRC32 是确定性的校验算法，且输出为 4 字节，我们可以尝试解析 a[0] 的字节流：
- 尝试不同的前缀长度（0-7字节）。
- 提取前缀后的 4 字节，验证是否为该前缀的 CRC32 值。
- 如果匹配，继续以“8字节数据 + 4字节CRC32”的格式解析后续数据。
- 校验所有块的 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 到 7for prefix_len inrange(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# ==================== 函数定义 ====================defmyhash(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 inrange(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)-1return 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 inrange(8):iflen(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 =Truewhile 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 +=12else: valid =Falsebreakif valid and pos ==len(a0_bytes): flag_bytes =b''.join(blocks)breaktry:print(f"Flag: {flag_bytes.decode()}")except:print(f"Flag (hex): {flag_bytes.hex()}")六、运行结果
Flag: DASCTF{th1s_is_the_fe3st_quest1on} 七、总结
这道题虽然名为 easy_hash，但考察的知识点比较全面：
- 代码审计能力：理解自定义哈希函数和加密流程。
- 代数基础：利用模运算性质求解多项式方程中的未知数。
- 逆向思维：在无法直接求逆的情况下，利用哈希函数的结构特性（数据+校验）进行数据还原。
- CRC32特性：理解CRC32是校验码而非加密算法，可用于数据完整性验证和结构解析。
整体来说是一道质量很高的密码学题目，不仅考察了数学推导，还考验了对数据结构的分析能力。
