[2019 X-MAS CTF] Hashed Presents

server.py

from hash import secureHash
import SocketServer
import string
import random
from text import *
import os
from hashlib import sha256

PORT = 2000
ROUNDS = 10
TIMEOUT = 120
sigma = string.ascii_letters+string.digits+'!@#$%^&*()-_=+[{]}<>.,?;:'

def isPrintable(x):
    global sigma

    alpha = set(sigma)
    beta = set(x)

    return alpha.intersection(beta) == beta    

def get_random_string(l, s):
    return ''.join([random.choice(s) for i in range(l)])

class ThreadedTCPRequestHandler(SocketServer.BaseRequestHandler):
    def PoW(self):
        s = os.urandom(10)
        h = sha256(s).hexdigest()
        self.request.sendall("Provide a hex string X such that sha256(X)[-6:] = {}\n".format(h[-6:]))
        inp = self.request.recv(2048).strip().lower()
        is_hex = 1
        for c in inp:
            if not c in '0123456789abcdef':
                is_hex = 0

        if is_hex and sha256(inp.decode('hex')).hexdigest()[-6:] == h[-6:]:
            self.request.sendall('Good, you can continue!\n')
            return True
        else:
            self.request.sendall('Oops, your string didn\'t respect the criterion.\n')
            return False

    def challenge(self, n):
        s = get_random_string(random.randint(30,35), sigma)
        H = secureHash()
        H.update(s)
        h = H.hexdigest()

        self.request.sendall(chall_intro.format(n, s, h))
        inp = self.request.recv(2048).strip()
        H_inp = secureHash()
        H_inp.update(inp)
        h_inp = H_inp.hexdigest()

        if(inp == s or not isPrintable(inp)):
            self.request.sendall(chall_wrong)
            return False    

        if(h_inp != h):
            self.request.sendall(chall_wrong)
            return False    

        self.request.sendall(chall_ok)
        return True

    def handle(self):
        self.request.settimeout(TIMEOUT)
        if not self.PoW():
            return
        self.request.sendall(intro.format(ROUNDS))

        for i in range(ROUNDS):
            if(not self.challenge(i+1)):
                self.request.sendall(losing_outro)
                return    

        self.request.sendall(winning_outro.format(FLAG))

        def finish(self):
            logger.info("%s client disconnected" % self.client_address[0])


class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass

if __name__ == '__main__':
    server = ThreadedTCPServer(('0.0.0.0', PORT), ThreadedTCPRequestHandler)
    server.allow_reuse_address = True
    server.serve_forever()

hash.py

class secureHash(object):
    def __init__(self):
        self.bits = 128
        self.mod = 2**128
        self.mask = 2**128 - 1
        self.step = 23643483844282862943960719738L
        self.hash = 9144491976215488621715609182563L

    def update(self, inp):
        for ch in inp:
            self.hash = ((self.hash + ord(ch)) * self.step) & self.mask

    def hexdigest(self):
        x = self.hash
        out = ''
        for i in range(self.bits/8):
            out=hex(x & 0xff)[2:].replace('L','').zfill(2)+out
            x >>= 8
        return out

 

Provided hash is a rabin-karp hash. To capture a flag, we must find a second preimage. Rabin-karp hash is not that secure, and I have read a post about collision in rabin-karp. (Post) However, the method provides in that post is not that fit on this situation.

 

After more googling, I find a similar problem - TWCTF 2017 Palindrome Pairs. According to Solution, LLL algorithm can be used to find a collision.

 

Although I am not that familiar with LLL algorithm, just copy & paste & modified.

 

collision-poly.sage

p = 23643483844282862943960719738
mod = pow(2,128)

N = 22 ## 22 to 34, to increase a success probability
print N

def sparse_poly():
    L_rows = []
    B = 100000

    for i in xrange(N):
        row = [1 if j==i else 0 for j in xrange(N)] + [B*Integer(pow(p,N+1-i,mod))]
        L_rows.append(row)

    L_matrix = Matrix(L_rows)
    print 'Built matrix'
    print type(L_matrix)
    L_redux = L_matrix.LLL()
    sparse = L_redux[0]
    print sparse[:-1]
    poly, vals = sparse[:N], sparse[N:]

    assert all(abs(x) <=70 for x in poly)
    assert all(x == 0 for x in vals)

    return poly

def build_strings(poly):
    a = [0 for _ in xrange(N)]
    b = [0 for _ in xrange(N)]

    # a[i] - b[(N-1)-i] = poly[i]

    for i in xrange(N):
        if poly[i] >= 0:
            a[i] = poly[i]
            b[i] = 0
        else:
            a[i] = 0
            b[i] = -poly[i]

    a_str = ''.join(chr(ord('a')+v) for v in a)
    b_str = ''.join(chr(ord('a')+v) for v in b)
    return a_str, b_str

def solve():
    poly = sparse_poly()
    #s1, s2 = build_strings(poly)
    #print s1, s2

solve()

(Modified form Here)

 

Let me explain more: polynomial is (6, -18, -3, -2, -31, -1, 4, -10, -31, 11, -33, 3, 16, 37, -29, 11, 13, -18, -1, 26, -31, 6) when N = 22.

 

It means if $a[0]-b[0] = 6$, $a[1]-b[1] = -18$, ... , $a[21]-b[21] = 6$ than $a$ and $b$ has same hash.

 

Is is little annoying that there is limit of character. So probability is not 100%. But you can capture a flag at most 5~10 min.

 

