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!

Crows know! Plan

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 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
            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(('', 13245))

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)

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])

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)$ python
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!