D^3CTF 2023 WriteUps

發表於 分類於

這次自己在 nyahello 隊伍中稍微打了一下，解了四題中的三題 crypto，難度我覺得都不容易所以可以寫一下 writeup。

d3bdd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from util import *
from hashlib import *
import os
from secret import flag
from Crypto.Util.number import *

assert flag[:9] == b'antd3ctf{' and flag[-1:] == b'}' and len(flag) == 64
assert sha256(flag).hexdigest() == '8ea9f4a9de94cda7a545ae8e7c7c96577c2e640b86efe1ed738ecbb5159ed327'


seed = sha256(b"welcome to D3CTF").digest() + sha256(b"have a nice day").digest()
A = sample_poly(seed , 0 , 2**32 - 5)
e = sample_poly(os.urandom(64) , -4 , 4)
s = encode_m(flag)
b = A*s + e
print(b.f)

其中的 util.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
from Crypto.Util.number import *

class PRNG:
    def __init__(self , seed):
        self.state = bytes_to_seedlist(seed)
        
        self.m = 738136690439
        # f = [randint(0 , m) for _ in range(16)]
        self.f = [172726532595, 626644115741, 639699034095, 505315824361, 372926623247, 517574605128, 185188664643, 151765551359, 246806484646, 313551698318, 366113530275, 546914911952, 246941706000, 157807969353, 36763045564, 110917873937]
        self.mbit = 40
        self.d = 16
        for i in range(self.d):
            self.generate()
    def generate(self):
        res = 0
        for i in range(self.d):
            res += self.f[i] * self.state[i]
            res %= self.m
        self.state = self.state[1:] + [res]
    def raw_rand(self):
        temp = self.state[0]
        self.generate()
        return temp



q = 2**32-5
n = 512
class polynomial:
    
    # polynomial in Zq[x]/(x^n - 1)

    def __init__(self,flist):
        if type(flist) == list:
            assert len(flist) == n
            self.f = [flist[i] % q for i in range(n)]

    def __add__(self , other):
        assert type(other) == polynomial
        return polynomial([(self.f[i] + other.f[i])%q for i in range(n)])
    def __sub__(self , other):
        assert type(other) == polynomial
        return polynomial([(self.f[i] - other.f[i])%q for i in range(n)])
    def __mul__(self , other):
        assert type(other) == polynomial
        res = [0]*n
        for i in range(n):
            for j in range(n):
                res[(i+j)%n] += self.f[i] * other.f[j]
                res[(i+j)%n] %= q
        return polynomial(res)

def bytes_to_seedlist(seedbytes):
    seedlist = []
    for i in range(16):
        seedlist.append(bytes_to_long(seedbytes[i*4:i*4+4]))
    return seedlist

def sample_poly(seed , lower , upper):
    prng = PRNG(seed)
    polylist = []
    for i in range(n):
        polylist.append((prng.raw_rand() % (upper - lower)) + lower)
    return polynomial(polylist)
def encode_m(m):
    m = bytes_to_long(m)
    flist = []
    for i in range(n):
        flist = [m&1] + flist
        m >>= 1
    return polynomial(flist)

簡單來說這題在 下做用 RLWE 加密 flag，符合 。其中的 是使用一個 MRG (Multiple Recursive Generator, LCG 的延伸) 生成的。按照題目 hint 和我最後得到的 flag 知道預期解是用 dual attack 做的，不過我這邊是用 unintended 解的。

關鍵在於這題 ，而 在 上是可分解的:

1
2
3
sage: P.<x>=ZZ[]
sage: factor(x^512-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)

所以對於每個因子 都符合 ，只要 degree 夠小的話就能直接用 LLL 解 modulo 的值，最後再 CRT 回去即可。這個其實就是之前 HackTM CTF 中我沒解的 GLP420 的核心概念。