solver.py

from hashlib import sha256
from Crypto.Util.number import *
import string

import socket



############ 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()





mod = 2**128
p = 23643483844282862943960719738
v = 9144491976215488621715609182563

s = 'abc'
sigma = string.ascii_letters+string.digits+'!@#$%^&*()-_=+[{]}<>.,?;:'
def hash(s):
  h = v
  for ch in s:
    h = (h+ord(ch))*p % mod
  return hex(h)[2:]


s = dict()
def PoW(query):
  i = 0
  while True:
    if i % 1000000 == 0:
      if input() == "quit":
        return None
    i += 1
    h = sha256(str(i).encode()).hexdigest()

    if h[-6:] == query:
      return str(i).encode().hex()

poly22 = (6, -18, -3, -2, -31, -1, 4, -10, -31, 11, -33, 3, 16, 37, -29, 11, 13, -18, -1, 26, -31, 6)
poly23 = (21, 15, 5, -1, 2, -24, 10, -11, -11, -22, -9, -11, -10, -16, -9, -54, -11, -7, 4, 15, 5, 8, 4)
poly24 = (-4, -3, -2, -1, -14, 0, 23, -9, 7, 21, 2, -13, -6, -5, 10, 9, -11, -8, 20, -3, 1, -32, -1, 2)
poly25 = (-3, -9, -7, 16, 3, 0, -6, -17, 0, -8, -8, 24, -3, -8, 23, 3, 5, -10, -7, 15, -9, 0, -11, -1, -10)
poly26 = (-14, -7, 11, 1, 1, 8, -13, 5, -12, 16, 10, 1, 7, -7, -3, -7, 4, -6, -1, -6, -1, 2, -8, 2, -1, -14)
poly27 = (2, -3, -7, 5, 3, 12, -13, 1, -13, -8, 13, 8, -8, -9, 0, 2, 13, 1, -3, -1, -11, -3, 6, 7, -8, 8, -8)
poly28 = (-6, 5, 4, 4, 3, -5, -8, -8, -6, -5, 3, -17, 8, 8, 5, -3, -6, 5, -6, -9, 11, 14, 10, 3, 6, 1, 1, 2)
poly29 = (14, 2, -1, -2, -16, 8, 6, 3, -1, -2, -9, -3, -3, 2, -10, -2, 11, -3, -1, 1, -7, 9, 7, 5, 0, 14, -3, 6, 0)
poly30 = (-7, -8, 5, -5, 3, 4, 6, -2, 0, 3, -15, -1, 14, 5, 3, -8, -3, -1, 6, -6, 1, -8, 0, -5, -5, 12, -7, 2, 3, 2)
poly31 = (-6, -13, -5, 10, 1, -3, 2, 4, -6, 1, -6, 3, -2, -5, 9, 4, -2, -14, -2, 1, 0, -3, 0, -2, 4, -1, 3, 4, -5, -1, -2)
poly32 = (-2, -4, 10, -3, 0, 1, 2, -5, -5, 5, -4, 1, 7, 1, 10, -6, 2, 0, -5, 4, 3, 0, -5, 1, -1, 4, 8, -5, 4, 2, 4, 0)
poly33 = (4, -4, -2, 1, 4, -8, -1, 8, -5, 2, 4, 1, 4, -1, 3, -5, -5, 0, -4, 0, -14, 2, 4, 9, 0, -9, -8, 7, -3, 2, 0, 0, 0)
poly34 = (-7, 1, -3, -5, -4, -5, 3, 3, 4, 3, -1, -9, 2, 4, 2, 3, 1, 2, 1, -3, 2, 3, 2, 0, 5, 0, -1, -1, -2, -9, -1, 2, 3, 2)


def collision(s):
  h = hash(s)
  n = len(s)
  polycount = 21
  for poly in [poly22, poly23, poly24, poly25, poly26, poly27, poly28, poly29, poly30, poly31, poly32, poly33, poly34]:
    polycount+=1
    if len(poly) > n: continue
    for factor in range(1,10):
      for st in range(n-len(poly)+1):
        L = list(s)
        ret = ''
        ret += s[:st]
        pos = True
        for i in range(st,st+len(poly)):
          ii = ord(s[i])+factor*poly[i-st]
          if ii < 0 or chr(ii) not in sigma:
            pos = False
            break
          ret += chr(ii)        
        if not pos: continue        
        ret += s[st+len(poly):]
        if hash(ret) == h:
          return ret
  return "FAIL"




s = dict()
for i in range(10000000):
  if i%1000000==0: print(i)
  h = sha256(str(i).encode()).hexdigest()
  s[h[-6:]] = str(i).encode().hex()



while True:
  r = remote('challs.xmas.htsp.ro', 10003)
  pow_target = recv(r).strip()[-6:]
  print(pow_target)
  if not pow_target in s: continue
  sendline(r, s[pow_target])
  x = recv(r) # Good, you can continue
  pos = True
  for step in range(10):
    if step != 0:
      recv(r) # Nice one, keep going!
    print ("step ", step)
    x = recv(r).strip()
    print("received : ",x)
    string = x[x.find("string")+8:]
    string = string[:string.find("and")-1]
    print(string)
    ans = collision(string)
    if ans == "FAIL":
      pos = False
      break
    sendline(r, ans)
  if pos:
    print(recv(r))
    print(recv(r))
    print(recv(r))
    exit(0)