D^3CTF 2023 WriteUps

發表於
分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This time I participated a bit in the nyahello team and solved three out of four crypto challenges. I found the difficulty quite high, so I decided to write a 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)

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

In short, this challenge involves encrypting the flag using RLWE in Zq[x]/(xn1)\mathbb{Z}_q[x]/(x^n-1), satisfying b(x)=A(x)s(x)+e(x)b(x)=A(x)s(x)+e(x). The ee is generated using an MRG (Multiple Recursive Generator, an extension of LCG). According to the hint and the flag I eventually obtained, the expected solution is to use a dual attack, but I solved it using an unintended method.

The key is that in this challenge n=512n=512, and xn1x^n-1 in Z[x]\mathbb{Z}[x] can be factored:

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)

So for each factor p(x)p(x), b(x)=A(x)s(x)+e(x)(modp(x))b(x)=A(x)s(x)+e(x) \pmod{p(x)} holds. If the degree is small enough, we can directly use LLL to solve for s(x),e(x)s(x), e(x) modulo p(x)p(x), and then use CRT to combine the results. This is essentially the core concept of the GLP420 challenge from HackTM CTF that I didn't solve before.

However, the problem here is that the largest degp(x)=256\deg p(x) = 256, and I found that LLL couldn't find the expected short vector with this degree, so it couldn't be solved. After some time, I realized that the flag format is fixed, so I could use the known information to remove some bits, making it easier for LLL to find the target. The details involve some variable substitutions, which can be found in my solver.

My solver is mainly adapted from Neobeo's solver, and it also uses flatter to significantly improve the time LLL takes.

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

In this challenge, (m,n)=(180,50)(m,n)=(180,50), the unknowns are the binary matrix x{0,1}m×nx \in \{0,1\}^{m \times n}, αFpn\alpha \in \mathbb{F}_p^n, and the number ss which is the flag. The known vectors e,hFpme,h \in \mathbb{F}_p^m satisfy xαh+se(modp)x\alpha \equiv h+se \pmod{p}.

Seeing xAxA immediately reminded me of HSSP (Hidden Subset Sum Problem), so I first used LLL to find MM such that MhMe0(modp)Mh \equiv Me \equiv 0 \pmod{p}, then Mxα0(modp)Mx\alpha \equiv 0 \pmod{p}. Since xx is a binary matrix, similar to the usual HSSP, we can expect the first mnm-n rows of MM to be the orthogonal lattice basis of xx, so another LLL can solve for xx.

After solving for xx, to find α\alpha, we realize we still don't know ss. I used LLL again to find MeM_e such that Mee0(modp)M_e e \equiv 0 \pmod{p}, then from MexαMeh(modp)M_e x \alpha \approx M_e h \pmod{p}, we can solve for α\alpha.

After solving, we find that the order of xx and α\alpha is not quite right, but that's not important as long as xαx\alpha is correct. Then, using xαhse(modp)x\alpha - h \equiv se \pmod{p}, we can get the flag ss.

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!}

According to the flag, we know this is called AHSSP. After checking, I found that A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem Appendix G mentions this problem (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}")

In this challenge, the RSA dd is nextPrime(i=014Ni)\operatorname{nextPrime}(\bigoplus_{i=0}^{14} N_i), and the NiN_i are unknown numbers. The special part is that it randomly selects some smaller primes pip_i and calculates Si,jNj(modpi)S_{i,j} \equiv N_j \pmod{p_i}, then shuffles each row (the jj index is not fixed).

If there were no shuffle, this challenge would be simple, as we could directly use CRT to solve for NiN_i, but the shuffle causes a lot of trouble.

When I saw p2321p \equiv 2^{321}, I realized that 15×321=481515 \times 321 = 4815 is much larger than log2Ni3211\log_2 N_i \equiv 3211, so my intuition told me this challenge is also related to LLL.

Thinking carefully about the CRT process, we realize that CRT can actually be done separately. For example, first find TiT_i such that

Ti1(modpi)Ti0(modpji)\begin{aligned} T_i &\equiv 1 \pmod{p_i} \\ T_i &\equiv 0 \pmod{p_{j \neq i}} \end{aligned}

Then for a system xai(modpi)x \equiv a_i \pmod{p_i}, the solution can be xaiTi(modpi)x \equiv \sum a_i T_i \pmod{\prod{p_i}}.

So if we assume SS is not shuffled and pretend SS, NN, and TT are matrices and vectors, we can write the relationship TSN(modp)TS \equiv N \pmod{p}.

But since SS is shuffled, TSTS is not NN, but we know that some entries in TSTS must sum to NimodpN_i \bmod{\,\prod{p}}. Using the fact that NiN_i is relatively small compared to p\prod{p}, we can flatten the TSTS matrix and write it as a knapsack-like lattice, expecting a short vector (Ni,u0,u1,)(N_i, u_0, u_1, \cdots), where ui0,1u_i \in {0,1}.

So after balancing the lattice weights, using LLL to take the first 15 bases, we can get all NiN_i, then solve for dd and use RSA decryption to get the flag.

Again, I used flatter instead of LLL and found the speed significantly faster 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}