Posts | Archive

CSAW CTF 2011 Kernel Exploitation Challenge

My challenge for this year's NYU Poly CSAW CTF finals was a Linux kernel exploitation challenge disguised as a crypto challenge. The challenge and solution are described below.

The Challenge

Each team is given unprivileged remote shell access to a Linux VM. There is a custom kernel module, SqueamishOssifrage.ko, loaded. The full source code of the kernel module is provided to the team. SqueamishOssifrage.c is reproduced below (and can be downloaded here):

/*
 * SqueamishOssifrage.c
 * CSAW 2011 CTF Challenge Kernel Module
 * Jon Oberheide <jon@oberheide.org>
 *
 * Decrypt the flag...and win?
 *
 * Information:
 *
 *   /proc/csaw/key:     get/set symmetric key
 *   /proc/csaw/encrypt: get/set encrypted payload
 *   /proc/csaw/decrypt: get/set decrypted payload
 *
 * Example usage:
 *
 *   # set a key
 *   $ echo "this is a key" > /proc/csaw/key
 *
 *   # encrypt payload with that key
 *   $ echo "hello world" > /proc/csaw/encrypt
 *
 *   # retrieve encrypted payload
 *   $ cat /proc/csaw/encrypt > payload.enc
 *
 *   # decrypt encrypted payload
 *   $ cat payload.enc > /proc/csaw/decrypt
 *
 *   # retrieve decrypted payload
 *   $ cat /proc/csaw/decrypt > payload.dec
 *
 *   # view decrypted payload
 *   $ cat payload.dec
 *   hello world
 */

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/proc_fs.h>
#include <linux/string.h>
#include <asm/uaccess.h>

#define PROC_CSAW    "csaw"
#define PROC_KEY     "key"
#define PROC_ENCRYPT "encrypt"
#define PROC_DECRYPT "decrypt"
#define MAX_LENGTH   128
#define MAX_ROUNDS   64
#define DELTA        0x9e3779b9

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Jon Oberheide");
MODULE_DESCRIPTION("CSAW 2011 CTF Challenge Kernel Module");

static struct proc_dir_entry *proc_csaw;
static struct proc_dir_entry *proc_key;
static struct proc_dir_entry *proc_decrypt;
static struct proc_dir_entry *proc_encrypt;

static uint32_t key[4] = { 0, 0, 0, 0 };
static uint32_t rounds = 32;
static unsigned char enc_blob[MAX_LENGTH];
static unsigned char dec_blob[MAX_LENGTH];

void encrypt(uint32_t k[], char *buf, int len, int rounds) __attribute__ ((optimize (0)));
void decrypt(uint32_t k[], char *buf, int len, int rounds) __attribute__ ((optimize (0)));
void scramble(uint32_t k[], uint32_t t[], uint32_t *s, uint32_t *d) __attribute__ ((optimize (0)));
void descramble(uint32_t k[], uint32_t t[], uint32_t *s, uint32_t *d) __attribute__ ((optimize (0)));

void
scramble(uint32_t k[], uint32_t t[], uint32_t *s, uint32_t *d)
{
    uint32_t n, sbox[8];
    uint32_t y = t[0], z = t[1];
    uint32_t delta = DELTA, sum = 0;

    for (n = 0; n < 8; n++) {
        sbox[n] = key[n % 4];
    }
    for (n = 0; n < 32; n++) {
        sum += delta;
        y += ((z << 4) + k[0]) ^ (z+sum) ^ ((z >> 5) + k[1]);
        z += ((y << 4) + k[2]) ^ (y+sum) ^ ((y >> 5) + k[3]);
    }
    t[0] = y; s = d + n; t[1] = z;
}

