読者です 読者をやめる 読者になる 読者になる

0ctf 2017 writeup

チーム yharima として参戦。 Welcome を除くと、onetimepad と integrity の二問だけしか解けず。

onetimepad

暗号化に使われたスクリプトと暗号文が渡されるので、それを復号する、そんな問題。

16byteの鍵と平文(16byte)をXORにかけて暗号化するが、鍵の生成法は次の通り(問題より抜粋)

def process(m, k):
    tmp = m ^ k
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

def keygen(seed):
    key = str2num(urandom(32))
    while True:
        yield key
        key = process(key, seed)

暗号文が三つ(16byte×3)、平文が二つ与えられるので、二つ分の鍵がわかる。 フラグの暗号用の鍵は一番最初に作られていて、その後生成された二つの鍵が既知。

結局のところ、process(m, k) の中の res が与えられたときに tmp を求めることができればよい。 これができれば既知の鍵二つから seed が求められ、seedと既知の鍵が分かっていれば一つ前に生成された鍵が求められる。

ここで、次の部分の処理にだけ注目する。

    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp

この処理を行うと元のビット列の間に 0 を挟んだものが結果となる。 tmp == 0b101 であれば res == 0b10001 になり、tmp == 0b1111 であれば res == 0b1010101 になる。 つまり、下から偶数番目のビットが必ず 0 になる。 この tmp * tmp 的な値を復元していく。

実際は if (res >> 256): res = res ^ P の処理が入るため、そうはならない。 しかし、ここで P の下位12bit に着目すると 0b0010000100101 となっており、下から偶数番目のビットが 1 となっているのは、6ビット目だけ。 基本的には、res の偶数番目のビットが立っていればそれは res = res ^ P の影響であることになる。 このことから、下位 bit から少しずつ復元が可能になる。 ただし、res = res ^ P で立ったビットがシフトされることにより再度 res = res ^ P されることも考慮すると、このやり方では6ビットは一意に特定できない。 6ビットだけ全探索して、tmp * tmp 的な値を気合で復元し、奇数番目のビットだけ抜き出すと res の候補がでる。

コードは下のようになった。

#!/usr/bin/env python
# coding=utf-8

def encode(tmp):
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

def str2num(s):
    return int(s.encode('hex'), 16)

def decode(k):
    for x in range(1 << 6):
        t = k
        for i in range(6):
            if x & (1 << i):
                t ^= 0x425 << i

        if t & 0b10101010:
            continue

        bh = x
        t = x << 256 | t
        for i in range(6, 256):
            if i % 2 == 0 and t & (1 << (i + 5)):
                bh ^= 1 << i
                m = 0x425 << i
                t ^= m
                if m >= (1 << 256):
                    bh ^= m >> 256
        y = bh << 256 | t

        b = 0
        for i in range(0, 512, 2):
            if y & (1 << i):
                b |= 1 << (i/2)

        if encode(b) == k:
            return b


P = 0x10000000000000000000000000000000000000000000000000000000000000425L
ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
fake_secret1 = "I_am_not_a_secret_so_you_know_me"
fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe"
f1 = str2num(fake_secret1)
f2 = str2num(fake_secret2)

k2 = ctxt2 ^ f1
k3 = ctxt3 ^ f2
d2 = decode(k2)
d3 = decode(k3)
seed = k2 ^ d3
k1 = seed ^ d2
f = k1 ^ ctxt1
print hex(f)[2:-1].decode('hex')

復号すると t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY が出る。 フラグの形式で提出しておわり。

他の方の writeup を見るとこれはガロア体における平方根を出す問題だったらしい。。。 ガロア体を知らずに解けたのは運がよかっただけっぽい。 ガロア体を勉強するいい機会になりました。

integrity

サーバに繋ぐと AES-CBC をもとにした暗号化と復号化ができる。adminだけ暗号化できないのだが、復号化して admin となる文字列を与えることができればフラグが出る。そんな問題。

暗号化は AES-CBC そのままではなく、以下のようになっている(問題より抜粋)。pad は16byteの倍数になるよう後ろにパディングするだけの関数。

    def encrypt(self,raw):
        raw = pad(raw)
        raw = md5(raw).digest() + raw

        iv = Random.new().read(BS)
        cipher = AES.new(self.key,AES.MODE_CBC,iv)

        return ( iv + cipher.encrypt(raw) ).encode("hex")

入力文字列に対して md5 を付け加えているのがミソ。 まず、適当な16文字の後に admin と付け足した文字列 (0123456789012345admin) を暗号化してやる。 CBC モードでの解凍は後ろのブロックから順に行われ、iv は最初のブロックに影響を与えるだけなので、iv を除いた暗号文の最初16byteを削っても admin のブロックは正しく復号化される。 後は先頭のブロックの復号結果が md5(pad('admin')) になるよう iv を調整するだけ。

変数名がとても雑だが下のようなコードで、復号結果が admin の文字列を生成できる。

