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スクリプトを見ることより,このアルゴリズムは次のように説明できる.
文字のメッセージ,13文字の秘密鍵から文字の暗号文が作成される.の表記はそれぞれメッセージ,秘密鍵,暗号文の上から桁目の文字コードを表す.
暗号文の生成には次の漸化式が用いられる.ここで,二項演算子について,はをで割ったあまりを表す.
最後に,出来上がった暗号文を16進数として出力する.出力された16進数の桁数は暗号文のちょうど2倍となる.
ここで,16進数となった暗号文を見てみよう.この16進数を2桁ずつに区切ることでもとの暗号文の各桁の文字コード,すなわちの値を知ることができる.
7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e
16進数となった暗号文の桁数が72桁だから,16進数として出力される前の暗号文は半分の36桁である.よって,さらに,この問題のメッセージの最後の13桁は秘密鍵と同じだから,この式を暗号文生成の漸化式に代入すると,
ただし,それぞれの文字コードを7bitの正の整数とすると,制約
が課される.
こうして,暗号鍵(の文字コード)に関する制約付き連立合同式を得た.13個の変数に対して13個の合同式が見出されているのでこの連立合同式の解としての暗号鍵を一意に定めることが可能かもしれないが,この合同式のままでは扱いが難しいので,メッセージに含まれる区切り文字に注目することにした.メッセージの区切り文字(半角の縦線)はフラグと暗号鍵の間である上から22桁目にあり,その文字コードは10進数で124である.よって,暗号文生成の漸化式に対してを代入・整理すると
となり,文字コードの範囲についての制約からが一意に求まる.この結果をもとの連立合同式に代入すれば,秘密鍵の各桁の文字コードを次々に求めることができる.秘密鍵全体が明らかになったら暗号文生成の漸化式に代入してメッセージの各桁の文字コードについて解くことでフラグを得られる.
この問題の秘密鍵は
ENJ0YHOLIDAY!
だった.また,フラグは
TWCTF{Crypto-is-fun!}
であった.