void
encrypt(uint32_t k[], char *buf, int len, int rounds)
{
    int i;

    if (rounds >= 0) {
        if (rounds % 3 == 0) {
            k[0] ^= k[1]; k[1] ^= k[0]; k[0] ^= k[1];
            k[2] ^= k[3]; k[3] ^= k[2]; k[2] ^= k[3];
        } else if (rounds % 3 == 1) {
            k[0] ^= k[2]; k[2] ^= k[0]; k[0] ^= k[2];
            k[1] ^= k[3]; k[3] ^= k[1]; k[1] ^= k[3];
        } else if (rounds % 3 == 2) {
            k[0] ^= k[3]; k[3] ^= k[0]; k[0] ^= k[3];
            k[2] ^= k[1]; k[1] ^= k[2]; k[2] ^= k[1];
        }
        encrypt(k, buf, len, rounds-1);
    } else {
        for (i = 0; i < len / 8; i++) {
            scramble(k, (uint32_t *)(buf + (i * 8)), (uint32_t *) 0, (uint32_t *) DELTA);
        }
    }
}

void
descramble(uint32_t k[], uint32_t t[], uint32_t *s, uint32_t *d)
{
    uint32_t n, sbox[8];
    uint32_t y = t[0], z = t[1];
    uint32_t delta = DELTA, sum = delta << 5;

    for (n = 0; n < 8; n++) {
        sbox[n] = key[n % 4];
    }
    for (n = 0; n < 32; n++) {
        z -= ((y << 4) + k[2]) ^ (y + sum) ^ ((y >> 5) + k[3]);
        y -= ((z << 4) + k[0]) ^ (z + sum) ^ ((z >> 5) + k[1]);
        sum -= delta;
    }
    t[0] = y; s = d + n; t[1] = z;
}

void
decrypt(uint32_t k[], char *buf, int len, int rounds)
{
    int i;

    if (rounds >= 0) {
        if (rounds % 3 == 0) {
            k[0] ^= k[1]; k[1] ^= k[0]; k[0] ^= k[1];
            k[2] ^= k[3]; k[3] ^= k[2]; k[2] ^= k[3];
        } else if (rounds % 3 == 1) {
            k[0] ^= k[2]; k[2] ^= k[0]; k[0] ^= k[2];
            k[1] ^= k[3]; k[3] ^= k[1]; k[1] ^= k[3];
        } else if (rounds % 3 == 2) {
            k[0] ^= k[3]; k[3] ^= k[0]; k[0] ^= k[3];
            k[2] ^= k[1]; k[1] ^= k[2]; k[2] ^= k[1];
        }
        decrypt(k, buf, len, rounds-1);
    } else {
        for (i = 0; i < len / 8; i++) {
            descramble(k, (uint32_t *)(buf + (i * 8)), (uint32_t *) 0, (uint32_t *) DELTA);
        }
    }
}

int
key_write(struct file *file, const char __user *ubuf, unsigned long count, void *data)
{
    char buf[MAX_LENGTH];

    printk(KERN_INFO "csaw: called key_write\n");

    memset(buf, 0, sizeof(buf));

    if (count > MAX_LENGTH) {
        count = MAX_LENGTH;
    }
    if (copy_from_user(&buf, ubuf, count)) {
        return -EFAULT;
    }

    sscanf(buf, "%16c\t%d", (char *) key, &rounds);

    return count;
}

int
key_read(char *page, char **start, off_t off, int count, int *eof, void *data)
{
    printk(KERN_INFO "csaw: called key_read\n");

    memcpy(page, key, sizeof(key));

    return sizeof(key);
}

int
encrypt_write(struct file *file, const char __user *ubuf, unsigned long count, void *data)
{
    char buf[MAX_LENGTH];
    uint32_t session[4];

    printk(KERN_INFO "csaw: called encrypt_write\n");

    memset(buf, 0, sizeof(buf));

    if (count > MAX_LENGTH) {
        count = MAX_LENGTH;
    }
    if (copy_from_user(&buf, ubuf, count)) {
        return -EFAULT;
    }

    memcpy(session, key, sizeof(key));

    encrypt(session, buf, sizeof(buf), rounds);

    memcpy(enc_blob, buf, sizeof(buf));

    return count;
}

