Context

This challenge was a gameboy file about finding one of the possible exit of the labyrinth.
You can move up to 4 directions :

• Up : U
• Down : D
• Left : L
• Right : R

I used bgb to emulate the game and debug.
I used Ghidra and GhidraBoy extension to decompile SM83 assembly language to C language.

Memory map

I didn’t know where to start so i looked at memory mapping of gameboy from gbdev.

It is said that WRAM has a mapped range of 0xC000 – 0xDFFF : this is the internal RAM of the gameboy where all temporary data are stored. Maybe interesting stuff are saved here.

I right clicked on the bgb screen to open the debugger, i looked at 0xc000 address (WRA0) and this is what i found out :

• 0xc000 : Y position of little dude on screen
• 0xc001 : X position of little dude on screen
• 0xc002 : ON / OFF animation sprite

Interesting… I used Ghidra to know all the references of 0xc000 and i saw that the address 0x0b55 wrote DAT_c805 to DAT_c000 :

So it means that :

• Something is written in X position at 0xc805
• I have to look at 0xc800 - 0xc900 address range because it seems that there is some data too

ULDR array

I restarted the game and looked at 0xc800 - 0xc900 address range in debugger :

It seems that 0xc808 is the address of a movements array ! If we go up, the map changes and U is stored in this array.

Because a value different of 0x00 is stored at 0xc828, i assume that the array has a length of 32 bytes (probably the length of the flag inside AMSI{...} flag format).

Let’s look at references of 0xc808 in Ghidra :

Very cool informations in FUN_06fc function :

• Line 7 confirms that 0xc808 is an array and obviously 0xc838 is the index of the array (incremented at line 8).
• Line 9 does stuff while its value is lower than 32 : it means that 32 is the length of our array

Let’s rename these Ghidra decompilation variables :

• DAT_c808 : ULDR_array
• DAT_c838 : index_of_ULDR_array

Another function at 0x729 uses ULDR_array :

Let me do some function cleaning :

undefined1 FUN_0729(void)
{
        return_value = 0;
        if (index_of_ULDR_array == 0x20) {
                for (int i = 0; i < 16; i++) {
                        if ((&DAT_c828)[i] != ((&ULDR_array)[(i * 2 + 1)] ^ (&ULDR_array)[i * 2])) {
                        return_value = 0;
                        return 0;
                        }
                }
                return_value = 1;
        }
        return return_value;
}

This FUN_0729 function is crucial :

• It checks if the index of ULDR array is equal to 32 bytes (end of the array)
• If the end of the array is reached, it will compare 16 times if ULDR_array[i * 2 + 1] ^ ULDR_array[i * 2] is equal to DAT_c828[i]
• If everything is good, it returns 0 otherwise it returns 1

It means that DAT_c828 is the array that probably compares the flag, and FUN_0729 function is the final checking flag function.

Winning message

To be sure of our assumption, let’s see all the references to FUN_0729.

There are two calls of FUN_0729 : FUN_0789 and FUN_09a7.
Because FUN_09a7 calls FUN_0729 once without checking the return value, i assume that this is not the one we’re looking at. But FUN_0789 does !

Indeed, it compares the return value with 0x00 at line 89 (address 0x8ff), and then does stuff.
So…. if i set PC register at 0x8ff… i should get a winning message, right ?

Bingo !
Because we know that FUN_0729 is cheking the flag, we have to look at DAT_C828 array to retrieve the XORed key from the intended flag : 19 19 08 16 07 00 19 11 08 16 11 19 00 1e 07 11

Retrieve the flag

Let’s use some Python code to retrieve all possible combinations of flag. We have multiple combinations because XOR function is non-injective (different inputs can give same output).

xored_key = [0x19,0x19,0x08,0x16,0x07,0x00,0x19,0x11,0x08,0x16,0x11,0x19,0x00,0x1e,0x07,0x11]
inputs = [0] * 32
movements = ['U','D','L','R'] # UP, DOWN, LEFT, RIGHT
all_possibilities = []

# Generate all possibilities
for x in xored_key:
        tmp_list = []
        for i in range(len(movements)):
                for j in range(len(movements)):
                        if(ord(movements[i]) ^ ord(movements[j]) == x):
                                tmp_list.append([movements[i]+movements[j]])
        all_possibilities.append(tmp_list)

