/ 2023-11-25-write-ups-DUCTF-2023
back to the top

Write-ups for Down Under CTF 2023

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:

The bridgekeeper’s 3rd question

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}

apbq rsa i

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}

FNV

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 (spoiler: we do not).

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.

FNV using lattice attacks

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’s a great motivation to dig in and find out what’s going on here.

TODO