然而這題有個小問題是這邊最大的 ，經我測試發現這樣 LLL 找不到我們預期的 short vector，所以解不開。後來花了一段時間才想到說它 flag format 是固定的，可以利用已知的資訊刪掉一些 bits 然後讓 LLL 比較容易找到我們需要的目標。這部分的細節就是一些變數的代換而已，詳情可以參考我的 solver。

我的 solver 主要是拿 Neobeo 之前的 solver 來改而成的，一樣使用了 flatter 來大大改善了 LLL 所花費的時間。

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
# based on https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage and https://github.com/y011d4/my-ctf-challenges/blob/main/2023-HackTMCTF-2023/crypto/glp-420/sol/solve.sage
# obviously unintended :)
from sage.all import *
from util import sample_poly, encode_m
from hashlib import sha256
from subprocess import check_output
from re import findall
from time import time
from binteger import Bin

seed = sha256(b"welcome to D3CTF").digest() + sha256(b"have a nice day").digest()
Af = sample_poly(seed, 0, 2**32 - 5).f
# fmt: off
Bf = [3926003029, 1509165306, 3106651955, 2983949872, 2393378576, 284179519, 2886272223, 1233125702, 3238739406, 2644118828, 3957954911, 3691185583, 1700019866, 2347785071, 1123825909, 2465646007, 401380313, 2707319872, 4202699559, 931784437, 3583947386, 2536644387, 2751259493, 1013056277, 1594454226, 3085910471, 3351540180, 2578522714, 2124408803, 1473642602, 2384063470, 215471267, 2252434344, 840082094, 1706153260, 628595906, 2138641953, 1768585251, 3672294042, 2648955311, 1101545943, 1462829980, 2490861499, 3154433480, 3991951537, 4073147435, 3072173371, 2030645383, 2273617209, 610264621, 698372144, 965611111, 3030212709, 3123517391, 1661563411, 2903488892, 4125601987, 3275402564, 3358433812, 1301393717, 183795461, 1088441539, 2652556595, 2457427974, 358582424, 3817487396, 3425059438, 3815131707, 3220004354, 3593522122, 323522616, 2934869693, 1474202000, 3934228907, 2196320858, 789973717, 2041502218, 3287331728, 4058939697, 4049446313, 348017657, 312085362, 2087430022, 2409976112, 4182313358, 2820922003, 3439144715, 2835376655, 4164304483, 3992296837, 713727154, 3972583007, 2995414574, 2136905409, 2369686792, 4225590417, 2855379895, 2894275304, 4218198385, 1863573123, 152470219, 209356356, 2181932671, 87528118, 1509977039, 4251082194, 2394181037, 2698855020, 2791852460, 2343631203, 3588377079, 3883095017, 950749052, 1959173107, 444526794, 1655217840, 1576152947, 1208885396, 1891439027, 2519060478, 3957349805, 2330774404, 1021949515, 626605966, 1495609785, 3059250785, 10735841, 631635858, 2165633772, 1024411702, 1473058591, 1486765493, 1116319646, 2246642032, 136293218, 2809056783, 1207288553, 2490191164, 2022388061, 685418618, 1646546899, 2121499626, 1520638759, 2692413636, 1600251896, 1096615514, 377802389, 2828283506, 1184471637, 1095772453, 2518678208, 2091649527, 2790341258, 2122133496, 2008741414, 1931789532, 3407552039, 2037926317, 3785173109, 537388020, 1347520697, 555823746, 45926964, 2223751155, 2244475841, 1543489738, 722236260, 509055199, 3467634480, 580843748, 1285583898, 762172276, 174622846, 3028903527, 3614079217, 1967089235, 2384435424, 2300454112, 1916488680, 1677513486, 3104896162, 3091029091, 2119463387, 4203135624, 2423205596, 4230847292, 2736568150, 1684068, 4250784177, 741156803, 3460657451, 3249083929, 2818353339, 1641238652, 2040105975, 4195607442, 1149072667, 3335478071, 1960764664, 3978941663, 3482443697, 2656259541, 2956574333, 1327577034, 2436857858, 2073805906, 1802723277, 2678500274, 2972947230, 3132107182, 3467032578, 2426347344, 882119229, 3525375754, 10703769, 2277849193, 2317934043, 4065668868, 1502526735, 2829798591, 491620775, 996910215, 917195400, 1260108701, 2336814388, 37709213, 2901142063, 237197224, 1598485695, 2742667143, 1006207745, 1310704554, 534238429, 3112353574, 2380924842, 488678141, 2362251562, 3671650202, 1373474649, 3770563775, 938589647, 1910576969, 2028715086, 2361257827, 2670923858, 3965429861, 3439583492, 2533589001, 3994264580, 939094829, 3362711263, 704355043, 2954166903, 3966370527, 507768808, 556128950, 113005142, 801326514, 2148700895, 3781985160, 509773408, 3517580267, 2066978314, 2580741498, 3483049277, 3402728951, 1376657292, 1005665197, 2226368584, 1962189041, 671306169, 3775557986, 829941861, 2266480501, 3373215874, 2066458459, 3942151992, 836495238, 3356308384, 1790629422, 577081693, 3896293081, 3143007239, 29998790, 3635296087, 1778531590, 3529468062, 1032288519, 4158133379, 670147084, 786100224, 4145211264, 3106208132, 2414940297, 816565256, 2421147924, 1115269055, 84397462, 450125894, 2616534041, 933989700, 2830477525, 3491928047, 1947624924, 2686771420, 2902325901, 160232448, 3325505253, 2612766083, 2059426891, 3360947950, 2872564882, 1622992720, 2098871616, 431960929, 4066245272, 846589370, 3614792013, 869087998, 3621673292, 3219192545, 3554446061, 2122297338, 1894053711, 3712869523, 3175426433, 1121610839, 1230706582, 883221652, 3378895464, 4209309584, 2997558184, 409046034, 2009074657, 3796666708, 3103438558, 3534784496, 1554926466, 3746409084, 644630989, 847404069, 3238052834, 3158156927, 2168700780, 2867150561, 462828594, 3242835677, 3788069093, 2758603660, 1152155811, 1634934432, 3750823533, 1966238016, 3434703051, 2587050497, 369972874, 1571180588, 502826002, 1394977871, 4209562869, 3661291539, 655998304, 3002301529, 738694423, 1318870183, 1813578224, 2117155417, 2792274549, 469969773, 2885986431, 1205074516, 2141754983, 2119779464, 1794537683, 2109156365, 4041147529, 4112783190, 3639979267, 2833631339, 4023397109, 3724794745, 2898586369, 4243064815, 3173181480, 3547135838, 4216682410, 2537261684, 2850433542, 219483902, 243293295, 3201931974, 3383998262, 2891064412, 2210611534, 1659936487, 2238921384, 1601586549, 1727355629, 2573540630, 397538418, 3982181296, 592903988, 1371833230, 2459822880, 3557146354, 2701900698, 3989213446, 3905799266, 2347299592, 2697290465, 1591743964, 2197267136, 1589688875, 2236270312, 522765112, 3207165428, 1317506342, 3816533175, 1982758394, 3243657510, 3691510923, 3611761928, 1421484363, 2228564874, 2666808060, 340876439, 1909587779, 3453796155, 563826858, 3667231388, 3801779454, 1450891603, 114865654, 1771017530, 1269957854, 3247368682, 829473682, 765526246, 2549194701, 1799890469, 4040022163, 2804947409, 723163470, 2851338295, 743766905, 1623487669, 3706971079, 1857049314, 3001074984, 2428057325, 965966662, 4147994952, 3435363246, 840837590, 1851376608, 1264280015, 3969646217, 2330457493, 3252447459, 1425491214, 1800245805, 1416249314, 3749252176, 617972101, 2161483583, 507648049, 4125775896, 225981076, 1543568816, 1606049079, 3418639383, 4203621112, 2298305661, 918844283, 1829417811, 3035193519, 899008380, 1911356195, 2266791547, 3222899067, 40452845, 285832361, 3748962583, 1501732506, 3660444087, 115130006, 2069772771, 1407520491, 1003548491, 1077094436, 1418848957, 3098099734, 3358357308, 1389355789, 3500246690, 67778141, 630658758, 1075172903, 2989608028, 1987981397, 254794036, 2707266088, 950342808, 1590742759, 2671217284, 494050210, 1914378487, 4230572038, 1798463290, 1484078510, 2214019553, 2674514189]
# fmt: on

