ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

3DSCTF Write-up

The 318br, DESEC and SucuriHC Capture The Flag (3DSCTF) に Harekaze として参加しました. 最終的に4293pで27位(全体435チーム)でした.
うち, 僕は1問解いて459p取得しました.

Write-upです.


[PPC 459] Single Digit Problem
Description : Let's play!

ncで接続してみると問題に関する注意書きが表示されました.

 [+] For this game, you need to type an expression that the answer is the
     requested number.

 [+] Allowed symbols: ( + - * / )

 [+] Limit of 31 characters

 [+] Numbers need to be less than 100000

 [+] Type 'start' to start:

(n, m)が与えられて, m(のみ)と四則演算を駆使してnにしよう という問題でした. 例えば (3,2) であれば 2+2/2 です.
mは問題ごとにランダムで与えられ, nは1ずつ増えていきます.
m/mで1が作れるので, m+m+...+m/m+m/m+...で調節すればうまくいきそうです.

50問目あたりから厳しくなってきました.
f:id:ushiromiya3:20171216074958p:plain

この場合だと54は6*9なので (1+1+1+1+1+1)*(1+1+1+1+1+1+1+1+1) が最適解ですが, これだと31文字を超えるので怒られます.
もしかしてこれ運に頼るしかないのではと祈りながら回してたところ, Sigle Digit って書いてあるけど 11 を繋げて 11 にできるのではないか とふと気付きました.

(11, 1)が出るまで繰り返して検証してみたところ, 可能である事が判明しました.
11, 22, 33, 44, ..., が使えます.


solverです.
何問あるのか不明だったので, 不正解が出たらそれに対するifを追加~みたいな書き方をしたのでかなり汚くなりました(フラグが出ればいいんです).
最適化もしていないのでたまに失敗します(書き直してたらフラグ出ました).

from pwn import *

HOST = "sdp01.3dsctf.org"
PORT = 8003

r = remote(HOST, PORT)

def make_formula(n, m):
  ret = ""
  one = str(m) + "/" + str(m) + "+"

  double = int(str(m)*2)
  if n == double : return str(double)

#  if n > 50 and m == 1:
#    if abs((n/10)*11 - n) < abs(n - (n/10-1)*11):
#      pass
  while n >= double:
    ret += str(double) + "+"
    n = n - double

  if m*2 == n:
    return ret + str(m) + "+" + str(m)
  elif m**2 == n:
    return ret + str(m) + "*" + str(m)
  elif n == m:
    return ret + str(m)
  elif m == 1 and n > 12:
    offset = ""
    if gmpy.is_prime(n):
      n -= 1
      offset = "1+"
    p, q = n, n
    for i in xrange(1,n):
      if n % i == 0:
        if i + (n/i) < p + q:
          p, q = i, (n/i)
    r = "(" + ((str(1) + "+")*p).rstrip("+") + ")"
    l = "(" + ((str(1) + "+")*q).rstrip("+") + ")"
    return ret + offset + r + "*" + l
  elif m > 6 and n % m > 5 :
    rep_num = n/m + 1
    return ret + ((str(m) + "+")*rep_num).rstrip("+") + "-(" +((str(m)+"/"+str(m)+"+")*(rep_num*m-n )).rstrip("+")+")"
  elif m > 6 and n%m == m-1:
    rep_num = n/m + 1
    return ret + ((str(m) + "+")*rep_num).rstrip("+") + "-(" +str(m)+"/"+str(m)+")"

  pw = 0
  while n > 20 and m**(pw+1) < n:
    pw += 1
  if pw > 0:
    ret += ((str(m) + "*")*pw).rstrip("*") + "+"
    n = n - m**pw

  while n - m >= 0:
    n -= m
    ret += str(m) + "+"

  ret += one*n
  return ret.rstrip("+")

print(r.recv(1024))
r.sendline("start")
data = (r.recvuntil(": ")).split()
print(data)
n, m = data[8], data[-1][0]
print(n,m)
r.sendline(m+'/'+m)
r.recvuntil("Correct!")
while True:
  try:
    data = r.recvuntil(": ").split()
    #print(data)
    n, m = int(data[6]), int(data[11][0])
    print(n,m)
    payload = make_formula(n,m)
    print(payload)
    r.send(payload)
    print(r.recvuntil("Correct!"))

  except Exception as e:
    msg = r.recv(1024)
    if "3DS" in msg:
      print(msg)
      exit()
    else:
      r.close()
      r = remote(HOST, PORT)
      print(r.recv(1024))
      r.sendline("start")
      data = (r.recvuntil(": ")).split()
      print(data)
      n, m = data[8], data[-1][0]
      print(n,m)
      r.sendline(m+'/'+m)
      r.recvuntil("Correct!")

100問クリアでフラグが得られました.