2025京麒CTF挑战赛-Crypto复现
有点遗憾，下午睡了快4小时，结束后一小时把onlinecrypto整了出来。(っ╥╯﹏╰╥c)
onelinecrypto
题目很短： 1
assert __import__('re').fullmatch(br'flag\{[!-z]{11}\}',flag:=os.getenvb(b'FLAG')) and [is_prime(int(flag.hex(),16)^^int(input('🌌 '))) for _ in range(7^7)]
这题一开始没看懂在干嘛，因为assert是永真的。然后@N1gh7ma12e说可能是侧信道，所以一直在试is_prime的时间。然后就发现只要输入的数字有一个小因子，那么is_prime很快就能返回False。当时就想到用这个方法判断flag是否含有因子2（虽然这个是显然的）。
然后就卡住了，而且由于昨晚睡太晚了，下午太困了就睡过去了，7点起来发现就5解了，所以又开始看这题。
思路
这题大概的思路是先求出flag模3的值，然后是模5的值，，，。这样循环几次后就可以用crt求出flag。
首先来看怎么求mod3的值，我们可以给靶机输入 \(k*2^{256} ,k \in \{1, 2, 3\}\) ，这样is_prime的输入就是 \(k*2^{256} + m\) ，而且 \(k*2^{256} + m\) 模3的所以情况一定是 \(\{0,1,2\}\)，所以当模3是0的时候，is_prime很快就能做出判断，这就从时间上告诉了我们flag模3的值。然后为了让区别更明显一些，我们不能只测这三个数，而是要对于每一个k，我们测出下面这些数的总时间:
\[ (k + j*3)*2^{256} + m, \ \ j \in {1,2,3 \dots} \]
对于同一个k，这些数模3的值都是一样的。
然后来看模5，我们需要让is_prime输入的数不含因子3和2，所以输入下面的数：
\[ (k + j*15)*2^{256} + m, \ \ j \in {1,2,3 \dots} \]
为了让他不含有因子3，可以解下面的同余方程:
\[ k*2^{256} + m \equiv 1 \mod 3 \]
由于m模3已经知道，所以可以求出k模3的值，记为\(k_1\)，然后将他带入上式:
\[ (3*t + k_1)*2^{256} + m \equiv 1 \mod 3 \]
然后枚举 \(t \in \{0, 1, 2, 3, 4\}\)，这样 \((3*t + k_1)*2^{256} + m\) 模5一定会出现 \(\{0,1,2,3,4\}\)，而且一定不含因子3，所以当模5是0时，is_prime判断时间会很快，这就从时间上告诉了我们flag模5的值。同样为了让区别更明显，对于每一个t我们测出下面这些数的总时间：
\[ (3*t + k_1 + 15 * j)*2^{256} + m , \ \ j \in {1,2,3 \dots} \]
对于同一个t，这些数模3模5的值都是一样的。
然后按照上面的步骤，依次求出模7，模11的的值，，，。最后将flag在模各个素数的值CRT。
exp
1 | from Crypto.Util.number import * |
Unwind On Vacation
题目: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64from ast import literal_eval
from hashlib import shake_128
import secrets
FLAG = "flag{redacted}"
def Hash(msg):
h = int(shake_128(msg).hexdigest(3*m),16)
return vector(GF(q),[(h:=h//q)%q if i else h%q for i in range(m)])
class UOV:
def __init__(self, m, n, q):
self.params = (m, n, q)
self.pub = None
self.O = random_matrix(ZZ, n-m, m)
self.refresh()
def keygen(self):
set_random_seed(seed:=secrets.randbits(128))
print("🌻", seed)
m, n, q = self.params
F = GF(q)
Ps = []
for _ in range(m):
P1 = random_matrix(F, n-m, n-m)
P2 = random_matrix(F, n-m, m)
P3 = (-self.O.T*P1*self.O-self.O.T*P2)
P = block_matrix(F, [[P1, P2], [zero_matrix(F, m, n-m), P3]])
print(P3.list())
Ps.append(P)
set_random_seed(secrets.randbits(128))
return Ps
def refresh(self):
self.pub = self.keygen()
def sign(self, msg):
if msg == "Unwind On Vacation": return None
m, n, q = self.params
F = GF(q)
O = block_matrix(F, 2, 1, [self.O, identity_matrix(F, m)])
v = random_vector(F, n, 1)
M = matrix(F, [v*(self.pub[i]+self.pub[i].T)*O for i in range(m)])
u = Hash(msg.encode())-vector([(v*self.pub[i]*v) for i in range(m)])
return v+O*M.solve_right(u)
def verify(self, msg, token):
msg = Hash(msg.encode())
t = vector(token)
for i in range(self.params[0]):
if t*self.pub[i]*t != msg[i]:
return False
return True
m, n = 73, 180
q = 0x10001
uov = UOV(m, n, q)
__import__("signal").alarm(1200)
for _ in range(80):
match input("> "):
case "R": uov.refresh()
case "S": print(f"{uov.sign(input("💬 "))}")
case "V": print("🚩", uov.verify("Unwind On Vacation",
literal_eval(input("📝 ")))*FLAG)
复现的时候参考了@hash-hash师傅的WP，顺便找了篇paper学习了一下UOV。
签名原理
这题的UOV并不是初代的的UOV，签名的方法也有所不同。这里就先说一下本题UOV的签名原理：
这里的公钥同样是m个矩阵P，矩阵P都是如下形式： \[
\mathbf{P}_i =
\begin{pmatrix}
\mathbf{P}_i^{(1)} & \mathbf{P}_i^{(2)}\\
\mathbf{0} & \mathbf{P}_i^{(3)}\\
\end{pmatrix}
\]
签名的过程仍然是求这个这个矩阵对应的二次多元多项式的逆映射。这个矩阵和初代的UOV很像，但是他对应的油醋多项式中油变量是会混在一起的。而签名的关键在于公钥\(\mathbf{P}_i\)中的\(\mathbf{P}_{i}^{(3)}\)，具有如下形式：
\[
\mathbf{P}_{i}^{(3)} = -\mathbf{O}^T\mathbf{P}_i^{(1)}\mathbf{O} -
\mathbf{O}^T\mathbf{P}_i^{(2)}
\] 其中\(\mathbf{O}\)就是私钥。这种形式的\(\mathbf{P}_i^{(3)}\)会让公钥满足如下性质：
\[
\mathbf{\overline{O}}^T\mathbf{P}_i\mathbf{\overline{O}} = \mathbf{0}
\] 其中： \[
\mathbf{\overline{O}} =
\begin{pmatrix}
\mathbf{O} \\
\mathbf{I}_m
\end{pmatrix}
\]
这样签名的形式就是: \[ \mathbf{s} = \mathbf{v} + \mathbf{\overline{O}}\mathbf{x} \]
\(\mathbf{x}\)就是签名要寻找的向量，我们带入得： \[ \mathbf{s}^T\mathbf{P}_i\mathbf{s} = (\mathbf{v} + \mathbf{\overline{O}}\mathbf{x})^T \mathbf{P}_i (\mathbf{v} + \mathbf{\overline{O}}\mathbf{x}) = \mathbf{v}^T\mathbf{P}_i\mathbf{v} + \mathbf{v}^T (\mathbf{P}_i + \mathbf{P}_i^T)\mathbf{\overline{O}}\mathbf{x} \]
可以发现二次项都消去了，所以只需要解一个线性方程组就行。而且想要完成签名，只需要拿到\(\mathbf{\overline{O}}\)的列向量生成的空间的一组基就行，因为\(\mathbf{B}^T\mathbf{\overline{O}}^T\mathbf{P}_i\mathbf{\overline{O}}\mathbf{B} = \mathbf{0}\)也是成立的，其中\(\mathbf{B}\)是对\(\mathbf{\overline{O}}\)的初等列变换。
解题思路
签名原理说完了，再来看看本题的解法。
本题的漏洞点在于每次刷新密钥用的都是同一个私钥，这样可以让我们收集到足够的方程来求解\(\mathbf{O}\)，以\(\mathbf{O}\)的第一条列向量\(\mathbf{o_1}\)为例，将它线性化会有\(\frac{(n - m)(n - m - 1)}{2} + 2(n -
m)\)即\(5885\)个变量，而我们能收集到\(80m\)即\(5840\)个方程，所以解空间还有\(q^{45}\)，而这里\(\mathbf{O}\)的生成居然用的是random_matrix(ZZ, n-m, m)，(基环居然是ZZ，赛中完全没有注意到这点)，这会导致生成的\(\mathbf{O}\)太小，让我们可以利用LLL恢复\(\mathbf{o_1}\)。由于\(\mathbf{o}_1\mathbf{P}_i\mathbf{o}_2 =
0\)，所以求出\(\mathbf{o}_1\)可以通过求\(\mathbf{o}_1\mathbf{P}_i\)右核的方式求出\(\mathbf{O}\)，拿到\(\mathbf{O}\)后正常签名就行。
exp
1 | # exp.sage |