BCTF 2015 experiment (English version)
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
According to the description, we can get flag after solving 50 questions. It seems easy, isn't it?
First 10 are questions judging the answer is integer or not.
Then, problems changed to asking about a sequence.
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:
First several are fixed problems, but others are random.
We are given about 2 minutes, so we have enough time to solve it.
The sequence are found in THE ON-LINE ENCYCLOPEDIA OF INTEGER SEQUENCES with the very same description.
I calculated the number based on it many times, then I noticed that the answer was in the calculated table in LINKS section.
Last 5 questions, we couldn't solve with the same way!
Luckily, they are fixed problems but needed little long time to find the answer.
Q46: Prime number (n is over 20 million)
Q47: Very large Catalan number
Q48: Number of sets of rooted connected graphs where every block is a complete graph.
Q49: Shapes of height-balanced AVL trees with n nodes.
Q50: a(n) = number of partitions of n (the partition numbers) modulo 1000000007
Although I couldn't understand the means of Q48-50, I copy-and-pasted expressions to Pari/GP and Mathematica and made my computer work hard.
Q46
? prime(23338403) %1 = 439756091
Q48
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}]
Q49
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 function is a very important technique. Without it, this calculation took very very long time and the question would be time out.
Q50
? {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
? a(23370) % 1000000007
%2 = 438545155
Finally, I wrote code below.
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()
This program works fine once every 3 times. Programming is difficult.
BCTF{Y0u_h4ve_m0ar_7ermz_than_205}
BCTF 2015 experiment
--- 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}
SECCON 2014 Finals
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
HomebrewでBottleを使わずソースからインストールする
メモです。
--build-from-source をインストール時に指定すれば行けるらしい。
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日目
16日目(@Segmentation fault(core dumped)
[:embed]
Apacheのmod_mimeの挙動が危なっかしい
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アプリがあると普通にこの挙動の影響を受けるところでした……
MacVimで日本語が文字化けする
set guifontwide=ヒラギノ角ゴ\ Pro\ W3:h15
KaoriYa MacVimだと何故かこの設定を読んでくれないのでbrew install macvimする。