Misay's blog

WMCTF2025

发表于 更新于 分类于
WMCTF2025WP&Review

写在前面

和DAWN的师傅们一起打了WMCTF2025 主要参与并负责了密码方向 SplitMaster&IshowSplit 两道以及 MISC方向 Pishing Mail的解出，各位学长都很给力，最终DAWN也是打进了前10，本文主要复现Crypto方向的5道赛题，以及MISC方向的两道赛题

Crypto

SplitMaster

task.py

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from Crypto.Util.number import *
import socketserver
import socket

def split_master(B_decimal, segment_bits):
    if len(segment_bits) < 3:
        raise ValueError("no")
    
    if sum(segment_bits) != 512:
        raise ValueError("no")
    
    n = len(segment_bits)
    found_combination = None
    for k in range(n,1,-1):
        from itertools import combinations
        for indices in combinations(range(n), k):
            if sum(segment_bits[i] for i in indices) > 30:
                continue

            valid = True
            for i in range(len(indices)):
                for j in range(i+1, len(indices)):
                    if abs(indices[i] - indices[j]) <= 1:
                        valid = False
                        break
                if not valid:
                    break
            if not valid:
                continue

            if 0 in indices and (n-1) in indices:
                continue
            if any(segment_bits[i]>=25 for i in indices):
                continue
            found_combination = indices
            break
        
        if found_combination is not None:
            break
    
    if found_combination is None:
        raise ValueError("no")
    
    binary_str = bin(B_decimal)[2:].zfill(512)
    if len(binary_str) > 512:
        raise ValueError("no")

    segments_binary = []
    start = 0
    for bits in segment_bits:
        end = start + bits
        segments_binary.append(binary_str[start:end])
        start = end
    
    segments_decimal = [int(segment, 2) for segment in segments_binary]
    
    return [segments_decimal[i] for i in found_combination]

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def handle(self):
        # 设置socket超时而不是使用signal.alarm
        self.request.settimeout(90)  # 90秒超时
        
        try:
            flag = b'WMCTF{test}'
            self.send(b"Welcome to WMCTF2025")
            key = getPrime(512)
            print(key)
            q = getPrime(512)
            self.send(b"q:"+str(q).encode())
            for i in range(20):
                a = getPrime(512)
                b = a * key % q
                gift = split_master(b, list(map(int, self.recv(b"> ").split())))
                self.send(b"a:"+str(a).encode())
                self.send(b"gift:"+str(gift).encode())  
            x = self.recv(b"the key to the flag is: ").decode()
            if x == str(key):
                self.send(flag)
        except socket.timeout:
            self.send(b"Time's up!")
        finally:
            self.request.close()  # 确保连接被关闭


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":

    HOST, PORT = '0.0.0.0', 10003

    print("HOST:POST " + HOST + ":" + str(PORT))
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

函数split_master会根据接收的数组以及数字返回有关传入数字的比特的信息 保证总比特数不超过30 且连续比特长不超过24

我们需要利用20组已知的a和我们能得到的有关b的比特泄露gift求出私钥b

赛中想到利用构造 segment_bits = [10, 160, 10, 161, 10, 161],我们能将b比较均匀的拆成6个部分 拥有离散的10*3的比特泄露

转化为随机位置泄露的HNP问题 我们参考Tover师傅的博客板子

造格子然后去打即可，exp

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from pwn import *
from Crypto.Util.number import inverse

# --- 配置 ---
HOST = '127.0.0.1'
PORT = 10003

# 43.138.4.37:31055

# 构造 segment_bits 以获取3个在512位空间中分布更均匀的10位信息。
# 总泄露位数仍然是30位。
segment_bits = [10, 160, 10, 161, 10, 161]
payload = " ".join(map(str, segment_bits)).encode()

# --- 连接服务器 ---
log.info(f"Connecting to {HOST}:{PORT}...")
try:
    sh = remote(HOST, PORT)
    log.success("Connection established!")
except PwnlibException as e:
    log.error(f"Failed to connect: {e}")
    log.error("Please make sure task.py is running in another terminal window!")
    exit()

# --- Step 1: 接收欢迎信息并提取 q ---
sh.recvuntil(b"q:")
q_str = sh.recvline().strip()
q = int(q_str)
log.success(f"Successfully retrieved q: {q}")

# --- Step 2: 初始化用于存储数据的列表 ---
a_list = []
bh1_list = []
bh2_list = []
bh3_list = []

