[ASISCTF QUAL 2017] Crows knows

ASIS is my favorite CTF, and my solution is a roller coaster.

Crows knows

Let’s start with this exciting challenge:

[+] Opening connection to 146.185.143.84 on port 13245: Done
**************************************************************
| Welcome to the Crow Impossible Task, crow knows the flag!! |
| Your mission is to find x, y such that x**6 + a * y**6 = b |
**************************************************************
Submit a printable string X, such that sha256(X)[-6:] =
'ba97f1'
2a1de5f80b3fd1b8a27e9c6cb15561e18b52ff8932206584919e601f4eba97f1
'axhw1'
[*] Switching to interactive mode
Please be patient ...
It takes a few seconds to load ...
a = 185896826602197681258604375323805663807947318745711427301362205160412166144960050911038400420988766704323406572826758016739206238707350
b = 13524448223630158017715492041334126463569268401117801348864959294793842965451824342277374244918855909387055183278807172982958268982129521187401292042264364670383039149161599701339927970744819404040062511495364765749689513796094553348050562134398461025490690197229927877193040700448738384649726251788857890242334159094024841683406939302952583244697400514245824055128561105099717744866054052137008182484840037154502878092061221143411710904322916425837847844997186813004211316225851423580231207968670673223811355304567966677718575677348552093054309642512145389193732072618256845044334368163185637926327201803224944506049394338418010020238707291740954158969191802412107123283576836241685794748383307518396757091403448246352071909268824755300401248171630692002863045534896012592495125175943161187876350068285757212443807566660208422742228455522882308082258840078918884206239703521938339895707254422503840056528176308206780050804320108174672419561
To win the flag, submit x and y :)

Intially, please keep in mind that this challenge was solved by my teammates, and they solved it in unintended way.

Therefore, I know the flag is, ASIS{Cornacchia_Is_an_AlgOri7hm_f0r_Solvin9_7h1s_ta5k!!}, this writeup is to perfect their solution.

Okay, so we are going to use Cornacchia’s algorithm to find the solution. I searched around to find the right library, speed up the running time and to find out the solution.

In case you’re too lazy to leave this page and read the wiki, here is a short brief:

How to solve x6 + d*y6 = m

  • Find r0, where r06 + d == 0 (mod m)

  • Find r1, where r1 == m (mod r0)

  • Find r2, where r2 == r0 (mod r1)

  • Find r3, where r3 == r1 (mod r2)

…​

So the expensive equation here is to solve r0. I dig in sympy, gmpy2, and find these functions is incapable of solving a CTF challenge. I prefer both SageMath and sympy, while in gmpy2, I have to implement algorithm from scratch.

Well, so jump on SageMath. Below code I point out which is a better way to solve r0 in Sage.

# Init variable
sage: a
510942438571185504862146581900640555500640477572981771980548460875885071908088741675995364754603088174599114716216851570247868015178202L
sage: b
18092284968119422460156775405666280307969700344487991732933071083138446730919724496456526764248760304245414461697126686479770756899253092163909365638724080157145360061139268023569125981467789207958610499534861163360741307129160240154203232637740110506368573357927961590039805828198155930009807016292278810693596209185246119309655888945767205675128682530936485720219719703977385722572140080519594492037622170571901870930980509686713561754082628164041420347958235990666527868256828147192595311170671285046830765792973588084287471416381669923125180934009450357226148535544661734836175623492729708936501533592443027569651111746291110855582965667265767520753664893992874707896141124866778884596810780145880551123750585520941915324536811155545670131722721748889493721106837097917062037440640382052872836385429757144018676593113795848197393136851334333874276510036428449545250100931267394327068621466245939226483205591262737267854504071117703552571L

sage: solve_mod(x^6 + a == 0, b)

