[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分前でした