[RCTF 2022] superguess

We denote the 20 characters of $x$ as $c_0, \dots, c_{19}$. Then $x = \sum_{i=0}^{20} 256^{19-i} \cdot c_i$. Note that $c_{15} = \_, c_{16} = c, \dots, c_{19} = t$.

We will try to adapt rkm's inequality solver here. The inequalities that we have is:

• $1 \leq x \cdot T_i - U_i - a_i \cdot q \leq q / 4$ for $1 \leq i \leq 90$.
• $c_i \leq c_{i+1}$ for $0 \leq i \leq 18$
• $c_{0}, \dots, c_{14}$ is ascii uppercase or digits.
• $c_{15}, \dots, c_{19}$ is constant

Unfortunately, this condtion is not enough to find appropriate vector in CVP. So we added customized conditions:

• $c_0$ to $c_3$ is digits and $c_4$ to $c_{14}$ is ascii uppercase.
• $c_0 < c_1 < c_2 < c_3$.
• $c_{i+1} - c_i \leq 5$ for $4 \leq i \leq 13$.
• $c_4 \in {A,B,C}, c_{14} \in {X,Y,Z}$.

We test all possible candidates $c_0, c_1, c_2, c_3, c_4, c_{14}$ for each connection.

The probability that randomly chosen $x$ satisfies this is about 1.4%. And if $x$ satistfies this, $x$ is reveal with a probability about 60%. So We can estimate that we can succeed after about 120 trials. In each connection, the running time is about 2 minutes in my PC. So I ran 10 parallel connections.

########
from sage.modules.free_module_integer import IntegerLattice
from sage.all import *
from pwn import *
from Crypto.Util.number import *
from itertools import combinations
from multiprocessing import Pool

from random import randint, choices, seed
from string import ascii_uppercase, digits


q = 0
T = []
U = []
r = None

def conn():
  global r,q,T,U
  r = remote("190.92.233.181", 23334)
  r.recvuntil(b" = ")
  q = int(r.recvline())
  r.recvuntil(b" = ")
  T = eval(r.recvline())
  r.recvuntil(b" = ")
  U = eval(r.recvline())

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI

#def Babai_CVP(mat, target, M, G):
def Babai_CVP(M, G, target):

  diff = target
  for i in reversed(range(G.nrows())):
    diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
  return target - diff


def solve(mat, lb, ub, weight = None):
  num_var  = mat.nrows()
  num_ineq = mat.ncols()

  max_element = 0 
  for i in range(num_var):
    for j in range(num_ineq):
      max_element = max(max_element, abs(mat[i, j]))

  if weight == None:
    weight = num_ineq * max_element

    # sanity checker
  if len(lb) != num_ineq:
    print("Fail: len(lb) != num_ineq")
    return

  if len(ub) != num_ineq:
    print("Fail: len(ub) != num_ineq")
    return

  for i in range(num_ineq):
    if lb[i] > ub[i]:
      print("Fail: lb[i] > ub[i] at index", i)
      return

      # heuristic for number of solutions
  DET = 0

  if num_var == num_ineq:
    DET = abs(mat.det())
    num_sol = 1
    for i in range(num_ineq):
      num_sol *= (ub[i] - lb[i])
    if DET == 0:
      print("Zero Determinant")
    else:
      num_sol //= DET
      # + 1 added in for the sake of not making it zero...
      print("Expected Number of Solutions : ", num_sol + 1)

  # scaling process begins
  # max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
  # applied_weights = []

  # for i in range(num_ineq):
  #   ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])

  #   # customized
  #   # if i < 12: ineq_weight *= 1


  #   applied_weights.append(ineq_weight)
  #   for j in range(num_var):
  #     mat[j, i] *= ineq_weight
  #   lb[i] *= ineq_weight
  #   ub[i] *= ineq_weight

  # Solve CVP
  target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
  result = Babai_CVP(M, G, target)

  for i in range(num_ineq):
    if (lb[i] <= result[i] <= ub[i]) == False:
      #print("Fail : inequality does not hold after solving")
      return result, -1
  fin = None

  if DET != 0:
    mat = mat.transpose()
    fin = mat.solve_right(result)

  ## recover your result
  return result, fin


