CryptoCTF 2025 brain buster 分类团队解题 writeup

这次 brain buster 分类由于人力短缺，有一题没有做出来。这里不得不说一句，1997 的各位真是尽力了，本来已经有其他日程安排的石卡库和托林都尽力拿时间出来做题。反观某个叛徒，在 1997 人手短缺的时候临阵叛逃，完全就是负贡献，如此行为，令人汗颜！

Leptocole (x)

题目描述

令 $q = 127, n = 26, k = 14$，题目中讨论的矩阵元素均在 $\mathbb{F} = GF(q)$ 中。

服务器先生成一个随机的矩阵 $G \in \mathbb{F}^{k \times n}$，以及一个随机的 $n \times n$ 排列矩阵 $Q$，该排列矩阵中的每行和每列恰好有一个随机非零元素。$H$ 是 $GQ$ 的最简行阶梯形式。$G$ 和 $H$ 已知。

我们需要给出矩阵 $U$ 和 $P$，使得：

$P$ 也满足上述对排列矩阵的定义
$U$ 和 $P$ 均可逆
$U G P = H$

若能给出这样的两个矩阵，那么就能拿到 flag。

我的尝试

因为时间问题，在比赛的时候，我只是简单地做了一些尝试，并没有深入研究。这题比赛的时候是套娃看的，虽然他没做出来，但是他也贡献出了自己的一份力量。

反观某个叛徒，因为被人唆使而临阵叛逃，造成 1997 的人力短缺！

赛后复盘 (x)

首先，最简行阶梯形式的变换可以写成一系列初等矩阵的乘积。如果我们把这个乘积记成 $R$ 的话，那么式子也就是可以写成

$H = R G Q$

也就是说，如果直接令 $U = R$，$P = Q$ 的话，就可以解出来了。

然后由于 $H \in \mathbb{F}^{k \times n}$，所以 $U \in \mathbb{F}^{k \times k}$，$P \in \mathbb{F}^{n \times n}$。

重排并放缩 $G$ 矩阵的列，使得其行向量均在 $H$ 的行空间中，且 $H$ 矩阵的可以写成分块矩阵的形式：

$H = \begin{bmatrix}I & H_1\end{bmatrix}$

如果我们将 $GQ$ 也写成分块矩阵的形式：

$T := GQ = \begin{bmatrix}T_1 & T_2\end{bmatrix}$

如果我们能保证列重排之后， $T_1$ 是正确的，那么其最简行变换之后的矩阵为

$H' = R' T = \begin{bmatrix}I & R' T_2\end{bmatrix}$

实在没招了

maple3142 的启发 (TODO)

我當初也沒解出這題
不過好像是找 paper 的題目
https://github.com/juliannowakowski/lep-cf

Multi Shooti

题目描述

题目基于一个块加密的系统。

题目有 8 个密钥 $k_i, i=0, 1, \ldots, 7$，以及有一个初始向量 $v$。

对于每个密钥，都有一个对应的块加密的系统 $E_{i} = E_{k_i, v}$。加密时，该系统内部是根据密钥 $k_i$ 和初始向量 $v$ 生成一系列流密钥，并让流密钥和明文对应位置异或。

对于整个块加密系统，对消息 $m$ 的加密则是依次用每个分系统进行加密：

$E(m) = E_7(\ldots(E_1(E_0(m)))\ldots)$

我们有已知特定 17 字节长消息 $m_0$，对该消息用该加密系统加密成已知 $c_0$。需要提供另一组密钥 $k’_i$，以及根据该组密钥对应的块加密系统 $E’$（初始向量仍然是 $v$），使得 $E’(c_0) = m_0$。如果能构造出这样一组密钥 $k’_i$，那么就能得到 flag。

我的解答

首先注意到加密的方式是异或，而且每次都是新初始化加密系统的实例。所以只要密钥固定，流密钥也就固定，两次加密就变成解密了。

其次也是流密钥的性质：上面公式里面嵌套加密的形式换成流密钥就是依次异或所有的流密钥，也就是密钥 $k_i$ 的 顺序芜锁胃。为了方便下面表述，我们记密钥 $k_i$ 对应的块加密系统为 $E_i$，所生成的流密钥是 $s_i$。这样，加密过程也可以被写为：

