[SECCON Beginners CTF 2020] Noisy equations

noise hides flag.

from os import getenv
from time import time
from random import getrandbits, seed


FLAG = getenv("FLAG").encode()
SEED = getenv("SEED").encode()

L = 256
N = len(FLAG)


def dot(A, B):
    assert len(A) == len(B)
    return sum([a * b for a, b in zip(A, B)])

coeffs = [[getrandbits(L) for _ in range(N)] for _ in range(N)]

seed(SEED)

answers = [dot(coeff, FLAG) + getrandbits(L) for coeff in coeffs]

print(coeffs)
print(answers)

解説

「FLAG44文字だし44回分サンプル取ってz3投げれば解けるやろ!」という発想のもとスクリプトを書きました

• サンプルを錬成するツール

  #!/usr/bin/env python3
  import os
  for i in range(0, 44):
      os.system("nc noisy-equations.quals.beginners.seccon.jp 3000 > log/log%02d.log" % i)

• ソルバー

  #!/usr/bin/env python3
  from z3 import *
  import json
  
  def dot(A, B):
      return sum([a * b for a, b in zip(A, B)])
  
  N = 44
  
  logs = []
  for i in range(N):
      with open("log/log%02d.log" % i, "r") as f:
          t = f.read().split('\n')
          coeffs = eval(t[0])
          answers = eval(t[1])
          logs.append({"coeffs": coeffs, "answers": answers})
  
  s = Solver()
  flag = IntVector("flag", N)
  srnd = IntVector("srnd", N)
  
  for h in range(N):
      for i in range(N):
          b = dot(flag, logs[h]["coeffs"][i])
          s.add(b + srnd[i] == logs[h]["answers"][i])
  
  r = s.check()
  print(r)
  if r == sat:
      m = s.model()
  else:
      print(r)
      exit()
  
  print(m)

15分ほど待つとflagが得られます ctf4b{r4nd0m_533d_15_n3c3554ry_f0r_53cur17y}

もうすこしいい方法があるみたいなのでよいこはマネしてはいけません ちなみにこのソルバを書き上げたのは大会終了5分前でした