int
encrypt_read(char *page, char **start, off_t off, int count, int *eof, void *data)
{
    printk(KERN_INFO "csaw: called encrypt_read\n");

    memcpy(page, enc_blob, sizeof(enc_blob));

    return sizeof(enc_blob);
}

int
decrypt_write(struct file *file, const char __user *ubuf, unsigned long count, void *data)
{
    char buf[MAX_LENGTH];
    uint32_t session[4];

    printk(KERN_INFO "csaw: called decrypt_write\n");

    memset(buf, 0, sizeof(buf));

    if (count > MAX_LENGTH) {
        count = MAX_LENGTH;
    }
    if (copy_from_user(&buf, ubuf, count)) {
        return -EFAULT;
    }

    memcpy(session, key, sizeof(key));

    decrypt(session, buf, sizeof(buf), rounds);

    memcpy(dec_blob, buf, sizeof(buf));

    return count;
}

int
decrypt_read(char *page, char **start, off_t off, int count, int *eof, void *data)
{
    printk(KERN_INFO "csaw: called decrypt_read\n");

    memcpy(page, dec_blob, sizeof(dec_blob));

    return sizeof(dec_blob);
}

int __init
csaw_init(void)
{
    printk(KERN_INFO "csaw: loading module\n");

    memset(enc_blob, 0, sizeof(enc_blob));
    memset(dec_blob, 0, sizeof(dec_blob));

    proc_csaw = proc_mkdir(PROC_CSAW, NULL);

    proc_key = create_proc_entry(PROC_KEY, 0666, proc_csaw);
    proc_key->read_proc = key_read;
    proc_key->write_proc = key_write;

    proc_encrypt = create_proc_entry(PROC_ENCRYPT, 0666, proc_csaw);
    proc_encrypt->read_proc = encrypt_read;
    proc_encrypt->write_proc = encrypt_write;

    proc_decrypt = create_proc_entry(PROC_DECRYPT, 0666, proc_csaw);
    proc_decrypt->read_proc = decrypt_read;
    proc_decrypt->write_proc = decrypt_write;

    printk(KERN_INFO "csaw: created /proc/csaw entries\n");

    return 0;
}

void __exit
csaw_exit(void)
{
    printk(KERN_INFO "csaw: unloading module\n");

    remove_proc_entry(PROC_KEY, proc_csaw);
    remove_proc_entry(PROC_ENCRYPT, proc_csaw);
    remove_proc_entry(PROC_DECRYPT, proc_csaw);
    remove_proc_entry(PROC_CSAW, NULL);

    printk(KERN_INFO "csaw: removed /proc/csaw entries\n");
}

module_init(csaw_init);
module_exit(csaw_exit);

A Crypto Challenge?

Lots of crypto looking stuff, huh? As the header tells you, the kernel module exposes an interface via /proc/csaw to set a key and encrypt/decrypt payloads:

/proc/csaw/key:     get/set symmetric key
/proc/csaw/encrypt: get/set encrypted payload
/proc/csaw/decrypt: get/set decrypted payload

The teams are also provided with a flag.enc file, which supposedly contains the flag if it can be decrypted successfully. The flag.enc file is as follows:

$ hexdump -C flag.enc
00000000  a6 8f 6d 42 a0 dd 0e a6  3b 95 99 94 d3 15 10 5a  |..mB....;......Z|
00000010  8d 9d ba 41 d1 4b 78 ba  ec c0 79 93 d8 05 23 a7  |...A.Kx...y...#.|
00000020  5c 25 80 c5 10 63 68 c4  8c 67 e6 68 42 f5 b5 87  |\%...ch..g.hB...|
00000030  42 b3 3d 51 3f a4 f2 85  1b e1 49 7f 20 12 55 49  |B.=Q?.....I. .UI|
00000040  07 00 d9 f4 e8 9e 17 5d  3c 69 fb 84 a3 4b 7d 25  |.......]<i...K}%|
00000050  d4 da 0c 3f 95 94 21 47  ab 1b 66 1e 13 c9 be d9  |...?..!G..f.....|
00000060  f2 57 57 48 21 2c 2c e2  e6 b6 b9 df 03 88 6b 25  |.WWH!,,.......k%|
00000070  15 14 bc 19 2a f0 6c b6  b8 d6 9e 6e 28 c1 5d 39  |....*.l....n(.]9|
00000080

