少し前まで開催されていた場阿忍愚CTFの writeup を淡々と書いていく。結果としては craSH2 の一問だけ解けなかった。頑張ったが悔しい。しかし無知な状態で始めたので一通りどのジャンルにも手が付けられるようになったのは収穫だった。世界一楽しい和風CTFを運営してくださった方に感謝したい。

量が多くて一度に書ききれなかったので、ひとまず芸術、二進術、暗号術、攻撃術までを記事にする。練習と兵法術に関しては省略する予定。

芸術

ワットイズディス？

なんとなく読めるが篆書。大和世幾由利天伊と書いてある。
ちなみに大和以降の文字はちゃんと平仮名の字源に沿った漢字が選ばれている模様。
「大和セキュリティ」と提出して正解。

cole nanee?

それっぽかったので特に調べることもなく「忍」と入れたら当たった。

Lines and Boxes

はじめはパーツを並び替えて漢字を作るのかと思ったが違う。
よくよく見ると A とか L とかアルファベットが見えて、英単語だと気づく。
「WORD PLAY」と提出して正解。

Why want something more?

この辺りから書について真剣に調べる必要が出てくる。
日本インターネット書道協会の早見表で草書のいろはを頭に叩き込む。右の字は奴、如、妃など女偏の字にあたりをつけ、左の字は疋に近いので是を疑う。問題タイトルからして哲学・宗教感が滲み出ているので、如や是などに絞って検索をかけてみると画像検索で同じ内容の作品を発見（第三十五回何有展）。フラグは「如是」。和の心が足りずに右から読むことにしばらく気付けなかったのは痛恨だった。

毎日使う

画像検索にかけるもダメ。 "goku tatoo" などと無駄に検索してもダメ。草書一覧などと画像検索の海をさまよっている間に気の文字が一致することに気付く。しかし「気」を提出しても正解にはならない。よくよく見ると下半分が米の字になっていたので、旧字体の方の「氣」を提出したら正解できた。

Extreme Shodo POWER!!

見るからに五文字なので一文字ずつ特定していく。
結論から行くと左から氣、之、呼、波、和。「氣」は文字を切り取って色を反転させて画像検索にかけると似た漢字が入ったロゴを発見。悦氏という会社？のロゴに入っていたのでその会社のサイトを調べた結果特定した。「呼」と「波」は篆書のようだったので、判子屋さんのサイトを軽く使わせてもらって部首、旁の順で特定した。「和」に関しては右から筆が入っており不自然ということに気付いたため（大和魂で気付ける）、左右に反転させると「和」に見えた（和の心）。残った「之」は確証はないが筆の並びからそれにしか見えなかった。
漢字のまま提出しても正解にならない。タイトルの "POWER"、問題文の "get bigger"、そして "きのこ（氣之呼）"から「きのこパワー」が連想されたのでこれを提出したところフラグだった。

二進術

壱萬回

64bit ELF なので実行してみると、簡単な四則演算をさせられる。タイトルから察するに一万回しないとフラグが出なさそうなので、とりあえず gdb で逆アセンブルしてみる。 showFlag という如何にもな関数を呼び出しているので、これの中身を見てみると一文字ずつ putchar で出力している。 putchar の引数を並べてやればフラグが出てくる。

DxLib遊戯如何様

オセロの Windows バイナリなのでとりあえず遊んでみる。 AI はそれほど強くないので普通に勝てるが、勝ってももう一回初めからになる。

OllyDbg でステップ実行しながら、勝利判定をしている気配がある箇所とオセロの盤面を記録している領域を特定。盤面のデータは4バイトにつき1マスになっており、値は 0, 1, 2 がそれぞれ駒無し、黒、白に対応している。勝利判定の直前にオセロの盤面を黒く塗りつぶすと完全勝利できた。ただし一回勝っただけではフラグは出てこない。何回かいじっていて盤面の領域の隣に勝利回数を記録する4バイトがあることに気付いたので、ここに0x7FFFFFEを入れた上で盤面を黒く塗りつぶす。すると次の勝負から背景にフラグが表示された。

↓ 記念写真
f:id:liniku:20160208220737p:plain

Unity遊戯如何様

自分が手を付けたときには既にヒントが出ていたので、ヒントに従って Assembly-CSharp.dll を逆コンパイルする。さらにヒント通り GUIManager を見ると、フラグは its_3DGame_Tutorial に見える。しかしこれを提出しても正解にならない。ふと同梱されていたゲームのキャプチャー画像を見ると、"Hint" という文字列を渡されたラベルのところが "HINT" と表示されている。どうやら大文字にどこかで変換しているようなので、先ほどのフラグを全て大文字にしたところ正解した。

