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)

  1. ----------
  2.   ------ |
  3.   |    | |
  4.   | .--- |
  5.   --------

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.

  1. import math
  2. import decimal
  3. from pwn import *
  4. context.log_level = 0
  6. _ctx = decimal.getcontext()
  7. _ctx.prec=2**12
  9. def floor(x):
  10.     with decimal.localcontext() as ctx:
  11.         #ctx.prec=100000000000000000
  12.         ctx.prec=1
  13.         ctx.rounding=decimal.ROUND_FLOOR
  14.         return x.to_integral_exact()
  16. # http://stackoverflow.com/a/19287714/1747702
  17. def spiral(n):
  18.     #given n an index in the squared spiral
  19.     #p the sum of point in inner square
  20.     #a the position on the current square
  21.     #n = p + a
  23.     _n = decimal.Decimal(n)
  25.     #r = math.floor((math.sqrt(n + 1) - 1) / 2) + 1
  26.     r = long(floor((decimal.Decimal(_n + 1).sqrt() - 1) / 2) + 1)
  28.     #compute radius : inverse arithmetic sum of 8+16+24+...=
  29.     p = (8 * r * (r - 1)) / 2
  30.     #compute total point on radius -1 : arithmetic sum of 8+16+24+...
  32.     en = r * 2
  33.     #points by face
  35.     a = (1 + n - p) % (r * 8)
  36.     #compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
  37.     #so square can connect
  39.     pos = [0, 0, r];
  40.     tmp = math.floor(a / (r * 2))
  41.     #find the face : 0 top, 1 right, 2, bottom, 3 left
  42.     if tmp == 0:
  43.         pos[0] = a - r
  44.         pos[1] = -r
  45.     elif tmp == 1:
  46.         pos[0] = r
  47.         pos[1] = (a % en) - r
  48.     elif tmp == 2:
  49.         pos[0] = r - (a % en)
  50.         pos[1] = r
  51.     elif tmp == 3:
  52.         pos[0] = -r
  53.         pos[1] = r - (a % en)
  55.     #print("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos)
  56.     newpos = [-pos[1], pos[0], r]
  57.     return newpos
  59. #for i in xrange(25):
  60. #    print i+1, spiral(i)
  62. #print spiral(87617132336372079846506616471286455749443259655954533789357600981378524569118335678751536947646080176816437606601550323221987024289898039719680451033326652052129641143066615453270361535742146132971398209593358690841000867875335581644900086496061447470988285895603240925546341429765197561195418284611512072176183221118915681135559699902117689293065428013532910524117825539447351947261308698064828704511533056969797355257686729816425986743810441213016227815358114008621623753229561235048044)
  64. p = process("openssl s_client -connect programming.pwn2win.party:9004", shell=True)
  66. p.recvuntil("Verify return code: 0 (ok)\n---\n")
  68. while True:
  69.     N=p.recvuntil("\n")
  70.     print "N=", N
  71.     ret = spiral(long(N) - 1)
  72.     p.sendline(str(ret[0]) + " " + str(ret[1]))
  74. print p.recv()
  76. #CTF-BR{iT-Was-JusT-BIgInteGeR-MFQnQRqKLcSHi}