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つあり，それぞれ１つの暗号文が掲載されています．それぞれ解く事で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つ以上の時では，恐らく圧縮方法が異なる．
  • 文字の種類が１つの時は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:実際の暗号，復号コードの仕様とは異なるが，雰囲気を伝えるために変えています．