解読術

image level 5

一文字ずつ画像になっているので並び替える。
更新時間順にソートすると "KOBE-GYU" になる。これがフラグ。
自力で並べ替えて "KOBEGYU-" と提出してダメだったのはいい思い出。

Ninjya Crypto

神代文字と言われる忍者の暗号らしい。
やまといえば、と書いてあるので「川」と答える。

Decrypt RSA

640bit の公開鍵と、それで暗号化されたであろうファイルが与えられる。片方の素数が小さい値であることを祈り素因数分解を試みたがダメだった。途中で素因数分解の結果が公知であることに気付く。
https://en.wikipedia.org/wiki/RSA_numbers#RSA-640
後は復号するだけなので自力で復号を試みた。

#!/usr/bin/env python

def extended_euclidean(a, b):
    r0 = a
    r1 = b
    s0 = 1
    s1 = 0
    t0 = 0
    t1 = 1

    while r1 > 0:
        q = r0 / r1
        r2 = r0 % r1
        s2 = s0 - q * s1
        t2 = t0 - q * t1
        r0 = r1
        r1 = r2
        s0 = s1
        s1 = s2
        t0 = t1
        t1 = t2
    
    return (s0, t0)


def main():
    n = 0xae5bb4f266003259cf9a6f521c3c03410176cf16df53953476eae3b21ede6c3c7b03bdca20b31c0067ffa797e4e910597873eef113a60feccd95deb5b2bf10066be2224ace29d532dc0b5a74d2d006f1
    p = 1634733645809253848443133883865090859841783670033092312181110852389333100104508151212118167511579
    q = 1900871281664822113126851573935413975471896789968515493666638539088027103802104498957191261465571
    e = 65537
    m = (p - 1) * (q - 1)
    st = extended_euclidean(m, e)
    d = (st[1] + m) % m

    f = open("flag.txt")
    data = f.read()
    c = 0
    for i in range(len(data)):
        c = c * 0x100 + ord(data[i])

    a = pow(c, d, n)
    flag = ""
    while a > 0:
        flag = chr(a % 0x100) + flag
        a = a / 0x100
    print flag

if __name__ == '__main__':
    main()

復号した結果謎のバイト列のあとに FLAG_IS_WeAK_rSA と出てきた。バイト列を無視して提出したら正解した。（他の方の writeup 見ると真面目に秘密鍵作るのが正解だったらしい）

Zach! Take a nap!

gen.py の中を見ると次のようなコードがあるので、与えられた b, c から bits を復元する問題になっている。

c = 0
for i in xrange(n):
    if bits[i] == "1":
        c += b[i]

初めは動的計画法あたりでいくのかと考えもしたが、あまりに数字が大きすぎて解ける気がしなかった。

調べているうちに、subset sum problem などと言われる類の問題であり、さらに具体的に言うと Merkle Hellman knapsack という暗号であることが分かった。 gen.py に書かれているとおり、w_i > w_1 + ... + w_{i-1} となるような数字列を暗号化したい情報のビット数分だけ求めておく（このような性質を super-increasing というらしい）。これを q > w_1 + ... + w_n を満たす適当な数 q と適当な数 r を使って公開情報となる b[i] = r * w[i] % q に変換する。暗号化ははじめに引用した通りビットが1の部分だけ b[i] を足し合わせていく。
r と q が既知の場合は d = c * r^(-1) % q として b[i] の和から w[i] の和に変換できる。w[i] は super-increasing なため、iが大きい順に d >= w[i] かどうかを調べていく。このとき、もしそうであれば bit[i] が 1, そうでなければ bit[i] が 0 であることが分かるため、元のビット列が復元できる。