t = '0123456789012345'
a = 'admin'
p = t + a
c = scheme.encrypt(p)
d = int(c[32:64],16)
e = int(t.encode('hex'), 16)
f = int(md5(pad(a)).hexdigest(), 16)
x = d ^ e ^ f
y = hex(x)[2:-1] + c[64:128]
print scheme.decrypt(y)

あとはこれの暗号/復号部分をソケット通信でやるように置き換えるなどして終わり。 フラグは flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}

志半ばで終わった問題たち

  • simplesqlin
    • WAF が破れなかったのでスキーマやテーブルを漁れず死亡
  • Temmo’s tiny shop
    • ほぼお買い物しただけ
  • onetimepad2
    • 式を弄って A^N を出せたっぽいが、そこから N を求めることができずに結局復号できず
    • Discrete logarithm?

AlexCTF 2017 write up

チーム yharima で参加したので、write up を書いておく。 暗号ばっかり解いていた。

CR2

問題文を読むと、one time pad を使ったけど one time と呼ばれる意味が分かっていない、的なことが書いてあったので、鍵が使いまわされているんだろうなあと予想。

one time pad といっても色々あるらしいのだが、XORで暗号文を作ると予想して、次のリンクにある通り解読を試みた。
http://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse/64

鍵をK、平文をTとしたときに、暗号文Cは鍵と平文の XOR をとったもの。

C = K ⊕ T

同じ鍵の暗号文が複数用意されている (C1, C2) とき、暗号文どうしの XOR をとると、鍵の影響を排除できる。

C1 = K ⊕ T1
C2 = K ⊕ T2
C1 ⊕ C2 = (K ⊕ T1) ⊕ (K ⊕ T2)
        = T1 ⊕ T2

C1 ⊕ C2に対し、平文に入っていそうな単語で適当な位置のXORをとってみて、結果が読める文になるところを探す。見つかった場合、その部分の平文が明らかになったことになる。ただし、元の単語と XOR の結果のどちらが C1 に含まれるのかはわからない。

問題のテキストは 11 行になっていたので、hex から byte に変換してから、適当な2行を選んで思いついた単語が入っているか確認していった。

結果、どうやら3行目に crypt という文字列が含まれているらしいことがわかった。 これで、次のような感じの平文になっていることが判明したので、あとは左右にそれっぽい文字がくるよう適当に伸ばしていけば全部解読できた。

___________________ime I__
___________________e and__
___________________crypt__
___________________hat i__
___________________ion m__
___________________tical__
___________________racke__
___________________kept __
___________________f you__
___________________ this__
___________________ways.  

解読結果はこちら。

Dear Friend, This time I u
nderstood my mistake and u
sed One time pad encryptio
n scheme, I heard that it 
is the only encryption met
hod that is mathematically
 proven to be not cracked 
ever if the key is kept se
cure, Let me know if you a
gree with me to use this e
ncryption scheme always. 

