CpawCTF Writeup (2023年版)

## はじめに
初心者向けの常設CTFであるCpawCTFに3ヶ月ほどかけて細々と取り組み、ようやく全問解き終わりました。記念に初Writeupとして個人的に面白いと思った問題の解法メモを残しておきます。
解答自体は載せないため、現在挑戦中という人はこれを見て自力でチャレンジしてみてもよいかもしれません。

問題は2023年10月時点のもの、環境はWindows 11です。

## 解法メモ
### Q7. Can you execute?
ジャンルはReversing。問題文にある通り、拡張子を調べて適切なOSで実行することでフラグを得ることができる問題。
まずは拡張子を調べることになりますが、少しGoogle等で検索すれば `file` コマンドで調べられることがわかります。しかし、WindowsのコマンドプロンプトやPowerShellではこのコマンドは使えません。ではどうするか？
手っ取り早いのはWSLを有効にしてubuntuを使うか、Gitインストール時に同梱されているGitBashを使うことかと思います。

拡張子がわかれば後は適切なOSで実行するだけの簡単な問題ですが、これはリバースエンジニアリングの問題なので、今後の勉強もかねてGhidraでバイナリ解析をしてみました。

https://github.com/NationalSecurityAgency/ghidra

Ghidraの使い方は以下の記事を参考にしました。

https://www.ninjastars-net.com/entry/2019/03/08/200000

アセンブラを眺めていたら、プログラム開始時に実行される `main()` 関数に答えがありそうだと気づき、Webで検索して以下がわかりました。
- `putchar()` はC言語で1文字を出力する関数である
- `putchar()` はASCIIコードを引数に取れる
- `+ '\x16'` は10進数で22を足している

