SECCON begineers CTF 2024 writeup

SECCON beginners2024に参加したのでチャレンジした問題について、書きます。

# 結果
普段からCTFの勉強をしているわけではないので、beginner向けの問題だけ挑戦しました。
![スクリーンショット 2024-07-07 18.33.54.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1120135/ef02323b-47b4-ad09-cb82-6ca6f4a1a965.png)
begineer向けのmisc, pwnable, cryptoを解いただけですが、順位は案外真ん中ぐらいでした。真面目に勉強してeasyとかも解けるようになれば100位台目指せる？（スコアボートだと200位の人は450ptぐらいでした。）

# crypto
## Safe Prime
### 問題
> Using a safe prime makes RSA secure, doesn't it?

この問題では以下のようなpythonファイルとoutput.txtが与えられました。
```python:chall.py
import os
from Crypto.Util.number import getPrime, isPrime

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
m = int.from_bytes(FLAG, 'big')

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")
```
``` output.txt
n = 29292736743351094890175.... 
c = 40791470236110804733312.... (長いので省略)
```
`n`（公開モジュラス）と`c`（暗号文）が与えられて、`FLAG`（平文）を求める問題です。

### 解答
RSAについては大学時代ある程度の理論的なところの証明も習ったのですが、すっかり忘れていました...　ただ、本来`p`(素数1), `q`(素数2)がランダムな素数でないといけないことはなんとなくわかったので、そこから解いて行きました。
`p`と`q`に次の関係があるため、`n`の値よりそれぞれの値が求まります。
```
q = 2p + 1
n = 2 * p ^ 2 + p (∵n = p * q)
0 = 2 * p ^ 2 + p - n
# ２次の解の公式により
p = ~~~~　(省略)
```
解の公式なんて久しぶりに使いました。
暗号化に使われる素数の値が分かったので、復号できるはずです。
具体的な計算はchatGPTに計算プログラムを作ってもらいました...

```python: slove.py
import math

p = 1210（省略）
e = 65537
q = 2 * p + 1

# nを計算
n = p * q

# totientを計算
totient = (p-1) * (q-1)

# 拡張ユークリッドの互除法を使ってdを求める
def extended_gcd(a, b):
    x, y, u, v = 0, 1, 1, 0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b, a, x, y, u, v = a, r, u, v, m, n
    return b, x, y

gcd, d, y = extended_gcd(e, totient)

if gcd != 1:
    raise ValueError("e and totient are not co-prime")
else:
    # dを適切な値に調整
    d = d % totient

# 暗号化されたメッセージcが与えられている
c = 4079.... （省略）

# 復号
m = pow(c, d, n)
print(f"復号化されたメッセージ: {m}")
FLAG = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
print(FLAG)

```

### 補足
m: 平文メッセージ（数値化されたFLAG）
p: 最初の素数（通常は秘密）
q: 2つ目の素数（通常は秘密）。ここではpを使って生成される強い素数
n: 公開モジュラス（p * q）
e: 公開指数
c: 暗号文
公開鍵は公開モジュラス (n)と公開指数 (e)のペア
秘密鍵は秘密指数 (d)と公開モジュラス (n)のペア
秘密指数dはeの法nにおけるモジュラ逆数

