2015-03-23

BCTF 2015 experiment

CTF

--- English version is here (poor English)---

Hi, we have a short survey with 50 questions. You can get a flag as award once you finished it.
$ nc 104.197.7.111 13135

問題文によれば、50問問題を解けばフラグをくれるらしい。簡単っぽい？

最初の10問は四則演算の結果が整数か否かを答える問題。
次に、

Description: The prime numbers.
The sequence starts with: 2,3,5,7,11,13,17,19,23,29
(first term is for n = 1)
n = 2418, Answer:

のような問題が出されるので、該当する数を答える。
ちなみにはじめ数問は固定の問題だったが途中からは完全にランダムな問題になった。
制限時間はそこそこ長く、1~2分くらい放っておいても大丈夫。

数列をオンライン大数列辞典で検索すると、全く同じDescriptionの数列があることがわかる。
それを元に人力で何度も計算して解いていると、LINKSの欄に計算済みの値が載っていてかつ問題で提示されるnが含まれていることに気づいた。

最後の5問はちょっと形式が変わって、計算済みの値が載っていない問題が出題された。

46問目: 2000万オーバーの順番にある素数
47問目: リストに載っていないカタラン数
48問目: Number of sets of rooted connected graphs where every block is a complete graph.
49問目: Shapes of height-balanced AVL trees with n nodes.
50問目: a(n) = number of partitions of n (the partition numbers) modulo 1000000007

最後の方はなんだかよくわからない。Pari/GPとかMathematicaに式をコピペしてCPUをぶん回した。
46問目

? prime(23338403)
%1 = 439756091

48問目

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[ j]}]*b[n-j], {j, 1, n}]/n]; b]; b = etr[aa]; c = etr[b]; aa = Function[{n}, If[n == 0, 0, c[n-1]]]; a = etr[aa]; Table[a[n], {n, 0, 700}]

49問目

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, Expand[x+B[x^2+2*x*y, x, d, a+b, a]], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; 
a[1298]

計算式内にExpandを入れると計算量が減って速く解ける。
これに気づいていなければ永遠に解けなかった。

50問目

? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
? a(23370) % 1000000007
%2 = 438545155

以下、コードです

import re
import time
import gmpy
import sympy
import requests
from pwn import *
 
s = remote('104.197.7.111', 13135)
s.recvuntil("Okay, let's begin with simple questions.\n")
 
problem_number = 1
 
for _ in range(10):
    print 'No. %d --------------------------' % problem_number
    x = s.recvuntil('Answer (yes/no): ')
    print x
    m = re.search('Is (.+) an integer or not?', x)
    expr = m.group(1)
    try:
        ans = str(safeeval.expr(expr))
        print expr
        print ans
        if ('.' not in ans) or re.search(r'\.0+$', ans):
            s.send('yes\n')
        else:
            s.send('no\n')
    except:
        s.send('no\n')
    problem_number += 1
 
print s.recvuntil('Time for calculating weird integer sequences.')
 
for i in range(35):
    print 'No. %d --------------------------' % problem_number
    s.recvuntil('Description: ')
    desc = s.recvuntil('\n')[:-1]
 
    buf = s.recv(1)
    seq = None
    if 'T' in buf:
        s.recvuntil('starts with: ')
        seq = s.recvuntil('\n')[:-1]
 
    print 'Description:', desc
    print 'The sequence starts with:', seq
    search = 'name:"%s"' % desc
    if seq and len(seq) < 40:
        search += ' seq:"%s"' % seq
 
    print 'Searching %s' % search
    res = requests.get('http://oeis.org/search', params={'q': search})
 
    m = re.search('<a href="/A([0-9]+)"', res.text)
    num = m.group(1)
    print 'found page:', num
 
    res = s.recvuntil('Answer: ')
    m = re.search(r' = (\d+), ', res)
    n = int(m.group(1))
    print 'n = ', n
 
    res = requests.get('http://oeis.org/A%s/b%s.txt' % (num, num))
    m = re.search('^%d +(-?[0-9]+)' % n, res.text, re.MULTILINE)
    if m is None:
        print 'not found'
        ans = raw_input('Input answer: ')
    else:
        ans = int(m.group(1))
    print 'Answer =', ans
    s.send(str(ans) + '\n')
    problem_number += 1
    time.sleep(0.2)
 
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
print 'n = ', n
ans = raw_input('Input answer: ')
print 'Answer =', ans
s.send('%s\n' % ans)
problem_number += 1
 
print 'No. %d --------------------------' % problem_number
s.recvuntil('Description: ')
desc = '"' + s.recvuntil('\n')[:-1] + '"'
s.recvuntil('The sequence starts with: ')
seq = s.recvuntil('\n')
res = s.recvuntil('Answer: ')
m = re.search(r'n = (\d+), ', res)
n = int(m.group(1))
ans = sympy.binomial(2*n, n)/(n+1)
print 'Answer =', ans
s.send('%d\n' % ans)
problem_number += 1
 
s.interactive()

ちなみにこのコードは3回に1回くらいしか完走してくれない、プログラミングは難しい。

BCTF{Y0u_h4ve_m0ar_7ermz_than_205}

