Reverse challenge which is finally a maze. A move is encoded on 2 bit of a character given as input. The combination which gets you out of the maze is the flag. We present here three different ways to solve the challenge.
[0x7ffff7dd6090]> ood aaaaaaaaaaa
Wait event received by different pid 22071
Process with PID 22072 started...
= attach 22072 22072
[0x7ffff7dd6090]> dc
hit breakpoint at: 55555555527d
[0x55555555527d]> dc
You can't go there!
[0x555555558060]> b 1130
[0x555555558060]> s 0x555555558060; psb
0x555555558060 OOOOAOO|||||OOOOOOOOOOO
0x555555558077 OO OOOO|||||OOOOO OOOOO
0x55555555808f OO OAOA|||||OOOOO OOOOO
0x5555555580a7 O OOOO| !!OOO
0x5555555580bf O OOOOO| |!!!!!!!!!!OOO
0x5555555580d7 O O//OA| |!!!!!!!!!!OOO
0x5555555580ef O O//OO| !!!!OOO
0x555555558107 O OOOOO|||!!!!! !!!!OOO
0x55555555811f O OOOOO|||||AAA AAOOOOO
0x555555558137 O ||||||AAA AAOOOOO
0x55555555814f O---- ||||||AAA OO
0x555555558167 OOO| ||||||AAAAAAOO OO
0x55555555817f OOO| |||||||AAAAAAOO OO
0x555555558197 OOO| |OOA|AAAAAAAAOO OO
0x5555555581af OOO| |OOA|AAAAAAAAOO OO
0x5555555581c7 OOO| |OOO|||||||||OO OO
0x5555555581df OOO| |_____OO|||||OO OO
0x5555555581f7 OOO| |O|||||OO OO
0x55555555820f OOO------| |O|||||OO OO
0x555555558227 OOXXXXXXO| |O||||| OO
0x55555555823f OOO//XXXO| OOOO
0x555555558257 OOO//XXXO| OO|||||OOOOO
0x55555555826f OOO!!XXXO| OO|||||OOOOO
0x555555558287 OOO!!XXXO OO||//////OO
0x55555555829f OOO!!OOOO OOO||//////OO
0x5555555582b7 OO OOO|||||||OOO
0x5555555582cf OO !!OO OOOOO|||||O|OOO
0x5555555582e7 OO !!OO OOOOO|||||O|OOO
0x5555555582ff OO !!OO OOOOOOOOOOO|OOO
0x555555558317 OO OOOO OOOOO|OOO
0x55555555832f OO OOOOOOOOOO OOOOO|OOO
0x555555558347 OO O|||||OOOO OOO|OOO
0x55555555835f OO O|||||OOOOOO OOO|OOO
0x555555558377 OO O|||||OOOOO OOO|OOO
0x55555555838f OO O|||| OOOO|OOO
0x5555555583a7 OO O|||||OOOOO OOOO|OOO
0x5555555583bf OO O|||||OOOOO OOOOOOOO
0x5555555583d7 OO O|||||OOOOO OOOO
0x5555555583ef OO |||||OOOOOOOOO OOOO
0x555555558407 OOO |||||OOOOOOOOO OOOO
0x55555555841f OOO OOOOOO OOOO
0x555555558437 OOOO|||||OOOOOOOOO OOOO
0x55555555844f OOOO|||||OOOOOOOOO OOOO
0x555555558467 OOOO|||||OOOOOOOO OOOO
0x55555555847f O////////OOOOOOOO O XO
0x555555558497 O////////OOOOOOOO OXO
0x5555555584af O////////OOOOOOOOOOOO O
We noticed that some X characters appear at the end of the maze. After playing a bit with
the argument we supposed that the goal was to move up to the top of the maze and each character
would make a move of the cursor in the maze.
Three different methods were used to solve this challenge:
1. angr
angr tool can be used to solve the challenge with the challenge without reversing. Here is the script.
#!/usr/bin/env python3importangrimportclaripydefdebug_stuff():"""
for debugging, can use killmyself() when doing ctrl+c -> Ipython shell
only one time is working
"""importsignalimportosdefkillmyself():os.system('kill %d'%os.getpid())defsigint_handler(signum,frame):print('Stopping Execution for Debug. If you want to kill the programm issue: killmyself()')ifnot"IPython"insys.modules:importIPythonIPython.embed()signal.signal(signal.SIGINT,sigint_handler)# simple logging stub to debugimportlogginglogging.basicConfig(level=logging.DEBUG)path_to_binary="the_grid1"p=angr.Project("./"+path_to_binary,load_options={"auto_load_libs":False})# here im using a symbolic value for argv[1], the size should be 8*real size because it's in bitspassword0_size_in_bits=8*11password0=claripy.BVS('password0',password0_size_in_bits)# here we create a state starting at main, with a argv[0] and 1, mandatory to pass first checkstate=p.factory.entry_state(args=[path_to_binary,password0])# create a simulation objects=p.factory.simgr(state)# use the explore analysis for basic blocks.explore(find=0x0004010A9,avoid=[0x00401096])ifs.found:solution_state=s.found[0]print(solution_state.solver.eval(password0,cast_to=bytes))else:print(f"s failed: {s}")
The script will output the flag after 10 to 20 seconds.
2. radare2
A possible alternative to angr is to use the debugging capabilities of radare2 through the r2pipe APIs which allows to send a string parameter describing the r2 command to run and get the result back as a string.
The initial idea was to identify how many X are present in memory before any new character is tested, then iterate of a charset of printables for each position by keeping only the best candidates, meaning the ones with most X present in the maze.
However, this did not le@d to the solution for two reasons:
“You can’t go there” is displayed while the character is processed whenever a wall is hit.
To resolve this issue, it is required to catch the output of the program to confirm a wall was hit or not.
Some characters such as @ were not accepted as an argument by radare2 as they were interpreted before. To circumvent the problem, there is two possibilities:
RTFM were it is explained that the whole command should be surrounded by double quote (obviously …)
1
r2> "ood @rgument"
Load the program with a dummy argument and replace it when the program is loaded :)
Long story short, below is the python2 script to solve the maze (ASLR disabled):
importr2pipeimportstringcharset=string.printabledeftest_candidates(p,y):l=[]# Initial pattern forsinp:# argument = good char + test char + paddingarg=s+"A"*(11-y)print"[Testing] "+arg# Launching r2 with debug/write mode enabler=r2pipe.open("thegrid_80f6b0f70565a2de15eab05c3ad603d18399bc2af1eabf870da6f2e4955b2a17",flags=["-d","-w"])# Reload with argumentsr.cmd('ood '+"A"*11)# Analyze binaryr.cmd('aaaa')# Continue execution until argument is in rdi registerr.cmd('dcu main+0x1f1')# Dump register addressrdi=r.cmd('dr rdi')# Seek rdir.cmd('s '+rdi)# Write the real argument to be tested @rdit=arg.encode("hex")r.cmd('w '+''.join(['\\x'+t[u:u+2]foruinrange(0,len(t),2)]))# Continue execution until the test loopr.cmd('dcu main+0x20d')# Perform y times the loop, before new chars are testedforuinrange(y):r.cmd('dcu main+0x20d')# Dump memory and identify how many X were addedsmem=r.cmd('fs strings; f').split("\n")[4].split(" ")[0]v=(r.cmd('pr 1152 @'+smem).replace("\x00","\n")).count('X')# Testing loopforxincharset:# argument = good char + test char + paddingarg=s+x+"A"*(11-y-1)# Launch r2 with debug/write mode enbaler=r2pipe.open("thegrid_80f6b0f70565a2de15eab05c3ad603d18399bc2af1eabf870da6f2e4955b2a17",flags=["-d","-w"])# Reload with argumentsr.cmd('ood '+"A"*11)# Seek rdir.cmd('s '+rdi)# Write the real argument to be tested @rdit=arg.encode("hex")r.cmd('w '+''.join(['\\x'+t[u:u+2]foruinrange(0,len(t),2)]))# Continue execution until the test loopr.cmd('dcu main+0x20d')# Perform y+1 times the loop to test the new charforuinrange(y+1):w=r.cmd('dcu main+0x20d')buf=r.cmd('pr 1152 @'+smem).replace("\x00","\n")# print buf # If error message is not displayed and more X than the initial pattern add it to the candidatesif"can't"notinwandbuf.count('X')>v:print"\t[GOOD] "+arg+"\n\n"l.append(arg[:y+1])# If argument is correct, "Nice job" is displayed meaning that the flag was foundif"Nice"inw:print"\n\n[FLAG] "+argexit()# /!\\ Don't forget to quit the current r2 process or you'll have an invasion of zombie processesr.quit()# Return list of candidatesreturnlflag=""candidates=[flag]foryinrange(len(flag),12):candidates=test_candidates(candidates,y)print"[CANDIDATES] "printcandidates
We noticed that the character is first right shifted by 6 and only the two last bits are kept. Then a function is called.
Then the character is shifted by 4 and the two last bits are kept and the same function is called and so on. Thus we supposed that
the function at 0x5555555551fa was a move function which takes 2 bits of the character as input.
After debugging a bit with several character we could figure out which move matches which 2-bit value:
|—-|————|
|0 | Left |
|1 | Up |
|2 | Right |
|3 | Down |
Thus for example, the character L is 01 00 11 00 in binary and we will move with Up, Left, Down and Left. After playing in the maze and verifying that we were moving the right way:
