Contents

[redpwnCTF2021] pickled-onions, 2k writeups

pickled-onions

Given file

Analyzing the source code:

We are given a .py file, so the first thing I did was throwing that in a text editor.

1
__import__('pickle').loads(b'(I128\nI4\nI99\nI112\nI105\nI99... #truncated )

The source contains just one line of code and it has something to do with pickle, which is a built-in python model used for “serializing and de-serializing a Python object structure”. In other words, it converts a python object to a byte stream, and vice versa.

After googling for a while, I learned that the byte stream is a sequence of opcodes for the Virtual pickle machine. This is a stack-based VM that will interpret those opcodes and build python objects for us. I also learned that, with the right opcodes, Virtual pickle machine can execute Python code!

If we try running the provided .py script, it will ask us for the correct input. But we don’t see that anywhere in the source code. At this point, I was pretty sure that this program uses the pickle VM to execute something, so the main logic is (probably) in that long byte stream.

Analyzing the pickle opcodes:

Pickle opcodes are one character and followed by their arguments, arguments are terminated with a newline. You can take a look at the list of all opcodes and what each of them does here

Luckily, we don’t have to parse those opcodes by hand. Python has a built-in module - pickletools - to help us do just that. Using pickletools.dis(), we will have the disassembled version of our opcode.

1
pickletools.dis(b'(I128\nI4\nI99\nI112\nI105\nI99... #truncated )
 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
/*...*/
544203: I        INT        73
544207: I        INT        54
544211: I        INT        52
544215: I        INT        10
544219: I        INT        133
544224: I        INT        82
544228: I        INT        133
544233: I        INT        82
544237: I        INT        147
544242: I        INT        133
544247: I        INT        82
544251: I        INT        133
544256: I        INT        82
544260: I        INT        133
544265: I        INT        82
544269: I        INT        46
544273: t        TUPLE      (MARK at 0)
544274: p    PUT        69420
544281: c    GLOBAL     'pickle loads'
544295: c    GLOBAL     'builtins bytes'
544311: g    GET        69420
544318: \x85 TUPLE1
544319: R    REDUCE
544320: \x85 TUPLE1
544321: R    REDUCE
544322: .    STOP

The program pushes a bunch of numbers into the stack and once again calls pickle.loads(), which means those numbers are pickle opcodes. With the help of pickletools.genops(), I was able to extract the numbers and disassemble them.

1
2
3
4
5
6
tup = []
for op in pickletools.genops(code):
    (opcode, arg, pos) = op    
    if (opcode.name == "INT"):
        tup.append(arg)
pickletools.dis(bytes(tup))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
   13: (    MARK
   14: \x8c     SHORT_BINUNICODE 'pickledhorseradish'
   34: C        SHORT_BINBYTES b'\x80\x04cpickle\nio\ncio\npickledmacadamia.__add__\ncio\npickledbarberry\n\x85R.'
  101: \x8c     SHORT_BINUNICODE 'pickledcoconut'
  117: C        SHORT_BINBYTES b'\x80\x04cpickle\nio\ncio\npickledmacadamia.__sub__\ncio\npickledbarberry\n\x85R.'

/*...*/

119476: \x8c     SHORT_BINUNICODE 'pickledpupunha'
119492: \x8c     SHORT_BINUNICODE 'Nope!'
119499: \x8c     SHORT_BINUNICODE 'Correct!'
119509: \x86     TUPLE2
119510: \x8c     SHORT_BINUNICODE 'pickledximenia'
119526: c        GLOBAL     'builtins input'
119542: \x8c     SHORT_BINUNICODE 'What is the flag? '
119562: \x85     TUPLE1
119563: R        REDUCE
119564: \x8c     SHORT_BINUNICODE 'pickledgarlic'
119579: \x8c     SHORT_BINUNICODE 'pickledcorneliancherry'
119603: \x8c     SHORT_BINUNICODE 'pickledboysenberry'
119623: \x86     TUPLE2
119624: d        DICT       (MARK at 13)

Now it builds a dict, with entry pickledximenia contains our input, pickledpupunha contains the tuple ("Nope!", "Correct!"), pickledgarlic contains the tuple ('pickledcorneliancherry', 'pickledboysenberry') and the rest are just opcodes. After that, we can see there are many function calls.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
119722: b    BUILD
119723: c    GLOBAL     'builtins print'
119739: c    GLOBAL     'io pickledpupunha.__getitem__'
119770: c    GLOBAL     'pickle loads'
119784: \x8c SHORT_BINUNICODE 'io'
119788: c    GLOBAL     'io pickledgarlic.__getitem__'
119818: c    GLOBAL     'io pickledburmesegrape.__eq__'
119849: I    INT        64
119853: \x85 TUPLE1
119854: R    REDUCE
119855: \x85 TUPLE1
119856: R    REDUCE
119857: \x93 STACK_GLOBAL
119858: \x85 TUPLE1
119859: R    REDUCE
119860: \x85 TUPLE1
119861: R    REDUCE
119862: \x85 TUPLE1
119863: R    REDUCE
119864: .    STOP

The above code can be roughly rewritten as:

1
print(pickledpupunha[pickledgarlic[len(ourInput) == 64]()])

We want the program to print Correct!, so the input has to be 64-char long. On top of that, pickledgarlic[1](), a.k.a pickledboysenberry() has to return 1.

Repeating the process above, we can get the disassembled code for pickledboysenberry. This function constructs even more pickle opcodes, which will be used to check our input. Again, using pickletools.genops() and pickletools.dis(), we can extract those opcodes. Those functions are fairly simple. We have pickledblackapple to check if each character is in the range from 32 to 127. The rest of the functions follow the same pattern: push every char of input to stack, pop them out one by one and save the chars it needs, then finally perform an arithmetic check. For example, this is a checking function: pickledgalendar

 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
/*...*/
  253: 0    POP
  254: 0    POP
  255: 0    POP
  256: 0    POP
  257: 0    POP
  258: p    PUT        0
  261: 0    POP
  262: c    GLOBAL     'pickle io'
  273: (    MARK
  274: \x8c     SHORT_BINUNICODE 'pickledmacadamia'
  292: g        GET        0
  295: \x8c     SHORT_BINUNICODE 'pickledbarberry'
  312: g        GET        1
  315: \x8c     SHORT_BINUNICODE 'pickledgarlic'
  330: \x8c     SHORT_BINUNICODE 'pickledcorneliancherry'
  354: \x8c     SHORT_BINUNICODE 'pickledmonstera'
  371: \x86     TUPLE2
  372: d        DICT       (MARK at 273)
  373: b    BUILD
  374: c    GLOBAL     'pickle loads'
  388: \x8c SHORT_BINUNICODE 'io'
  392: c    GLOBAL     'io pickledgarlic.__getitem__'
  422: c    GLOBAL     'pickle io'
  433: (    MARK
  434: \x8c     SHORT_BINUNICODE 'pickledmacadamia'
  452: c        GLOBAL     'pickle loads'
  466: c        GLOBAL     'io pickledlychee'
  484: \x85     TUPLE1
  485: R        REDUCE
  486: \x8c     SHORT_BINUNICODE 'pickledbarberry'
  503: I        INT        57
  507: d        DICT       (MARK at 433)
  508: b    BUILD
  509: 0    POP
  510: c    GLOBAL     'pickle loads'
  524: c    GLOBAL     'io pickledcrabapple'
  545: \x85 TUPLE1
  546: R    REDUCE
  547: \x85 TUPLE1
  548: R    REDUCE
  549: \x93 STACK_GLOBAL
  550: \x85 TUPLE1
  551: R    REDUCE
  552: .    STOP

Finding the flag:

Since every functions follow a fixed pattern, we can easily iterate over their opcodes and generate constraints for our z3 solver.

 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
s = Solver()
flag = [BitVec("x%d"%(i), 8) for i in range(64)]

def calVars(v1, v2, calculation):
    val = v1
    if calculation == "pickledhorseradish":
        val += v2
    elif calculation == "pickledcoconut":
        val -= v2
    elif calculation == "pickledlychee":
        val ^= v2
    return val
    
def addConstraint(s, v1, v2, compare):
    if compare == "pickledcrabapple":
        s.add(v1 == v2)
    elif compare == "pickledportabella":
        s.add(v1 != v2)
    elif compare == "pickledquince":
        s.add(v1 <= v2)
    elif compare == "pickledeasternmayhawthorn":
        s.add(v1 >= v2)


calculateFuncs = ["pickledhorseradish", "pickledcoconut", "pickledlychee"]
compareFuncs = ["pickledcrabapple", "pickledportabella", "pickledquince", "pickledeasternmayhawthorn"]

for func in checkFuncs:
    iter = pickletools.genops(checkFuncs[func])
    varId = 63
    vars = {}
    calculation = None
    compare = None
    for op in iter:
        (opcode, arg, pos) = op
        if (opcode.name == "POP"):
            varId -= 1
        if (opcode.name == "PUT"):
            vars[arg] = flag[varId]
        if (arg == "pickledmacadamia"):
            (nextOp, nextArg, nextPos) = next(iter)
            if (nextOp.name == "GET"):
                pickledmacadamia = vars[nextArg]
            elif (nextOp.name == "INT"):
                pickledmacadamia = nextArg
        if (arg == "pickledbarberry"):
            (nextOp, nextArg, nextPos) = next(iter)
            if (nextOp.name == "GET"):
                pickledbarberry = vars[nextArg]
            elif (nextOp.name == "INT"):
                pickledbarberry = nextArg
        if (opcode.name == "GLOBAL" and arg.replace("io ", "") in calculateFuncs):
            calculation = arg.replace("io ", "")
            pickledmacadamia = calVars(pickledmacadamia, pickledbarberry, calculation)
        if (opcode.name == "GLOBAL" and arg.replace("io ", "") in compareFuncs):
            compare = arg.replace("io ", "")
    addConstraint(s, pickledmacadamia, pickledbarberry, compare)

And the flag is flag{n0w_th4t5_4_b1g_p1ckl3_1n_4_p1ckl3_but_1t_n33d3d_s0m3_h3lp}

Full script: solve.py

2k

Given files

Analyzing main function and parsing the opcodes:

We are given a 64bit ELF, so straight to IDA it goes.

The main function first does some basic stuff like: allocate a buffer, read prog.bin, etc… After that, it iterates over each byte of prog.bin and does this:

1
2
    if ( progBin_[i] <= 0x53u )
      __asm { jmp     rax }

IDA can’t decompile this, so we have to read the assembly code. Doing so shows me that this is clearly a switch-case statement, with the jump table at 0x21d0:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
.text:00000000000012E1                 lea     r15, unk_21D0
/..../
.text:0000000000001300                 cmp     byte ptr [rbp+rax+0], 53h ; 'S'
.text:0000000000001305                 lea     r13d, [rdx+1]
.text:0000000000001309                 ja      short loc_1330
.text:000000000000130B                 movzx   eax, byte ptr [rbp+rax+0]
.text:0000000000001310                 movsxd  rax, dword ptr [r15+rax*4]
.text:0000000000001314                 add     rax, r15
.text:0000000000001317                 db      3Eh
.text:0000000000001317                 jmp     rax

My teammate @redandblue found a blog that show us how manually define switch-case statements in IDA. For this challenge, just go to Edit -> Other -> Specify switch idiom, then use the following config:

/posts/redpwn2021/switch.png

Tip
While IDA can’t recognize a switch statement like this, BinaryNinja can do it pretty well. So if you don’t want to configure anything, BinaryNinja is a good choice.

After defining the switch statement, we can easily see that this is a stack-based VM. Here’s a short summary about all of its opcodes:

  • 0x1: Duplicate the topmost value of the stack.
  • 0x2: Pop a value from stack.
  • 0x3: Print the flag if the topmost value on stack is 0.
  • 0x10, 0x11, 0x12, 0x13, 0x14, 0x15: arithmetic operations
  • 0x16, 0x17: comparing operations
  • 0x20, 0x21: input/output operations
  • 0x22: push a specified number to stack
  • 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36: jump statements
  • The program also has an array to be used as “memory” for the VM, and the last 6 opcodes: 0x40, 0x41, 0x50, 0x51, 0x52, 0x53 are operations on this memory.

After knowing the functionality of every opcodes, I wrote a simple disassembler for prog.bin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
with open("prog.bin", "rb") as f:
    opcodes = f.read()
    
opName = {1: "DUP", 2: "POP", 3: "CHECK", 0x10: "ADD", 0x11: "SUB", 0x12: "MUL", 0x13: "DIV", 0x14: "MOD", 0x15: "MUL_MOD", 0x16: "IS_EQ",
    0x17: "CMP_0", 0x20: "INPUT", 0x21: "PRINT", 0x22: "PUT", 0x30: "JMP", 0x31: "JZ", 0x32: "JNZ", 0x33: "JLZ", 0x34: "JGZ", 0x35: "JLEZ",
    0x36: "JGEZ", 0x40: "STACK_TO_ARR", 0x41: "ARR_TO_STACK", 0x50: "INC_ARR_PTR", 0x51: "DEC_ARR_PTR", 0x52: "ADD_ARR_PTR", 0x53: "SUB_ARR_PTR"} 

rip = 0
while rip < len(opcodes):
    op = opcodes[rip]
    
    if (op != 0x22):
        print(str(rip) + ":\t\t" + opName[op])
        rip += 1
    else:
        print(str(rip) + ":\t\t" + opName[op] + "\t\t" + str(struct.unpack("<H", opcodes[rip + 1:rip + 3])[0]))
        rip += 3

Solving using z3:

Thanks to the disassembler, we can now understand what prog.bin is trying to do.

1
2
3
4
5
6
7
0:		PUT		12
3:		JMP
4:		PUT		1
7:		CHECK
8:		PUT		0
11:		CHECK
12:		PUT		115

First, it jumps straight to address 12. But notice that, at address 8, the program pushes 0 to stack then executes the print flag instructions. We know that the program only gives us the flag if the topmost value on the stack is 0, so this must be the address we need to reach. By the same logic, we don’t want to get to address 4.

At address 12, the program prints out the string “sice dice:”, then ask us for 64 bytes of input. It then subtracts each char by 0x2f and puts our input to memory. After that, it performs a series of checks, following the pattern: load input char(s) from memory –> perform arithmetic operations –> compare against a constant –> jump to address 4 if the comparison is wrong.

Since there are over 6000 lines in the disassembled opcode, reading all of them and solving manually is out of the question. Instead, I tried to emulate all the opcodes in python and generate constraints for z3 automatically.

We will supply the input as z3 BitVec, and whenever there is a conditional jump to address 4, we can just skip the jump and add an appropriate constraint to z3 solver.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
flag = [BitVec("x%d"%(i), 16) for i in range(64)]
flagPos = 0

.....

    elif op == 0x20:			#input
        stack.append(flag[flagPos])
        flagPos += 1
        rip += 1
        
.....

    elif op == 0x31:            #jump if zero
        addr = stack.pop()
        token = stack.pop()
        if addr == 4:
            s.add(token != 0)
            rip += 1
        elif token == 0:
            rip = addr
        else:
            rip += 1

Since all the character is subtracted by 0x2f before they are put to the memory, and I don’t want to deal with negative numbers, I added the following constraints to z3.

1
2
for i in flag:
    s.add(And(i >= 48, i <= 127))

The script will generate false inputs if I remove that, so there must still be something wrong with my code. Nevertheless, it still managed to give me one correct input, and that is enough to get the flag: flag{kenken_is_just_z3_064c4}

Full script: solve.py