# 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:
```bashadb install prehistoric-mario.apk```
Once the game is  launched, here is an overview of what it looks like:
![screenshot_1](https://raw.githubusercontent.com/dspiricate/writeups/main/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:
```javaprivate 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:
```javapublic 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/dspiricate/writeups/main/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.
```pythonimport hashlibfrom itertools import productc = [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 cfor 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/dspiricate/writeups/main/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/dspiricate/writeups/main/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/dspiricate/writeups/main/ALLES/Prehistoric%20Mario/screenshot_4.png)
The flag is here!
**ALLES{1TS_A_DINO}**
