TSG Live CTF 6 writeup

先日行われたTSG Live! 6中の企画の一つ、TSG Live CTFに外部チームの一員として招待され、参加してきましたので記念writeupです。放送のアーカイブはこちら↓

チームは公式には kurenaifさん、ptr-yudai、私の3人でしたが、助っ人としてst98さんにもいくつかの問題を解いていただきました。正直私はいてもいなくても同じ結果になっただろうと思っていますが、このチームで参戦できて楽しかったです。私が解いた問題のうち、Fisherだけは正答数がすくなかったのでwriteupを書いておきます。

与えられるのは次のようなソースコードで、 string_to_signalsは文字列を[0, 1]からなるモールス符号に変換する関数です。素直に読むと、フラグ文字列をモールス符号に変換し、さらに01の符号データをsin波で表しています。それだけなら良いのですが、この波形データをランダムにシャッフルしたあと、wav形式で保存しています。

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

flag = open('flag.txt').read()
signals = string_to_signals(flag)

assert(len(signals) == 473)

wave = np.empty(len(signals) * 2000)
for i in range(len(wave)):
  if signals[i // 2000] == 0:
    wave[i] = 0.0
  else:
    
    wave[i] = np.sin(i * 439.97 / 44100 * (2 * np.pi))


np.random.shuffle(wave)

sf.write('result.wav', wave, 44100, 'PCM_24')

結構困るように見え、また想定解法（賢い）では困った前提で $x$ が小さいときに $\sin(x) \approx x$ であることを利用しているのですが、実験をしてみると意外にもsin波を構成する点が、どのiに対応するかがほぼ一対一で対応付けられることに気が付きました。おそらく浮動小数点の演算誤差からくるものだとは思いますが、へーという感じです。

というわけで、自分で i を回しながら $\sin(\frac{439.97i}{44100 * 2\pi})$ に一致する点があるかないかで、その周辺が0/1のどちらを波形に変換したものかを判断することができます。一致の判定は浮動小数点でやると怖いので、多少の誤差を受け入れることにして小数を文字列に変換して、小数点以下n桁までが一致するかを見ました。

import soundfile as sf
import numpy as np
from utils import signals_to_string

filepath = 'result.wav'
data, _ = sf.read(filepath)

print(len(data))
size = len(data)
data = set(["{:.6f}".format(d) for d in data])

rev_data = []

for i in range(size):
  k = np.sin(i * 439.97 / 44100 * (2 * np.pi))
  ks = "{:.6f}".format(k)
  if ks in data:
    rev_data.append(k)
  else:
    rev_data.append("x")


signal = []
for i in range(0, len(rev_data), 2000):
  if rev_data[i:i+2000].count("x") > 500:
    signal.append(0)
  else:
    signal.append(1)



print(signals_to_string(signal))

重ねて申し上げますが、楽しい企画に誘ってくださり対戦どころか問題まで用意してくださったTSGの皆様、一緒にチームを組んでくれたkurenaifさん、ありがとうございました。楽しかったです