Contents

GreHack 2019 - Delayed Memories - The Grid

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.

Description

The flag doesn’t follow any particular format.

DOWNLOAD FILE

Solution

We were given a binary without much information.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
$ r2 thegrid_80f6b0f70565a2de15eab05c3ad603d18399bc2af1eabf870da6f2e4955b2a17 
[0x000010c0]> ia
arch     x86
baddr    0x0
binsz    13820
bintype  elf
bits     64
canary   false
class    ELF64
compiler GCC: (Debian 9.2.1-4) 9.2.1 20190821
crypto   false
endian   little
havecode true
intrp    /lib64/ld-linux-x86-64.so.2
laddr    0x0
lang     c
linenum  false
lsyms    false
machine  AMD x86-64 architecture
maxopsz  16
minopsz  1
nx       true
os       linux
pcalign  0
pic      true
relocs   false
relro    partial
rpath    NONE
sanitiz  false
static   false
stripped true
subsys   linux
va       true

Nevertheless the strings were interesting:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
[0x000010c0]> iz
[Strings]
nth paddr      vaddr      len size section type  string
―――――――――――――――――――――――――――――――――――――――――――――――――――――――
0   0x00002004 0x00002004 19  20   .rodata ascii You can't go there!
1   0x00002018 0x00002018 17  18   .rodata ascii Usage: %s <flag>\n
2   0x0000202a 0x0000202a 21  22   .rodata ascii You lost your way ...
3   0x00002040 0x00002040 9   10   .rodata ascii Nice job!
0   0x00003060 0x00004060 23  24   .data   ascii OOOOAOO|||||OOOOOOOOOOO
1   0x00003078 0x00004078 23  24   .data   ascii OO OOOO|||||OOOOO OOOOO
2   0x00003090 0x00004090 23  24   .data   ascii OO OAOA|||||OOOOO OOOOO
3   0x000030a8 0x000040a8 23  24   .data   ascii O  OOOO|          !!OOO
4   0x000030c0 0x000040c0 23  24   .data   ascii O OOOOO| |!!!!!!!!!!OOO
5   0x000030d8 0x000040d8 23  24   .data   ascii O O//OA| |!!!!!!!!!!OOO
6   0x000030f0 0x000040f0 23  24   .data   ascii O O//OO|        !!!!OOO
7   0x00003108 0x00004108 23  24   .data   ascii O OOOOO|||!!!!! !!!!OOO
8   0x00003120 0x00004120 23  24   .data   ascii O OOOOO|||||AAA AAOOOOO
9   0x00003138 0x00004138 23  24   .data   ascii O     ||||||AAA AAOOOOO
10  0x00003150 0x00004150 23  24   .data   ascii O---- ||||||AAA      OO
11  0x00003168 0x00004168 23  24   .data   ascii OOO|  ||||||AAAAAAOO OO
12  0x00003180 0x00004180 23  24   .data   ascii OOO| |||||||AAAAAAOO OO
13  0x00003198 0x00004198 23  24   .data   ascii OOO| |OOA|AAAAAAAAOO OO
14  0x000031b0 0x000041b0 23  24   .data   ascii OOO| |OOA|AAAAAAAAOO OO
15  0x000031c8 0x000041c8 23  24   .data   ascii OOO| |OOO|||||||||OO OO
16  0x000031e0 0x000041e0 23  24   .data   ascii OOO| |_____OO|||||OO OO
17  0x000031f8 0x000041f8 23  24   .data   ascii OOO|       |O|||||OO OO
18  0x00003210 0x00004210 23  24   .data   ascii OOO------| |O|||||OO OO
19  0x00003228 0x00004228 23  24   .data   ascii OOXXXXXXO| |O|||||   OO
20  0x00003240 0x00004240 23  24   .data   ascii OOO//XXXO|         OOOO
21  0x00003258 0x00004258 23  24   .data   ascii OOO//XXXO| OO|||||OOOOO
22  0x00003270 0x00004270 23  24   .data   ascii OOO!!XXXO| OO|||||OOOOO
23  0x00003288 0x00004288 23  24   .data   ascii OOO!!XXXO  OO||//////OO
24  0x000032a0 0x000042a0 23  24   .data   ascii OOO!!OOOO OOO||//////OO
25  0x000032b8 0x000042b8 23  24   .data   ascii OO        OOO|||||||OOO
26  0x000032d0 0x000042d0 23  24   .data   ascii OO !!OO OOOOO|||||O|OOO
27  0x000032e8 0x000042e8 23  24   .data   ascii OO !!OO OOOOO|||||O|OOO
28  0x00003300 0x00004300 23  24   .data   ascii OO !!OO OOOOOOOOOOO|OOO
29  0x00003318 0x00004318 23  24   .data   ascii OO OOOO       OOOOO|OOO
30  0x00003330 0x00004330 23  24   .data   ascii OO OOOOOOOOOO OOOOO|OOO
31  0x00003348 0x00004348 23  24   .data   ascii OO O|||||OOOO   OOO|OOO
32  0x00003360 0x00004360 23  24   .data   ascii OO O|||||OOOOOO OOO|OOO
33  0x00003378 0x00004378 23  24   .data   ascii OO O|||||OOOOO  OOO|OOO
34  0x00003390 0x00004390 23  24   .data   ascii OO O||||       OOOO|OOO
35  0x000033a8 0x000043a8 23  24   .data   ascii OO O|||||OOOOO OOOO|OOO
36  0x000033c0 0x000043c0 23  24   .data   ascii OO O|||||OOOOO OOOOOOOO
37  0x000033d8 0x000043d8 23  24   .data   ascii OO O|||||OOOOO     OOOO
38  0x000033f0 0x000043f0 23  24   .data   ascii OO  |||||OOOOOOOOO OOOO
39  0x00003408 0x00004408 23  24   .data   ascii OOO |||||OOOOOOOOO OOOO
40  0x00003420 0x00004420 23  24   .data   ascii OOO         OOOOOO OOOO
41  0x00003438 0x00004438 23  24   .data   ascii OOOO|||||OOOOOOOOO OOOO
42  0x00003450 0x00004450 23  24   .data   ascii OOOO|||||OOOOOOOOO OOOO
43  0x00003468 0x00004468 23  24   .data   ascii OOOO|||||OOOOOOOO  OOOO
44  0x00003480 0x00004480 23  24   .data   ascii O////////OOOOOOOO O   O
45  0x00003498 0x00004498 23  24   .data   ascii O////////OOOOOOOO   O O
46  0x000034b0 0x000044b0 23  24   .data   ascii O////////OOOOOOOOOOOO O
47  0x000034c8 0x000044c8 23  24   .data   ascii OOOOOOOOOOOOOOOOOOOOOOO

