math314のブログ

主に競技プログラミング,CTFの結果を載せます

SECCON CTF 2014 決勝戦 サーバ六 write-up

SECCON CTF 2014決勝戦・全国大会カンファレンス

チーム Mr.Takedashi(メンバー: @misodengaku, @aki33524, @chibiegg, @__math) で出ていました. 9/24位です. 日本人チームの中では4/13位でした.今年はcryptoがあったので幾つか問題が解けました.

他のメンバーのwrite-upです

SECCON 2014全国 - aki33524の日記

SECCON CTF 2014 決勝戦 参加記 « chibiegg日誌

SECCON 2014 全国大会に出た - misodengakuのブログ

去年も決勝大会(http://math314.hateblo.jp/entry/2014/03/03/210318)に出たのですが,順位が下の方で悔しい思いをしました.2014年も出れたなら1桁の順位をとろう!とチームで言っていたので,目標が達成出来て満足です.

私は主に サーバ六 の問題を担当したので,簡単にwrite-up を書きたいと思います.

サーバ六の問題は,cryptoです.(画面のキャプチャを取りたかったけど,競技後すぐにPCが落ちて取れない…)

平文を投げると暗号文が返ってくるページがあります. 例えば,

  • AAAA -> bbbb
  • 0123 -> cNFx

という風. 連続して平文を投げると「wait 5s.」と返ってきます,待ちましょう. ルール説明のページには以下の条件が.

  • この暗号は可逆な変換である事が保証されている(明示されていないが,動画を見ることでわかる)
  • 入力,出力共に[0-9A-Za-z_/] の 64文字のみ

(この説明のページに動画がuploadされており,非常に分かりやすかったので公開して欲しい.)

問題が乗っているページは4つあり,それぞれ1つの暗号文が掲載されています.それぞれ解く事で100ptが得られます.

問題1

暗号文 : U8OOh7i3YI8_YJo8i_Yi7IzY37Y5u9JoY97dYOCud8uC7_YHC_3YbY8_3YhiCuoYu7YhACJoYE8C_J9Y7IIdiio3YA8OYA8IzoiYuAoY7iYdOoYhi7uoYio83YiCqAuY

解法

単純な換字式暗号です. 平文として 012...89ABC...YZ,abc...yz_/ の64文字を投げると変換テーブルが獲得出来ます.

プログラム

def solve1():

    frm = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890/_"
    to = "b1gkVL0PTaQwprGUvK5mtnZBMD8SI3oHqACRzJE_7y6iOud2hW9jlNFxeX4/sfcY"

    dest = "U8OOh7i3YI8_YJo8i_Yi7IzY37Y5u9JoY97dYOCud8uC7_YHC_3YbY8_3YhiCuoYu7YhACJoYE8C_J9Y7IIdiio3YA8OYA8IzoiYuAoY7iYdOoYhi7uoYio83YiCqAuY"
    ans = ""
    for i in dest:
        j = to.index(i)
        ans += frm[j]

    print ans

問題2

暗号文 : pQ0018PYsa7_nskQqrgP0szQrgsSg0Usa77OsdYg2UdIdqQUd82sQskQqrgPsd0sQYzd2d0UPQUd82szb0gJIs1kbsUkgsUdzgs1gJJszQbsd0sUkgs0k85JYsUdUJgs

解法

この問題は記憶に残ってないんですが,プログラムを見る限り問題1と一緒?みたいです. どなたか覚えている方がいらっしゃったら教えて下さい.

プログラム

def solve2():

    frm = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_/"
    to = "HaXKTnOV_7QSqYgIjkdurJz28AwP0U5D1Zb3RhW4NCBlFexfymtp/oELivM69csG"
    dest = "pQ0018PYsa7_nskQqrgP0szQrgsSg0Usa77OsdYg2UdIdqQUd82sQskQqrgPsd0sQYzd2d0UPQUd82szb0gJIs1kbsUkgsUdzgs1gJJszQbsd0sUkgs0k85JYsUdUJgs"
    ans = ""
    for i in dest:
        j = to.index(i)
        ans += frm[j]
    print ans

問題3

暗号文 : DoAfaC677d_zTTHa8rP6B13euZjIItppyLd09V1CmNeNI4HJxGAfLW7c1j_gZfHaCDifovzDjkTNNJi5XL3WWfnqVQe1itFHF_3YbmbVGzUti9UEXHAWJ_MZKRqQZiHo

解法

文字,文字列の長さによって変換テーブルをずらす必要がある問題です. 'A' * 64,'B' * 64, ... と投げる事で推測出来ます.

プログラム

def rotate(x,idx):
    idx %= len(x)
    return x[idx:] + x[:idx]

def solve3(dest):

    frm = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_/"
    table = "bUvkmzVMG48KxHhlsquAf/c2ZwO_dEayogPD7nCRNTX59rJWLF3S6Qj1YeBpiIt0"
    at = []

    for x in frm:
        idx = table.index(x)
        cur_table = rotate(table,idx + 1)
        at.append(cur_table)

    first = len(dest) % 64
    ans = ""
    for count,i in enumerate(dest):
        count = (count + first) % 64
        for j in xrange(64):
            cur = at[j][count]
            if i == cur:
                ans += frm[j]
                break

    print ans
solve3("DoAfaC677d_zTTHa8rP6B13euZjIItppyLd09V1CmNeNI4HJxGAfLW7c1j_gZfHaCDifovzDjkTNNJi5XL3WWfnqVQe1itFHF_3YbmbVGzUti9UEXHAWJ_MZKRqQZiHo")

問題4

暗号文は紛失しました,辛い.

解法

とりあえず問題3と同じく'A' * 64 とか投げてみます.[0-9a-zA-Z_/]の64種類について,1文字ずつ暗号化してみると,何か規則性が見えてきました.

  • 0 -> gDAAAQB
  • 1 -> gEAAAQB
  • 2 -> gIAAAQB
  • 3 -> gMAAAQB
  • 4 -> gQAAAQB

...

  • n gG4AAQB
  • o gG8AAQB
  • p gHAAAQB

...

2,3文字目以外すべて一致 & どうも入力したasciiコードと,大小関係が一致していそうな雰囲気がします. きっとAは0を意味するんだろうなあと推測.

更に,他の人の入力したログが最新20件程度確認できる事を利用して,暗号化の履歴を獲得. すると,「最後の1文字はABCのいずれか」であることが判明.

色々入力した結果,考えたことを箇条書きにしていきます.

  • どうもbase64っぽく見える
  • 'AB' * 100 くらい入力したのに,出力されるバイト数がとても少ない.圧縮されている.
  • 'A' のように1文字なら,元のデータより大きい.これは圧縮の特徴
  • gzipを試すが違う.
  • 最後が'A'なら'A'を消す.'B'なら代わりに'='で置き換え,'C'なら'=='で置き換える -> base64でdecode出来た
  • 文字の種類が1つの時と,2つ以上の時では,恐らく圧縮方法が異なる.
  • 文字の種類が1つの時はrun lengthぽい.以降無視,2種類以上を考える
  • LZSSではない,スライド窓を使った暗号化には見えない.
  • 先頭4byteは,複合語のサイズ
  • 'ABBBBBB','BAAAAAA' を暗号化すると,先頭5-7byte目辺りのみが違う.
  • [先頭4byte = サイズ] [テーブル] [データ] という構造に見える
  • この感じはハフマン符号では?と辺りをつける.16進数で眺めてもわからないのでデータを2進数で表示するように.
  • [複合後サイズ] [ [0...01] [asciiコード] [0...01][asciiコード] ... ] [データ] は確定
  • [0...01]の部分がハフマン符号を作る木であることは明らかだが,生成方法が分からず…
  • time up

残念. 後から解法を聞いたので,解いたらコードを上げます.

defence point

問題を紹介してきましたが,これとは別にdefence pointが稼げる場所がありました.

自分で問題を作成し,サーバにuploadして,特定の条件を満たす1チームだけにdefence pointとして5分に20ptが与えられます. 条件は,

  • 最も解いているチーム数が少ない問題
  • コードのbyte数が最も少ない
  • 問題作成が最も早かった

の3つです. 1番目の条件で一意に決まらない場合は2番目の条件,それでもだめなら3番目の条件が適応されます.

問題の作成には encode,decodeの処理を書いたpythonスクリプトを提出が必要です. 一度問題を作ると,次の問題を作るまで1時間待たなければなりません.

...

ところでルールの1つ目に

  • この暗号は可逆な変換である事が保証されている

というのがありました.これは具体的には plain = decode(encode(plain)) ならばよい,ということです.

次に,「最も解いているチーム数が少ない問題」と書きましたが,「解けた」と判定する条件は,実は def CHECK(plain,cypher): return encode(plain) == cypher で確認されています.

とすると

import uuid
def encode(plain): return str(uuid.uuid4()) + plain
def decode(cypher): return cypher[36:]

というコードはvalid*1ですが,CHECK関数でtrueが返る確率はほぼ0ですね.

中盤これに気付いたチームがこのコードを投げると,競技内容が「復号化の難しいコードを作る」から「pythonコードゴルフ」 に変わりました.素敵ですね.

実はコードゴルフに乗り遅れても点数を取る方法はありました. 「暗号化を一切しないコードが最も短い」という特性を利用して, 得点が加算される直前に暗号化をしないコードを投げる事で20ptを得る事が出来ました.鯖に遅延とか他のチームの兼ね合いを考える運ゲーだったりして面白い.

感想

暗号問題がとても楽しく,私はこれしか手を付けてませんでした.

おまけ

持ち込み量1位

片付けについて

*1:実際の暗号,復号コードの仕様とは異なるが,雰囲気を伝えるために変えています.