LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

1日1CTFAdvent Calendar 2024

Day 13
@hiikunZ

Warmup SQLite (TSG CTF 2024) WriteUp

Posted at

はじめに

この記事は 1日1CTF Advent Calendar 2024 の 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()
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 に埋め込まれたものと一致する入力を求めよ。という問題。

考察

情報を探すと、ほぼ このページ にめっちゃ書いてある。

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 で書き直す。

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

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

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}

感想

つらかった

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?