チームr0bu5tとして、SECCON Beginners CTF 2020に参加していました。
自分が解いたNoisy equationsの解法を共有します。数学的なところが非常に面白くて、解いていて楽しかったです！
Noisy equations
問題
以下のサーバ側のコードが与えられていて、そのサーバに接続するとcoeffsとanswersが返ってくるというものです。
乱数が使われているので毎回異なる結果が返ってきます。
server.py
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)
解法
コードを読み解くと、以下のようになっていることがわかります。
A_ix + b = y_i
Aがcoeffs, xがFLAG, bがseedで固定されたgetrandbits(L), yがanswersです。Aに関しては乱数が固定されていないため、実行するたびに値が変わります。
これを2回取得すれば、xを求めることができます。
A_1x + b = y_1\\
A_2x + b = y_2\\
\Rightarrow (A_1-A_2)x = y_1-y_2\\
\Rightarrow x = (A_1-A_2)^{-1}y_1-y_2\\
以下のコードでFLAGを得ることができました。
solver.py
import numpy as np
from sympy import Matrix
A1 = Matrix([[123123..., ...], ...])
y1 = Matrix([123123..., ...])
A2 = Matrix([[123123..., ...], ...])
y2 = Matrix([123123..., ...])
A = (A1-A2)
y = (y1-y2)
soln = A.LUsolve(y)
print(''.join([chr(s) for s in soln]))
\Rightarrow ctf4b\{r4nd0m\_533d\_15\_n3c3554ry\_f0r\_53cur17y\}
チームメンバー・運営の皆様お疲れ様でした。