SYSCALL invokes an OS system-call handler at privilege level 0. It does so by loading RIP from the IA32_LSTAR MSR (after saving the address of the instruction following SYSCALL into RCX). (The WRMSR instruction ensures that the IA32_LSTAR MSR always contain a canonical address.) SYSCALL also saves RFLAGS into R11 and then masks RFLAGS using the IA32_FMASK MSR (MSR address C0000084H); specifically, the processor clears in RFLAGS every bit corresponding to a bit that is set in the IA32_FMASK MSR.
valid means whether this data is DELETEd or not. hash is calculated from key in new_hash() and is used for searching the hashtable (htb) for the entry.
hash calculation
The pointers of them are stored in hashtable(structure entry *htb[0x100]). The LSB of hash is used as the key of hashtable. If the hash collides, new entry is put into root of the linked list in htb_link().
Memory Allocation Structure
Most of data is stored in buffer which is allocated via alloca() or calloc(). But key and value are allocated via original allocation system, which uses Garbage Collection.
Memory Pool is described as below structure: structure mpool mp
memory pool
Memory Allocation System and Garbage Collection
Buffer is allocated from this system via alloc().
memory allocation
It first check whether the rest of space is enough for requested size. Here, p->cap means the upper limit size of the memory pool. If there is no space, it calls gc(), or Garbage Collection function.
garbage collection
The default size of memory pool is 0x80. After estimating the size of inuse memory, it adjusts new pool size. In init_mpool(), new pool is allocated via malloc(), then p->base, p->cap, and p->inuse is updated. In migrate() function, all the entries is re-allocated in updated memory pool. Note that all the key are re-allocated, but data is re-allocated only when e->valid is true.
migrate all the entries
The last phase of gc() is to free() the old memory pool.
3: Vulnerabilities
To be honest, I couldn't find any vulns or kinda any clues at first glance....
I guess the author of this challenge has already written author's writeup (I think this trend is typical especially in recent Japanese CTF), but I didn't wanna see it. And I don't know who is the author, though I can guess ptr-yudai disaster-level pro or shift_crops world-end pro is.
(Edit 20201019: my guess-work was correct and the author shift_crops has already written the writeup. See below)
The curious part 1. In db_get() which searches hashtable for the requested entry, the buffer of the entry is checked as bellow.
curious memory check in db_get()
Similar check is performed also in db_reg():
curious memory check in db_reg()
Memory allocation and re-allocation should be performed in alloc() and migrate(). If they are perfect, these check wouldn't be needed. It means that the allocation system can collapse and the entry can be in out-of-memory region.
The curious part 2.Why does this system leave deleted or migrated data unfreed. In migrate(), data which satisfies e->valid&&e->size>0 is reallocated, but is not freed. Therefore, the old data become floating-pointer and can be used to leak some info, I guess.
The curious part 3, which is a totally mistake of mine, but usefull notice. Does this system need to shrink the pool in gc()?
the memory pool can shrink
Yeah, this behavior itself is OK, with no problems. But this small notice led me to exploit.
The curious part 4, why reading and writing data is performed via read() and write()? Why not fgets() or something like it. In CTF context, this often means that you can write arbitrary value regardless of NULL byte of newline(0x1A).
The vuln
Let these three curious parts combined.
Suppose below situation:
suppose
The size of old pool is 0x800, which has a data A in it. Note that this data is at addr of 0x1xx ~ 0x2xx. Data A is DELETEd and valid flag becomes 0. This pointer still remains in hashtable. After that, old pool shrinks to the size of 0x200. Well, the head of data A is in the range of current memory pool, but its body exceeds the range of the memory pool.
What happens if we re-register data with key "A"? ent_lookup() just checks its key and doesn't check valid flag. And after that, db_reg() checks as below:
db_reg()
Okay, it also does NOT check valid flag. In addition, it RE-RAISE valid flag. Next if check would pass because it only checks the head of data(e->data).
The curious parts assembles now. Yes, floating-pointer remains in hashtable after delete. Yes, weird memory check is performed and it is insufficient. Yes, the memory pool can shrink and can be placed on the old memory pool. And yes, OOB read/write is available now...!
4: Linear OOB to leak heapbase
The concept is perfect, but doing it was totally brain-fucking trial-and-error work... tcache was very annoying and inuse + ensure < new_size/4 was very irritating. key is allocated even when its valid flag is 0. And I mistakenly assumpted that new_size is evaluated multiple times in one gc() call, which wasted so much time.
Anyway, below script does well heap feng-shui. (I really hate this word heap feng-shui. It is as good as saying nothing...)
2. Allocate data "A" in 0x800 pool. Then delete it.
3. Shrink to 0x400 and 0x800 pool is freed. It is consolidated with top chunk.
Note that data "A" is deleted but still remains in 0x800 old pool. In other word, data "A" is in top chunk. Now, chunks looks like below:
data A is in old mp(top)
Then, we pad first space of old pool (top chunk) by allocating dummy entries. After some padding, we make pool shrink to the size of 0x200. Note that this pool is allocated from top chunk, or old pool. Heap would look like below:
data A is beyond current pool!!
Yeah! The head of data A is actually in the current pool. However, its body is beyond the pool and exeeds to next chunk! If we allocate entry, it would be allocated right next to the current pool. Therefore, we have now overlapping chunk and OOB write access! We can write arbitrary value into the entry structure.
At this time, valid flag of A is down cuz A is already deleted. But just writing some value into A re-raises it. If we allocate one more entry, we can read its content because A is allocated for huge size. We get heapbase.
5: Non-linear read to leak libcbase
We can overwrite data and key pointer of entry structure using OOB write now. Next, we have to leak libcbase. We have to generate unsortedbin and leak its fd. Generating unsorted is easy. Re-generating 0x800 size pool and freeing it would be enough.
However, don't forget that data and key must point to the addr in the current pool, otherwise the program dies soon.
addr check @ db_get()
Therefore, we have to generate unsorted and re-generate overlap data again...
It was really brain-fucking work again. Finally below script works well.
# generate unsorted
_put("C", 0x3e0, "C"*0x300) # inuse 0x410 # cap #0x800
_del("C")
_put("#", 0x3e0-2, "#"*0x300)
_del("#") # inuse 0x7f0 # cap 0x800
_put("M", 0x20-2, "M"*4)
_del("M") # inuse 0x52 # cap 0x400
_put("N", 0x3a0-2, "N"*0x200) # unsorted is generated
_del("N") # inuse 0x3f2
_put("O", 0x20-2, "O") # cap 0x200, again!
###################################
_put("P", 0x190, "T") # target whose entry is on deleted A
# NOTE: old A should be in base+inuse range
Now, heap looks like below:
Overwrite victim entry's size using OOB of A. By reading A or victim data, we can leak fd of unsortedbin.
6: tcache poisoning to overwrite __free_hook
We have heapbase and libcbase, but don't have AAW. Let's do tcache poisoning. We use tcache 0x410 as a victim.
First, we have to free memory pool of the size 0x400 twice to link to tcache. But current heap is a little bit dirty due to previous work for leak. Unfortunately, entry structure has pointer in it and they are dereferenced in gc() and migrate() function. So they should be valid value, or the program dies. Especially data pointer is not used if its valid flag is 0, but key pointer is always dereferenced regardless of valid flag.
Now, __free_hook is overwriten with system. However, "/bin/sh\x00" should be at the head of the pool. The content of the pool is migrated as below at migrate():
It just lookup hashtable and migrate keys by strcpy. So we have to determine the first non-NIL entry of hashtable and give "/bin/sh\x00" for its key. In my case, it was overwritable via OOB of data A, so not difficult :)
./chall: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=02a44cf279881f5887ca24374b56d586be571c89, not stripped
RELRO: No RELRO
Stack: No canary found
NX: NX disabled
PIE: No PIE (0x400000)
RWX: Has RWX segments
