ASIS CTF 2021 Writeups
Table of Contents
These are writeups for the first CTF I participated in during a weekend. Before that I only solved some picoctf and Google Beginners quest challenges after the 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 file is only one pdf. Opening the only shows the text “Real-World Misco-graphy”. Checking the meta data with exiftool and doing binwalk to search for a file in the file did not yield any interesting results. After that I wanted to linearize the pdf with qpdf, but it gave me the error:
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 for this cross-reference table. It is actually a quite interesting part of the pdf file format specification used in older pdf versions. There is more on that in that article:
Understanding the PDF file Format - PDF Xref tables explained
But actually, the details don’t matter here. At the bottom of the pdf there is the startxref statement
[...]
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
But there is also another startxref followed by an %%EOF above. PDF viewers will take the bottom one. Deleting everything after the first %%EOF, shows 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
file gesture.img gives us gesture.img: data so that sounds promising.
But with binwalk gesture.img we have more luck. The first entry in the table is.
DECIMAL HEXADECIMAL DESCRIPTION
--------------------------------------------------------------------------------
0 0x0 YAFFS filesystem, little endian
After that there come a lot of files which look like the contents of an android device. So now we need to get the data out of 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 used so much these days. But YAFFS runs on a NASA satellite. I tried a bunch of discontinued tools before I found one which can actually extract the data. Just mounting it would be too easy. The one that ended up working me, is unyaffs2 from unyaffs2 (https://code.google.com/archive/p/yaffs2utils/)
./unyaffs2 -p 512 -s 16 ../../gesture.img ../../extracted/
Let’s look at what we got there (this command finds all files and executes the file command on it, because file extensions are not to be trusted)
find -type f -exec file {} \;
After looking at a couple of results, two that sticks out are 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
And in fact this file contains the signal backup code (mirrored).
I used https://github.com/xeals/signal-back for singal backup extraction. Extracting media got me a bit confused, because the same image as above was included again, but the file size and compression differ.
But looking at the messages there is one message, that sticks 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 wrapping of this is Morse code encoding the flag
N3VER_7RU5T_T1NE_SE3_I_4_N0TH1N6_I5_L00_P3RCEN7_S3CURE
It needs to be put 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 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}')
And the output of the last print as a txt file.
At the beginning of the CTF I looked at this challenge, but it was then quickly solved by my teammate.
The key insight is that we know p to be len(enc) and now the only thing stopping us from decrypting is the number s that satisfies is_valid with p. We can go through the whole ring by trying out s between 2 and p-1. We can guess that the secret is_valid is, as we are in a p modulus ring:
def is_valid(s, p):
return gcd(s, p) == 1
Actually, we do not even need to guess p, but could also exploit the fact that we know the first chars of msg to be ASIS{ . But let’s go 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 get
#!/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 got the idea, but used sage the wrong way and got stuck. But failing at this got me to learn more about SMT solvers. So here is a automatic solution with 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)