2024L3HCTF

*代表赛时未解出的题

badrlwe

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 Crypto.Util.number import *
from random import *
import random
import numpy as np
from secret import flag, sk

assert len(flag[7:-1]) <= 64
data = [ord(i) for i in list(flag[7:-1])]

for i in range(len(sk)):
    assert data[i] == sk[i] 

q = 1219077173
R.<x> = PolynomialRing(Zmod(q), 'x')
N = 1024

f = x^N - 1

a = [0] * N
for i in range(N):
    a[i] = randint(0, q)

s = sk

e = [0] * N
for i in range(N):
    val = np.random.normal(loc=0.0, scale=2.1, size=None)
    e[i] = int(val)

a = R(a)
s = R(s)
e = R(e)
b = (a*s + e)%f

print(a)
print(b)
print(q)

题目就是构造了一个普通的rlwe，但是值得关注的是多项式\(x^N - 1\)可约 

1
2
3
sage: P.<x>=ZZ[]
sage: factor(x^1024-1)
(x - 1) * (x + 1) * (x^2 + 1) * (x^4 + 1) * (x^8 + 1) * (x^16 + 1) * (x^32 + 1) * (x^64 + 1) * (x^128 + 1) * (x^256 + 1) * (x^512 + 1)
进行一个RLWE to CVP，降维至128可造格求解。让我想到D^3CTF的d3bdd当时多项式也可约，预期解其实是Dual Attack，但被这种做法非预期了，于是直接对着maple师傅的脚本改了一下。 
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
from sage.all import *

# 定义多项式环
q = 1219077173
N = 1024
R = PolynomialRing(Zmod(q), "x")

# 输入的字符串
a = 

# 将字符串转换为多项式
polynomial = R(str(a))

# 提取系数
a = polynomial.coefficients()

b = 
polynomial = R(str(b))

# 提取系数
blist = polynomial.coefficients()

q = 1219077173
n = 1024
F = Zmod(q)["x"]
a = F(a)
b = F(blist)


x = F.gen()
ps = [
    x - 1,
    x + 1,
    x**2 + 1,
    x**4 + 1,
    x**8 + 1,
    x**16 + 1,
    x**32 + 1,
    x**64 + 1,
    x**128 + 1,
    x**256 + 1,  # too big for LLL/flatter to solve svp
    x**512 + 1,
]
# this must hold over Z[x] instead of Zq[x]
assert prod(ps) == x**n - 1


# def flatter(M):
#     # compile https://github.com/keeganryan/flatter and put it in $PATH
#     z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
#     ret = check_output(["flatter"], input=z.encode())
#     return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))


def solve(poly, a, b, slen=None):
    # solve for a*s+e=b (mod poly)
    # where s and e are small
    # and len(s) = slen
    global mat, mat2
    n = poly.degree()
    if slen is None:
        slen = n
    print(f"Try solving with deg(poly) = {n}")
    t0 = time()
    main_block = matrix([vector(a * x**i % poly) for i in range(n)])
    approx = 1024 // n  # approximation for the average of target vector
    mat = block_matrix(
        ZZ,
        [
            [1, -main_block, 0],
            [0, q, 0],
            # kannan embedding
            [
                0,
                matrix(vector(b % poly)),
                matrix([[approx]]),
            ],
        ],
    )
    mat[:, slen:n] *= q  # force zero
    print(f"Lattice size = {mat.dimensions()}")
    # mat2 = flatter(mat)
    mat2 = mat.LLL()
    print(f"{mat.nrows()}x{mat.ncols()} lattice reduced in {time()-t0}")
    for ret in mat2:
        if ret[-1] < 0:
            ret = -ret
        if ret[-1] == approx:
            print(ret)
            print()
            return F(list(ret[:n]))


rs = [solve(p, a, b) for p in ps[:-1]]
a = [89, 48, 117, 95, 82, 64, 52, 49, 49, 89, 95, 75, 110, 48, 119, 95, 67, 121, 99, 108, 79, 116, 111, 109, 49, 99, 95, 80, 111, 108, 121,
     33, 65, 75, 64, 67, 111, 33, 60, 74, 62, 94, 53, 35, 68, 81, 125, 111, 68, 111, 61, 111, 40, 106, 55, 36, 37, 60, 49, 84, 56, 104, 49, 114]
for i in a:
    print(chr(i % 256), end="")