r, q が未知の場合は上記の手順をとることができないため、復号は容易ではないが幾つか破る方法が存在する。この辺りの話は格子の数学と関わりが深いらしい。初めはこちらの解説に沿って復号を試みた。ざっくり言ってしまえば、{[1, 0, 0, ..., 0, b_1], [0, 1, 0, ..., 0, b_2], ..., [0, 0, 0, ..., 1, b_n], [0, 0, 0, ...,0, -c]} という基底からなる格子のうち原点から最も近い点を探せば、その点の座標が復元したいビット列に対応することを利用する。格子のうち原点から最も近い点を探す問題は Shortest vector problem (SVP) として知られており、LLL Algorithm を使って近似解を求めることができる。ちなみに厳密解を求める問題は NP 困難らしい。初めは LLL Algorithm を自力で実装して N=10 くらいであれば解けることを確認したが、いざ問題を解こうとするとあまりの遅さに絶望した。諦めてライブラリなど探し回った結果、sagemathというツールがあったのでそれを使った。 LLL() という関数がいて高速に LLL Algorithm を終わらせてくれるので胸躍らせたが、実行してみると厳密解にまではたどり着いてくれず答えを出すことはできなかった。考えてみればあくまでも近似解法なので解ける保証はない。試した感覚だと次元が小さいうちは答えを出せる確率が高いが、次元が 100 を超えてくると基本的に答えは出ない。

ここで一回心が折れた。

しかしそれでも諦めきれなかったので、Shamir Attack という攻撃方法を試してみることにした。何個か文献を読んだので参考にしたものを貼り付けておく。
http://arxiv.org/ftp/arxiv/papers/1210/1210.8375.pdf
https://www.ifor.math.ethz.ch/teaching/lectures/integer_prog_ss10/chapter06
http://cacr.uwaterloo.ca/techreports/2004/cacr2004-08.pdf
先の方法では bit[i] を直接求めようとしたが、Shamir Attack では r, q に相当する数を見つけることで暗号を破る。 r, q と完全に一致しなくても、掛けて剰余をとることで superincreasing な配列を復元できれば、復号することは可能になる。詳細は省くが、|b[i]/b[0] - k[i]/k[0]| が極めて小さくなるような k[i] を求め、(k[0] * b[i]) % b[0] として b を superincreasing な配列に変換することができる。 |b[i]/b[0] - k[i]/k[0]| が極めて小さくなるような k[i] を求める問題（有理数が複数与えられたとき、同一の分母で極めて近い値の有理数を求める問題）は simultaneous diophantine problem と呼ばれており、これも LLL アルゴリズムによって解くことができる。

simulatenous diophantine problem を解くため、次のような sage スクリプトを書いた。 LLL アルゴリズムでは近似解しかでないので、精度が高くなるように a[0, n-1] の部分は調整してある。

f = open('b.txt')
t = f.readline().rstrip().split(', ')
t = [ long(x) for x in t ]
f.close()

f = open('c.txt')
s = long(f.readline().rstrip())
f.close()

n = len(t)

a = Matrix(ZZ, n, n)
for i in xrange(n-1):
   a[0, i] = t[i+1]
for i in xrange(n-1):
   a[i+1, i] = -t[0]
# smaller, more precise approximation
# a[0, n-1] = int(floor(pow(t[0], 1.0/n)))
a[0, n-1] = int(floor(pow(t[0], 1.0/n))/2)

f = open('m.txt', 'wb')
f.write(a.str())
f.close()

b = a.LLL()

# find the shortest vector
m = -1
r = -1
for i in xrange(n):
    s = 0
    for j in xrange(n):
        s += b[i, j] * b[i, j]
    if m == -1 or m > s:
        m = s
        r = i

# check if simultaneous diophantine problem is correctly solved
k = [0] * n
k[0] = b[r, n-1] / a[0, n-1]
for i in range(1, n):
    k[i] = (k[0] * t[i] - b[r, i-1]) / t[0]
for i in range(1, n):
    print float(t[i])/t[0], float(k[i])/k[0]

無事 simulatenous diophantine problem が解けたので、上記スクリプトの k[0], t[0] を U.txt, M.txt として保存して次のスクリプトで superincreasing な配列を作成し、フラグを出した。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-

import sys

def input_b():
    f = open('b.txt')
    line = f.readline()
    bstr = line.split(', ')
    b = [long(s) for s in bstr]
    f.close()
    return b

def input_c():
    f = open('c.txt')
    line = f.readline()
    cstr = line.rstrip()
    c = long(cstr)
    return c

def input_U():
    f = open('U.txt')
    line = f.readline()
    cstr = line.rstrip()
    U = long(cstr)
    return U 

def input_M():
    f = open('M.txt')
    line = f.readline()
    cstr = line.rstrip()
    M = long(cstr)
    return M 

