mintcocs's learning_vm 풀이

TL;DR

1. 문제

올바른 코드를 찾는 VM 크랙미 문제입니다.

2. 초기 분석

Mach-O 64-bit arm64 ObjC 바이너리이고 give me the code 출력 이후 opcode를 하나씩 처리하며 작동합니다.

3. 분석

vm에서 처리되는 코드는 PROGRAM에 저장되어 있고
initWithProgram -> print -> run 순으로 작동합니다.

PROGRAM:

0x40, 0x33, 0x00, 0x80, 0xDB, 0x37, 0x9A, 0x57, 0x72, 0x96, 0x6F, 0x60, 0x32, 0x04, 0xE2, 0x7B, 0x38, 0x10, 0x4E, 0x22, 0x2A, 0x84, 0x6B, 0xBC, 0x4F, 0x4B, 0x00, 0x4E, 0x4F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0x00, 0x1E, 0x00, 0x15, 0x01, 0x00, 0x00, 0x01, 0x01, 0x00, 0x64, 0x02, 0x1E, 0x00, 0x01, 0x61, 0x00, 0x02, 0x64, 0x03, 0x03, 0x00, 0x01, 0x30, 0x00, 0x03, 0x42, 0x60, 0x00, 0x12, 0x01, 0x01, 0x02, 0x15, 0x30, 0x01, 0x02, 0x42, 0x3E, 0x00, 0x65, 0x18, 0x00, 0xFF, 0x65, 0x1B, 0x00, 0xFF

initWithProgram은 프로그램 초기화를 수행하는 함수입니다.

VM은 4개의 레지스터가 존재합니다.

program = PROGRAM
pc = 0
flags = 0
registers = [0,0,0,0]
memory = [...]

run은 program을 처리하는 디스패처입니다.

우선 여기까지 코드를 작성해보겠습니다.

실행 결과:

python solution.py
op 0x40 pc#1
op 0x33 pc#2
op 0x0 pc#3

이제 처리되는 순서대로 하나씩 op를 추가해보겠습니다.

case 0x40u:
        self->_pc = (dword_10000000C)(self, "fetchWord");
        continue;

op 0x40은 pc를 fetchWord로 이동하는 명령어입니다.

if op == 0x40:
   self.pc = self.read_word()

python solution.py
op 0x40 pc#1
op 0x60 pc#52

op 0x60은 입력을 읽고 memory에 저장하는 역할을 수행하고 있습니다.

op 0x60 이랑 updateZeroFlagWithValue도 추가 하겠습니다.

python solution.py
op 0x40 pc#1
op 0x60 pc#52
op 0x1 pc#57

더 진행하기 전에 좀 더 읽기 편하게 고쳤습니다.

python solution.py
run with code = "12345"