# 循环20次来收集数据
for i in range(20):
    log.info(f"--- Round {i+1}/20 ---")
    
    sh.recvuntil(b"> ")
    sh.sendline(payload)
    log.info(f"Sent segment_bits: {payload.decode()}")
    
    sh.recvuntil(b"a:")
    a_str = sh.recvline().strip()
    a = int(a_str)
    
    sh.recvuntil(b"gift:")
    gift_str = sh.recvline().strip().decode()
    gift_list = eval(gift_str)

    sh.recvuntil(b"key:")
    key_str = sh.recvline().strip().decode()
    true_key = int(key_str)
    
    if len(gift_list) == 3:
        bh1, bh2, bh3 = gift_list
        log.info(f"Received gift: {gift_list}, extracted parts: bh1={bh1}, bh2={bh2}, bh3={bh3}")
        
        a_list.append(a)
        bh1_list.append(bh1)
        bh2_list.append(bh2)
        bh3_list.append(bh3)
    else:
        log.warning(f"Received an unexpected gift format: {gift_list}")


# 现在你可以直接使用 a_list, bh1_list, bh2_list, bh3_list 和 q 
# 来进行后续的密码分析。

length = 512
leak_length = 10
T1 = 2^(512-leak_length)
T2 = 2^(512-leak_length-160)
T3 = 2^(512-leak_length*2-160)
T4 = 2^(512-leak_length*2-160-161)
T5 = 2^(512-leak_length*3-160-161)
print(len(a_list))
inv_a0 = inverse_mod(a_list[0],q)


D = []
Ai = []
E = []
F = []

for i in range(1,20):
    A = a_list[i] * inv_a0
    Ai.append(A % q)
    D1 = bh1_list[i]*T1 - A*bh1_list[0]*T1
    D2 = bh2_list[i]*T3 - A*bh2_list[0]*T3
    D3 = bh3_list[i]*T5 - A*bh3_list[0]*T5
    D.append((D1+D2+D3) % q)
    E.append(A * T2 % q)
    F.append(A * T4 % q)

R = 2^161
n = 19

M = Matrix(ZZ,3*n+4)
for i in range(n):
    M[3*i,3*i] = -q
    M[3*i+1,3*i] = -T2
    M[3*i+2,3*i] = -T4
    M[3*i+1,3*i+1] = 1
    M[3*i+2,3*i+2] = 1

    M[-4,3*i] = Ai[i]
    M[-3,3*i] = F[i]
    M[-2,3*i] = E[i]
    M[-1,3*i] = D[i]

M[-4,-4] = 1
M[-3,-3] = 1
M[-2,-2] = 1
M[-1,-1] = R

L = M.BKZ(block_size=24)

key_candidate = []
for l in L:
    if l[-1]:
        b0 = vector(l)
        b01 = b0[-2]
        b03 = b0[-3]
        b05 = b0[-4]
        key = (bh1_list[0]*T1 + b01*T2 + bh2_list[0]*T3 + b03*T4 + bh3_list[0]*T5 + b05) * inv_a0 % q

        key_candidate.append(key)

print(key_candidate)
print(true_key)
# if true_key in key_candidate:
#     print("found")

# 43.138.4.37:31055

sh.sendlineafter(b"the key to the flag is: ", str(true_key).encode())
response= sh.recvall(timeout=2)
print(response)

格的参数还可以进一步优化 大概有1/3的概率能找到key，本地出了后交给 Ramoor师傅用代码打远程成功出了，拿下二血

赛后看到别的师傅找到一个Trick

构造 -257 513 -257 513的序列

1
2
3
4
5
Welcome to WMCTF2025
q:9861430895025459477553092372852393541874339091269599286733236011532282532345396778429343483337130529182773612573595360674235802007820723008241118435213327
> -257 513 -257 513
a:10311738079985788524348250930378887840235618248819905021512068084058439869758091860311941760876644520871282741083309749114892507621255837856268626603123599
gift:[30524567771060486261423907587778820949788903093067527468240286198675156055398, 45779902845695456433368637342563313580177390291673538250967582387199430778996]

能拿到510位b的比特 那就很好做了 多取几组打格子即可

IshowSplit

task.py

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from Crypto.Util.number import *

from hashlib import md5

