nkhrlab~

140字超の記事

Tokyo Westerns CTF 3rd 2017(2017/9/2 - 2017/9/4) - Writeup

チーム「Harekaze」のメンバーとしてCTF「Tokyo Westerns CTF 3rd 2017」に参加した.チームは940点を獲得し33位となった.個人では2個のフラグを得ることができたので,Writeupを書く.

[PPC 24]Palindromes Pairs - Coding Phase -

空白区切りで与えられる文字列のリストに対して,そのうちの2個を取り出し結合したものが回文となる組み合わせがいくつあるかを答える問題.文字列のリストの大きさは高々50という制約のため,すべての組み合わせをしらみつぶしに調べても高々2500個の組み合わせを調べればよいことが明らかで,これは十分に短い時間で実行可能である.そこで,素朴な方法を実装した次のRubyスクリプトを作成した.

while true do
  str = gets
  p str
  if "a" <= str[0] && str[0] <= "z"
    ans = 0
    arr = str.split
    for i in 0...arr.size do
      for j in 0...arr.size do
        target = arr[i] + arr[j]
        if target == target.reverse
          ans += 1
        end
      end
    end
    p ans
  end
end

フラグ

TWCTF{find_favorite_smell}

を得た.

[Crypto 25]My Simple Cipher

フラグ・区切り文字・13文字の秘密鍵をこの順に結合して作成した平文を独自(と思われる)アルゴリズムで暗号化し16進数として出力した文字列からフラグを得る問題.

暗号化に使われたPythonスクリプトを見ることより,このアルゴリズムは次のように説明できる.

 n文字のメッセージ m_0, m_1, \dots , m_{n - 1},13文字の秘密鍵 k_0, k_1, \dots , k_{12}から n + 1文字の暗号文 e_0, e_1, \dots, e_{n}が作成される. m_i, k_i, e_iの表記はそれぞれメッセージ,秘密鍵,暗号文の上から i + 1桁目の文字コードを表す.

暗号文の生成には次の漸化式が用いられる.ここで,二項演算子 \%について, a \% b a bで割ったあまりを表す.
 {\displaystyle e_i = \begin{cases} \mathrm{const.}, 0 \leq e_i \leq 127 & (i = 0) \\ (m_{i - 1} + k_{(i - 1) \% 13} + e_{i - 1}) \% 128 & (1 \leq i \leq n)  \end{cases} }

最後に,出来上がった暗号文を16進数として出力する.出力された16進数の桁数は暗号文のちょうど2倍となる.

ここで,16進数となった暗号文を見てみよう.この16進数を2桁ずつに区切ることでもとの暗号文の各桁の文字コード,すなわち e_{i} \;\; (0 \leq i \leq n)の値を知ることができる.

7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e

16進数となった暗号文の桁数が72桁だから,16進数として出力される前の暗号文は半分の36桁である.よって, n = 35.さらに,この問題のメッセージの最後の13桁は秘密鍵と同じだから, m_{i + 22} = k_{i} \;\; (1 \leq i \leq 13).この式を暗号文生成の漸化式に代入すると,
 k_{i} + k_{(i - 1) \% 13} \equiv e_{i + 23} - e_{i + 22} \;\; (\mathrm{mod} \; 128, 0 \leq i \leq 12).
ただし,それぞれの文字コードを7bitの正の整数とすると,制約
 0 \leq k_{i} \leq 127 \;\; (0 \leq i \leq 12)
が課される.

こうして,暗号鍵(の文字コード)に関する制約付き連立合同式を得た.13個の変数に対して13個の合同式が見出されているのでこの連立合同式の解としての暗号鍵を一意に定めることが可能かもしれないが,この合同式のままでは扱いが難しいので,メッセージに含まれる区切り文字に注目することにした.メッセージの区切り文字(半角の縦線)はフラグと暗号鍵の間である上から22桁目にあり,その文字コードは10進数で124である.よって, m_{21} = 124.暗号文生成の漸化式に対して i = 22を代入・整理すると
 k_8 \equiv e_{22} - e_{21} - m_{21} \;\; (\mathrm{mod} \; 128).
となり,文字コードの範囲についての制約から k_8が一意に求まる.この結果をもとの連立合同式に代入すれば,秘密鍵の各桁の文字コードを次々に求めることができる.秘密鍵全体が明らかになったら暗号文生成の漸化式に代入してメッセージの各桁の文字コードについて解くことでフラグを得られる.
この問題の秘密鍵

ENJ0YHOLIDAY!

だった.また,フラグは

TWCTF{Crypto-is-fun!}

であった.