[2018 X-MAS CTF] The ultimate Christmas game

 

시작하자마자 md5 Proof-Of-Work를 요구합니다. 확률은 $2^{-20}$이니 금방 찾아지겠네요. 코드를 아래와 같이 짜서 빠르게 구해봅시다.

import hashlib
def md5_pow(prefix):
  for i in range(100000000):
    if hashlib.md5(str(i).encode()).hexdigest().startswith(prefix):
      return str(i)

 

그 다음엔 NIM게임이 진행됨을 알 수 있습니다. NIM게임의 필승전략은 이 곳을 참고해주세요. 코드는 아래와 같습니다.

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)
###################################
print(md5_pow('22222'))
r = remote('199.247.6.180',14002)
msg = recv(r)
prefix = msg[msg.find('=')+1:msg.find('=')+6]
sendline(r,md5_pow(prefix))
while True:
  msg1 = recv(r)
  msg2 = recv(r)
  print("msg1 ", msg1)
  print("msg2 ", msg2)
  table = msg2[msg2.find('['):msg2.find(']')+1]
  l = eval(table)
  print(l)
  xor_all = 0
  for i in range(len(l)): xor_all ^= l[i]
  assert(xor_all != 0)
  query = (-1,-1)
  for i in range(len(l)):
    xor = xor_all ^ l[i]
    if l[i] >= xor:
      query = (i,l[i]-xor)
      break
    if query[0] != -1: break
  print("query : ",query)
#  msg3 = recv(r)
#  print("msg3 ", msg3)
  sendline(r,str(query[0]))
  msg4 = recv(r)
  print("msg4 ", msg4)
  sendline(r,str(query[1]))