Warmup SQLite (TSG CTF 2024) WriteUp

# はじめに
この記事は [1日1CTF Advent Calendar 2024](https://qiita.com/advent-calendar/2024/1-day-1-ctf) の 13 日目の記事です。

# 問題
Warmup SQLite (問題出典: TSG CTF 2024)
> とりあえずSQLiteのバイトコードに慣れるか...

## 問題概要

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.

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

```sq: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
```

入力を `~~Your input is filled here~~` にして EXPLAIN すると `dump` ファイルの内容になる sql 文について、結果が `server.py` に埋め込まれたものと一致する入力を求めよ。という問題。

## 考察

情報を探すと、ほぼ [このページ](https://www.sqlite.org/opcode.html) にめっちゃ書いてある。

`dump` の形式は多分次の通り。

```
addr|opcode|p1|p2|p3|p4|p5
```

以下、資料を参考に `dump` をひたすら擬似コードに翻訳する。
***
```:dump-1
0|Init|0|88|0||0
```
```:擬似コード-1
PC = 88
```
`PC` はプログラムカウンタ。
***

```:dump-2
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
```

```:擬似コード-2
r[13] = ""
r[15] = 1
r[16] = 1
r[18] = 2
r[19] = 1
r[28] = 10
r[30] = 7
r[31] = 2
r[32] = 256
PC = 1
```
`r` は適当な配列。ここでは変数の初期化をしていそう。

***


```:dump-3
1|InitCoroutine|1|68|2||0
```

```:擬似コード-3
cor[1] = PC
PC = 68
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
PC = 2
```

`cor` はコルーチン用の配列。PC を保存し、コルーチンを開始している。

***
```:dump-4
68|SorterOpen|6|5|0|k(1,B)|0
69|InitCoroutine|1|0|2||0
```

```:擬似コード-4
r[6] = Sorter(1, TEXT)
cor[1] = PC
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
PC = 2
```

コルーチンの情報をすぐに書き換えている?

***

```:dump-5
70|Yield|1|79|0||0
```

```:擬似コード-5
swap(PC, cor[1]) ← Yield
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
if Coroutine が EndCoroutine で終了:
    PC = 79
```

コルーチンの処理を中断し、もとの処理に戻っている。`擬似コード-4` よりこのあと `PC` は `2` になる。

***

```:dump-6
2|OpenPseudo|1|2|3||0
3|OpenEphemeral|4|3|0||0
4|InitCoroutine|3|34|5||0
```

```:擬似コード-6
r[1] = OpenPseudo(r[2])
r[4] = OpenEphemeral
cor[3] = PC
PC = 34
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
PC = 5
```

新たなコルーチンを生成してる。

***

```:dump-7
34|InitCoroutine|3|0|5||0
```

```:擬似コード-7
cor[3] = PC
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
PC = 5
```

作ったばっかりのコルーチンを書き換えるの、何…?

***

```:dump-8
35|Yield|3|46|0||0
```

```:擬似コード-8
swap(PC, cor[3]) ← Yield
(Yield or EndCoroutine が呼び出されるまで Coroutine を実行)
if Coroutine が EndCoroutine で終了:
    PC = 46
```

`擬似コード-7` より `PC` は `5` に移る。

***

```:dump-9
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
```

```:擬似コード-9
r[3] = OpenPseudo(r[4])
r[5] = OpenEphemeral
r[5] = ""
r[6] = "~~Your input is filled here~~"
r[7] = -1
r[8] = mkrec([r[5], r[6], r[7]])
r[9] = r[5].newrowid()
r[5].insert(intkey=r[9],data=r[8])
☆:
if r[5] is empty:
    PC = 33
r[5] = r[5].first_entry
r[3] = NULL
r[4] = *r[5]
r[5].delete()
r[10] = r[3][0]
r[11] = r[3][1]
r[12] = r[3][2]
swap(PC, cor[3]) ← Yield
```

if 文に引っかからなければ、`疑似コード-8` の続きである `36` に移る。

***

```:dump-10
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
```

```:擬似コード-10
r[20] = r[10]
if r[13] == r[20]:
    PC = 45 (この疑似コードの最後)
r[21] = unicode(r[20])
r[22] = r[12]
r[23] = 0
r[20] = mkrec([r[21], r[22], r[23]])
r[24] = r[4].newrowid()
r[4].insert(intkey=r[24] data=r[20])
PC = 35
```

`r[13]` は空文字列。`疑似コード-8` に移る。が、今度は `疑似コード-8` の Yield で飛ぶ先が `疑似コード-9` の続きの `21` になる。

```:dump-11
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
```
```:擬似コード-11
r[8] = r[3][1]
if r[8] == r[13]:
    PC = 32 (この疑似コードの最後)
r[14] = r[3][1]
r[5] = substr(r[14],r[15],r[16])
r[17] = r[3][1]
r[6] = substr(r[17], r[18])
r[8] = r[3][2]
r[7] = r[19] + r[8]
r[8] = mkrec([r[5], r[6], r[7]])
r[9] = r[5].newrowid()
r[5].insert(intkey=r[9] data=r[8])
PC = 13
```
`疑似コード-9` の☆に移る。
ループしたので、以降 `疑似コード-9` の if 文で引っかかった場合を考える。

***


```:dump-12
33|EndCoroutine|3|0|0||0
```

```:擬似コード-12
EndCoroutine(cor[3])
```
`擬似コード-5` より `46` へ移る。

***

```:dump-13
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
```

```:擬似コード-13
if r[4] is empty:
    PC = 67
r[4] = r[4].first_entry
r[4].delete()
r[1] = NULL
r[2] = r[4]
r[25], r[26], r[27] = r[1]
swap(PC, cor[1]) ← Yield
```

if 文に引っかからなければ、`擬似コード-5` の続きである `71` に移る。

***
```:dump-14
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
```

```:擬似コード-14
r[33] = r[27]
if r[28] != r[33]:
    PC = 78 (この疑似コードの最後)
r[35] = r[25]
r[36] = r[27]
r[34] = r[26]
r[38] = mkrec([r[34], r[35], r[36]])
r[6].insert(intkey=r[34] data=r[38])
PC = 70
```

`疑似コード-5` へ移る。が、今度は `疑似コード-5` の Yield で飛ぶ先が `疑似コード-13` の続きの `54` になる。

***
```:dump
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
```
```:擬似コード
r[20] = r[1][2]
if r[28] <= r[20]:
    PC = 66 (この疑似コードの最後)
r[29] = r[1][0]
r[24] = r[29] * r[30]
r[20] = r[31] + r[24]
r[21] = r[20] % r[32]
r[22] = r[1][1]
r[20] = r[1][2]
r[23] = r[19] + r[20]
r[20] = mkrec([r[21], r[22], r[23]])
r[24] = r[4].newrowid()
r[4].insert(intkey=r[24] data=r[20])
```

`擬似コード-13` に移る。
ループしたので、以降 `疑似コード-13` の if 文で引っかかった場合を考える。

***
```:dump
67|EndCoroutine|1|0|0||0
```
```:擬似コード
EndCoroutine(cor[1])
```
`擬似コード-5` より `79` へ移る。

***

```:dump
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
```

```:擬似コード
r[7] = OpenPseudo(r[39])
if r[6] == NULL:
    PC = 87 (この疑似コードの最後)
r[6].sort()
r[29] = r[6]
r[37] = r[7][2]
r[36] = r[7][0]
r[35] = r[7][1]
output += [r[35], r[36], r[37]]

if next(r[6]):
    PC = 81 (r[29] = ... のところ)
exit()
```

***

わかりにくい。

一旦つなげてみる。

```
r[13] = ""
r[15] = 1
r[16] = 1
r[18] = 2
r[19] = 1
r[28] = 10
r[30] = 7
r[21] = 2
r[32] = 256
r[6] = Sorter(1, TEXT)
r[1] = OpenPseudo(r[2])
r[4] = OpenEphemeral
r[3] = OpenPseudo(r[4])
r[5] = OpenEphemeral
r[5] = ""
r[6] = "~~Your input is filled here~~"
r[7] = -1
r[8] = mkrec([r[5], r[6], r[7]])
r[9] = r[5].newrowid()
r[5].insert(intkey=r[9],data=r[8])
while True:
    if r[5] is empty:
        break
    r[5] = r[5].first_entry
    r[3] = NULL
    r[4] = *r[5]
    r[5].delete()
    r[10] = r[3][0]
    r[11] = r[3][1]
    r[12] = r[3][2]
    r[20] = r[10]
    if r[13] != r[20]:
        r[21] = unicode(r[20])
        r[22] = r[12]
        r[23] = 0
        r[20] = mkrec([r[21], r[22], r[23]])
        r[24] = r[4].newrowid()
        r[4].insert(intkey=r[24] data=r[20])
    r[8] = r[3][1]
    if r[8] == r[13]:
        continue
    r[14] = r[3][1]
    r[5] = substr(r[14],r[15],r[16])
    r[17] = r[3][1]
    r[6] = substr(r[17], r[18])
    r[8] = r[3][2]
    r[7] = r[19] + r[8]
    r[8] = mkrec([r[5], r[6], r[7]])
    r[9] = r[5].newrowid()
    r[5].insert(intkey=r[9] data=r[8])

while True:
    if r[4] is empty:
        break
    r[4] = r[4].first_entry
    r[4].delete()
    r[1] = NULL
    r[2] = r[4]
    r[25], r[26], r[27] = r[1]
    if r[28] == r[33]:
        r[35] = r[25]
        r[36] = r[27]
        r[34] = r[26]
        r[38] = mkrec([r[34], r[35], r[36]])
        r[6].insert(intkey=r[34] data=r[38])
    r[20] = r[1][2]
    if r[28] <= r[20]:
        continue
    r[29] = r[1][0]
    r[24] = r[29] * r[30]
    r[20] = r[31] + r[24]
    r[21] = r[20] % r[32]
    r[22] = r[1][1]
    r[20] = r[1][2]
    r[23] = r[19] + r[20]
    r[20] = mkrec([r[21], r[22], r[23]])
    r[24] = r[4].newrowid()
    r[4].insert(intkey=r[24] data=r[20])

r[7] = OpenPseudo(r[39])
r[6].sort()

while r[6]:
    r[29] = r[6].pop()
    r[37] = r[7][2]
    r[36] = r[7][0]
    r[35] = r[7][1]
    output += [r[35], r[36], r[37]]

exit()
```


自分が間違ったぽいところは雰囲気で察して直し、さらに変数名などをわかりやすくする。

```
sorter = Sorter(1, TEXT)

r[5].insert(["", "~~Your input is filled here~~", -1])

while not r[5] is empty:
    x, y, z = r[5].pop()
    if x != "":
        r[4].insert([ord(x[0]), z, 0])
    if y != "":
        r[5].insert([x[0],x[1:], z + 1])

while not r[4] is empty:
    x, y, z = r[4].pop()
    if 10 == z:
        sorter.insert([y, x, z])
    if 10 <= z:
        continue
    r[4].insert([(x * 7 + 2) % 256, y, z + 1])

sorter.sort()

while sorter:
    x, y, z = sorter.pop()
    r[37] = r[7][2]
    r[36] = r[7][0]
    r[35] = r[7][1]
    output += [y, x, z]

exit()
```

さらに整理して python で書き直す。
```python
inp = "~~Your input is filled here~~"
res = []
for i in range(0, len(inp)):
    x = ord(inp[i])
    for _ in range(10):
        x = (x * 7 + 2) % 256
    res.append(x)
print(res)
```

## solver

ここまでくれば逆変換は簡単。

```python
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]

flag = ""

for i in res:
    for _ in range(10):
        i = ((i - 2) * pow(7,-1,256)) % 256
    flag += chr(i)

print(flag)
```

flag: `TSGCTF{SELECT_hacker_FROM_nerds_WHERE_level="disaster"_LIMIT_64}`

## 感想
つらかった