Unsorted Bin Attack

Reading time: 10 minutes

기본 정보

자세한 내용은 unsorted bin이 무엇인지 이 페이지를 확인하세요:

Bins & Memory Allocations

Unsorted 리스트는 청크의 bk 주소에 unsorted_chunks (av)의 주소를 쓸 수 있습니다. 따라서 공격자가 unsorted bin 안의 청크에서 bk 포인터의 주소를 수정할 수 있다면, 그는 그 주소를 임의의 주소에 쓸 수 있게 되어 Glibc 주소를 leak 하거나 일부 방어를 우회하는 데 도움이 될 수 있습니다.

요약하자면, 이 공격은 임의의 주소에 큰 숫자 하나를 설정할 수 있게 합니다. 이 큰 숫자는 힙 주소나 Glibc 주소일 수 있습니다. 전통적인 목표는 더 큰 사이즈의 fast bin을 만들기 위해 global_max_fast 였습니다(즉 unsorted bin attack에서 fast bin attack으로 전환할 수 있게 해줌).

• Modern note (glibc ≥ 2.39): global_max_fast became an 8‑bit global. Blindly writing a pointer there via an unsorted-bin write will clobber adjacent libc data and will not reliably raise the fastbin limit anymore. Prefer other targets or other primitives when running against glibc 2.39+. See "Modern constraints" below and consider combining with other techniques like a large bin attack or a fast bin attack once you have a stable primitive.

guyinatuxedo의 코드는 이를 매우 잘 설명합니다. 다만 malloc들을 Tcache에 빠지지 않도록 충분히 큰 메모리로 바꾸면 앞서 언급한 오류인 malloc(): unsorted double linked list corrupted 가 발생하는 것을 볼 수 있습니다.

실제 쓰기가 일어나는 방식

• Unsorted-bin 쓰기는 free 시에, 해제된 청크가 unsorted 리스트의 헤드에 삽입될 때 발생합니다.
• 삽입 동안, allocator는 bck = unsorted_chunks(av); fwd = bck->fd; victim->bk = bck; victim->fd = fwd; fwd->bk = victim; bck->fd = victim; 를 수행합니다.
• 만약 free(victim)을 호출하기 전에 victim->bk를 (mchunkptr)(TARGET - 0x10)으로 설정할 수 있다면, 마지막 문장이 쓰기를 수행합니다: *(TARGET) = victim.
• 이후 allocator가 unsorted bin을 처리할 때, 정합성 검사로 언링크하기 전에 bck->fd == victim과 victim->fd == unsorted_chunks(av) 같은 것들을 확인합니다. 삽입 시 이미 bck->fd(우리의 TARGET)에 victim을 썼기 때문에, 이 쓰기가 성공했다면 이러한 검사는 만족될 수 있습니다.

현대적 제약 (glibc ≥ 2.33)

현재 glibc에서 unsorted‑bin 쓰기를 신뢰성 있게 사용하려면:

• Tcache 간섭: tcache에 해당하는 사이즈의 경우 free는 tcache로 분기되어 unsorted bin을 건드리지 않습니다. 따라서
  • 요청을 MAX_TCACHE_SIZE보다 크게 하거나(기본적으로 64‑bit에서 ≥ 0x410), 또는
  • 해당 tcache bin을 채워서(7개 항목) 추가 free가 글로벌 bin에 도달하도록 하거나, 또는
  • 환경을 제어할 수 있다면 tcache를 비활성화(예: GLIBC_TUNABLES glibc.malloc.tcache_count=0)합니다.
• Unsorted 리스트의 정합성 검사: 다음 allocator 경로에서 unsorted bin을 검사할 때 glibc는(단순화) 다음을 확인합니다:
  • bck->fd == victim 및 victim->fd == unsorted_chunks(av); 그렇지 않으면 malloc(): unsorted double linked list corrupted로 abort합니다.
• 이는 타겟 주소가 두 번의 쓰기를 견뎌야 함을 의미합니다: 먼저 free 시에 *(TARGET) = victim; 나중에 청크가 제거될 때 *(TARGET) = unsorted_chunks(av)(allocator가 bck->fd를 다시 bin 헤드로 덮어씀). 단순히 큰 비영(非零) 값을 강제하는 것이 유용한 타겟을 선택하세요.
• 현대 익스플로잇에서의 전형적인 안정적 타겟
  • "큰" 값을 플래그/한계로 취급하는 애플리케이션 또는 전역 상태.
  • 간접 프리미티브(예: 이후의 [fast bin attack](Fast Bin Attack)을 위해 설정하거나 후속 write‑what‑where로 피벗하기 위한 준비).
  • 새로운 glibc에서 __malloc_hook/__free_hook는 2.34에서 제거되었습니다 — 이들을 목표로 삼지 마십시오. glibc ≥ 2.39에서는 global_max_fast 역시 피하십시오(다음 노트 참조).
