Tuesday, June 5, 2012

Defcon 20 CTF qualifiers: urandom 300

On this challenge we need to connect to a service that will give us 100000 unsigned integers (uint16_t), and we need to send the required steps to sort this huge list. However, is not going to be an easy task, as there are 2 restrictions:
  1. You only have 10 seconds for reading the numbers, sorting them and sending back the answer to the server 
  2. The anser needs to be "optimal" (or close enough). "[...] If you correctly sort the array in sufficiently few moves I will give you a key!" 

You can solve the first restriction with a good server with good network connection. However, you won't get the answer if you don't meet the second requirement.

As speed is one of our concerns, our sorting algorithm will be Quicksort. It's fast, but... it'll take a huge amount of "swap moves" or "steps" to sort the numbers. It'll take around ~1M moves to sort a random array of 100000 elements, so we'll need to improve that (sending that amount of data might require a really fast internet connection, and for sure it won't be the optimal solution).

Thinking about the problem I realize that the "swaps" moves can be reduced. Imagine that you need to order a deck of cards. Basically you'll search the lowest card from left to right, moving it to the left (first position) once you've found it. Afterwards, you'll search the next-lowest card, and so on. This algorithm that most people use is called Insertion sort. Of course, that process is quite slow, but if you think about that, it can be optimal regarding the number of "swap moves".

The idea behind is that you will sort your deck in the usual way, but using a "cheat-sheet/oracle" that will tell you exactly which is the sorted position for each of your cards. In that case, you'll need only one "swap move" per card, using a maximum of N swap moves and it'll run very quickly.

Therefore, we'll use 2 lists: the first one will be the original (unordered) list. The next one will be the sorted one (using quicksort). Using the sorted list will allow us to get the optimal? number of "swaps moves".Here you go the quick and dirty algorithm:

  1. Grab the unsorted list of integers
  2. Sort them using Quicksort
  3. For each number in the sorted list:
  1. Get the number's position in the sorted list (Sth)
  2. Get the number's position in the unsorted list (Uth)
  3. Send to the server one "swap move", using the previous information (Uth:Sth)
  4. Update the unsorted list with the move that we have sent (that's because the same number might need to be used or moved more than once until it's been "ordered").


Implementing this solution solved only one part of the problem. Issues like bad coding practices, the 5 minutes cooldown and the overall speed of the Python/network code made it difficult to get the solution. In fact, the most difficult part was troubleshooting the apparently "flawless" code, as the server was rejecting any solution... In the end, I found out that it was a little/big endian issue :'(.

After fixing all the previous issues, and running again the script, we got the solution:
Congratulations, your final array is sorted correctly.

Here is your key: a7482ddfb82601fdc392b67836883dcc

I've added here the code that generates the "swap moves" from some sample "datadumps" that were obtained during the CTF. Be careful, as it's a really low quality code :(.

Finally, I'd like to say thanks to my team, as they give me a hand that allowed me to solve this challenge :).

No comments:

Post a Comment