# Problem

Didn’t save the original text but here are my words:

Imagine an infinite 2d grid. Start at (0, 0). Move one unit right, then turn left whenever possible so that you don’t intersect with your trail. I.e. make a counter clock wise spiral. The challenge input is the number of iterations, the solution is the coordinate where the point ends up.

For input=4, the solution is (-1, 1)

``````----------
------ |
|    | |
| .--- |
--------

``````

# Solution

It took a while for me to get what the challenge really was about. Instead of wasting time on trying to solve the problem, I did what a proper script kiddie does well - I used Google. I found a very good solution on stackoverflow that takes the number of iterations and returns the coordinates in O(1) time.

The challenge input is a huge number, sometimes over 1024 bits in length, so we need to support that.

I re-wrote the code in python, rotated the coordinates (since the spiral went clockwise in the code above) and adapted it to use `decimal` to get arbitrary precision. Then just hooked it up to the game server and got the flag.

``````import math
import decimal
from pwn import *
context.log_level = 0

_ctx = decimal.getcontext()
_ctx.prec=2**12

def floor(x):
with decimal.localcontext() as ctx:
#ctx.prec=100000000000000000
ctx.prec=1
ctx.rounding=decimal.ROUND_FLOOR
return x.to_integral_exact()

# http://stackoverflow.com/a/19287714/1747702
def spiral(n):
#given n an index in the squared spiral
#p the sum of point in inner square
#a the position on the current square
#n = p + a

_n = decimal.Decimal(n)

#r = math.floor((math.sqrt(n + 1) - 1) / 2) + 1
r = long(floor((decimal.Decimal(_n + 1).sqrt() - 1) / 2) + 1)

#compute radius : inverse arithmetic sum of 8+16+24+...=
p = (8 * r * (r - 1)) / 2
#compute total point on radius -1 : arithmetic sum of 8+16+24+...

en = r * 2
#points by face

a = (1 + n - p) % (r * 8)
#compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
#so square can connect

pos = [0, 0, r];
tmp = math.floor(a / (r * 2))
#find the face : 0 top, 1 right, 2, bottom, 3 left
if tmp == 0:
pos = a - r
pos = -r
elif tmp == 1:
pos = r
pos = (a % en) - r
elif tmp == 2:
pos = r - (a % en)
pos = r
elif tmp == 3:
pos = -r
pos = r - (a % en)

#print("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos)
newpos = [-pos, pos, r]
return newpos

#for i in xrange(25):
#    print i+1, spiral(i)

#print spiral(87617132336372079846506616471286455749443259655954533789357600981378524569118335678751536947646080176816437606601550323221987024289898039719680451033326652052129641143066615453270361535742146132971398209593358690841000867875335581644900086496061447470988285895603240925546341429765197561195418284611512072176183221118915681135559699902117689293065428013532910524117825539447351947261308698064828704511533056969797355257686729816425986743810441213016227815358114008621623753229561235048044)

p = process("openssl s_client -connect programming.pwn2win.party:9004", shell=True)

p.recvuntil("Verify return code: 0 (ok)\n---\n")

while True:
N=p.recvuntil("\n")
print "N=", N
ret = spiral(long(N) - 1)
p.sendline(str(ret) + " " + str(ret))

print p.recv()

#CTF-BR{iT-Was-JusT-BIgInteGeR-MFQnQRqKLcSHi}

``````