2015-04-06

KSNCTF #20 G00913

CTF KSNCTF

問題

ksnctf - 20 G00913

考えたこと

意味深なタイトルだけど意味がわからないやつはググる。
また脆弱性の名前かな〜とか思ってたら検索トップに KSNCTF の記事出てきたので固有名詞ではなさそう。

問題は ${\pi = 3.141592\dots}$ の中に出てくる最初の10桁の素数はなにかという問題で、ググれば出てきそうな気はする。ググったら出てきた。

${\pi}$ は

${\frac{\pi}{4} = \Sigma^\infty_{n=0}} \frac{(-1)^n}{2n+1}$

みたいな有名なやつから

${\pi = 426880\sqrt{10005} \left\{\Sigma^\infty_{n=0} \frac{(-1)^n(6n)!(13591409+545140134n)}{(3n)!n!^3 × 640320^{3n}} \right\}^{-1}}$

みたいなわけのわからん式でも表せるらしいので、ある程度大きい ${n}$ で計算して10桁ずつ区切って素数判定していけばよさそう。
と思って有名なほうでコード書いてみたけど、収束速度が遅くてちょっと無理そうだった。めんどくさくなったのでやめた。タイトルもググれって言ってることに気付いたのでやめてもいいと思う（適当）

2015-04-04

KSNCTF #17 Math II

CTF KSNCTF

問題

ksnctf - 17 Math II

考えたことはとくにない

まず問題の数 ${n}$ に対して ${10^k \leq n \lt 10^{k+1}}$ を満たす ${k}$ を2分探索で求めてその範囲でまた2分探索した。

コード書いた。

https://github.com/sekai013/ksnctf/blob/master/math2/math2.rb

走らせたらコード出た。

2015-04-04

KSNCTF #16 Math I

CTF KSNCTF

問題

ksnctf - 16 Math I

考えたこと

RSA 暗号というやつ。長くなったので別途まとめた。

RSA暗号について雑にまとめた - sekai013's blog

この問題は素因数分解できちゃったときにメッセージを解読できるよというやつ。

コード書いて走らせたら取れた。

https://github.com/sekai013/ksnctf/blob/master/math1/math1.rb

暗号おもしろくて結構好き。RSA のしくみはもともと本で読んですごいな〜と思って覚えてたのでなんとかなった。

2015-04-04

RSA暗号について雑にまとめた

RSA とは？

暗号化の方式. 暗号化における鍵配送問題を解決する公開鍵暗号を実現した画期的な方法. 発明者3人の名前から RSA という名前になった.

必要な知識

だいたい wikipedia に載ってる.
- オイラーのΦ関数

ruby で書くとこんな感じ

def euler(n)
  coprimes = (1..n).select {|k|
    n.gcd(k) == 1
  }
  coprimes.size
end

オイラーの定理

${ a\ と\ n\ が互いに素であれば\ a^{{\rm euler}(n)}\ と\ n\ は互いに素 }$
拡張されたユークリッドの互除法

${ a, b \in \mathbb{N}, a > b\ に対し }$

${ ax + by = {\rm gcd}(a, b) }$

${ となるような\ x, y\ を求めるアルゴリズム }$

${ r_0 = a, r_1 = b\ とするとユークリッドの互除法から }$

