ASIS CTF 2017 Quals - Crows know! writeup
This time, the task is very simple: after completing an obligatory proof of work (a basic SHA256 bruteforce) and waiting a couple seconds we are presented with a couple of pretty big integers, a and b. So what’s the mission?
Your mission is to find x, y such that x**6 + a * y**6 = b
Okay. Do we have a plan?
Why of course we do!
So let’s get our hands dirty and dive into some sympy docs! The function we need can be found rather easily, and that other thing, the true cube root algorithm, we can nick from the good people over at StackOverflow.
Here’s the code then!
import socket
import hashlib
import itertools
import string
from mpmath import cbrt, im
from sympy.abc import x, y
from sympy.solvers.diophantine import diop_quadratic
def true_cbrt(n):
lo = 0
hi = n
while lo < hi:
mid = (lo+hi)//2
if mid**3 < n:
lo = mid+1
else:
hi = mid
return lo
def recvuntil(s, stop):
data = ""
data += s.recv(1)
while not data.endswith(stop):
data += s.recv(1)
return data
s = socket.socket()
s.connect(('146.185.143.84', 13245))
recvuntil(s,"Submit")
pow_target = s.recv(1024)[-7:-1]
# proof of work
pow = ""
for word in itertools.product(string.printable, repeat=5):
if hashlib.sha256(''.join(word)).hexdigest()[-6:] == pow_target:
pow = ''.join(word)
break
s.send(pow + '\n')
data = recvuntil(s, ':)')
print data
answer = data.split("\n")
a = int(answer[2].split(' ')[-1])
b = int(answer[3].split(' ')[-1])
solutions = diop_quadratic(x**2 + a*(y**2) - b)
for sol in solutions:
if im(cbrt(sol[0])) == 0 and im(cbrt(sol[1])) == 0:
out_x = true_cbrt(sol[0])
out_y = true_cbrt(sol[1])
break
s.send("%d %d\n" % (out_x, out_y))
print s.recv(1024)
print s.recv(1024)
Let’s run it and wait a bit…
(ctf) tr@karabut.com:~/work/asisquals17$ python crows.py
Please be patient ...
It takes a few seconds to load ...
a = 30741415699351712223222592216948664852787225938672761888182663459401433940293299920472821794247792558438137266179003170954852009167996
b = 5493768938913164268735898548345740984062864198582915532893452862692397723477349340213609803716310002722689784104429402408034399680657214203589114662020419403506380275921075865806868813167390548527002018378296772011002830464813992537445273710373363121247809539380530302504021135339366740636410963119289644130568327436166142653219502858785723203265988729334812946807271940413511096470449043813939925759131485224930805050595388961884769573807597931344321170355620526497042548348665782820474459300583235597864519400688289208986957832681459966933968204573143630154199268824952951642924625108969237666308633980889261559554117298872683137210357137988177192697560524562835477922442010038014370796719316949327823897102946508453004777622812045656957796013010907193455701053005247975317200627083352360327185314875288693488759973999715297338413318230762734322668133288476183336301663326505090120348966948964517423252467946014780068274519231694498484297
To win the flag, submit x and y :)
Congratz! :) ASIS{Cornacchia_Is_an_AlgOri7hm_f0r_Solvin9_7h1s_ta5k!!}
Math is neat!
I almost missed the CTF, only getting my hands on it in the last hours, and didn’t have that much time to play – so naturally I tried my luck with one of the unsolved (at the moment) challenges. Crows know! turned out to be surprisingly not difficult – I guess it’s just that nobody cares for PPC :) The only other challenge I touched was Tatter, but I managed to get only a quarter of the flag before the game ended. If I get some time to spend on getting the code working in full, it would make for a great writeup though!