Escape from ELF
Description
A good traveller is one who knows how to travel with the mind.
A colleague of yours has sent you a program he developed and wants to challenge you.
Find the shortest entries that validates your access and get the flag.
File: chall.
TL;DR
The program uses our arguments as combination to control the movement of a player in a corresponding maze. When all levels are solved, our combinations are checked to ensure that they were the shortest ones.
The shortest combination allows the player to get out of the maze in minimum action, where the maximum is 8. In order to find them, we admit that the player can slide and go up to 15 cells in a straight line with a single action.
Reverse engineering
The file we’re given is a x86_64 ELF executable:
# file chall
chall: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=53800f34d1e7ef3715752bce6f01e9aedf7fedfa, stripped
It’s stripped so we won’t have any debug symbols.
Looking at the .rodata segment, we can see that there are not many strings, but some of them are referring to the flag output:
All these strings are used within the main function, let’s analyze it.
main function analysis
Having spent some time RE this program, I came up with the following description of the main function:
- for each of the first 3 arguments passed to the program (
argv[1]toargv[3]):- load a corresponding set of game level settings (i.e., the player default position, board width, etc.)
- cast the argument to a 64-bit unsigned integer (
unsigned long long int) and save it into a history - play the corresponding game level (see
playfunction) - if we’ve solved the game level, a counter is incremented
- finally:
- check if we’ve solved all game levels
- compare the sum of our arguments to a constant (basically check for expected shortest values)
- print the flag containing the history entries
- exit
Here’s the corresponding pseudocode:
And, here are the structures and enums used in the function:
Notes: please keep in mind that these data types and all semantic elements have been inferred throughout the global RE process. In order to deduce them, I globally applied this iterative process:
- search for cross-references on dynamic and static data (e.g.
.rodata,.datasegments, program arguments) - make basic description of instruction blocks
- search for semantic links between blocks (e.g.
jmp,jnz,js) - search for data processing (e.g.
lea,mov,add,sub) - search for semantic links between the data processing and the data itself (e.g. “the fourth byte is used as a length indicator”)
- create additional data types (e.g.
struct,enum) - apply data types to the raw data
At this point, we don’t really know how to win at these games, we need to go deeper!
play function analysis
This function is fairly simple:
- we split the argument
argv[i](passed by themainfunction) into multiple bytes (where the max is8becausesizeof(unsigned long long int) / 8 == 64 / 8 == 8) - extract the low and high nibble (4-bits less significant bits and more significant bits within the byte) where:
- the high nibble (the leftmost one) is used as a direction indicator
- the low nibble (the rightmost one) is used as a step count
- play these moves description on the current level (see
move_playerfunction) - return the game status for the last valid move
Here’s the corresponding pseudocode:
And, here is the structure used in the function:
So far, we still don’t know how the game works and how to validate its levels, let’s dig a little more!
move_player function analysis
This function is pretty long, but quite simple:
- get the move direction indicator:
- if it equals
8, we will have to make enough steps to move the player one cell up (i.e., we subtract the width of our game board from our current position) - if it equals
2, we want our player to move one cell to down (i.e., we add the width of our game board to our current position) - if it equals
4, we want our player to move one cell to the left (i.e., we decrement our current position) - if it equals
6, we want our player to move one cell to the right (i.e., we increase our current position)
- if it equals
- we apply the move as many times as requested (note: the step count is stored on 4 bits, so we can’t make more than 15 steps in the same direction in a single action)
- if the destination cell is a wall, there’s a collision → game over
- if the destination cell isn’t inside the board, there’s an overflow → game over
- if the destination cell is the end cell, we’ve solved the current level
- Finally, we return the new player position
Here’s the corresponding pseudocode:
And, here are the enums used in the function:
We now know the game rules, they’re pretty simple:
- the game level board has a variable width
- the player starts at a random position on the game board
- the player moves on X and Y axis allowing up, down, left and right movements
- the player can only move on a valid cell (i.e., not a wall)
- we must reach the end cell in a minimum of movement (less than 9)
There are now some problems to solve this challenge, the most annoying being that no function has been implemented to visualize the player’s progression in the current level. Let’s do something about it!
Uncovering game levels
In order to play the game without being blindfolded, we can take advantage of the fact that each game function returns the new player position, and represent the game board in ASCII.
In order to do that, we just need to call a function like the following one at the desired time:
// display level board with player position ('o' character).
void display(struct level_t * level, uint16_t pos) {
int i;
uint8_t cell_char;
for (i=0; i < strlen(level->board); i++) {
// get the current cell char.
cell_char = level->board[i] ^ level->xor_mask;
if ((i % level->board_width == 0) && (i != 0)) { // add a line break at the end of each board lines.
printf("\n");
}
if (i == pos) { // if the current current cell is the starting one.
c = 'o';
}
printf("%c ", c); // print the current cell char.
}
printf("\n");
}
In order to call this function easily after each level run, I created a game wrapper (sources: debug.tar.gz) that basically loads the original challenge file as a shared library:
# gcc -o -Wall debug.c -ldl -o debug
# ./debug 0 0 0
[+] Loaded functions:
move: 0x7feae328a17e
play: 0x7feae328a2d8
[+] Level 1: (moves = 0)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 o 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 0 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
[+] Level 2: (moves = 0)
8 o 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 8
[+] Level 3: (moves = 0)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 0 8 8 8 8
8 8 8 8 8 8 o 8 8 8 8 8 8 8 8
8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
Okay, so the game consists of a kind of maze puzzle where the player (marked with a o) has to reach a cell (marked with a 0) without hitting a wall (marked with a 8).
Maze representation
The challenge description stated that we should be looking for the shortest entries that validates our access. For the sake of the exercise, I decided to use the python networkx module to find the shortest path allowing the player to reach the exit cell on each board.
In order to keep a data structure close the binary one (struct level_t) to represent the game levels, I created a list of dict and stored the decoded board:
levels = [
{
'width': 21,
'board': [
'8', '8', '8', '8', '8', ...
]
}, { ... }
]
From maze to directed graph
The directed graph creation is pretty simple and consists in a few steps:
- for each cell of the board, if it’s a valid cell (i.e., not a wall):
- get the 2D position of the current cell relative to the first cell of the board (the top-left one)
- create a vertex at the current position
- if we can go down, left or right:
- get the 2D position of the adjacent cell
- create a vertex at the adjacent position
- create a bidirectional edge between the current and the adjacent vertex
Here’s an example of an implementation of this algorithm using networkx:
import networkx
import matplotlib.pyplot as plt
from levels import *
WALL, CELL, PLAYER, TARGET = ('8', ' ', 'o', '0')
color_map = {
WALL: '#000000',
CELL: '#ffffff',
PLAYER: '#22b14c',
TARGET: '#ed1c24'
}
def is_valid_cell(cell):
"""basically check if we're able to go to the specified cell."""
return cell == CELL or cell == PLAYER or cell == TARGET
def get_2d_pos(index, width):
"""convert an index into a (x, y) position based on the matrix width."""
return (index % width, index // width)
def create_graph(board, width, player_node, target_node):
"""create a graph with adjacent cells."""
graph = networkx.DiGraph()
for cell_i, cell in enumerate(board):
if is_valid_cell(cell):
node = get_2d_pos(cell_i, width)
graph.add_node(node, pos=node, color=color_map[cell])
# check if we can go to an adjacent cell.
for dir_ in (width, -1, 1): # DOWN, LEFT, RIGHT (we are traversing the maze)
adj_cell_i = cell_i+dir_
# if we can go to the adjacent cell,
# create a bidirectional path between the current and the adjacent cell
if adj_cell_i >= 0 and adj_cell_i <= len(board): # check board boundaries.
adj_cell = board[adj_cell_i]
adj_node = get_2d_pos(adj_cell_i, width)
graph.add_node(adj_node, pos=adj_node, color=color_map[adj_cell])
if is_valid_cell(adj_cell):
graph.add_edge(node, adj_node)
graph.add_edge(adj_node, node)
else:
node = get_2d_pos(cell_i, width)
graph.add_node(node, pos=node, color=color_map[cell])
return graph
for level in levels:
board = level['board']
width = level['width']
# get player and target nodes.
player_node = get_2d_pos(board.index(PLAYER), width)
target_node = get_2d_pos(board.index(TARGET), width)
# convert the board to a directed graph.
graph = create_graph(board, width, player_node, target_node)
# get position and colors of each nodes.
pos = networkx.get_node_attributes(graph, 'pos')
colors = [x for x in networkx.get_node_attributes(graph, 'color').values()]
# create a new pyplot figure.
fig = plt.figure(figsize=(width // 2, (len(board) // width) // 2))
# draw the networkx graph on it.
networkx.draw(graph, with_labels=False, pos=pos, node_color=colors, node_shape='s', node_size=200, edge_color='yellow', arrows=False)
# visual settings.
fig.set_facecolor('black')
plt.gca().set_aspect('equal')
plt.gca().invert_yaxis()
# display the graph.
plt.draw()
And, here are the outputs:
Actual challenge solving
We now have an overview of the player’s moves and a graph representation of each level. To solve the challenge, we now have to find the shortest combination to reach the end of levels.
First try: dijkstra algorithm
In order to find the shortest path from start to end node, we can use the dijkstra algorithm:
# get the shortest path using dijkstra algorithm.
short_path = networkx.shortest_path(graph, player_node, target_node, method='dijkstra')
short_path_edges = list(zip(short_path, short_path[1:]))
# highlight the shortest path.
networkx.draw_networkx_edges(graph, edgelist=short_path_edges, pos=pos, edge_color='purple', width=10, arrows=False)
networkx.draw_networkx_nodes(graph, nodelist=short_path[1:-1], pos=pos, node_color='orange', edgecolors='purple', linewidths=1.5, node_shape='s')
# display the graph.
plt.draw()
Outputs:
Now, let’s convert these short paths into move combination:
import operator
UP, DOWN, LEFT, RIGHT = (8, 2, 4, 6)
def sub_tuple(a, b):
return tuple(map(operator.sub, a, b))
def convert_path_to_moves(path):
"""convert path to moves ("DIRECTION+STEPS" notation)."""
moves = []
current_pos = path[0]
for next_pos in path:
move = sub_tuple(next_pos, current_pos)
if move != (0, 0): # check if we're actually moving.
if move[0] == 0: # UP or DOWN
if move[1] > 0: # DOWN
dir_ = DOWN
elif move[1] < 0: # UP
dir_ = UP
steps = abs(move[1])
elif move[1] == 0: # LEFT or RIGHT
if move[0] > 0: # RIGHT
dir_ = RIGHT
elif move[0] < 0: # LEFT
dir_ = LEFT
steps = abs(move[0])
if len(moves) == 0 or moves[-1][0] != dir_: # player has not moved in this direction yet.
moves.append([dir_, 0])
next_move = (moves[-1][1] + steps)
for _ in range(next_move // 0xf): # we can't do more than 0xf steps in the same direction at a time.
moves[-1][1] = 0xf
moves.append([dir_, (next_move % 0xf)])
else:
moves[-1][1] = next_move
current_pos = next_pos
return moves
def get_printable_path(path):
buf = ''
moves = convert_path_to_moves(path)
for move in moves:
buf += f'{move[0]:x}{move[1]:x}'
return buf
print(get_printable_path(short_path))
Output:
612441
216a2262216121612d
214224448262824282
# ./debug 612441 216a2262216121612d 214224448262824282
[+] Loaded functions:
move: 0x7fb738d6b17e
play: 0x7fb738d6b2d8
[+] Level 1: (moves = 612441)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 o 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
[+] Level cleared!
[+] Level 2: (moves = ffffffffffffffff)
8 o 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 8
[+] Level 3: (moves = ffffffffffffffff)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 0 8 8 8 8
8 8 8 8 8 8 o 8 8 8 8 8 8 8 8
8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
Mmh, the moves combinations for levels 2 and 3 don’t fit into a 64-bit unsigned integer, there must be something wrong…
Second try: direct path
We made a mistake in the construction of the graph. In fact, even if the results are valid, they don’t represent the shortest program entries to get out of the maze, which is not what we want… In order to get the shortest program entries, we need to find the shortest path with the least change of direction.
At first, I thought of creating an edge-weighted graph and playing with the edge weights, but it adds a concept of dynamic weights based on our previous moves, making its implementation complex.
Then, I thought of the following assumption:
The player can slide and go up to 15 cells in a straight line with a single action.
We can therefore create a new graph that allows the player to make slides:
def create_alt_graph(board, width, player_node, target_node):
"""create a graph with accessible cells."""
graph = networkx.DiGraph()
for cell_i, cell in enumerate(board):
if is_valid_cell(cell):
node = get_2d_pos(cell_i, width)
graph.add_node(node, pos=node, color=color_map[cell])
# check if we can go to an adjacent cell.
for dir_ in (width, -1, 1): # DOWN, LEFT, RIGHT (we are traversing the maze)
for i in range(1, 0x10):
adj_cell_i = cell_i+(dir_*i)
# if we can go to the adjacent cell,
# create a bidirectional path between the current and the adjacent cell
if adj_cell_i >= 0 and adj_cell_i <= len(board): # check board boundaries.
adj_cell = board[adj_cell_i]
adj_node = get_2d_pos(adj_cell_i, width)
graph.add_node(adj_node, pos=adj_node, color=color_map[adj_cell])
if is_valid_cell(adj_cell):
graph.add_edge(node, adj_node)
graph.add_edge(adj_node, node)
else:
break
else:
node = get_2d_pos(cell_i, width)
graph.add_node(node, pos=node, color=color_map[cell])
return graph
Outputs:
Now, let’s try it:
# ./debug 612441 216a2242266629 81662462864c2242
[+] Loaded functions:
move: 0x7f69a24c517e
play: 0x7f69a24c52d8
[+] Level 1: (moves = 612441)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 o 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
[+] Level cleared!
[+] Level 2: (moves = 216a2242266629)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 o 8
[+] Level cleared!
[+] Level 3: (moves = 81662462864c2242)
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 o 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
[+] Level cleared!
All level has been solved using, I guess, the shortest solution. That should be enough to get the flag:
# ./chall 612441 216a2242266629 81662462864c2242
Congrats!
Here is your flag: DGA{612441_216a2242266629_81662462864c2242!}
Download links: solve.py, levels.py.
Flag
The final flag is: DGA{612441_216a2242266629_81662462864c2242!}
Happy Hacking!