[2018 X-MAS CTF] A Christmas Dilemma

 

또 MD5 POW를 요구합니다. 이전 문제에서 쓴 코드를 그대로 활용하면 됩니다.

 

 

500번 쿼리 이내로 주어진 정의역 안의 global max를 구하라고 하네요. 만약 이 함수가 연속함수가 아니라면 절대 풀 수 없는 문제이니 연속함수일 것이라고 가정했습니다. 그러고나면 일단 주어진 정의역 구간을 420등분해 각 지점의 값을 구해서 최댓값을 나타내는 지점을 찾습니다. 이제 해당 지점 주변에서 0.01 단위로 이동하며 값을 더 개선시킵니다. 이 풀이가 언제나 정확한 값을 주는 것은 아니지만, 대충 2-3번에 1번 꼴로는 정답이 나오더군요.

 

from Crypto.Util.number import *
import binascii,socket,sys
import hashlib

def gcd(a, b):
  if a == 0: return b
  return gcd(b%a, a)

def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  g, y, x = egcd(b%a,a)
  return (g, x - (b//a) * y, y)

def inv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m

# x**2 = a (mod m), m is prime
def quad_congruence_equation(a, m):
  assert((m+1)%4 == 0)
  return pow(a, (m+1)//4, m)
# m must satisfies pairwise relatively prime
def crt(a, m):
  n = len(m)
  ret = a[0]
  mod = m[0]
  for i in range(1,n):
    m1 = mod
    mod *= m[i]
    m2inv = inv(m[i],m1)
    m1inv = inv(m1,m[i])
    ret = (ret*m[i]*m2inv+a[i]*m1*m1inv)%mod
  return ret

# 0x6161 -> 'AA'
def i2s(x):
  return long_to_bytes(x).decode("utf-8")

############ my socket ###############
def interactive(socket):
  print("[+] interactive mode")
  while True:
    rr = socket.recv(2**16).decode()
    if not rr:
      print("[!] socket closed")
      return None
    print(rr)
    socket.send((input('> ')+'\n').encode())

def remote(ip, port):
  sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  print("[+] Connecting to {}:{}".format(ip,port))
  sock.connect((ip,port))
  print("[+] Done!")
  return sock

def sendline(socket, msg):
  if type(msg) == str: msg = msg.encode()
  if msg[-1] != b'\n': msg += b'\n'
  socket.send(msg)

def recv(socket):
  return socket.recv(2**16).decode()

def md5_pow(prefix):
  for i in range(100000000):
    if hashlib.md5(str(i).encode()).hexdigest().startswith(prefix):
      return str(i)
###################################
r = remote('199.247.6.180',14001)
powmsg1 = recv(r)
print('powmsg1', powmsg1)
prefix = powmsg1[powmsg1.find('=')+1:powmsg1.find('=')+6]
sendline(r,md5_pow(prefix))
intro1 = recv(r)
#print('intro1', intro1) Ok, you can continue @@@
intro2 = recv(r)
domain = eval(intro2[intro2.find('('):intro2.find(')')+1])
print("domain : ", domain)
query1num = 420
chunk = (domain[1]-domain[0])/(query1num-1)
localmx = -10000000
localidx = -1
val = [0.0]*425
for i in range(query1num):  
  sendline(r,'1')
  msg1 = recv(r) 
#  print("msg1", msg1)
  sendline(r, str(domain[0]+chunk*i))
  msg2 = recv(r)
#  print("msg2", msg2) 
  try:
    msg2 = msg2[msg2.find('=')+2:]
  #  print(msg2)
    val[i] = float(msg2[:msg2.find('\n')])
    if val[i] > localmx:
      localidx, localmx = i, val[i]
  except:
    print("error on parse ", msg2)
  #print(i,domain[0]+chunk*i,val[i])
  if i % 10 == 9: print("{}/{}...".format(i+1,query1num))
#  print("{}/{}...".format(i+1,query1num))
  msg3 = recv(r)
#  print("msg3", msg3)

print(localidx, localmx)
query2num = 499-query1num
cand_domain = domain[0]+chunk*localidx - 0.01*(query2num/2)
for i in range(query2num):
  sendline(r,'1')
  msg1 = recv(r) 
#  print("msg1", msg1)
  sendline(r, str(cand_domain + 0.01*i))
  msg2 = recv(r)
  try:
    msg2 = msg2[msg2.find('=')+2:]
    vv = float(msg2[:msg2.find('\n')])
    print("{}th guess : ".format(i+1), cand_domain + 0.01*i, vv)
  except:
    print("error on parse ", msg2)
  localmx = max(localmx,vv)
  msg3 = recv(r)
#  print(msg3)

sendline(r,'2')
msg1 = recv(r) 
print("guess ",localmx)
sendline(r,str(localmx))
print(recv(r))
print(recv(r))
print(recv(r))