Tags: android reverse apk 

Rating: 5.0

# Prehistoric Mario

## Category: Reverse Engineering - Medium

In this challenge, the user must win an Android Mario-like game.

### The game

To start the challenge, the APK has first been installed on an emulated Android created with AVD manager.

To do so, `adb` was used on the running device with the command:

```bash
adb install prehistoric-mario.apk
```

Once the game is launched, here is an overview of what it looks like:

![screenshot_1](https://raw.githubusercontent.com/alexis-elmrini/writeups/master/ALLES/Prehistoric%20Mario/screenshot_1.png)

The user is a dinosaur who can only go right and left, crouch or jump.

The map seems to be quite small and is composed of either walls or interrogative boxes.

There are, at first glance, 11 interrogative boxes. If the dinosaur touches one of them from the bottom, its color changes. A box can have 4 colors: Green, Red, Yellow or Blue.

It seems that the aim is to find the right combination of colors to spawn the flag.

### Decompiling the APK

In order to decompile the APK, I used *APK Studio*, a software based on several tools that allows to decompile the APK, modify the source code and recompile it.

The main sources of the application are then located on `sources/com/alles/platformer` folder. Especially, the file `MyPlatformer.java` contains the most interesting methods.

#### The `checkFlag()` method

I immediately spotted the `checkFlag` method, whose code is:

```java
private void checkFlag() {
MessageDigest messageDigest;
int intValue;
byte[] bArr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
TiledMapTileLayer tiledMapTileLayer = (TiledMapTileLayer) this.map.getLayers().get("questionmarks");
int i = 0;
int i2 = 0;
while (i < 100) {
int i3 = i2;
for (int i4 = 0; i4 < 100; i4++) {
TiledMapTileLayer.Cell cell = tiledMapTileLayer.getCell(i, i4);
if (!(cell == null || !cell.getTile().getProperties().containsKey("questionmarkType") || (intValue = ((Integer) cell.getTile().getProperties().get("questionmarkType")).intValue()) == 1337)) {
bArr[i3] = (byte) intValue;
i3++;
}
}
i++;
i2 = i3;
}
try {
messageDigest = MessageDigest.getInstance("SHA-256");
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
messageDigest = null;
}
messageDigest.update(bArr);
messageDigest.update("P4ssw0rdS4lt".getBytes());
if (toHex(messageDigest.digest()).equals("024800ace2ec394e6af68baa46e81dfbea93f0f6730610560c66ee9748d91420")) {
try {
messageDigest.update(bArr);
messageDigest.update("P4ssw0rdS4lt".getBytes());
messageDigest.update(bArr);
byte[] digest = messageDigest.digest();
byte[] decode = Base64Coder.decode(Gdx.files.internal("flag_enc").readString());
SecretKeySpec secretKeySpec = new SecretKeySpec(digest, 0, digest.length, "RC4");
Cipher instance = Cipher.getInstance("RC4");
instance.init(2, secretKeySpec, instance.getParameters());
String str = new String(instance.doFinal(decode));
FileHandle local = Gdx.files.local("map_flag.tmx");
local.writeString(str, false);
Gdx.files.local("tileSet.png").writeBytes(Base64Coder.decode(/*base64 encoded data */), false);
TmxMapLoader tmxMapLoader = new TmxMapLoader(new LocalFileResolver());
tmxMapLoader.getDependencies(BuildConfig.FLAVOR, local, null);
AssetManager assetManager = new AssetManager(new LocalFileResolver());
assetManager.load("tileSet.png", Texture.class);
assetManager.finishLoading();
tmxMapLoader.loadAsync(assetManager, "map_flag.tmx", local, (TmxMapLoader.Parameters) null);
this.map.dispose();
this.map = tmxMapLoader.loadSync((AssetManager) null, (String) null, (FileHandle) null, (TmxMapLoader.Parameters) null);
this.renderer = new OrthogonalTiledMapRenderer(this.map, 0.0625f);
} catch (Exception e2) {
e2.printStackTrace();
}
}
}
```

The method works as following:

1. An array (bArr) of length 11 is initialized.
2. The tiles of type "Question Mark" are retrieved.
3. Each case of the game's 100x100 grid is checked:
1. If the case is a question mark tile, its `intValue` is put into the array bArr, except if this value is 1337.
4. A SHA-256 digest is initialized.
5. The digest is updated with the bArr byte array.
6. The digest is updated with a salt: "P4ssw0rdS4lt".
7. If the digest matches a given hash, then the flag file is decrypted and displayed on the game.

There are now three goals to achieve:

1. Find the values corresponding to the colors.
2. Once it is done, find which combination generates the given hash.
3. Find how to trigger the `checkFlag` method

#### The color code

Again in the `MyPlatformer.java` file, the int values can be found, in the `updateKoala` method:

```java
...
if (cell2.getTile().getProperties().containsKey("questionmarkType")) {
int intValue = ((Integer) cell2.getTile().getProperties().get("questionmarkType")).intValue();
if (intValue == 1337) {
new Array();
checkFlag();
} else {
if (intValue == 0) {
intValue = 21;
} else if (intValue == 21) {
intValue = 97;
} else if (intValue == 97) {
intValue = 37;
} else if (intValue == 37) {
intValue = 0;
}
try {
new TiledMapTileLayer.Cell();
cell2.setTile(this.map.getTileSets().getTile(this.questionMarkTileMapping.get(Integer.valueOf(intValue)).intValue()));
tiledMapTileLayer.setCell((int) next.x, (int) next.y, cell2);
} catch (Exception unused) {
}
}
z = true;
}
...
```

I guess this method is called at every new frame and is used to act on the map elements according to the user's position, velocity and environment.

Here, cell2 is probably the cell above the user. This part of the method is about the case in which the cell2 is a question mark tile. If the `intValue` is not 1337, it is changed according to a cycle.

Thus the possible values are 0, 21, 37 and 97.

A grep on these values is useful to find the corresponding sprite IDs of each color. It is linked in the `create` method:

```java
public void create() {
...
this.questionMarkTileMapping = new HashMap<>();
this.questionMarkTileMapping.put(0, 128);
this.questionMarkTileMapping.put(21, 160);
this.questionMarkTileMapping.put(37, 176);
this.questionMarkTileMapping.put(97, 192);
this.controller = new Controller();
}

```

By checking in the `assets` folder, the tile set can be found:

![tileSet.png](https://raw.githubusercontent.com/alexis-elmrini/writeups/master/ALLES/Prehistoric%20Mario/tileSet.png)

It is a 16x16 map containing the textures of each tile type. Taken from the top-left corner to the bottom-right corner, the ID of each tile can be calculated. Thus, the intValue-color association is done:

- Green = G = 0 = 0x00
- Red = R = 21 = 0x15
- Yellow = Y = 37 = 0x25
- Blue = B = 97 = 0x61

#### The color combination

It is then possible to find the right combination by computing the digest for all the 4^11 possible color combinations.

```python
import hashlib
from itertools import product
c = [chr(0), chr(21), chr(37), chr(97)]
col = "GRYB"
mapping = list(product(c, repeat=11)) # Generate all the combinations of 11 characters on the charset c
for t in mapping:
word = "".join(t)
sha = hashlib.sha256()
sha.update(word)
sha.update("P4ssw0rdS4lt")
if(sha.hexdigest() == "024800ace2ec394e6af68baa46e81dfbea93f0f6730610560c66ee9748d91420"):
print word.encode('hex'), ':', "".join([col[c.index(x)] for x in t]) # Print the solution in hex and "color" formats
```

The script gives the following solution:

```
1500612515252561612515 : RGBYRYYBBYR
```

#### The `checkFlag` trigger

As shown in the `updateKoala` method, the `checkFlag` method is triggered when hitting a question mark tile that is different from the green, red, yellow and blue ones. The tile set gives the clue that the question mark tile should be multicolored.

I decided to play a bit more to the game, finding a "secret" platform when I jumped over the wall on the right:

![screenshot_2.png](https://raw.githubusercontent.com/alexis-elmrini/writeups/master/ALLES/Prehistoric%20Mario/screenshot_2.png)

I fell on a hidden platform, with the secret tile at the end:

![screenshot_3.png](https://raw.githubusercontent.com/alexis-elmrini/writeups/master/ALLES/Prehistoric%20Mario/screenshot_3.png)

After having set the right color combination (from left to right), I hit the tile, and then...

![screenshot_4.png](https://raw.githubusercontent.com/alexis-elmrini/writeups/master/ALLES/Prehistoric%20Mario/screenshot_4.png)

The flag is here!

**ALLES{1TS_A_DINO}**

Original writeup (https://github.com/alexis-elmrini/writeups/tree/master/ALLES/Prehistoric%20Mario).