Indeed, it seems that some strings were representing a maze.

We first noticed that the given argument should be 11 characters long or the program exits:

1
2
3
4
0x0000126b          xor eax, eax                ; arg2                                                                                                                            
0x0000126d          repne scasb al, byte [rdi]                                                                                                                                    
0x0000126f          cmp rcx, 0xfffffffffffffff3                                                                                                                                   
0x00001273          jne 0x12cb

Then the program iterate over each characters of the argument until it reaches the null character:

/resources/2019/grehack/thegrid/move_code.png
Move code

If a wrong input is given the binary complains:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
[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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/env python3

import angr
import claripy

def debug_stuff():

    """
    for debugging, can use killmyself() when doing ctrl+c -> Ipython shell
    only one time is working

    """

    import signal
    import os

    def killmyself():
        os.system('kill %d' % os.getpid())

    def sigint_handler(signum, frame):
        print ('Stopping Execution for Debug. If you want to kill the programm issue: killmyself()')
        if not "IPython" in sys.modules:
            import IPython
            IPython.embed()

    signal.signal(signal.SIGINT, sigint_handler)

    # simple logging stub to debug
    import logging
    logging.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 bits
password0_size_in_bits = 8*11
password0 = 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 check
state = p.factory.entry_state(args=[path_to_binary, password0])

# create a simulation object
s = p.factory.simgr(state)

# use the explore analysis for basic block
s.explore(find=0x0004010A9 ,avoid=[0x00401096]) 

if s.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):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import r2pipe
import string

charset = string.printable