That's it! Can you solve the challenge?

Spoiler Alert!

I will provide the solution further down the page, so stop reading right now if you want to try your hand at exploiting the challenge on your own!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

SPOILER AHEAD - STOP SCROLLING IF YOU DON'T WANT TO SEE THE SOLUTION!

The Solution

Ok, that should be enough! Now to the actual solution. Hopefully you were able to get past the first part of guessing the right key, which should be straightforward to any crypto folks based on the SqueamishOssifrage name or via a quick Google search:

http://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage

Armed with the key, you can decrypt the flag.enc as follows:

$ echo "The Magic Words are Squeamish Ossifrage" > /proc/csaw/key
$ cat flag.enc > /proc/csaw/decrypt
$ cat /proc/csaw/decrypt
Congrats on decrypting the secret payload. Unfortunately, your flag is
not here. It is actually in /root/flag.txt. Good luck.

So, despite the appearance of the code, this was not actually a crypto challenge, but rather a kernel exploitation challenge. Would you expect anything else? ;-)

The next step in the challenge was to find the vulnerability in the SqueamishOssifrage kernel module. Most of the module is a hacked up TEA cipher that doesn't really do anything interesting other than act as a red herring.

If you look in the key_write() function, you can see that there's an undocumented ability to set the number of rounds of the TEA cipher:

sscanf(buf, "%16c\t%d", (char *) key, &rounds);

So, you can set the TEA cipher to perform 666 rounds by doing:

echo -e "testtesttesttest\t666" > /proc/csaw/key

Now, the TEA cipher is implemented recursively, which is key (no pun intended) to the challenge. So the more rounds you specify, the deeper the call stack in the kernel.

On Linux kernels, you have a limited kernel stack (commonly 8k on x86). If you have a deeply recursive kernel function, especially one where the amount of recursion is controlled by an attacker, you may end up clobbering sensitive data in the thread_info structure which is stored at the base of your process' kernel stack. More detailed info on Linux kernel stack overflows and how to exploit them is available here in a previous blog post:

So if you made it this far, the challenge is more or less straightforward at this point. Just continue trying more rounds (and therefore a deeper kernel call stack) until the "tip" of the stack hits the restart_block.fn function pointer that is stored at the base of the kernel stack. You'll probably crash the kernel a few times by recursing too deep and clobbering sensitive members of the thread_info structure, but with a few tries, you'll eventually determine the right number of rounds to directly hit the restart_block member (which on the target VM/kernel was 114 rounds).

You can easily test whether your restart_block function pointer has been clobbered by calling the restart_syscall system call:

syscall(__NR_restart_syscall);

In this case, the tip of the kernel stack is not directly under your control, but is indeed a userspace address (0x9e3779b9 passed as the last parameter to scramble/descramble). So by clobbering the restart_block function pointer with a userspace address, all you need to do is mmap your payload at that userspace address and trigger its execution via the restart_syscall system call.

To make the privesc a little more challenging, /proc/kallsyms is not readable as an unprivileged user, so retrieving the usual prepare_kernel_cred/commit_creds symbols is thwarted. However, I did leave a System.map world-readable in /boot which provides the equivalent symbols.

After escalating privileges, simply read the flag from /root/flag.txt.

Copyright © 2015 - Jon Oberheide <jon at oberheide dot org>.