糖醋小鸡块的blog
0%

2025-WMCTF-wp-crypto

发表于 更新于 分类于 Valine：

LW3和LW5这两道题其实很早之前就出好了，打算给NKCTF结果却没办。前些天maple在HitconCTF出的BabyLWE那道题让我意识到可能是时候让这两个题目亮相了，正好@yolbby需要支援，就支援了这两道给WMCTF。

与此同时也包含@yolbby那道LemonPepper的原装wp，想着wp的完整性就把两道HNP也搞了搞(`・ω・´)

SplitMaster

题目

题目描述：

1
It's up to you.

题目：

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
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()

题目生成一个512bit的key(记作$k$)，以及512bit的模数$q$，给出$q$之后进行20次交互：

  • 随机生成512bit的素数$a_i$
  • 计算$b_i = a_ik \quad(mod\;q)$
  • 可以自行输入一个列表segment_bits，做一个gifti = split_master(bi， segment_bits)
  • 给出每一轮的$a_i$以及gifti

其中split_master(bi)的操作主要是泄露$b_i$的部分比特信息，并且对于泄露的形式存在一定要求。直接从预期的效果来看要求主要有：

  • 至少将$b_i$分成三段
  • 泄露的部分需满足：
    • 每一块不超过25bit
    • 泄露的总和加起来不超过30bit
    • 不能同时泄露头和尾

需要求解出$k$并发回给靶机，从而拿到flag。

思路

预期显然是个分chunk的HNP问题，不过@rec发现了一个非预期——输入的segment_bits这个列表似乎没有对负数做检查。所以发一个[1,1,-3,513]，就可以泄露出$b_i$的二进制表示的[2:-1]，因此爆几位就能拿到$k$了。

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
from Crypto.Util.number import *
from ast import literal_eval
from pwn import *

context.log_level = "critical"

sh = remote("62.234.144.69", 32731)
sh.recvuntil(b"q:")
q = int(sh.recvline().strip().decode())
As = []
b_s = []
for _ in range(20):
    sh.sendline(b"1 1 -3 513")
    sh.recvuntil(b"a:")
    a = int(sh.recvline().strip().decode())
    As.append(a)
    sh.recvuntil(b"gift:")
    b_ = literal_eval(sh.recvline().strip().decode())[1]
    b_s.append(b_)

for i in range(8):
    for j in range(8):
        t11, t12 = str(bin(i)[2:].zfill(3))[:2], str(bin(i)[2:].zfill(3))[-1]
        t21, t22 = str(bin(j)[2:].zfill(3))[:2], str(bin(j)[2:].zfill(3))[-1]
        b1 = int(t11 + bin(b_s[0])[2:].zfill(509) + t12, 2)
        b2 = int(t21 + bin(b_s[1])[2:].zfill(509) + t22, 2)
        k1 = inverse(As[0], q) * b1 % q
        k2 = inverse(As[1], q) * b2 % q
        if(k1 == k2):
            if(not isPrime(k1)):
                k1 += q
            sh.recvuntil(b"the key to the flag is: ")
            sh.sendline(str(k1).encode())
            print(sh.recvline())
            sh.close()


#WMCTF{Th3_d1ff1culty_Is_up_t0_y0u}


IShowSplit

题目

题目描述：

1
It's up to me.

题目：

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}")

这一次是静态题目，在生成512bit的模数$p$以及秘密数$k$之后，首先计算了一个gift=split_master(key,[182,20,200,10,100])，之后进行十轮如下计算：

其中$k_{i,1} < 2^{64}, k_{i,2} < 2^{128}, k_{i,3} < 2^{256}$。给出模数$p$、gift以及每一组的$b_i, a_i, r_{i,j}$，要求解出$k$。

思路

由于固定了chunk位置所以是非常直白的HNP了，并且由于泄露了隐藏数$k$的比特所以并不需要消去他，实测了下banlace都不需要，LLL就可以解了。

exp

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from hashlib import md5

p=
A=
B=
R=
gift=
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
d = 2^100*gift[1] + 2^310*gift[0]

nums = 10
L = Matrix(ZZ, 3*nums+3+1, 3*nums+3+1)

for i in range(2*nums+4):
    L[i, i] = 1

for i in range(nums):
    ri1, ri2, ri3 = R[i]
    Ci = -inverse(ri3, p)*(A[i]*d - B[i]) % p
    ai1, ai2, ai3 = -inverse(ri3, p)*A[i] % p, -inverse(ri3, p)*2^110*A[i] % p, -inverse(ri3, p)*2^330*A[i] % p
    bi1, bi2 = -inverse(ri3, p)*ri1 % p, -inverse(ri3, p)*ri2 % p

    L[0, 2*nums+4+i] = Ci

    L[1, 2*nums+4+i] = ai1
    L[2, 2*nums+4+i] = ai2
    L[3, 2*nums+4+i] = ai3

    L[4+2*i, 2*nums+4+i] = bi1
    L[4+2*i+1, 2*nums+4+i] = bi2

for i in range(nums):
    L[-i-1, -i-1] = p

Q = diagonal_matrix(ZZ, [2^256, 2^156, 2^56, 2^74] + [2^192, 2^128]*nums + [1]*nums)
L = L * Q
L = L.LLL()
L = L / Q

res = list(map(abs, L[0]))
key = d + res[1] + 2^110*res[2] + 2^330*res[3]
flag="WMCTF{"+md5(str(key).encode()).hexdigest()+"}"
print(flag)


#WMCTF{ed27074de5c476e67328e04b6e27a5b8}


LW3

题目

题目描述：

1
LW:3

题目：

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实例：

其中$(m,n)=(90,64)$，与一般的LWE不同的是，题目的$\mathbf{e}$的各分量取值仅在三个固定值中随机选择，而这三个固定值均为$GF(p)$下的随机数。

需要求解出私钥$s$，从而解AES得到flag。

背景

正好趁这次题目好好讲讲LWE，因为之前这篇里对于LWE一些攻击的解释现在回头再看，其实不太好懂的同时也真的很麻烦。

主要是primal_attack的优化版本

LWE

我们不妨从另外一个角度来重新审视LWE——他是由如下要素组成的特殊线性系统：

  • $n$个$GF(p)$下的随机变量，也就是$\mathbf{s}$

  • $m$个$GF(p)$下的有限制变量，也就是$\mathbf{e}$

    这里具体是什么限制根据情况而定，比如离散高斯分布、中心二项分布以及这道题目里的三元随机采样等

    有时LWE也会对$\mathbf{s}$做限制，常见于各种RLWE以及MLWE等

  • $m$个由上述$m+n$个变量构成的线性等式

并且可以知道，在对$\mathbf{s}$不做任何限制的情况下，$m \le n$的情况是没有意义的，因此一般会有$m > n$。

primal attack

从这个角度出发的话，不做优化的primal_attack，其直观解释就是不做任何处理，直接规约整个线性系统，从而在规约后的短向量中找到$\mathbf{s}$以及$\mathbf{e}$，实际列出格其实也就是：

primal attack(优化版本)

而优化后的primal_attack我们知道是一种只规约出$\mathbf{e}$而不规约出$\mathbf{s}$的办法，这样做有两点好处：

  • 由于目标向量中不再出现$\mathbf{s}$，因此格可以降$n$维，提升了规约速度
  • $\mathbf{s}$本身代表$n$个$GF(p)$下的随机变量，完全不能算小量，因此对格规约基本起不到帮助，去掉他也可以排除掉这层影响

说起来简单，但是之前那篇文章介绍原理和实现的时候看上去却有些麻烦。

然而一旦切换到现在这种视角一切就很好解释的通了，整个primal attack的步骤其实就是：

  • 消元消去$n$个$\mathbf{s}$代表的变量，将原来的$m$个等式、$m+n$个变量的线性系统转化成的$m-n$个等式、$m$个变量的线性系统
  • 此时剩余的$m$个变量即为$\mathbf{e}$，因此规约这个线性系统即可

理解起来容易，实现则更简单，由于：

而对这样的$L$做个行阶梯消元并去掉零行，得到的方阵就是我们最终的格$L’$，也即primal_attack做了优化之后的攻击格。

思路

依然用上述角度来审视一遍题目，现在的LWE的线性系统其实是：

  • $\mathbf{s}$代表的$n$个$GF(p)$下的随机变量
  • $\mathbf{e}$代表的$m$个$GF(p)$下的有限制变量
  • $m$个由上述$m+n$个变量构成的线性等式

特殊之处在于这里的$\mathbf{e}$的限制是已知的三个值中的随机采样。

尝试

按之前的题的经验(如easy_mod，0CTF的signin，以及今年刚出的HITCON的BabyLWE等)，由于本题给出了$e$的取值范围$E$，所以或许可以找到某种线性变换，使得$E$能映射为一个新取值范围$E’$，而这个新的$E’$三个值都较小，从而利于规约。但本题的$E$是纯随机取值，所以存在线性变换使得三个值都变小的概率极小。这一点可以用如下的格的思路验证：

我们的目的是找到一个线性变换：

这个线性变换：

  • $E’$较小
  • $k, t$未知

可以看出这其实就是格干的事情，较小的$E’$就是我们要规约出来的值，为此构造如下格：

规约出来的结果其实也就是理论能找到的最短的$E’$了，代码及结果如下：

1
2
3
4
5
6
7
8
9
10
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_)
1
(-298, 582, -285)

可以看出得到的$E’$显然不够短，规约不了，所以需要改变策略。

预期

核心思想一句话就可以概括——提升变量的个数，来缩减变量的大小

前些天打过NSS 4th的这道LeetSpe4k的师傅应该多少会反应过来这样去做：将随机抽取三个值的过程，看作是未知的01向量和已知错误向量的内积，比如说对于任意一个分量$e_i$有：

其中$x_i,y_i,z_i \in \{0, 1\}$。

写到这去复制文章链接的才发现我完全忘记继续写那篇8月的wp总集了，有空再补上TT

这样子表示之后，整个系统显然依然是线性的，因此我们最初的LWE结构发生了改变：

  • $\mathbf{s}$代表的$n$个$GF(p)$下的随机变量
  • $\mathbf{e}$代表的$3m$个$GF(p)$下的01变量
  • $m$个由上述$3m+n$个变量构成的线性等式

而之前可能有见过以下几个题目的敏锐一点的师傅应该能察觉到一个更深的事实：

  • LilCTF的Space Travel
  • 2024 NKCTF的EZ_random
  • 甚至更早的2023 SEKAICTF的Noiser CRC

刚刚做的$x_i,y_i,z_i \in \{0, 1\}$的限制其实完全不到位，因为这几个01变量明显存在更强的限制：

而这样的三选一的结构存在一个仿射子空间，因此可以将三维降成两维，也就是：

此时有：

可以看出这样降维完全不改变新的变量均为01变量这一件事，因此这样操作之后LWE最终变成了：

  • $\mathbf{s}$代表的$n$个$GF(p)$下的随机变量
  • $\mathbf{e}$代表的$2m$个$GF(p)$下的01变量
  • $m$个由上述$2m+n$个变量构成的线性等式

此时我们想要应用优化后的primal attack，也就是消元将$n$个$\mathbf{s}$代表的变量消掉，就会得到最终需要的结果：一个由$m-n$个等式、$2m$个01变量构成的线性系统。

此时要做的事情似乎所剩不多了——构造一个$2m+1$大小的格，规约出这$2m$个01变量似乎就好，但是……

优化

可以看出，通过上述方式转化后的LWE问题，我们的目标向量大小是和模数$p$完全无关的。而对于越大的$p$，我们的目标向量在格中会显得越短，求解也会越容易。

格中最短向量$\lambda_1(L)$和次短向量$\lambda_2(L)$的Gap越大越利于求解，这是由于格基规约算法的第一行向量的上界与实际的$\lambda_1(L)$有关

而问题出在这里，虽然本题最终的格是181维，在如此多的CTF挑战中完全不算大，但本题的$p$是20bit左右的数量级，因此Gap的差距并没有到很夸张的地步，所以求解出作为最短向量的目标向量是一个问题。为此需要做一点优化才行。

第一个优化其实老生常谈，对于规约01变量的问题，比如背包，采用$2x-1$将其映射到$1,-1$就是个很常用的优化，这样的优化本质上是做了一个类似$01$到$\frac{1}{2}, -\frac{1}{2}$的balance，因此提高了Gap，降低了求解SVP的难度。

第二个优化可能小众一点：

由于最后的问题在于约化能力，因此自然要选能求解短向量能力更强的算法，朴素一点讲的话就比如LLL求不出来就换成BKZ，BKZ做不出来就继续抬高blocksize，大多数师傅应该都这样做过。

对于这道题目来说可以用筛法或者blocksize更大的BKZ去尝试求解，打过今年高校密码挑战赛的师傅应该会听说blaster这样一个黑科技，虽然他需要格的entry比较小(小于32bit或者64bit，似乎取决于具体的机器数)，但是在符合要求的情况下可以很快地实现blocksize较大的BKZ算法，而本题最终可以用blaster求解，在个人电脑跑的话大概五六分钟左右。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
from subprocess import check_output
from re import findall

def blaster(M, block_size=40, bkz_tour=5):
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    open("Lattice_test", 'w').write(z+'\n')

    ######################################## if need verbose, add "-v"
    ret = check_output([
        "python3", "./src/app.py",
        "-i", "Lattice_test", "-b" + str(block_size), "-t" + str(bkz_tour), "-v"
        ])
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
1
2
gift = 
enc = 
1
2
3
4
5
p = 1048583
m, n = 90, 64
E = gift[:3]
A = Matrix(Zmod(p), m, n, gift[3:3+m*n])
b = vector(Zmod(p), gift[3+m*n:])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
nums = m

A_ker = A[:nums].left_kernel().matrix()
Fp = Zmod(p)
V = Fp["".join(["x"+str(i)+", " for i in range(nums)]) + "".join(["y"+str(i)+", " for i in range(nums)]).strip(", ")]
x, y = vector(V.gens()[:nums]), vector(V.gens()[nums:2*nums])

XY = (Matrix(x).stack(Matrix(y))).T
ve = vector(Zmod(p), [E[1]-E[0], E[2]-E[0]])
XYe = XY*ve

polys = A_ker*XYe - A_ker*(b[:nums]-vector([E[0]]*nums))
M, V = Sequence(polys).coefficients_monomials()
M = M.T.dense_matrix()
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
#################################################################### use reduction
M1, M2 = M[:nums-n], M[nums-n:]
if(1): #2x-1 method
    L = block_matrix(ZZ,[
        [2, -2*M2*M1^(-1)],
        [0, p]
    ])
    for i in range(nums+n):
        L[nums+n, i] = -1
    L[nums+n, nums+n] = 1
    for i in range(nums-n):
        L[nums+n, -(i+1)] -= 1

if(0):
    L = block_matrix(ZZ,[
        [1, -M2*M1^(-1)],
        [0, p]
    ])

print(L.dimensions())
L = blaster(L, 63, 5)
#L = g6k_reduce(L)
#L = L.BKZ(block_size=10)
print(L[0])
print(float(L[0].norm()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
res = vector(ZZ, L[0]).list()
res = res[nums+n+1:] + res[:nums+n]

recover_e = []
for i in range(nums):
    if(res[i] == 1 and res[i+nums] == 1):
        recover_e.append(E[0])
    elif(res[i] == -1 and res[i+nums] == 1):
        recover_e.append(E[1])
    elif(res[i] == 1 and res[i+nums] == -1):
        recover_e.append(E[2])
    else:
        recover_e.append("?")

print(recover_e)
1
2
3
4
5
6
7
8
9
from Crypto.Cipher import AES
from hashlib import md5

s = A[:nums].solve_right(b[:nums] - vector(GF(p), recover_e))
flag = AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc)
print(flag)


#WMCTF{extend_70_B1n@rY_R3pr3sent@ti0n!}


LemonPepper

题目

题目描述：

1
🍋🍋🌶️🌶️,🌶️🌶️🍋🍋,🦍🦍✋🌿⬆️;🍯🍯🔥🔥,🔥🔥🍯🍯,🐜🐜🏃🍃🏠

题目：

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
from random import randrange
from Crypto.Util.number import getPrime

with open('flag.txt') as f:
    FLAG = f.read().strip()

class flavorings:
    def __init__(self, p, l):
        self.l, self.p = l, p
        self.state = [randrange(p) for i in range(l)]
        self.a = [randrange(128) for i in range(l)]
    def __next__(self):
        s = choice([sum(self.state[i] ^ d * self.a[i] for i in range(self.l)) % self.p for d in range(1, 4)])
        self.state = [s] + self.state[:-1]
        return s

class LemonPepper:
    def __init__(self, q, t, e1, e2, p, l):
        self.q, self.t, self.e1, self.e2 = q, t, e1, e2
        self.mcg = flavorings(p, l)
    def Lemon(self):
        q, t, e1, e2 = self.q, self.t, self.e1, self.e2
        R.<x> = PolynomialRing(Zmod(q ^ e2))
        roots = [randrange(q ^ (e2-e1)) + sum(next(self.mcg) * q ^ (i + t) for i in range(e1))] + [randrange(q ^ e2) for i in range(t - 1)]
        return randrange(q ^ e2) * prod([(x - root) ^ choice(range(2,5)) for root in roots])
    def Pepper(self):
        q, t, e = self.q, self.t, self.e2
        R.<x> = PolynomialRing(Zmod(q ^ e))
        roots = [next(self.mcg) * q ^ 130 + randrange(q ^ 130) + randrange(q ^ 70) * q ^ 131 for i in range(t)]
        return randrange(q ^ e) * prod([(x - root) * (x - root - q ^ t) for root in roots]) * prod([x - root - q ^ 40 for root in sample(roots, 2)])

print('''💀 ORDER INCOMING!
"25-min RUSH RECIPE: 7x🍋 CUPS + 3x🌶️ DASHES! COOK NOW!"
⏱️ 24:59... 24:58...''')

__import__("signal").alarm(1500)

p, l = 257, 25
q, t, e1, e2 = 27658548947, 30, 135, 165
lemonpepper = LemonPepper(q, t, e1, e2, p, l)

print("🍋 Precision Zest Injection!")
for i in range(7):
    print(lemonpepper.Lemon().list())

print("🌶️ Chaotic Spark Ignition!")
for i in range(3):
    print(lemonpepper.Pepper().list())

print("SHOVE PLATES INTO PORTAL! 🛸🍽️ VALIDATE 🍋🌶️ COMBO OR KITCHEN MELTDOWN! 💣💥")
assert [int(i) for i in input("> ").split(',')] == lemonpepper.mcg.state

print(f"🍋🌶️ CHAOS COMBO! +500 EXTREME POINTS! ⚡💥 MUTANT FLAVOR UNLOCKED! {FLAG}")

这题就直接放@yolbby的原装wp了，原汁原味ρ(・ω・、)

wp

题目给出了flavorings类和LemonPepper类，其中flavorings类具有mcg结构，作为LemonPepper类的伪随机数生成器。整个题目给出了Lemon和Pepper两组数据，要求恢复最终flavorings类中的state。

1.第一个part，我们调用7次Lemon函数，其在$q^{135}$下返回

我们的目标是恢复$\text{root}_i$集合中包含伪随机数生成器的解，这可以通过求解$f$函数来完成。根据一般意义上的Hensel Lift，对于$f$的一个解$x$，有迭代公式

而在重根的情况下，存在

我们没法直接进行Hensel Lift来获得$q^k$上的解$x$（这也是在SageMath中使用.roots函数会卡住的原因）。要在这个条件下对方程进行求解，我们就要想办法把方程从重根方程变成无重根方程。由于本题的根的重数在$\{2,3,4\}$中选取，因此我们对函数式进行三次求导，就能够将重数为$4$的根保留在多项式中。构建函数$g$如下

$g$在$p^{165}$上是可解方程。故我们可以恢复所有的重数为$4$的解，恢复后将重数为$4$的项从$f$中删除，即可将函数式的重数选取范围降至$\{2,3\}$。以此类推，即可完成Lemon部分的求解。

2.求解完7个多项式的解，我们可以恢复得到mcg的$945$个生成量。观察mcg的生成函数，有

使用全线性化处理式子，有

我们共有$m=945$个式子，但存在$\tbinom{n+3}{n}=3275$个单项式，式子数量远小于单项式数量。故采取Arora-Ge使用的技巧增加样本数量：对于任意一个式子，我们对其分别乘以所有度小于$d$的单项式，此时式子数量变成$m\tbinom{n+d}{d}$，单项式数量变成$\tbinom{n+d+3}{n}$。取$d=1$，当样本数量为$m=914$时，式子数量为$23764$，单项式数量为$23750$。而为了构成方程，我们还需要额外的$n$组样本，总共需要$939$个mcg输出，小于我们拥有的输出量。构造对应的矩阵方程，我们可以完整求解得到所有的$a_i$。

3.恢复所有的$a_i$后，我们已经拥有了mcg的完整状态，即使如此，mcg的每一次随机数生成都伴随着一次随机的三选一，因此我们仍然需要去跟进mcg的输出。对于第二个part，我们调用三次Pepper函数，其在$q^{165}$下返回

相比part1，本部分生成了一个在低指数下具有重根的式子。即使采用part1中的方法，我们也只能在$q^{30}$上求出对应的解，想要继续抬升，则又会受到导数等于$0$的限制。而$q$的大小为$30$bit，意味着我们无法采用爆破的方式去进行深搜。这样，我们只能采取在p-adic域上定义函数，以牺牲精度为代价求取一定范围上的解。对于本题，我们可以在$q^{135}$上恢复所有不在$sample(\text{roots},2)$中的元素的解。这样，我们也就变相得到了30组mcg生成随机数中的28组，其顺序未知。

4.由于在part2之前整个mcg类对我们而言已经透明，而求解得到的列表包含30组随机生成数中的28组，我们可以采用剪枝算法来确定生成顺序的唯一解。注意到剪枝过程中可能会出现多解，成功存在一定概率性，成功率大概为70%左右。

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
from Crypto.Util.number import *
from time import time
from pwn import *

def solvelemon(p, poly, e = 165):
    R.<x> = PolynomialRing(Zmod(p^e))

    poly = R(poly)
    def gcd(x, y):
        while True:
            x, y = y, x % y  
            if y == 0:
                return x
                
    for i in range(3):
        g = poly
        for j in range(3-i):
            g = diff(g)

        for j in gcd(poly,g).roots(multiplicities=False):
            ans = int(j)
            s = []
            for _ in range(165):
                s.append(int(ans % p))
                ans //= p
                
            if all([_ < 257 for _ in s[30:]]):
                return s[30:]
            poly //= (x-j)^(i+1)

def linearation(c):
    from tqdm import trange

    p, n = 257, 25
    R = PolynomialRing(GF(p),[f'x{i}' for i in range(n)])
    x = [i for i in R.gens()]+[1]
    
    dic = {}
    m = []
    v = []
    for i in trange(914):
        f = prod(sum(c[i:i+n][j]^d*x[j] for j in range(n))-c[i+n] for d in range(1,4))
        for d1 in range(n+1):
            vr, term = 0, x[d1]
            g = f*term
            coes, mons = g.coefficients(), g.monomials()
            mr = [0 for i in range(23750)]
            for mon,coe in zip(mons,coes):
                if mon == 1:
                    vr = -coe
                    continue
                if mon not in dic.keys():
                    dic[mon] = len(dic)
                mr[dic[mon]] = coe
            m.append(mr)
            v.append(vr)
            
    v = matrix(v)
    al = matrix(GF(p),m).T.solve_left(v).list()
    a = []
    for i in x[:-1]:
        a.append(al[dic[i]])
    return a
    
def solvepepper(poly, e = 165):
    R.<x> = PolynomialRing(Zmod(p^e))
    f = R(poly)
    
    Qpp = Qp(p, prec=e)
    R.<x> = PolynomialRing(Qpp)
    re = R(f).roots()
    
    nexts = []
    for i in re:
        ans = eval(str(i[0]).split('O')[0][:-3].replace('^','**'))
        if ans.bit_length() > 4000:
            nexts.append(int(ans%p^135)//p^134)
    return nexts[::2]

def guess(s, a, nexts, label):
    global ans
    if nexts == [-1]*25:
        ans = s
        print(1)
    nc = [sum(s[i] ^ d * a[i] for i in range(30)) % 257 for d in range(1, 4)]
    for i in nc:
        if i in nexts:
            nexts1 = deepcopy(nexts)
            nexts1[nexts1.index(i)] = -1
            guess([i]+s, a, nexts1, label)
        else:
            if label < 5:
                guess([i]+s, a, nexts, label+1)


from pwn import *
context.log_level = 'error'

p = 27658548947
re = remote('',)

re.recvuntil(b'Injection!\r\n')
s = []
for i in range(7):
    s += solvelemon(p,eval(re.recvline()))
print(s)
a = linearation(s)[::-1]
s = s[-25:][::-1]

re.recvuntil(b'Ignition!\r\n')
for i in range(3):
    nexts = solvepepper(eval(re.recvline()))
    global ans
    ans = []
    guess(s,a,nexts,0)
    s = ans[:25]

re.recvuntil(b'> ')
re.sendline(str(s)[1:-1].encode())
print(re.recvline())
print(re.recvline())

非预期

这个题的唯一解来自@Aqua Cat他们的非预期，其实从预期的角度他们赛中已经完成了大部分，但是非预期bypass掉了最关键也最难的全线性化那一步，而bypass的方式是：

1
2
3
4
5
6
███╗   ███╗████████╗
████╗ ████║╚══██╔══╝
██╔████╔██║   ██║   
██║╚██╔╝██║   ██║   
██║ ╚═╝ ██║   ██║   
╚═╝     ╚═╝   ╚═╝

哈哈，继@hashhash昨年N1CTF的Matrix、我今年红明谷的EcBag相继被MT以奇怪的姿势打掉之后，MT依然生命力旺盛，最终在这次坑了@yolbby一把。

而能用MT打的部分在于randrange(q^e)，虽然由于会存在一定概率的reject导致这并不能完全等同于getrandbits的连续输出，但是概率不算很大的情况下19年BalsnCTF的unpredictable这道题目给了一个解法，所以可以跳过全线性化的步骤直接进行预测。

random能不用真的还是不用的好，防不胜防哈哈哈


LW5

题目

题目描述：

1
LW:5

题目：

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
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))

类似LW3，但这一次可以自己输入5个error作为随机选取的值，而对于输入的error会做check，主要需要满足：

  • 模$p$意义下互不相同
  • 无法直接线性映射到一个均较小的值

此外对参数$n$进行了略微降低，从64改到了56，依然是要攻破这个LWE的私钥$\mathbf{s}$从而拿到flag。

思路

其实出完这个题目的时候很担心有奇怪的逃课的姿势，不过仔仔细细想了一圈也没有太想到，虽然最终没有出现什么非预期，但是可能会被偷鸡的隐患隐隐约约感觉还是存在。

毕竟check实在长得有点奇怪XD

言归正传，聊回这个题目的思路。如果完全理解了LW3的话肯定很自然的就会类似想到：由于同样限制了不能直接将五元的错误集合线性映射到各分量都较小的情况，因此继续采用转成$4m$个01变量的方式，然后去规约$4m+1$的格。然而$4m+1$有361维，虽然不能说很大但绝对也不算小，并且由于格的维数上去了而约束数量没有变，因此Gap缩小的很快，极端一点甚至没有办法保证目标向量还是最短向量，更不用说规约出来了。

此时需要一个tradeoff的思想，我们可以想到直接线性映射的情况大概是$m$个$\sqrt{q}$数量级的变量，而二进制展开则是$4m$个01变量，那么有没有办法构造一个错误集合，使得其转化后变量数量增多的不多，而且变量的数量级也不大？

这当然是可以做到而且可以轻松做到的，回顾这两种方法其实能找到一种共性：都是找到一个基$g$，使得其能够用较小的系数线性表示出所有可能的error。比如对于直接的线性映射，可以写为：

这里的$X$矩阵实际也就是$\mathbf{e}$经线性映射能达到的最小的$\mathbf{e}’$。

而对于二进制展开(不利用仿射子空间降维)，可以写为：

此时$X$矩阵即为每一行有且仅有一个1的01矩阵。

而利用仿射子空间降维后的二进制展开则可以写为：

此时$X$的每一行分别为$(0,0,0,0),(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)$。

所以，当线性映射界不够而二进制展开格维数又过大时，可以考虑找一组相对来说维数较小、对应矩阵$X$分量值也较小的基$\mathbf{g}$，从而尽量辅助最后的规约。并且本题由于$\mathbf{e}$能自定义输入，因此只需要自行构造一个小$X$矩阵，并随机生成$\mathbf{g}$直至满足题目对于$\mathbf{e}$的其余限制即可。

此后的展开过程和LW3就完全一样了，最后同样用了blaster来帮助找到短向量。

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
from subprocess import check_output
from re import findall

def blaster(M, block_size=40, bkz_tour=5):
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    open("Lattice_test", 'w').write(z+'\n')

    ######################################## if need verbose, add "-v"
    ret = check_output([
        "python3", "blaster/src/app.py",
        "-i", "Lattice_test", "-b" + str(block_size), "-t" + str(bkz_tour), "-v"
        ])
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
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
from pwn import *
from ast import literal_eval

context.log_level = "critical"

#sh = process(["sage", "chal.sage"])
sh = remote("62.234.62.107", 30617)
#sh = remote("localhost", 10007)
sh.recvuntil(b"your error plz :)")
sh.sendline(str([259832, 985692, 628744, 767011, 478513]).encode())

gift = literal_eval(sh.recvline().strip().decode()[4:])
enc = literal_eval(sh.recvline().strip().decode()[4:])

p = 1048583
E = [259832, 985692, 628744, 767011, 478513]
g = (725860, 184456)
m, n = 90, 56
A = Matrix(Zmod(p), m, n, gift[:m*n])
b = vector(Zmod(p), gift[m*n:])
nums = 5

from Crypto.Util.number import *
d = m

A_ker = A[:d].left_kernel().matrix()
Fp = Zmod(p)
V = Fp["".join(["x"+str(i)+", " for i in range(d)]) + "".join(["y"+str(i)+", " for i in range(d)]).strip(", ")]
x, y = vector(V.gens()[:d]), vector(V.gens()[d:2*d])

XY = (Matrix(x).stack(Matrix(y))).T
ve = vector(Zmod(p), g.list())
XYe = XY*ve

polys = A_ker*XYe - A_ker*(b[:d]-vector([E[0]]*d))
M, V = Sequence(polys).coefficients_monomials()
M = M.T.dense_matrix()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#################################################################### use reduction
M1, M2 = M[:d-n], M[d-n:]

if(1):
    L = block_matrix(ZZ,[
        [1, -M2*M1^(-1)],
        [0, p]
    ])

print(L.dimensions())
L = blaster(L, 63, 10)
#L = L.BKZ(block_size=10)
print(L[0])
print(float(L[0].norm()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
res = vector(ZZ, L[0]).list()
nums = m
res = res[nums+n+1:] + res[:nums+n]

recover_e = []
for i in range(m):
    if(res[i] == 0 and res[i+nums] == 0):
        recover_e.append(E[0])
    elif((res[i] == -1 and res[i+nums] == 0) or (res[i] == 1 and res[i+nums] == 0)):
        recover_e.append(E[1])
    elif((res[i] == 0 and res[i+nums] == 2) or (res[i] == 0 and res[i+nums] == -2)):
        recover_e.append(E[2])
    elif((res[i] == 1 and res[i+nums] == -1) or (res[i] == -1 and res[i+nums] == 1)):
        recover_e.append(E[3])
    elif((res[i] == 2 and res[i+nums] == -1) or (res[i] == -2 and res[i+nums] == 1)):
        recover_e.append(E[4])
    else:
        print(res[i], res[i+nums])
        recover_e.append("?")
print(E)
print(recover_e)
1
2
3
4
5
6
7
8
9
from Crypto.Cipher import AES
from hashlib import md5

s = A[:nums].solve_right(b[:nums] - vector(GF(p), recover_e))
flag = AES.new(key=md5((str(s)).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc)
print(flag)


#WMCTF{F1nD_@_BETTER_L1n3aR_b@SIS!}