Hitcon CTF 2016 Quals - Writeup Beelzemon

Posted on Mon 10 October 2016 in writeups

PPC - 150 pts

Beelzemon gives you two integers 1 <= k <= n <= 20. It wants to know if you can split a set `{a | -(2**n) <= a <= (2**n) - 1} into two sets A, B s.t. |A| = |B| and sum({a**k | a in A}) = sum({b**k | b in B}). Give Beelzemon either A or B to save your life. (separate the numbers by space)

This problem is pretty easy to understand. We got this set : set and we need to split it in two part of same size in order to follow the rule rule

This partition problem is well known and we can find many solutions for positive sets (i.e all elements in the set are >= 0) Therefore we take the following algorithm and will change it a bit : :::python def find_partition(int_list): "returns: An attempt at a partition of int_list into two sets of equal sum" A = set() B = set() for n in sorted(int_list, reverse=True): if sum(A) < sum(B): A.add(n) else: B.add(n) return (A, B)

Here we are gonna make the split on modified sets, we elevate every element of the int_list to the power of k Then, to avoid the problem of non positive elements in this algorithm we add 2^n to every element in the int_list Due to the shape of the input set (being a range of integers without missing numbers in between), making equal size sets is pretty straightforward. We just need to put the last element (which will add 0 to the sum and therefore change nothing in our partition) to the partition having the less elements to make equal size partitions.

This problem takes a certain amount of time when (n,k) equals (16,16) but nothing impossible. My algorithm gets the flag in about 9 minutes. This is a lot, and yes a C++ implementation could be faster, but that's not too much here. (Edit : process is a lot faster now thanks to elbae. It takes about 10 seconds)

Here is the final code giving us the flag we want :

Pod for Team Fourchette Bombe
import socket
import re
import operator
import time

def find_partition(int_list,n,k):
    len_A=0; len_B=0; sum_A=0; sum_B=0
    Aret = ""; Bret = ""

    for i in range(0,len(int_list)):
        int_list[i] += 2**n
    for nb in int_list:
        if nb == 0:
            if len_A < len_B:
                Aret+= str(-2**n)+ " "
                Bret+= str(-2**n)+ " "
            if sum_A < sum_B:
               Aret+=str(nb-(2**n))+ " "
               Bret+=str(nb-(2**n))+ " "
    return (Aret)

def main():
    begin = time.time()
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('', 6666))
    while True:
        data = s.recv(2048)
        print "Received:", data
        if len(repr(data)) <=2 :
        mgex = re.search('([0-9]+) ([0-9]+)', repr(data))
        if mgex != None:
            n = long(mgex.group(1));
            k = long(mgex.group(2));
            mySet = range(-2**n,2**n);
            partition = find_partition(mySet,n,k)

    print "Connection closed."
    print "Process duration :", time.time() - begin


And this process gives us the flag : hitcon{8Ee121m0n kNow3 ev1l Num8e2}

EDIT : Thanks to elbae for his remark concerning time improvement. As I said, I did not search much for improvement as far as it was still reasonable. But with more cases to perform, this improvement could have been a must have to flag this challenge !