q = 2**32 - 5
n = 512
F = GF(q)["x"]
a = F(Af)
b = F(Bf)


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
]
# 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 = 512 // 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)
    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]]
L = lcm(ps[:-1])  # deg(L) = 256
s_mod_L = crt(rs, ps[:-1])  # this is s (mod L)
e_mod_L = (b - a * s_mod_L) % L
print(s_mod_L)
print(e_mod_L)

# use known information to simplify the problem
ks = F(encode_m(b"antd3ctf{" + b"\x00" * (64 - 9 - 1) + b"}").f)
l = 8 * 9
# a(ks+s'*x^l)+e = b
# a*x^l*s'+e=b-a*ks
# deg(s') = 8*(64-9-1) = 432
ap = (a * x**l) % (x**n - 1)
bp = (b - a * ks) % (x**n - 1)
sp_mod_L = (s_mod_L - ks) * inverse_mod(x**l, L) % L

# a'*(sp_mod_L+L*u)+e=b'
# a'*L*u+e=b'-a'*sp_mod_L
rem = ps[-1]
app = ap * L % rem
bpp = (bp - ap * sp_mod_L) % rem
# uu = u (mod rem)
# but since deg(u) = 512-8*(9+1)-256, uu = u
uu = solve(rem, app, bpp, slen=512 - 8 * (9 + 1) - 256)  # ~10min

