D^3CTF 2023 WriteUps
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 , satisfying . The 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 , and in 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 , holds. If the degree is small enough, we can directly use LLL to solve for modulo , 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 , 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, , the unknowns are the binary matrix , , and the number which is the flag. The known vectors satisfy .
Seeing immediately reminded me of HSSP (Hidden Subset Sum Problem), so I first used LLL to find such that , then . Since is a binary matrix, similar to the usual HSSP, we can expect the first rows of to be the orthogonal lattice basis of , so another LLL can solve for .
After solving for , to find , we realize we still don't know . I used LLL again to find such that , then from , we can solve for .
After solving, we find that the order of and is not quite right, but that's not important as long as is correct. Then, using , we can get the flag .
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 is , and the are unknown numbers. The special part is that it randomly selects some smaller primes and calculates , then shuffles each row (the index is not fixed).
If there were no shuffle, this challenge would be simple, as we could directly use CRT to solve for , but the shuffle causes a lot of trouble.
When I saw , I realized that is much larger than , 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 such that
Then for a system , the solution can be .
So if we assume is not shuffled and pretend , , and are matrices and vectors, we can write the relationship .
But since is shuffled, is not , but we know that some entries in must sum to . Using the fact that is relatively small compared to , we can flatten the matrix and write it as a knapsack-like lattice, expecting a short vector , where .
So after balancing the lattice weights, using LLL to take the first 15 bases, we can get all , then solve for 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}