TSG CTF 2024 write-up (Reversingジャンル全問)

TSG CTF 2024へ参加しました。そのwrite-up記事です。

コンテスト概要

2024/12/14(土) 16:00 +09:00 - 12/15(日) 16:00 +09:00の24時間開催でした。他ルールはRulesページから引用します:

Rules
- Don’t prevent other teams from having fun.
- Don’t share flags or hints, or you’ll be banned.
- Don’t attack (e.g. DoS) our infrastructure, or you’ll be banned.
- Don’t do automated scanning. It will be considered to be DoS.
- The flag format is TSGCTF{blahblah}, unless otherwise specified.
- The prize will be paid with PayPal. If it doesn't suit you, we can pay that in BitCoin at an arbitrary exchange rate we determine.
- The teams must publish the writeups of the solved problems in CTFTime to get their prizes.
- The number of members in a team is unlimited.
- People who belong to TSG are not allowed to participate in TSG CTF.

Support
If you have issue with TSG CTF, please contact us by joining official Discord server, and clicking "Create Ticket" button in the #ask-admin channel.

About “beginner” challenges
If you are unfamiliar with CTF, we highly recommend you to first take a look at the challenges with "beginner" tag. They will be released at the same time as the CTF launch.
In TSG CTF, Beginner's tasks are not "beginner-level challenges." We define a beginner's task as a challenge that does not require any experience or knowledge specific to CTF, but can be solved with knowledge that even a beginner has. Please don't be discouraged if you can't solve a "beginner's task". At times it can be hard!

Release Schedule
Disclaimer: This schedule is tentative. We will make the best effort to deliver these challenges as planned. However any changes are expected anytime.
(省略)

過去のTSGCTFと同様に、 beginner ジャンルの定義が独特です。 問題のリリーススケジュールには、日本時間の16時(=開始直後)、18時、20時、22時に問題が公開されることや、公開予定の問題ジャンルや推定難易度が記載されていました。記載通りに公開されていたはずです。

結果

Reversingジャンル4問をすべて正解できました！

環境

WindowsのWSL2(Ubuntu 24.04)を使って取り組みました。

Windows

c:\>ver

Microsoft Windows [Version 10.0.19045.5247]

c:\>wsl -l -v
  NAME                   STATE           VERSION
* Ubuntu-24.04           Running         2
  docker-desktop-data    Running         2
  kali-linux             Stopped         2
  docker-desktop         Running         2
  Ubuntu-22.04           Running         2

c:\>

他ソフト

• IDA Free Version 9.0.240925 Windows x64 (64-bit address size)(Free版IDAでもversion 7頃からx64バイナリを、version 8.2からはx86バイナリもクラウドベースの逆コンパイルができます)

WSL2(Ubuntu 24.04)

$ cat /proc/version
Linux version 5.15.167.4-microsoft-standard-WSL2 (root@f9c826d3017f) (gcc (GCC) 11.2.0, GNU ld (GNU Binutils) 2.37) #1 SMP Tue Nov 5 00:21:55 UTC 2024
$ cat /etc/os-release
PRETTY_NAME="Ubuntu 24.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.1 LTS (Noble Numbat)"
VERSION_CODENAME=noble
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=noble
LOGO=ubuntu-logo
$ python3 --version
Python 3.12.3
$ python3 -m pip show pip | grep Version:
Version: 24.0
$ python3 -m pip show pwntools | grep Version:
Version: 4.13.0
$ python3 -m pip show z3-solver | grep Version:
Version: 4.8.16.0
$ gdb --version
GNU gdb (Ubuntu 15.0.50.20240403-0ubuntu1) 15.0.50.20240403-git
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
$ gdb --batch --eval-command 'version' | grep 'Pwndbg:'
Pwndbg:   2024.02.14 build: 2b9beef
$ docker --version
Docker version 27.2.0, build 3ab4256
$

解けた問題

例年のTSGCTF同様に、本コンテストでは問題説明文として日本語と英語の2種類が提供されました。本記事では日本語版の問題文を掲載します。

[Reversing, beginner] Misbehave (74 teams solves, 114 points)

このバイナリ、少し変なんです……

初心者向けのヒント：
- 添付ファイルはx86-64のLinux上で動くELF形式の実行可能ファイルです
- 実行して正しいFLAGを入力すると、Correct!と表示されます
- GhidraやIDA Freeで処理の概要を把握しましょう
- gdbで実際に動かしながら挙動を確認しましょう
- すべての処理の内容を正確に理解する必要はありません
  - その処理が何を入力とし、何を変更するのかを把握するだけで十分なこともあります

配布ファイルとして、misbehaveがありました:

$ file *
misbehave: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=0cc0ad6f3eef296bf5d38d4252a2faff8dc71160, for GNU/Linux 3.2.0, not stripped
$

IDAで開いて解析しました。main関数は次の内容でした(変数名等置き換え後):

int __fastcall main(int argc, const char **argv, const char **envp)
{
  char strInputSize48[48]; // [rsp+0h] [rbp-40h] BYREF
  int dwRandomValue; // [rsp+30h] [rbp-10h]
  int dwCompareUnit4; // [rsp+34h] [rbp-Ch]
  int i; // [rsp+38h] [rbp-8h]
  char bSucceeded; // [rsp+3Fh] [rbp-1h]

  bSucceeded = 1;
  dwCompareUnit4 = 4;
  input_flag(strInputSize48, 48);
  init(11447LL, 34LL);
  for ( i = 0; i <= 11; ++i )
  {
    dwRandomValue = gen_rand();
    *(_DWORD *)&strInputSize48[4 * i] ^= dwRandomValue;
    if ( memcmp(&strInputSize48[4 * i], &flag_enc[4 * i], dwCompareUnit4) )
      bSucceeded = 0;
  }
  if ( bSucceeded )
    puts("Correct!");
  else
    puts("Wrong...");
  return 0;
}

main関数から呼び出している関数は次の機能を持ちます:

• input_flag関数は、標準入力から文字列を読み込みつつ、末尾の改行文字を除去します。
• gen_rand関数は、グローバル変数stateを使って、stateの状態を更新しつつ、uint32_t値を返します。

上述のところだけを見ると、あたかも「デバッガー実行して適当な入力を与え、gen_rand関数の戻り値を確認することで、グローバル変数配列flag_encから正解の入力を逆算する」ができそうに見えます。

しかし実は、init関数で豪快なことをしていました:

void __fastcall init(__int64 a1, __int64 a2)
{
  state = 0xFEEDF00DDEADBEEFLL;
  *(_QWORD *)((char *)&loc_1381 + a1) = (char *)&loc_1381 + a2;//  init(11447LL, 34LL);→memcmp置き換え
}

グローバル変数stateを初期化しています。そして、init関数内部のアドレスloc_1381からの相対オフセットを使ったアドレスへ、uint64_t値を書き込んでいます。計算すると、書き換え先のアドレスはmemcmp@got、書き換え後の内容は13A3の関数でした。つまり、main関数ではmemcmp関数ではなく13A3の関数を呼び出します！