これらの情報を基に[ASCIIコード表](https://www.k-cube.co.jp/wakaba/server/ascii_code.html)で一文字ずつ変換すればフラグを入手できます。

<details><summary>main()関数の中身</summary><div>

```C
undefined8 main(void)

{
  int local_7c;
  undefined4 local_78 [4];
  undefined4 local_68;
  undefined4 local_64;
  undefined4 local_60;
  undefined4 local_5c;
  undefined4 local_58;
  undefined4 local_54;
  undefined4 local_50;
  undefined4 local_4c;
  undefined4 local_48;
  undefined4 local_44;
  undefined4 local_40;
  undefined4 local_3c;
  undefined4 local_38;
  undefined4 local_34;
  undefined4 local_30;
  undefined4 local_2c;
  undefined4 local_28;
  undefined4 local_24;
  undefined4 local_20;
  undefined4 local_1c;
  undefined4 local_18;
  undefined4 local_14;
  undefined4 local_10;
  
  local_78[0] = 0x4d;
  local_78[1] = 0x5a;
  local_78[2] = 0x4b;
  local_78[3] = 0x61;
  local_68 = 0x65;
  local_64 = 0x2e;
  local_60 = 0x59;
  local_5c = 0x49;
  local_58 = 99;
  local_54 = 0x59;
  local_50 = 0x5f;
  local_4c = 0x49;
  local_48 = 0x55;
  local_44 = 0x58;
  local_40 = 0x59;
  local_3c = 0x61;
  local_38 = 0x49;
  local_34 = 0x2f;
  local_30 = 0x36;
  local_2c = 0x30;
  local_28 = 0x49;
  local_24 = 0x50;
  local_20 = 0x53;
  local_1c = 0x56;
  local_18 = 0x4f;
  local_14 = 0x29;
  local_10 = 0x67;
  for (local_7c = 0; local_7c < 0x1b; local_7c = local_7c + 1) {
    putchar((int)(char)((char)local_78[local_7c] + '\x16'));
  }
  putchar(10);
  return 0;
}
```

</div></details>

### Q13. 隠されたフラグ
ジャンルはStego。問題文にある通り、画像の隅っこにあるフラグ自体はすぐに見つかります。この問題が面白かったのは、フラグを見つけた後に一体それが何を表しているのかを考えることだと思います。

<details><summary>画像の隅にある文字列 その1</summary><div>

`-.-. .--. .- .-- .... .. -.. -.. . -. ..--.-`

</div></details>

<details><summary>画像の隅にある文字列 その2</summary><div>

`-- . ... ... .- --. . ---... -.--.-`

</div></details>

「2種類の文字しか使われていない」というところがヒントです。最終的には[このページ](https://www.electronics-notes.com/articles/ham_radio/morse_code/characters-table-chart.php)を見て文字列を変換し、フラグをゲットしました。

### Q16. HttpTrafic
ジャンルはNetwork+Forensic。パケットキャプチャの定番ツールであるWireSharkのチュートリアル的な問題です。
実はこの問題が初めて自力で答えにたどり着けず解法を調べた問題でした。理由は、単純にWireSharkの使い方を知らなさ過ぎた、というところです。

この問題を解くには、WireSharkのエクスポート機能を使います。この機能を使うことで、パケットから元のWebページを構成するファイル群を復元することができます。
ただ、それだけでは解けず、パケットの情報を基にディレクトリ構造を組みなおす必要があります。適切なディレクトリ構造を復元すれば、htmlファイルからフラグを入手できます。

<details><summary>パケットに記録されたhtmlの一部</summary><div>

```
<p class="lead">フラグが欲しかったら下のボタンを押すんだ！！</p>
<p><img id="image1" class="img-rounded" id="image1" src="./img/image.jpg"/></p>
<p><a class="btn btn-large btn-success" onclick="OnButtonClick();">ボタン</a></p>
~~~~~
<script src="./js/button2.js"></script>
```

</div></details>

### Q18. leaf in forest
ジャンルはForensic。ファイルの中からフラグを見つけ出すだけの単純な問題ではある。`cat` でファイルの中身を確認し、あとはどう処理してフラグを見つけるかだが、今回は簡単なプログラムで特定の文字列を消してフラグを探してみることにした。プログラムはNimで書きました。

<details><summary>作成したプログラム</summary><div>

```nim
import os
import pegs
import strutils
import unicode

block:
  let f = open("misc100", FileMode.fmRead)
  defer:
    close(f)

  let text = f.readLine()
  let subtext = text.replace("lovelive!", "")

  echo subtext
```

</div></details>

ちなみに `flie` コマンドで調べるとまさかのパケットキャプチャファイルらしいが、WireSharkでは開くことができない。こういうファイルどうやって作るんだろ？

### Q20. Block Cipher
ジャンルはCrypto。与えられているC言語のソースコードはかなりシンプルですが、以下の知識が必要です（わからなかったので調べました）。

- `argc`と`argv`はコマンドライン引数
    - `argc`はコマンドライン引数の数を表す（この問題では使わない）
    - `argv`は各コマンドライン引数の値を表す
        - `argv[0]`は必ず実行するプログラムのパスが入る
- `atoi()`は文字列型をint型へ変換する関数

以上を踏まえると、このプログラムを実行するときに実際に入力するコマンドライン引数`argv[1]`と`argv[2]`がわかればこの問題は解けることになります。なんなら実行するのが早いです。
`argv[1]`が暗号文になるというのはすぐにわかると思いますが、問題は`argv[2]`で、こちらは特定の数字が入ります。適当に試してみてもいつかは解けますが、ここではソースコードから推測してみます。

- プログラムを読む限り、並べ替えである
- `i`と`j`と`key`の関係から、`key`の値ごとに文字を区切って逆向きに読めばよいことがわかる
- 暗号文に1文字だけある大文字が最初と考えるのが自然

以上でフラグを入手できます。

### Q21. reversing easy!
ジャンルはReversing。本来はこれが初めてバイナリ解析を行う問題なのだと思いますが、Q7で先にやってしまっており概ね手順はわかっていたので、今回もGhidraを使ってバイナリ解析を行い、フラグを生成している部分を探します。
この問題もプログラム開始時に実行される `main()` 関数でフラグを生成しています。

<details><summary>main()関数の中身</summary><div>

```C
undefined4 main(void)

{
  int in_GS_OFFSET;
  undefined2 local_4b;
  undefined local_49;
  int local_48;
  int local_44;
  int local_40 [4];
  undefined4 local_30;
  undefined4 local_2c;
  undefined4 local_28;
  undefined4 local_24;
  undefined4 local_20;
  undefined4 local_1a;
  undefined2 local_16;
  int local_14;
  
  local_14 = *(int *)(in_GS_OFFSET + 0x14);
  local_1a = 0x77617063;
  local_16 = 0x7b;
  local_40[0] = 0x79;
  local_40[1] = 0x61;
  local_40[2] = 0x6b;
  local_40[3] = 0x69;
  local_30 = 0x6e;
  local_2c = 0x69;
  local_28 = 0x6b;
  local_24 = 0x75;
  local_20 = 0x21;
  local_4b = 0xa7d;
  local_49 = 0;
  local_44 = 5;
  printf("%s",&local_1a);
  if (local_44 != 5) {
    for (local_48 = 0; local_48 < 9; local_48 = local_48 + 1) {
      putchar(local_40[local_48]);
    }
  }
  printf("%s",&local_4b);
  if (local_14 != *(int *)(in_GS_OFFSET + 0x14)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}
```

</div></details>

フラグ自体は入手できたのですが、正直アセンブラを読んでもなんでそのフラグでよいのか自身を持って説明できないので、この辺りはもっと勉強が必要そうです。

### Q23. またやらかした！
ジャンルはReversing。解法自体はQ21とほぼ変わりませんが、今回は暗号文を解くプログラムということで、単純にはフラグは入手できません。とりあえず例のごとく、Ghidraでバイナリ解析して `main()` 関数を確認します。

<details><summary>main()関数の中身</summary><div>

```C
undefined4 main(void)

{
  int iVar1;
  uint *puVar2;
  int local_84;
  uint local_7c [14];
  uint local_44 [14];
  
  local_7c[0] = 0x7a;
  local_7c[1] = 0x69;
  local_7c[2] = 0x78;
  local_7c[3] = 0x6e;
  local_7c[4] = 0x62;
  local_7c[5] = 0x6f;
  local_7c[6] = 0x7c;
  local_7c[7] = 0x6b;
  local_7c[8] = 0x77;
  local_7c[9] = 0x78;
  local_7c[10] = 0x74;
  local_7c[11] = 0x38;
  local_7c[12] = 0x38;
  local_7c[13] = 100;
  puVar2 = local_44;
  for (iVar1 = 0xe; iVar1 != 0; iVar1 = iVar1 + -1) {
    *puVar2 = 0;
    puVar2 = puVar2 + 1;
  }
  for (local_84 = 0; local_84 < 0xe; local_84 = local_84 + 1) {
    local_44[local_84] = local_7c[local_84] ^ 0x19;
  }
  return 0;
}
```

</div></details>

今までと異なる点として、for文の中に `^ 0x19` という計算があります。調べてみたところ、これはビット単位のXOR計算に相当するようです。そこで、以下のサイトを使って1つずつ計算すると以下のようになります。

https://yanohirota.com/bitwise-operator/

- 0x7a ^ 0x19 = 0x63 ==> c
- 0x69 ^ 0x19 = 0x70 ==> p
- 0x78 ^ 0x19 = 0x61 ==> a
- 0x6e ^ 0x19 = 0x77 ==> w

残りの計算も行ってフラグを入手します。なお、これはバーナム暗号といいます。

### Q.29 CommonWorld
ジャンルはCrypto。RSA暗号を解く問題です。サマーウォーズ！
とはいえ、RSAは現在最も使われている公開鍵暗号方式のアルゴリズムであり、そんな簡単に解けたら大問題です。`hint.txt` も読みましたが全く解き方の見当もつきません。
そんな時、当日参加できなかったSECCON Beginners Live 2023のアーカイブ動画を見ていたらちょうどCrypto入門があり、まさに似たような問題の解法が紹介されていました。
なお、このレベル（といってもまだまだ初心者レベル）のCryptoの問題を解こうと思うと、高等数学の知識が不可欠になってきます。

RSA暗号も万能ではなく、以下の脆弱性があります。

- Low Public-Exponent Attack
    - 公開鍵eが十分小さいとき、秘密鍵dを取得することなく平文mを復元できてしまう脆弱性
- Common Modulus Attack
    - 2組の公開鍵 (e1, N) (e2, N) と、それぞれに対応する暗号文 c1, c2 が与えられているとき、e1とe2が互いに素である場合、平文mが復元できてしまう脆弱性
    - e1とe2が互いに素であることにより、`e1s1 + e2s2 = 1`を満たす s1, s2 が存在するため、拡張ユークリッドの互除法により s1, s2 を求めることで、 `c1^s1 * c2^s2 = m^e1s1 * m^e2s2 = m^(e1s1+e2s2) = m`となる
- Hastad's Broadcast Attack
    - 平文mと単一の公開鍵eに対し、異なるNによって作られた暗号文cがe個あるとき、mを復元できてしまう脆弱性
    - 中国剰余定理を用いる

この問題では、問題文と`hint.txt`においてNが共通の2組の公開鍵が与えられており、かつe1とe2は互いに素であるため、Common Modulus Attackが成立します。あとはプログラムを作成して計算することでフラグを入手できます。

高等数学のプログラミングというとpythonが圧倒的にメジャーですが、今回はJuliaで実装しました。

<details><summary>作成したプログラム（関数部分のみ）</summary><div>

```julia
function exGCD(a, b)
  if b == 0
    return 1, 0, a
  end
  x, y, d = exGCD(b, a % b)
  x, y = y, x - div(a, b) * y
  println("(x, y, d) = ", (x, y, d))
  return x, y, d
end

function commonModulusAttack(n, e1, c1, e2, c2)
  s1, s2, d = exGCD(e1, e2)
  println("(s1, s2) = ", (s1, s2))
  return (powermod(c1, s1, n) * powermod(c2, s2, n)) % n
end
```

</div></details>

## おわりに
CTFは普段の業務で自分が携わることがないような技術領域のスキルや知識の底上げにはもってこいだと感じました。あと純粋に面白い。

今回のWriteupは面白い・興味深いと感じた問題だけpick upしましたが、振り返ると書いてるとReversingでバイナリ解析するのが楽しかったんだなーと思いました。

CpawCTFはまだまだBeginnerクラスなので、より難易度の高い問題を自力で解けるようスキルアップしていきたいですね。