$E(m) = m \oplus s_0 \oplus s_1 \oplus \ldots \oplus s_7$

根据上面两点，在比赛的时候，我首先想的是如果 $k_i’ = k_i, i = 0, 1, \ldots, 7$，那么检验式肯定满足。于是我就想着能否用 z3-solver 之类的去把加密系统给参数化，然后去解密钥，结果是不行地。

然后就是代码审计这一块了：要敏锐地察觉到 服务器对我们输入的另一组密钥 $k’_i$ 的个数是没有限制的！ 也就是说，我们理论上可以输入很多组密钥 $k’_i$，它也会按照顺序去计算加密过程。假设我们输入 $t$ 组密钥，服务器就会计算

$E'(c_0) = E'_{t-1}(\ldots(E'_1(E'_0(c_0)))\ldots)$

也就是说，我们可以调大密钥组数 $t$，来增加构造成功的可能性。

还是代码审计：在审计加密系统 $E_i$ 的实现的时候，我 tmd 居然发现初始向量 $v$ 是 没有被用到 的！也就是说，给定一组 $k’_i$，我们可以本地算出密钥 $k’_i$ 对应的流密钥 $s’_i$ 的，也就是

$c_0 \oplus s'_0 \oplus s'_1 \oplus \ldots \oplus s'_{t-1} = m_0$

也就是说，我们要找到 $s’_0, s’_1, \ldots s’_{t-1}$，使得

$s'_0 \oplus s'_1 \oplus \ldots \oplus s'_{t-1} = m_0 \oplus c_0$

其中 $m_0 \oplus c_0$ 是 $17 \times 8 = 136$ 比特，可以看作是一个 136 维的 $GF(2)$ 向量。在 $GF(2)$ 中，上面这个式子的右边是一个常量，左边是一堆 136 维向量的和。把这个问题放得广一点，因为这些向量是我们自己生成的，用或者是不用完全是由我们自己决定的，所以可以引入一个用或者不用的“开关”变量 $x_i$，那么把这些列向量 $s_i$ 拼起来，上面这个式子也就变成了

$S x = \begin{bmatrix}s_0 & s_1 & \ldots & s_{t-1}\end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_{t-1}\end{bmatrix} = x_0 s_0 + x_1 s_1 + \ldots + x_{t-1} s_{t-1} = u$

此时最大的问题就是这个方程要有解，关键在于向量 $s_0, s_1, \ldots s_{t-1}$ 张成的空间要囊括 $u$ 这个向量，也就是 $S$ 矩阵要满秩。实际上，把 $t$ 往大了设，譬如大过 136，$S$ 就很可能满秩。

所以思路就是：

生成 $t$ 个密钥 $k’_i, i = 0, 1, \ldots, t-1$
对每个密钥 $k’_i$，计算其对应的流密钥 $s’_i$
解上面的方程 $Sx = u$，解得 $x_i, i = 0, 1, \ldots, t-1$
只取那些 $x_i = 1$ 对应的 $k’_i$，送给服务器

代码如下，首先为了代码的模块化，先把题目的加密类给抽出来，然后直接 import 之。

from pwn import *
from sage.all import *
from Crypto.Util.number import *
from shoot import Shooti

class Gao:
    def __init__(self):
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote("91.107.252.0", "13137")
        self.bits = []
        self.keys = []
        self.ans = []

    def gao_one(self):
        self.conn.sendlineafter('[Q]uit\n', 'c')
        c = self.conn.recvline().decode().strip()
        self.cnt += 1
        if 'y = ' in c:
            y = self.R(c.split('y = ')[1])
            return True, y
        else:
            return False, 0

    def recv_dest(self):
        self.conn.sendlineafter('[Q]uit\n', 'c')
        self.conn.recvuntil('cipher = ')
        c = eval(self.conn.recvline().decode().strip())
        m = list(map(ord, "give me the flag!"))
        dest_bits = []
        for mi, ci in zip(m, c):
            dest = mi ^ ci
            for j in range(8):
                dest_bits.append((dest >> j) & 1)
        self.dest_bits = dest_bits

    def get_bits(self):
        N = 200
        vec = 'ed6b8b40a4944397'
        A = []
        for i in range(N):
            key = 'ff' + os.urandom(9).hex()
            s = Shooti(key, vec)
            keystream = [s.BITSEQ() for _ in range(8 * 17)]
            self.keys.append(key)
            A.append(keystream)
        A = matrix(GF(2), A)
        b = vector(GF(2), self.dest_bits)
        x = A.solve_left(b)
        for i in range(N):
            if x[i] == 1:
                self.ans.append(self.keys[i])
        self.ans = ','.join(self.ans)

    def submit_ans(self):
        self.conn.sendlineafter('[Q]uit\n', 'd')
        self.conn.sendlineafter('keys:\n', self.ans)

    def gao(self):
        self.recv_dest()
        self.get_bits()
        self.submit_ans()
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

