Ricerca CTF 2023 Writeup (NEMU, Rotated Secret Analysis)
Ricerca CTF 2023にチーム TSG-graduates で参加しました。4位でした。
Ricerca CTF 2023は賞金獲得要件に「日本国内在住である学生のみで構成される」があるので、それに適合しない人々の集まりです。日本国内在住である学生の人たちがチーム TSG で参加をしており、あちらはあちらで盛り上がっていたようです。*1
🏁Ricerca CTF 2023 終了🏁
— 株式会社リチェルカセキュリティ (@RicercaSec_JP) April 22, 2023
本日 4 月 22 日(土)午後 10 時をもって #RicercaCTF 2023 は終了しました。
ご参加くださり、誠にありがとうございました。 pic.twitter.com/Qi0APWhPsg
BOFSec, Rotated Secret Analysis, NEMUあたりを解きました。NEMUとRotated Secret Analysisのwriteupを書きます。
NEMU
すごい。あのC言語が、GCC拡張で関数内関数定義なんて許すんですね。知らなかった。
https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html
ソースコードを少しにらむと、r1, r2, r3, aの定義はint32_tなのに、load,mov,...の引数はuint64_tとなっており、サイズ不一致が起きていることがわかります。特にuint64_t*を受け取ってそこに書き込みを行うmov, inc, dblで破壊を行えることに気づきます。
ここで破壊可能なのは(32bitの)r1, r2, r3, aそれぞれの直後に位置する32bitな訳ですが、これをGhidraやgdbで確認すると、実際の所r1の直後32bitの値であることが分かります。
gyazo.com
gyazo.com
gdb上のstack領域0x7fffffffdd40から16byteが、4つの32bit register用領域で、その直後0x7fffffffdd50から4byteが、破壊可能箇所です。ここに今なにがあるのか気になります。一見ランダムな値に見えますが、どうも機械語っぽいような気もします。逆アセンブルしてみます。
かなり機械語っぽいです。でも待てよ、ここってstack領域なはずだぞ？
なんてこった、このELF、stack領域が実行可能だ。わざわざこんなことするとも思えないので、きっと関数内関数定義を使った副作用なんでしょう。今main.cをgccでコンパイルしてみたら、ちゃんとldが警告出してきました。
$ gcc main.c /usr/bin/ld: warning: /tmp/ccg7DhQI.o: requires executable stack (because the .note.GNU-stack section is executable)
強い情報を得ました。stackは実行可能で、そしてそこを4byteだけですが書き換え可能ということです。ここっていつ実行される命令列なんでしょう。ちょっと調べてみると、この0x7fffffffdd50は、add関数へのtrampolineであることが分かります*2。同様にして、0x7fffffffdd6cからaddiへのtrampoline、0x7fffffffdd88からdblへのtrampolineがあることが分かります。
ENDBR64命令は、実際の所なんなのかよく知りませんが、各関数の一番始めについていがちで、いつも読み飛ばしています。きっと深淵な存在意義はあるのでしょうけど、まあだいたいNOPです。たぶん。怒られる。
ENDBR64の位置を破壊すると、add NEMU命令を呼ぶたびに、直前に好きなことができるようになります。4byteだけですが、なにをしましょうか。いろいろ考えた結果、PUSH rdiを入れておくと良い感じになると結論づけました。
main関数から、CALL rbxでtrampolineに飛んできて、rdiに関数内関数定義済み関数への第一引数が飛んできて、addの場合はregisterのアドレスがやってきます。ここでPUSH rdiをしておいて、trampoline jump先からRETするときに、PUSHしておいたregister値の格納先stack領域アドレスにripが移ります。stack領域は実行可能なので、registerに適切な機械語さえ入れておけば、問題なく実行が行えます。registerに入れておく機械語の最後にRETを入れておくと、うまく整合してmain関数のもとの位置(CALL rbx直後)にripが戻り、なにごとも無かったかのように実行を続けることが出来ます。
この作業によって、少なくともr3とr2の8byte - RET用1byte = 7byte、自由に機械語を実行できるようになりました。7byteもあったらだいたいの1手作業は行えて、それを繰り返し可能です。
この7byteの自由空間を使って、addi用trampolineコード周辺の改ざんを行いました。いつものshell-stormさんからもらってきた*3 27byteシェルコードに置換を行いました。これ以降、addi NEMU命令は使用不可能になりますが、別に要らないでしょう。ギリギリdbl用trampolineコードまでは食わないようです。別に食っても問題なかったですが。
最後にaddi NEMU命令を実行して、addi用trampolineコード箇所にあるシェルコードを実行して、シェルが取れて終わりです。
ローカルではexpect 'opcode:'なるプロンプト待ちを入れていたのですが、リモートで実行したら永遠に終わらなかったため、このwaitはコメントアウトしました。CTF pwn問題、ほんとに、network越しのI/O bufferingがかかわってくるとめちゃくちゃ面倒になるので、今回のような決定的なI/O処理は本当にえらいですね～～ 一切プロンプト待ちを行わなくても動く。
コードは以下になります。
gist.github.com
Rotated Secret Analysis
RSAで、ただしN = pqのpとqが、512bit rotated関係にあります。
pとqの関係性を利用して、Nの素因数分解を考えます。p = 2**512 a + b (a, bは512bit以下)と表したとき、q = 2**512 b + aと表せて、つまりN = pq = (2**512 a + b)(2**512 b + a)と表せるでしょう。
2048bitのNの下位512bitおよび上位512bitを取れば、abの値が、繰り上がりを考慮した数bitのずれを許した上で、ほとんど正しく求まります。
abの値を仮定すれば、Nからaa+bbも算出できます。(a+b)^2を構成すれば、a+bも算出できます。abとa+bが分かったとき、aおよびbの算出は、二次方程式の解と係数の関係*4から、二次方程式の解の公式で行えます。
コードは以下になります。
gist.github.com
問題を作ってくれて、開催してくれて、一緒に参加してくれて、writeupを読んでくれて、ありがとうございました。
*1:2チーム間での情報の分断のため、各々用のSlack private channelを用意しました。また、情報共有のため、いつも使いがちなツールは使わずに、古き良きGoogle Docsを利用しました。HackMDでも良かったかもしらんが、思いつかなかった。
*2:trampolineっていうのは正確な定義は知りませんが、OS Kernelの実装とかで出てくるあれです、 https://en.wikipedia.org/wiki/Trampoline_(computing) Wikipediaを読んで雰囲気を感じてくれ
*3:いつもありがとう。
*4:どうでもいい話ですが、高校生のときに友人から聞いた話で、一部の塾だか界隈では「解と計数の関係より」と百回も一万回も書くのが面倒なので、界隈内用語として「かけかより」という略語が通用するそうです。真実は知りません。かわいくないですか？