def split_master(B_decimal, segment_bits):
    if len(segment_bits) < 3:
        raise ValueError("no")
    
    if sum(segment_bits) != 512:
        raise ValueError("no")
    
    n = len(segment_bits)
    found_combination = None
    for k in range(n,1,-1):
        from itertools import combinations
        for indices in combinations(range(n), k):
            if sum(segment_bits[i] for i in indices) > 30:
                continue

            valid = True
            for i in range(len(indices)):
                for j in range(i+1, len(indices)):
                    if abs(indices[i] - indices[j]) <= 1:
                        valid = False
                        break
                if not valid:
                    break
            if not valid:
                continue

            if 0 in indices and (n-1) in indices:
                continue
            
            if any(segment_bits[i]>=25 for i in indices):
                continue

            found_combination = indices
            break
        
        if found_combination is not None:
            break
    
    if found_combination is None:
        raise ValueError("no")
    
    binary_str = bin(B_decimal)[2:].zfill(512)
    if len(binary_str) > 512:
        raise ValueError("no")

    segments_binary = []
    start = 0
    for bits in segment_bits:
        end = start + bits
        segments_binary.append(binary_str[start:end])
        start = end
    
    segments_decimal = [int(segment, 2) for segment in segments_binary]
    
    return [segments_decimal[i] for i in found_combination]

p=getPrime(512)
key=randrange(1,p)
gift=split_master(key,[182,20,200,10,100])

flag="WMCTF{"+md5(str(key).encode()).hexdigest()+"}"

A=[]
B=[]
R=[]
M=[64, 128, 256]
for i in range(10):
    a=randrange(1,p)
    A.append(a)
    s=0
    rr=[]
    for j in range(3):
        r=randrange(1,p)
        k=randrange(1,2^M[j])
        s+=r*k%p
        rr.append(r)
    R.append(rr)
    B.append((a*key+s)%p)

print(f"p={p}")
print(f"A={A}")
print(f"B={B}")
print(f"R={R}")
print(f"gift={gift}")

类似上题 是给定chunk泄露的HNP问题

通用的是造格子打的方法，这里关于noise的信息是 我们知道以及的范围上界，就不难想到把放到格子里面，用系数去配平，貌似这样就能出了，Polaris的师傅就是这样做的 再用gift来验证

详细说就是 消去，得到 左边是已知量，记为,那么也就是 我们想随便求出一组来恢复，那就把这里的

9个等于0的方程放在格子里面 然后给放在右边，式子如下 真的是很自然但又非常有效的思路 感谢星盟的师傅们！

后续有参考官方的wp

给出了命题paperExtended Hidden Number Problem and Its Cryptanalytic Applications | SpringerLink

命题的情景是

Definition1 即 的情况 其中我们都已知 知道一个上界 完美契合

在GPT师傅的帮助下实现了一个复现 思路大致如下给定 、、上界

设 ，取 使 ，。

组装基矩阵

目标向量 用 LLL(+Babai) 在格子 中找。

解码 输出 作为 。

这相对是这种限阶HNP的通用处理思路 造一个有放缩的格子 通过调整数据使得问题规划为CVP下BaBai可解的

最后再学习了一下鸡块师傅的造格方法 也是受益匪浅，我们来看看

既然 还给了的已知位 我们展开一下不难得到 要求实际上也就是求

我们当时对于 不好造格子的主要原因就是我们右边没有一个可以暴露出来放到目标向量的一个”常量”，这里鸡块师傅的处理方式是手动乘已知系数的逆元，把最大的给暴露出来，也就是 这样子我们就能把放到我们想要去规约的目标向量里面，然后带入上面关于的等式，即 已知量全部先算好，令 问题就变为 写成等式 我们希望找到这样的短向量 我们由1式 也就是线性约束 能构造约束矩阵 这里我们每列的系数都是两两对齐的，构造的矩阵 我们理想的格子长这样 右侧是我们尝试用来落实的线性规划，左侧的单位阵用来承接我们期望的短向量，最后 我们期望构造的运算是 既然就是理想的目标向量，而的我们其实很可控，不妨想想 何时，有 再次看回1式 就很自然 只要我们的恰好是线性方程中的自然就配上了，所以最后方程形似 这里我们通过构造格子 让我们LLL/BKZ找到的就是1式线性方程组中的 这一步就叫做“吃掉p” 其实之前2 3个方程的格算法也有这种思路的体现 当时就理所当然的接受了，我们已知是具备一个线性关系的 藏在10组方程中 那么我们即使给乘上一个大系数 线性关系还是在 而且当变量越大 方程组对应欧氏范数中其权重就会更大 算法会更多的去保留大权值变量的线性关系 把它做小 故而这就实现了我们能去格出而尽可能的少受到无关变量的影响，这就是我们常说的”配平”

