Heap Overflow Length Extension for GHOST vulnerability

Heap Overflow Length Extension for GHOST vulnerability

이 글은 CVE-2015-0235, 일명 'ghost' 취약점에 대해서 분석하면서 dl-malloc 자체에 대해서도 같이 분석하게 된 내용을 정리한 것이다. ghost 취약점은 glibc 의 gethostbyname 함수내부적으로 heap overflow 가 발생하는 취약점인데, 이 취약점에서 발생하는 overflow 는 제한된 범위의 제이터로 고작 4바이트(32비트) 또는 8바이트(64비트) 밖에 되지 않기 때문에 일반적으로 exploitable 하기가 매우 어렵다. 

CVE-2015-0235 의 exploitability 는 heap layout 과 malloc 방식에 매우 의존적이기 때문에, ghost 취약점의 파급력을 판단하기 위해서는 malloc 을 상세히 분석하는것이 중요하다.

- Terminology

mallc 포인터 : malloc 을 해서 받은 포인터. 유저가 사용하는 데이터의 시작주소

chunk : malloc 이 관리하는 자료구조. chunk 의 구조는 그림으로 보면 다음과 같음

chunk 포인터 : malloc 에 대한 메타데이터까지 포함하는 청크의 시작주소. prev_size 필드의 시작.

bin : 비슷한 사이즈의 chunk 들의 집합. 연결리스트로(fastbin 의 경우 싱글, 나머지는 이중) 연결되어있음.

wilderness / arena / top chunk : sbrk() 로 OS 로부터 할당받은 사용되지 않은 힙영역. malloc 은 기본적으로 이미 free 된 chunk 들을 뒤지다가 정 없으면 이영역에서 새롭게 chunk 를 할당함.

An allocated chunk looks like this:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            | Size of previous chunk, if allocated                        | |

            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            | Size of chunk, in bytes                                   |M|P|

      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            | User data starts here...                                      .

            .                                                               .

            . (malloc_usable_size() bytes)                                  .

            .                                                               |

nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            |  Size of chunk                                                |

            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

            ...

chunk 속에 있는 각각의 필드들은 chunk 가 할당된 상태냐 free 된 상태냐에 따라 의미가 달라짐.

- Allocation Size of malloc

malloc 으로 할당되는 메모리 사이즈는 8 의 배수로만 할당되는데, 청크사이즈가 8n 이면 정확히 8n 바이트만큼 자기한테 할당된 공간을 쓰지만 8n+1 만큼의 사이즈를 요쳥하는경우 8(n+1) 만큼의 사이즈가 잡히는게 아니라 8n+4 까지는 다음번 청크의 prev_size 부분을 공간으로 활용한다. 왜냐하면 다음청크의 prev_size 는 현재 청크가 free 되기 전까지는 쓰일일이 없기때문에 공간을 절약하기 위함이다. 이때문에 heap overflow 가 일어날때 해당 청크의 size 가 몇인지에 따라 덮어쓰게되는 뒤쪽청크의 레이아웃이 달라진다. 이는 ghost 취약점과 같은 상황에서 매우 중요한 요소다. 64비트의 경우 16n 이다

- Allocation Algorithm of malloc

malloc 이 메모리를 할당하는 알고리즘은 메모리 사이즈에 의존한다. 이는 크게 3가지 사이즈 범위의 기준으로 나위어지는데, 

1. 64바이트 이하의 malloc 요청의 경우 fastbin 에서 먼저 가용한 공간이 있는지 검색한다. fastbin 의 free chunk 들은 비록 free chunk 이지만 inuse 비트가 셋 되어있는 상태를 유지한다. 이는 다른 인접한 chunk 와 merge 되는일이 없도록 하기 위함이다. 만약 가용한 freechunk 가 fastbin 에 없다면 free 된 small chunk 들중에 best fit 등의 알고리즘으로 할당할 chunk 를 찾는다. 만약 small chunk 들도 가용한게 하나도 없다면 wilderness 에서 잘라온다.