# misc
## getRank
### 問題
以下のようなサーバー側のプログラムとwebページのリンクが与えられました。
```typescript:main.ts
import fastify, { FastifyRequest } from "fastify";
import fs from "fs";

const RANKING = [10 ** 255, 1000, 100, 10, 1, 0];

type Res = {
  rank: number;
  message: string;
};

function ranking(score: number): Res {
  const getRank = (score: number) => {
    const rank = RANKING.findIndex((r) => score > r);
    return rank === -1 ? RANKING.length + 1 : rank + 1;
  };

  const rank = getRank(score);
  if (rank === 1) {
    return {
      rank,
      message: process.env.FLAG || "fake{fake_flag}",
    };
  } else {
    return {
      rank,
      message: `You got rank ${rank}!`,
    };
  }
}

function chall(input: string): Res {
  if (input.length > 300) {
    return {
      rank: -1,
      message: "Input too long",
    };
  }

  let score = parseInt(input);
  if (isNaN(score)) {
    return {
      rank: -1,
      message: "Invalid score",
    };
  }
  if (score > 10 ** 255) {
    // hmm...your score is too big?
    // you need a handicap!
    for (let i = 0; i < 100; i++) {
      score = Math.floor(score / 10);
    }
  }

  return ranking(score);
}

const server = fastify();

server.get("/", (_, res) => {
  res.type("text/html").send(fs.readFileSync("public/index.html"));
});

server.post(
  "/",
  async (req: FastifyRequest<{ Body: { input: string } }>, res) => {
    const { input } = req.body;
    const result = chall(input);
    res.type("application/json").send(result);
  }
);

server.listen(
  { host: "0.0.0.0", port: Number(process.env.PORT ?? 3000) },
  (err, address) => {
    if (err) {
      console.error(err);
      process.exit(1);
    }
    console.log(`Server listening at ${address}`);
  }
);

```
Webページ画面
![スクリーンショット 2024-07-07 21.52.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1120135/1c3d3102-7e74-d3e5-671e-f15184c87732.png)
ページ自体は0~9の番号を推測して正解だった場合にスコアを獲得できます。獲得したスコアがランキングで何位なのかを確認することができます。
`main.ts`を見るとランキングで１位になるとフラグを獲得できるようになっています。
ランキングは固定値で`[10 ** 255, 1000, 100, 10, 1, 0]`となっています。そのため、`10 ** 255`より大きなスコアを出せば、１位になってフラグを獲得できます。しかし、サーバ側では大きすぎる値には以下のような処理がされてしまうので、そこをどう潜り抜けるかという問題です。
```typescript
if (score > 10 ** 255) {
    // hmm...your score is too big?
    // you need a handicap!
    for (let i = 0; i < 100; i++) {
      score = Math.floor(score / 10);
    }
```

### 解答
ドメインの/にPOSTリクエストを送ることで直接、chall関数を実行させることができます。受け取られた値はまず文字列として300文字以上だと無効な値とされてしまします。そのため、299文字以下の文字列しか送れません。その後、値はparseIntという関数によってStringからIntに変換され、10 ** 255との比較が行われます。[javascriptのドキュメント](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/parseInt)によると、parseIntは16進数も扱うことができます。したがって、16進数を使うことで、文字列として299文字以下かつ10 ** 255よりも大きな値を送信することができます。以下のようなリクエストボディを送信することでフラグをゲットすることができました。
```
{
"input": "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
}
```

# pwnable
## simpleoverflow
### 問題
> Cでは、0がFalse、それ以外がTrueとして扱われます。
> `nc simpleoverflow.beginners.seccon.games 9000`

以下のような、cのソースとコンパイルされたバイナリーが渡されます。
```c:src.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main() {
  char buf[10] = {0};
  int is_admin = 0;
  printf("name:");
  read(0, buf, 0x10);
  printf("Hello, %s\n", buf);
  if (!is_admin) {
    puts("You are not admin. bye");
  } else {
    system("/bin/cat ./flag.txt");
  }
  return 0;
}

__attribute__((constructor)) void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(120);
}

```
### 解答
タイトルにある通りオーバーフローをさせます。`is_admin`を1にできればフラグをゲットできます。`buf`は`char`型が10文字分でその後ろに`is_admin`が`int`型で確保されています。`read(0, buf, 0x10)`で16バイト分入力できるので、`aaaaaaaaaa1`のような入力をするとオーバーフローによって`is_admin`の値が更新されてフラグをゲットできます。

# 感想
時間があまりとれず、できそうなものだけ手を付けました。来年はもう少し時間を確保して、すべてのesay・beginnerの問題を挑戦したいです。