D^3CTF 2023 WriteUps

發表於 2023-04-30

分類於 CTF

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

d3bdd

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:

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)

簡單來說這題在 $\mathbb{Z}_q[x]/(x^n-1)$ 下做用 RLWE 加密 flag，符合 $b(x)=A(x)s(x)+e(x)$ 。其中的 $e$ 是使用一個 MRG (Multiple Recursive Generator, LCG 的延伸) 生成的。按照題目 hint 和我最後得到的 flag 知道預期解是用 dual attack 做的，不過我這邊是用 unintended 解的。

關鍵在於這題 $n=512$ ，而 $x^n-1$ 在 $\mathbb{Z}[x]$ 上是可分解的:

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)

所以對於每個因子 $p(x)$ 都符合 $b(x)=A(x)s(x)+e(x) \pmod{p(x)}$ ，只要 degree 夠小的話就能直接用 LLL 解 $s(x), e(x)$ modulo $p(x)$ 的值，最後再 CRT 回去即可。這個其實就是之前 HackTM CTF 中我沒解的 GLP420 的核心概念。

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

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

# 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

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

這題有 $(m,n)=(180,50)$ ，未知的部分有 binary matrix $x \in \{0,1\}^{m \times n}$ 、 $\alpha \in \mathbb{F}_p^n$ 還有個數 $s$ 是 flag。已知的是向量 $e,h \in \mathbb{F}_p^m$ 符合 $x\alpha \equiv h+se \pmod{p}$ 。

從 $xA$ 那邊一看就讓我想到 HSSP (Hidden Subset Sum Problem)，所以我就先用 LLL 找了 $M$ 符合 $Mh \equiv Me \equiv 0 \pmod{p}$ ，那麼 $Mx\alpha \equiv 0 \pmod{p}$ 。既然 $x$ 是 binary matrix，這邊和一般的 HSSP 一樣我們可以預期 $M$ 的前 $m-n$ rows 是 $x$ 的 orthogonal lattice basis，所以再一次 LLL 就能求得 $x$ 了。

求得 $x$ 之後之後想求 $\alpha$ 會發現我們還不知道 $s$ ，我這邊是再用一次 LLL 找使 $M_e e \equiv 0 \pmod{p}$ 的 $M_e$ ，那麼從 $M_e x \alpha \approx M_e h \pmod{p}$ 就能解出 $\alpha$ 。

解出來之後會發現 $x$ 和 $\alpha$ 順序都不太對，但那個不重要，只要 $x\alpha$ 正確即可。之後只要用 $x\alpha - h \equiv se \pmod{p}$ 就能拿到 flag $s$ 了。

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

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 的 $d$ 是 $\operatorname{nextPrime}(\bigoplus_{i=0}^{14} N_i)$ ，而 $N_i$ 都是未知的數。特別的地方是它有隨機取一些比較小的質數 $p_i$ 然後計算 $S_{i,j} \equiv N_j \pmod{p_i}$ ，之後 shuffle 每個 row ( $j$ index 不固定)。

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

我是在看到 $p \equiv 2^{321}$ 的時候發現 $15 \times 321 = 4815$ 遠比 $\log_2 N_i \equiv 3211$ 大，所以直覺告訴我這題也和 LLL 有關。

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

\begin{aligned} T_i &\equiv 1 \pmod{p_i} \\ T_i &\equiv 0 \pmod{p_{j \neq i}} \end{aligned}

那麼對於一個 $x \equiv a_i \pmod{p_i}$ 的系統，可以得出解為 $x \equiv \sum a_i T_i \pmod{\prod{p_i}}$ 。

所以如果假設 $S$ 沒有 shuffle 過，然後假裝 $S$ 和 $N$ 以及 $T$ 分別是矩陣和向量的話可以寫出 $TS \equiv N \pmod{p}$ 的關係式。

但是 $S$ 有 shuffle 過，所以 $TS$ 並不是 $N$ ，但是我們知道 $TS$ 中肯定有某些 entries 加總起來 $\bmod{\,\prod{p}}$ 之下會是 $N_i$ 。此時利用 $N_i$ 相對於 $\prod{p}$ 比起來不大的這個事實，會發現只要把 $TS$ 這個矩陣攤平，然後用類似 knapsack 的 lattice 寫出來就能預期有個 $(N_i, u_0, u_1, \cdots)$ 的 short vector，其中 $u_i \in {0,1}$ 。

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

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

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}

d3bdd#

d3pack#

d3noisy#

d3bdd

d3pack

d3noisy