팀 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에 관해서는 난수가 고정되어 있지 않기 때문에 실행할 때마다 값이 바뀝니다.

이것을 두 번 얻으면 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\}

팀 멤버·운영의 여러분 수고하셨습니다.