得到 flag 为

1	CCTF{t3X7_3ncRyp7i0n_uS!nG__Grain__c1ph3R!!}

赛后复盘

之后某天，V 在 1997 群里面谈到了一个区块链上的攻击场景：

记 $H$ 为 SHA3 哈希函数的后 224 位，需要构造一个“碰撞”满足：

$H(a_0) \oplus H(a_1) = H(b_0) \oplus H(b_1) \oplus \ldots \oplus H(b_{124})$

构造手法应该和这题的解法是差不多，也是随机找一组 $b_0, b_1, \ldots, b_{t}$ 并算出这些哈希来，然后构造一个 $GF(2)$ 下的线性方程组去解。但是如何最小化 $x_i$ 中不为 0 的值个数，说实话有点 8 知道，目前看来最好的方法也就是在解空间里面硬搜+拼人品了。

Phoney

题目描述

先生成三个未知的素数 $p, q, r$，其中 $p$ 为 512 比特，$q$ 为 576 比特，$r$ 为 640 比特。已知加密指数 $e = 1234567891$。服务器给出

$N = pqr$
$s = (p^{-1} \bmod qr) + p$
$l = q \bmod p$
$c = m^e \bmod N$

试求 $m$

我的解答

首先看到题目给出的一些条件，会想到把同余式写成整除式：

$q = k p + l$

其中由大小关系，$k$ 大概为 64 比特。

然后对 $s$ 模 $q$ 分析：

$s \equiv p + p^{-1} \pmod{q}$

然后就是把整除式用模 $q$ 分析：

$kp + l \equiv 0 \pmod{q}$ $p \equiv -l/k \pmod{q}$

代入 $s$ 的式子中：

$s \equiv -l/k-k/l \pmod{q}$

化简：

$s k l \equiv -l^2-k^2 \pmod{q}$

也就是

$k^2 + l^2 + s k l \equiv 0 \pmod{q}$

这就是一个关于 $k$ 的方程，看看能不能用 coppersmith 来做：Coppersmith 方法要求解 $x_0$ 的界满足：

$|x_0| < \frac{1}{2}N^{\frac{\beta^2}{\delta} - \epsilon}$

这里 $N$ 是 1728 bit，$q$ 是 576 bit，所以 $\beta = 1/3$，多项式的度数 $\delta = 2$，所以右边的数大概是 $1728 \times (1/18) - 1 = 95$ 比特这个量级，64 比特是能解的。在解的时候，我还是不放心，就用一个变换 $k’ = k + 2^{63} + 2^{62}$ 代换了一下，就把解的范围变换到 $[-2^{62}, 2^{62}]$ 了。

如果 coppersmith 可以解出解的话，那么就可以利用最大公约数求得 $q$ 的值，然后利用 $p = (q - l) / k$，$r = N / pq$ 得到其他素数的值，最后用 RSA 解密即可。代码如下：

from Crypto.Util.number import *

n = 
s = 
l = 
c = 
e = 1234567891


PR.<k0> = PolynomialRing(Zmod(n))
k = k0 + 2^63 + 2^62
f = k^2 + l^2 + l * k * s
sol = f.small_roots(X=2^62, beta=0.32, epsilon=0.015)
k_ = sol[0]
q = gcd(ZZ(f(k_)), n)
k = ZZ(k_ + 2^63 + 2^62)
p = (q - l) // k
r = n // (p * q)
assert n == p * q * r
d = inverse_mod(e, (p-1)*(q-1)*(r-1))
m = pow(c, d, n)
print(long_to_bytes(int(m)))

解得 flag 为

