The binary stores a maze in `char[1000]` array. Arrays for different levels are adjacent in memory,and right after them goes "history" array. While it is possible to choose level from 1 to 8, thereare only 5 maze arrays, which means that, if you choose sixth level, it will be actually played onthe "history" array.
What is history? You can turn it on with `h` key, after what the direction of your movements will bestored in history. Direction is a 2-bit number, it denotes a direction that you took to the nextcell, and is stored on stepping to another cell. On starting position going forward will be 0, rightis 1, back is 2, and left is 3. Restarting the level (`r`) does not write anything to the history.Cell size is 10 steps, so you need to take at least 6 steps from starting position to write anythingto history.
Described scheme is a primitive that allows you to completely control level 6 contents. It happensbecause there are free cells in all 4 directions on the starting position of the starting level(level 0?). We take 2 bits that we want to store, move to the neighbour cell in appropriatedirection, and "respawn" to the starting position using `r`.
Now we need to know what to write. Maze structure starts with 2-byte long magic "MZ". After that gotwo 1-byte dimensions, X and Y. Next goes 8 byte long "signature", and finally there goes an arrayof X*Y chars, which is a map of a maze. Maze structure is padded to 1000 bytes with `\x00`. In mazemap, `0` means free cell, `1` is a wall, and `*` is a cell with yellow box (which we need toobtain). Signature is computed by encrypting SHA-256 of padded maze array using AES-128-CBC andtaking first 8 bytes. Those crypto algorithms seem to be modified a bit, I didn't manage to recreatethe scheme in Python. Anyway, easiest way is to start game in GDB, patch in our maze payload andjump to signature checking code.
This is the solution in its entirety, since level 0 is trivial, and we get flying ability aftergetting yellow box, so we need just to fly up and look for a flag on the plane wing.
The maze I used is 1x4, it places yellow box right in front of us:
`111*`
For Babymaze we get signature `0xd3, 0xa4, 0xdb, 0xe5, 0x6d, 0xbf, 0x6c, 0xdf` and following moves:
```press H !!!> ^ < >    1 0 3 1> > v v    1 1 2 2^ ^ ^ >    0 0 0 1^ ^ > ^    0 0 1 0< > ^ <    3 1 0 3v v > ^    2 2 1 0< > v <    3 1 2 3< v > >    3 2 1 1> v < >    1 2 3 1v < < <    2 3 3 3> v < ^    1 2 3 0< > < <    3 1 3 3^ < ^ >    0 3 0 1^ < ^ >    0 3 0 1^ < ^ >    0 3 0 1^ v v v    0 2 2 2```
For Mamamaze signature is `0xa7, 0xac, 0x3c, 0x37, 0x7e, 0xa3, 0xbc, 0x5a`, moves are:
```press H !!!> ^ < >    1 0 3 1> > v v    1 1 2 2^ ^ ^ >    0 0 0 1^ ^ > ^    0 0 1 0v v > <    2 2 1 3v v < ^    2 2 3 0^ < < ^    0 3 3 0^ < > <    0 3 1 3> < < v    1 3 3 2v v ^ <    2 2 0 3v < < ^    2 3 3 0> > v v    1 1 2 2^ < ^ >    0 3 0 1^ < ^ >    0 3 0 1^ < ^ >    0 3 0 1^ v v v    0 2 2 2```