lw3&lw5

都是类似的思路 放在一起 题面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from random import choice, sample
from Crypto.Cipher import AES
from hashlib import md5
from secret import flag

m, n = 90, 64
p = 1048583

E = sample(range(1, p), 3)
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(E) for i in range(m)])
b = A*s + e

print("🎁 :", E + A.list() + b.list())
print("🚩 :", AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

给定的是一个LWE系统

是在给出的集合中选择的，我们已知,想求

我们可以如下抽象一个LWE系统

组随机变量,组有限制的变量，组由上述组变量得到的线性等式

LWE中的也就是error,往往会有各种限制 比如二项分布 残差标准差关系等等

不难很直接地构造得到一个规约的式子 自然 我们对于这个格的优化思路是利用已知的的约束 尝试只规约而不规约,同时提升规约速度 增加规约出的几率,从而解方程得到

抽象上来说就是

原本个变量 个方程，变成个变量 个方程，我们构造的是 有 而且我们是可以对进行行阶梯标准化的 不影响我们的乘算

OK 攻击的思路大致如上 接下来看题

一般来说如果是构造的选取的区间,我们总是期望能找到一组线性变换 即 其中三个值都很小 我们在其中选的时候值也小 很好规约出来，也就是我们用一个矩阵描述我们是如何选取的,那么方程组 可以写成 即 这里的会比较小 好规约

那么我在这道题中试一下 发现

1
2
3
4
5
6
7
8
9
10
11
12
13
L = block_matrix(ZZ, [
    [Matrix(ZZ, E)],
    [Matrix(ZZ, [1]*len(E))],
    [p]
])
E_ = L.LLL()[3]
k, t = Matrix(Zmod(p), L).solve_left(E_)[:2]
assert k*vector(GF(p), E) + t*vector(GF(p), [1,1,1]) == vector(GF(p), E_)

print(E_)

# (-298, 582, -285)

并不够小~

这里我们参照鸡块师傅的预期解法

我们知道从中选出可以如下抽象 而且我们的实际上只有三种取法 我们可以降一个维度 其中的取法只有或者或者

这个我们就可以试着去规约一下

此时

是组随机变量

是组随机变量 但是有0，1的限制

个包含的方程

再套用前面的思路 尝试消去

得到组包含个01变量的线性方程，在后续就是考虑如何优化来解决这里的规约问题，预期使用的是blaster

这里关于具体格子怎么造不做一个深入的分析 主要是概述一下解决这种LWE的共通思路

也就是从无限制的随机变量脱离出来 找到便于规约的 有限制关系的变量，利用大小/线性/空间选择的有限性 来使我们能够去规约出来 尝试找到解

官方wp中提及2023SEKAICTF中的noise_crc 2024NKCTF Ez_random 好像也涉及了这一个点 用更多的变量换取更强的限制关系,同时做好对变量的降维，增加我们去规约出来的可行性

LW5
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
from Crypto.Cipher import AES
from ast import literal_eval
from random import choice
from hashlib import md5
from secret import flag


def check(E):
    assert len(set([_ % p for _ in E])) == 5
    L = block_matrix(ZZ, [
        [Matrix(ZZ, E)],
        [Matrix(ZZ, [1]*5)],
        [p]
    ])
    E_ = L.LLL()[3]
    return max([abs(_) for _ in E_]) > 1337 and min([abs(_) for _ in E_]) > 337
    
p = 1048583
E = literal_eval(input("your error plz :)"))
assert check(E)

m, n = 90, 56
s = random_vector(Zmod(p), n)
A = random_matrix(Zmod(p), m, n)
e = vector(Zmod(p), [choice(E) for i in range(m)])
b = A*s + e

print("🎁 :", A.list() + b.list())
print("🚩 :", AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(flag))

做了两个优化 首先是完全不让你去找到能映射到短error的 随后是的维度拓展到5 你就算用01去降维 后续还是维的变量格要处理 规约不了一点

不过我们参照前面的思路 找一组基 使得消去随机变量后 我们的线性方程仍然是变量可规约的

也就是 是上述用格基归约找到的5个短分量式，如果考虑用”选取”的二进制展开思路，则是 可以降一个维度 搓一个小的一直生成 直到通过检测 后续思路同lw3

总结

强度比较高的比赛 题目质量也非常棒 很多问题有了更高维度的看法 感谢命题师傅以及其他给出解答的师傅 非常宝贵的学习机会!