def main():
    b = input_b()
    c = input_c()
    U = input_U()
    M = input_M()

    b2 = [0] * len(b)
    for i in range(0, len(b)):
        b2[i] = (b[i] * U) % M
    c2 = (c * U) % M

    used = [0] * len(b)
    p = c2
    for i in range(len(b)-1, 0, -1):
        if p >= b2[i]:
            used[i] = 1
            p -= b2[i]
        else:
            used[i] = 0
    q = c
    for i in range(1, len(b)):
        if used[i]:
            q -= b[i]
    if q > 0:
        used[0] = 1
        q -= b[0]
    flag = hex(int(''.join([str(bit) for bit in used]), 2))[2:-1].decode('hex')
    print flag


if __name__ == '__main__':
    main()

実行すると flag={AdiShamirSpoiled} と出てきた。とても疲れた。

攻撃術

craSH

スタックを壊した。

与えられたシェルでは、入出力のリダイレクトを読み込むときに、'>' もしくは '<' を見つけ、その後ろのスペース以外の文字列を読み込んだ後、読み込みが終わった箇所をスペースで塗りつぶす (get_redirect)。スペース以外の文字列を読み込む関数 (extract_str) は、左から見ていって ' ', '>', '<', '\0' のいずれかが見つかったところを文字列の終端として読み込む。そして、終端の次の位置を返す。 get_redirect で塗りつぶすスペースの箇所は '>' または '<' から extract_str の返り値の直前までとなっている。つまり、状況によっては本来消されるべきではない '>', '<', '\0' がスペースに変換されてしまう。

試しに次のようにコマンドを打ってみる。

$ echo foo > a
$ echo bar > b
$ cat < a>b
bar

3つ目のコマンドは本来何も標準出力されないはずだが、入力のリダイレクトを読み込んだ後、'>' が ' ' に変換されて

cat     b

が残り、bar が標準出力される。

幸運なことに文字列の終端文字 '\0' も消すことができるので、これを利用して入力用のバッファ (input) のところでオーバーフローを狙う。その一連の流れがこれ。

$ echo foo > a
$ echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa > < a
$ $ ls
`�.�� a

なんでもいいが、あらかじめ入力リダイレクト用のファイルを作っておく。 fgets で最大127バイト読み込まれるので、改行は input の中に入らず、input の最後6バイトは > < a\0 となる。入力リダイレクトを読み込んだ時点で、終端の '\0' が ' ' に変わる。次に出力リダイレクトを読み込むと、input の128バイトの領域を超えた先の ' ' 以外の連続する文字列がリダイレクト先として読み込まれてスペースで塗りつぶされる。 ls でファイルを確認すると、怪しげなバイト列がファイル名になったファイルが存在する。

一回投げただけではシェルが落ちないので、このコマンドを何度も投げ続けると最終的にスタックの領域外に書き込もうとするのかエラーで落ちる。 python で適当な間隔で投げ続けるようにしてしばらく待ったらフラグが出てきた。

flag={NoMoreBashdoor}

これで解けたのは良かったが、結局ヒープオーバーフローの方法がわからず craSH 2 に歯が立たなかったのは残念。

Ninja no Aikotoba

合言葉を一個ずつ答えていく。

一つ目と二つ目はアスキーコード表など参照して文字におこすだけ。それぞれ 'Yama' と 'too'。

三つ目は encrypt 関数が微妙に難読化されているが、配列の添字演算子[] のオペランドが交換可能なことに注意すると、やっているのはこれだけ。

for x in range(6):
    result[x + 6] = ((ans[x] & ans[x+6]) << 1) + (ans[x] ^ ans[x+6])
    result[x] = ans[x] - ans[x + 6]

表示される最初の6つの数字から、ans[x], ans[x+6] の差分がわかるので、アルファベットの中から虱潰しに合うものを探す。答えは 'KansaiTanaka'。

四つ目は MD4 でハッシュにされているが、四文字だとわかっているので全探索する。答えは 'Zach'。

最後はノーヒントだが、is_matched のバグで潜り抜けられる。 strcmp の返り値は負か0か正かで判定すべきところが、-1 か 1 なら一致しないと判定されている。いろいろと試したところ、24文字以内であれば異なる文字列の場合1か-1が返ってくるが、24文字目まで同じで25文字目以降が異なる場合は、最初に異なった文字のアスキーコードの差が返ってくる。 YamatooKansaiTanakaZachまでで23文字あるので、24文字目をa~z, A~Zとして、25文字目はa,Aの2種類で試し後ろに適当に8文字以上付け加えればOK。自動で流し込んだところ、'xaaaaaaaaaaaaaaaaaaaaaaa' を入力したところでフラグが出た。

flag={GetsuFumaDen}

liniku's blog

場阿忍愚CTF writeup (1)

芸術