def test_candidates (p,y):
    l = []
    # Initial pattern 
    for s in p:
        # argument = good char + test char + padding
        arg=s + "A"*(11-y)
        
        print "[Testing] " + arg
        
        # Launching r2 with debug/write mode enable
        r = r2pipe.open("thegrid_80f6b0f70565a2de15eab05c3ad603d18399bc2af1eabf870da6f2e4955b2a17", flags=["-d","-w"])
        
        # Reload with arguments
        r.cmd('ood ' + "A"*11)
        
        # Analyze binary
        r.cmd('aaaa')
        
        # Continue execution until argument is in rdi register
        r.cmd('dcu main+0x1f1')
        
        # Dump register address
        rdi=r.cmd('dr rdi')
        
        # Seek rdi
        r.cmd('s ' + rdi)

        # Write the real argument to be tested @rdi
        t=arg.encode("hex")
        r.cmd('w '+ ''.join(['\\x'+t[u:u+2] for u in range(0,len(t),2)]))

        # Continue execution until the test loop
        r.cmd('dcu main+0x20d')

        # Perform y times the loop, before new chars are tested
        for u in range(y):
            r.cmd('dcu main+0x20d')

        # Dump memory and identify how many X were added
        smem = r.cmd('fs strings; f').split("\n")[4].split(" ")[0]
        v=(r.cmd('pr 1152 @'+smem).replace("\x00","\n")).count('X')

        # Testing loop
        for x in charset:
            # argument = good char + test char + padding
            arg=s + x + "A"*(11-y-1)

            # Launch r2 with debug/write mode enbale
            r = r2pipe.open("thegrid_80f6b0f70565a2de15eab05c3ad603d18399bc2af1eabf870da6f2e4955b2a17", flags=["-d","-w"])

            # Reload with arguments
            r.cmd('ood ' + "A"*11)

            # Seek rdi
            r.cmd('s ' + rdi)

            # Write the real argument to be tested @rdi
            t=arg.encode("hex")
            r.cmd('w '+ ''.join(['\\x'+t[u:u+2] for u in range(0,len(t),2)]))

            # Continue execution until the test loop
            r.cmd('dcu main+0x20d')

            # Perform y+1 times the loop to test the new char
            for u in range(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 candidates
            if "can't" not in w and buf.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 found
            if "Nice" in w:
                print "\n\n[FLAG] " + arg
                exit()
            # /!\\ Don't forget to quit the current r2 process or you'll have an invasion of zombie processes
            r.quit()
    # Return list of candidates
    return l

flag = ""
candidates = [flag]

for y in range(len(flag),12):
    candidates = test_candidates(candidates,y)
    print "[CANDIDATES] "
    print candidates

3. ReverseFu

According to the assembly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
0x555555555275      mov dil, byte [rbx]
0x555555555278      test dil, dil
0x55555555527b      je 0x5555555552b7
0x55555555527d      shr edi, 6
0x555555555280      inc rbx
0x555555555283      and edi, 3
0x555555555286      call 0x5555555551fa
0x55555555528b      movsx edi, byte [rbx - 1]
0x55555555528f      sar edi, 4
0x555555555292      and edi, 3
0x555555555295      call 0x5555555551fa
0x55555555529a      movsx edi, byte [rbx - 1]
0x55555555529e      sar edi, 2
0x5555555552a1      and edi, 3
0x5555555552a4      call 0x5555555551fa
0x5555555552a9      mov dil, byte [rbx - 1]
0x5555555552ad      and edi, 3
0x5555555552b0      call 0x5555555551fa
0x5555555552b5      jmp 0x555555555275

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
[0x7ffff7ea0946]> b 1130
[0x7ffff7ea0946]> 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|      X|O|||||OO OO
0x55555555820f OOO------|X|O|||||OO OO
0x555555558227 OOXXXXXXO|X|O|||||   OO
0x55555555823f OOO//XXXO|X        OOOO
0x555555558257 OOO//XXXO|XOO|||||OOOOO
0x55555555826f OOO!!XXXO|XOO|||||OOOOO
0x555555558287 OOO!!XXXOXXOO||//////OO
0x55555555829f OOO!!OOOOXOOO||//////OO
0x5555555582b7 OO     XXXOOO|||||||OOO
0x5555555582cf OO !!OOXOOOOO|||||O|OOO
0x5555555582e7 OO !!OOXOOOOO|||||O|OOO
0x5555555582ff OO !!OOXOOOOOOOOOOO|OOO
0x555555558317 OO OOOOXXXXXXXOOOOO|OOO
0x55555555832f OO OOOOOOOOOOXOOOOO|OOO
0x555555558347 OO O|||||OOOOXXXOOO|OOO
0x55555555835f OO O|||||OOOOOOXOOO|OOO
0x555555558377 OO O|||||OOOOOXXOOO|OOO
0x55555555838f OO O||||      XOOOO|OOO
0x5555555583a7 OO O|||||OOOOOXOOOO|OOO
0x5555555583bf OO O|||||OOOOOXOOOOOOOO
0x5555555583d7 OO O|||||OOOOOXXXXXOOOO
0x5555555583ef OO  |||||OOOOOOOOOXOOOO
0x555555558407 OOO |||||OOOOOOOOOXOOOO
0x55555555841f OOO         OOOOOOXOOOO
0x555555558437 OOOO|||||OOOOOOOOOXOOOO
0x55555555844f OOOO|||||OOOOOOOOOXOOOO
0x555555558467 OOOO|||||OOOOOOOOXXOOOO
0x55555555847f O////////OOOOOOOOXOXXXO
0x555555558497 O////////OOOOOOOOXXXOXO
0x5555555584af O////////OOOOOOOOOOOO O

We finally reached the end of the maze:

1
2
3
4
5
[0x000010c0]> "ood LeAd@Ze@VAY"
Process with PID 6486 started...
= attach 6486 6486
[0x7f92a9ded090]> dc
Nice job!

And the parameter is the flag to submit.