# 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) \quad \text{($i$ は虚数単位)}
$$

これを $n$ 乗した $W_{2025}^{n}$ は $2205$ 種類の値を取り、周期も $2205$ である。この性質は最初に見た `wave[i]` と一致している。

生成されるモールス信号におけるひとつの単位は、ある時点から連続した $2000$ 個の $1$ であるから、次のように表される。

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

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

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

$$
\begin{equation}
\begin{split}
\mathrm{result} &= \sum_{i = 0}^{472} \mathrm{signals}[i] \cdot W_{2025}^{2000i} \cdot \mathrm{unit}
\end{split}
\end{equation}
$$

前述の「`result.wav` の各値に `wave[i]` が何回現れるかのマッピング」を $\mathrm{counts}$ とおくと、$\mathrm{result}$ と $\mathrm{counts}$ は全く同一のものである。

$\mathrm{signals}$ はインデックスが $1$ 増える度に単位時間の開始が $2000$ ずれていて扱いづらい。よって、インデックスが $1$ 増える度に単位時間の開始が $1$ ずれるように並べ替えたものを考える。

$$
\mathrm{signals'}[2000i \bmod 2205] = \mathrm{signals}[i]
$$

ここで $\mathrm{signals'}$ の長さは $2205$ とし、上記にあてはまらないとき $\mathrm{signals'}[i] = 0$ とする。

ただし $\mathbb{Z}/2205\mathbb{Z}$ における $2000$ の加法群を考えると位数は $2205 / \gcd(2205, 2000) = 441$ である。$0 \le i \lt 473$ はこれを超えるため、重複が起こってしまうことが考えられるが、今回はフラグの先頭文字列が `TSGCTF{` であることがわかっているので $73 \le i \lt 473$ に絞ることができる。

$\mathrm{counts}$ から `TSGCTF{` の分を取り除いたものを $\mathrm{counts'}$ とすると

$$
\begin{equation}
\begin{split}
\mathrm{counts'} &= \sum_{i = 73}^{472} \mathrm{signals'}[2000i \bmod 2025] \cdot W_{2025}^{2000i} \cdot \mathrm{unit} \\
&= \sum_{i = 0}^{2024} \mathrm{signals'}[i] \cdot W_{2025}^{i} \cdot \mathrm{unit} \\
&= \left( \sum_{i = 0}^{2024} \mathrm{signals'}[i] \cdot W_{2025}^{i} \right) \cdot \left( \sum_{j = 0}^{2024} \mathrm{unit}[j] \cdot W_{2025}^{j} \right) \\
&= \sum_{n = 0}^{2024} \left( \sum_{i + j = n} \mathrm{signals'}[i] \cdot \mathrm{unit}[j] \right) \cdot W_{2025}^{n}
\end{split}
\end{equation}
$$

$\mathrm{counts'}$ の $W_{2025}^{n}$ 成分は

$$
\mathrm{counts'}[n] = \sum_{i = 0}^{n} \mathrm{signals'}[i] \cdot \mathrm{unit}[n - i]
$$

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

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

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

が得られる。あとはここから $\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))