# Y0u_R@411Y_Kn0w_CyclOtom1c_Poly!AK@Co!<J>^5#DQ}oDo=o(j7$%<1T8h1r

babySPN

呃出题人把key给了，直接算哈希就行。

babySPN revenge

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
import random
import time
from secret import flag, K
from hashlib import sha256
from Crypto.Util.number import *

def bin_to_list(r, bit_len):
    list = [r >> d & 1 for d in range(bit_len)][::-1]
    return list

def list_to_int(list):
    return int("".join(str(i) for i in list), 2)

Pbox=[1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16]
Sbox=[14, 13, 11, 0, 2, 1, 4, 15, 7, 10, 8, 5, 9, 12, 3, 6]

def round_func(X,r,K):
    kstart=4*r - 4
    XX = [0] * 16
    for i in range(16):
        XX[i] = X[i] ^ K[kstart+i]
    for i in range(4):
        value = list_to_int(XX[4*i:4*i+4])
        s_value = Sbox[value]
        s_list = bin_to_list(s_value, 4)
        XX[4*i],XX[4*i+1],XX[4*i+2],XX[4*i+3] = s_list[0],s_list[1],s_list[2],s_list[3]

    Y=[0] * 16
    for i in range(16):
        Y[Pbox[i]-1]=XX[i]
    return Y

def enc(X,K):
    Y = round_func(X,1,K)
    Y = round_func(Y,2,K)
    Y = round_func(Y,3,K)
    Y = round_func(Y,4,K)

    kstart=4*5 - 4
    for i in range(16):
        Y[i] ^= K[kstart+i]
    return Y


assert len(K) == 32
for i in K:
    assert i == 0 or i == 1

hash_value = sha256(long_to_bytes(list_to_int(K))).hexdigest()
print(hash_value)
assert flag[7:-1] == hash_value

XX = [0]*16
for i in range(4):
    XX[i*4] = 1
    print(enc(XX,K))
    XX[i*4] = 0

# [0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
# [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0]
# [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1]
# [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1]

根据题目SPN去搜，一开始看了几篇线性分析的文章，但都看不太懂😭

但是直观来看直接爆破的话复杂度是232，但是最后四位只起异或作用，复杂度只有228，队内师傅多线程爆破出了。赛后看其余师傅们讨论，用MITM也可以打，还有看到用z3的。想着看到官方wp之后好好学一下线性分析，但似乎就是用z3之类的求解器求解0.0（以下是官方wp）

求解思路：构造 \(GF(2)\) 上的方程等式，用添加中间变量的方法降低MQ方程组的次数（线性化方法），然后用sage自带的sat求解器求解（sat方法）（先把 \(GF(2)\) 上的MQ方程转成CNF，然后喂给sage内置的sat求解器，其他的sat求解器也可）。这个方法大概也是20s出结果，但是可以有效求解密钥较长的情况（前提是网络简单）。

*can_you_guess_me

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from random import *
# from secret import flag
flag = getPrime(86)
print(long_to_bytes(flag))
q = getPrime(128)

n = 5
T = 2**48
E = 2**32

t = [randint(1, T) for i in range(n)]
e = [randint(1, E) for i in range(n)]
a = [(t[i] * flag - e[i]) % q for i in range(n)]
print('q =', q)
print('a =', a)

flag = "L3HSEC{" + hex(flag)[2:] + "}"

print('flag =', flag)

# q = 313199526393254794805899275326380083313
# a = [258948702106389340127909287396807150259, 130878573261697415793888397911168583971, 287085364108707601156242002650192970665, 172240654236516299340495055728541554805, 206056586779420225992168537876290239524]

题目很不错，但是很搞我心态，让我感觉到了格的玄学，自己造的格子怎么调就是规约不出来。

题目给了5组\(a_i=t_i*x+e_i \; mod \; q\)，加了模数的ACD，所以一开始思路很自然是消去\(x\)然后加上\(k_i*q\)，但这个格子我始终没调出来。

看官方wp后感觉这种方法确实妙，求出\(t_i\)后，利用\(a_i\)再去造HNP的格子求x。

还看了S1uM4i的wp，给了代码，过段时间研究一下造的格子。

CTF
2024L3HCTF
https://sch01ar.github.io/2024/02/06/2024L3HCTF/
作者
Roo1e
发布于
2024年2月6日
许可协议