13A3の関数は次の内容でした:

_BOOL8 __fastcall UpdateStateWithXorAndCompareArgument(_DWORD *a1, _DWORD *a2)
{
  state = (unsigned int)*a1 ^ (unsigned __int64)state;
  return *a1 != *a2;
}

4バイト単位のmemcmp相当の比較をするのと同時に、グローバル変数stateを第1引数とのXOR結果で更新しています。main関数から呼び出す際の第1引数はユーザー入力内容であるため、state内容はユーザー入力に依存して変化します。

全体として、gen_rand関数は、次の値を返します:

1. 初回の呼び出しは、固定値です。init関数でグローバル変数stateを初期化した直後にgen_rand関数が呼び出されるためです。
2. 2回目の呼び出しは、ユーザー入力の最初4バイトへ依存します。13A3の関数でもグローバル変数state変数を更新するためです。
3. 以降同様に、ユーザー入力の最初4*Nバイトへ依存した内容を返します。

全体として、次の処理を行えばフラグを逆算できます:

1. 先頭4バイトは、初回のgen_rand関数の戻り値4バイトと、グローバル変数配列flag_enc先頭4バイトのXORで分かります。
2. 次の4バイトは、「先頭4バイトが正しい場合のgen_rand関数の次の戻り値4バイト」と、グローバル変数配列flag_encの次の4バイトのXORで分かります。
3. 以降同様に、「それまでの4バイト単位で入力が正しい場合のgen_rand関数の戻り値4バイト」とグローバル変数配列flag_encのその段階の4バイトのXORで分かります。

gen_rand関数の戻り値を確認するために、pwntoolsライブラリのpwn.process関数でgdbコマンドを自動操作して、main+0x4Aでraxレジスタ内容を出力させました。なお、gdb -x myscript.pyでGDBを自動操作する方法もありますが、gdbモジュールの使い方を私は分かっていません。そのため普段と同じコマンドで操作できるpwn.process経由で実行しています。ソルバーです:

#!/usr/bin/env python3
import pwn

pwn.context.log_level = "CRITICAL"  # ignore pwn.process's log


def run_with_dprintf(flag: str):
    with pwn.process(["gdb", "-q", "--nx", "misbehave"]) as io:
        # GDB_PROMPT = b"pwndbg>"
        GDB_PROMPT = b"(gdb)"
        OUTPUT_LINE_PREFIX = "LINE_PREFIX"
        io.sendlineafter(
            GDB_PROMPT,
            rf"""dprintf  *(main+0x4A), "{OUTPUT_LINE_PREFIX} %lld\n", $rax""".encode(),
        )
        io.sendlineafter(GDB_PROMPT, b"run")
        io.sendlineafter(b"flag?", flag.encode())

        output = io.recvuntil(GDB_PROMPT).decode()
        result = []
        for line in output.splitlines():
            # エスケープシーケンスはどこで入っていたのか……。
            if line.startswith("\x1b[m"):
                line = line[len("\x1b[m") :]

            if not line.startswith(OUTPUT_LINE_PREFIX):
                continue
            value = int(line[len(OUTPUT_LINE_PREFIX) :])
            result.append(value)
        return result


# IDAで「.data:0000000000004080」へカーソルを合わせた状態で、Shift+Eで「Export data」してHex表現を得ました。
flag_enc = bytes.fromhex(
    "20 60 6F 90 AE 77 8F F3 FC 09 A5 5E DD 6B 39 51 DF FD 6E 5E A8 60 88 85 BC D7 95 52 75 E9 82 F3 B7 A2 04 95 4A 0E 5C 67 53 81 13 BF 34 61 70 C1"
)


flag = ""
round_count = len(flag_enc) // 4

for i in range(round_count):
    output = run_with_dprintf(flag.ljust(48, "@"))
    current: int = output[i] ^ pwn.u32(flag_enc[4 * i : 4 * (i + 1)])
    flag += current.to_bytes(4, "little").decode()
    print(flag)

実行しました:

