2023-11-25 — last updated 2024-02-12
DownUnderCTF 2023 took place in early September of this year. Afterwards I had the intention to do a few write-ups, but moving and switching jobs delayed that process for a bit. I finally found some time to polish a few of my notes for the challenges I spent time on during the CTF.
This page contains write-ups for the following challenges:
What is your name?
What is your quest?
What is your favourite colour?
We’re presented with a page that asks us three familiar questions. Looking at the source, we find the following Javascript snippet:
<script id="challenge" src="text/javascript">
function cross() {
prompt("What is your name?");
prompt("What is your quest?");
answer = prompt("What is your favourite colour?");
if (answer == "blue") {
document.getElementById('word').innerText = "flag is DUCTF{" + answer + "}";
cross = escape;
}
else {
document.getElementById('word').innerText = "you have been cast into the gorge";
cross = unescape;
}
}
</script>
Easy enough! But answering blue leads us to a swift cast into the gorge. Indeed, logging the output of prompt shows us the answer is an empty string..
Upon closer inspection, we note src="text/javascript". That’s a cleverly disguised Javascript file, with the following contents:
prompt = function (fun, x) {
let answer = fun(x);
if (!/^[a-z]{13}$/.exec(answer)) return "";
let a = [], b = [], c = [], d = [], e = [], f = [], g = [], h = [], i = [], j = [], k = [], l = [], m = [];
let n = "blue";
a.push(a, a, a, a, a, a, a, a, a, a, a, a, a, a, a, a, a, b, a, a, a, a, a, a, a, a);
b.push(b, b, b, b, c, b, a, a, b, b, a, b, a, b, a, a, b, a, b, a, a, b, a, b, a, b);
c.push(a, d, b, c, a, a, a, c, b, b, b, a, b, c, a, b, b, a, c, c, b, a, b, a, c, c);
d.push(c, d, c, c, e, d, d, c, c, c, c, b, c, c, d, c, b, d, a, d, c, c, c, a, d, c);
e.push(a, e, f, c, d, e, a, e, c, d, c, c, c, d, a, e, b, b, a, d, c, e, b, b, a, a);
f.push(f, d, g, e, d, e, d, c, b, f, f, f, a, f, e, f, f, d, a, b, b, b, f, f, a, f);
g.push(h, a, c, c, g, c, b, a, g, e, e, c, g, e, g, g, b, d, b, b, c, c, d, e, b, f);
h.push(c, d, a, e, c, b, f, c, a, e, a, b, a, g, e, i, g, e, g, h, d, b, a, e, c, b);
i.push(h, a, d, b, d, c, d, b, f, a, b, b, i, d, g, a, a, a, h, i, j, c, e, f, d, d);
j.push(b, f, c, f, i, c, b, b, c, j, i, e, e, j, g, j, c, k, c, i, h, g, g, g, a, d);
k.push(i, k, c, h, h, j, c, e, a, f, f, h, e, g, c, l, c, a, e, f, d, c, f, f, a, h);
l.push(j, k, j, a, a, i, i, c, d, c, a, m, a, g, f, j, j, k, d, g, l, f, i, b, f, l);
m.push(c, c, e, g, n, a, g, k, m, a, h, h, l, d, d, g, b, h, d, h, e, l, k, h, k, f);
walk = a;
for (let c of answer) {
walk = walk[c.charCodeAt() - 97];
}
if (walk != "blue") return "";
return {toString: () => _ = window._ ? answer : "blue"};
}.bind(null, prompt);
eval(document.getElementById('challenge').innerText);
It iterates over the characters in our answer, and moves through the arrays. Each array contains references to the next; if we end up at array n, we have supposedly entered the correct input.
We can simply work our way backwards manually. Starting at m, there is only a singular n at index [4]. We then find an m at index [11] in array l, and an l in array k at index [15], et cetera.
This leads to the sequence [4, 11, 15, 17, 20, 15, 0, 2, 2, 4, 1, 4, 17]. Adding 97 and reversing the sequence, we get: rebeccapurple.
DUCTF{rebeccapurple}
Just a simple RSA problem with some extra equations.
There are two RSA challenges in the crypto category – presumably this one is easy.
We get a Python script that performs RSA encryption, but also leaves us with a few hints: two integers of the form $a \cdot p + b \cdot q$, with $0 \le a < 2^{12}$ and $0 \le b < 2^{312}$.
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
hints = []
for _ in range(2):
a, b = randint(0, 2**12), randint(0, 2**312)
hints.append(a * p + b * q)
FLAG = open('flag.txt', 'rb').read().strip()
c = pow(bytes_to_long(FLAG), e, n)
print(f'{n = }')
print(f'{c = }')
print(f'{hints = }')
The challenge also comes with output.txt, supposedly containing the encrypted flag.
n = 14660571735908952489002993827903664741357457851760908649720903490242781200599279200941555625377480322300761434214784243355865531476885778933049205035635857511724445636189412010232288883997962334374976967072473569268104938242162374146303713780734432405002257811743659454802783820254267629648005198676228493220090910570651981720956782436579563383210521881408697895574988998166073088181182460781625583449895170069416296911080037108242200943819190329592722210240372478763827674403639468179156438805357971476738826284179397702996711111034575635088841241354137431691608708586537071546432546205216081312804647066737570894023
c = 3014228465839024222531913178876755997202579066571946568117957620992626184075072645592929274030475721860516337363549964023809640935927422141596369521625373032887992171544987963053649222268839362296140298254567557247243959631873642653628768056590251288717876967238844363668216669345111199235366782491099628442127257864721021039424850656858549634126388057122624827577450574032676846584352473272792426900482052166907296663510940614653937816719545779923761921955012981313093729997041764588048873232122578759116941501754753461228949083630697583974029795241994896139613416128261382360080426690047897663352151650683784366653
hints = [67585409877128467394273747844708023711838736622300021631288299732185049081526590070916229113028139589562794761992161702552127144257559125951801065743849636934249630981744074216493369003468402441168300904480336834940777808019851079394816890016422575441233207435464900093733380879874842695796266071203345796326004992321513696172431553195641602978421349425073721183337173252205696314692954319121838740596, 782369796451936135579812610738083472168315963073406077738956209771703291533885768715713836864555818764933142195016274849912821793067896876879775874626375680114617513069518529094752988467057235780327327874593431997790580089256851961020111777818708980408558380525792906243767981446549436960403836084157427542914546700430818824224973669530677353137795028589982623354988306696364282934565224135139011055012]
While $b$ is a large number, $a$ is actually comparatively small. This suggests we can iterate over all values of $a$; even trying all pairs of $a_1$ and $a_2$ (for hint 1 and 2) is totally feasible. We just need a way to recognize the correct one.
Let’s label the hints $h_i = a_i \cdot p + b_i \cdot q$. We need a way to isolate either one of the two primes, as we can then compute the $gcd$ of that term with $n = p \cdot q$ to find the respective prime.
Computing $h_1 - h_2$ gives us $(a_1 - a_2) \cdot p + (b_1 - b_2) \cdot q$. That does not quite cancel out, as $a_1$ and $a_2$ differ. But what if we instead compute $a_2h_1 - a_1h_2$?
\begin{align} a_2h_1 - a_1h_2 &= a_2(a_1 \cdot p + b_1 \cdot q) - a_1(a_2 \cdot p + b_2 \cdot q)\\ &= a_1a_2 \cdot p + a_2b_1 \cdot q - a_1a_2 \cdot p - a_1b_2 \cdot q\\ &= (a_1a_2 - a_1a_2) \cdot p + (a_2b_1 - a_1b_2) \cdot q \\ &= (a_2b_1 - a_1b_2) \cdot q \end{align}
This implies we can compute $gcd(a_2h_1 - a_1h_2, n)$ to find $q$ and essentially recover the RSA key.
We still need a way to recognize $a_1$ and $a_2$. Computing the $gcd$ works for this as well: if we have the wrong values, we will simply get $1$, as $a_2h_1 - a_1h_2$ won’t share a factor with $n$.
from math import gcd
with open("output.txt", "r") as f:
data = f.read()
exec(data)
def find_q(hints, n):
for a1 in range(2**12):
for a2 in range(2**12):
maybe_q = gcd(a2 * hints[0] - a1 * hints[1], n)
if 1 < maybe_q < n:
print(f"Found q: {maybe_q}")
return maybe_q
q = find_q(hints, n)
p = n // q
phi = (p - 1) * (q - 1)
e = 0x10001 # from challenge
d = pow(e, -1, phi)
m = pow(c, d, n)
m_bytes = m.to_bytes(length=512, byteorder="big")
print(m_bytes.decode("utf-8"))
DUCTF{gcd_1s_a_g00d_alg0r1thm_f0r_th3_t00lbox}
I know FNV is not a cryptographic hash function, but it's secure since nobody wrote a tool to break it.
This is another crypto challenge. The challenge file consists of a Python snippit that implements the FNV hash function.
#!/usr/bin/env python3
import os
def fnv1(s):
h = 0xcbf29ce484222325
for b in s:
h *= 0x00000100000001b3
h &= 0xffffffffffffffff
h ^= b
return h
TARGET = 0x1337133713371337
print("Welcome to FNV!")
print(f"Please enter a string in hex that hashes to 0x{TARGET:016x}:")
s = bytearray.fromhex(input())
if fnv1(s) == TARGET:
print('Well done!')
print(os.getenv('FLAG'))
else:
print('Try again... :(')
The challenge boils down to finding a pre-image for the 16-byte value 1337133713371337. The FNV operations are invertible, but each step absorbs a byte of input. This means we start on both ends, and perform a classic meet-in-the-middle attack.
During the CTF, I quickly whipped up some lazy Python code to perform the attack. Not knowing the target length, I gradually increase the length until, at length 7 (i.e., two halves of 4), the code takes too long to run.
from math import ceil
def fnv1(s):
h = 0xCBF29CE484222325
for b in s:
h *= 0x00000100000001B3
h &= 0xFFFFFFFFFFFFFFFF
h ^= b
return h
def fnv1_op(s, h=0xCBF29CE484222325):
h *= 0x00000100000001B3
h &= 0xFFFFFFFFFFFFFFFF
h ^= s
return h
def fnv1_op_inv(s, h):
h ^= s
h *= 0xCE965057AFF6957B
h &= 0xFFFFFFFFFFFFFFFF
return h
# TARGET = 0x1337133713371337
TARGET = fnv1(b"abcde") # this works!
MAX_INPUT_LEN = 6 # raising this to 8 takes too long
N = ceil(MAX_INPUT_LEN / 2)
forward = []
backward = []
for i in range(N):
forward.append({})
backward.append({})
for c in range(256):
forward[0][fnv1_op(c)] = bytes([c])
for c in range(256):
backward[0][fnv1_op_inv(c, h=TARGET)] = bytes([c])
for i in range(N - 1):
for h, s in forward[i].items():
for c in range(256):
forward[i + 1][fnv1_op(c, h=h)] = s + bytes([c])
for h, s in backward[i].items():
for c in range(256):
backward[i + 1][fnv1_op_inv(c, h=h)] = bytes([c]) + s
f_acc = {}
for i in range(N):
f_acc |= forward[i]
b_acc = {}
for i in range(N):
b_acc |= backward[i]
overlap = f_acc.keys() & b_acc.keys()
for o in overlap:
print(f_acc[o], b_acc[o])
Remark that 0xCE965057AFF6957B is the multiplicative inverse of 0x00000100000001B3, modulo 264.
After the CTF I learned that indeed, meet-in-the-middle is one of the possible solution paths (the other, as always, is LLL). A slightly more efficient approach seems necessary, though; the above code takes roughly 22 seconds of wall-clock time on my M1 Macbook Air, and presumably in the order of (at least!) 512x as long when increasing from 6 to 8 bytes – assuming we would have enough resources (
I’ve been meaning to gain some familiarity with Rust or Go for these kind of things, as sometimes Python abstractions create unnecessary bottlenecks. Now that the CTF has ended, I wanted to try ot implement the same attack in Rust.
use std::collections::{HashMap, HashSet};
fn fnv1(s: &[u8]) -> u64 {
let mut h: u64 = 0xcbf29ce484222325;
for &b in s {
h = h.wrapping_mul(0x00000100000001b3);
h ^= b as u64;
}
h
}
fn fnv1_op(s: u8, h: Option<u64>) -> u64 {
let mut h = h.unwrap_or(0xcbf29ce484222325);
h = h.wrapping_mul(0x00000100000001b3);
h ^ (s as u64)
}
fn fnv1_op_inv(s: u8, h: u64) -> u64 {
let mut h = h;
h ^= s as u64;
h.wrapping_mul(14886173955864302971)
}
fn main() {
let target = fnv1(b"abcde");
assert!(target == 2260915612829301322);
const MAX_INPUT_LEN: u32 = 6;
let half_len: u32 = (MAX_INPUT_LEN as f32 / 2.0).ceil() as u32;
let mut forward: Vec<HashMap<u64, Vec<u8>>> = Vec::new();
let mut backward: Vec<HashMap<u64, Vec<u8>>> = Vec::new();
for _ in 0..half_len {
forward.push(HashMap::new());
backward.push(HashMap::new());
}
for c in 0..=255 {
forward[0].insert(fnv1_op(c, None), vec![c]);
backward[0].insert(fnv1_op_inv(c, target), vec![c]);
}
for i in 0..(half_len - 1) as usize {
// Use split_at_mut to get two refs (forward[i] and forward[i+1])
let (previous, current) = forward.split_at_mut(i + 1);
for (h, s) in &previous[i] {
for c in 0..=255 {
let mut s1 = s.clone();
s1.push(c);
current[0].insert(fnv1_op(c, Some(*h)), s1);
}
}
let (previous, current) = backward.split_at_mut(i + 1);
for (h, s) in &previous[i] {
for c in 0..=255 {
let mut s1 = Vec::new();
s1.push(c);
s1.append(&mut s.clone());
current[0].insert(fnv1_op_inv(c, *h), s1);
}
}
}
// We cannot call .intersection on the keys of a HashMap directly..
let mut f_acc = HashMap::new();
for map in forward.iter() {
f_acc.extend(map);
}
let mut b_acc = HashMap::new();
for map in backward.iter() {
b_acc.extend(map);
}
let set1: HashSet<&u64> = f_acc.keys().cloned().collect();
let set2: HashSet<&u64> = b_acc.keys().cloned().collect();
for hash in set1.intersection(&set2) {
println!("{:?} {:?}", f_acc[hash], b_acc[hash]);
}
}
I learned a bunch about Rust in the process, but it should not come as a surprise that literally translating the code does no good. Presumably the Python code is actually fairly efficient for what it’s doing — it’s just not doing smart things. Let’s try a less flashy approach, with less object copying and a bit more thought. We can readily make two observations.
The first observation is that we do not need to create two maps and compute their overlap; it suffices to create a map in one direction, and check every computed value against that map when working our way back.
The second concerns the size of the map. A quick glance at our memory usage shows that creating a map based on 4-byte input strings quickly grows too big. Indeed, storing only the 64-bit key for each of those inputs would already amount to 8 x 2564 = 34359738368 bytes, or 32 GiB. Let’s limit ourselves to 3-byte inputs, instead.
package main
import (
"fmt"
"sync"
)
func fnv1_op(h uint64, a uint64) uint64 {
h *= 0x00000100000001B3
h ^= a
return h
}
func fnv1_op_inv(s uint64, h uint64) uint64 {
h ^= s
h *= 0xCE965057AFF6957B
return h
}
type entry struct {
length int
data [3]uint8
}
func main() {
target := uint64(0x1337133713371337)
fmt.Printf("Target: %x\n", target)
table := make(map[uint64]entry)
var ha, hb, hc uint64
var a, b, c uint64
fmt.Println("Building table..")
for a = 0; a < 256; a++ {
fmt.Println(a)
ha = fnv1_op(0xCBF29CE484222325, a)
table[ha] = entry{1, [3]uint8{uint8(a), 0, 0}}
for b = 0; b < 256; b++ {
hb = fnv1_op(ha, b)
table[hb] = entry{2, [3]uint8{uint8(a), uint8(b), 0}}
for c = 0; c < 256; c++ {
hc = fnv1_op(hb, c)
table[hc] = entry{3, [3]uint8{uint8(a), uint8(b), uint8(c)}}
}
}
}
var wg sync.WaitGroup
wg.Add(256)
fmt.Println("Finding matches..")
val, ok := table[target]
if ok {
fmt.Println("Found", val.data[:val.length])
}
for a = 0; a < 256; a++ {
go func(a uint64) {
defer wg.Done()
var ha, hb, hc, hd uint64
var b, c, d uint64
ha = fnv1_op_inv(target, a)
if val, ok := table[ha]; ok {
fmt.Println("Found", val.data[:val.length], a)
}
for b = 0; b < 256; b++ {
hb = fnv1_op_inv(ha, b)
if val, ok := table[hb]; ok {
fmt.Println("Found", val.data[:val.length], b, a)
}
for c = 0; c < 256; c++ {
hc = fnv1_op_inv(hb, c)
if val, ok := table[hc]; ok {
fmt.Println("Found", val.data[:val.length], c, b, a)
}
for d = 0; d < 256; d++ {
hd = fnv1_op_inv(hc, d)
if val, ok := table[hd]; ok {
fmt.Println("Found", val.data[:val.length], d, c, b, a)
}
}
}
}
}(a)
}
wg.Wait()
fmt.Println("Done!")
}
The above Go code runs in roughly a minute of wall-clock time to check all 7-byte inputs; 3 bytes using the map, and 4 bytes working our way back. Now that we understand the problem a bit better, it is obvious that this is unlikely to lead to a successful pre-image: under the simplifying assumption that FNV1 is a random bijection, we would expect only a single 8-byte pre-image to exist. The probability for a 7-byte input to exist would then be only 0.4%.
A naive attempt to use a key-value-store to store the lookup table on disk leads to dreadful performance, and was, quite frankly, not much fun to implement. Trivially extending the above code to check the 8-byte input space runs in 5 hours and 39 minutes of totally non-scientific wall clock time (i.e., while casually using my laptop), and indeed finds a single 8-byte pre-image: 68 29 F4 51 9A 54 C9 0B.
The solution provided by the challenge author makes use of LLL. Blindly running the code immediately finds a working solution – given the performance described above, that is as good a reason as any to dig in and find out what’s going on here.
TODO