2015-02-09

SECCON 2014 Finals

f:id:xrekkusu:20150209090547p:plain

12位でした。
dodododoはWebを全完目標、バイナリでそれを支えるみたいな感じでCTFで上位に入ることが多いのですが、今回は残念ながらWebが振るわずちょうど真ん中くらいの順位になってしまいました。

自分が解いたのはサーバ六の暗号1~3です。1~3はどれもよく見れば答えがわかる問題だったのでやるだけでした。

以下暗号問題1~3のwriteupです。

暗号1

暗号文はメモり忘れていたのでありません。（変換しなおせば作れるが面倒）
明らかに単一換字式暗号なので文字種が全部入った文字列を暗号化して対応を取る。やるだけ。

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ__
↓
HaXKTnOV_7QSqYgIjkdurJz28AwP0U5D1Zb3RhW4NCBlFexfymtp/oELivM69css

Plaintext: Password_can_learn_rock_do_Style_you_situation_find_A_and_write_to_while_mainly_occurred_has_hacker_the_or_use_wrote_read_right_
Flag: SECCON{tyhoie_o}

他の問題でもそうですが、フラグは与えられたCiphertextと同じ文字列を生成できたときにその末尾に付加されていました。

暗号2

単一換字式暗号らしいがなにか様子がおかしい。1文字ずつ増やしていくと3文字ごとに換字暗号のテーブルが同じになったので、(文字数%3)を取って換字暗号のテーブルを変更していると予測。あとは1番と同様に解きました。

Plaintext: Password_1985_hackers_make_best_1996_identification_a_hacker_is_administration_myself_why_the_time_well_may_is_the_should_title_
Flag: SECCON{_utr_urs}

暗号3

AA...AA (128chars)を暗号化すると前半64文字と後半64文字が同じになります。
AA...AA (64chars)ではこう。

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
↓
f/c2ZwO_dEayogPD7nCRNTX59rJWLF3S6Qj1YeBpiIt0bUvkmzVMG48KxHhlsquA

BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
↓
piIt0bUvkmzVMG48KxHhlsquAf/c2ZwO_dEayogPD7nCRNTX59rJWLF3S6Qj1YeB

Plaintextの1文字を変えるとそこに対応したCiphertextの1文字が変わる。加えて64文字目だけが何故か暗号化されていないということに気づく。その後、BB...BB (64chars)ではCiphertextがAのときと似ているが位置がずれていることがわかる。

このことから文字ごとにテーブルを生成して、n文字目が暗号文と一致するテーブルを生成した元の文字が平文と予想しました。言葉で説明しても複雑なのがわかると思いますが、脳内でこの整理をするのにちょっと時間がかかりました。

次のようなコードを書いて全文字種に対するテーブルを生成して、なんとかする。

table = 'f/c2ZwO_dEayogPD7nCRNTX59rJWLF3S6Qj1YeBpiIt0bUvkmzVMG48KxHhlsquA' * 2
for i in range(len(chars)):
    subtable[chars[i]] += table[table.find(chars[i])+1:][i]

Plaintext: missing
Flag: SECCON{ea_ubsec}

暗号4

平文に突っ込まれた文字が1種類だとランレングス圧縮、2文字以上ならハフマン法らしい。確かに暗号化できてるけど……という問題。解けなかった代わりに平文をメモってあったので貼っておきます。

AAAAgBX7KsK03QWS3Leud1FmWe5LyodjFstpL6Eo1JFKpioWItFrXBdrv6Vrf9ZwOK3TmBqriKkisDVXD/E45TcNOQUwNumw8L8pNiO4vLfxzsz6FYGDMB25IvYwO2ZI6qzbhOMi4dfSGkQfd8h5YAB

2014-12-24

HomebrewでBottleを使わずソースからインストールする

メモです。

--build-from-source をインストール時に指定すれば行けるらしい。

homebrew/Bottles.md at master · Homebrew/homebrew · GitHub

2014-12-15

coins+brew=神(?)

この記事はcoins Advent Calendar 2014の15日目の記事です。

0. 駄文

筑波大学の情報科学類(通称coins)では学内に100台を優に超すiMacが設置されていて、coins生ならば誰でも自由に使うことが出来ます。(例外)

しかし、大学が管理するMacなのでRubyやPythonのバージョンが古いなど、不満な点もいくつかあります。これを解決するためには自分でパッケージをビルドしてユーザーディレクトリ下に置くか、管理者の元へ突撃して宗教戦争を行うしかありません。

ただ、大体の場合、パッケージが「今すぐ」必要であったり、バージョンアップに追従しにくいことから、前者の手段を取ることになるでしょう。

MacではHomebrewというパッケージ管理アプリがよく利用されていますが、これはもともと管理者権限なしでも動くようにできているため、制限された環境で利用するのには最適です。

早速導入してみましょう。

1. 導入

% git clone https://github.com/Homebrew/homebrew.git ~/.brew
% export PATH="$HOME/.brew/bin:$PATH"

これだけです。びっくり。

2. パッケージのインストール

coins環境のVimは古く、また当然Luaも使えないので非常に不便です。
さくっとLua付きのVimを入れてしまいましょう。

