Tag: math

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 = 2ⁿ – 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. 2⁴ – 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)[0]
			    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!