## 0x41414141 CTF: Misc: optimizer (400)

This is from the 0x41414141 CTF by pop_eax.

For this challenge, we are just given details for two server instances; one for US and one for EU.

Connecting via netcat, we are told that we will be given a number of problems and we have to solve them. It mentions that level 1 is tower of hanoi. A quick google search and I find more information about it. After some trial and error using different possibilities for the number of pegs.

This presentation was especially helpful in determining the formula (moves = 2n – 1) to get the number of moves: http://www.cs.uvm.edu/~rsnapp/teaching/cs32/lectures/hanoi.pdf

A manual check confirms the formula is correct, but the server responds with another problem.

There are four disks listed, so n=4. 24 – 1 = 15

We will need to automate this 🙂

``````import socket

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('45.134.3.200', 9660))

print('Server:', str(s.recv(1024)))
#print s.recv(1024)
while True:
data = s.recv(1024).strip()
if data:
count = 0
data = str(data)
print(data)
for i in data:
if i == ',':
count = count + 1
count = count + 1
n = pow(2, count) - 1
if '[' in data:
s.send(str(n))
print('Client: ', n)
s.close()``````

When I run this script, it iterates through quite a few problems, then the server reports that I’m in level 2: and have to give the number of inversions for the provided output.

A quick google search helps me figure out how to do this in python. https://www.geeksforgeeks.org/python-program-for-count-inversions-in-an-array-set-1-using-merge-sort/

I add some checks for the current level to help apply the appropriate process and then calculate the inversions:

``````import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('45.134.3.200', 9660))

def getInvCount(arr, n):

inv_count = 0
for i in range(n):
for j in range(i + 1, n):
if (arr[i] > arr[j]):
inv_count += 1

return inv_count
level = 1
print('Server:', str(s.recv(1024)))
while True:
data = s.recv(2048).strip()
if data == '':
break
if data:
if 'level 1' in data:
level = 1
print ('********************************** Level 1 **********************************')
if 'level 2' in data:
level = 2
print ('********************************** Level 2 **********************************')

if level == 1:

count = 0
data = str(data)
print str(data)
for i in data:
if i == ',':
count = count + 1
count = count + 1
n = pow(2, count) - 1
if '[' in data:
s.send(str(n))
#print('Client: ', n)

if level == 2:
print str(data)

if '[' in data:
sep = ']'
stripped = data.split(sep, 1)
arr1 = stripped.split(', ')
arr1 = map(lambda each:each.strip("["), arr1)
arr = arr1
arr = [int(numeric_string) for numeric_string in arr1]
n = len(arr)
inversioncount = getInvCount(arr,n)
s.send(str(inversioncount))
s.close()
``````

Here is a video of the script in action:

And the flag:

I really appreciate the challenge!