DEFCON CTF 2013 Quals “grandprix” Writeup

This time at DEFCON CTF quals there was a special task category, namely OMGACM or competitive programming. Here is a solution to OMGACM 3 task. We have a remote host that offers to play a race game:

Connected to grandprix.shallweplayaga.me.
Escape character is '^]'.
Use 'l' and 'r' to move. Don't crash.
Press return to start

OK, we send ‘\n’ to start and see a 5×8 track with different obstacles:

|-----|
| c  P|
|  P T|
|     |
|     |
|    T|
|  c  |
|     |
|     |
|  u  |
|-----|

u – is our “car” which should avoid:

T - tree
Z - zebra
r - rock
P - person
c - car

What we need is to send ‘l\n’ to turn left ‘r\n’ to turn right or just ‘\n’ to move straight. This is a pathfinding problem which can be solved using the A* (AStar) algorithm. I found a nice implementation in python here. The algorithm to solve this task is as follows:

  • parse track to get the position of the obstacles and of our car identified by x and y
  • construct a map, set corresponding nodes as blocked
  • try to launch pathfinding algo on every free node at the top the track until we find a path
  • finally subtract current position of the car from the first element of the computed path, if it is 1 we turn left, if -1 – right, otherwise we send ‘\n’.

After I got fully working solver, I faced a time limit problem, as only 2 minutes were given to get to the finish. However I overcame this problem when the code was launched from an Amazon EC2 instance. To get the key you needed to pass the track several times:
DEFCON CTF 2013 Quals OMGACM grandprix
Here is complete code of the solver: http://raz0r.name/grandprix.py


Posted

in

by

Tags:

Comments

2 responses to “DEFCON CTF 2013 Quals “grandprix” Writeup”

  1. jhlange Avatar
    jhlange

    A* was not required for this one. For each of the three possible moves I recursively checked if there exists a solvable path with an index of +/_ 1.

    As a small optimization on this, because in my manual run I noticed they occasionally sent two boards, I sorted the valid paths by the distance (straight ahead) to the closest object

  2. Raz0r Avatar

    @jhlange Nice!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.