给 halois 赞助了一道题用于 SCTF2026，没想到变成了0解题

（文章有使用 Agent 来辅助生成部分内容，因此可能存在细微区别）

fault_hash

其实出题的时候考虑到现在 ai 发展这么迅猛，会不会被打烂，结果一个解也没，还是非常惊讶的。（不过听 halois 说给的提示词足够好的话 30 min 就可以秒了不知道真的假的）

题目

from md5 import md5
from os import urandom
from secret import flag

s = urandom(94)
leak = int(input('> '))
while seed := int(input('seed: ')): 
    print(f'h1 = {md5(s, int(seed))}\nh2 = {md5(s[:leak], int(seed))}')
    if seed == int.from_bytes(s):
        print(f'{flag = }')

其中 md5.py

from random import Random

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
MAX = 2**32


def byte_bin(msg):
    return "".join([bin(i)[2:].zfill(8) for i in msg])


def int_bin(a, l):
    return bin(a)[2:].zfill(l)


def int_bin_le(a, l):
    return "".join([bin(i)[2:].zfill(8) for i in a.to_bytes(l // 8, "little")])


def bin_int_le(a):
    byte_list = [a[i : i + 8] for i in range(0, len(a), 8)]
    return int("".join(reversed(byte_list)), 2)


def bin_hex(a, l):
    return hex(int(a, 2))[2:].zfill(l)


def int_left_shift(a, k, bit=32):
    return ((a << k) & 0xFFFFFFFF) | ((a & 0xFFFFFFFF) >> (bit - k))


def F(x, y, z):
    return (x & y) | ((x ^ 0xFFFFFFFF) & z)


def G(x, y, z):
    return (x & z) | (y & (z ^ 0xFFFFFFFF))


def H(x, y, z):
    return x ^ y ^ z


def I(x, y, z):
    return y ^ (x | (z ^ 0xFFFFFFFF))


def FF(a, b, c, d, Mi, s, tj):
    return (b + int_left_shift((a + F(b, c, d) + Mi + tj) & 0xFFFFFFFF, s)) & 0xFFFFFFFF


def GG(a, b, c, d, Mi, s, tj):
    return (b + int_left_shift((a + G(b, c, d) + Mi + tj) & 0xFFFFFFFF, s)) & 0xFFFFFFFF


def HH(a, b, c, d, Mi, s, tj):
    return (b + int_left_shift((a + H(b, c, d) + Mi + tj) & 0xFFFFFFFF, s)) & 0xFFFFFFFF


def II(a, b, c, d, Mi, s, tj):
    return (b + int_left_shift((a + I(b, c, d) + Mi + tj) & 0xFFFFFFFF, s)) & 0xFFFFFFFF

def pad(msg):
    l = len(msg)
    k = (448 - (l + 1) % 512) % 512
    return msg + "1" + k * "0" + int_bin_le(l, 64)


def cf(bi, A, B, C, D, seed):
    M = []
    for i in range(16):
        M.append(bin_int_le(bi[32 * i : 32 * i + 32]))
    a, b, c, d = A, B, C, D
    table = [
        ("a", FF, "a", "b", "c", "d", 0, 7, 0xD76AA478),
        ("d", FF, "d", "a", "b", "c", 1, 12, 0xE8C7B756),
        ("c", FF, "c", "d", "a", "b", 2, 17, 0x242070DB),
        ("b", FF, "b", "c", "d", "a", 3, 22, 0xC1BDCEEE),
        ("a", FF, "a", "b", "c", "d", 4, 7, 0xF57C0FAF),
        ("d", FF, "d", "a", "b", "c", 5, 12, 0x4787C62A),
        ("c", FF, "c", "d", "a", "b", 6, 17, 0xA8304613),
        ("b", FF, "b", "c", "d", "a", 7, 22, 0xFD469501),
        ("a", FF, "a", "b", "c", "d", 8, 7, 0x698098D8),
        ("d", FF, "d", "a", "b", "c", 9, 12, 0x8B44F7AF),
        ("c", FF, "c", "d", "a", "b", 10, 17, 0xFFFF5BB1),
        ("b", FF, "b", "c", "d", "a", 11, 22, 0x895CD7BE),
        ("a", FF, "a", "b", "c", "d", 12, 7, 0x6B901122),
        ("d", FF, "d", "a", "b", "c", 13, 12, 0xFD987193),
        ("c", FF, "c", "d", "a", "b", 14, 17, 0xA679438E),
        ("b", FF, "b", "c", "d", "a", 15, 22, 0x49B40821),
        ("a", GG, "a", "b", "c", "d", 1, 5, 0xF61E2562),
        ("d", GG, "d", "a", "b", "c", 6, 9, 0xC040B340),
        ("c", GG, "c", "d", "a", "b", 11, 14, 0x265E5A51),
        ("b", GG, "b", "c", "d", "a", 0, 20, 0xE9B6C7AA),
        ("a", GG, "a", "b", "c", "d", 5, 5, 0xD62F105D),
        ("d", GG, "d", "a", "b", "c", 10, 9, 0x02441453),
        ("c", GG, "c", "d", "a", "b", 15, 14, 0xD8A1E681),
        ("b", GG, "b", "c", "d", "a", 4, 20, 0xE7D3FBC8),
        ("a", GG, "a", "b", "c", "d", 9, 5, 0x21E1CDE6),
        ("d", GG, "d", "a", "b", "c", 14, 9, 0xC33707D6),
        ("c", GG, "c", "d", "a", "b", 3, 14, 0xF4D50D87),
        ("b", GG, "b", "c", "d", "a", 8, 20, 0x455A14ED),
        ("a", GG, "a", "b", "c", "d", 13, 5, 0xA9E3E905),
        ("d", GG, "d", "a", "b", "c", 2, 9, 0xFCEFA3F8),
        ("c", GG, "c", "d", "a", "b", 7, 14, 0x676F02D9),
        ("b", GG, "b", "c", "d", "a", 12, 20, 0x8D2A4C8A),
        ("a", HH, "a", "b", "c", "d", 5, 4, 0xFFFA3942),
        ("d", HH, "d", "a", "b", "c", 8, 11, 0x8771F681),
        ("c", HH, "c", "d", "a", "b", 11, 16, 0x6D9D6122),
        ("b", HH, "b", "c", "d", "a", 14, 23, 0xFDE5380C),
        ("a", HH, "a", "b", "c", "d", 1, 4, 0xA4BEEA44),
        ("d", HH, "d", "a", "b", "c", 4, 11, 0x4BDECFA9),
        ("c", HH, "c", "d", "a", "b", 7, 16, 0xF6BB4B60),
        ("b", HH, "b", "c", "d", "a", 10, 23, 0xBEBFBC70),
        ("a", HH, "a", "b", "c", "d", 13, 4, 0x289B7EC6),
        ("d", HH, "d", "a", "b", "c", 0, 11, 0xEAA127FA),
        ("c", HH, "c", "d", "a", "b", 3, 16, 0xD4EF3085),
        ("b", HH, "b", "c", "d", "a", 6, 23, 0x04881D05),
        ("a", HH, "a", "b", "c", "d", 9, 4, 0xD9D4D039),
        ("d", HH, "d", "a", "b", "c", 12, 11, 0xE6DB99E5),
        ("c", HH, "c", "d", "a", "b", 15, 16, 0x1FA27CF8),
        ("b", HH, "b", "c", "d", "a", 2, 23, 0xC4AC5665),
        ("a", II, "a", "b", "c", "d", 0, 6, 0xF4292244),
        ("d", II, "d", "a", "b", "c", 7, 10, 0x432AFF97),
        ("c", II, "c", "d", "a", "b", 14, 15, 0xAB9423A7),
        ("b", II, "b", "c", "d", "a", 5, 21, 0xFC93A039),
        ("a", II, "a", "b", "c", "d", 12, 6, 0x655B59C3),
        ("d", II, "d", "a", "b", "c", 3, 10, 0x8F0CCC92),
        ("c", II, "c", "d", "a", "b", 10, 15, 0xFFEFF47D),
        ("b", II, "b", "c", "d", "a", 1, 21, 0x85845DD1),
        ("a", II, "a", "b", "c", "d", 8, 6, 0x6FA87E4F),
        ("d", II, "d", "a", "b", "c", 15, 10, 0xFE2CE6E0),
        ("c", II, "c", "d", "a", "b", 6, 15, 0xA3014314),
        ("b", II, "b", "c", "d", "a", 13, 21, 0x4E0811A1),
        ("a", II, "a", "b", "c", "d", 4, 6, 0xF7537E82),
        ("d", II, "d", "a", "b", "c", 11, 10, 0xBD3AF235),
        ("c", II, "c", "d", "a", "b", 2, 15, 0x2AD7D2BB),
        ("b", II, "b", "c", "d", "a", 9, 21, 0xEB86D391),
    ]
    Random(seed).shuffle(table)
    state = {"a": a, "b": b, "c": c, "d": d}
    for target, func, x, y, z, w, mi, s, tj in table:
        state[target] = func(state[x], state[y], state[z], state[w], M[mi], s, tj)
    a, b, c, d = state["a"], state["b"], state["c"], state["d"]
    A, B, C, D = (A + a) % MAX, (B + b) % MAX, (C + c) % MAX, (D + d) % MAX
    return A, B, C, D


def round(msg, seed):
    a = A
    b = B
    c = C
    d = D
    n = len(msg) // 512
    bi = []
    for i in range(n):
        bi.append(msg[512 * i : 512 * i + 512])
    for i in bi:
        a, b, c, d = cf(i, a, b, c, d, seed)
    return int_bin_le(a, 32) + int_bin_le(b, 32) + int_bin_le(c, 32) + int_bin_le(d, 32)


def md5(msg, seed=None):
    bin_msg = byte_bin(msg)
    pad_msg = pad(bin_msg)
    c = round(pad_msg, seed)
    return bin_hex(c, 32)

md5

想要解决这个题目，首先肯定要了解一下 md5 的结构。

MD5 处理消息时会先 padding。假设原消息长度是 $l$ bit，padding 之后长度会变成 $512$ 的倍数，并且最后 $64$ bit 存原消息长度：

$$msg\ \Vert\ 1\ \Vert\ 0^k\ \Vert\ l$$

然后消息会被切成若干个 $512$ bit 的 block。每个 block 又会被拆成 16 个 32-bit word：

$$M[0],M[1],\ldots,M[15]$$

MD5 内部有 4 个 32-bit state：

$$(a,b,c,d)$$

初始值是固定的：

$$\begin{aligned} A &= 0x67452301 \\ B &= 0xefcdab89 \\ C &= 0x98badcfe \\ D &= 0x10325476 \end{aligned}$$

每个 block 会执行 64 个 step。一个 step 大概长这样：

$$b = c + \operatorname{rol}(b + f(c,d,a) + M[i] + T, r)$$

这里 $f$ 是 MD5 的四种布尔函数之一，$M_i$ 是当前 step 用到的消息 word，$T$ 和 $r$ 是常数。注意这个形式很重要：一个 step 只会更新一个寄存器，其它三个寄存器在这一行里只是作为输入。

回到题目，其就是魔改了 md5 的 step 都存进了一个 table，然后在查询之前利用 seed 进行打乱。

如果只看 md5(s, seed)，它像是一个普通的 hash oracle。但结合上面的 MD5 结构就会发现：只要能控制这 64 行 step 的顺序，就能让某些寄存器先动、某些寄存器后动，从而设计出局部方程。

所以这题真正要打的不是 MD5 的碰撞，而是：

如何把 seed 变成 64 个 step 的可以相对于我们好利用的排列控制器？

shuffle

本质就是 MT19937 如何恢复 seed，这个网上文章也很多了，主要是看其如何调用的随机数代码：

for i = 63 ... 1:
    j = randbelow(i + 1)
    swap(i, j)

其中 randbelow 来自 getrandbits(k)，其实细节知不知道似乎也没啥区别，丢 ai 就好了 XD

拿到 seed 以后我们就解决了第一步，就是可以自己控制 step 的排列。

单块原像恢复

回到题目，我们发现 s 是 94 bytes 的也就是两块，而两块相比于一块的情况要较为复杂，再加上我们可以自己输入 leak 来获取 s 前面几 bytes 的情况。因此可以考虑先研究 1 块的情况。

考虑到为了最大限度的获得信息，我们取 leak = 55，所以题目第一步就变成了如何恢复单块原像恢复。（leak 大于 55 会因为padding 出现两块）

对其进行 padding 以后 $M$ 的结构为：

$$\begin{aligned} M[0\ldots12] &= s[0:52] \\ M[13] &= s[52:55]\ \Vert\ 0x80 \\ M[14] &= 55 \times 8 \\ M[15] &= 0 \end{aligned}$$

可以发现其实我们需要恢复的只有 $M[0]...M[13]$，然后其中 $M[15]=0$ 是一个非常有用的 word。

回到前面我们讲的 step 的式子：

$$b = c + \operatorname{rol}(b + f(c,d,a) + M[i] + T, r)$$

而且一个 step 只会更新一个寄存器，也就是只会改变 $b$，但是 $a,c,d$ 是不动的。

然后又可以注意到对于每一个 $M[i]$ 都存在一个 step 只改变其的 $b$，因此我们如果构造这么两个排列：

$$\begin{aligned} P_1 &= R \Vert U \Vert K \\ P_2 &= R \Vert K \Vert U \end{aligned}$$

其中 $U$ 是使用 $M[i]$ 的那个更新 $b$ 的 step， $K$ 是使用 $M[15]=0$ 的那个更新 $b$ 的 step，$R$ 是剩余 62 个的随机排列。

执行完 $R$ 后，内部状态设为：

$$(a, b_0, c, d)$$

接下来 $U$ 和 $K$ 都只更新 $b$，所以无论顺序是 $U,K$ 还是 $K,U$，最后输出里的 $a,c,d$ 都应该一样。考虑把两边的 $b$ 回代消掉中间状态可以得到类似：

$$\operatorname{rol}(x,22)-x \equiv e \pmod {2^{32}}$$

的方程，通过解方程可以得到 $M[i]$ 或者少量的候选，不过这个可以换不同的 $R$ 来取交集解决。最后循环多次即可拿到所有的 $M[0]...M[13]$ 从而恢复 $s[:55]$。

恢复 $s$ 第一块

然后注意到 $s$ 的第一块是 64 bytes，因此我们还需要恢复剩下的 9 bytes。

很显然这部分肯定是无法通过 h2 直接解决，需要使用 h1。

构造 witness

观察题目里的 MD5 压缩函数，每个 step 只会更新 a,b,c,d 中的一个寄存器。因此我们可以固定某个 target，例如 b，只在更新 b 的 16 个 step 内做局部换序。

选两个 step：

$$row_i,\ row_j$$

要求它们满足：

• target 相同
• 使用的布尔函数相同
• rotation 相同

然后在中间插入若干个同 target 的 step，构造两种短序列：

$$left = row_i \Vert middle \Vert row_j$$

$$right = row_j \Vert middle \Vert row_i$$

也就是说，left 和 right 只交换了两端两个 step 的顺序。

将这个短序列嵌入到该 target 对应的 16 个 step 中，其它 target 的 step 保持一致。然后分别查询服务得到两次 h1。

如果两次结果中非 target 的三个 digest word 完全相同，就说明这个局部换序对真实消息块形成了一个有效约束。这样的约束记为一个 positive witness。

例如 target 为 b 时，检查：

$$a_{left}=a_{right},\quad c_{left}=c_{right},\quad d_{left}=d_{right}a_{left}=a_{right},\quad c_{left}=c_{right},\quad d_{left}=d_{right}$$

如果成立，则保留该 witness。

用 witness 检查候选

对于任意候选的第一块：

$$M_0' = s[:55] \Vert guess_9$$

我们在本地模拟这组 witness。若该候选正确，则对应的局部换序应满足：

$$target(left) = target(right)$$

如果不相等，就用两者差异的 bit 数作为代价：

$$cost = \operatorname{popcount}(target(left)\oplus target(right))$$

对所有 witness 求和：

$$score(M_0') = \sum cost_i$$

正确的第一块应该满足：

$$score(M_0)=0$$

因此恢复 s[55:64] 就变成了一个 9 字节的小搜索问题：寻找一个 guess_9，使得所有 witness 的总代价为 0。

实际做的时候可以先收一批正 witness，然后做小种群搜索和坐标修正。为了防止 witness 太少导致假解，找到 score = 0 后，再额外收一批 holdout witness 验证一下。（很显然这种玩意丢给 ai 就完事了，自己写是不可能的）

然后由此我们可以完整恢复出来了 $s$ 的第一块。

恢复 $s$ 第二块

第一块知道以后，就可以把两块问题拆开。

对于任意排列 P，第一块压缩后的链值可以本地算：

$$C_1(P)=compress(M_0, IV, P)$$

服务端给的 h1(P) 是两块都压完之后的结果，所以可以扣掉第一块：

$$S_2(P)=h_1(P)-C_1(P)\pmod {2^{32}}$$

这样题目就变成了 已知初始链值，如何恢复第二块。

第二块格式也很固定：

$$\begin{aligned} M_1[0\ldots6] &= s[64:92] \\ M_1[7] &= s[92:94]\ \Vert\ 0x80\ \Vert\ 0x00 \\ M_1[8\ldots13] &= 0 \\ M_1[14] &= 94 \times 8 \\ M_1[15] &= 0 \end{aligned}$$

所以未知量就是 7 个完整 word，加上 M1[7] 的低 16 bit。

单 word 过滤

接下来我们先不急着直接恢复全部的 $M_1$，而是先对每一个未知 word 单独做过滤。

对于某个未知的 $M_1[i]$，可以找一个和它同 residue 的已知 padding word 作为参照：

$$K = M_1[8 + (i \bmod 4)]$$

这里 $M_1[8],M_1[9],M_1[10],M_1[11]$ 都是 $0$，所以它们是已知的。

为什么要找同 residue 的 word？因为在 MD5 的 step 表里面，$M[i]$ 和 $M[i+8]$ 会出现在同 target、同函数、同 rotation 的位置上。比如 $M_1[0]$ 和 $M_1[8]$ 都能找到形如：

$$target = b,\quad func = G,\quad rot = 20$$

的 step。这样我们就可以构造一个只和当前未知 word 有关的局部换序。

设：

• $U$ 是使用未知 $M_1[i]$ 的 step
• $K$ 是使用已知 padding word 的 step

构造两个局部 gadget：

$$\begin{aligned} left &= U \Vert middle \Vert K \\ right &= K \Vert middle \Vert U \end{aligned}$$

这里的 middle 只选同 target 且消息 word 已知的 step，或者干脆为空。这样在检查某个候选值 $v$ 的时候，整个局部 gadget 里面唯一的未知量就是 $v$。

完整排列可以写成：

$$\begin{aligned} P_L &= R \Vert left \\ P_R &= R \Vert right \end{aligned}$$

也就是把这个局部 gadget 放在最后。因为最后几行都只更新同一个 target，所以其它三个寄存器在 gadget 执行期间不会变，并且它们的值可以直接从最终输出里读出来。

不过这里有一个两块消息带来的问题：同一组排列会同时作用在第一块和第二块上。如果 $P_L$ 和 $P_R$ 压完第一块以后的链值不同，那么第二块的初始状态也不同，后面就不能把左右两边放在一起比较。

所以我们先在本地筛 witness，要求：

$$compress(M_0, IV, P_L)=compress(M_0, IV, P_R)$$

只有满足这个条件的排列对，才拿去查询服务端。这样进入第二块时，左右两边的初始链值是一样的；又因为前缀 $R$ 完全相同，所以进入最后局部 gadget 前的状态也一样。

现在考虑如何检查候选值 $v$。一个 target step 可以写成：

$$x'=y+\operatorname{rol}(x+f(y,z,w)+M+T,r)$$

于是可以反过来：

$$x=\operatorname{ror}(x'-y,r)-f(y,z,w)-M-T$$

对于服务端返回的 $h_1(P_L)$ 和 $h_1(P_R)$，我们先扣掉第一块链值，拿到第二块最后的裸状态 $S_2(P_L),S_2(P_R)$。然后从左右两边的 target 输出开始，把最后的 gadget 逆回去。

如果 $v$ 是正确的，那么左右两边应该逆回同一个局部入口：

$$entry_L(v)=entry_R(v)$$

否则这个 $v$ 就可以丢掉。

实际实现时不会直接扫完整的 $2^{32}$。第一组 witness 可以用来生成候选：因为 $U$ 和 $K$ 被选成同 target、同函数、同 rotation，入口相等的条件最后会化成只含 $v$ 的 rotation 方程，和前面恢复 $s[:55]$ 时类似，只需要枚举少量低位分支即可得到一小批候选。后续再换不同的 witness，不断取交集即可。

对于 $M_1[7]$，它的格式是：

$$M_1[7] = s[92:94]\ \Vert\ 0x80\ \Vert\ 0x00$$

也就是小端意义下：

$$M_1[7] = 0x00800000 + x$$

其中 $x$ 只有低 $16$ bit 未知，所以这一项甚至可以直接枚举 $2^{16}$ 个值，再用上面的 witness 过滤。

经过这个步骤后，每个未知 word 都会得到一个较小的候选集合：

$$\begin{aligned} Cand_0,\ Cand_1,\ \ldots,\ Cand_7 \end{aligned}$$

其中 $Cand_7$ 里的值都已经满足 padding 的高 $16$ bit。

MITM 合并

单 word 过滤只能说明“每个 word 单独看起来可能对”，但这些候选之间不一定能组合成同一个真实第二块。因此最后还需要把这些候选合并。

这里继续利用 step 只更新一个寄存器的性质。

如果我们把某个 target 的 16 个 step 放在整个排列最前面，那么这 16 行执行完以后，后面的 48 行都不会再修改这个 target。因此最终 digest 里这个 target 的裸输出，只依赖：

• 第二块进入时的链值；
• 这个 target 对应的 16 个 step；
• 这些 step 用到的消息 word。

第一块 $M_0$ 已经知道，所以对于任意排列 $P$，第二块入口链值：

$$C_1(P)=compress(M_0,IV,P)$$

可以本地算出来。服务端返回的 $h_1(P)$ 扣掉 $C_1(P)$ 后，也能得到第二块执行完后的裸状态。于是我们可以对某个 target 单独做 meet-in-the-middle。

比如 target 为 $a$ 时，涉及的未知 word 只有：

$$M_1[0],\ M_1[1],\ M_1[4],\ M_1[5]$$

其它 $a$ 的 step 用到的都是 padding word，已经已知。

我们控制 $a$ 的 16 行顺序，把它拆成两段：

$$a\_rows = L\_rows \Vert R\_rows$$

其中 $L\_rows$ 主要放使用 $M_1[0],M_1[1]$ 的 step，$R\_rows$ 主要放使用 $M_1[4],M_1[5]$ 的 step，中间可以穿插已知 padding step。

然后做 MITM：

1. 枚举 $(M_1[0],M_1[1])\in Cand_0\times Cand_1$，从入口 $a_0=C_1(P)_a$ 正向执行 $L\_rows$，得到中间值 $mid$，存入哈希表；
2. 枚举 $(M_1[4],M_1[5])\in Cand_4\times Cand_5$，从最终 $a_{out}=S_2(P)_a$ 反向执行 $R\_rows$，也得到一个 $mid$；
3. 如果两个 $mid$ 相同，就保留这组四个 word 的组合。

这样就不用枚举四个 word 的完整笛卡尔积，而是拆成了左右两边各两个 word。

同理，target 为 $c$ 时，涉及的未知 word 是：

$$M_1[2],\ M_1[3],\ M_1[6],\ M_1[7]$$

于是再做一次 MITM，就可以得到剩下四个 word 的组合。

这两组刚好覆盖第二块的全部未知量：

$$\begin{aligned} a\text{-group} &: M_1[0],M_1[1],M_1[4],M_1[5] \\ c\text{-group} &: M_1[2],M_1[3],M_1[6],M_1[7] \end{aligned}$$

如果一次 MITM 后还有多个组合，就换一组 target 行顺序重新收一个 witness 再过滤。一般一两组之后就能唯一。

最后得到完整的第二块：

$$\begin{aligned} M_1[0\ldots6] &= s[64:92] \\ M_1[7] &= s[92:94]\ \Vert\ 0x80\ \Vert\ 0x00 \end{aligned}$$

所以取数据部分即可：

$$s[64:94] = M_1[0]\Vert M_1[1]\Vert\cdots\Vert M_1[6]\Vert M_1[7][0:2]$$

最终：

$$s = M_0 \Vert s[64:94]$$

拿到完整的 $94$ bytes 之后，提交即可得到 flag。