print(Bin(list((sp_mod_L + L * uu) * x**l + ks)).bytes)
# antd3ctf{Dual^attack_1s_real1y_inteRest1ng!@#$L@tT1ce_MaSter!!!}

d3pack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from random import *


p = getPrime(1024)
n = 50  
m = 180  

flag = b''
assert len(flag) == 48
secret = []
s = bytes_to_long(flag)
for i in range(n):
    secret.append(randint(0, p))


alpha = vector(secret)
x = [vector([randint(0, 1) for i in range(n)]) for j in range(m)]
e = vector([randint(0, p) for i in range(m)])
h = vector([(alpha * x[i] -s * e[i])% p for i in range(m)])

print("p={}\n\ne={}\n\nh={}".format(p, e, h))

這題有 ，未知的部分有 binary matrix 、 還有個數 是 flag。已知的是向量 符合 。

從 那邊一看就讓我想到 HSSP (Hidden Subset Sum Problem)，所以我就先用 LLL 找了 符合 ，那麼 。既然 是 binary matrix，這邊和一般的 HSSP 一樣我們可以預期 的前 rows 是 的 orthogonal lattice basis，所以再一次 LLL 就能求得 了。

求得 之後之後想求 會發現我們還不知道 ，我這邊是再用一次 LLL 找使 的 ，那麼從 就能解出 。

解出來之後會發現 和 順序都不太對，但那個不重要，只要 正確即可。之後只要用 就能拿到 flag 了。

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
from Crypto.Util.number import long_to_bytes

n = 50
m = 180

with open("output.txt") as f:
    exec(f.read())

F = GF(p)
h = vector(h)
e = vector(e)


def find_ortho_fp(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))], [ZZ(p), 0]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= p
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


def find_ortho_zz(*vecs):
    assert len(set(len(v) for v in vecs)) == 1
    L = block_matrix(ZZ, [[matrix(vecs).T, matrix.identity(len(vecs[0]))]])
    print("LLL", L.dimensions())
    nv = len(vecs)
    L[:, :nv] *= p
    L = L.LLL()
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