$ time ./solve.py
TSGC
TSGCTF{h
TSGCTF{h1dd3
TSGCTF{h1dd3n_fu
TSGCTF{h1dd3n_func7i
TSGCTF{h1dd3n_func7i0n_4
TSGCTF{h1dd3n_func7i0n_4nd_s
TSGCTF{h1dd3n_func7i0n_4nd_s31f_
TSGCTF{h1dd3n_func7i0n_4nd_s31f_g07_
TSGCTF{h1dd3n_func7i0n_4nd_s31f_g07_0ver
TSGCTF{h1dd3n_func7i0n_4nd_s31f_g07_0verwr17
TSGCTF{h1dd3n_func7i0n_4nd_s31f_g07_0verwr173}\x00\x00
./solve.py  2.65s user 0.51s system 136% cpu 2.314 total
$

フラグを入手できました: TSGCTF{h1dd3n_func7i0n_4nd_s31f_g07_0verwr173}

[Reversing, easy] Warmup SQLite (24 teams solves, 189 points)

とりあえずSQLiteのバイトコードに慣れるか...

配布ファイルとして、READMD.mdなどがありました:

$ file *
README.md: ASCII text
dump:      ASCII text
hello.db:  SQLite 3.x database, last written using SQLite version 3043002, unused bytes 12, file counter 2, database pages 2, cookie 0x1, schema 4, UTF-8, version-valid-for 2
server.py: Python script text executable Python script, ASCII text executable, with very long lines (303)
$ cat README.md
# Warmup SQLite

`dump` is the result of `EXPLAIN <hidden SQL>` with the parameter `~~Your input is filled here~~`.

We use the same sqlite3 as SQLite of Hand, another pwn challenge in TSG CTF 5, to dump this code.
$

hello.dbやserver.pyはよく分かりません。本問題にnc接続先等はありません。おそらくdump作成に使われたのだと思います。次のserver.py内容のうち、res内容のみソルバーで使いました:

import sqlite3
import re
import sys

res = [100, 115, 39, 99, 100, 54, 27, 115, 69, 220, 69, 99, 100, 191, 56, 161, 131, 11, 101, 162, 191, 54, 130, 175, 205, 191, 222, 101, 162, 116, 147, 191, 55, 24, 69, 130, 69, 191, 252, 101, 102, 101, 252, 189, 82, 116, 41, 147, 161, 147, 132, 101, 162, 82, 191, 220, 9, 205, 9, 100, 191, 38, 68, 253]

def check(s):
    return bool(re.match('^[a-zA-Z0-9_=}{"]+$', s))

def run(s):
    conn = sqlite3.connect('hello.db')
    cursor = conn.cursor()

    with open('query.sql', 'r') as f:
        query = f.read()

    try:
        cursor.execute(query, (s,))
        for (idx, row) in enumerate(cursor.fetchall()):
            assert(row[0] == res[idx])
        print('correct')
    except Exception as _:
        print('wrong')
    finally:
        conn.close()

def main():
    print('input string: ')
    s = sys.stdin.readline().strip()
    if not (s and len(s) == 64 and check(s)):
        print("wrong")
        return
    run(s)

main()

実質的な問題本体のdumpは次の内容です:

0|Init|0|88|0||0
1|InitCoroutine|1|68|2||0
2|OpenPseudo|1|2|3||0
3|OpenEphemeral|4|3|0||0
4|InitCoroutine|3|34|5||0
5|OpenPseudo|3|4|3||0
6|OpenEphemeral|5|3|0||0
7|String8|0|5|0||0
8|String8|0|6|0|~~Your input is filled here~~|0
9|Integer|-1|7|0||0
10|MakeRecord|5|3|8||0
11|NewRowid|5|9|0||0
12|Insert|5|8|9||8
13|Rewind|5|33|0||0
14|NullRow|3|0|0||0
15|RowData|5|4|0||0
16|Delete|5|0|0||0
17|Column|3|0|10||0
18|Column|3|1|11||0
19|Column|3|2|12||0
20|Yield|3|0|0||0
21|Column|3|1|8||0
22|Eq|13|32|8|BINARY-8|80
23|Column|3|1|14||0
24|Function|6|14|5|substr(3)|0
25|Column|3|1|17||0
26|Function|2|17|6|substr(2)|0
27|Column|3|2|8||0
28|Add|19|8|7||0
29|MakeRecord|5|3|8||0
30|NewRowid|5|9|0||0
31|Insert|5|8|9||8
32|Goto|0|13|0||0
33|EndCoroutine|3|0|0||0
34|InitCoroutine|3|0|5||0
35|Yield|3|46|0||0
36|Copy|10|20|0||2
37|Eq|13|45|20|BINARY-8|80
38|Copy|10|20|0||2
39|Function|0|20|21|unicode(1)|0
40|Copy|12|22|0||2
41|Integer|0|23|0||0
42|MakeRecord|21|3|20||0
43|NewRowid|4|24|0||0
44|Insert|4|20|24||8
45|Goto|0|35|0||0
46|Rewind|4|67|0||0
47|NullRow|1|0|0||0
48|RowData|4|2|0||0
49|Delete|4|0|0||0
50|Column|1|0|25||0
51|Column|1|1|26||0
52|Column|1|2|27||0
53|Yield|1|0|0||0
54|Column|1|2|20||0
55|Ge|28|66|20|BINARY-8|80
56|Column|1|0|29||0
57|Multiply|30|29|24||0
58|Add|31|24|20||0
59|Remainder|32|20|21||0
60|Column|1|1|22||0
61|Column|1|2|20||0
62|Add|19|20|23||0
63|MakeRecord|21|3|20||0
64|NewRowid|4|24|0||0
65|Insert|4|20|24||8
66|Goto|0|46|0||0
67|EndCoroutine|1|0|0||0
68|SorterOpen|6|5|0|k(1,B)|0
69|InitCoroutine|1|0|2||0
70|Yield|1|79|0||0
71|Copy|27|33|0||2
72|Ne|28|78|33|BINARY-8|80
73|Copy|25|35|0||2
74|Copy|27|36|0||2
75|Copy|26|34|0||2
76|MakeRecord|34|3|38||0
77|SorterInsert|6|38|34|3|0
78|Goto|0|70|0||0
79|OpenPseudo|7|39|5||0
80|SorterSort|6|87|0||0
81|SorterData|6|39|7||0
82|Column|7|2|37||0
83|Column|7|0|36||0
84|Column|7|1|35||0
85|ResultRow|35|3|0||0
86|SorterNext|6|81|0||0
87|Halt|0|0|0||0
88|String8|0|13|0||0
89|Integer|1|15|0||0
90|Integer|1|16|0||0
91|Integer|2|18|0||0
92|Integer|1|19|0||0
93|Integer|10|28|0||0
94|Integer|7|30|0||0
95|Integer|2|31|0||0
96|Integer|256|32|0||0
97|Goto|0|1|0||0

SQLiteのオペコードを全部読もうとして挫折

とりあえずsqlite opcodeでGoogle検索をするとThe SQLite Bytecode EngineやWhy SQLite Uses Bytecodeを見つけました。真面目に読んで、次のことが分かりました(数十分学習しただけなので誤りがあればすみません):

• SQLiteではprepared statementの実装として、バイトコードを使います。他のDBMSとは異なり、Tree-Of-Objectsではありません。
• SQLiteのバイトコードでは、各種命令は1つのオペコードと5個のオペランドを持ちます。オペランドはP1～P5で表されます。
• 実際に何個のオペランドを使うかは命令種類へ依存します。

後は、実際に使われている各種命令を人目で読みやすくなるようにパースしようとしました。残骸です:

#!/usr/bin/env python3


def sequence_register(begin, count):
    return ", ".join(map(lambda x: f"r{x}", range(begin, begin + count)))


with open("dump", "r") as f:
    for line in f.readlines():
        line = line.strip()
        (index, inst, p1, p2, p3, p4, p5) = line.split("|")
        p1 = int(p1)
        p2 = int(p2)
        p3 = int(p3)
        # p4は文字列の場合もある
        p5 = int(p5)

        print(f"{index}, {inst}({p1}, {p2}, {p3}, {p4}, {p5})".ljust(40), end=": ")
        match inst:
            case "Add":
                print(f"r{p3} := r{p1} + r{p2}")
            case "Column":
                print(f"r{p3} := GetColumn(cursor={p1}, column_index={p2}, {p4=}, {p5=})")
            case "Copy":
                print(f"{sequence_register(p2, p3+1)} := {sequence_register(p1, p3+1)}")
            case "Delete":
                print(f"DeleteRow(cursor={p1}, flags={p5})")
            case "EndCoroutine":
                print(f"assert *r{p1}==Yield; Goto r{p1}->p2; r{p1} := PC;")
            case "Eq":
                print(f"if (r{p3} == r{p1}) Goto {p2}")
            case "Function":
                function_parameter_count = int(p4[-2])
                print(f"r{p3} := {p4}({sequence_register(p2, function_parameter_count)})")
            case "Ge":
                print(f"if (r{p3} >= r{p1}) Goto {p2}")
            case "Goto":
                print(f"Goto {p2}")
            case "Halt":
                print(f"Exit(code={p1}, {p3=}, {p4=})")
            case "Init":
                print(f"Init(goto {p2})")
            case "InitCoroutine":
                print(f"r{p1} := Corountine(addr={p2}); r{p3}=yieldable")
            case "Insert":
                print(f"Insert(cursor={p1}, mem_blob=r{p2}, table={p4}, flag={p5})")
            case "Integer":
                print(f"r{p2} := {p1}")
            case "MakeRecord":
                print(f"ConvertToRecord(r{p1}..r{p1+p2-1}, string='{p4}')")
            case "Multiply":
                print(f"r{p3} := r{p2} * r{p1}")
            case "Ne":
                print(f"if (r{p3} != r{p1}) Goto {p2}")
            case "NewRowid":
                print(f"r{p2} := GetRowId(cursor:={p1}, p3={p3})")
            case "NullRow":
                print(f"cursor{p1} := NullRow()")
            case "OpenEphemeral":
                print(f"r{p1} := Cursor(column_count={p2}, {p4},{p5}); r{p3} := changed;")
            case "OpenPseudo":
                print(f"r{p1} := Cursor(addr=r{p2}, field_count={p3})")
            case "Remainder":
                print(f"r{p3} := r{p2} % r{p1}")
            case "ResultRow":
                print(f"return Row(r{p1}..r{p1+p2-1})")
            case "Rewind":
                print(f"ResetColumn(cursor={p1}); Goto {p2}")
            case "RowData":
                print(f"r{p2} := RowData(cursor={p1}, p3={p3})")
            case "SorterData":
                print(f"r{p2} := Sorted(cursor={p1}); ClearCache(cursor={p3})")
            case "SorterInsert":
                print(f"r{p2} := SqlIndexKey_ResultOfMakeRecord(); sorter{p1} := Key;")
            case "SorterNext":
                print(f"r{p1} := TODO")
            case "SorterOpen":
                print(f"r{p1} := Sorter(column_count={p2}, {p4},{p5}); r{p3} := changed;")
            case "SorterSort":
                print(f"Sort(sorter={p1}); if (NotSorted) Goto {p2}")
            case "String8":
                print(f"r{p1} := len('{p4}'); r{p2} :='{p4}'")
            case "Yield":
                print(f"Swap(PC, r{p1}); MayBeGoto {p2}")

ただ、Coroutine関係や、Sorter関係の引数の意味や役割が分かりませんでした。そのためパーサー作成途中で力尽きました。

部分的なパース結果から実行内容をエスパー

完全な解析には挫折しました。しかし断片的なパース結果でも、何となく分かる部分があります:

$ ./parse_dump.py
0, Init(0, 88, 0, , 0)                  : Init(goto 88)
(よくわからないので省略)
55, Ge(28, 66, 20, BINARY-8, 80)        : if (r20 >= r28) Goto 66
56, Column(1, 0, 29, , 0)               : r29 := GetColumn(cursor=1, column_index=0, p4='', p5=0)
57, Multiply(30, 29, 24, , 0)           : r24 := r29 * r30
58, Add(31, 24, 20, , 0)                : r20 := r31 + r24
59, Remainder(32, 20, 21, , 0)          : r21 := r20 % r32
60, Column(1, 1, 22, , 0)               : r22 := GetColumn(cursor=1, column_index=1, p4='', p5=0)
61, Column(1, 2, 20, , 0)               : r20 := GetColumn(cursor=1, column_index=2, p4='', p5=0)
62, Add(19, 20, 23, , 0)                : r23 := r19 + r20
63, MakeRecord(21, 3, 20, , 0)          : ConvertToRecord(r21..r23, string='')
64, NewRowid(4, 24, 0, , 0)             : r24 := GetRowId(cursor:=4, p3=0)
65, Insert(4, 20, 24, , 8)              : Insert(cursor=4, mem_blob=r20, table=, flag=8)
66, Goto(0, 46, 0, , 0)                 : Goto 46
(よくわからないので省略)
88, String8(0, 13, 0, , 0)              : r0 := len(''); r13 :=''
89, Integer(1, 15, 0, , 0)              : r15 := 1
90, Integer(1, 16, 0, , 0)              : r16 := 1
91, Integer(2, 18, 0, , 0)              : r18 := 2
92, Integer(1, 19, 0, , 0)              : r19 := 1
93, Integer(10, 28, 0, , 0)             : r28 := 10
94, Integer(7, 30, 0, , 0)              : r30 := 7
95, Integer(2, 31, 0, , 0)              : r31 := 2
96, Integer(256, 32, 0, , 0)            : r32 := 256
97, Goto(0, 1, 0, , 0)                  : Goto 1

Init命令で88番目の命令へジャンプし、88～96番目の命令でレジスタを初期化しています。特にr19、r28、r30、r31、r32レジスタの内容は以降読み込み専用になり、変化しないようです。レジスタの内容を踏まえたう55～66番目の命令を読むと、「10回ループしていそう」「((何か * 7) + 2) % 256を計算していそう」な雰囲気を感じます。

試しに、フラグの先頭文字Tに前述の計算を10回適用すると、server.pyのres[0]と一致しました。同様に、res配列からフラグ全体を逆算できると考えました。

ソルバーと実行結果

逆算にはz3-solverライブラリを使いました:

#!/usr/bin/env python3

import z3

# server.pyの内容のコピー
# fmt:off
res = [100, 115, 39, 99, 100, 54, 27, 115, 69, 220, 69, 99, 100, 191, 56, 161, 131, 11, 101, 162, 191, 54, 130, 175, 205, 191, 222, 101, 162, 116, 147, 191, 55, 24, 69, 130, 69, 191, 252, 101, 102, 101, 252, 189, 82, 116, 41, 147, 161, 147, 132, 101, 162, 82, 191, 220, 9, 205, 9, 100, 191, 38, 68, 253]
# fmt:on


def convert(value):
    return (value * 7 + 2) % 256


def invert_10times(index: int) -> int:
    solver = z3.Solver()
    flag_original = z3.BitVec("flag", 8)
    flag = flag_original
    for i in range(10):
        flag = convert(flag)
    solver.add(flag == res[index])
    if solver.check() != z3.sat:  # CheckSatResult
        raise Exception("Can not solve...")
    return solver.model()[flag_original].as_long()


for i in range(len(res)):
    print(chr(invert_10times(i)), end="")
print()

実行しました:

$ time ./solve.py
TSGCTF{SELECT_hacker_FROM_nerds_WHERE_level="disaster"_LIMIT_64}
./solve.py  0.58s user 0.02s system 543% cpu 0.111 total
$

フラグを入手できました: TSGCTF{SELECT_hacker_FROM_nerds_WHERE_level="disaster"_LIMIT_64}

[Reversing, med] TSGDBinary (20 teams solves, 205 points)

普段使い

最初に弁明します。全体的な動作をあまり分かっていません！分かった範囲でのみ記述します。

配布ファイルとして、各種ファイルがありました:

$ file *
start.sh:      ASCII text
tsgdbinary:    ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=8f616032874f47a9297c15a5c48f59e838080865, for GNU/Linux 3.2.0, stripped
tsgdbinary.py: Python script, ASCII text executable
$

start.shは、tsgdbinary.pyをGDBスクリプトとして読み込ませつつtsgdbinaryバイナリを実行する内容です:

sudo gdb --nx -x ./tsgdbinary.py ./tsgdbinary

IDAでtsgdbinaryバイナリを開くと、一見すると次のmain関数だけのように見えます:

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  _BYTE s[48]; // [rsp+0h] [rbp-70h] BYREF
  char s2[35]; // [rsp+30h] [rbp-40h] BYREF
  char v6; // [rsp+53h] [rbp-1Dh]
  int v7; // [rsp+54h] [rbp-1Ch]
  __int64 v8; // [rsp+58h] [rbp-18h]
  unsigned __int64 v9; // [rsp+68h] [rbp-8h]

  v9 = __readfsqword(0x28u);
  strcpy(s2, "TSGCTF{dummy_plz_execute_start.sh}");
  v6 = 0;
  v7 = 0;
  v8 = 0LL;
  setvbuf(stdout, 0LL, 2, 0LL);
  memset(s, 0, sizeof(s));
  printf("FLAG: ");
  __isoc99_scanf("%47s", s);
  if ( !memcmp(s, s2, 0x30uLL) )
    puts("Correct!");
  else
    puts("Wrong...");
  return 0LL;
}

しかし後述するように、バイナリ中には暗号化されたデータや関数が隠されています。

tsgdbinary.py読解

tsgdbinary.pyは295行あります。また、pkuwl = chr(115) + chr(101) + chr(116)のように、無意味な識別子名が使われていたり、chr関数で難読化されていたりします。

人力で読解したり動的解析したりすると、次のことが分かりました:

• 全体的に、gdb.executeでGDBコマンドを実行したり、gdb.parse_and_evalでレジスタ値を設定したりします。
  • RIPレジスタ含めて変更します。これによって制御フローを自由に操っています。
• plm(o)関数では、引数のファイル名のファイルを開いて内容を読み込み、Pythonのexec関数で実行します。
• 一部の関数では、バイナリ中から1バイトXORで文字列を復号して、GDBスクリプトやPythonスクリプトとして実行します:
  • koop関数では、「mmap関数で0x72433a3c000へ読み書き可能なメモリを確保して、0x7fffffffe460から0x30バイトコピー」するGDBスクリプトを、バイナリの0x4040E0から305バイト分読み込み、0x3Cの1バイトXORで復号して、実行します。
  • pom関数では、「0x72433a3c000から0x30バイト分、別のバイト列を使ってXOR」するPythonスクリプトを、バイナリの0x404220から270バイト分、0x48の1バイトXORで復号して、exec関数で実行します。
    • この時、復号したPythonスクリプトではkoqw(wole, meiq+i)等の、tsgdbinary.py側で定義する識別子名を使います。そのためtsgdbinary.py側で識別子名を読みやすく変更していると、復号したPythonスクリプトで実行エラーになる点に注意が必要です。
  • トップレベルの241行、ou = xec(lku + 0x3080, 71)付近で、「mmap関数で0x6547ea867000へ読み書き実行可能なメモリを確保」するGDBスクリプトを、バイナリの0x404080から71バイト分読み込み、0xD7の1バイトXORで復号して、実行します。
• ehc関数は、GDB history用ファイルのN行目(0-indexed)を実行します。使用箇所を確認するとehc(4)と5行目を実行するものであり、すべてcontinueのために実行していました。
• lpe(e)関数やolu(e)関数では、どうやらブレークポイントの設定アドレスを操作しているようです(詳細未調査)。

なお、tsgdbinary.pyには、動的解析を妨げる次の処理が存在しました。

• kn関数で、sys.stdoutとsys.stderrを/dev/nullへ設定します。
• yd関数で、sys.stdoutとsys.stderrを閉じ、sys.__stdout__とsys.__stderr__から再設定します。

上述の処理があるとprintデバッグ等ができなくなるので、コメントアウトして動作確認しました。

動作確認時は、次の方法などを使いました(前述した通り、tsgdbinary.pyの識別子名を変更していると内部実行するPythonスクリプトで実行エラーになる点に注意が必要です):

• print関数を使って引数等を表示しました。出力結果はgdbの出力にそのまま反映されました。なお、前述した、sys.stdout等を操作する解析妨害処理には注意してください。
• gdb.execute("x/48bx 0x72433a3c000")等で、メモリ内容等を確認しました。
• 処理場所を確認したいところでraise SystemExit("TEST!")等でGDBスクリプトを中断させて、後はGDBのプロンプトで各種コマンドを使って確認しました。

読解結果の概要

全体として、次の処理を行っているようです:

1. scanf関数でフラグを入力させます。
2. (復号したGDBスクリプトで)mmap関数で0x72433a3c000へメモリを確保して、0x7fffffffe460から0x30バイトをコピーします。
3. (復号したPythonスクリプトで)0x72433a3c000内容と別のなにかのバイト列を使って、バイナリの4013F9の関数で1バイトずつXORを取って変換します。
4. (復号したGDBスクリプトで)mmap関数で0x6547ea867000へ読み書き実行可能なメモリを確保します。メモリの初期内容は0で埋められた状態です。
5. 262行目のfor i in range(0, 6)のループで、次の内容を実行します。
   1. 0x6547ea867000へ、0x401000 + 0x3340 + 0x1000 * iから、0x1000バイト分XORします。
      • 初回では0x6547ea867000内容は0で埋まった状態であるため、実質的に0x404340からのコピーになります。その内容は、第2引数を使った巨大なswitch/caseです。第1引数は使いません。
      • 2回目以降は、前の値とのXORになります。2回目～6回目全てで、また違った内容の巨大なswitch/case処理です。
      • それらの内容は、x/4096i 0x6547ea867000 などのGDBコマンドで確認しました。後で使います。
   2. 0x6547ea867000 + luwe[i]のアドレスを関数として、第2引数を0x6547ea867000 + 8*iからの8バイト整数として呼び出します。巨大なswitch/caseに基づいた値が返ります。
   3. 巨大なswitch/caseの戻り値と、固定値0x89FC76AEF8D6A8C3を引数に、0x4015a5の関数(uint64_t2つの足し算関数)を呼び出します。その結果の8バイトを、今回のループでの変換結果とします。
6. 上のループの変換結果と、0x6547ea867fa0からの0x30バイトを引数に、mainのmemcmp呼び出しへ移って正誤判定します。

フラグ入力書き込み先と0x7fffffffe460

上の読解結果から分かるように、tsgdbinary.pyでは0x7fffffffe460から0x30バイトを入力として扱います。しかし私の環境では、最初のscanf関数で何を入力しても、0x7fffffffe460からの内容は固定でした。調査中のメモです:

0x7fffffffe460: 0x04    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7fffffffe468: 0x38    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7fffffffe470: 0x05    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7fffffffe478: 0x0d    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7fffffffe480: 0x07    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x7fffffffe488: 0x00    0x50    0xfc    0xf7    0xff    0x7f    0x00    0x00

gdb.execute("b __isoc99_scanf")でscanf関数へブレークポイントを設定して書き込み先アドレスを調べると、私の場合は0x7fffffffe140と異なるアドレスになりました。一方で複数回実行しても常に0x7fffffffe140になりました。

しばらくの間、「フラグとして何を入力しようとも、最後のmemcmp関数の引数も、途中のあらゆるデータ内容も、一切何も変化しない」と困っていました。他の問題へ移ったりした後に、「もしかして、0x7fffffffe460にはscanf関数での入力内容が格納されるべきアドレスなのでは？」と考えました。koop()関数の、本来動作の0x7fffffffe460からコピーする処理の後に、次の処理を追加しました:

    # 手元環境での文字列入力先アドレス 0x7fffffffe140 へ置き換えます
    gdb.execute("""
    set $src = 0x7fffffffe140
    set $dst = 0x72433a3c000
    set $size = 4
    set $count = 0x30 / $size
    set $i = 0
    while ($i < $count)
        set $value = *(int *)($src + $i * $size)
        set *(int *)($dst + $i * $size) = $value
        set $i = $i + 1
    end
    """)
    print("After copy from input")
    gdb.execute("x/48bx 0x72433a3c000")

こうすると、途中に流れるデータがようやく入力内容に従って変化してくれました。

ソルバーと実行結果

本問題を解くにあたって、動作確認用出力を追加したり、確認結果からまた別のものを探したりしていました。最終的なソルバーです:

#!/usr/bin/env python3

import pwn

# memcmp実行著効前での「gdb.execute("x/6gx $rsi")」
expected_values = [
    0xA2AEFE64311FD342,
    0xD596AC1C4805AD02,
    0xA7F7D0B5234B62E6,
    0xAC3A6008591956CA,
    0x07B88E0A05C47D75,
    0x387973ADEF3D794F,
]


# `0x401000 + 0x3340 + 0x1000 * i`からのXORして復元した、巨大switch/case関数の一部
inv_switch_case_list = [
    # 0x6547ea867568:      movabs rax,0x66221e42571b1b1d
    # 0x6547ea867572:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea867576:      jne    0x6547ea86758c
    # 0x6547ea867578:      movabs rax,0x18b287b538492a7f
    # 0x6547ea867582:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea867586:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea86758a:      pop    rbp
    # 0x6547ea86758b:      ret
    0x66221E42571B1B1D,
    # 0x6547ea8672ba:      movabs rax,0x2063383b75652f77
    # 0x6547ea8672c4:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea8672c8:      jne    0x6547ea8672de
    # 0x6547ea8672ca:      movabs rax,0x4b9a356d4f2f043f
    # 0x6547ea8672d4:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea8672d8:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea8672dc:      pop    rbp
    # 0x6547ea8672dd:      ret
    0x2063383B75652F77,
    # 0x6547ea86787b:      movabs rax,0x6b655a6961635674
    # 0x6547ea867885:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea867889:      jne    0x6547ea86789f
    # 0x6547ea86788b:      movabs rax,0x1dfb5a062a74ba23
    # 0x6547ea867895:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea867899:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea86789d:      pop    rbp
    # 0x6547ea86789e:      ret
    0x6B655A6961635674,
    # 0x6547ea8677ec:      movabs rax,0x641733226f50717c
    # 0x6547ea8677f6:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea8677fa:      jne    0x6547ea867810
    # 0x6547ea8677fc:      movabs rax,0x223de9596042ae07
    # 0x6547ea867806:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea86780a:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea86780e:      pop    rbp
    # 0x6547ea86780f:      ret
    0x641733226F50717C,
    # 0x6547ea8671a7:      movabs rax,0x624f786e344f6e7a
    # 0x6547ea8671b1:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea8671b5:      jne    0x6547ea8671cb
    # 0x6547ea8671b7:      movabs rax,0x7dbc175b0cedd4b2
    # 0x6547ea8671c1:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea8671c5:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea8671c9:      pop    rbp
    # 0x6547ea8671ca:      ret
    0x624F786E344F6E7A,
    # 0x6547ea867502:      movabs rax,0x1c566d342c774434
    # 0x6547ea86750c:      cmp    QWORD PTR [rbp-0x10],rax
    # 0x6547ea867510:      jne    0x6547ea867526
    # 0x6547ea867512:      movabs rax,0xae7cfcfef666d08c
    # 0x6547ea86751c:      mov    QWORD PTR [rbp-0x8],rax
    # 0x6547ea867520:      mov    rax,QWORD PTR [rbp-0x8]
    # 0x6547ea867524:      pop    rbp
    # 0x6547ea867525:      ret
    0x1C566D342C774434,
]

MOD = 1 << 64
temp_bytes = bytearray()
for i in range(len(expected_values)):
    switch_case_result = (expected_values[i] - 0x89FC76AEF8D6A8C3 + MOD) % MOD
    # print(f"{switch_case_result:x}") # この出力を基に、switch/caseのアセンブリ出力から検索して、対応する元の値を検索しました。
    temp_bytes.extend(inv_switch_case_list[i].to_bytes(8, "little"))

# print(f"{temp_bytes.hex() = }")

# 入力に「T」1文字を与えて、XOR結果を確認しました。
# fmt:off
xor_values = [
    0x1d,    0x48,    0x5c,    0x14,    0x16,    0x58,    0x59,    0x56,
    0x15,    0x49,    0x10,    0x40,    0x58,    0x59,    0x54,    0x10,
    0x06,    0x09,    0x00,    0x00,    0x07,    0x05,    0x04,    0x07,
    0x49,    0x41,    0x0f,    0x1a,    0x17,    0x00,    0x48,    0x03,
    0x1e,    0x0c,    0x10,    0x55,    0x00,    0x1c,    0x10,    0x00,
    0x05,    0x2a,    0x16,    0x5e,    0x4d,    0x10,    0x56,    0x1c,
    ]
xor_values[0] ^= ord("T")
# fmt:on

print(pwn.xor(temp_bytes, xor_values).decode())

実行しました:

$ ./solve.py
TSGCTF{0bfu5ca70r_can_al50_u53_gdb_and_b1nary}\x00\x00
$

フラグを入手できました: TSGCTF{0bfu5ca70r_can_al50_u53_gdb_and_b1nary}

[Reversing, med] serverless (17 teams solves, 221 points)

CTFにもサーバーレスの波が到来！

サーバーは問題の概要説明のため補助的に提供されており、問題を解くためにサーバーに接続する必要はありません。

http://<REDACTED>:20906/TSGCTF{dummy_dummy}

配布ファイルとしてcompose.ymlがありました:

$ file *
compose.yml: ASCII text
$ wc -l compose.yml
5495 compose.yml
$

はい、compose.ymlの1ファイルだけです！見たときに声が出ました！

内容は、別のYMLデータが埋め込まれたものでした:

services:
  proxy:
    image: envoyproxy/envoy:v1.31.4
    restart: no
    command: ["--log-level info", "--config-path /etc/envoy/envoy.yaml"]
    ports:
      - "20906:20906"
    configs:
      - source: proxy.yaml
        target: /etc/envoy/envoy.yaml
configs:
  proxy.yaml:
    content: |
      admin:
      (中略)

埋め込まれた内容をproxy.yamlとして保存して確認すると、途中から置き換えパターンが長く長く続くものでした:

admin:
  address:
    socket_address: { address: 127.0.0.1, port_value: 0 }
static_resources:
  clusters:
    # 省略
  listeners:
  - name: api-listener
    address:
      socket_address: { address: 0.0.0.0, port_value: 20906 }
    filter_chains:
    - filters:
      - name: envoy.filters.network.http_connection_manager
        typed_config:
          # いくつかのメンバー省略
          route_config:
            name: local_route
            virtual_hosts:
            - name: local_service
              domains: ["*"]
              routes:
              - match:
                  # please decode `%7B` to `{` and `%7D` to `}` before submission.
                  safe_regex: { regex: "^/TSGCTF%7B[a-zA-Z0-9_-]+%7D/?$" }
                route:
                  cluster: redirect-cluster
                  timeout: 1s
                  internal_redirect_action: HANDLE_INTERNAL_REDIRECT
              - match:
                  prefix: "/"
                direct_response:
                  status: 200
                  body:
                    inline_string: "ill-formed"
          # 他のメンバー省略
  - name: redirect-listener
    # 丸々省略
  - name: internal-listener
    address:
      socket_address: { address: 0.0.0.0, port_value: 20908 }
    filter_chains:
    - filters:
      - name: envoy.filters.network.http_connection_manager
        typed_config:
          # いくつかのメンバー省略
          route_config:
            name: local_route
            virtual_hosts:
            - name: local_service
              domains: ["*"]
              routes:
              - match:
                  path: "/"
                direct_response:
                  status: 200
                  body:
                    inline_string: "ok"
              - match:
                  safe_regex: { regex: "^(.*)/eq.*" }
                redirect:
                  regex_rewrite:
                    pattern: { regex: "^(.*)/eq" }
                    substitution: "\\1(w)(s)(p)/"
              # 以降同様にひたすらmatch/redirectの組が続く、全5000行
              - match:
                  safe_regex: { regex: "^(.*)S\\(s\\).*" }
                redirect:
                  regex_rewrite:
                    pattern: { regex: "^(.*)S\\(s\\)" }
                    substitution: "\\1"
              - match:
                  prefix: "/"
                direct_response:
                  status: 200
                  body:
                    inline_string: "ng"

リダイレクトパターンを見やすくする

Yamlでは1つのmatch/redirectの組が6行にわたっていて、全体を見るのが大変です。内容をざっくり確認するパーサーを書きました:

#!/usr/bin/env python3

import yaml  # pip install pyyaml

# compose.ymlからyaml部分を別ファイル保存しています
with open("proxy.yaml") as f:
    data = yaml.safe_load(f)

listeners = data["static_resources"]["listeners"]
internal_listener = next(
    listener for listener in listeners if listener["name"] == "internal-listener"
)
routes = internal_listener["filter_chains"][0]["filters"][0]["typed_config"][
    "route_config"
]["virtual_hosts"][0]["routes"]
for route in routes:
    # print(route)
    match = route["match"]

    if "path" in match:
        # pathが"/"まで簡約されたら正解
        assert match["path"] == "/"
        assert route["direct_response"]["body"]["inline_string"] == "ok"
    elif "prefix" in match:
        # 簡約失敗時は不正解
        assert match["prefix"] == "/"
        assert route["direct_response"]["body"]["inline_string"] == "ng"
    else:
        # 簡約本体
        regex: str = match["safe_regex"]["regex"]
        pattern: str = route["redirect"]["regex_rewrite"]["pattern"]["regex"]
        substitution: str = route["redirect"]["regex_rewrite"]["substitution"]
        assert regex == pattern + ".*"

        pattern_prefix = "^(.*)"
        assert pattern.startswith(pattern_prefix)
        pattern = pattern[len(pattern_prefix) :]
        pattern = pattern.replace("\\-", "-")
        pattern = pattern.replace("\\(", "(")
        pattern = pattern.replace("\\)", ")")
        assert "\\" not in pattern

        def is_digit_or_lower_or_hyphen(s: str):
            return all(
                map(
                    lambda c: c == "-"
                    or (ord("a") <= ord(c) <= ord("z"))
                    or (ord("0") <= ord(c) <= ord("9")),
                    s,
                )
            )

        assert (
            not pattern.startswith("/")
            or pattern == r"/)"
            or is_digit_or_lower_or_hyphen(pattern[1:])
        )

        substitution_prefix = r"\1"
        assert substitution.startswith(substitution_prefix)
        substitution = substitution[len(substitution_prefix) :]

        left_paren_count = substitution.count("(")
        right_paren_count = substitution.count(")")
        assert (
            substitution == ")"
            or substitution == "(/"
            or left_paren_count == right_paren_count
        )

        print(f"{pattern.ljust(16)} => {substitution}")

./parse.py | tee output.txt のように実行して、結果をoutput.txtへ保存しました。output.txtは最後のソルバーでも使います。

なお、compose.ymlのcommand箇所を--log-level debugへ変更してコンテナを起動すると、大量のログの中でリダイレクト推移が分かります。その状態でサンプル入力を与えて、リダイレクト状況を観察したりしました。

リダイレクトパターン考察

リダイレクトのパターンを調べると、次のような構成になっていることが分かりました。

• フラグ始まりのTSGCTF{の開き波括弧%7Bを、(/と、「開き丸括弧 + スラッシュ」へ変換。
• フラグ終わりの}の閉じ波括弧%7Dを、)と閉じ丸括弧へ変換。
• \)を、)と閉じ波括弧へ変換。つまりスラッシュを除去。
• _を、)(/と、「閉じ丸括弧 + 開き丸括弧 + スラッシュ」へ変換。
• /eq等の「スラッシュ + 1～2文字の英小文字or数字orハイフン」を、(w)(s)(p)/等の「丸括弧で囲まれた小文字3個 + スラッシュ」へ変換。
• /6i等の「スラッシュ + 1～2文字の英小文字or数字orハイフン」を、(s)(y)(n)RZK/等の「丸括弧で囲まれた小文字3個 + 大文字3個 + スラッシュ」へ変換。
• /wz等の「スラッシュ + 1～2文字の英小文字or数字orハイフン」を、cDPL/等の「小文字1個 + 大文字3個 + スラッシュ」へ変換。
• M(m)等の「大文字 +　丸括弧で囲まれた小文字」を空文字列へ変換。これはA～Zの26文字すべてでこの組み合わせが存在します。
• (パターン上は%7D%7Bを+へ変換するものもあります。しかしこれは起こらないでしょう)

パターンすべてを通して考察すると、スラッシュの位置がパターンで重要なことが分かります。

• 開き波括弧やアンダースコアによってスラッシュを生成
• /eq等のパターンで、文字列を変換しつつ、スラッシュを後ろへ移動
• /)と閉じ丸括弧まで到達するとスラッシュを消去

目標は、リダイレクト結果が/になることです。そのためには、TSGCTF文字列を除去する必要があります。除去できるパターンを考えるとTSGCTF(f)(t)(c)(g)(s)(t)パターンを完成させる必要があることが分かります。

つまり、tsfctfの文字について、以下のリダイレクト先を満たすパターンを発見する必要があります:

• 最初のリダイレクト先は、tABC/形式の「目標の小文字1個 + 大文字3個 + スラッシュ」パターン
• 途中のリダイレクト先は (c)(b)(a)XYZ/形式の「直前の大文字3個を打ち消す丸括弧で囲まれた小文字3個 + 別の大文字3個 + スラッシュ」パターンの0回以上の繰り返し
• 最後のリダイレクト先は、(z)(y)(x)/形式の、「直前の大文字3個を打ち消す丸括弧で囲まれた小文字3個 + スラッシュ」パターン

ソルバーと実行結果

考察結果をもとに、目的のパターンを探索するソルバーを書きました。書いているうちは「/aパターンを使いたいのに/abパターンが競合したら大変そう」と思いましたが、幸いにしてその競合は起こりませんでした。ソルバーです:

#!/usr/bin/env python3

import dataclasses
import re


@dataclasses.dataclass(frozen=True)
class Node:
    pattern: str  # /-z などでは「-z」。
    begin_lower: str  # なければ空文字列
    paren_lower: str  # 大体3文字のはず
    upper: str  # 大体3文字、たまに0文字
    upper_to_reversed_lower: str  # reversed(upper.tolower())、処理削減用


def construct_node_list() -> tuple[list[Node], dict[str, str]]:
    node_list: list[Node] = []
    paren_lower_to_pattern_dict: dict[str, str] = {}  # ["wsp"]=>"eq"
    with open("output.txt") as f:
        for line in f.readlines():
            elem = line.split("=>")
            pattern: str = elem[0].strip()
            substitution: str = elem[1].strip()
            if not pattern.startswith("/"):
                continue
            if pattern == "/)":
                continue

            pattern = pattern[1:]
            assert substitution.endswith("/")

            if substitution.startswith("("):
                m = re.match(
                    r"^\(([0-9a-z-])\)\(([0-9a-z-])\)\(([0-9a-z-])\)([A-Z]{3})?/$",
                    substitution,
                )
                assert m
                paren_lower = m.group(1) + m.group(2) + m.group(3)
                upper = m.group(4) or ""
                upper_to_reversed_lower = upper.lower()[::-1]
                if upper:
                    node_list.append(
                        Node(
                            pattern,
                            begin_lower="",
                            paren_lower=paren_lower,
                            upper=upper,
                            upper_to_reversed_lower=upper_to_reversed_lower,
                        )
                    )
                else:
                    paren_lower_to_pattern_dict[paren_lower] = pattern
            else:
                m = re.match(r"^([0-9a-z-])?([A-Z]{3})/$", substitution)
                assert m
                begin_lower = m.group(1)
                upper = m.group(2) or ""
                upper_to_reversed_lower = upper.lower()[::-1]
                node_list.append(
                    Node(
                        pattern=pattern,
                        begin_lower=begin_lower,
                        paren_lower="",
                        upper=upper,
                        upper_to_reversed_lower=upper_to_reversed_lower,
                    )
                )
    return (node_list, paren_lower_to_pattern_dict)


# node_list[i] -> node_list[j] が連結 => j in list[i]
def construct_edge_list(node_list: list[Node]) -> list[list[int]]:
    edge_list: list[list[int]] = [[] for i in range(len(node_list))]
    for i in range(len(node_list)):
        for j in range(i + 1, len(node_list)):
            # upper_to_reversed_lower が空文字列のやつがいます。
            if node_list[i].upper_to_reversed_lower == node_list[j].paren_lower:
                edge_list[i].append(j)
                edge_list[j].append(i)
    return edge_list


node_list, paren_lower_to_pattern_dict = construct_node_list()
edge_list = construct_edge_list(node_list)
# pprint.pprint(node_list)
# pprint.pprint(edge_list)
# pprint.pprint(paren_lower_to_pattern_dict)
# for i in range(len(node_list)):
#     print(f"{node_list[i].pattern} => '{node_list[i].begin_lower}'; ", end="")
#     print(", ".join(map(str, edge_list[i])))


def explorer(expected_begin_lower: str) -> list[str]:
    result_pattern_list = []
    is_used_node_list = [False] * len(node_list)

    def dfs(current_upper_to_reversed_lower: str) -> bool:
        # print(result_pattern_list)
        if current_upper_to_reversed_lower in paren_lower_to_pattern_dict:
            result_pattern_list.append(
                paren_lower_to_pattern_dict[current_upper_to_reversed_lower]
            )
            return True

        for inner_node_index in range(len(node_list)):
            if is_used_node_list[inner_node_index]:
                continue
            if (
                node_list[inner_node_index].paren_lower
                != current_upper_to_reversed_lower
            ):
                continue

            result_pattern_list.append(node_list[inner_node_index].pattern)
            is_used_node_list[inner_node_index] = True
            succeeded = dfs(node_list[inner_node_index].upper_to_reversed_lower)
            if succeeded:
                return succeeded
            # is_used_node_list[inner_node_index] = False # 連結成分でだめなら何やってもだめ。
            result_pattern_list.pop()

        return False

    for outer_node_index in range(len(node_list)):
        if node_list[outer_node_index].begin_lower != expected_begin_lower:
            continue

        result_pattern_list.append(node_list[outer_node_index].pattern)
        is_used_node_list[outer_node_index] = True
        succeeded = dfs(node_list[outer_node_index].upper_to_reversed_lower)
        if succeeded:
            return result_pattern_list
        # is_used_node_list[outer_node_index] = False # 連結成分でだめなら何やってもだめ。
        result_pattern_list.pop()

    raise Exception(f"Not found for {expected_begin_lower = }")


flag = "TSGCTF{"
for c in reversed("TSGCTF"):
    pattern = explorer(c.lower())
    assert pattern

    if c != "F":
        flag += "_"
    flag += "".join(pattern)
flag += "}"
print(flag)

実行しました:

$ time ./solve.py
TSGCTF{http-red1rect5-can_funct10n_as-tur1ng-c0mp1ete_m4rk0v-a1g0rithm_proce55ing_funct10n}
./solve.py  0.06s user 0.01s system 78% cpu 0.094 total
$ curl -i http://localhost:20906/TSGCTF%7Bhttp-red1rect5-can_funct10n_as-tur1ng-c0mp1ete_m4rk0v-a1g0rithm_proce55ing_funct10n%7D
HTTP/1.1 200 OK
content-length: 2
content-type: text/plain
date: Sun, 15 Dec 2024 11:10:38 GMT
server: envoy
x-envoy-upstream-service-time: 222

ok
$

フラグを入手できました: TSGCTF{http-red1rect5-can_funct10n_as-tur1ng-c0mp1ete_m4rk0v-a1g0rithm_proce55ing_funct10n}

感想

• どの問題も面白い問題でした！
• 自己GOT書き換えを初めて見ました。驚きました！
• SQLiteのバイトコードに少しだけ詳しくなれました。カーソルやテーブル関連の高機能な命令があるということは分かりました。
• バイナリ+GDBスクリプトの構成も面白かったです。デバッガーそのものや、デバッガー用スクリプトの強力さを再認識しました。
• 検索パターンと置き換え結果のパターンで、「全体として何をしているか」「どの状態を目的にするか」を考えるのも面白かったです。