varnum = 9 + 90 # c5 to c13, a0 to a89 (we fix c0,c1,c2c3,c4,c14)
eqnum = 10 + 90 # 10 : c condition, 90 : given equation
B = bytes_to_long(b'_cfrt')
mat = matrix(ZZ, varnum, eqnum)
M = None
G = None

def init_mat():
  FACTOR = (q//4) // 5
  #print(FACTOR)
  #print(U[0])
  global mat, M, G
  mat = matrix(ZZ, varnum, eqnum)
  M = None
  G = None

  #varnum = 9 + 90 # c5 to c13, a0 to a89 (we fix c0,c1,c2c3,c4,c14)
  #eqnum = 10 + 90 # 10 : c condition, 90 : given equation
  mat[0, 0] = 1 * FACTOR

  for i in range(8):
    mat[i, i+1] = -1* FACTOR
    mat[i+1, i+1] = 1* FACTOR

  mat[8, 9] = 1* FACTOR

  # given equation
  for i in range(90):
    for j in range(9):
      mat[j, i + 10] = T[i] * 256^(14 - j)
    mat[i+9, i + 10] = -q

  M = IntegerLattice(mat, lll_reduce=True).reduced_basis
  G = M.gram_schmidt()[0]
  print("init_mat done")

def LLL(c0, c1, c2, c3, c4, c14):
  FACTOR = (q//4) // 5
  #print("now", c0,c1,c2,c3)
  varnum = 9 + 90 # c5 to c13, a0 to a89 (we fix c0,c1,c2c3,c4,c14)
  eqnum = 10 + 90 # 10 : c condition, 90 : given equation
  lb = [0]*eqnum
  ub = [0]*eqnum

  # c condition
  lb[0] = 65* FACTOR
  ub[0] = 70* FACTOR

  for i in range(8):
    lb[i+1] = 0* FACTOR
    ub[i+1] = 5* FACTOR

  lb[9] = 85* FACTOR
  ub[9] = 90* FACTOR

  # given equation
  for i in range(90):
    lb[i+10] = U[i]+1    - T[i] * (B + c0 * 256^19 + c1 * 256^18 + c2 * 256^17 + c3 * 256^16 + c4 * 256^15 + c14 * 256^5) 
    ub[i+10] = U[i]+q//4 - T[i] * (B + c0 * 256^19 + c1 * 256^18 + c2 * 256^17 + c3 * 256^16 + c4 * 256^15 + c14 * 256^5)

  res, fin = solve(M, lb, ub)


  #for i in range(10):
  #  print(res[i] // FACTOR)

  if fin == -1:
    return None


  S = chr(c0) + chr(c1) + chr(c2) + chr(c3) + chr(c4)
  S += chr(res[0] // FACTOR)
  for i in range(1,9):
    gap = res[i] // FACTOR
    S += chr(ord(S[-1]) + gap)
  S += chr(c14)
  S += '_cfrt'
  print("!!!!!!!!!!!!!!!!!!!!!!!!!")
  print(S)
  print("!!!!!!!!!!!!!!!!!!!!!!!!!")
  vv = bytes_to_long(S.encode())
  r.sendline(str(vv).encode())
  print(r.recvline())
  r.interactive()
  exit(0)
  return S

def gogo():
  conn()
  init_mat()
  COMB_NUM = list(combinations(list(range(48,58)), 4))
  COMB = []
  for a in range(65, 68):
    for b in range(88, 91):
      for elem in COMB_NUM:
        z = list(elem[:])
        z.append(a)
        z.append(b)
        COMB.append(z)

  print("brute len", len(COMB))

  #zz = sorted(key)
  #recover = LLL(ord(zz[0]),ord(zz[1]),ord(zz[2]),ord(zz[3]),ord(zz[4]),ord(zz[14]))
  #print("!!!", recover)
  #input()
  #exit()


  #r = get_data()
  with Pool(16) as p:
    result = p.starmap(LLL, COMB)

  for vv in result:
    if vv: print(vv)

  r.close()

CNT = 0
while True:
  CNT+=1
  print("@@@@@@ NOW ", CNT, "@@@@@@")
  gogo()
#LLL(3,3,6,9)