SECCON Beginners 2018 東京に参加してきました
1.スケジュールなど
-
当日のスケジュール
10:00～10:30 受付
10:30～11:00 開演、オリエンテーション（CTFとは？）
11:00～12:30 講義1（Crypto）
12:30～13:30 休憩（昼食は各自でおとりください）
13:30～15:00 講義2（pwn）
15:15～16:45 CTF演習問題
17:00～17:45 CTF解説
18:00～19:00 交流会
19:00 終了
-
当日の雰囲気など
入ったときは、ここにコンピュータの猛者（見習い）達が集まっているというのをヒシヒシと感じた。やはりリンゴのパソコンは多い（自分はwindows）。今回演習用としてデフォルトのKali Linuxを使用した。今までCTFにチャレンジするときはVMでUbuntuを使っていて、$sudo apt-getできないやつはパッケージをダウンロードしてmakeしたりしていた。しかし、Kali LinuxにはCTFに使える色々なアプリケーションが標準搭載されている！！Ubuntuよりもこっちの方がいいのだろうか。そこでスタッフに話を聞いてみたところ
「確かに有用なアプリがデフォルトで入っているのは良いが、PwnではUbuntu環境で実行されているものが多くライブラリの場所が同じなので楽なことがある」
ということでUbuntuも良いということだ。他にArchAssaultも良いと聞いた（初めて聞いた）。
Kali linuxのリンク
https://www.offensive-security
2.講義について
今回はスケジュールの通りCryptoとPwnの講義が行われた。大まかに説明するとCryptoではmodの計算からRSAの計算までを、Pwnではgdb-peadの使い方からバッファオーバーフローさせる話までを聞いた。RSAの計算は理解した。しかし、
Pwn全然分からん！
ということでこの記事ではほとんどPwnには触れない（てか触れられない）。後に頑張りますスミマセン。
-
Cryptoの講義について
いつもは、Forensicsしかやらないので初めて真面目にCryptoを学ぶ。そしてやはり人から直接学べるというのはとても良い。この分野で必要なのは、プログラミング力と数学をやる気持ちだけということだ。なんと分かりやすい。
modの計算
まずmodの計算から入るのだが、高校生以上ならたぶん大体の人がわかるのではないだろうか。
例えば
a mod N ・・・これはaをNで割ったあまりである。
この時Nのことを法と呼ぶ。
ということで早速、実際にやった練習問題を
100 mod 7 = 2
4 * 10 mod 11 = 7
4 * 11 mod 11 = 0
4 * 12 mod 11 = 4 * 1 mod 11 = 4
6^5 mod 11 = (6 mod 11)*(6^2 mod 11)^2 = 10
6^10 mod 11 = (6^5 mod 11)*(6^5 mod 11) = 1
hint: 4 * 10 mod 11は(4 * 10) mod 11と解釈する。
分配法則は成り立つ。例えば、4 * 10 mod 11 = (4 mod 11) * (10 mod 11) mod 11
答えは式の等号の後に白色で記述してある。
ここで除算は無いのかと思った人はいるだろうか。modにおいて除算は通常の除算と同様には実現できないというのが難しいところだ。例えば、
4 / 2 mod 11 = 2
9 / 3 mod 11 = 3
であるが、5 / 4 mod 11 = ?
余りは整数でなければいけない。そこで除算が常にできる条件は、
法と割る数が互いに素であること
では、上の式はどうなるのか。
5 / 4 mod 11 = x
4 * x mod 11 = 5
x = 4
しかし、毎回これをただ探すのは辛い。そこで 4y ≡ 1( mod 11)を満たす。y(=4^-1)を探す。つまり、割る代わりに-1乗の値(逆元）を掛ける。この逆元を使って、先のxを求めるには拡張ユークリッドの互除法を使う。詳しく知りたい方は、おググりください。
では、簡単に使い方だけを説明
ここでは、法と割る数から(1)、(2)を導き、その二つを使いなるべくxの係数が小さくなるように引き、また新たにできたものを引いてだんだんとxの係数を1に近づけていく。
そして、このx ≡ 3 (=1/4 mod 11) を使うと
5 / 4 mod 11 = 5 * 3 mod 11 = 4
このように使う。条件のとおり法と割る数が互いに素でない場合はできないので注意。では、練習問題
4^(-1) mod 11 = 3 mod 11 = 3
3^(-1) mod 7 = -2 mod 7 = 5
8^(-1) mod 35 = -13 mod 35 = 22
先の練習問題と同じように答えは＝の後に白色で記述してある。
RSAの話
CTFではよくでるCryptoの問題ということで、これが理解できればCryptoの問題が一個だけでも解けるようになるかもしれない。公開鍵うんぬんの話は既知であるとして話を進めていく。RSAの鍵生成は次のようになっている。
1.素数p, qを生成、N = pqとする
2. eを決定する。65537がよく使われる。（eはφ(N)と互いに素）
3. ed ≡ 1 (mod φ(N))を満たすdを求める。つまり、 d ≡ e^−1 (mod φ(N))として求める。
ここでφ(N) = (p-1)(q-1)
4.公開鍵(N,e)と秘密鍵dを得る
平文をM、暗号文をCとすると
暗号化:C = M^e mod N
復号:M = C^d mod N
なぜ復号できるのかなど証明の話が知りたい方は、おググりください。フェルマーの小定理やオイラーの定理などが関わってます。
では練習問題
p = 7、q = 13 、e = 5 、M = 3 のとき
公開鍵・秘密鍵は？ 暗号文は？ 復号して平文が出るか？
説明のとおりにやれば数値が出るはずなので答えのみ
N = 91, φ(N) = 72, d = 29 C = M^e = 61 M = C^d = 3
答えは白色でこの文の上の行に記述されている。
ここまでの参考・引用：CryptoBeginners Crypto講師 れっくす さん
これでRSAの問題は大体解けるはず。平文や暗号文は文字に変換してあることが多い。また、本来とけないはずのRSAが解けるのは何故なのか一応触れておく。解けるように作られているのは実際に使われている桁数よりも少なくしてあったり、数学的に脆弱なものを問題として扱っているからである。次は、お待ちかねのCTFの話に入っていこう。
RSAを解く上で使えそうなサイトリンク
factordb.com 入力した数値を素数に分けてくれる
Sage Cell Server python記述が使える。modの計算ができ、例えば、4 mod 11は pow(4,1,11)と書く。また通常のpythonではできない4^(-1) mod 11はpow(4,-1,11)として計算できる。
3.CTF演習について
午後にはCTFの演習が行われた。まずは自分の成績についてお話する。解けた問題は全11問中4問で400pt。スコアボードは以下のようになっている。
121人中17位タイと、一見悪くないように聞こえるが簡単なものしか解けなかったので良くもない。普通のCTFであれば10pt~50ptぐらいのものしか解けなかった。解けた問題にだけ触れる。
Misc
Welcome (100pt)
問題文にflagがあるのでそれをsubmit
Tekisan4b in Shinagawa (100pt)
IPアドレスがあり、それをクリックするとSECCONおなじみの100問連続正解しなければいけない簡単な計算問題。phpか何かでスクリプトを書いた方が楽なのだろうが自分には書けないので、集中して100問解いた。
Crypto
Factoring (100pt)
N
今だ自分はCとC++しか使えないので、プログラムを作ろうとした。あれ、intだめやん。うん？doubleもダメか？となったので上で説明のときに挙げた
factordb.comを使い、計算はSage Cell Serverでクリア。
Go Fast (100pt)
これは上で挙げたSage Cell Serverを使うと一瞬で終わる。
その他の問題について
Writeupは忙しいので付けていない。
他の方のWriteup
自分より上位だった方々のブログです。