2. 64 바이트 이상 malloc 요청의 경우 fastbin 에서 찾지않고 곧바로 small chunk 부터 찾는다. 

3. 512 바이트 전/후 사이즈로 처리가 조금 다른데 자세히 분석하지 않았음.

4. 64비트 malloc 에서는 fastbin 의 기준사이즈가 120 바이트이다

- What happens when you free

1. 64바이트 이하의 청크들은 fastbin 에 들어가는데 inuse 비트를 유지한다. 다만 fd 포인터 위치가 0 으로 채워진다(아마 어떤 인덱스를 의미하는것같다). 그렇다면 free 된 청크인지 아닌지, 그 리스트들을 어떻게 접근하는지는 어떻게 처리되는가? -> 분석안해서 잘모르겠다

2. 64바이트 이상의 청크들은 자신의 사이즈에 따라 자신이 속한 bin 으로 들어간다. 일단 인접한 chunk 의 inuse 비트가 해제되고 청크의 malloc pointer 위치에 fd/bk 포인터가 생성된다. 이 포인터는 이중연결리스트로서 bin 에서의 next chunk, previous chunk 를 가리킨다. 

3. fastbin 에 들어간게 아닌 어떤 chunk 가 free 됬을때 인접한 chunk 랑 merge 할수있는지 판단해서 가능하다면 unlink 한다. 아래를 보면 자명하다. free 할때 인접한 청크가 또 free 되있으면 merge 를 수행하는데, 그렇지 않고 띄엄띄엄 free 시켜보면 free 청크의 fd/bk 포인터들이 계속해서 생기는것을 볼수있다.

chunk before free(0804b070)(40)

[00000000][00000031][41414141][41414141]...[00000039]

chunk after free(0804b070)(40)

[00000000][00000031][00000000][41414141]...[00000039]

chunk before free(0804b0d8)(56)

[00000000][00000041][41414141][41414141]...[00000049]

chunk after free(0804b0d8)(56)

[00000000][00000041][00000000][41414141]...[00000049]

... 여기까지는 fastbin 에 들어간 free chunk 라서 prev_inuse 비트가 유지되고 fd 포인터 위치에 0 이 들어간걸 볼수있다. 그러나 이후부터는 inuse 비트가 해제되고 fd/bk 에 청크 포인터가 들어간다.

chunk before free(0804b160)(72)

[00000000][00000051][41414141][41414141]...[00000059]

chunk after free(0804b160)(72)

[00000000][00000051][b7fc5470][b7fc5470]...[00000058]

chunk before free(0804b208)(88)

[00000000][00000061][41414141][41414141]...[00000069]

chunk after free(0804b208)(88)

[00000000][00000061][0804b160][b7fc5470]...[00000068]

- Exploiting Heap Overflow in dl-malloc (old)

원래 heap overflow 가 발생하면 application 의 heap layout 과 무관하게 왠만해선 write-what-where primitive 를 얻을수 있을 확률이 매우 높았다. 왜냐하면 overflow 된 힙청크가 언젠가는 free 될것이고, 그 경우 overflow 에 의해서 인접한 chunk 가 어떤 상태이든 상관없이 free 된 청크인것처럼 조작시켜놓으면, merge(consolidate) 과정에서 unlink 매크로가 우리가 원하는 포인터에 우리가 원하는 값을 쓰는 상황을 만들어 주기 때문이었다.

그러나 아쉽게도 이것이 GLIBC 버전 2.3.3 이후(매우매우 옜날) 부터 패치되면서 막혀버렸다. unlink 시에 다음과같은 검증루틴이 추가되었기 때문이다.

- unlink 하고자하는 청크의 다음청크의 이전청크가 나 자신인가?

- unlink 하고자하는 청크의 이전청크의 다음청크가 나 자신인가?

C 코드로 딱 두줄이면되는 이 단순한 검증코드가 추가된것때문에 heap overflow 의 파급력이 엄청나게 줄어들었다.

