ASIS CTF 2021 Writeups
Table of Contents
These are writeups for the first CTF I participated in while it was running. Before that, I had only practiced on picoCTF, pwn.college, and Google CTF Beginners Quest challenges outside live events. I played with KITCTF, the CTF team of the Karlsruhe Institute of Technology.
Factory #
Challenge description:
In the simplest terms, factory misco-graphy is the ratio of output to input!
The challenge consists of a single PDF. Opening it shows only the text “Real-World Misco-graphy”. Checking the metadata with exiftool and running binwalk to search for embedded files did not yield any interesting results. After that, I tried to linearize the PDF with qpdf, which produced the following warnings:
WARNING: factory.pdf: file is damaged
WARNING: factory.pdf (offset 11250): xref not found
WARNING: factory.pdf: Attempting to reconstruct cross-reference table
qpdf: operation succeeded with warnings; resulting file may have some problems
So I googled PDF cross-reference tables. They are quite an interesting part of the PDF file format. You can read more about them in this article:
Understanding the PDF File Format: PDF Xref Tables Explained
The details don’t matter here, though. Near the end of the PDF, there is a startxref marker:
[...]
xref
0 10
0000000000 65535 f
0000000015 00000 n
0000000074 00000 n
0000000310 00000 n
0000000507 00000 n
0000000635 00000 n
0000001463 00000 n
0000002113 00000 n
0000011014 00000 n
0000011065 00000 n
trailer
<<
/Info 9 0 R
/ID [<c6204cbba3e9874bd89c21cf85c0b9bb> <d851a1d3e37ffdda1b67f1174cd1bf1b>]
/Root 8 0 R
/Size 10
>>
startxref
11250
%%EOF
There is also an earlier startxref followed by a %%EOF marker. PDF viewers use the final one. Deleting everything after the first %%EOF reveals the “real” PDF containing the flag.
ASIS{PDF_1N_PDF_iZ_A_T4sK_fOR_fOreEnSic5_L0v3RS}
Gesture #
The challenge description says:
A gesture is a file that is intended to indicate or emphasize something!
Note: flag is lowercase string, put the flag in ASIS{flag} too.
The challenge file is gesture.img.
Running file gesture.img gives us gesture.img: data, so that sounds promising.
We have more luck with binwalk gesture.img. The first entry in the table is:
DECIMAL HEXADECIMAL DESCRIPTION
--------------------------------------------------------------------------------
0 0x0 YAFFS filesystem, little endian
The remaining entries include many files that look like the contents of an Android device. Now we need to extract the data from the image. YAFFS stands for “Yet Another Flash File System” and is supported by Android, but as far as I can tell, it is not widely used these days. YAFFS also runs on a NASA satellite. I tried a bunch of discontinued tools before finding one that could actually extract the data. Just mounting it would be too easy. The tool that ended up working for me was unyaffs2 from yaffs2utils.
./unyaffs2 -p 512 -s 16 ../../gesture.img ../../extracted/
Let’s look at what we extracted. This command finds all files and runs the file command on each one, because file extensions are not to be trusted:
find -type f -exec file {} \;
Two results stand out: an encrypted Signal backup and this weird file:
./Android/data/com.android.gallery3d/cache/.nomedia/.latentorism: JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16, comment: "Compressed by jpeg-recompress", progressive, precision 8, 186x60, components 3
In fact, this file contains a mirrored image of the Signal backup code.
I used signal-back to extract the Signal backup. The extracted media confused me a bit: it included the same image as above, but with a different file size and compression.
One message stands out:
83,3,15,1,,1634817424071,1634817423795,1634817423912,31337,1,-1,10485780,1,0,,"-. ...-- ...- . .-. ..--.- --... .-. ..- ..... - ..--.- - .---- -. . ..--.- ... . ...-- ..--.- .. ..--.- ....- ..--.- -. ----- - .... .---- -. -.... ..--.- .. ..... ..--.- .-.. ----- ----- ..--.- .--. ...-- .-. -.-. . -. --... ..--.- ... ...-- -.-. ..- .-. .
Opportunity is missed by most people because it is dressed in overalls and looks like work. --Thomas Edison
-. ...-- ...- . .-. ..--.- --... .-. ..- ..... - ..--.- - .---- -. . ..--.- ... . ...-- ..--.- .. ..--.- ....- ..--.- -. ----- - .... .---- -. -.... ..--.- .. ..... ..--.- .-.. ----- ----- ..--.- .--. ...-- .-. -.-. . -. --... ..--.- ... ...-- -.-. ..- .-. .",,GCM,-1,0,0,0,0,1,,0,1634817484896,0,0,91dde932-5fad-46d0-9f37-f60451dad76f,-1
The Morse code surrounding the quotation encodes the flag:
N3VER_7RU5T_T1NE_SE3_I_4_N0TH1N6_I5_L00_P3RCEN7_S3CURE
Convert this text to lowercase and wrap it in ASIS{...}.
Crypto Warm up #
Challenge description:
Recovering secrets is hard, but there are always some easy parts to do it!
We are given the following Python script and its output in a text file:
#!/usr/bin/env python3
from Crypto.Util.number import *
import string
from secret import is_valid, flag
def random_str(l):
rstr = ''
for _ in range(l):
rstr += string.printable[:94][getRandomRange(0, 93)]
return rstr
def encrypt(msg, nbit):
l, p = len(msg), getPrime(nbit)
rstr = random_str(p - l)
msg += rstr
while True:
s = getRandomNBitInteger(1024)
if is_valid(s, p):
break
enc = msg[0]
for i in range(p-1):
enc += msg[pow(s, i, p)]
return enc
nbit = 15
enc = encrypt(flag, nbit)
print(f'enc = {enc}')
I looked at this challenge at the beginning of the CTF, but my teammate quickly solved it.
The key insight is that p equals len(enc). That leaves us looking for a value of s that satisfies is_valid(s, p). We can search for it by trying candidate values modulo p. Since we are working modulo a prime, we guess that the secret is_valid function checks for coprimality:
def is_valid(s, p):
return gcd(s, p) == 1
We can also use the known prefix, ASIS{, to recognize candidate decryptions. Let’s take the easy route to the flag:
#!/usr/bin/env python3
from Crypto.Util.number import *
import string
from math import gcd
import tqdm
def random_str(l):
rstr = ''
for _ in range(l):
rstr += string.printable[:94][getRandomRange(0, 93)] # one random char
return rstr # random string of length p -l
def is_valid(s, p):
return gcd(s, p) == 1
def encrypt(msg, nbit):
l = len(msg)
p = getPrime(nbit) # 15 Bit random prime, p = 19489
rstr = random_str(p - l)
msg += rstr
# len(msg) = p
while True:
s = getRandomNBitInteger(1024)
if is_valid(s, p):
break
enc = msg[0] # Because 0 can never be the result of pow
for i in range(p-1): # so we get p = len(enc)
# for none of the enc after index 0,1 we know if it is flag or random
enc += msg[pow(s, i, p)]
return enc
def decrypt(enc, p, s):
msg = ['A'] + ['#'] * (p-1)
for i in range(p - 1):
msg[pow(s, i, p)] = enc[i + 1]
return ''.join(msg)
nbit = 15
# enc = encrypt(flag, nbit)
# print(f'enc = {enc}')
with open('chal/output.txt', 'r') as f:
enc = f.read()[6:]
p = len(enc)
for s in tqdm.tqdm(range(2, p-1)):
if is_valid(s, p):
dec = decrypt(enc, p, s)
if dec.startswith('ASIS{'):
print(dec)
ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}
Madras #
Challenge description:
Madras is a great place to learn the occult! The occult, is a category of supernatural beliefs and practices which generally fall outside the scope of religion and science. Do you want to go Madras?
We are given the following script and output:
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import FLAG
def gentuple(nbit):
a, b, c = [getPrime(nbit // 3) for _ in '012']
return a, b, c
def encrypt(msg, params):
a, b, c = params
e, n = 65537, a * b * c
m = bytes_to_long(msg)
assert m < n
enc = pow(m, e, n)
return enc
nbit = 513
a, b, c = gentuple(nbit)
enc = encrypt(FLAG, (a, b, c))
print(f'a*b + c = {a*b + c}')
print(f'b*c + a = {b*c + a}')
print(f'c*a + b = {c*a + b}')
print(f'enc % a = {enc % a}')
print(f'enc % b = {enc % b}')
print(f'enc % c = {enc % c}')
print(f'enc = {enc}')
a*b + c = 4553352994596121904719118095314305574744898996748617662645730434291671964711800262656927311612741715902
b*c + a = 4414187148384348278031172865715942397786003125047353436418952679980677617016484927045195450392723110402
c*a + b = 2621331497797998680087841425011881226283342008022511638116013676175393387095787512291008541271355772802
enc % a = 1235691098253903868470929520042453631250042769029968
enc % b = 2235727505835415157472856687960365216626058343546572
enc % c = 1197976933648163722609601772402895844093866589777721
enc = 6238548897897912462708514382106387305984378113132192980353695746912882399991285268937548949835500837749446265632471076030233510866260067177632747513323223
This is an easy challenge when you know how to use a solver. I had the right idea, but used SageMath incorrectly and got stuck. That failure prompted me to learn more about SMT solvers. Here is an automated solution using Z3:
from z3 import *
s = Solver()
a = Int('a')
b = Int('b')
c = Int('c')
enc = 6238548897897912462708514382106387305984378113132192980353695746912882399991285268937548949835500837749446265632471076030233510866260067177632747513323223
s.add(a*b + c == 4553352994596121904719118095314305574744898996748617662645730434291671964711800262656927311612741715902)
s.add(b*c + a == 4414187148384348278031172865715942397786003125047353436418952679980677617016484927045195450392723110402)
s.add(c*a + b == 2621331497797998680087841425011881226283342008022511638116013676175393387095787512291008541271355772802)
s.add(enc % a == 1235691098253903868470929520042453631250042769029968)
s.add(enc % b == 2235727505835415157472856687960365216626058343546572)
s.add(enc % c == 1197976933648163722609601772402895844093866589777721)
if s.check() != sat:
print("No solution")
exit(0)
m = s.model()
a = m[a].as_long()
b = m[b].as_long()
c = m[c].as_long()
n = a * b * c
e = 65537
phi = (a - 1) * (b - 1) * (c - 1)
d = pow(e, -1, phi)
dec = pow(enc, d, n)
flag = bytes.fromhex(hex(dec)[2:]).decode('utf-8')
print(flag)