Mhe = find_ortho_fp(h, e)
assert Mhe * h % p == 0
assert Mhe * e % p == 0
# Mhe[: m - n] is expected to be orthogonal to x
Lx = find_ortho_zz(*Mhe[: m - n]).T
# this should work:
# alpha = Lx.solve_right(h + s * e)
# but we don't know s, so we find a orthogonal basis to e to remove e
Me = find_ortho_fp(e)
assert Me * e % p == 0
alpha = (Me * matrix(F, Lx)).solve_right(Me * h)
xa = Lx * alpha
s = (xa - h)[0] / e[0]
print(long_to_bytes(int(s)))
# d3ctf{G3eat1_1t_i5_ea51_f0r_y0u_t0_break_ahssp!}

根據 flag 我們知道這個叫做 AHSSP，查了一下才發現原來 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem 的 Appendix G 就有提到這個問題了 (Affine Hidden Subset Sum Problem) XD

d3noisy

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
from Crypto.Util.number import *
from random import shuffle
from sympy import nextprime

def getKey():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    N = [getRandomNBitInteger(3211) for _ in range(15)]
    d = 0
    for _ in N:
        d = d ^ _
    d = nextprime(d)
    e = inverse(d,(p-1)*(q-1))
    return N, n, e

def leak(N):
    p,S = [],[]
    for i in range(15):
        p.append(getPrime(321))
        r = [N[_]%p[i] for _ in range(15)]
        shuffle(r)
        S.append(r)
    return p, S

m = bytes_to_long(flag)
N,n,e = getKey()
p,S = leak(N)
c = pow(m,e,n)

print(f"n = {n}")
print(f"p = {p}")
print(f"S = {S}")
print(f"c = {c}")

這題 RSA 的 是 ，而 都是未知的數。特別的地方是它有隨機取一些比較小的質數 然後計算 ，之後 shuffle 每個 row ( index 不固定)。

如果沒有 shuffle 的話這題很簡單，直接 CRT 就能求 了，但是 shuffle 之後就造成了很大的麻煩。

我是在看到 的時候發現 遠比 大，所以直覺告訴我這題也和 LLL 有關。

仔細想一下 CRT 的流程會發現 CRT 的其實是可以分開來做的，例如先取 符合

那麼對於一個 的系統，可以得出解為 。

所以如果假設 沒有 shuffle 過，然後假裝 和 以及 分別是矩陣和向量的話可以寫出 的關係式。

但是 有 shuffle 過，所以 並不是 ，但是我們知道 中肯定有某些 entries 加總起來 之下會是 。此時利用 相對於 比起來不大的這個事實，會發現只要把 這個矩陣攤平，然後用類似 knapsack 的 lattice 寫出來就能預期有個 的 short vector，其中 。

所以平衡一下 lattice 的權重之後 LLL 再取前 15 個 basis 就能得到所有的 了，然後求 之後 RSA 解密拿到 flag。

這邊我一樣還是用 flatter 取代 LLL，發現速度上真的快上非常的多 XD。

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
from sage.all import *
from Crypto.Util.number import long_to_bytes
from sympy import nextprime
from subprocess import check_output
from re import findall
from operator import xor


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


with open("out.txt") as f:
    exec(f.read())

T = [crt([0] * i + [1] + [0] * (15 - i - 1), p) for i in range(15)]
A = sum([list(t * vector(s)) for t, s in zip(T, S)], [])
M = block_matrix(
    ZZ,
    [
        [vector([prod(p)]), vector([0] * 15 * 15)],
        [matrix(A).T, matrix.identity(15 * 15)],
    ],
)
K = 2**3211
M[:, 1:] *= K
# M = M.LLL()
M = flatter(M)
# LLL: more than 3 minutes
# flatter: ~20 seconds
M[:, 1:] /= K
d = reduce(xor, [abs(x) for x in M[:15, 0]])
d = nextprime(d)
m = pow(c, d, n)
print(long_to_bytes(m))
# antd3ctf{0c85f77e-bfee-da57-78f2-e961ffd4ca45}