그러면 이제 heap overflow 는 application specific 한 자료구조속의 포인터를 덮는다던지 하는게 아니면 일반적으로 써먹을수있는 시나리오는 전무한것인가? 완전히 그렇지많은 않다. unlink 가 패치되기 전처럼 강력한 익스플로잇 시나리오는 아니지만 일반적으로 exploit 에 도움이 될만한정도의 기법이 남아있긴 한다.

- Heap Overflow Length Extension

힙은 매우 넓고 방대한 공간이라서 application 이 이부분에 어떤 객체들을 어떻게 놓고 쓸지는 전혀 정해져있지 않다. 따라서 힙 오버플로우가 만약 발생했을때, 이것이 exploitable 할 확률이 높으려면 최대한 overflow 할수있는 사이즈의 길이가 길어야한다(그래야 덮을수있는 중요 객체들이 많아질것이므로).

이미 힙 오버플로우 버그가 무제한으로 힙을 덮을수 있는 경우라면 이 기법은 전혀 도움될게 없지만, 만약에 힙 오버플로우 버그가 원래 할당된 힙버퍼에서 조금밖에 더 오버플로우를 못하는 상황, 또는 Controllable 하지 않은 데이터에 의해 오버플로우가 되는 상황이라면 이 기법이 유용할 수 있다. (* 여기서 새로 제시하거나 찾은 기법이 아니고 이미 해커들이 알고있는 것이다)

핵심은 바로 free 청크의 size 를 바꿔서 malloc 이 잘못된 할당을 하도록 유도하는것이다. 예를들어 크기 100짜리 청크뒤에 중요한 데이터가 있는데, 100짜리 청크가 free 된 이후에 넘치는 길이가 짧은 힙 오버플로우 또는 4byte write-what-where 버그에 의해서 이 free chunk 의 사이즈정도만 조작할 수 있다고 가정하자. 그 이후에 공격자가 원하는 사이즈만큼 malloc 을 호출할 수 있는 상황이라면, 공격자는 중요한 데이터를 덮을 수 있다.

예를들어 아래의 상황을 보자

0x00000000 ... [overflow chunk] [free chunk] [ important object ]  ... 0xFFFFFFFF

이 상황에서 overflow chunk 에서의 오버플로우가 important object 까지는 덮을수 없다고 해도, free chunk 의 사이즈부분은 덮을수가 있다. 만약 그렇다면 free chunk 의 size 부분을 매우 큰 값(31337 이라고 가정하자) 으로 조작하고, 이후 공격자가 malloc(31337) 이 호출되게 유도할 수 있다면 malloc 은 31337 사이즈의 chunk 를 free chunk 부분에서 재활용해줄것이다. 만약 free chunk 의 원래 size 가 337 바이트였다고 치면 힙을 조금밖에 overflow 못하던 상황이 31000 바이트를 overflow 할 수 있는 상황으로 발전한다.

이때 사이즈를 덮는 free chunk 가 fastbin chunk 인 경우 chunk 포인터 + fake size 의 부분이 prev_size 가 있는것으로 malloc 이 착각을 하게되기때문에 해당 부분의 LSB 가 1 로 세팅되어있어야한다. 안그러면 모든것이 꼬이고 segfault 가 나게된다. 다음부분에서 game over...

(gdb) x/10i $eip

=> 0xb7e951b1: testb  $0x1,0x4(%edi,%eax,1)

   0xb7e951b6: je     0xb7e950d0

(gdb) set *0x804b87c=1

해당위치를 일단 강제로 set 시키고 넘어가면... (원래는 사이즈를 미세하게 조절해서 이미 힙쓰레기데이터에 남아있는 1 을 가리키도록 하면되지만)

Breakpoint 2, 0xb7e951b1 in ?? () from /lib/i386-linux-gnu/libc.so.6

(gdb) i r

eax            0x48 72

