CryptoCTF 2025 tough cookie 分类 团队解题 writeup 之一
这次 tough cookie 分类没有全部做出来，有一道题卡住了，想到了可能的解法，但是没有去实践
实际上就是事后诸葛亮
Asemoon
题目描述
题目基于 $GF(2^{64})$ 中的运算，首先生成了一个模多项式 $g$ 保证 $g$ 不可约，然后代码中的 CP 是 $g$ 的 反向二进制 表示，即，如果 $g(x) = x^{64} + \sum_{i=0}^{63} a_i x^i$，则 $CP = \sum_{i=0}^{63} a_i 2^{63-i}$
然后是 CT 的计算，遍历 $b = 0, 1, \ldots, 255$，代码中的位运算也要 反着看 才会比较符合“多项式取模”的运算：
if cb & 1: 也就是如果 $b$ 对应的多项式高位是 $x^{63}$cb = (cb >> 1) ^^ CP: $b$ 对应的多项式乘以 $x$，再模 $g(x)$cb >>= 1: 否则 $b$ 对应的多项式乘以 $x$，因为乘完之后的多项式高位不是 $x^{64}$，所以没必要模 $g(x)$
所以对应的多项式也要反着看，譬如
- $b=1$ 对应的多项式是 $f(x) = x^{63}$
- $b=2$ 对应的多项式是 $f(x) = x^{62}$
- $b=5$ 对应的多项式是 $f(x) = x^{63} + x^{61}$
然后算出来的 CT 就是 $x^8 f(x) \bmod g(x)$
题目生成一个随机的 64 位数 $s$，并提供 2 个运算：
recheck 一个根据 CT 进行迭代运算的“哈希函数”，接受一个消息 $m$ 和一个初始值 $v$，用以下代码计算
把上面的操作转换为 $GF(2^{64})$ 上的多项式运算，就是
消息的分量 $m_i$ 对应多项式的法则和上面相同，也是把 $1$ 映射到 $x^{63}$，把 $5$ 映射到 $x^{63} + x^{61}$……
第二行的转换比较好理解，第三行的转换可以把右移 8 位看成是把至多位 $x^{55}$ 的乘上 $x^8$，CT 的代换则是把 $x^{56}$ 到 $x^{63}$ 的部分先乘了个 $x^8$，再模多项式 $g(x)$（注意 CT 的定义），所以把两部分合起来就是在乘一个 $x^8$
举个例子，如果消息是 CNM，那么
C对应 67，01000011，对应多项式 $x^{63} + x^{62} + x^{57}$N对应 78，01001110，对应多项式 $x^{62} + x^{61} + x^{60} + x^{57}$M对应 77，01001101，对应多项式 $x^{63} + x^{61} + x^{60} + x^{57}$
所以 recheck(CNM, 0) 迭代到最后的多项式是
也就是
然后加上常数项，recheck(CNM, v) 迭代到最后，还要加个常数项 $x^{24} v(x)$
verify 输入初始值 $v$ 和当前时间戳 $t$，验证 recheck(s xor t, v) 是否等于 $v$。由之前对 但是 $s$ 是生成的随机未知数，$t$ 是当前时间戳，由此可见上句话在说个 JB。recheck 的分析容易知道当 $t = s$ 的时候，上式恒成立。
然后题目给出了两个交互选项：
检验 token 输入 $v$ 使得 verify 通过。若能通过，则给 flag
获取信息 返回以下值：
recheck('CCTF', recheck(s xor t, 0))- 一个随机 64 位素数 $r$
- $5^{CP} \bmod r$
试获取 flag
我的解答
首先是获取 $CP$。因为 $r$ 是 64 位素数，所以离散对数是可以直接求出来的。而且因为可以多次获取信息，还可以只挑那些光滑的来解离散对数。
然后是通过上面的两个 recheck 嵌套获取 $s \oplus t$ 的值。
由上面对 recheck 函数的分析，实际上就是减去（加上，反正这两运算在 $GF(2^{64})$ 里面一个意思） CCTF 对应的多项式即可
然后是通过上面的 recheck 检测，由上面的分析等价于解一个方程：
所以就是直接解就行了：
因为 $t$ 是 10 秒一变的时间戳，我们这里没有啥耗时的操作，所以就当作是定值，懒得调了。（要是在代码运行的过程中 $t$ 变了那就证明比较倒霉）。然后就是实现和 debug 了：
1 | from pwn import * |
然后在题目的 gen_CP 中，有可能 $c$ 的高位不为 0，转换会失败。不过这个概率比较小，碰上了就再来一次就行了。flag 为：
1 | CCTF{CRC_0v3R_quO7i3nT_r!n9S} |
Goliver II (x)
题目描述
题目给了一个特殊版本的 ECDSA。记已知曲线为 $E_p$，并已知生成元 $G$。每次连接的时候生成一个私钥 $x$，并且算出对应的、可获取的公钥 $P = xG$。签名过程均对 flag 的前半 $t$ 签名，过程如下：
- 输入一个 ID $k$
- 算出消息的哈希 $h = H(x_h)$
- 算出 $Q = (t+k)G$
- 记 $r = x_Q$
- 记 $s = (t + k)^{-1} (h + r x) \bmod n$
- 服务器仅给出 $s$ 的值
每次连接服务器可以执行至多 3 次的签名，且单次连接中，$k$ 的选择不能重复。
若能在某次连接时，把对应私钥 $x$ 给求出来，那么就能得到 flag。
我们的尝试
因为 $t$ 为 flag 的前半部分，为定值，不难想到多次连接时可能能利用这个不变量做一些文章。
重新写一下问题形式：记执行签名次数为 $j = 1, 2, 3$，记服务器连接次数为 $i = 1, 2, 3, \ldots$。因为服务器仅给出 $s$ 的值，所以只能依赖式子
这里主要难搞的有两点
- $r^{(i)}_j$ 未知
- $h$ 未知
但是由 $r$ 的计算过程，可以把 $r$ 定死在某些变量里面：
令 $k = n, 2 n, 3n$，则 $r$ 的值相同，由上面那个式子，会发现 $s_j{i}$ 也相同，也就是说没有通过 3 次输入，获取到任何有价值的信息。
令 $k = k_0, n - 2 t - k_0$，这样算出的 $Q$ 恰好一个是 $Q$，一个是 $-Q$。它们的横坐标相等，所以可以获得相同的 $r$，可以消掉一个变量。但是因为 $t$ 未知，所以没法操作。
- 因为 $t$ 是 flag 的前半段，所以 赌 flag 较短，也就是可以通过枚举
CCTF{xxx来确定 $t$ 的值。如果这样的话，$h$ 的值相当于也有了。则有： - $(t+k_0) s_1 \equiv h + r x \pmod{n}$
- $-(t+k_0) s_2 \equiv h + r x \pmod{n}$
- 也就是要检查两式的左边是否相等；如果相等，则 flag 前半段 $t$ 值直接被猜出
- 很遗憾，对不上，寄
- 因为 $t$ 是 flag 的前半段，所以 赌 flag 较短，也就是可以通过枚举
令 $k = -1, 0, 1$，则 3 次交互的 $r$ 分别为 $x_{(k-1)G}, x_{kG}, x_{(k+1)G}$。当然这里有一个问题：题目会检验 $k>0$ 要满足，但是没有检验其他的，所以实际输入的时候可以改为 $k = n-1, n, n+1$，则题目式子可以被写成
- $(t + k_j) s_j^{(i)} \equiv h + r_j x^{(i)} \pmod{n}$
如果我们一共有 $N$ 次连接，那么一共 $3N$ 次交互就有 $3N$ 个式子，但是未知量仅有 $t, h, r_j, x^{(i)}$，数量仅有 $5 + N$ 个，所以是管够的。
然后 沛公 就做了一版尝试：
1 | from goliver_ii import * |
结果打印出来的多项式都不太行。
赛后复盘
赛后发现，其实就该这样做，不过当时没有继续细想，所以就放弃了。
其实感觉和去年那道 Rehawk 一样，在碰到多元多次方程的时候，没搞懂自己到底要什么东西。其实这里最关键的就是 $t$
所以就不管其他那些乱七八糟的东西，直接上 groebner basis 就行了，然后就会发现 grobner basis 里面分别有关于 $h$ 和 关于 $t$ 的一元一次多项式，直接解就行了，然后稍微检查一下解的前缀满足 CCTF{ 格式。
如果 $t$ 和 $h$ 的值已经求出来了，相当于 $t+k$ 也知道，$r$ 也知道，相当于可以直接解出 $x$ 了。代码如下：
1 | from pwn import * |
真滴可惜，我他妈比赛的时候也不知道干啥去了，也没有拿着沛公的代码多调两下
然后就是，不知道为什么自己手搓的通过 sylvester_matrix 再求行列式的土味 resultant 不能解出 $t$ 来，麻
Juliax
题目描述
题目基于 CRT-RSA，$p$, $q$ 均为 512 bit，$e$ 为 72 bit，有 $d_p$ 和 $d_q$ 的低 199 位泄露，其中
已知 $N = pq$，$e$，$c = m^e \bmod{N}$，求 $m$。
我的解答
想到 CRT-RSA，就想到了之前 0CTF 有过的一道 ezRSA++，直接把 idek 的 脚本 抄来跑了，不过要改一些地方
- 各未知量的界（$p, k, l$）
- 参考 论文 的 Table 1，当 $\beta=0.5$ 的时候，$\sigma$ 为 1
- 额外需要测试规约后可用的多项式个数
改好了之后如下：
1 | m = 3 |
然后发现只能解出 $k$ 和 $l$ 来，不能解出 $p$。这个时候 V 给了另一个代码：
1 | """ |
然后就解出了 $d_p$ 高位。然后直接模 $p$ 下解密即可（为什么不模 $N$？因为我懒）
1 | from Crypto.Util.number import * |
得到 flag 为
1 | CCTF{f4c70r1ng_w!7h_0nlY_a_thIrD_0F_7H3_53creT_CR7-3xp0n3n75!} |
赛后复盘
实际上 V 给的这个代码就是在利用下面这个等式
同时要先把上面的式子模 $k$ 分析，得到 $d_{ph} \bmod k$ 的值：
再把等式去做模 $N$ 的 coppersmith，把未知的 $p$ 当作 $N$ 给模掉就行了（可以算一下界，利用完上面的模 $k$ 分析后，未知数的位数仅为 $512 - 199 - 72 = 241$ 位，大概是 $N^{1/4}$ 这个级别的）：
1 | xq = 4198425198326169691466 |
然后比赛的时候还试了直接用 cuso 去解，好像解不出来
flag 提到的内容应该是 A Third is All You Need: Extended Partial Key
Exposure Attack on CRT-RSA with Additive
Exponent Blinding，也是一篇蛮经典的 论文
Expulsion is All You Need
Lowdown
题目描述
记 $\mathbb{F} = GF(2^8), k=10$
密钥生成 随机生成矩阵 $G \in \mathbb{F}^{k \times k}$，以及 $2 < r, a < 2^{192}$。计算 $A = G^{ar}$。公钥为 $(G, A)$，私钥为 $r$
签名 输入一个长度小于 10 的消息 $m$
- 算出其 SHA1 哈希 $h = H(m)$
- 计算 $G_2 = G^r$
- 生成随机数 $2 < n < 2^{192}$
- 计算 $S = A G_2^{-n h}$
- 计算 $T = G_2^n$
- 服务器返回 $(S, T)$
验签 输入消息 $m$，以及待验证签名 $(S, T)$
- 算出其 SHA1 哈希 $h = H(m)$
- 验证 $S T^{h} = A$ 是否成立
挑战 服务器给一个长度为 40 的随机消息，需要给签名 $(S, T)$ 使得
- 签名通过
- $S$ 转成整数表示要以
13开头 - $T$ 转成整数表示要以
37开头
通过挑战即给 flag
我的解答
看到矩阵乘法运算和幂运算容易想到 特征分解，但是好像用不着
本地试了一下，$G$ 的阶能求出来，也就是离散对数能求。但是直接调用 sagemath 的官方 API 貌似不能直接求，因为没实现矩阵类的 __hash__ 方法，那就手撕一下 Pohlig-Hellman 得了。
然后假设我们已经知道 $A = G^k$，那么要构造满足条件的 $S, T$ 就很简单：
- 随机满足限制的 $T$ 矩阵
- 计算 $S = A T^{-h}$
- 验证 $S$ 矩阵是否满足限制，这个概率应该是 $1/256$
然后分析一下他的那个限制，他是用 startswith 来限制的，实际上就是限制整数的范围，也就是限制 $S_{00}, T_{00}$ 就能满足。估算一下，$S$ 转成整数的话大概是 $2^{8 \times 10 \times 10}=2^{800} \approx 10^{240}$ 这个量级，应该能估算出个 $S_{00}, T_{00}$ 限制的范围，或者用下面的代码来做个简单 check：
1 | for i in range(256): |
然后发现
- 当
i = 50, 51, 52的时候，满足整数首位为13的限制 - 当
i = 143, 144的时候，满足整数首位为37的限制
这样的话，实际上上面所说的离散对数也不用求了，整个就一乱搞，代码如下：
1 | from pwn import * |
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment