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
2. Conquer
3. Choice
4. switchable_cat
5. cooking

Rev

1. Half
2. Three
3. Poker
4. Leak
5. 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

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

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

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

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 でゴリ押し (これでいいのかはわからない)

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 で見てみる

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

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 なのでシンボルが残っていないのでそれっぽい処理を探す)

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 なので両方が成り立たないようにデバッガで操作する．

フラグレジスタについて

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

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 をとっているだけなので復号化も同じ処理をすれば良い．

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 に書き込む．

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 で読んでみる

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 バイトを取得している．

暗号化する際は，メッセージを受け取って色々しているが，デバッガで実行してみると，以下の部分に入るまでは入力したメッセージが書き換えられたりされていないことが分かった．

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

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 以外のジャンルも，順次書き足していきたいと思ってはいます．