ecx            0xb7fc5440 -1208200128

edx            0x49 73

ebx            0xb7fc4ff4 -1208201228

esp            0xbfffe1f0 0xbfffe1f0

ebp            0x40 0x40

esi            0x804b0d8 134525144

edi            0x804b118 134525208

eip            0xb7e951b1 0xb7e951b1

eflags         0x283 [ CF SF IF ]

cs             0x73 115

ss             0x7b 123

ds             0x7b 123

es             0x7b 123

fs             0x0 0

gs             0x33 51

(gdb) c

Continuing.

malloc(2048) at 0804b078    

prev_size:00000000, size:00000809

[Inferior 1 (process 11024) exited normally]

(gdb) 

원래 40바이트청크가 free 된 공간이었는데 2000 바이트 malloc 으로 재할당되었다.

2000 바이트 malloc 공간을 사용자가 자유롭게 이용할수 있다면, 1960 바이트의 힙오버플로우를 발생시킬 수 있다.

- Difference of malloc / realloc

realloc 의 경우 현재 청크를 제자리에서 확장할수있나 보고 그게 안되면 현재청크를 free 한뒤에 malloc 을 더 큰사이즈로 호출해준다. 여기서 중요한점은 realloc 이 chunk 를 extend 하는 과정에서 인접한 chunk 의 사용유무를 판단하는 방식이 free chunk bin 의 연결리스트를 따라다니면서 찾는것이 아니라 realloc 청크의 size 를 통해서 인접 chunk 의 prev_inuse 비트를 체킹하는 방식이라는 것이 중요하다.

realloc 이 현재청크를 확장할수 있는자 판단하는 방식은 인접한 청크의 사이즈와, 현재청크의 사이즈를 더한것이 realloc 하고자하는 사이즈보다 큰가? 이것을 확인하는 것이다. 그래서 인접한 청크랑 합치면 사이즈 조건이 충족되는경우라면 그다음은 인접한 청크가 free 된것인지 사용중인지를 확인하는데, 이때 중요한것이 free 여부를 판단하는 방식이 전역 bin 포인터에서 포인터를 따라가서 보는게 아니라, 인접한 청크의 사이즈를 기반으로 그 뒤의 인접한 청크의(next next chunk) prev_inuse 비트를 보고 판단한다는 점이다. 

따라서 4바이트정도의 작은 힙오버플로우에 의해서 인접한 청크의 사이즈만 조작할수있는 경우에 해당청크를 realloc 시킬 수 있다면 인접한 청크가 어떤상태이든 무관하게 free 된것처럼 realloc 루틴이 착각하게 만들수있고 결과적으로 Heap Overflow Length Extension 이 가능해진다. 

그러나 아쉽게도 realloc 의 경우에는 현재청크를 인접한 청크랑 병합하면서 인접한 청크를 unlink 를 시키기때문에 인접한 chunk 의 데이터부분...  fd/bk 부분의 데이터를 제어할수 없는 상황이라면 unlink 에러를 피해갈 수 없다. 만약 해당부분이 제어가능하다면 강제로 유효한 fd, bk 를 데이터로서 놓으면 우회할 수 있을것이나, ASLR 이 있다면 해당 청크 자신의 시작주소가 몇인지 알수가 없기때문에 이것도 문제가 될것이다.

- Unresolved Issues

분석하지 못한부분들이 많이 남아있어서 그런것같은데, 일단 디버깅을 한 결과만 가지고볼때 위에서 언급한 Heap Overflow Length Extension 을 수행하고자 할 때, 공격자가 제어할 수 있는 malloc 이전에 제어할수 없는 다른 malloc 이 끼게되는 상황이라면 문제가 발생한다.