• global_max_fast에 관하여 최근 glibc에서는
  • glibc 2.39+에서는 global_max_fast가 8‑bit 전역이 되었습니다. 전통적인 방식대로 힙 포인터를 여기에 쓰는 트릭은 더 이상 깔끔하게 동작하지 않으며 인접한 allocator 상태를 손상시킬 가능성이 높습니다. 다른 전략을 선택하세요.

최소 익스플로잇 레시피 (modern glibc)

목표: 크래시 없이 unsorted‑bin 삽입 프리미티브를 사용해 힙 포인터 하나를 임의 주소에 단일 임의 쓰기로 달성합니다.

• Layout/grooming
  • tcache를 우회할 만큼 큰 사이즈로 A, B, C 할당(예: 0x5000). C는 top chunk와의 통합(consolidation)을 방지합니다.
• 손상(Corruption)
  • A에서 B의 청크 헤더로 오버플로우하여 B->bk = (mchunkptr)(TARGET - 0x10)을 설정합니다.
• 트리거(Trigger)
  • free(B). 삽입 시 allocator가 bck->fd = B를 실행하므로 결과적으로 *(TARGET) = B가 됩니다.
• 이후(Continuation)
  • 계속 할당을 진행하고 프로그램이 unsorted bin을 사용한다면 allocator가 나중에 *(TARGET) = unsorted_chunks(av)로 덮어쓸 것임을 예상하세요. 두 값 모두 일반적으로 큰 값이며, 단지 "큰" 것을 검사하는 타겟에서는 이것만으로도 사이즈/한계 의미를 바꿀 수 있습니다.

Pseudocode skeleton:

// 64-bit glibc 2.35–2.38 style layout (tcache bypass via large sizes)
void *A = malloc(0x5000);
void *B = malloc(0x5000);
void *C = malloc(0x5000); // guard

// overflow from A into B’s metadata (prev_size/size/.../bk). You must control B->bk.
*(size_t *)((char*)B - 0x8) = (size_t)(TARGET - 0x10); // write fake bk

free(B); // triggers *(TARGET) = B (unsorted-bin insertion write)

Unsorted Bin Infoleak Attack

사실 이것은 매우 기본적인 개념입니다. unsorted bin의 청크들은 포인터를 갖고 있습니다. unsorted bin의 첫 번째 청크는 실제로 **fd**와 bk 링크가 **main arena (Glibc)**의 일부를 가리키고 있습니다.
따라서, unsorted bin 안에 청크를 넣고 이를 읽을 수 있다면 (use after free), 또는 적어도 하나의 포인터를 덮어쓰지 않고 다시 할당하여 읽을 수 있다면, Glibc info leak을 얻을 수 있습니다.

유사한 attack used in this writeup에서는 4개 청크 구조(A, B, C, D — D는 top chunk와의 consolidation을 방지하기 위함)를 악용했습니다. B에서의 null byte overflow를 이용해 C가 B가 사용되지 않은 것으로 표시하게 했습니다. 또한 B의 prev_size 데이터를 수정해 크기가 B의 크기 대신 A+B가 되도록 했습니다. 그 다음 C를 해제하고 A+B로 consolidate(합쳐졌습니다)했지만 B는 여전히 사용 중이었습니다. 크기 A의 새 청크를 할당한 뒤, libc에서 leaked 된 주소들을 B에 써서 거기서 유출시켰습니다.

참조 및 기타 예제

• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/unsorted_bin_attack/#hitcon-training-lab14-magic-heap
• 목표는 전역 변수를 4869보다 큰 값으로 덮어써 flag를 얻는 것이며, PIE는 활성화되어 있지 않습니다.
• 임의 크기의 청크를 생성할 수 있고 원하는 크기의 heap overflow가 존재합니다.
• 공격은 세 개의 청크를 생성하는 것으로 시작합니다: overflow를 악용할 chunk0, 오버플로우될 chunk1, 그리고 이전 것들이 top chunk와 consolidate되는 것을 방지할 chunk2.
• 그다음 chunk1을 free하고 chunk0을 오버플로우시켜 chunk1의 bk 포인터가 가리키게 합니다: bk = magic - 0x10
• 그 후 chunk3을 chunk1과 같은 크기로 할당하면 unsorted bin attack이 발생하고 전역 변수의 값이 변경되어 flag를 얻을 수 있게 됩니다.
• https://guyinatuxedo.github.io/31-unsortedbin_attack/0ctf16_zerostorage/index.html
• merge 함수는 전달된 두 인덱스가 동일하면 해당 영역에 realloc을 수행한 뒤 free하지만, 사용 가능한 해제된 영역에 대한 포인터를 반환하므로 취약합니다.
• 따라서, 2개의 청크가 생성됩니다: 자신과 병합될 chunk0과 top chunk와의 consolidating을 막기 위한 chunk1. 그런 다음 merge 함수가 chunk0으로 두 번 호출되어 use after free가 발생합니다.
• 그후 view 함수가 인덱스 2(사용 후 해제된 청크의 인덱스)로 호출되어 libc address를 leak합니다.
• 바이너리는 **global_max_fast**보다 큰 크기만 malloc하도록 보호되어 있어 fastbin이 사용되지 않으므로, 전역 변수 global_max_fast를 덮어쓰기 위해 unsorted bin attack이 사용됩니다.
• 그다음 edit 함수를 인덱스 2(사용 후 해제 포인터)로 호출해 bk 포인터를 p64(global_max_fast-0x10)로 덮어쓸 수 있습니다. 그러면 새 청크를 만들 때 이전에 조작된 free 주소(0x20)가 사용되어 unsorted bin attack을 trigger하고 global_max_fast를 매우 큰 값으로 덮어써서 이제 fast bin에 청크를 생성할 수 있게 됩니다.
• 이제 fast bin attack이 수행됩니다:
• 우선 __free_hook 위치에서 fast 크기 200의 청크로 작업할 수 있음이 발견됩니다:

• gef➤  p &__free_hook
  

$1 = (void (**)(void *, const void *)) 0x7ff1e9e607a8 <__free_hook> gef➤ x/60gx 0x7ff1e9e607a8 - 0x59 0x7ff1e9e6074f: 0x0000000000000000 0x0000000000000200 0x7ff1e9e6075f: 0x0000000000000000 0x0000000000000000 0x7ff1e9e6076f <list_all_lock+15>: 0x0000000000000000 0x0000000000000000 0x7ff1e9e6077f <_IO_stdfile_2_lock+15>: 0x0000000000000000 0x0000000000000000

• 이 위치에 크기 0x200의 fast 청크를 얻을 수 있다면, 실행될 함수 포인터를 덮어쓸 수 있습니다.
• 이를 위해 크기 0xfc의 새 청크를 생성하고 해당 포인터로 merged 함수를 두 번 호출하면, fast bin에 크기 0xfc*2 = 0x1f8인 해제된 청크에 대한 포인터를 얻을 수 있습니다.
• 그 다음 이 청크에서 edit 함수를 호출해 이 fast bin의 fd 주소를 이전의 **__free_hook**을 가리키도록 수정합니다.
• 그 후 fast bin에서 이전의 쓸모없는 청크를 꺼내기 위해 크기 0x1f8의 청크를 하나 생성하고, 또 다른 크기 0x1f8의 청크를 생성하면 fast bin의 청크가 __free_hook 위치로 할당되어 이를 system 함수의 주소로 덮어씁니다.
• 마지막으로 문자열 /bin/sh\x00를 담은 청크를 delete 함수로 free하면, **__free_hook**가 호출되어 /bin/sh\x00를 인자로 system이 실행됩니다.
• CTF https://guyinatuxedo.github.io/33-custom_misc_heap/csaw19_traveller/index.html
• 1B overflow를 악용해 청크를 unsorted bin에서 consolidate하여 libc infoleak을 얻고, 그 후 fast bin attack을 수행해 malloc hook을 one gadget 주소로 덮어쓰는 또 다른 예제입니다
• Robot Factory. BlackHat MEA CTF 2022
• 0x100보다 큰 크기의 청크만 할당할 수 있습니다.
• Unsorted Bin attack으로 global_max_fast를 덮어씁니다 (ASLR 때문에 1/16 확률로 동작합니다 — 수정해야 하는 비트 수와 관련).
• Fast Bin attack으로 전역 청크 배열을 수정합니다. 이렇게 하면 임의의 읽기/쓰기 primitive를 얻어 GOT을 수정하고 어떤 함수를 system으로 포인팅하도록 설정할 수 있습니다.

참조

• Glibc malloc unsorted-bin integrity checks (example in 2.33 source): https://elixir.bootlin.com/glibc/glibc-2.33/source/malloc/malloc.c
• global_max_fast and related definitions in modern glibc (2.39): https://elixir.bootlin.com/glibc/glibc-2.39/source/malloc/malloc.c