結局、鍵がフラグだった。
ALEXCTF{HERE_GOES_THE_KEY}
(初めからALEXCTF{とXORとっていけばよかった)

CR4

RSAの問題。 とりあえず modulus を見てみる。

$ openssl rsa -noout -text -in key.pub -pubin
Public-Key: (399 bit)
Modulus:
    52:a9:9e:24:9e:e7:cf:3c:0c:bf:96:3a:00:96:61:
    77:2b:c9:cd:f6:e1:e3:fb:fc:6e:44:a0:7a:5e:0f:
    89:44:57:a9:f8:1c:3a:e1:32:ac:56:83:d3:5b:28:
    ba:5c:32:42:43
Exponent: 65537 (0x10001)

399 bit の RSA コンテストはなかったが、factordb に聞いたら素因数分解してもらえた。 あとは Wikipedia にある通り、例の式に従って復号。
フラグは ALEXCTF{SMALL_PRIMES_ARE_BAD}

CR5

nc でつなぐと、次の数字を教えてもらうか、予想の入力をすることができる。 教えてもらうと乱数列が返ってくるので、これを予想すればいいっぽい

線形合同法では?、と思い次のリンクの通り乱数列の予測を試みた。
security.stackexchange.com

リンク先に書いてある通りだが、ここにもまとめておく。

x[n + 1] = a * x[n] + b (mod m)

より

x[n + 1] - x[n] = a * (x[n] - x[n - 1]) (mod m)

となるので、

y[n] = x[n + 1] - x[n] (mod m)

とおくと、

y[n + 1] = a * y[n] (mod m)

よって

y[n + 2] * y[n] - (y[n + 1])^2 = 0 (mod m)

これにより、y[n + 2] * y[n] - (y[n + 1])^2 を十分な数の n について集め、最大公約数をとれば、m が求められる。

あとは、y[1] = a * y[0] (mod m) を解いて a を出して、x[1] = a * x[0] + b (mod m) を解いて b を出すだけ。

最初の10回くらいは聞いて、それをもとに m, a, b を求め、乱数列を出す。 10回連続で正解すると、フラグを出してくれた。

flag is ALEXCTF{f0cfad89693ec6787a75fa4e53d8bdb5}

書いたスクリプトはこんな感じ。

#!/usr/bin/env python

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b:
        a, b = b, a%b
    return a

def egcd(a, b):
    x, lx = 0, 1
    y, ly = 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, lx = lx - q * x, x
        y, ly = ly - q * y, y
    return lx, ly

x = [
    4251151823,
    2502705517,
    4101273005,
    1396379746,
    4159332548,
    3671236567,
    433240385,
    465003001,
    2767252763,
    952274152
]

# x[i + 1] = a * x[i] + b (mod m)
# y[i + 1] = a * y[i] (mod m)
y = []
for i in range(len(x) - 1):
    y.append(x[i + 1] - x[i])

# z[i] = y[i + 2] * y[i] - (y[i + 1])^2 = 0 (mod m)
z = []
for i in range(len(y) - 2):
    zz = y[i + 2] * y[i] - y[i + 1] * y[i + 1]
    if zz < 0:
        zz = -zz
    z.append(zz)

m = z[0]
for i in range(len(z)):
    m = gcd(m, z[i])

for i in range(len(y)):
    while y[i] < 0:
        y[i] += m

# p * y[0] + q * m = r (mod m)
# p * y[0] = r (mod m)
p, q = egcd(y[0], m)
r = (p * y[0]) % m
# y[1] = a * y[0]
# p * y[1] = a * p * y[0] = a * r
a = ((y[1] / r) * p) % m

# a * x[0] + b = x[1] (mod m)
# b = x[1] - a * x[0] (mod m)
b = (x[1] - a * x[0]) % m

print "check y"
yy = []
yy.append(y[0])
for i in range(len(y) - 1):
    t = (a * yy[i]) % m
    yy.append(t)
    print y[i + 1], yy[i + 1], (y[i + 1] - yy[i + 1])

print

print "check x"
xx = []
xx.append(x[0])
for i in range(len(x) - 1):
    t = (a * xx[i] + b) % m
    xx.append(t)
    print x[i + 1], xx[i + 1], (x[i + 1] - xx[i + 1])

print

print "show x"
xx = []
xx.append(x[0])
for i in range(29):
    t = (a * xx[i] + b) % m
    xx.append(t)

for i in range(len(xx)):
    print '{0}\t{1}'.format(i, xx[i])

次CTFに参加するときは暗号以外も解きたい。

2017年書き初め

正月を過ぎてしまったが、新年ということで初心者ながら短歌を詠んだので記事にする。

55 31 db eb 13            
2d 80 33 e1 01 78 08
2d f0 c7 67 58
79 f2 43 89 d8 5d c3
6a 0d 58 cd 80 eb ed

Linux/x86 向けのアセンブラ短歌になっている。

ソースは次の通り。

    .intel_syntax noprefix
    .section .text
    .global main
    .type main, @function
main:
    push ebp             /* 1 */
    xor ebx, ebx         /* 2 */
    jmp 4f               /* 2 */
1:  sub eax, 0x01E13380  /* 5 */ # 365 * 24 * 60 * 60
    js 3f                /* 2 */
2:  sub eax, 0x5867c7f0  /* 5 */ # 2017-01-01 00:00:00 JST
    jns 1b               /* 2 */
    inc ebx              /* 1 */
3:  mov eax, ebx         /* 2 */
    pop ebp              /* 1 */
    ret                  /* 1 */
4:  push 0x0d            /* 2 */
    pop eax              /* 1 */
    int 0x80             /* 2 */
    jmp 2b               /* 2 */

現在時刻を取得し、2017年であれば終了ステータス0で正常終了し、そうでなければ終了ステータス1で終了する。

上のソースを in2017.S というファイル名で保存し、動作確認をしてみる。

$ gcc in2017.S -o in2017 -masm=intel -m32
$ ./in2017 && echo 2017
2017

今は 2017 年のようだ。 時刻を変えて確認する。

$ sudo date -s "2016-12-31 23:59:59"; ./in2017 || echo "not 2017" 
2016年 12月 31日 土曜日 23:59:59 JST
not 2017
$ sudo date -s "2017-01-01 00:00:00"; ./in2017 && echo "2017"
2017年  1月  1日 日曜日 00:00:00 JST
2017
$ sudo date -s "2017-12-31 23:59:59"; ./in2017 && echo "2017"
2017年 12月 31日 日曜日 23:59:59 JST
2017
$ sudo date -s "2018-01-01 00:00:00"; ./in2017 || echo "not 2017" 
2018年  1月  1日 月曜日 00:00:00 JST
not 2017

確かに2017年かどうかを判別できている。

初めは2017年であれば「🐓」とでも表示する短歌を作ろうと思ったのだが、力不足で完成させられなかった。「🐓」と表示する代わりに、ジャンプ系の命令を多く配してみた。5句中4句にジャンプ命令が含まれている。

書き初め風に言えば、「飛躍の年」だ。
幸多き年になりますように。

場阿忍愚CTF writeup (1)

少し前まで開催されていた場阿忍愚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] を足し合わせていく。
rq が既知の場合は 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}

とりあえず最初の記事

書いたものを公開する場所を持ち合わせていなかったので開設した。

備忘録を兼ねて、技術的なことなど気が向いたときにでも書く。