TSG CTF 2021 Advanced Fisher Writeup

tags: CTF

この writeup は TSG 内部で行われた TSG CTF 2021 レビュー中に書かれたものです。

問題

フラグから 440 Hz のトーンを用いたモールス信号を生成し、それを前後にシャッフルして出力した音声が与えられる。

解法

まずは出力される音声に使われている正弦波を確認する。

wave[i] = np.sin(i * 440 / 44100 * (2 * np.pi))

$44100/gcd(440,44100)=2205$ より wave には

$2205$ 種類の数値が現れ、周期も

$2205$ である。

よって出力結果に現れる数値も高々

$2205$ 種類である。ここで results.wav の各値がどの wave[i] に一致するかに変換しても情報量は変わらない。また results.wav はシャッフルされているため、wave[i] が何回現れるかのマッピングに変換しても情報量は変わらない。

（実装上の注意として、音声ファイルは 24 ビット浮動小数点数で出力されているので、値同士の比較方法に注意する。）

さて、配列というデータを離散フーリエ変換の文脈でわかりやすく操作するために、以下を導入する。

$$W_{2025}=\exp \left(-i\frac{2\pi }{2025}\right)\text{(}i\text{ は虚数単位)}$$

これを

$n$ 乗した

$W_{2025}^n$ は

$2205$ 種類の値を取り、周期も

$2205$ である。この性質は最初に見た wave[i] と一致している。

生成されるモールス信号におけるひとつの単位は、ある時点から連続した

$2000$ 個の

$1$ であるから、次のように表される。

$$\mathrm{unit}[i]=\{\begin{array}{ll}1& (0\le i<2000)\\ 0& (2000\le i<2025)\end{array}$$

$$\mathrm{unit}=\sum _{i=0}^{2024}\mathrm{unit}[i]\cdot W_{2025}^i$$

生成される音声は以下のように表される。

$$\begin{array}{rl}\mathrm{result}& =\sum _{i=0}^{472}\mathrm{signals}[i]\cdot W_{2025}^{2000i}\cdot \mathrm{unit}\end{array}$$

前述の「result.wav の各値に wave[i] が何回現れるかのマッピング」を

$\mathrm{counts}$ とおくと、

$\mathrm{result}$ と

$\mathrm{counts}$ は全く同一のものである。

$\mathrm{signals}$ はインデックスが

$1$ 増える度に単位時間の開始が

$2000$ ずれていて扱いづらい。よって、インデックスが

$1$ 増える度に単位時間の開始が

$1$ ずれるように並べ替えたものを考える。

$${\mathrm{signals}}^{\prime }[2000imod2205]=\mathrm{signals}[i]$$

ここで

${\mathrm{signals}}^{\prime }$ の長さは

$2205$ とし、上記にあてはまらないとき

${\mathrm{signals}}^{\prime }[i]=0$ とする。

ただし

$\mathbb{Z}/2205\mathbb{Z}$ における

$2000$ の加法群を考えると位数は

$2205/gcd(2205,2000)=441$ である。

$0\le i<473$ はこれを超えるため、重複が起こってしまうことが考えられるが、今回はフラグの先頭文字列が TSGCTF{ であることがわかっているので

$73\le i<473$ に絞ることができる。

$\mathrm{counts}$ から TSGCTF{ の分を取り除いたものを

${\mathrm{counts}}^{\prime }$ とすると

$$\begin{array}{rl}{\mathrm{counts}}^{\prime }& =\sum _{i=73}^{472}{\mathrm{signals}}^{\prime }[2000imod2025]\cdot W_{2025}^{2000i}\cdot \mathrm{unit}\\ & =\sum _{i=0}^{2024}{\mathrm{signals}}^{\prime }[i]\cdot W_{2025}^i\cdot \mathrm{unit}\\ & =(\sum _{i=0}^{2024}{\mathrm{signals}}^{\prime }[i]\cdot W_{2025}^i)\cdot (\sum _{j=0}^{2024}\mathrm{unit}[j]\cdot W_{2025}^j)\\ & =\sum _{n=0}^{2024}(\sum _{i+j=n}{\mathrm{signals}}^{\prime }[i]\cdot \mathrm{unit}[j])\cdot W_{2025}^n\end{array}$$

${\mathrm{counts}}^{\prime }$ の

$W_{2025}^n$ 成分は

$${\mathrm{counts}}^{\prime }[n]=\sum _{i=0}^n{\mathrm{signals}}^{\prime }[i]\cdot \mathrm{unit}[n-i]$$

となり、これは畳み込みの形をしている。

よって逆畳み込みによって

$${\mathrm{signals}}^{\prime }={\mathcal{F}}^{-1}[\mathcal{F}[{\mathrm{counts}}^{\prime }]/\mathcal{F}[\mathrm{unit}]]$$

が得られる。あとはここから

$\mathrm{signals}$ を復元すれば良い。

コード

from collections import Counter
import soundfile as sf
import numpy as np
from utils import signals_to_string, string_to_signals

# Generate a cycle
cycle = [0] * 2205
for i in range(len(cycle)):
  cycle[i] = np.sin(i * 440 / 44100 * (2 * np.pi))

# Round values to 24-bit
sf.write("cycle.wav", cycle, 44100, "PCM_24")
cycle, _ = sf.read("cycle.wav")
cycle = list(cycle)

# Get result.wav
result, _ = sf.read("result.wav")

# Count
counts = [0] * 2205
for value, count in Counter(result).items():
  index = cycle.index(value)
  counts[index] = count

# Remove spaces
counts[0] = counts[1]

# Prepare leading signals
leading_signals = string_to_signals("TSGCTF{")

# Remove leading signals
for i in range(len(leading_signals)):
  for j in range(2000):
    counts[(2000 * i + j) % len(counts)] -= leading_signals[i]

# Deconvolution!
def deconvolve(h, g):
  n = len(h)
  H = np.fft.rfft(h, n)
  G = np.fft.rfft(g, n)
  F = H / G
  f = np.fft.irfft(F, n)
  return np.rint(f).astype(np.int64)

reordered_signals = deconvolve(counts, [1] * 2000)

# Restore signals
signals = [0] * 473

signals[:len(leading_signals)] = leading_signals

for i in range(len(leading_signals), len(signals)):
  signals[i] = reordered_signals[2000 * i % len(reordered_signals)]

print(signals_to_string(signals))