# Show all possibilities
for _ in all_possibilities:
        p = ""
        for y in _:
                p += "".join(y)
                p += ','
        print(p)

And here is the result :

UL,LU,
UL,LU,
DL,LD,
DR,RD,
UR,RU,
UU,DD,LL,RR,
UL,LU,
UD,DU,
DL,LD,
DR,RD,
UD,DU,
UL,LU,
UU,DD,LL,RR,
LR,RL,
UR,RU,
UD,DU,

That’s great : each line has two or four possibilities of movements. But there is another problem…

If we go up, we can’t go up anymore or even to the left / right : we can only go down (but we can infinitely go down/left/right).
Furthermore, when we go up, it will trigger the flag checking function (FUN_0729) and we flag only if this is the last movement of the array : so we know that the last movement will be U.
Thanks to our python script, we know that the last move is DU.
In, this same pattern, we know that the first move can only be U : thanks to our python script, we know that the first move is UL.

Let’s arrange our Python script to generate all possible flags :

xored_key = [0x19,0x19,0x08,0x16,0x07,0x00,0x19,0x11,0x08,0x16,0x11,0x19,0x00,0x1e,0x07,0x11]
inputs = [0] * 32

movements = ['U','D','L','R'] # UP, DOWN, LEFT, RIGHT
all_possibilities = []

# Generate all possibilities
for x in xored_key:
    tmp_list = []
    for i in range(len(movements)):
        for j in range(len(movements)):
            if(ord(movements[i]) ^ ord(movements[j]) == x):
                tmp_list.append([movements[i]+movements[j]])
    all_possibilities.append(tmp_list)

# Remove all forbidden moves and reduce the number of possibilities before itertools cartesian product
forbidden_moves = ["UU","UL","UR"]
for i in range(0, len(all_possibilities)):
    for j in range(len(all_possibilities[i])):
        if(i == 0):
            if(all_possibilities[i][j][0] not in ["UU","UL","UR"]):
                # Check for first move because we can only go up
                del all_possibilities[i][j][0]
        elif(i == 15):
            if(all_possibilities[i][j][0] not in ["DU"]):
                # Check for the last move to be only "DU"
                del all_possibilities[i][j][0]
        else:
            if(all_possibilities[i][j][0] in forbidden_moves):
                del all_possibilities[i][j][0]
    all_possibilities[i] = [_ for _ in all_possibilities[i] if _] # Remove empty lists

from itertools import product

# Use cartesian product to list all final possibilities
combinations = [list(map(list, p)) for p in product(*all_possibilities)]

# Final filter of 1152 possible moves
for i in range(len(combinations)):
    combinations[i] = ''.join(sub[0] for sub in combinations[i])

flags = []

for i in range(len(combinations)):
    up = 0
    for j in range(len(combinations[i])):
        if(combinations[i][j] == 'U'):
            up += 1
            j += 1
        if(j < len(combinations[i]) and combinations[i][j] == 'D'):
            up = 1
            j += 1
        if(up > 2): # Impossible
            break
        if(up == 2):
            if(j < len(combinations[i]) and  combinations[i][j] in ['U','L','R']): # Impossible
                break
        if(j == len(combinations[i]) - 1):
            flags.append("AMSI{" + combinations[i] + '}')
            break
        
for _ in flags:
    print(_)

And here are the 8 possible flags

AMSI{ULLUDLDRRUDDLUDUDLDRUDLUDDLRRUDU}
AMSI{ULLUDLDRRUDDLUDUDLDRUDLUDDRLRUDU}
AMSI{ULLUDLDRRUDDLUDUDLRDUDLUDDLRRUDU}
AMSI{ULLUDLDRRUDDLUDUDLRDUDLUDDRLRUDU}
AMSI{ULLUDLRDRUDDLUDUDLDRUDLUDDLRRUDU}
AMSI{ULLUDLRDRUDDLUDUDLDRUDLUDDRLRUDU}
AMSI{ULLUDLRDRUDDLUDUDLRDUDLUDDLRRUDU}
AMSI{ULLUDLRDRUDDLUDUDLRDUDLUDDRLRUDU}