[op 0x40 pc#1 zf=0]
        JMP 51

[op 0x60 pc#52 zf=0]
        memory[30] = 49
        memory[31] = 50
        memory[32] = 51
        memory[33] = 52
        memory[34] = 53
        registers[0] = 5

[op 0x1 pc#57 zf=0]

이제 op 0x1을 처리해봅시다.

case 1u:
        v49 = (dword_10000000C)(self, "fetchByte");
        v48 = (dword_10000000C)(self, "fetchByte");
        if ( v49 < 4u )
        {
          self->_registers[v49] = v48;
          (dword_10000000C)(self, "updateZeroFlagWithValue:", self->_registers[v49]);
        }
        continue;

상수 LOAD네요.

run with code = "12345"

[op 0x40 pc#1 zf=0]
        JMP 51

[op 0x60 pc#52 zf=0]
        memory[30] = 49
        memory[31] = 50
        memory[32] = 51
        memory[33] = 52
        memory[34] = 53
        registers[0] = 5

[op 0x1 pc#57 zf=0]
registers[0] = 0

[op 0x1 pc#60 zf=0]
registers[1] = 0

[op 0x64 pc#63 zf=0]

다음은 op 0x64

메모리 LOAD입니다.

elif op == 0x64:
                reg1 = self.read_byte()
                addr = self.read_word()
                reg2 = self.read_byte()

                rB = self.registers[reg2]
                print(f"registers[{reg1}] = memory[{addr + rB}]\t({view(self.memory[addr + rB])})")
                self.registers[reg1] = self.memory[addr + rB]
                self.set_zf(self.registers[reg1])

[op 0x1 pc#57 zf=0]
registers[0] = 0

[op 0x1 pc#60 zf=0]
registers[1] = 0

[op 0x64 pc#63 zf=0]
registers[2] = memory[30]       (49 (0x31) -> 1)

[op 0x61 pc#68 zf=0]

같은 방식으로 하나씩 추가합니다.

[op 0x1 pc#57 zf=0]
        registers[0] = 0
        
[op 0x1 pc#60 zf=0]
        registers[1] = 0

[op 0x64 pc#63 zf=0]
        registers[2] = memory[30]       (49 (0x31) -> 1)

[op 0x61 pc#68 zf=0]
        x = registers[0] ^ registers[2] (0 ^ 49 (0x31) -> 1)
        registers[0] = (x >> 7) | (2 * x)       (98 (0x62) -> b)

[op 0x64 pc#71 zf=0]
        registers[3] = memory[3]        (128 (0x80) -> )

[op 0x30 pc#76 zf=0]
        CMP registers[0], registers[3]  (98 (0x62) -> b, 128 (0x80) -> )

[op 0x42 pc#79 zf=0]
        JNE 96  (-> jumped)

[op 0x65 pc#97 zf=0]
        NO

[op 0xff pc#100 zf=0]

end

pc#97에서 NO가 출력되었습니다.

트레이스를 살펴보면 바로 이전 pc#76에서 r0과 r3을 비교하고 pc#79에서 두 값이 달라 실패 분기로 넘어갔습니다.

코드를 분석해보면:

1. pc#63에서 입력의 첫 글자를 r2에 저장
2. pc#68에서 r0과 r2를 xor하고 rol해서 r0에 저장
3. pc#71에서 memory[3] (128) 을 가져와서 r3에 저장
4. r0 == r3 비교

pc#57에서 r0이 0으로 초기화됐으므로 rol만 되돌리면 첫번째 글자를 알 수 있습니다.

>>> print(chr(128 >> 1))
@

    sol = solution(program)
    sol.run("@2345")

첫글자를 바꾸고 다시 결과를 확인해보겠습니다.

[op 0x64 pc#71 zf=0]
        registers[3] = memory[3]        (128 (0x80) -> )

[op 0x30 pc#76 zf=0]
        CMP registers[0], registers[3]  (128 (0x80) -> , 128 (0x80) -> )

[op 0x42 pc#79 zf=1]
        JNE 96  ()

[op 0x12 pc#82 zf=1]
end

넘어갔네요.

이제 더 진행해보겠습니다.

[op 0x64 pc#63 zf=0]
        registers[2] = memory[30]       (64 (0x40) -> @)

[op 0x61 pc#68 zf=0]
        x = registers[0] ^ registers[2] (0 ^ 64 (0x40) -> @)
        registers[0] = (x >> 7) | (2 * x)       (128 (0x80) -> )

[op 0x64 pc#71 zf=0]
        registers[3] = memory[3]        (128 (0x80) -> )

[op 0x30 pc#76 zf=0]
        CMP registers[0], registers[3]  (128 (0x80) -> , 128 (0x80) -> )

[op 0x42 pc#79 zf=1]
        JNE 96  ()

//////////////////////

[op 0x12 pc#82 zf=1]
        regsiters[1]++
        // r1 = index

[op 0x1 pc#84 zf=0]
        registers[2] = 21

[op 0x30 pc#87 zf=0]
        CMP registers[1], registers[2]  (1, 21 (0x15) -> )
        // index == 21?

[op 0x42 pc#90 zf=0]
        JNE 62  (-> jumped)
        // loop

[op 0x64 pc#63 zf=0]
        registers[2] = memory[31]       (50 (0x32) -> 2)
        // r2 = input[i]

[op 0x61 pc#68 zf=0]
        x = registers[0] ^ registers[2] (128 (0x80) ->  ^ 50 (0x32) -> 2)
        registers[0] = (x >> 7) | (2 * x)       (101 (0x65) -> e)
        // xor = prev ^ input[i]
        // prev = rol(xor)

[op 0x64 pc#71 zf=0]
        registers[3] = memory[4]        (219 (0xdb) -> Û)
        // r3 = enc_flag[i]

[op 0x30 pc#76 zf=0]
        CMP registers[0], registers[3]  (101 (0x65) -> e, 219 (0xdb) -> Û)
       

[op 0x42 pc#79 zf=0]
        JNE 96  (-> jumped)

[op 0x65 pc#97 zf=0]
        NO

[op 0xff pc#100 zf=0]

end

memory[3]부터 21자를 input으로 만든 값과 끝까지 비교해서 검사하는 로직임이 명확해졌습니다.

enc_flag부터 확인해 보겠습니다.

[op 0x42 pc#79 zf=0]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 32 33 34 35 00 00 00 00 00 | @2345.....
        JNE 96  (-> jumped)

[op 0x65 pc#97 zf=0]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 32 33 34 35 00 00 00 00 00 | @2345.....
        NO

80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC

이제 역산 스크립트를 짜봅시다.

def solve(self):
        enc_flag = self.memory[3:23]
        flag = ''
        prev = 0

        for byte in enc_flag:
            x = byte >> 1
            x |= (byte & 1) << 7
            c = chr(x ^ prev)
            prev = byte
            flag = f"{flag}{c}"

        print(f"flag is {flag}")

end
flag is @m@z1n9!_y0u_g07_7h1

slice를 잘못 해서 마지막 글자가 출력안되네요.

[op 0x12 pc#82 zf=1]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y
        regsiters[1]++

[op 0x1 pc#84 zf=0]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y
        registers[2] = 21

[op 0x30 pc#87 zf=0]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y
        CMP registers[1], registers[2]  (21 (0x15) -> , 21 (0x15) -> )

[op 0x42 pc#90 zf=1]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y
        JNE 62  ()

[op 0x65 pc#93 zf=1]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y
        OK

[op 0xff pc#96 zf=1]
[memory: 3..23] 80 DB 37 9A 57 72 96 6F 60 32 04 E2 7B 38 10 4E 22 2A 84 6B BC | ..7.Wr.o`2..{8.N"*.k.
[memory: 30..39] 40 6D 40 7A 31 6E 39 21 5F 79 | @m@z1n9!_y

end

수정하고 플래그를 입력하면 OK가 출력됩니다.

4. 정리

flag is @m@z1n9!_y0u_g07_7h15

트레이스를 출력하며 opcode를 하나씩 구현해 VM의 동작을 분석했습니다.

입력을 XOR한 뒤 ROL하여 내부에 저장된 데이터와 비교하는 구조였고, 이를 역산해 올바른 코드를 복원할 수 있었습니다.

아래는 분석 과정에서 파악한 일부 Opcode 목록입니다.

Opcode	의미
0x40	JMP
0x60	READ_INPUT
0x01	LOAD_CONST
0x64	LOAD_MEMORY
0x61	XOR_ROL
0x30	CMP
0x42	JNE
0x65	PRINT
0x12	INC
0xFF	HALT

전체 스크립트

def view(v):
    if 10 < v if isinstance(v, int) else ord(v) < 250:
        return f"{v} ({hex(v)}) -> {chr(v)}"
    return v

def dump(memory, index, size):
    chunk = memory[index: index+size]
    hex_repr = chunk.hex(' ').upper()
    ascii_repr = ''.join(chr(b) if 32 <= b <= 126 else '.' for b in chunk)
    print(f"[memory: {index}..{index+size-1}] {hex_repr:<29} | {ascii_repr}")

class solution:
    def __init__(self, program):
        self.pc = 0
        self.flags = 0
        self.registers = bytearray(4)
        self.memory = bytearray(256)

        size = len(program)
        self.memory[:size] = program[:size]

    def read_byte(self):
        current = self.memory[self.pc]
        self.pc += 1
        return current

    def read_word(self):
        lo = self.read_byte()
        hi = self.read_byte()
        return (hi<<8) | lo

    def set_zf(self, val):
        if val:
            self.flags &= ~1
        else:
            self.flags |= 1

    def run(self, code: str):
        print(f"run with code = \"{code}\"\n")

        while 1:
            op = self.read_byte()
            print(f"[op {hex(op)} pc#{self.pc} zf={self.flags}]")
            dump(self.memory, 3, 21)
            dump(self.memory, 30,10)

            if op == 0x40:
                n = self.read_word()
                print(f"\tJMP {n}")
                self.pc = n

            elif op == 0x60:
                reg = self.read_byte()
                addr = self.read_word()
                size = self.read_byte()

                length = min(len(code), size)

                for i in range(length):
                    print(f"\tmemory[{addr + i}] = {ord(code[i])}")
                    self.memory[addr + i] = ord(code[i])

                print(f"\tregisters[{reg}] = {length}")
                self.registers[reg] = length
                self.set_zf(length)

            elif op == 0x1:
                reg = self.read_byte()
                val = self.read_byte()

                print(f"\tregisters[{reg}] = {val}")
                self.registers[reg] = val

            elif op == 0x64:
                reg1 = self.read_byte()
                addr = self.read_word()
                reg2 = self.read_byte()

                rB = self.registers[reg2]
                print(f"\tregisters[{reg1}] = memory[{addr + rB}]\t({view(self.memory[addr + rB])})")
                self.registers[reg1] = self.memory[addr + rB]
                self.set_zf(self.registers[reg1])

            elif op == 0x61:
                reg1 = self.read_byte()
                reg2 = self.read_byte()

                x = self.registers[reg1] ^ self.registers[reg2]
                y = ((x >> 7) | (2 * x)) & 0xFF

                print(f"\tx = registers[{reg1}] ^ registers[{reg2}]\t({view(self.registers[reg1])} ^ {view(self.registers[reg2])})")
                print(f"\tregisters[{reg1}] = (x >> 7) | (2 * x)\t({view(y)})")
                self.registers[reg1] = y
                self.set_zf(y)

            elif op == 0x30:
                reg1 = self.read_byte()
                reg2 = self.read_byte()

                print(f"\tCMP registers[{reg1}], registers[{reg2}]\t({view(self.registers[reg1])}, {view(self.registers[reg2])})")
                self.set_zf(self.registers[reg1] - self.registers[reg2])

            elif op == 0x42:
                target = self.read_word()
                print(f"\tJNE {target}\t({'-> jumped' if self.flags & 1 == 0 else ''})")
                if self.flags & 1 == 0:
                    self.pc = target

            elif op == 0x65:
                a = self.read_word()
                s = '\t'
                while self.memory[a]:
                    s += chr(self.memory[a])
                    a += 1
                print(s)

            elif op == 0x12:
                reg = self.read_byte()
                print(f"\tregsiters[{reg}]++")
                self.registers[reg] += 1
                self.set_zf(self.registers[reg])


            elif op == 0xFF:
                print("HALT!")
                break

            elif op == 0x0:
                continue

            else:
                break

            print("")

        print("end")

    def solve(self):
        enc_flag = self.memory[3:24]
        flag = ''
        prev = 0

        for byte in enc_flag:
            x = byte >> 1
            x |= (byte & 1) << 7
            c = chr(x ^ prev)
            prev = byte
            flag = f"{flag}{c}"

        print(f"flag is {flag}")


if __name__ == "__main__":
    program = [0x40, 0x33, 0x00, 0x80, 0xDB, 0x37, 0x9A, 0x57, 0x72, 0x96, 0x6F, 0x60, 0x32, 0x04, 0xE2, 0x7B, 0x38, 0x10, 0x4E, 0x22, 0x2A, 0x84, 0x6B, 0xBC, 0x4F, 0x4B, 0x00, 0x4E, 0x4F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60, 0x00, 0x1E, 0x00, 0x15, 0x01, 0x00, 0x00, 0x01, 0x01, 0x00, 0x64, 0x02, 0x1E, 0x00, 0x01, 0x61, 0x00, 0x02, 0x64, 0x03, 0x03, 0x00, 0x01, 0x30, 0x00, 0x03, 0x42, 0x60, 0x00, 0x12, 0x01, 0x01, 0x02, 0x15, 0x30, 0x01, 0x02, 0x42, 0x3E, 0x00, 0x65, 0x18, 0x00, 0xFF, 0x65, 0x1B, 0x00, 0xFF]
    sol = solution(program)
    sol.run("@m@z1n9!_y0u_g07_7h15")
    sol.solve()