# BabyStack

Đây là một file PE 64 bit, khi mình mở ra và sau khi nhìn quanh một hồi mình nhận thấy chương trình được viết bằng C++, và vẫn còn các symbol của class được để lại:


Những bạn reverse python bytecode đủ nhiều sẽ biết rất rõ về Stack VM. Stack VM là một dạng VM được thiết kế để thao tác các toán tử trên một ngăn xếp (stack) bằng việc đẩy vào (push), lấy ra (pop) và thao tác các toán tử trên stack. Sơ đồ sau đây để minh họa việc thao tác toán tử cộng trong mô hình stack VM:

  PUSH 12345                  PUSH 67890                    ADD                        POP

|             |            |             |            |             |            |             |
+             +            +      |      +            +             +            +             +
|             |            |      |      |            |             |            |             |
+      |      +            +      V      +            +             +            +             +
|      |      |            |             |            |             |            |             |
+      V      +            +-------------+            +             +            +             +
|             |            |    67890    |            |             |            |             |
+-------------+            +-------------+            +-------------+            +             +
|    12345    |            |    12345    |            |    80235    |            |             |
+-------------+            +-------------+            +-------------+            +-------------+

Phép toán cộng sẽ được thực hiện bằng cách đẩy hai giá trị cần cộng vào, thực hiện phép cộng trên hai giá trị đầu tiên của stack và pop kết quả đó ra, và các toán tử khác hầu như đều thực hiện theo các bước tương tự như phép cộng.

File thực thi của challenge này sẽ thực hiện 3 bước chính:
- Khởi tạo các đoạn bytecode cho VM:


Ngoài ra sau khi nhập xong input, chương trình sẽ chèn các kí tự vừa nhập vào các bytecode trên:


- Đánh giá các opcode: trong bước này, chương trình sẽ lần lượt tìm các opcode, đánh giá xem đó là opcode nào để có thể trích xuất các thông tin phù hợp cho từng opcode đó:


Ví dụ trong hình trên, chương trình sẽ kiểm xem opcode có phải là 6 hay không (ở đây `rom[iter + 1]` sẽ là các opcode). Nếu phải thì chương trình sẽ trích xuất thêm 2 phần tử `rom[iter + 2]` và `rom[iter + 3]`, tạo một giá trị `WORD` từ 2 thông số này. Và từ đây cũng có thể dễ nhận thấy rằng riêng `opcode 6` này có kích thước là 4 bytes, các opcode còn lại chỉ có kích thước 2 bytes.

Sau khi có đầy đủ thông tin, chương trình sẽ thực thi các opcode vừa tìm được.

- Thực thi opcode:


Ở bước này, chương trình sẽ đưa các thông tin vừa giải mã được từ bước trên, đưa vào cho `VM` để thực thi phần còn lại của chương trình. Chúng ta có thể thấy có tổng cộng 8 opcodes.

Trong lúc giải, mình đã viết một đoạn script nhỏ bằng python với mục đích để disassemble đoạn VM trên:

rom = bytes.fromhex('0006000101060c0d010600080105010622380106ff00010801020106313001010106694e01000007000001060c0d01062d410102010600080105010622380106552201010106ff00010801020106333201010106326a0100000700000106493001060008010501063e5e0106ff00010801020106353401010106450a01000007000001063b2001060008010501066b2d0106ff000108010201063736010101065b7801000007000001062b79010600080105010670410106ff00010801020106393801010106374501000007000001067879010600080105010634410106ff00010801020106626101010106550a01000007000001066a3601060008010501062d010106ff00010801020106646301010106581e0100000700000106751b01060008010501063b170106ff000108010201066665010101060f190100000700000106777c010600080105010645300106ff00010801020106686701010106760301000007000001060f3701060008010401063b23010600ff0108010201066a69010101064a12010000070000')

i = 0

stack = []

while i < len(rom):
    step = 0
    word = -1
    byte = -1
    id = hex(i)[2:].ljust(6, ' ')
    print(id, end='')

    if rom[i + 1] == 6:
        step = 4
        word = rom[i + 3] + (rom[i + 2] << 8)
        byte = rom[i]
    else:
        step = 2
        byte = rom[i]

    match rom[i + 1]:
        case 0:
            print(f'EQUAL')
        case 1:
            print(f'XOR')
        case 2:
            print(f'ADD')
        case 3:
            print(f'SUBTRACT')
        case 4:
            print(f'SHL')
        case 5:
            print(f'SHR')
        case 6:
            print(f'PUSH {hex(word)}')
        case 7:
            print(f'POP')
        case 8:
            print(f'AND')

        case _:
            print(f'Invalid opcode {rom[i + 1]}')
            break

    i += step

Kết quả sẽ trông như sau:

0     PUSH 0x1
4     PUSH 0xc0d
8     PUSH 0x8
c     SHR
e     PUSH 0x2238
12    PUSH 0xff00
16    AND
18    ADD
1a    PUSH 0x3130
1e    XOR
20    PUSH 0x694e
24    EQUAL
26    POP
28    EQUAL
2a    PUSH 0xc0d
2e    PUSH 0x2d41
32    ADD
...

Trong đoạn VM trên, input mình nhập vào là `0123456789abcdefghij`, vì 2 kí tự đầu của input là `01` tương ứng trong mã hex chính là 0x30 và 0x31, nên ở dòng `1a`, lệnh `PUSH 0x3130` thực chất push input của mình vào stack.

Tới đây chúng ta chỉ việc reverse ngôn ngữ `Stack VM` này để tìm ra flag cuối cùng. Mình sẽ tập trung ở đoạn code sau:

4     PUSH 0xc0d
8     PUSH 0x8
c     SHR
e     PUSH 0x2238
12    PUSH 0xff00
16    AND
18    ADD
1a    PUSH 0x3130
1e    XOR
20    PUSH 0x694e
24    EQUAL
26    POP
28    EQUAL

Đầu tiên chương trình sẽ push 2 giá trị `0xc0d`, `0x8` và thực hiện phép `shift right`, kết quả trên stack của phép tính `0xc0d >> 0x8` sẽ là `0xc`. Tương tự từ dòng `e` đến dòng `16`, chương trình sẽ thực hiện phép toán `0x2238 & 0xff00` với kết quả là `0x2200`, như vậy trên stack chỉ còn 2 giá trị chính là `0x2200` và `0xc`. Tiếp theo chương trình sẽ thực hiện phép cộng và giá trị còn lại trên stack sẽ là `0x220c`. Sau đó chương trình sẽ đẩy 2 kí tự đầu tiên của input trên và xor với kết quả vừa tìm được, nghĩa là `0x3130 ^ 0x220c`. Sau cùng chương trình sẽ lấy kết quả vừa rồi và so sánh với lại giá trị vừa được push vào `0x694e`. Nếu giống nhau đồng nghĩa với việc 2 kí tự đầu tiên của input chính là 2 kí tự đầu của flag. Để kiểm chứng mình đã viết 1 đoạn script nhỏ để tính ra hai kí tự trên:


và các giá trị còn lại của flag được kiêm tra bằng cách trên nên ta chỉ việc lặp lại các bước vừa được đề cập để tìm ra được flag cuối cùng của challenge này.