Allen Chang

Allen Chang

B.S. Georgia Tech Math and CS, '25

CTFing updates, and a writeup

9 minute read

Published:

Hello!

I’ve been meaning to start a blog for a while but never got around to it; this will probably be a place where I just write about personal updates and random things inconsistently.

Recently I’ve been getting back into CTFs with Squid Proxy Lovers. I used to play a lot in high school and occassionally with GreyHat, Georgia Tech’s CTF team, but it’s been a while since I was seriously active, and I wanted to find a more competitive team. One of my cointerns at Trail of Bits this summer invited me to the CTF team that he captains, so I figured it’s a good opportunity to get back into it.

Last week we played in CSAW Qualifiers (2nd) and CyberBayCTF Qualifiers (2nd), both for on-site finals in October. This week we casually played CrewCTF. CrewCTF had a lot of high-quality challenges so I figured I could do a writeup on a challenge I did here.

misc/Bytecode Bonanza

misc/Bytecode Bonanza was a two-part challenge revolving around writing Python bytecode in a limited instruction set. We’re given a set of three challenges which go through this filter function:

def create_function(parameters, prompt):
  bytecode = bytes.fromhex(input(prompt))
  
  if len(bytecode) > 512:
    print("Too long")
    exit()
  
  opcodes = [bytecode[i*2] + bytecode[i*2+1]*256 for i in range((len(bytecode)+1) // 2)]
  
  allowlist = [ 0x0001, 0x0004, 0x0006, 0x000f, 0x0017, 0x0190 ] + [0x0073 + i * 512 for i in range(128)]
  
  if any([op not in allowlist for op in opcodes]):
    print("Illegal opcode")
    exit()
  
  preamble = b"".join([bytes([0x7c, i]) for i in range(parameters)])
  
  code = preamble + bytecode + bytes([0x53, 0])
  
  dummy = dummies[parameters]
  
  dummy.__code__ = dummy.__code__.replace(co_code=code,co_stacksize=1000000000)
  
  return dummy

The goal is to input bytecode as hex, which is injected into a dummy function’s __code__ attribute. We can observe that the main restriction is a 512 length upper bound, and that the bytecodes we can use are in a very limited instruction set in allowlist. After doing some research we can observe the following behaviors:

  • 0x01: POP_TOP, pops the top of stack (TOS)
  • 0x04: DUP_TOP, duplicates the TOS
  • 0x06: ROT_FOUR, rotates TOS down into 4th-to-top position and 2nd-4th members up one position
  • 0x0f: UNARY_INVERT, bitwise inverts TOS as -(x+1)
  • 0x17: BINARY_ADD, pops top 2 elements off stack and pushes their sum
  • 0x190: EXTENDED_ARG, only used with POP_JUMP_IF_TRUE to add 256 to the address jumped to, since we can write 512 bytes of bytecode
  • 0x73, 0x273, …, 0xfe73, POP_JUMP_IF_TRUE, limited to even offsets 0-255 since each opcode is 2 bytes long

We also note that Python bytecode is stack-based, and our arguments are fed in order dummy(a,b,c) -> [a,b,c]. For sake of notation we’ll assume the square arrays shown above grow left to right.

Tooling and Setup

The first thing to do is to make a debugger for testing bytecode. I vibe coded a quick debugger using dis to parse my bytecode:

============================================================
BYTECODE ANALYSIS
============================================================
Hex: 040004000f0017001700040006000600060004000600060006...
Length: 470 bytes

Opcodes (reading as 16-bit little-endian):
  Offset   0: 0x0004 (    4) DUP_TOP
  Offset   2: 0x0004 (    4) DUP_TOP
  Offset   4: 0x000f (   15) UNARY_POSITIVE
  Offset   6: 0x0017 (   23) BINARY_ADD
  Offset   8: 0x0017 (   23) BINARY_ADD
  Offset  10: 0x0004 (    4) DUP_TOP
  Offset  12: 0x0006 (    6) ROT_FOUR
  Offset  14: 0x0006 (    6) ROT_FOUR
  Offset  16: 0x0006 (    6) ROT_FOUR
  Offset  18: 0x0004 (    4) DUP_TOP
  ... (225 more opcodes)

Full function bytecode (with preamble and return):
  7c 00 7c 01 7c 02 04 00 04 00 0f 00 17 00 17 00 04 00 06 00 06 00 06 00 04 ... 04 00 73 26 01 00 01 00 53 00

============================================================
DISASSEMBLY (first 20 lines)
============================================================
 12           0 LOAD_FAST                0 (a)
              2 LOAD_FAST                1 (b)
              4 LOAD_FAST                2 (c)
              6 DUP_TOP
              8 DUP_TOP
             10 UNARY_INVERT
             12 BINARY_ADD

Since I intended to be writing raw bytecode, this is pretty useful for debugging typoes.

Making Gadgets

The CTF challenge was split into two parts; the first asks you to implement (1) subtraction, (2) return constant, and (3) multiply, and the second asks you to implement RSA/modular exponentiation.

Here are some miscellaneous observations about the opcode set:

  • Stack movement is very annoying. Only the top element is easily accessed, everything else can only be accessed with ROT_FOUR, which destroys the stack below it (needing to be restored)
  • We can only jump if true (nonzero)

My intuition about this challenge is that we need to very neatly describe a stack invariant and preserve it meticuously. This is very necessary for jumps. To do this, I write a set of well-defined gadgets that have specific functions.

  • 04000f001700040017000f00: Replaces TOS with 1
  • 04000f0017000f00: Replaces TOS with 0 (admittedly very nice solution)
  • 040004000f001700040017000f001700: Add 1 to TOS
  • 0f0017000f0004000f0004000f00170017000f00: Pop off [A,B] from TOS and pushes A-B
  • 040004000f00170017000f00: Negate TOS
  • 04000400060006000600040006000400040006000100010001000600 Duplicate [A,B] from TOS, resulting in [...A,B,A,B]. This is very useful in certain applications, despite the bytecode being long.

Hence, subproblem 1 (subtraction) can be solved with a gadget above.

Return 1337 as Constant

Subproblem 2 (return 1337) is slightly more complicated, but not particularly hard. We observe bin(1337)=10100111001, so we build up the number from MSB to LSG. We can double the TOS by writing 04001700 (duplicate, then add), so it becomes trivial to return any constant. We write:

04000f001700040017000f00 # Replace TOS with 1
04001700 # Double TOS
04001700 # Double TOS
040004000f001700040017000f001700 # Add 1 to TOS
04001700 # etc ...
04001700
04001700
040004000f001700040017000f001700
04001700
040004000f001700040017000f001700
04001700
040004000f001700040017000f001700
040017000400170004001700
040004000f001700040017000f001700

to complete part 2.

Multiplication

This is where things get interesting, since we have to manipulate the instruction pointer to loop now. We can consider many multiplication algorithms, but since the numbers are small, we can naively add integer A to itself B times. Then the pseudocode is as follows:

def mult(a,b):
  sum = a
  while 1:
    b -= 1
    if b = 0:
      return sum
    sum += a

In implementation, the while loop is one jump instruction. Since our jumps can only be if true/nonzero, the if statement can only check whether b is nonzero. If it is nonzero, we wish to jump to sum += a; if it is not, the next instruction should jump to a return statement at the end.

Furthermore, we must consider setting up a stack invariant. After some experimentation I end up with [X, sum, a, b], where X is garbage. X is included since rotating the stack occurs four at a time. Hence, this is the code I came up with:

040004000600060006000400060006000600 # Setup stack invariant
040004000f0017001700 # b -= 1
04007334 # If b is nonzero, skip the following line and jump to (A)
040004000f00170004001700 0f00734e # If it is zero, we return sum and jump to end
0600040006001700040006000600010006000600060004007316 # (A). Add S += a
010006000600010001000100 # Destroy stack

RSA and Modular Exponentiation

This gets very messy, and there’s a couple of more gadgets we need to implement. Exponentiation without modular arithmetic is easy, since it is just the next hyperoperation after multiplication (which we already implemented), so the algorithm would be exactly the same. However, taking a modulo is surprisingly difficult with this instruction set. Consider the classical algorithm; a % b is computed by subtracting b until a < 0 (and you take the least nonnegative value). However, given the only jump statement we have, we have nowhere to derive sign of an integer from.

The solution that we end up with abuses the limited input size. p,q <= 100, so we can simply test equality of all positive integers to see if a number is positive. Thus, we implement a comparator as follows:

040004000f001700040017000f000400170004001700040017000400170004001700040017000400170004001700040017000400170004001700040017000400170004001700040017000400170004001700040017000400170004001700
040004000f0017001700 04000400060006000600040006000400040006000100010001000600
0f0017000f0004000f0004000f00170017000f00 73 b0
04000f001700040017000f00 0400 73 bc
0400 73 b8
0400 73 bc
0400 73 64

We upper bound the integer at \(2^{14}\), hence the long first line. It pushes 1 to the TOS if nonnegative and 0 to the TOS if negative. This is slightly suboptimal but easy to work with as a primitive.

Next, we implement the modulus operation. This takes the comparator and repeatedly subtracts until it is less than 0, then takes the least nonnegative value:

04000400060006000600040006000400040006000100010001000600
0f0017000f0004000f0004000f00170017000f00

04000400060006000600040006000400040006000100010001000600010004001700040017000400170004001700040017000400170004001700
040004000f0017001700 04000400060006000600040006000400040006000100010001000600
0f0017000f0004000f0004000f00170017000f00 73 bc
04000f001700040017000f00 0400 73 c8
0400 73 c4
0400 73 c8
0400 73 70 
73 ce

0100 73 e2
04000400060001000600060006000100 0f00 73 06

Here we also introduce a stack invariant in the first line of the code. I also change the upper bound from \(2^{14}\) to \(128pq\), which introduces a small speedup to the code and saves many bytes from the line that pushes \(2^{14}\).

Then the final payload is as follows:

040004000f0017001700
04000600060006000400060006000600010006000600
040004000f0017001700 
0400 73 3a
0400 9001 73 d8

06000600 040004000600060006000400060004000400060001000100010006000100 # Multiplication
040004000f0017001700 040004000600060006000400060006000100 
040004000f0017001700 040073 8a
0400 73 a6
0600040006001700040006000100 040004000f0017001700 0400 73 78
0600 0600 0600 0100 0100 0100
060006000600
04000400060006000600040006000400040006000100010001000600 

04000400060006000600040006000400040006000100010001000600 # Modulus
0f0017000f0004000f0004000f00170017000f00
04000400060006000600040006000400040006000100010001000600010004001700040017000400170004001700040017000400170004001700

040004000f0017001700 04000400060006000600040006000400040006000100010001000600 # Comparator
0f0017000f0004000f0004000f00170017000f00 9001 73 8e
04000f001700040017000f00 0400 9001 73 a0
0400 9001 73 9a
0400 9001 73 a0
0400 9001 73 3e
9001 73 aa
0100 9001 73 be
04000400060001000600060006000100 0f00 73 d4

04000600060004000600010001000100060006000600
0400  73 26
01000100

and we are done.