% brew install --with-lua --with-luajit vim

すごい。

% brew install tmux coreutils binutils

マシマシしていくぞ。

3. おわりのはじまり

brewの記事を書くつもりがなんと導入が簡単すぎて一瞬で終わってしまいました。
ですが重大なことをまだ話していません。

brewの導入はただのはじまりではなく、おわりのはじまりなのです。

というのも、一般的なcoins生のホームディレクトリというのは3GBの容量しかないため、ちょっと張り切ってパッケージを導入するとすぐに限界が来てしまいます。

Disk quotas for user s1411*** :
     Filesystem    1K blocks         quota        limit    grace   files   quota   limit   grace
          /home      2728855       3072000      3584000           128501       0       0

ちょっと前にヤバいと思ってDownloadsの中身とかを消したのですが、それでも9割の領域を使ってしまっています。

coins+brew=神にはなれなかった。終わり。

4. 神への道

4.1 coins-admin

coinsのマシンはcoins-adminという教員と学生によって構成された組織が管理しています。coins-adminに入るとホームディレクトリの容量が実際無限になるそうですが、管理があまり得意でないので入るのはちょっと厳しい気がしています。

adminになっちゃえば普通に神になってるのと変わらないよね。

4.2 気合

coins生が利用するマシンには「計算機利用の手引き」なるものが設置されていて、「ディスクスペースが足りない場合は適当な場所にメールを送ること」という記述があります。

文脈から察するに、正当な理由であればホームディレクトリの容量を増やすことができるしれないということです。
また、VMを利用したいという理由で申請したら通ったという話も(噂みたいなものですが)聞いています。

自分の場合は適当に整理して2.7GB/3GB程度の使用量なので、もっと綺麗にしてかつ2.9GB/3GBくらいまでディスクをたっぷり使ってからメールを送ってみたいと思います。

5. coins Advent Calendar 2014

14日目
<a href="http://negi-magnet.hatenablog.com/entry/2014/12/14/000258">MikuMikuWatch製作記 - ねぎらぼ</a>

16日目(@Segmentation fault(core dumped)
[:embed]

2014-11-06

Apacheのmod_mimeの挙動が危なっかしい

CTF Security

tkbctf#4のITF Point Systemの出題に使ったネタです。
知ったタイミングでブログ記事かなんかにしたかったのですが、問題に使うと決めてしまったので今の今まで書くことが出来ませんでした。

mod_mime - Apache HTTP Server Version 2.4

ファイルは複数の拡張子を持つことができ、拡張子の順番は通常は関係ありません。例えば、ファイル welcome.html.fr がコンテントタイプは text/html に、言語はフランス語にマップされる場合、welcome.fr.html もまったく同じ情報にマップされます。同じメタ情報にマップされる拡張子が複数あるときには、言語とコンテントエンコーディングを除いて、右側にあるものが使用されます。たとえば、.gif が MIME タイプ image/gif にマップされ、.html が MIME タイプ text/html にマップされる場合は、ファイル welcome.gif.html は MIME タイプ text/html に関連付けられます。

とApacheのドキュメントにありますが、要は存在する複数の拡張子の内、右から順番に見ていってApacheのMIMEに存在するものがあればそれを用いるという感じです。

これにより"abc.php.unknown"のような名前のファイルをApacheにphpとして認識させることが可能になります。tkbctf#4ではこの手法を用いて、ユーザー名をファイル名に含むSQLiteDBファイルにアクセスさせる問題を出題しました。

実際のところ、こんな話があるならいろいろな場所でPHP Remote Code Executionが発生して大事件になっている気がしますが、パッケージマネージャによってはその問題を回避するためか、下記のような設定が書かれています。

#...
<FilesMatch "\.php$">
    SetHandler application/x-httpd-php
</FilesMatch>
#...

この書き方であればファイル名の末尾にphp 拡張子があるときだけPHPとして実行させるということができるので安全になります。

ちなみに自分のMac上で動いているApacheでは普通にAddHandlerしていたため、うっかり[username].datみたいな謎ファイルを吐き出すようなWebアプリがあると普通にこの挙動の影響を受けるところでした……

2014-10-28

MacVimで日本語が文字化けする

set guifontwide=ヒラギノ角ゴ\ Pro\ W3:h15

KaoriYa MacVimだと何故かこの設定を読んでくれないのでbrew install macvimする。

2014-09-22

CSAW 2014 Bin300(2) weissman

0x13 + 9byteなchunkがたくさんあることからchunkの構造を推測し、データを読み込んでchunk情報だけを吐き出すスクリプトはすぐに書けた。
しかし、圧縮されていると思われるchunkだけどう展開したらいいかわからない。

「jpegの画像はバイナリデータだしほとんど圧縮効いてないんじゃないか」と気がついて、とりあえず圧縮chunkの部分を0x00で展開するようなスクリプトにしてみたら一応画像として読み込めるようになった。

f:id:xrekkusu:20140922173850j:plain

ギリギリ読める。

key{I know How long it'd take me, and I can prove it}

バランスを取りたい

よくCTFの記事を書きます