# MIPS

#### Writeup by hgarrereyn

**Reverse Engineering***140 points*- Description: The modern renaissance man knows of many things, ranging from cyber security, to architecture. Can you prove that you're more than just a computer whiz? mips. Enter the flag as a hexadecimal number, prefixed by 0x

# Overview

This program accepts a single 4-byte integer as an input and prints either `Not quite! Keep trying.`

or `Good job! Submit your input value as the flag.`

.

There is exactly one integer that works.

# Solution

To solve this, I first had to read up on MIPS (I actually printed out some pages from wikepedia so I could reference the opcodes).

One new thing for me was the concept of a "branch delay slot". Basically, this is an extra instruction that comes after a jump and is executed even if the jump succeeds. For example, look at this line in the assembly code:

```
b $L3
addiu $3,$3,-13
```

The `addiu`

instruction will execute before the branch instruction.

My approach was to work at the code from two sides:

- Figure out what conditions have to be met at the end in order to print the success message
- Figure out how the input was broken down and stored

Then as I went, I took notes next to the assembly code and tried to simplify the conditional expressions.

Early on, I figured out that the integer input was broken down into 4 individual bytes that were operated on independently for a significant portion of the program.

One thing I noticed happening was shift and add - which is a way to multiply two numbers. Take for example the following python code:

```
byte = 34
a = (byte << 3) + (byte << 4) + (byte << 6)
```

This kind of thing occured quite a bit in the MIPS assembly. Now, in order to simplify it, remember that lshift is simply multiply by 2. So that expression becomes:

```
a = (byte * 2**3) + (byte * 2**4) + (byte * 2**6)
```

or

```
a = byte * 88
```

I used this technique of simplifying down many lines of assembly in order to come up with the following two conditions that had to be met to have the right flag:

```
(16,777,215)(b0) + (-12,517,375)(b1) + (b3) - 1922105344 + 18176 == 0
b2 == (b3 * 2) + 3
```

where `b0`

is the most significant byte of the input and `b3`

is the least.

Now, we need integer solutions to this equation so I wrote a simple python force to check possibilites (note: it checks 2^16 solutions which is significantly reduced from the 2^32 possible solution space)

```
# By Harrison Green <hgarrereyn>
def a(b0,b1,b3):
return (16777215 * b0) + (-12517375 * b1) + b3 - 1922105344
for i in range(0,256):
for j in range(0,256):
v = a(i,j,0)
if abs(v) < 18176 + 256:
b0 = i
b1 = j
b3 = -v
b2 = (b3 * 2) + 3
val = (b0 << 24) + (b1 << 16) + (b2 << 8) + b3
print('Bytes: ' + str([b0,b1,b2,b3]))
print('Decimal: ' + str(val))
print('Hex: ' + hex(val))
```

Running this script gives:

```
$ python mipsSolver.py
Bytes: [175, 81, 191, 94]
Decimal: 2941370206
Hex: 0xaf51bf5e
```

We can verify that this solution is correct by entering the decimal number into a MIPS emulator.

Then we submit the hex value as the flag.

Flag: `0xaf51bf5e`