Traceback (most recent call last):
  File "crow.sage.py", line 11, in <module>
    r0 = solve_mod(x**_sage_const_2  + d == _sage_const_0 , m)
  File "/usr/lib/sagemath/local/lib/python2.7/site-packages/sage/symbolic/relation.py", line 1008, in solve_mod
    solution =_solve_mod_prime_power(eqns, p, i, vars)
  File "/usr/lib/sagemath/local/lib/python2.7/site-packages/sage/symbolic/relation.py", line 1111, in _solve_mod_prime_power
    possibles = cartesian_product_iterator([xrange(len(R)) for _ in xrange(len(vars))])
  File "sage/rings/ring.pyx", line 211, in sage.rings.ring.Ring.__len__ (/usr/lib/sagemath//src/build/cythonized/sage/rings/ring.c:3308)
OverflowError: long int too large to convert to int

After a few minutes with solve_mod, it crashes.

Try another way, with Integer builtin type in Sage:

sage: a = Integer(a)
sage: b = Integer(b)
sage: time Mod(-a,b).nth_root(6)

https://www.youtube.com/watch?v=8BvV9arABLs

or just use naked long type

sage: time Mod(-a,b).sqrt()

https://www.youtube.com/watch?v=yL0RzgUpGjk

Quicker than the previous one 1s. Although it’s still too long. But Mod().nth_root() is the best method I can find at the moment.

So plug-in, write a whole Sage code:

Cornacchia.sage
#!/usr/bin/env sage

f = open('log').read()
exec(f)
# I know, it's bad, but I verified the variable before exec, calm down
d = a
m = b

r0 = Mod(-d, b).nth_root(6)
r0 = Integer(r0)

rlist = [m, r0]

for i in range(1,4096):
	r_i = rlist[i-1] % rlist[i]
    if (m - r_i^6) % d == 0:
    	# Integer number inside square
        s = (m - r_i^6) // d
        if s.is_power_of(6):
        	x = r_i
            y = s.nth_root(6)
            break
    rlist.append(r_i)

And you wonder, why the hell I don’t write a connecting script inside Sage? Nope. I won’t do that, I won’t bring more complicated things to my life.

Here is the connecting script:

connect.py
#!/usr/bin/env python
from pwn import *

host, port = '146.185.143.84', 13245

r = remote(host,port)

print r.readuntil('sha256(X)[-6:] = ')

h = r.readline().strip()

def brute(end):
	while True:
		h = ''.join(random.sample(string.printable, 5))
		if sha256sumhex(h).endswith(end):
			print sha256sumhex(h)
			return h

print repr(h)

res = brute(h)

print repr(res)

r.writeline(res)

print r.readuntil('load ...\n')

a = r.readline()
print a
b = r.readline()
print b

print r.readuntil(':)\n')

f = open('log','w')
f.write(a)
f.write(b)
f.close()

r.interactive()

In interactive mode, I will manually paste x and y.

Experiment result

Time out

Conclusion

To conclude, here is the perfect solution, the lesson for this article is: Sage is very very slow

while :; do python PerfectSolution.py; done;

almostPerfectSolution.py
from sympy import *
from pwn import *
import signal

signal.alarm(300)

exec(a)
exec(b)

d = a
m = b

r0 = nthroot_mod(-a, 6, b)

rlist = [b, r0]

def solve(rlist):
	low_bound = int(root(m, 6))
	for i in range(1,4096):
		r_i = rlist[i-1] % rlist[i]

		#print r_i
		if (m - r_i**6) % d == 0:
			print 'in'
			# Integer number inside square
			s = (m - r_i**6) // d
			s = root(s,6)
			print 'FOUND', '='*20
			x = r_i
			y = s

			return x,y

		if r_i < low_bound:
			return
		rlist.append(r_i)

# Start with r0
x,y = solve(rlist)

print '{} {}'.format(x,y)

assert x**6 + a*y**6 == b

r.writeline('{} {}'.format(x,y))

Update

After examining the result, I can calculate cube root directly on result so I don’t have to run 6th-root like the code above.

And solution produce in one run.

perfectsolution.py
from sympy import *
from pwn import *
import signal
from sympy.solvers.diophantine import cornacchia

signal.alarm(300)

host, port = '146.185.143.84', 13245

r = remote(host,port)

print r.readuntil('sha256(X)[-6:] = ')

h = r.readline().strip()

def brute(end):
	while True:
		h = ''.join(random.sample(string.printable, 8))
		if sha256sumhex(h).endswith(end):
			print sha256sumhex(h)
			return h

res = brute(h)

r.writeline(res)

print r.readuntil('load ...\n')

a = r.readline()
print a
b = r.readline()
print b

print r.readuntil(':)\n')

exec(a)
exec(b)

result = list(cornacchia(1,a,b))
x,y = result[0][0], result[0][1]
x = root(x,3)
y = root(y,3)

print '{} {}'.format(x,y)

assert x**6 + a*y**6 == b

r.writeline('{} {}'.format(x,y))

r.interactive()
log
[+] Opening connection to 146.185.143.84 on port 13245: Done
**************************************************************
| Welcome to the Crow Impossible Task, crow knows the flag!! |
| Your mission is to find x, y such that x**6 + a * y**6 = b |
**************************************************************
Submit a printable string X, such that sha256(X)[-6:] =
'e28a6b'
c238f39947158e0ed708e2d20afa0cf5e9ccf48472d49b2973a49ea684e28a6b
'wxnkRoYe'
Please be patient ...
It takes a few seconds to load ...

a = 532989999066309503913017789396479145841922198531504447834341671190756697418728847154657676161181498433098401388345786995127967423230271

b = 74990050564399456620718691939281988658004527544836525834216727773265241250449452353603562659510803802909872294189645411512595258690968349050777077073082122984897798048329519514872492921107666431386984002980785852957926875308226868502009839291339995604753984721621330213308600807144015326261562338660744273098483260496348011172639860014416836683623158022869246093397350100092108013820303548386519355317818579328707631639713524337265878652681924704458613028590960965498308565664342779404644810568383655734052371837040900749603766585773930302863610059737240283293466018555439381506766991031314158349894413255128356719503982064882617379175363794267458795831665595137202840491654681470323942061348038171752980221513228713821758241847310512734285297041824291737193584923358839545333267219017843807657589766023045554560282956194654113293340209611262852946139551107428152269359446080391046592633874672962895444010003987064007837858069282559817

To win the flag, submit x and y :)

in
FOUND ====================
168656307159894287414924807702898749637303563848040577577007009739949158456335928874336431632444477397973141358340665667935580302750949 22805911309989043909051045463294133642554612155421806829268352452088464355031812346771132442550025116356487102504025454173032796537996
[*] Switching to interactive mode
$
$
Congratz! :) ASIS{Cornacchia_Is_an_AlgOri7hm_f0r_Solvin9_7h1s_ta5k!!}
[*] Got EOF while reading in interactive
$

Thanks to ASIS for this challenge. And thank you for your time. :))