1	CCTF{c0UlD_b3_ReCoVEr3d_v!4_Coppersmiths_m3ThOd?}

Snails

题目描述

题目基于 ECDSA。给出一个已知的模 $p$ 的椭圆曲线 $E_p: y^2 = x^3 + a x + b$，其中 $p$ 为 521 bit，阶为 $n$；以及已知生成点 $G$，私钥 $d$ 为 flag。给定固定的 38 字节长消息 $m_0$。

服务器接受 任意次交互：输入消息 $m$，其中要求 $m_0$ 为 $m$ 的子串，且 $m$ 为 40 字节长。然后就是魔改了的 ECDSA 流程：

计算 $m$ 的 SHA512 哈希值 $h = H(m)$
记 $t$ 为 $h$ 作为整数的比特数（忽略前导 0），生成一个 $t$ 比特的随机数 $k$
计算倍点 $P = kG$
计算 $r = x_P$
计算 $s = (k^{-1}(h + r d)) \bmod n$
返回 $(r, s)$

试求私钥 $d$

我的解答

这里的猫腻就在这个随机数 $k$ 太小了，小过 $n$ 的 521bit，于是就可以当成一个 HNP 来解。

特别地，因为 $m_0$ 要是 $m$的子串，所以我们可以遍历一下所有的 $m$，一共是 $3 \times 256^2$ 个，选出 SHA256 值最小的那个送过去：

from Crypto.Util.number import *
from hashlib import sha512
import itertools


H = 2**999
s = b''

m = '✔✔✔ My signature is the priority'.encode()
for i, j in itertools.product(range(256), repeat=2):
    for mi in [m + bytes([i, j]), bytes([i, j]) + m, bytes([i]) + m + bytes([j])]:
        h = bytes_to_long(sha512(mi).digest())
        if h < H:
            H = h
            s = mi
print(f'{s = }')
print(f'{H = }')
print(f'{H.bit_length() = }')

算出来的结果是 H.bit_length() = 497，也就是说$k$的高15bit都为0，所以我们就可以利用格基规约，解出私钥$d$ 来（具体方法可移步春乎）。

需要注意的就是，这题的 pull 数据和求解可以分成两步来做。Pull 数据的代码如下：

from pwn import *
from Crypto.Util.number import *
import pickle
from tqdm import trange

class Gao:
    def __init__(self):
        # self.conn = process(['sage', 'another.sage'])
        self.conn = remote("91.107.133.165", "33337")
        self.rlist = []
        self.slist = []

    def gao_one(self):
        m = b'\x97;\xe2\x9c\x94\xe2\x9c\x94\xe2\x9c\x94 My signature is the priority'
        self.conn.sendlineafter('[Q]uit\n', 's')
        self.conn.sendlineafter('message: \n', m)
        self.conn.recvuntil('r = ')
        r = eval(self.conn.recvline())
        self.conn.recvuntil('s = ')
        s = eval(self.conn.recvline())
        self.rlist.append(r)
        self.slist.append(s)

    def gao(self):
        for i in trange(50):
            self.gao_one()
        with open('1.pickle', 'wb') as f:
            pickle.dump((self.rlist, self.slist), f)

if __name__ == '__main__':
    g = Gao()
    g.gao()

求解代码如下：

import pickle
from Crypto.Util.number import *
with open('1.pickle', 'rb') as f:
    rlist, slist = pickle.load(f)

n = 
h = 

N = 50
L = [[0 for j in range(N+1)] for i in range(N+1)]
r0, s0 = rlist[0], slist[0]
for i in range(N-1):
    ri, si = rlist[i+1], slist[i+1]
    A = ri * s0 * inverse_mod(r0 * si, n) % n
    B = (r0 * h - ri * h) * inverse_mod(r0 * si, n) % n
    L[i][i] = n
    L[N-1][i] = A
    L[N][i] = B
L[N-1][N-1] = 1
L[N][N] = h
L = matrix(ZZ, L)
L = L.BKZ(block_size=12)

k0 = L[0][-2]
m = (k0 * s0 - h) * inverse_mod(r0, n) % n
print(long_to_bytes(int(m)))

得到 flag 为：

1	CCTF{prIv4T3_kEy_rEc0v3rY_fOr_P521_!n_r3AL_w0rlD!}