즉, 예를들어 100바이트 청크를 free 하고나서, malloc 이 일어나고 (제어할수 없는 malloc), 그 이후에 오버플로우에 의해서 free 청크 사이즈를 3000 정도로 조작했다고 가정하면, 이후 공격자가 제어할수 있는 malloc(3000) 을 요청하게되면 조작된 사이즈를 가진 free 청크주소에 malloc 할당이 되지 않는다.  malloc(3000) 을 사이즈 조작 직후 바로 수행하면 문제없이 되는데, 이에대한 원인은 분석을 안한부분에 있는것 같다.

정적분석을 하진 않았지만 이 현상에 대해서 디버깅을 해보면 다음과 같다.

일단 free 된 청크의 사이즈를 조작한 직후에 fd 주소를 따라가보면 다음과 같다

(gdb) x/30wx 0x7ffff7dd3798

0x7ffff7dd3798: 0x00602d20 0x00000000 0x00000000 0x00000000

0x7ffff7dd37a8: 0xf7dd3798 0x00007fff 0xf7dd3798 0x00007fff

0x7ffff7dd37b8: 0xf7dd37a8 0x00007fff 0xf7dd37a8 0x00007fff

0x7ffff7dd37c8: 0xf7dd37b8 0x00007fff 0xf7dd37b8 0x00007fff

0x7ffff7dd37d8: 0xf7dd37c8 0x00007fff 0xf7dd37c8 0x00007fff

0x7ffff7dd37e8: 0xf7dd37d8 0x00007fff 0xf7dd37d8 0x00007fff

0x7ffff7dd37f8: 0xf7dd37e8 0x00007fff 0xf7dd37e8 0x00007fff

그런데 제어할 수 없는 malloc (제어할수 없음과 동시에 조작된 size 에 맞아떨어지지 않는 malloc) 이 수행된 이후에 free 청크를 보면 fd 주소가 바뀌어있는것을 볼 수 있고, 따라가보면 다음과 같다.

(gdb) x/30wx 0x7ffff7dd3858

0x7ffff7dd3858: 0xf7dd3848 0x00007fff 0xf7dd3848 0x00007fff

0x7ffff7dd3868: 0x00602410 0x00000000 0x00602410 0x00000000

0x7ffff7dd3878: 0xf7dd3868 0x00007fff 0xf7dd3868 0x00007fff

0x7ffff7dd3888: 0xf7dd3878 0x00007fff 0xf7dd3878 0x00007fff

0x7ffff7dd3898: 0xf7dd3888 0x00007fff 0xf7dd3888 0x00007fff

0x7ffff7dd38a8: 0xf7dd3898 0x00007fff 0xf7dd3898 0x00007fff

0x7ffff7dd38b8: 0xf7dd38a8 0x00007fff 0xf7dd38a8 0x00007fff

0x7ffff7dd38c8: 0xf7dd38b8 0x00007fff

원래 free chunk 가 갑자기 다른 bin 으로 이동하는 일은 본적이 없는데, 아무래도 size 를 강제로 바꾼것때문에

그것에 기반해서 해당 size 에 맞는 bin 으로 free chunk 가 이동해버리는것 같다.

이부분은 왜이렇게 되는지 정확한 원인은 분석하지 않았다.

또 다른 의문점은 malloc 본체코드 int_malloc() 에서 보면 size 가 fastbin 에 해당 안하는경우는 fastbin 리스트에서 할당할 chunk 를 안뒤지는데 왜 fastbin 사이즈의 청크를 free 해놓은것도 사이즈를 조작하면 큰사이즈 malloc 시 재할당이 가능한지 모르겠다.  한마디로 사이즈 10 짜리 malloc 버퍼를 free 했다가 사이즈를 3000 으로 덮고 다시 malloc 3000 을 할때.. 일단 3000 이라는 사이즈가 fastbin 에 안속하니까 10짜리 free chunk 의 리스트를 뒤질일이 없을것같은데, 왜 실제로 해보면 prev_inuse 비트만 맞추게되면 가능한지 모르겠다. 분석을 잘못한부분이 있거나 못본부분이 있어서 그런것 같다. 

참고자료 : http://egloos.zum.com/studyfoss/v/5206220