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 $\mathbb{Z}_q[x]/(x^n-1)$, satisfying $b(x)=A(x)s(x)+e(x)$. The $e$ 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=512$, and $x^n-1$ in $\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)$, $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)$ modulo $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 $\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)$, the unknowns are the binary matrix $x \in \{0,1\}^{m \times n}$, $\alpha \in \mathbb{F}_p^n$, and the number $s$ which is the flag. The known vectors $e,h \in \mathbb{F}_p^m$ satisfy $x\alpha \equiv h+se \pmod{p}$.

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

After solving for $x$, to find $\alpha$, we realize we still don't know $s$. I used LLL again to find $M_e$ such that $M_e e \equiv 0 \pmod{p}$, then from $M_e x \alpha \approx M_e h \pmod{p}$, we can solve for $\alpha$.

After solving, we find that the order of $x$ and $\alpha$ is not quite right, but that's not important as long as $x\alpha$ is correct. Then, using $x\alpha - h \equiv se \pmod{p}$, we can get the 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!}

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 $d$ is $\operatorname{nextPrime}(\bigoplus_{i=0}^{14} N_i)$, and the $N_i$ are unknown numbers. The special part is that it randomly selects some smaller primes $p_i$ and calculates $S_{i,j} \equiv N_j \pmod{p_i}$, then shuffles each row (the $j$ index is not fixed).

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

When I saw $p \equiv 2^{321}$, I realized that $15 \times 321 = 4815$ is much larger than $\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 $T_i$ such that

Then for a system $x \equiv a_i \pmod{p_i}$, the solution can be $x \equiv \sum a_i T_i \pmod{\prod{p_i}}$.

So if we assume $S$ is not shuffled and pretend $S$, $N$, and $T$ are matrices and vectors, we can write the relationship $TS \equiv N \pmod{p}$.

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

So after balancing the lattice weights, using LLL to take the first 15 bases, we can get all $N_i$, then solve for $d$ 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}