${ \left(\array{ r_0 = q_0r_1 + r_2 \newline r_1 = q_1r_2 + r_3\newline \vdots\newline r_n = q_n{\rm gcd}(r_0,r_1) + 0 }\right. }$

${ ここで }$

${ \left(\array{ \left(\array{r_0 \newline r_1}\right) = \left(\array{q_0\ 1\newline 1\ \ 0}\right) \left(\array{r_1 \newline r_2}\right) \newline \vdots \newline \left(\array{r_n \newline {\rm gcd}(r_0,r_1)}\right) = \left(\array{q_n\ 1\newline 1\ \ 0}\right) \left(\array{{\rm gcd}(r_0,r_1) \newline 0}\right) }\right. }$

${ より }$

${ \left(\array{r_0 \newline r_1}\right) = \left(\array{q_0\ 1\newline 1\ \ 0}\right)\dots \left(\array{q_n\ 1\newline 1\ \ 0}\right) \left(\array{{\rm gcd}(r_0,r_1) \newline 0}\right) }$

${ また }$

${ \left|\array{q_n\ 1\newline 1\ \ 0}\right| = -1\ より \left(\array{q_n\ 1\newline 1\ \ 0}\right)^{-1} = \left(\array{0\ \ \ \ \ \ 1\newline 1\ \ -q_n}\right) }$

${ よって }$

${ \left(\array{{\rm gcd}(r_0,r_1) \newline 0}\right) = \left(\array{0\ \ \ \ \ \ 1\newline 1\ \ -q_n}\right)\dots \left(\array{0\ \ \ \ \ \ 1\newline 1\ \ -q_0}\right) \left(\array{r_0 \newline r_1}\right) }$

${ この行列の積を計算すると\ (1,1)\ 成分から\ x\ が,\ (1,2)\ 成分から\ y\ が得られることがわかる. }$

RSA 暗号のしくみ

${ \left(\array{ m : 平文(もとのメッセージ) \newline p, q: 十分大きい素数(p \neq q) \newline n := pq \newline \phi(n) := {\rm euler}(n) = (p-1)(q-1) \newline e : \phi(n)\ 未満かつ\ e\ と\ \phi(n)\ は互いに素となるような自然数 }\right. }$

${ とする. }$

${ d : de \equiv 1 \mod \phi(n)\ となるような自然数を考えると,\ ^\exists k \in \{0,1,\dots\}\ に対して }$

${ de = k\phi(n) + 1 \Leftrightarrow de - k\phi(n) = 1\ とかける. }$

${ ここで,\ e\ と\ \phi(n)\ は互いに素であるから\ {\rm gcd}(e, \phi(n)) = 1 }$

${ よって拡張されたユークリッドの互除法により\ d\ を求めることができる. }$

${ ここで,\ c = m^e \mod n\ とすると, }$

${ c^d \equiv (m^e)^d \equiv m^{de} \equiv m^{k\phi(n)+1} \mod n }$

${m\ と\ n\ が互いに素であるとき}$

${ オイラーの定理より\ m^{\phi(n)} \equiv 1 \mod n }$

${ よって\ m^{k\phi(n)+1} \equiv 1^k ・ m \mod n }$

${ c\ から\ d,\ n\ によって\ m\ を復元可能. }$
${{\rm gcd}(m,n) = p\ のとき}$

${ m^{k\phi(n)+1} \equiv m \equiv 0 \mod p }$

${ m^{k\phi(n)+1} = m^{k(p-1)(q-1)+1} = \left(m^{q-1}\right)^{k(p-1)}・m \equiv 1^{k(p-1)}・m \mod q (オイラーの定理) }$

${ よって\ m^{k\phi(n)+1}\equiv m \mod n\ となり\ c\ から\ d, n\ によって\ m\ を復元可能. }$

${ \left(\array{ (命題)\ \ \ \ 自然数 n > 1, k > 1, 異なる {\rm 2} つの素数\ p, q\ に対し\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \newline n^k \equiv n \mod p\ かつ\ n^k \equiv n \mod q\ であれば\ n^k \equiv n \mod pq である.\newline (証明)\ \ \ \ 条件より適当な自然数\ a,b\ を用いて\ n^k - n = pa = qb\ とおける.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \newline a = qb/p\ とすると,\ a\ が自然数であることと, p,q\ が異なる素数であることから,\ b\ は\ p\ を因数にもつ }\right) }$

${ {\rm gcd}(m,n) = q のときも同様に復元可能 }$

一方 ${d}$ がわからないと ${m}$ の復元は困難(らしい)

アリスがボブにメッセージ ${m}$ を安全に送りたいとき

ボブは素数 ${p, q}$ と, ${(p-1)(q-1)}$ と互いに素な自然数 ${e}$ を用意して, ${n = pq, d}$ を計算する.
ボブは ${e, n}$ を公開する.
アリスは ${m}$ に対して ${m^e \mod n}$ を計算してボブに送信する.
ここで第三者キャロルにアリスが送信した暗号文を盗み見られたとしても, ${d}$ がわからないキャロルには暗号文を解読できない.
暗号文を受け取ったボブは秘密鍵 ${d}$ を用いて ${m}$ を復元してメッセージを読む.

という感じで安全に送れる. ${n}$ 公開されてるなら ${n=pq}$ だから ${p}$ も ${q}$ もわかって ${d}$ もわかるやん！
と言いたくなるけど, 巨大な素数の合成数の素因数分解しようと思ったらめちゃくちゃに時間がかかるのでまあ現実的には無理ということになっている.

思ったより長くなってしまった。見にくいけど腰が痛いのでぶん投げる。間違ってたら教えてください。

2015-04-02

KSNCTF #14 John

CTF KSNCTF

問題

ksnctf - 14 John

考えたこと

ぱっと見てわからなかったので意味ありそうなタイトル John でググるけど John が一般的すぎてそれっぽいのはひっかからない。

問題文見てたら user00, 01, ..., 20 ときていきなり 99 になっているのでなんだろうと思ったらメッセージだった。

user99:$6$SHA512IsStrong$DictionaryIsHere.http//ksnctf.sweetduet.info/q/14/dicti0nary_8Th64ikELWEsZFrf.txt:15491:0:99999:7:::

SHA512 is strong. Dictionary is here: http://ksnctf.sweetduet.info/q/14/dicti0nary_8Th64ikELWEsZFrf.txt

と読める。見てみたら単語がずらっとならんでて前問を思い出した。
どうやら何かが SHA512 で暗号化されているらしい。SHA512 は解けなさそう。

この辺でググりなおしてみる。john dictionary, john sha512 ときたところでそれっぽいのが出た。

John the Ripper を使って、パスワードクラック - ギリギリギリギリジンジンギリギリギリジンジンジン

John the Ripper というパスワードクラッカーがあるらしい。apt-get john で簡単にインストールできる。
John the Ripper のパスワード解析には

ユーザーネームからパスワードを推測する方法
john --single myPasswordFile
辞書を用いて攻撃する方法
john --wordlist=myDictionaryFile myPassswordFile
ルールを指定して総当り
john --incremental:Rule myPasswordFile

の3通りあるらしく、単に john myPasswordFile とすると john 側で持ってる辞書とかを使いながら全部の方法でパスワードを推測するらしい。
今回は dictionary というファイルが与えられているので辞書だけ使ってアタックする。問題文を users, 上の URL から拾ってきた辞書を dictionary として保存して john --wordlist=dictionary users 実行したら5秒くらいで解析終わった。結果を見るには john --show users でOK

user00:FREQUENT:15491:0:99999:7:::
user01:LATTER:15491:0:99999:7:::
user02:ADDITIONAL:15491:0:99999:7:::
user03:GENDER:15491:0:99999:7:::
user04:__________:15491:0:99999:7:::
...

21 password hashes cracked, 1 left

解析できてないのは user99 だけなので問題ない。どう考えても頭の文字を拾っていけば旗取れそうなので適当にコード書いたら旗取れた。

begin
    File.open 'result' do |file|
        file.each do |line|
            line.match(/^user\d\d:(.*)/) {|match|
                print match[1][0]
            }
        end
        puts
    end
rescue => e
    puts e.message
end

思ったこととか

問題文見た時なんかのデータベースかな〜とか思ってたけど、途中で Linux のアカウント情報であることを知った。せっかくなので調べてみた。

参考になるページ

何も知らない人間にとってはググってツール使って終わりみたいな感じになってしまうけど、それじゃあ意味ないので、問題見るたびにいろいろ調べてみたい。ちゃんとわかってる人にとっては最後のメッセージなくても SHA512 で暗号化されてるアカウント情報だってわかる。ググって解けるかどうかよりそういうところが重要な気がする。

2015-04-01

KSNCTF #13 Proverb

CTF KSNCTF

問題

ksnctf - 13 Proverb

考えたこと

思考停止でいけるところまでいく

% ssh q13@ctfq.sweetduet.info -p 10022

[q13@localhost ~]$ ls -a
.  ..  .bash_logout  .bash_profile  .bashrc  flag.txt  proverb  proverb.txt  readme.txt

[q13@localhost ~]$ cat flag.txt 
cat: flag.txt: 許可がありません

[q13@localhost ~]$ cat readme.txt 
You are not allowed to connect internet and write the home directory.
If you need temporary directory, use /tmp.
Sometimes this machine will be reset.

[q13@localhost ~]$ ./proverb 
Ignorance is bliss.

readme の内容は多分前にも見た。なにかやるなら /tmp 以下でやれというやつ。
proverb というやつを実行すると英語出てきた。bliss というのは幸福という意味で、知らぬが仏に近い英語のことわざらしい。 proverb なるほど。

[q13@localhost ~]$ ./proverb 
Blood is thicker than water.

もう一回実行したら変わった。血は水よりも濃い。知らなかったのでググった。なるほど。

血は水よりも濃い - 故事ことわざ辞典

proverb.txt を見てみるとことわざっぽいのがいろいろ書いてあったので、proverb はここから1行ランダムに出力してるっぽい。

[q13@localhost ~]$ mv flag.txt proverb.txt 
mv: try to overwrite `proverb.txt', overriding mode 0444 (r--r--r--)? n

読んだばっかりの readme を忘れてた。

[q13@localhost ~]$ cp proverb /tmp/proverb
cp: `proverb' と `/tmp/proverb' は同じファイルです

[q13@localhost ~]$ cp flag.txt /tmp/proverb.txt
cp: `flag.txt' を 読み込み用でオープンできません: 許可がありません

[q13@localhost ~]$ mv flag.txt /tmp/proverb.txt
mv: try to overwrite `/tmp/proverb.txt', overriding mode 0644 (rw-r--r--)? y
mv: cannot move `flag.txt' to `/tmp/proverb.txt': 許可がありません

パーミッションがないので旗のほうをコピーできない。でも /tmp/ 内に proverb.txt というファイルがあるらしい。

[q13@localhost ~]$ cd /tmp
[q13@localhost tmp]$ ./proverb
Please make your own subdirectory.

なるほど。

[q13@localhost tmp]$ mkdir mytmp
[q13@localhost tmp]$ cd mytmp

困ったのでググったら symlink を張れって書いてあったので張ったら読めた。

[q13@localhost mytmp]$ ln -s ~/proverb proverb [q13@localhost mytmp]$ ln -s ~/flag.txt proverb.txt [q13@localhost mytmp]$ ./proverb FLAG_****************

思ったこととか

とにかく symlink を張れとしか書いてなかったので調べてみたらこんな記事見つけた。

ロリポップのサイト改ざん事件に学ぶシンボリックリンク攻撃の脅威と対策 | 徳丸浩の日記

これはレンタルサーバの問題らしいけど似たような感じがする。

[q13@localhost ~]$ ls -l
合計 28
-r-------- 6 q13a q13a    22  6月  1 05:21 2012 flag.txt
---s--x--x 7 q13a q13a 14439  6月  1 04:59 2012 proverb
-r--r--r-- 1 root root   755  6月  1 04:58 2012 proverb.txt
-r--r--r-- 1 root root   151  6月  1 04:48 2012 readme.txt

flag.txt は所有者だけ読みこみ可能になってるけど、 proverb の所有者もユーザ q13 だから読み込めるということなんだろうか。調べるのはむずそうだったので試してみた。

% echo 'this is test' > text
% ruby read.rb
this is text
% chmod 044 text
% ruby read.rb
read.rb:1:in 'read': Permission denied @ rb_sysopen - text (Errno::EACCES)
% sudo useradd hoge
% sudo chown hoge text
% ruby read.rb
this is text

# read.rb
begin
    text = File.read 'text'
    puts text
rescue => e
    puts e
end

どうやらそうっぽい気がするような感じがする（？）

今まで何も考えず mv とか cp 使ってたけど、こういうコマンドには対象のファイルとか親ディレクトリのパーミッションが関わってくるらしい。
言われてみれば当然という感じがする。なるほどという感じだった。

2015-03-29

KSNCTF #12 Hypertext Preprocessor

CTF KSNCTF

問題

ksnctf - 12 Hypertext Preprocessor

考えたこと

意味はわからんけど意味有りげなタイトルはググれと習ったのでまずタイトルでググると、Hypertext Preprocessor っていうのは PHP のことらしい。カッコイイ。
ハイパーテキストプリプロセッサ書けますって言ってみたい。

問題のページを開くと時限爆弾的なのが出てくる。ソースを見ると <title>Clock</title> って書いてあるけど数字は動いてない。
Unix time 的な何かの基準の時間とか？そもそも時間かどうかも怪しい。

と思ったけど更新したら数字変わった。

[更新前]2012:1823:20:15:03:28:21:08:21:42:07:36:10
[更新後]2012:1823:20:15:03:28:21:09:56:54:55:13:38

2012:1823:YY:YY:MM:DD:HH:mm:SS:...

くらいな気はするけど 2012:1823 というのはわからない。でも2012はなんとなく2012年な気がした。

CGI版PHPにリモートからスクリプト実行を許す脆弱性(CVE-2012-1823) | 徳丸浩の日記

まあタイトル見た感じ99%これという感じがする。
CGI 環境で PHP 動かしてると任意のスクリプトを外部から実行されるとかいうヤバそうな脆弱性。
OS コマンドインジェクションとかいうのを本で読んだけどそれっぽい。

= を含まないクエリをコマンドライン引数として認識される。例えば ?-s とかいうクエリを投げると -s オプションを渡すことができてソースが見れるらしい。やってみたらソース見れた。

<?php // 主要部分抜粋
    //  Flag is in this directory.

    date_default_timezone_set('UTC');
    
    $t = '2012:1823:20:';
    $t .= date('y:m:d:H:i:s');
    for($i=0;$i<4;$i++)
        $t .= sprintf(':%02d',mt_rand(0,59));
?>

このディレクトリ内のファイルから旗を見つけないといけない。

指定できるのは -s だけじゃなくて、 -d オプションで php.ini (PHP の設定ファイル) の設定を指定できる(らしい)。こわい。

allow_url_include=On
auto_prepend_file=php://input

php.ini をこういう設定にしておくと POST パラメータとして送信した内容を PHP ファイルとして実行できる(らしい)。コード書いた。

https://github.com/sekai013/ksnctf/blob/master/hypertext_preprocessor/hypertext.rb

実行したら旗取れた。

思ったこととか

PHP とか Perl の CGI の脆弱性の話聞いたことあるけど聞いたことあるだけだし、 PHP は3秒くらいしか見たことないし、 Perl は全くわからない。
見たやつをちょっとずつ覚えていけばいいか。