Unicorn CTF 2020 Task

writeup-2020-unictf-remote-control.py

#!/usr/bin/env python3
"""
Unicorn CTF 2020: Manager on remote work (misc, 999 pts)
Bruteforce solution without z3 or anything except math and force.
Most likely, not the intended solution, but it does work.

Requirements:
python >=3.8 for math.prod
sympy for multiset_permutations
"""
import math
import string

from sympy.utilities.iterables import multiset_permutations
from itertools import permutations

#
# Step 0:
# Prepare constants
# 
init_state = b"\x90\x9c\t\xc5\x9aP`5Ez\xf6\x98\xb7\xe5#\x9fR\x13\x9eJ\xd3\xf6'{\x19f;p\xb0\x85E\xeb\x9e\xbd\xc8\xfai\xf3\x9a@"

target_prod = 2760417597537019351700664712711713267399333595054080000000
target_length = 97
target_sum = 482

# Array containing list of sets of equal numbers.
# We're assuming they're distinct.
# Also, because target_prod divides by 7**16 and there is no fixed number repeated more than 13 times,
# we are assuming that one of those two unused numbers is 7. 
fixed_numbers = [
	[2,3,12,13,24,32,42,47,53,57,61,67,86],
	[16,44,48,54,77,79,93],
	[39,51,62,64,69,84,89],
	[0,7,11,19,29,41,46,58,66,80],
	[26,31,33,38,81,96],
	[5,17,55,56,74],
	[6,9,21,50,60,63,65,70,72,83,90,91,92],
	[14,18,34,43,59,68,87,88]
]

# Assuming that the first bytes are "unictf{"
flag_signature = b"unictf{"
first_bytes_signature = tuple(x ^ init_state[i] for i, x in enumerate(flag_signature))

#
# Step 1:
# Find possible fixed numbers
#

def brute_fixed_numbers(a,b,c,d,e,f,g,h,i,j):
	divisors = [ a**13, b**7, c**7, d**10, e**6, f**5, g**13, h**8]
	number_prod = int(math.prod(x for x in divisors if x))
	if target_prod % number_prod:
		return False
	number_sum = a*13 + b*7 + c*7 + d*10 + e*6 + f*5 + g*13 + h*8
	
	# i, j - that 28 numbers
	ij_sum = target_sum - number_sum
	ij_prod = target_prod // number_prod
	ij_cnt = 28

	if ij_sum < 0:
		return False

	# Check if any possible free numbers combination exists
	for x in range(15):
		x1 = 28 - x
		if i**x * j**x1 * number_prod != target_prod:
			continue
		if i*x + j*x1 != ij_sum:
			continue
		return True

all_except_7 = set(range(10)) - set([7])
fixed_numbers_possible = tuple(x for x in permutations(all_except_7) if brute_fixed_numbers(*x, 7))
print("[+] Step 1 is done")
print("[!] Possible free number combinations are: \n\t - " + '\n\t - '.join(list(str(combination) for combination in fixed_numbers_possible)))


fixed_numbers_possible = fixed_numbers_possible[5:]
print("[!] Skipping 5 wrong combinations right to the {}".format(str(fixed_numbers_possible[0])))

#
# Step 2:
# Find free number positions
#

nonfree = set(sum(fixed_numbers, []))
free = sorted(list(set(range(target_length)) - nonfree))
def construct(nf,f):
	"""
	Construct a number given fixed and free numbers lists
	"""
	
	number = list(range(target_length))
	for i, elist in enumerate(fixed_numbers):
		for idx in elist:
			number[idx] = nf[i]
	for i, y in enumerate(f):
		number[free[i]] = y
	return sum(y * 10**i for i,y in enumerate(reversed(number)))

def nth_byte(x, n):
	"""
	Get nth byte of the number (LE)
	"""
	return (x % int(256**(n+1)) // int(256**n))

def check(number):
	"""
	Check if number looks like our flag
	"""

	# Check first bytes
	for i, b in enumerate(first_bytes_signature):
		if nth_byte(number, i) != b:
			return False
	
	# Check if the rest bytes are ascii-printable
	number_bytes = number.to_bytes(300, byteorder='little')[:40]
	possible_flag = "".join([chr(number_bytes[i] ^ init_state[i]) for i in range(40)])
	for x in possible_flag:
		if x not in string.printable:
			return False
	print("[+] Solved! Flag is: {}".format(possible_flag))
	return True

for x in fixed_numbers_possible:
	print('[*] Checking current fixed_numbers combination (should take about 20 minutes): {}'.format(str(x)))
	
	seven_repeats = 16 								# x divides by 7**16
	unknown_repeats = len(free) - seven_repeats 	# there are only 248 unknown digits
	for p in multiset_permutations((x[8],)*unknown_repeats + (7,)*seven_repeats): 
		number = construct(x[:8], p)
		if check(number):
			print('[+] Bruteforce is a force')
			exit(0)