SECCON Beginners CTF 2023 Writeup (Crypto, Rev)

# はじめに
SECCON Beginners CTF 2023 に参加しました．
もちろん今回も一人ですが，順位は 15 位で Web とか Misc が全然できなかった割には良かったと思います．

Crypto と Rev は全完できたので全体としては 27 問中，20 問解けました．
とにかく，Web が読めなさ過ぎた上に何をしたら良いのかわからなかったので，もっと勉強します．

Crypto 全 5 問と Rev 全 5 問の Writeup です．

## 目次
### Crypto
1. [CoughingFox2](#coughingfox2)
2. [Conquer](#conquer)
3. [Choice](#choice)
4. [switchable_cat](#switchable_cat)
5. [cooking](#cooking)

### Rev
1. [Half](#half)
2. [Three](#three)
3. [Poker](#poker)
4. [Leak](#leak)
5. [Heaven](#heaven)

# CoughingFox2
## 問題
```
beginner
暗号問題に初めて挑戦する方向けに独自暗号と暗号化した後の出力を配布します。 ご覧の通り、簡易な暗号方式なので解読は簡単です。 解読をお願いします！

The original cipher for beginners and encrypted text are provided. Needless to say, this cipher is too childish, and that easy to decrypt! So, could you please decrypt it?

CoughingFox2.tar.gz a2be048e61bfc5acaf6a23d3948568e0a2ea247c
```

## 解法
$(f_i + f_{i + 1})^2 + i$ としてランダムにソートしている．
$x^2 + i \quad (0 \le i < len(cipher))$ となるかどうかで $i$ の値がわかり (cipher が短いので一意に定まる) ，それを基にソートする．
FLAG の 1 文字目は 'c' なので，$("c" + x)^2 == c[0]$ となるような $x$ を探索すれば 2 文字目がわかる．これを繰り返せば FLAG が得られる．

## Solver
```py
import gmpy2

cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636]

def main():
    idxs = []
    for c in cipher:
        idxs.append(search(c))
    assert len(idxs) == len(set(idxs))
    
    sorted_flag = [0] * len(cipher)
    for i in range(len(cipher)):
        sorted_flag[idxs[i]] = cipher[i] - idxs[i]

    flag = 'c'
    c = ord('c')
    for sf in sorted_flag:
        for i in range(0x20, 0x7e + 1):
            if (c + i)**2 == sf:
                c = i
                flag += chr(i)
                break
    print(flag)

def search(c):
    for i in range(len(cipher)):
        _, res = gmpy2.iroot(c - i, 2)
        if res:
            return i

if __name__ == '__main__':
    main()
```

# Conquer
## 問題
```
easy
なんだか目が回りそうな問題ですね……

Conquer.tar.gz 4fe9007c38458ac345dc11109666d30b5d1f8f93
```

## 解法
もともとの長さは 440 ビットぐらいと考えらえる (XOR でビット数が増えることはない)
```
>>> key.bit_length()
438
>>> cipher.bit_length()
436
```
以下の手順で暗号化している
1. cipher = flag ^ key
2. key を $cipher^3 \mod {length}$ ビットだけ左回転シフト
3. cipher = cipher ^ key
4. 2 に戻る

単純に逆の処理をすれば良い
ただし，ビット数が確定していない (おそらく FLAG のビット数から取ってきているので 439 ビット) ので適当に当たる

## Solver
```py
def main(length = 500):
    key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
    cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379

    for i in range(32):
        if key == 0:
            exit()
        cipher ^= key
        key = inv_ROL(key, pow(cipher, 3, length), length)

    flag = cipher ^ key

    flag = '0' * (8 - (flag.bit_length() % 8)) + bin(flag)[2:]
    flag = [chr(int(flag[i * 8 : (i + 1) * 8], 2)) for i in range(len(flag)//8)]
    flag = ''.join(flag)
    if 'ctf' in flag:
        print(flag)

def inv_ROL(bits, N, length):
    for _ in range(N):
        bits = (((bits & 1) << (length - 1)) | ((bits >> 1) & (2**(length - 1) - 1)))
    return bits

if __name__ == '__main__':
    length = 500
    for i in range(100):
        main(length - i)
```

# Choice
## 問題
```
medium
Can you make the right choice?

nc choice.beginners.seccon.games 1336

Choice.tar.gz 1ca5bab45beb346ec267943511844da3d41d34b6
```

## 解法
3 つの素数 $p, q, r$ の RSA になっている．
$s = pq + qr + rp$ が与えられていて，$p^a + q^a + r^a \mod n \quad (a > n)$ の値をリクエストすることができる．

$f(n) = p^a + q^a + r^a \mod n$ とすると以下の式が成り立つ

$$
f(n+3) + f(n+1) \cdot s - f(n) \cdot n \\
= p^{n+3} + q^{n+3} + r^{n+3} + (p^{n+1} + q^{n+1} + r^{n+1}) \cdot (pq + qr + rp) - (p^{n} + q^{n} + r^{n}) \cdot (pqr) \\
= p^{n+3} + q^{n+3} + r^{n+3} + p^{n+2} q + p q^{n+2} + q^{n+2} r + q r^{n+2} + r^{n+2} p + r p^{n+2} \\
= f(n + 2) \cdot (p + q + r)
$$

* 法 $n$ のもとで考えるので $p + q + r = (f(n+3) + f(n+1) \cdot s) \cdot f(n+2) ^ {-1}$
* (最初から法 $n$ で考えて $pqr$ を持つ項が現れれば消すようにして式変形したほうが楽)

復号するのに必要な値は $\phi = (p-1)(q-1)(r-1) = n - s + (p + q + r) - 1$ なので求めることができ，復号できる．

## Solver
```py
from pwn import *
from Crypto.Util.number import *

e = 65537

def main():
    io = remote('choice.beginners.seccon.games', 1336)
    n = int(io.recvline().decode().split()[2])
    e = int(io.recvline().decode().split()[2])
    c = int(io.recvline().decode().split()[2])
    s = int(io.recvline().decode().split()[2])

    f1 = get_pow(io, n + 1)
    f2 = get_pow(io, n + 2)
    f3 = get_pow(io, n + 3)
    p_q_r = ((f3 + f1 * s) * pow(f2, -1, n)) % n

    phi = n - s + p_q_r - 1
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    print(long_to_bytes(m))

def get_pow(io, a):
    io.sendlineafter(b'input a(a>n) : ', str(a).encode())
    io.recvline()
    return int(io.recvline().decode().split()[2])

if __name__ == '__main__':
    main()
```

# switchable_cat
## 問題
```
medium
暗号化アルゴリズムをつくったよ
あ！さっそくねこちゃんが平文を暗号化しにきたよ！
かわいいね！！！！

switchable_cat.tar.gz bb6b9ad73eed319d1aa00978c9a8d179737d4cc7
```

## 解法
初期値から状態を計算して暗号化したときと同じ状態にしたいが，普通には計算できない．

LFSR の遷移は GF(2) 上での行列を用いて表現できることが知られている．
交互に違う処理になっているので，2回の遷移を 1 セットとして行列を作る．

## Solver
```py
from Crypto.Util.number import *

seed = 219857298424504813337494024829602082766
cipher = 38366804914662571886103192955255674055487701488717997084670307464411166461113108822142059

class LFSR:
    def __init__(self):
        self.bits = 128
        self.rr = seed
        self.switch = 0
    def next(self):
        r = self.rr
        if self.switch == 0:
            b = ((r >> 0) & 1) ^^ \
                ((r >> 2) & 1) ^^ \
                ((r >> 4) & 1) ^^ \
                ((r >> 6) & 1) ^^ \
                ((r >> 9) & 1)
        if self.switch == 1:
            b = ((r >> 1) & 1) ^^ \
                ((r >> 5) & 1) ^^ \
                ((r >> 7) & 1) ^^ \
                ((r >> 8) & 1)
        r = (r >> 1) + (b << (self.bits - 1))
        self.rr = r
        self.switch = 1 - self.switch
        return r & 1
    
    def gen_randbits(self, bits):
        key = 0
        for i in range(bits):
            key <<= 1
            key += self.next()
        return key

n = 128
mat1 = []
mat2 = []
for i in range(n - 1):
    mat1.append([1 if i + 1 == j else 0 for j in range(n)])
    mat2.append([1 if i + 1 == j else 0 for j in range(n)])
mat1.append([1 if i in [0, 2, 4, 6, 9] else 0 for i in range(n)])
mat2.append([1 if i in [1, 5, 7, 8] else 0 for i in range(n)])

mat1 = matrix(GF(2), mat1)
mat2 = matrix(GF(2), mat2)

k = ord("🐈")*ord("🐈")*ord("🐈") * 4
m = mat2 * mat1

r = []
for i in range(n):
    r.append((seed >> i) & 1)
r = vector(GF(2), r)
r = (m^k) * r

seed = 0
for i in range(n):
    seed += (int(r[i]) << i)

lfsr = LFSR()
lfsr.rr = seed

key = lfsr.gen_randbits(296)
flag = key ^^ cipher
print(long_to_bytes(flag))
```

# cooking
## 問題
```
hard
Let's Cooking!

nc cooking.beginners.seccon.games 1337

cooking.tar.gz 5e98a698cfc9a5938151a52d0457bfca21af6576
```

## 解法
問題設定は以下のようになっている．
* 素数 $p$ を選択すると $m ^ 3 \mod p$ の値が返される．
* $g$ を選択して $(m \oplus s)^{m + 3g} \cdot g^{3(m + 3g)} + g(m \oplus s)^3 \mod p$ が返される． (16 回)
* $m$ の値がわかれば FLAG がもらえる．

$m < p$ なら 3 乗根は解けそうなので Sage でゴリ押し (これでいいのかはわからない)

```py
from pwn import *
from Crypto.Util.number import getPrime

p = getPrime(2048)

io = remote('cooking.beginners.seccon.games', '1337')
io.sendlineafter(b'p = ', str(int(p)).encode())
m3 = int(io.recvline().decode().strip().split()[-1])
m = mod(m3, p).nth_root(3)
print('m =', m)

for _ in range(16):
    io.sendlineafter(b'g = ', b'1')

io.sendlineafter(b'Thank you. By the way, where do you think this meat comes from?', str(int(m)).encode())
print(io.recvline())
```

# Half
## 問題
```
beginner
バイナリファイルってなんのファイルなのか調べてみよう！

あとこのファイルってどうやって中身を見るんだろう...？

Half.tar.gz f532a2ee8c9018ab2bb82d275b6a6838f54af630
```

## 解法
実行ファイルの中にそのまま FLAG があるので，strings コマンドを使うだけ
```
$ strings ./half
```

# Three
## 問題
```
easy
このファイル、中身をちょっと見ただけではフラグは分からないみたい！

バイナリファイルを解析する、専門のツールとか必要かな？

Three.tar.gz 708918558460842584a4b762c6113f480e6ff781
```

## 解法
まずは Ghidra で見てみる
```c

undefined8 validate_flag(char *param_1)

{
  char cVar1;
  size_t sVar2;
  undefined8 uVar3;
  int local_c;
  
  sVar2 = strlen(param_1);
  if (sVar2 == 0x31) {
    for (local_c = 0; local_c < 0x31; local_c = local_c + 1) {
      if (local_c % 3 == 0) {
        cVar1 = (char)*(undefined4 *)(flag_0 + (long)(local_c / 3) * 4);
      }
      else if (local_c % 3 == 1) {
        cVar1 = (char)*(undefined4 *)(flag_1 + (long)(local_c / 3) * 4);
      }
      else {
        cVar1 = (char)*(undefined4 *)(flag_2 + (long)(local_c / 3) * 4);
      }
      if (cVar1 != param_1[local_c]) {
        puts("Invalid FLAG");
        return 1;
      }
    }
    puts("Correct!");
    uVar3 = 0;
  }
  else {
    puts("Invalid FLAG");
    uVar3 = 1;
  }
  return uVar3;
}
```

コードを読むと，まず入力の長さが 0x31 かどうか確認される．
そして，インデックスを 3 で割った剰余によってどこから比較する文字を取ってくるか処理を分けている．
インデックスを i としたとき flag_(i // 3) + (i // 3) * 4 のアドレスが比較する文字となる．

flag_0 とかから Ghidra で一文字ずつ読むのは大変なので，ファイルの先頭からのオフセットだけメモって (Ghidra はファイルの先頭のアドレスが 0x100000 で表示される) Python でする．

## Solver
```py
data = open('./three', 'rb').read()

flag0 = 0x2020
flag1 = 0x2080
flag2 = 0x20c0

flag = ''
for i in range(0x31):
    base = [flag0, flag1, flag2][i % 3]
    flag += chr(data[base + (i // 3) * 4])

print(flag)
```

# Poker
## 問題
```
medium
みんなでポーカーで遊ぼう！点数をたくさん獲得するとフラグがもらえるみたい！

でもこのバイナリファイル、動かしてみると...？実行しながら中身が確認できる専門のツールを使ってみよう！

Poker.tar.gz 90920728f7e3757e105c71df2cfda0ffb534cf99
```

## 解法
とりあえず Ghidra
(file コマンドで見てみると stripped なのでシンボルが残っていないのでそれっぽい処理を探す)
```c
undefined8 main(void)

{
  undefined4 choice;
  int i;
  int score;
  
  score = 0;
  show_banner();
  i = 0;
  while( true ) {
    if (0x62 < i) {
      return 0;
    }
    show_score(score);
    choice = get_input();
    score = game(score,choice);
    if (99 < score) break;
    i = i + 1;
  }
  show_flag();
  return 0;
}
```
score が 100 以上なら FLAG が得られる．
ただ，何回も繰り返すのは大変なので，デバッガを使って分岐の処理の結果をいじる．

以下の命令が比較している部分で，ジャンプしなければ FLAG が得られる．
```
001022b5 7e 0c           JLE        LAB_001022c3
```

JLE 命令がジャンプする条件は，```SF != OF``` または ```ZF=1``` なので両方が成り立たないようにデバッガで操作する．

<details><summary>フラグレジスタについて</summary>

| フラグ | 意味 | フラグが立つ条件 | 下位からのビット位置 (0 スタート) |
| --- | --- | --- | --- |
| OF | Overflow Flag | 演算結果で桁あふれが発生 | 11 |
| SF | Sign Flag | 演算結果が負の値 | 7 |
| ZF | Zero Flag | 演算結果がゼロ | 6 |

</details>

## Solve
JLE 命令のところにブレークポイントを打って，今回は ```ZF=1``` は成り立っているが，```SF != OF``` が成り立っていないので SF を落とすことで成立させる．
```
(gdb) b *0x555555554000 + 0x22b5
Breakpoint 1 at 0x5555555562b5
(gdb) start
Function "main" not defined.
Starting program: /home/toha/work/seccon/work/beginners_ctf_2023/rev/poker/Poker/poker 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

██╗███╗   ██╗██████╗ ██╗ █████╗ ███╗   ██╗    ██████╗  ██████╗ ██╗  ██╗███████╗██████╗
██║████╗  ██║██╔══██╗██║██╔══██╗████╗  ██║    ██╔══██╗██╔═══██╗██║ ██╔╝██╔════╝██╔══██╗
██║██╔██╗ ██║██║  ██║██║███████║██╔██╗ ██║    ██████╔╝██║   ██║█████╔╝ █████╗  ██████╔╝
██║██║╚██╗██║██║  ██║██║██╔══██║██║╚██╗██║    ██╔═══╝ ██║   ██║██╔═██╗ ██╔══╝  ██╔══██╗
██║██║ ╚████║██████╔╝██║██║  ██║██║ ╚████║    ██║     ╚██████╔╝██║  ██╗███████╗██║  ██║
╚═╝╚═╝  ╚═══╝╚═════╝ ╚═╝╚═╝  ╚═╝╚═╝  ╚═══╝    ╚═╝      ╚═════╝ ╚═╝  ╚═╝╚══════╝╚═╝  ╚═

================
| Score :   0  |
================

[?] Enter 1 or 2: 1
[-] Player 2 wins! Your score is reseted...

Breakpoint 1, 0x00005555555562b5 in ?? ()
(gdb) p $eflags
$1 = [ CF AF SF IF ]
(gdb) set $eflags &= ~(1 << 7)
(gdb) p $eflags
$2 = [ CF AF IF ]
(gdb) c
Continuing.
[!] You got a FLAG! ctf4b{4ll_w3_h4v3_70_d3cide_1s_wh4t_t0_d0_w1th_7he_71m3_7h47_i5_g1v3n_u5}
[Inferior 1 (process 17068) exited normally]
```


# Leak
## 問題
```
medium
サーバーから不審な通信を検出しました！

調査したところさらに不審なファイルを発見したので、通信記録と合わせて解析してください。

機密情報が流出してしまったかも...？

Leak.tar.gz 490838f1586dc1a7a9347ea879beb78575555b88
```

## 解法
Ghidra でコードを読むと，入力で指定した IP アドレスのポート 5000 に ```/tmp/flag``` にある FLAG を暗号化して送信している．

暗号化では，以下のように用意した配列と XOR をとっているだけなので復号化も同じ処理をすれば良い．
```c
flag_data[i] = flag_data[i] ^
            abStack_118
            [(int)(uint)(byte)(abStack_118[(int)(uint)local_122] +
                                abStack_118[(int)(uint)local_123])];
```

wireshark で follow tcp としてデータを抜き出し，```/tmp/flag``` に書き込む．
```py
cipher = bytes.fromhex('8e57ff5945da900628b2abfa497332334a7329413c34b7f66273250f954016fa47e9228da5cd3d53eeb4b3518ed289935be059cbfbb11b')

f = open('/tmp/flag', 'wb')
f.write(cipher)
f.close()
```

```$ nc -lp 5000``` で接続を待って，ローカルに向けて実行する．

```
## ターミナル 1
$ nc -lp 5000

## ターミナル 2
$ ./leak
Enter IP address: 127.0.0.1
Data sent successfully

## ターミナル 1
$ nc -lp 5000
ctf4b{p4y_n0_4ttent10n_t0_t4at_m4n_beh1nd_t4e_cur4a1n}
```

# Heaven
## 問題
```
hard
メッセージを暗号化するプログラムを作りました。

解読してみてください！

Heaven.tar.gz f088ab04b586f9f424144dab142796cd3c8d333a
```

## 解法
Ghidra で読んでみる
```c
undefined8 main(void)

{
  undefined uVar1;
  byte bVar2;
  int iVar3;
  uint uVar4;
  uint uVar5;
  char *pcVar6;
  long lVar7;
  uint *puVar8;
  uint *puVar9;
  long lVar10;
  long lVar11;
  bool bVar12;
  undefined local_21;
  char local_20 [8];
  
  getrandom(&local_21,1,0);
  while( true ) {
    while( true ) {
      puts("------ menu ------");
      puts("0: encrypt message");
      puts("1: decrypt message");
      puts("2: exit");
      __printf_chk(1,&DAT_00402045);
      pcVar6 = fgets(local_20,8,stdin);
      if (pcVar6 == (char *)0x0) {
        return 0;
      }
      lVar7 = strtol(local_20,(char **)0x0,10);
      iVar3 = (int)lVar7;
      if (iVar3 != 1) break;
      puts("TODO: implement decrypt_message()");
    }
    if (iVar3 == 2) break;
    if (iVar3 == 0) {
      __printf_chk(1,"message: ");
      fgets(message,0x100,stdin);
      uVar1 = local_21;
      puVar9 = (uint *)message;
      do {
        puVar8 = puVar9;
        uVar4 = *puVar8 + 0xfefefeff & ~*puVar8;
        uVar5 = uVar4 & 0x80808080;
        puVar9 = puVar8 + 1;
      } while (uVar5 == 0);
      bVar12 = (uVar4 & 0x8080) == 0;
      if (bVar12) {
        uVar5 = uVar5 >> 0x10;
      }
      if (bVar12) {
        puVar9 = (uint *)((long)puVar8 + 6);
      }
      lVar7 = (long)puVar9 + (-0x4041c3 - (ulong)CARRY1((byte)uVar5,(byte)uVar5));
      if (lVar7 != 0) {
        lVar7 = lVar7 + -1;
        if (lVar7 != 0) {
          lVar10 = 0;
          do {
            lVar11 = lVar10 + 1;
            bVar2 = calc_xor(message[lVar10],uVar1);
            message[lVar10] = sbox[bVar2];
            lVar10 = lVar11;
          } while (lVar7 != lVar11);
        }
        __printf_chk(1,"encrypted message: %02x",local_21);
        print_hexdump(message,lVar7);
      }
    }
  }
  return 0;
}
```
とりあえず最初に ```getrandom(&local_21,1,0);``` でランダムな 1 バイトを取得している．

暗号化する際は，メッセージを受け取って色々しているが，デバッガで実行してみると，以下の部分に入るまでは入力したメッセージが書き換えられたりされていないことが分かった．
```c
if (lVar7 != 0) {
  lVar7 = lVar7 + -1;
  if (lVar7 != 0) {
    lVar10 = 0;
    do {
      lVar11 = lVar10 + 1;
      bVar2 = calc_xor(message[lVar10],uVar1);
      message[lVar10] = sbox[bVar2];
      lVar10 = lVar11;
    } while (lVar7 != lVar11);
  }
  __printf_chk(1,"encrypted message: %02x",local_21);
  print_hexdump(message,lVar7);
}
```
ここのループではメッセージを前から順に一文字ずつ処理している．
具体的には，その文字とランダムに得た固定の 1 バイトの値を XOR してその値を SBOX のインデックスとして変換している．

最後に出力は先頭にランダムな値を付け加えている．

よって SBOX の値は調べればわかるので，逆の処理をすれば良い．
ただ，このまますると ```bse3az...``` というのが得られて，どの文字も 1 ずつ減った値が得られてしまうので，最後にインクリメントだけする．(Ghidra の逆コンパイルでこの処理が現れていないのか，Solver を書き間違えているのかはわからなかった．．)

## Solver
```py
cipher = list(bytes.fromhex('ca6ae6e83d63c90bed34a8be8a0bfd3ded34f25034ec508ae8ec0b7f'))

data = open('./Heaven/heaven', 'rb').read()
sbox = list(data[0x3080:0x3080 + 256])

x = cipher[0]
flag = [0] * (len(cipher) - 1)
for i in range(len(flag)):
    for j in range(len(sbox)):
        if cipher[i + 1] == sbox[j]:
            idx = j
            break
    flag[i] = (idx ^ x) + 1

print(''.join(list(map(chr, flag))))
```

# おわりに
かなり頑張りはしましたが，全然手をつけられなかった問題もあったので，もっと早く解けるようにしたいです．
~~他のジャンルも，順次書き足していきたいと思います．~~
Crypto，Rev 以外のジャンルも，順次書き足していきたいと思ってはいます．