==Phrack Inc.== Volume 0x0b, Issue 0x39, Phile #0x09 of 0x12 |=---------------------=[ Once upon a free()... ]=-----------------------=| |=-----------------------------------------------------------------------=| |=--------------=[ anonymous ]=-------------=| |=-------------=[ 초벌 번역 : Null@Root(Nanu9,River,Bear) ]=-------------=| |=------------=[ 의역 : amadoh4ck ]=-------------=| Unix system의 C 표준 라이브러리에는 메모리의 가변량을 동적으로 다루는 함수들이 있다. 프로그램들은 이 함수들을 이용하여 시스템으로부터 동적으로 메모리를 할당 받을 수 있다. OS(운영체제)는 "heap"이라고 알려진 메모리 chunk의 크기를 바꿀 수 있는 system call을 제공한다. 이것은 "brk"라는 system call이다. 이 system call 위에 malloc 인터페이스가 있다. 즉, malloc은 "brk" system call과 응용프로그램 사이의 계층(layer)을 제공하는 것이다. malloc은 응용프로그램의 요 구에 의해 하나의 큰 블록을 더 작은 chunk로 동적으로 분리하고, 제거할 수 있다. 또한, 이런 동작을 하는 동안 발생할 지도 모르는 단편화(조각화) 현상을 피할 수도 있다. malloc은 단지 동적으로 크기가 변하는 선형 파일 시스템(linear file system) 과 비교할 수 있다. malloc 인터페이스가 갖추어야 할 몇가지 설계 목표는 다음과 같다. - stability(안정성) - performance(성능) - avoidance of fragmentation(단편화 방지) - low space overhead(공간 오버헤드 줄임) 현재 몇개의 일반적인 malloc 구현들이 있다. 대부분 공통적인 것 중 하나가 AT&T 에 의해 구현된 System V 이고, 그 외에 GNU C Library 구현과 Microsoft 운영체제 의 malloc-similar(RtlHeap*) 인터페이스가 있다. 운영체제별로 사용하는 알고리즘을 나타낸 표가 다음과 같다. 알고리즘 | 운영 체제 ------------------------+-------------------------------------------------- BSD kingsley | 4.4BSD, AIX (compatibility), Ultrix BSD phk | BSDI, FreeBSD, OpenBSD GNU Lib C (Doug Lea) | Hurd, Linux System V AT&T | Solaris, IRIX Yorktown | AIX (default) RtlHeap* | Microsoft Windows * ------------------------+-------------------------------------------------- 대부분의 malloc 구현들이 이식(port)되기 쉽고 아키텍쳐에 독립적이라는 사실은 흥미로운 일이다. 이러한 malloc 구현의 대부분이 'brk' system call을 이용하여 만들어 졌다. #define으로 이러한 동작을 바꿀 수 있다. 필자가 알고 있는 구현들 모두가 ANSI C로 쓰여졌고, 최소화 했으며 온전하게 코드를 체크하지 않았다. 그들 대부분이 경고와 여분의 체크를 위해 특별한 컴파일 정의(#define)을 사용할 뿐이 다. 그것 조차 성능의 이유로 최종 build에서는 기본적으로 꺼 놓는다. 구현들 중 어떤 것은 버퍼오버플로우를 감지할 수 있도록 check하는 것들도 있다. 그러나, 이 러한 check들도 개발 과정의 오버플로우를 검출할 목적일 뿐이고 최종적인 단계의 exploit은 막지 못한다. Storing management info in-band 대부분의 malloc 구현들은 자신의 관리 정보를 저장하고 공유한다. 이러한 정보에는 사용되고 있거나 사용이 해제된(free) block들의 리스트, 메모리 block의 크기, heap 영역 자체에 포함된 유용한 정보들이 해당된다. malloc/free의 전체적인 아이디어가 응용프로그램의 동적 요구에 기초를 두고 있기 때문에, 관리 정보 또한 많은 자료(정보)들을 가지고 있다. 이러한 이유로, malloc은 단지 응용프로그램이 요청한 메모리의 양을 예약하는 것처럼 보이지만, 실제로는 응 용프로그램이 사용하는 메모리 block의 바로 앞과 뒤에 관리정보들을 저장하게 되는 것이다. 응용프로그램이 malloc 인터페이스를 통해 메모리 블록을 요구하게 되면 이것은 후에 버퍼오버플로우 취약점이 발생될 수 있다. 이것은 chunk 뒤의 데이타를 바꿈으로써 가능하게 된다. malloc 관리 구조체(management structures)를 수정하는 게 가능하게 되는 것이다. 이러한 방법은 Solar Designer의 "wizard-like exploit"에서 설명되었 다. malloc으로 할당된 버퍼의 오버플로우 공격의 핵심은 이 관리 정보를 수정함으로써 나중에 임의의 메모리에 오버라이트가 가능하게 된다는 것이다. 이 방법으로, pointer들이 writable process memory에 덮어쓰여 지고, linkage 테이 블이나 응용프로그램 레벨 데이타, 리턴 어디레스등이 수정 가능해 진다. 이러한 공격을 시도하기 위해 우리는 malloc구현의 내부를 깊이 훑어 보아야 한다. 이 기사는 GNU C 라이브러리와 System V 구현에 공통적으로 사용된 것을 논의하고, 리눅스, 솔라리스, IRIX 시스템하에서 malloc으로 할당된 버퍼들을 오버플로우를 이 용하여 조작하는 방법을 알아보려 한다. System V 의 malloc 구현 ======================= IRIX와 솔라리스는 self-adjusting binary trees에 기반을 둔 구현을 사용한다. 이 구현의 이론적 배경은 [2]에 설명되어져 있다. 이 구현의 기본적인 아이디어는 같은 크기의 malloc chunks list를 binary tree로 유지하는 것이다. 만일 같은 크기로 두개의 chunk를 할당한다면, 그들은 같은 노드 안에 있을 것이고, 이 노드의 같은 리스트 안에 있을 것이다. 그 트리는 트리 요소의 크기에 의해서 정렬 되어진다. The TREE structure (트리구조) TREE 구조 정의는 mallint.h안에서 찾을 수 있다. 이 파일에는 tree요소들에 쉽게 접 근하기 위해 사용되는 매크로들도 포함되어 있다. mallint.h 파일은 솔라리스 운영체 제 배포소스에서 발견할 수 있다.[4] 비록 같은 소스기반의 IRIX를 고칠 수는 없었지 만 여기에도 여러가지 비슷한 점이 있다. 몇몇 64비트 alignment를 제외하고 malloc 인터페이스는 같은 메미로 레이아웃과 함수들을 내부적으로 생성한다. 또한, 솔라리 스 소스를 IRIX 익스플로잇을 위해 사용할 수 있다. 각 tree element는 오버헤드를 피하거나, alignment를 강제로 설정하는 등 각각 다른 목적을 위해 사용될 수 있도록 union으로 정의되어 있다. /* the proto-word; size must be ALIGN bytes */ typedef union_w_ { size_t w_i; /* an unsigned int */ struct_t_ *w_p; /* a pointer */ char w_a[ALIGN]; /* to force size */ } WORD; Central TREE structure definition: 주요 트리 구조 정의 /* structure of a node in the free tree (free tree안의 노드 구조) */ typedef struct _t_ { WORD t_s; /* size of this element */ WORD t_p; /* parent node */ WORD t_l; /* left child */ WORD t_r; /* right child */ WORD t_n; /* next in link list */ WORD t_d; /* dummy to reserve space for self_pointer */ } TREE; chunk 헤더의 t_s 요소는 malloc 함수를 호출할 때 요청한 크기를 반올림한 값이다. 이 크기는 항상 word 단위로 반올림되기 때문에 t_s 요소의 하위 2비트는 사용되지 않는다. 이 2비트는 일반적으로 항상 0값을 가진다. 0 대신에 다른 값이 온다해도 그 값은 크기와는 무관한 의미를 가진다. 그 값은 flag 요소로써 사용되어 진다. malloc.c 소스로 부터 아래와 같은 사실을 알 수 있다. BIT0: 1은 블록이 사용되고 있을 때, 0은 free일 때 BIT1: 블록이 사용되고 있고, 연속된 메모리상의 이전 블록이 free이면 이 비트는 1이다. 그렇지 않으면 항상 0이다. TREE Access macros: Tree 접근 매크로들 /* usable # of bytes in the block */ #define SIZE(b) (((b)->t_s).w_i) /* free tree pointers */ #define PARENT(b) (((b)->t_p).w_p) #define LEFT(b) (((b)->t_l).w_p) #define RIGHT(b) (((b)->t_r).w_p) /* forward link in lists of small blocks */ #define AFTER(b) (((b)->t_p).w_p) /* forward and backward links for lists in the tree */ #define LINKFOR(b) (((b)->t_n).w_p) #define LINKBAK(b) (((b)->t_p).w_p) 메모리를 할당하는 모든 operation을 위해 정렬(certain alignment)과 최소 크기가 아래와 같이 정의된다. #define WORDSIZE (sizeof(WORD)) #define MINSIZE (sizeof(TREE) - sizeof(WORD)) #define ROUND(s) if (s%WORDSIZE) s += (WORDSIZE-(s%WORDSIZE)) Tree 구조는 할당된 chunk 각각의 핵심적인 요소이다. 일반적으로 오직 t_s와 t_p 요소만이 사용되고 사용자 data는 t_l 부터 저장된다. 노드가 free되면 이것이 바 뀌고, data는 더 효과적으로 free element를 다루기 위해서 재사용된다. chunk는 기울어진 tree(splay tree)안의 element를 나타낸다. 더 많은 chunk가 free될 때, malloc 구현은 그것의 오른쪽 다음에 있는 free chunk를 합치려고 한다. 동시에 dangling free tree stat안에 있을 수 있는 청크는 기껏해야 FREESIZE(기본 32byte) 만큼이다. 그것들은 모두 'flist' 배열안에 저장되어진다. 리스트가 이미 가득차 있 을때 free가 실행된다면 이 리스트안의 오래된 element는 떨어져 나가고 realfree (함수명)로 들어가게 된다. 그리고나서 이 공간은 새로운 freed element가 차지한다. free를 위한 많은 호출이 한줄 안에서 발생할 경우 속도를 증가시키고 defragmention (조각화,단편화)을 피하기 위해서 이다. 실질적으로 합병하는 과정은 realfree에 의 해 실행된다. 이것은 chunk를 root pointer로 시작하는 central tree에 넣는다. 트리 는 그것들의 요소의 크기에 의해서 정렬되어지고 self-balanceing(자체 균형잡기)한 다. 이것을 소위 splay tree(기울어진 트리)라 한다. 이 트리안에서 element들은 검 색속도를 높이기 위해 특별한 방법으로 순환한다.(예로 google.com은 더 많은 정보를 위한 splay tree이다.) 이것은 더 이상 여기에서 중요하지 않다. 그러나 free chunk 의 두가지 단계가 있음을 기억해야 한다. 하나는 'flist' 배열 안에서이고, 다른 하 나는 'Root'로 시작하는 트리의 free-element 안에서 이다. 메모리의 작은 chunk를 할당하기 위한 특별한 처리 루틴이 몇개 있는데, 이것은 우연 하게도 40byte보다 작은 크기일 때 일어난다. 이것들은 여기서 고려하지 않는다. 그 러나, 기본적인 아이디어는 tree안에 그것을 두는 것이 아니라 extra list안에 둔다 는 것이다. malloc 기반의 버퍼오버플로우를 익스플로잇 시키기 위해 IRIX와 솔라리스에서 사용 하는 보다나은 방법이 여기 있다. 한 chunk가 realfree 될때 이웃 chunk들이 이미 realfree된 tree 안에 있는 지 검사 된다. 만일 이런 경우라면, 논리적으로 두 chunk를 합병시키고 크기가 변했으므로 tree안의 위치를 다시 정렬해야 한다. 이 합병처리는 node들로 구성된 tree안에서의 pointer 병경을 수반한다. 이 노드들은 chunk header 자체로 표현된다. 다른 tree element를 위한 포인터가 그 곳(node)에 저장된다. 우리가 그것들을 덮어 쓸수 있다면, chunk를 합칠 때 그 포인터(pointer) 를 수정할 수 있을 것이다. 여기 malloc.c 안에서 어떻게 되는지 보여준다. (이것은 흥미로운 부분을 위해 수정되었다.) static void realfree(void *old) { TREE *tp, *sp, *np; size_t ts, size; /* pointer to the block */ tp = BLOCK(old); ts = SIZE(tp); if (!ISBIT0(ts)) return; CLRBITS01(SIZE(tp)); /* 다음 블록과 합쳐 질 수 있는 지 체크 */ np = NEXT(tp); if (!ISBIT0(SIZE(np))) { if (np != Bottom) t_delete(np); SIZE(tp) += SIZE(np) + WORDSIZE; } NEXT가 현재 chunk의 바로 다음에 있는 청크라는 것을 기억한다. 그래서, 메모리 구 조는 아래와 같다. tp old np | | | [chunk A header] [chunk A data] | [chunk B of free ....] | chunk boundary 일반적인 경우 응용프로그램은 어떤 영역을 할당받게 되고 malloc 으로 부터 (old) 포인터를 얻게 된다. 그리고, chunk data의 오버플로우가 허용된다. 우리는 오버플로 우에 의해 chunk 경계를 넘고 뒤쪽의 data에 기록할 수 있게 된다. 이 뒤쪽의 data는 free되었거나 사용중인 chunk 이다. np = NEXT(tp); 우리는 오직 old 뒤쪽의 data를 오버플로우 시킬수 있다. 현재 chunk 헤더 자체는 수 정할 수 없다. 그러므로, 어떤 방법으로도 np 포인터에 영향을 줄 수 없다. 그것(np 포인터)은 항상 chunk의 경계를 가리킨다. 이제 우리의 chunk와 그것 뒤의 chunk를 합치는 게 가능한 지 검사하게 된다. 기억해야 할 것은 우리가 현재 chunk의 오른쪽 chunk를 조절할 수 있다는 것이다. if (!ISBIT0(SIZE(np))) { if (np != Bottom) t_delete(np); SIZE(tp) += SIZE(np) + WORDSIZE; } 만일 chunk가 free고 free element tree안에 있으면 BIT0은 0이다. 또한 그것이 free 이고 마지막 chunk(특별한 Bottom chunk)가 아니라면 그 chunk는 tree에서 지워진다. 그런 다음 두개의 chunk들의 크기가 더해지고 나중에 realfree 함수에 의해 전체 리 사이즈된 chunk가 tree안으로 다시 들어가게 된다. 중요한 조건이 있는데 그것은 오버플로우된 chunk가 malloc 영역 안의 마지막 chunk 가 아니어야 한다는 것이다. 1. 오버플로우된 chunk는 마지막 chunk가 아니어야 한다. 여기서 t_delete 함수가 어떻게 작용하는 지 보자. static void t_delete(TREE *op) { TREE *tp, *sp, *gp; /* if this is a non-tree node */ if (ISNOTREE(op)) { tp = LINKBAK(op); if ((sp = LINKFOR(op)) != NULL) LINKBAK(sp) = tp; LINKFOR(tp) = sp; return; } 다른 경우도 있다, 이것이 exploit 하기가 쉬운 것 중의 하나이므로 이것을 설명하 도록 한다. 나는 벌써 이것에 싫증을 느꼈기 때문에, 여기에 그 중 하나를 설명만 할 것이다. 다른 것들과 매우 비슷하다. (malloc.c를 봐라.) ISNOTREE는 TREE구조체의 't_l' 요소와 -1을 비교한다. -1은 non-tree 노드를 위한 특별한 표시로(이중연결 리스트를 위해 사용) exploit 시키기에 특별한 문제는 없다. 어쨌든, 이것은 exploit을 위한 첫번째 조건이다. 2. fake->t_l = -1; 이제 FOR(t_n)과 BAK(t_p) 사이에 연결끊기가 끝났고, 다음과 같이 다시 쓰여질 수 있다. t1 = fake->t_p t2 = fake->t_n t2->t_p = t1 t1->t_n = t2 이것은 pseudo-raw-assignment에 의해 동시에 쓰여진다. [t_n + (1 * sizeof(WORD))] = t_p [t_p + (4 * sizeof(WORD))] = t_n 이 방법으로 우리는 특정 주소에 임의의 주소값을 기록할 수 있다. 이 방법을 사용 하기로 하자. t_p = retloc - 4 * sizeof(WORD) t_n = retaddr 이 방법으로 retloc은 retaddr로 덮어쓰여지고, *(retaddr+8)은 retloc으로 덮어 쓰 여 질 것이다. 만약 retaddr에 실행코드가 있다면, 8~11바이트 만큼의 작은 점프가 발생할 것이다. 또한, 더 나은 경우, 주소들이 바뀌게 될 것이다. 마지막으로 우리는 버퍼를 다음과 같이 덮어쓴다. | | chunk boundary Where: t_s = some small size with lower two bits zeroed out t_p = retloc - 4 * sizeof(WORD) t_l = -1 t_r = junk t_n = retaddr t_d = junk 비록 모든 데이타가 32bit 포인터로 저장될 지라도, 각 구조체의 원스들은 8byte를 사용한다는 사실을 주목하라. 이것은 각각의 원소에 대해서 최소한 ALIGN 바이트가 사용되도록 정해져 있는 WORD union 때문이다. ALIGN은 기본적으로 8byte로 정의되어 있다. 그래서 chunk 경계 뒤의 실제 오버플로우는 다음과 같이 보일 것이다. ff ff ff f0 41 41 41 41 ef ff fc e0 41 41 41 41 | ....AAAA....AAAA ff ff ff ff 41 41 41 41 41 41 41 41 41 41 41 41 | ....AAAAAAAAAAAA ef ff fc a8 41 41 41 41 41 41 41 41 41 41 41 41 | ....AAAAAAAAAAAA 모든 'A' 문자들은 임의로 설정할 수 있다. 't_s'는 NUL 바이트를 회피하기 위해서 작은 음수로 대체되었다. 만약 당신이 NUL 바이트를 사용하기 원한다면, 아주 적은 것을 써라. 그렇지 않으면 realfree함수는 나중에 깨질것이다. 버퍼는 다음과 같이 덮어 써진다. [0xeffffce0 + 32] = 0xeffffca8 [0xeffffca8 + 8] = 0xeffffce0 좀 더 자세하게 알고 싶으면 mxp.c 예제코드를 보라. IRIX나 솔라리스에서 malloc 기반의 버퍼오버플로우 익스플로잇을 하려면 아래의 요 약내용을 참고하라. 1. 오버플로우를 하고자 하는 것 뒤에 가짜 chunk를 생성한다. 2. 가짜 chunk는 realfree로 보내지고, 당신이 오버플로우 시킨 chunk와 합 병된다. 3. 가짜 chunk가 realfree로 보내지기 위해서는 malloc함수가 다시 호출되거 나, free()함수가 여러 번 실행되어야 한다. 4. 오버플로우된 청크는 마지막 chunk가 아니어야 한다. (the one before Bottom) 5. Jump-ahead를 shellcode/nop-space 앞에 덧붙여 잘못된 unlink-overwrite 주소를 실행하지 않도록 한다. 6. 이러한 t_splay 루틴을 사용한 공격 또한 가능하다. 그러므로 당신이 여 기 설명한 공격을 사용할 수 없다면(0xff바이트를 쓸 수 없을때), luke 소스를 사용하라. System V의 malloc 관리방법엔 여러가지 악용방법이 존재하며, 이 방법들은 GNU 구현 에서보다 더 유용하다. 이것은 malloc 자체를 이해하기 어렵게 만드는 동적 트리구조 체를 사용하기 때문이다. 만약 당신이 여기까지 읽었다면, 당신 고유의 malloc 기반 버퍼오버플로우 방법을 찾을 수 있으리라고 확신한다. GNU C Library 구현 ================== GNU C 라이브러리는 어플리케이션이 요구한 메모리 조각에 대한 정보를 보관하고 있 는 데, 이것을 chunk라 부른다. 그것은 다음과 같다.(malloc.c에서 응용되었음) +---------------------------------------------------+ chunk-> | prev_size | +---------------------------------------------------+ | size | +---------------------------------------------------+ mem -> | data | : ... : +---------------------------------------------------+ nextchunk -> | prev_size ... | : : mem은 pointer이다. malloc()의 리턴값이다. 만약 당신이 아래와 같이 program한다면 unsigned char *mem = malloc(16); mem은 그림의 포인터이고, (mem - 8)은 'chunk' 포인터이다. 'prev_size'는 특별한 기능을 가지고 있다. 만일 현재 chunk 앞의 chunk가 사용되지 않는다면(이미 free되었다면), prev_size는 그 이전 chunk의 크기를 저장하고 있다. 그렇지 않은 경우(chunk가 사용중이면)에는 prev_size는 이것의 'data'의 부분으로 사용되어 4바이트를 저장한다. 'size'는 특별한 의미를 지닌다. 예상한대로 그것은 메모리의 현재 블록(data 섹션)의 크기를 저장한다. malloc()를 호출하면, 당신이 malloc()에 넘겨준 크기에 4 byte와 다음 더블 워드 경계의 크기 만큼이 더 추가된다. 그래서 malloc(7)은 malloc(16)이 되고 malloc(20)은 malloc (32)가 된다. malloc(0)은 malloc(8)이 될 것이다. 이와 같이 동작하는 이유는 나중 에 설명한다. 이와 같이 덧붙여진 4byte중 하위 3비트는 항상 0이고, chunk의 실제 길이에는 아무 영향을 미치지 않는다. 다른 용도로 사용될 뿐이다. 이들은 chunk의 특별한 속성을 지정하기 위해 사용된다. 가장 하위비트는 PREV_INUSE라고 하며 이전의 chunk가 사 용중인지 아닌지를 표시한다. 이것(PREV_INUSE)은 다음 chunk가 사용중이면 1이 설 정된다. 두번째 비트는 메모리 영역이 mmap되어 있으면 설정된다. 이런 경우는 특별 한 경우로 우리는 신경쓰지 않는다. 세번째 비트는 사용되지 않는다. 현재의 청크가 사용중인지 아닌지를 시험하기 위해서, 우리는 다음 청크의 size값에 있는 PREV_INUSE비트를 검사해 봐야 한다. 우리가 free(mem)을 사용하여 청크를 free()하면, 몇몇 검사를 한 후 메모리가 풀린 다.(release) 만약 그 메모리의 이웃 블럭이 free 되었다면(이 역시 PREV_INUSE 프래 그를 검사하여 확인) 그들은 재사용 가능한 블록의 수는 줄이고, 크기는 늘리기 위해 합병된다. 만약 합병이 불가능하면 그 다음 청크는 PREV_INUSE비트가 클리어 되어 표 시되고, 청크의 1 bit를 변환한다. +----------------------------------+ chunk -> | prev_size | +----------------------------------+ | size | +----------------------------------+ mem -> | fd | +----------------------------------+ | bk | +----------------------------------+ | (old memory, can be zero bytes) | : : nextchunk -> | prev_size ... | : : 보다시피 메모리에 두개의 새로운 값이 있다. 그 곳은 예전에 우리가 data를 저장해 두던 곳이다.('mem' 포인터가 지정하는 곳) 이 두개의 값은 'fd'와 'bk'라고 하며 chunk의 이전과 이후를 가리키는 포인터들이다. 이들은 합병되지 않은 free memory 의 이중링크드리스트를 가리킨다. free가 실행될 때 마다, 이 리스트가 검사되고, 통 합되지 않은 블록들이 합쳐진다. 전체 메모리는 어떤 임의의 메모리를 free 시킬 때 마다 매번 하나로 합치는 과정을 반복한다. malloc의 크기는 이 두 포인터를 위해서 최소한 8바이트이어야 한다. 만일 'bk'포인 터 뒤 메모리에 예전 자료가 남아 있으면 그 메모리는 다음 malloc이 호출될 때까지 사용되지 않고 남아 있게 된다. 이 관리방법에서 재미있는 것은 내부의 전체정보가 in-band에 저장된다는 것이다. -- a clear channeling 문제(문자열 자체가 포멧스트링 명령이 되는 것이나, 분리가 능한 전화선의 제어채널, 메모리 스택내에 리턴 어드레스가 저장되는 것등의 문제) 우리가 이 내부 관리 정보를 덮어 쓸수 있으므로, 만약 malloc으로 할당된 영역을 덮 어 쓴다면, 덮어 쓴 이후 이것이 어떻게 처리되는 지 살펴 보아야 한다. 정상적인 프 로그램에선 모든 malloc된 영역은 다시 free되는데, 우리는 malloc.c 파일 안에 있는 chunk_free() 함수를 살펴보자. static void chunk_free(arena *ar_ptr, mchunkptr p) { size_t hd = p->size; /* its head field */ size_t sz; /* its size */ int idx; /* its bin index */ mchunkptr next; /* next contiguous chunk */ size_t nextsz; /* its size */ size_t prevsz; /* size of previous contiguous chunk */ mchunkptr bck; /* misc temp for linking */ mchunkptr fwd; /* misc temp for linking */ int islr; /* track whether merging with last_remainder */ check_inuse_chunk(ar_ptr, p); sz = hd & ~PREV_INUSE; next = chunk_at_offset(p, sz); nextsz = chunksize(next); malloc은 청크를 'arenas'라고 불리는 특별한 구조체를 이용하여 관리한다. Arenas는 이제 현재청크가 'top'청크의 경계로 직접 free 될 수 있는지 검사한다. 'top'청크는 'arenas'에서 언제나 메모리청크의 가장 위에 있는 것으로, 사용가능한 메모리의 경 계이다. 전체 if 블록은 malloc 영역 안에 있는 전형적인 버퍼오버플로우에 대해 무 관하다. if (next == top(ar_ptr)) /* merge with top */ { sz += nextsz; if (!(hd & PREV_INUSE)) /* consolidate backward */ { prevsz = p->prev_size; p = chunk_at_offset(p, -(long)prevsz); sz += prevsz; unlink(p, bck, fwd); } set_head(p, sz | PREV_INUSE); top(ar_ptr) = p; if ((unsigned long)(sz) >= (unsigned long)trim_threshold) main_trim(top_pad); return; } 이제 이전 청크가 사용중인지 아닌지를 검사하기 위해 현재청크의 'size'를 검사한다 (PREV_INUSE 플래그를 검사하는 방법으로). 만약 다음과 같은 경우라면 두 청크는 합 쳐지게 된다. islr = 0; if (!(hd & PREV_INUSE)) /* consolidate backward */ { prevsz = p->prev_size; p = chunk_at_offset(p, -(long)prevsz); sz += prevsz; if (p->fd == last_remainder(ar_ptr)) /* keep as last_remainder */ islr = 1; else unlink(p, bck, fwd); } 현재 청크의 다음 청크가 free되었는지 검사하는 방법도 이와 비슷하다.(두 청크 다 음 청크의 PREV_INUSE 플래그를 검사한다.) 다음과 같은 경우에도 두 청크는 하나로 합쳐지게 된다. if (!(inuse_bit_at_offset(next, nextsz))) /* consolidate forward */ { sz += nextsz; if (!islr && next->fd == last_remainder(ar_ptr)) /* re-insert last_remainder */ { islr = 1; link_last_remainder(ar_ptr, p); } else unlink(next, bck, fwd); next = chunk_at_offset(p, sz); } else set_head(next, nextsz); /* clear inuse bit */ set_head(p, sz | PREV_INUSE); next->prev_size = sz; if (!islr) frontlink(ar_ptr, p, sz, idx, bck, fwd); } 솔라디자이너가 우리에게 보여준 것 처럼, unlink매크로를 이용해서 메모리 임의의 영역을 덮어 쓰는 것이 가능하며 여기에 그 방법을 설명한다. 일반적인 버퍼오버플로우 현상이 발생하는 경우는 다음과 같다. mem = malloc (24); gets (mem); ... free (mem); 이 방법으로 malloc된 청크는 다음과 같다. [ prev_size ] [ size P] [ 24 bytes ... ] (next chunk from now) [ prev_size ] [ size P] [ fd ] [ bk ] or [ data ... ] 당신이 보는 바와 같이 다음 청크는 우리가 오버플로우 시키는 청크의 뒷 경계에 있 다. 우리는 뒤에 있는 또다른 청크의 헤더를 덮어 쓸수 있다. 즉, 현재 청크의 데이 타 영역뒤의 어떤 것도 덮어 쓸수 있다는 것이다. chunk_free 함수의 뒷부분에 가면 이러한 코드를 볼수 있다. if (!(inuse_bit_at_offset(next, nextsz))) /* consolidate forward */ { sz += nextsz; if (!islr && next->fd == last_remainder(ar_ptr)) /* re-insert last_remainder */ { islr = 1; link_last_remainder(ar_ptr, p); } else unlink(next, bck, fwd); next = chunk_at_offset(p, sz); } inuse_bit_at_offset은 malloc.c의 시작 부분에 매크로로 정의 되어 있다. #define inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE) 우리가 'next' chunk의 헤더를 제어할 수 있으므로 if 블록 전체를 마음대로 할 수 있다. 우리의 청크가 가장 최상위 chunk의 경계에 있을 때를 제외하고는 if문 안의 내용은 흥미롭지 않다. 그래서 if문 밖의 명령들을 실행하기 위해 조건을 조절할 수 있다면 우리는 unlink를 부를 수 있을 것이다. 이것 또한 매크로로 정의되어 있다. #define unlink(P, BK, FD) \ { \ BK = P->bk; \ FD = P->fd; \ FD->bk = BK; \ BK->fd = FD; \ } unlink는 bck와 fwd의 두개의 임시포인터 변수와 free chunk를 위한 포인터를 가지고 호출된다. unlink는 next chunk 헤더에 아래와 같이 실행한다. *(next->fd + 12) = next->bk *(next->bk + 8) = next->fd 그것들은 서로 교환되지는 않지만 fd와 bk 포인터는 다른 chunk를 가리킨다. 이 두 chunk들이 연결되고 테이블로 부터 현재 청크를 없앤다. 그러므로, malloc을 기반으로 하는 버퍼오버플로우를 익스플로잇 시키기 위해서 우리 는 다음 청크에 가짜 헤더를 만들어야 하고, 우리의 청크가 free 되기를 기다려야 한 다. [buffer .... ] | [ prev_size ] [ size ] [ fd ] [ bk ] '|'은 청크의 경계이다. 우리가 지정한 prev_size와 size는 중요하지 않은 값이다. 그러나 이것들이 잘 작동 하려면 다음과 같은 조건이 만족되어야 한다. a) 'size'의 최하위 비트는 0 이어야 한다. b) 'prev_size' 와 'size' 는 읽혀질 포인터로 안전하게 더해져야 한다. 그래서 몇 천 밖에 안되는 아주 작은 값을 사용하거나 Null byte를 피하기 위해 0xfffffffc 같은 큰 값을 사용한다. c) 당신은 (chunk_boundary + size + 4) 의 최하위 비트가 zero로 맞추어 지게 보 장해야 한다. (0xfffffffc는 잘 작동할 것이다.) 'fd' 와 'bk' 의 값은 아래의 방법으로 정해진다.(솔라 디자이너가 Netscape 익스플 로잇에서 사용한 것처럼) fd = retloc - 12 bk = retaddr 그러나 (retaddr + 8)에 어떤 값이 쓰여질 수 있고 그 주소에 있던 내용이 파괴될 수 있다. 당신은 retaddr에 간단히 '\xeb\x0c'를 넣음으로써 이것을 회피할 수 있다. 이 것은 내용을 파괴시키는 것을 넘어서 12바이트를 점프할 것이다. <6> <4 bogus> | \xff\xff\xff\xfc \xff\xff\xff\xfc 여기서 '|'는 청크 경계이다.(우리가 오버플로우하는 그 지점) 두 음수는 free()의 몇 가지 검사를 통과하고 NUL 바이트를 피한다. 그런 다음 우리는 (retloc - 12) 포 인터에 'jmp-ahead' 코드가 저장되어 있는 return address를 저장한다. '|' 앞쪽 버 퍼에 들어가는 값들은 처음 12바이트를 제외하고 다른 x86 익스플로잇과 같다. 처음 12바이트를 이와 같이 하는 이유는 unlink 매크로에 의해 우리가 원하지 않는 다른 값이 쓰여지기 때문에 그 부분을 점프하여 정상적인 쉘코드를 실행하기 위해서이다. Off-by-one / Off-by-five ------------------------ 임의의 포인터를 오버라이트 할 수 있는데, 어떤 경우 5바이트만 오버라이트할 수 있 을 수도 있고, 특별한 경우 단지 1바이트만 가능할 수도 있다. 5바이트를 오버라이트 할 때 메모리 레이아웃은 아래와 같다. [chunk a] [chunk b] 여기서 청크 a는 우리의 제어하에 있고 오버플로우가 가능한 청크이다. 청크 b는 오 버플로우가 일어날 때 이미 할당되어 있었다고 가정하자. 청크 b의 처음 다섯 바이트 를 덮어 쓰면, 청크 헤더의 'prev_size' 항목의 4바이트와 'size'항목의 최하위 1 바 이트를 우리의 뜻대로 바꿀 수 있다. 이제 청크 b가 free() 될 때, 'size'의 PREV_INUSE 플래그가 클리어된 상태이기 때문에 이전 청크와 합병하려 할 것이다. 만일 우리가 'prev_size'에 작은 값을 준다면, 청크 a의 크기보다 더 작은 가짜 청크 구조를 새로 만들 수 있다. [chunk a ... fakechunk ...] [chunk b] | p 청크 b의 'prev_size'는 거짓 청크를 가리킨다. 이러한 설정을 이용하여 익스플로잇 이 가능한 코드는 이미 전에 논하였다. if (!(hd & PREV_INUSE)) /* consolidate backward */ { prevsz = p->prev_size; p = chunk_at_offset(p, -(long)prevsz); sz += prevsz; if (p->fd == last_remainder(ar_ptr)) /* keep as last_remainder */ islr = 1; else unlink(p, bck, fwd); } 'hd'는 청크 b의 size 항목이다. 우리가 그것(hd)을 오버라이트 할때, 하위 2비트를 클리어한다. 그래서 PREV_INUSE가 클리어 되어 if 조건이 만족하게 된다.(NUL이 사실 상 이러한 일을 한다.) if문 안의 몇몇 명령으로 원래 청크 b를 가리켰던 포인터 'p'는 우리의 가짜 청크에 재배치된다. 그리고 나서, unlink 매크로가 호출되고, 우리는 여느 때처럼 포인터를 덮어 쓸수 있다. 이 기사의 앞부분에서는 기준 청크의 다음 청크와의 합병을 이용하는 방법에 대해 설 명하였고, 지금은 이전 청크와의 합병을 이용하는 방법을 설명하였다. 이것이 혼란스러운가? malloc 오버플로우를 익스플로잇 할때, 그 세부적인 것에 대해 걱정하지 말아라. 그 것은 당신이 더 넓은 범위의 malloc 기능을 이해하면 더 명확해 질 것이다. malloc 구현의 개요와 설명을 더 잘 알고 싶다면, GNU C Library 참고 매뉴얼을 자세 히 보아라. 이것은 또한 non-malloc과 관련된 것을 이해하기 위해서도 좋은 문서이다 =============================================================================== 이하 생략... =============================================================================== Thanks ====== I would like to thank all proofreaders and correctors. For some really needed corrections I thank MaXX, who wrote the more detailed article about GNU C Library malloc in this issue of Phrack, kudos to him ! :) References ========== [1] Solar Designer, http://www.openwall.com/advisories/OW-002-netscape-jpeg.txt [2] DD Sleator, RE Tarjan, "Self-Adjusting Binary Trees", 1985, http://www.acm.org/pubs/citations/journals/jacm/1985-32-3/p652-sleator/ http://www.math.tau.ac.il/~haimk/adv-ds-2000/sleator-tarjan-splay.pdf [3] The GNU C Library http://www.gnu.org/manual/glibc-2.2.3/html_node/libc_toc.html [4] Solaris 8 Foundation Source Program http://www.sun.com/software/solaris/source/ |=[ EOF ]=---------------------------------------------------------------=|